【Water】由AX = B求解谈起

Quixote

在求解AX=B时候，用最原始的高斯淘汰法，会导致截断误差以及舍入误差的出现。但在用迭代法的时候，主元全得保证非零这里，有点蛋疼。我想了两种方法，一种是直接用高斯-约当方法进行行变换，但这样时间的浪费就是第一步加第二步，虽然一定能保证有解。另外一种方式是将每列的有效行进行存储，然后从最小有效开始进行处理，但这样写逻辑复杂，而且极度蛋疼，空间复杂度随着n指数式增长。虽然一觉睡醒，想到了两个迭代一起进行，但这样的话收敛速度就又是个噩梦。
所以我想问问大家在对于主元的处理上有什么好的方法，或者使用了另外的不产生严重的舍入误差又能快速收敛且时间复杂度不可怕的运算么？


补充内容 (2015-2-15 02:56):
问题解决，一句话。迭代法的收敛性与直接法的稳定性，我选择了后者。并做了一定的改动，达到了0.0001的精度。

Quixote

天荒地老

看不懂还是帮顶一下贴吧

Quixote

洅迲愛伱辰 发表于 2015-2-11 15:43
不知道arm公司提供的dsp库里面是不是有这个 方程解算的函数

arm的CMSIS里面的求解线性方程组Demo的代码比我写的代码还要渣。

Quixote

黑色密码 发表于 2015-2-11 15:55
不明觉厉！
我不知道你所说的高斯法以及高斯约当法是什么意思，反正和我所学有些许不同。
高斯法、高斯约 ...

不然的话就如同我能知道这个现在不能做，但没有办法让他能去做。此外，直接法得不到精确解。如果你真的写过这个程序用单纯的汇编，你会发现无法解决舍入误差。尤其是小主元问题，虽然可以通过列主元勉强解决，但在高阶稀疏矩阵是不可解得精确解的。

Quixote

黑色密码 发表于 2015-2-11 15:55
不明觉厉！
我不知道你所说的高斯法以及高斯约当法是什么意思，反正和我所学有些许不同。
高斯法、高斯约 ...

迭代法要求谱半径小于1，首先不讨论这个求特征值的可行性。主要是如何保证全部收敛的措施。

sonchen双子

完全看不懂，，，大神就是吊。。。

lihuanhuan

                                                      

Okabe

黑色密码这个ID就本身很带数理逻辑的感觉，再看发的贴果然是有干货的，厉害，学习了

仰望，蘫迗

看到LZ我惊呆了，看到楼上吓得我都不敢说话了- -

黑色密码

不明觉厉！
我不知道你所说的高斯法以及高斯约当法是什么意思，反正和我所学有些许不同。
高斯法、高斯约当法是类似的，都是模拟手工解线性方程组的方法，因此可以求出准确解！
高斯法将方阵A化为上三角阵后继续化为对角阵，直接得结果。
高斯约当法只化为上三角阵，进而将未知元的值进行回代。
而迭代法（简单迭代和Gauss-Seidel迭代）确实会因为主元为零而产生蛋疼的问题。（就算主元非零还会有不收敛的问题）
我最先想到的是L-U分解来做，后来想了一下，其实和高斯约当法没太大区别，因为分解完相当于可以做一个可逆线性变换转换成类似高斯约当法结果的上三角阵，然后需要回代两次，但是好处是你可以很快完成分解。
总的来说这几种方法（实际上是四种：高斯，高斯约当，L-U（其中对A的L-U分解有Dolittle和Crout两种方式，差不多））都是数值计算中常用解法，保证相同的精度并且足够快（肯定比Crammer法则快得多了）。
从我的角度来说这几种方法我都用过，速度是差不多的，如果要再快你就想办法解决迭代主元的问题，实质上是矩阵范数的问题。