→ yeebon: chx64的1/2悖論真的很經典呢07/22 16:41
!!!!!!!!!!!!!!簽名檔破555000點擊率啦!!!!!!!!!!!!!!
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.12.74.14
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1522762518.A.A1B.html
※ 編輯: j0958322080 (39.12.74.14), 04/03/2018 21:41:28
※ 編輯: j0958322080 (39.12.74.14), 04/03/2018 21:41:58
※ 發信站: 批踢踢實業坊(ptt.cc)
※ 轉錄者: j0958322080 (39.12.74.14), 04/03/2018 21:55:49
※ [本文轉錄自 Prob_Solve 看板 #1QmuCMeR ]
作者: j0958322080 (Tidus) 看板: Prob_Solve
標題: [問題] QR 分解如何寫出 O(n^3)
時間: Tue Apr 3 21:35:15 2018
之前在解最小平方法問題時需要使用此演算法,
不過在寫的時候因為需要寫到四個迴圈,複雜度是 O(m^2n^2),
所以矩陣一大速度就變得很慢,
我看許多數值計算的書寫此演算法的演算複雜度是 O(mn^2),
主要是因為要利用分解出來的 Q 矩陣將 A 分解成上三角矩陣 R,
R = Qn...Q2Q1A
這一步需要用到矩陣相乘,又要一直去找到 Qi 矩陣就需要用到四個迴圈,
速度會比單純使用 LU 分解慢很多。
還沒想到只需要用到三個迴圈的方法,不知道各位是怎麼寫這個演算法的??
Algorithm : A is an m by n matrix
for k=1:n
for i=k:m
compute norm
for i=k:m
for j=k:m
compute Q matrix
for i=k:m
for j=k:m
for h=k:n
compute R matrix
--
!!!!!!!!!!!!!簽名檔破555000點擊率啦!!!!!!!!!!!!!!!
Fw: [問卦] 電影:決勝21點的機率問題 https://goo.gl/2BpbB7 #1MfN3FgZ (joke)