作者j0958322080 (Tidus)
看板Prob_Solve
標題Re: [問題] 解最小平方法的問題 Ax~b
時間Tue Jan 2 23:12:37 2018
http://web.mit.edu/ehliu/Public/Yelp/conditioning_and_precision.pdf
最近尋找了一下與這有相關的資料,有以下結論:
1. 直接解 Normal eq. --> 最爛
-1
2. x = A b
(1). 選 pivot 的高斯消去 --> 反解的時候會不穩定,
最好是消成約化梯式當聯立方程組去解。
(2). 選 pivot 的 LU 分解 --> 穩定,但是計算量滿大的,還算可以的方法。
3. QR 分解
(1). 一般的 Gram-schmidt --> 不穩定,但是好平行化
(2). 修正版 Gram-schmidt --> 比(1)穩定,但較不易平行化
(3). Householder --> 可以不用選 pivot 直接解,
選 pivot 也可以,但是計算量大。
4. SVD 分解 --> 最穩定,即便是rank-deficient,但是計算量最大。
T
以我們的問題來說 A A 必定為 Full-rank 的矩陣,應該不需要擔心rank-deficient。
所以大概就是以 SVD 跟 QR Householder(QRH) 之間做選擇。
我目前是使用 LU 分解在解這問題,之後會試試看 QRH 跟 SVD,
如果有人已經寫出來希望能夠分享經驗,謝謝。
看了一下 B-spline 的方法,這個方法有辦法得到誤差是最小的嗎??
另外梯度下降法應該會依賴於解猜得好不好吧??
--
!!!!!!!!!!!!!簽名檔破555000點擊率啦!!!!!!!!!!!!!!!
Fw: [問卦] 電影:決勝21點的機率問題
https://goo.gl/2BpbB7 #1MfN3FgZ (joke)
→ yeebon: chx64的1/2悖論真的很經典呢07/22 16:41
!!!!!!!!!!!!!!簽名檔破555000點擊率啦!!!!!!!!!!!!!!
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.247.167.2
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1514905961.A.4E0.html
※ 編輯: j0958322080 (27.247.167.2), 01/02/2018 23:13:23
推 DJWS: 感謝通知 01/03 09:11
→ DJWS: 連結裡面沒有提到SVD用了什麼算法 SVD和QR的算法都不只一種 01/03 09:13
推 DJWS: b-spline fitting 我沒有研究 無法回答 01/03 09:15
→ DJWS: 對稱正定矩陣是凸函數 梯度下降法不必用猜的 01/03 09:17
→ DJWS: 梯度共軛法甚至保證N步就得到答案(根本就是公式解了) 01/03 09:25
→ DJWS: ^^^^^^^^^^ 共軛梯度法 01/03 09:26
→ j0958322080: 這樣看起來這問題最佳解法應該是共軛梯度法了 01/03 10:30
→ j0958322080: 不過後來看一下應該是對於不同的條件有不同的step si 01/03 10:46
→ j0958322080: ze,所以不想繼續修改程式的話SVD或QR還是最佳選項 01/03 10:46