Re: [問題] 解最小平方法的問題 Ax~b

[DJWS (...)]

※ 引述《j0958322080 (Tidus)》之銘言：
: 我想要去FIT一條四次方的曲線，其中 x 的值為50000左右，
: 依照理論我會用到x^4，這樣整個矩陣A*A^T的最大值與最小值會差到40次方，
: 我自己寫了一個程式用 LU 分解去計算反矩陣，求得的反矩陣跟 EXCEL 的結果完全一樣，
: 可是我發現那兩個矩陣(A*A^T)和(A*A^T)^-1在 EXCEL 裡面乘起來不是單位矩陣，
: 而且有些非對角線元素甚至達到10^8，這樣的結果不知道是否會與我想要的解差很多??
: 因為目前只有想到用反矩陣解，不知道有沒有什麼比較好的演算法可以解的比較精確??

先講結論：我也不知道

稍微幫忙整理一下資訊

1. 我看過的大學課程資料，通通沒有提過這件事。

2. 這網頁的reference列了很多書，我沒有全部讀過，所以可能最近幾天翻一翻吧。
　 http://mathworld.wolfram.com/LeastSquaresFitting.html

3. 如果這些書都沒有答案，那答案可能藏在論文、專利、專案裡面。
　 這種情況嘛，除非去找專家，要不然光靠自己應該是找不到答案。
　 可能要去專業討論區發問吧，例如這種的：
 　https://math.stackexchange.com/questions/tagged/numerical-methods

4. 解least square的方法（資料量從少到多，速度從慢到快，精確度從高到低）
   (1) 公式解(Normal Equation/QR/SVD)
　 (2) 梯度下降法/遞推法(Levenberg-Marquardt Algorithm/Conjugate Gradient)
　　　 主要是針對正定矩陣進行加速
　 (3) 隨機取樣(RANSAC/Iterative Closest Point)
　　   隨便抓5點，然後做多項式內插。
　     然後重複這個步驟很多次，從中找到最好的那個多項式。

　 實際應用幾乎都是(2)(3)，所以很難找到(1)的討論。尤其又是四次多項式...

5. 說到FIT四次方曲線，有一個非常接近的東西叫做 bezier curve fitting
   因為貝茲曲線很有名，所以資料應該滿多的，我猜可以往這方面去找。

6. 說到多項式內插，谷歌一下就有討論精確度的論文了，還滿好找的：
   http://www.sciencedirect.com/science/article/pii/S0024379505004520


我也想知道答案是什麼。如果你找到答案了，希望可以ＣＣ給我，謝謝！

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.137.8.87
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1514178553.A.7FC.html
推 j0958322080: 我覺得這誤差應該跟計算太多次有關係，目前在想是否
→ j0958322080: 可以利用什麼數學定理來減少計算量。不過梯度下降法
→ j0958322080: 我之前以為只是要得到最小誤差的理論推導而已，之後
→ j0958322080: 會試試看這個演算法和QR分解，感謝
推 j0958322080: 我剛剛看了一下，最好的方法是把A做QR分解，整個問題
→ j0958322080: 就只剩下 Qx = Rb，剩下解線性方城組就好