作者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)
1F：→ yeebon: chx64的1/2悖论真的很经典呢07/22 16:41
！！！！！！！！！！！！！！签名档破555000点击率啦！！！！！！！！！！！！！！
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 27.247.167.2
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1514905961.A.4E0.html
※ 编辑: j0958322080 (27.247.167.2), 01/02/2018 23:13:23
2F：推 DJWS: 感谢通知 01/03 09:11
3F：→ DJWS: 连结里面没有提到SVD用了什麽算法 SVD和QR的算法都不只一种 01/03 09:13
4F：推 DJWS: b-spline fitting 我没有研究 无法回答 01/03 09:15
5F：→ DJWS: 对称正定矩阵是凸函数 梯度下降法不必用猜的 01/03 09:17
7F：→ DJWS: 梯度共轭法甚至保证N步就得到答案(根本就是公式解了) 01/03 09:25
8F：→ DJWS: ^^^^^^^^^^ 共轭梯度法 01/03 09:26
9F：→ j0958322080: 这样看起来这问题最佳解法应该是共轭梯度法了 01/03 10:30
10F：→ j0958322080: 不过後来看一下应该是对於不同的条件有不同的step si 01/03 10:46
11F：→ j0958322080: ze，所以不想继续修改程式的话SVD或QR还是最佳选项 01/03 10:46