PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] 降低 QR 分解的演算複雜度

看板Prob_Solve (計算數學 Problem Solving)作者 (Tidus)時間6年前 (2018/04/05 02:06), 編輯推噓5(5推 0噓 12→)
留言17則, 4人參與, 6年前最新討論串1/1
之前在解最小平方法寫了 QR 分解，(A 為 m by n 的矩陣) 雖然寫得出來，可是演算複雜度高達 O(m*m*n*n)， 看書上是寫演算複雜度是 O(m*n*n)， 主要是因為要一直重複矩陣乘法，所以沒辦法很快。 code 如下 http://codepad.org/DsAtdHDK 感謝各位 -- ！！！！！！！！！！！！！簽名檔破555000點擊率啦！！！！！！！！！！！！！！！ Fw: [問卦] 電影：決勝21點的機率問題 https://goo.gl/2BpbB7 #1MfN3FgZ (joke)
→
07/22 16:41,
chx64的1/2悖論真的很經典呢
07/22 16:41
！！！！！！！！！！！！！！簽名檔破555000點擊率啦！！！！！！！！！！！！！！ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.12.74.14 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1522865204.A.4CE.html
推
04/05 07:05, 6年前 , 1F
剛剛找了一些資料 真的都沒講到 Q = H1...Hn 應該怎麼乘
04/05 07:05, 1F
→
04/05 07:18, 6年前 , 2F
04/05 07:18, 2F
→
04/05 07:21, 6年前 , 3F
最後一頁上半部有講怎麼乘
04/05 07:21, 3F
→
04/05 09:18, 6年前 , 4F
我是已經這樣算了，但這樣複雜度還是O(m*m*n*n)
04/05 09:18, 4F
→
04/05 09:20, 6年前 , 5F
QR分解裡面的迴圈都是從 k 開始不是從 1 開始
04/05 09:20, 5F
→
04/05 09:44, 6年前 , 6F
平行?
04/05 09:44, 6F
推
04/05 10:28, 6年前 , 7F
在 DJWS 提供的資料的 6-31 頁第一個公式？
04/05 10:28, 7F
→
04/05 14:04, 6年前 , 8F
好像沒辦法這樣算耶，要先把 H 算出來才可以乘 A
04/05 14:04, 8F
推
04/05 20:19, 6年前 , 9F
QR分解裡面的迴圈確實是從k開始 算Q的時候卻不是從k開始
04/05 20:19, 9F
→
04/05 20:26, 6年前 , 10F
Q其實也可以從 k 開始，因為拆成方塊矩陣後左上角的
04/05 20:26, 10F
→
04/05 20:26, 6年前 , 11F
是單位矩陣，所以只需要乘右下角的矩陣，但這樣複雜
04/05 20:26, 11F
→
04/05 20:26, 6年前 , 12F
度還是m*m*n*n
04/05 20:26, 12F
推
04/05 20:36, 6年前 , 13F
然後如同FRAXIS所說的 公式裡的點積 看起來必須預先計算
04/05 20:36, 13F
→
04/05 20:38, 6年前 , 14F
vk^T dot x_k:m 應該要預先計算
04/05 20:38, 14F
→
04/05 20:38, 6年前 , 15F
修正 vk dot x_k:m 應該要預先計算
04/05 20:38, 15F
→
04/09 21:14, 6年前 , 16F
這樣感覺有點像是用空間換時間??
04/09 21:14, 16F
推
04/10 05:25, 6年前 , 17F
對
04/10 05:25, 17F
‣ 更多 j0958322080 的文章
文章代碼(AID): #1QnHGqJE (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 j0958322080 的文章
文章代碼(AID): #1QnHGqJE (Prob_Solve)