作者as7218 (Kaigiks)
看板Math
標題Re: [線代] 最小平方法與對稱方陣的問題
時間Wed Jan 3 15:08:03 2018
來獻醜一下...(′・ω・‵)
底下講的都是 full column rank 的情況。
※ 引述《j0958322080 (Tidus)》之銘言：
: 標題: [線代] 最小平方法與對稱方陣的問題
: 時間: Mon Jan 1 18:50:18 2018
: 在解最小平方法問題 Ax ~ b 時，(A 屬於 M (R))
: m x n
: T T
: 最後得到的解就是 x = (A * A) * A b，
: T T
: 想問一下為什麼不能直接從 (A * A)x = A b 解，
其實可以，畢竟數學上這麼做是對的，只是通常不會這麼做。
理由有很多種，其中一種是用這個方式解出來的解容易不準。
尤其如果 A 本身越接近 singular，本來就已經不容易準了，
解 normal equation 出來會更慘。
至於原因，只要數值計算相關的書都會提到，因為 condition number 會變大。
condition number 越大，這個問題就越敏感 (sensitive)，
也就是只要問題稍微擾動一點，解出來的解相對誤差會差很多。
（而且擾動誤差是沒辦法避免的，因為浮點數設計上就是會有）
可以用 normal equation + condition number 做關鍵字去 google，
能查到很多寫的不錯的 lecture，這裏就不贅述了。
:
: 這樣不就只是一個聯立方程組而已嗎??
:
: 我看在計算數學中解這問題通常會使用 QR 分解，
: T -1
: 其中 Q = Q = Q ，所以把 A 拆解成 QR 矩陣的乘積，可得
: T T T T T T
: (A * A)x = A b --> (QR) QRx = (QR) b -->R Rx = (QR) b
這裡，因為不知道你是故意這麼寫的，所以提醒一下。
實務上 QR 分解後不會像這邊這樣寫的去解。
例如 m ≧n 時, 我們會把 A 分解成
┌ R1 ┐
A = QR = [ Q1 Q2 ]│ │ = Q1 R1. （其中 Q, R1 分別是 m x m, n x n 方陣）
└ 0 ┘
最小平方問題會變成
|| R1 x - Q1^T b ||
|| Ax - b || = || Q^T (A x - b) || = || ||
|| Q2^T b ||
上面最小值發生於 R1 x = Q1^T b 時，因此原問題轉為解這個聯立方程組。
不會去解你上面寫的 R^T R x = (QR)^T b，
除了計算量，還有上面提到解 normal equation 的原因是一樣的。
（解這個，和解原本的 normal equation 意思差不多，失去做 QR 的意義...）
:
: （中略）
:
: → j0958322080 : QR分解最後是解聯立方程還是也是要算反矩陣?? 01/02 23:14
數學上，解聯立方程組和算反矩陣是等價的問題。
但算出反矩陣問題很多：
1. 只要用浮點數去存基本上都是近似解，再去乘回原方程組又會產生誤差、
2. 耗費空間儲存反矩陣、
3. 計算量超高。
所以不會這麼做。
直接用高斯消去法 + backward substitution 去解就好了。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.30.202.147
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1514963286.A.033.html
※ 編輯: as7218 (61.30.202.147), 01/03/2018 15:11:30
推 j0958322080 : 太感謝了，目前是用LU分解去做這個問題，之後應該會 01/03 15:57
→ j0958322080 : 使用QR分解去解。SVD解這問題應該是最穩定的，只是 01/03 15:57
→ j0958322080 : 計算量大。這個問題我有在計算數學版(prob_solve)與 01/03 15:57
→ j0958322080 : 其他人討論，如果有空的話也可以去那邊討論，因為這 01/03 15:57
→ j0958322080 : 問題比較多在計算上面，數學問題倒是沒這麼大 01/03 15:57
推 annboy : 長知識推 01/03 20:01