江苏龙网

  1. 首页 > 生活 > >

用共轭梯度法解形如 Ax = b 的方程时有啥优点

一般来说，迭代法的优点是灵活，这包括占用存储空间比较小，对稀疏矩阵可以显著提升，以及对于并不要求精确解时可以在（相比直接法）较短的时间内给出在允许误差范围内的一个解，另外，对于不依赖于迭代顺序的迭代法，还可以并行或者分布式计算。在常用的迭代算法中，共轭梯度法大概是唯一一个理论上在有限步以内就可以得到解的方法（当然实际上由于计算误差并不能做到），就凭这一点就决定了它在处理正定阵时是应当优先考虑的迭代算法
■网友
参照wiki中对于CG法的描述可以知道，“大型，稀疏”是两个很关键的特征，也是CG法擅长的地方。其次，直接求逆和线性方程组的直接解法应该是两种不同的表述，因为对于矩阵求逆其实也是一个比较困难的事情，尤其是在阶数较高的情况，在Matlab中也并不建议使用inv(A)*b的来求解线性方程组，而是使用A\\b或mldivide(A,B)。
然后再说Matlab中的A\\b或mldivide(A,B)，这货并不是一种算法而是一类算法的集合，参照官网文档。文档中说对于full形式的矩阵（Matlab中默认的矩阵类型），可能涉及的求解算法包括以下:QR solver, triangular solver, permuted triangular sovler, Hessenberg solver, LU solver, LDL solver, Cholesky solver.
其次，CG法有很多的类型，这个可以参照Matlab中CG法相关的函数，比如bicg,bicgstab,bicgstabl,pcg,cgs等，它们都属于CG类的方法。值得注意的是，它们在help文档中的例子基本上使用的都是稀疏矩阵(sparse)。
最后回答题主对于非稀疏矩阵A，A\\b和CG的对比。我进行了一个两种方法的对比测试。矩阵大小分别为10,50,100,200,500,1000,2000,5000，并且均是对称正定的，CG法采用的是cgs（其他bicg,pcg等在这种简单测试中差距并不大）。
用共轭梯度法解形如 Ax = b 的方程时有啥优点

Fig 1 不同阶数的矩阵A，A\\b结果的残差范数用共轭梯度法解形如 Ax = b 的方程时有啥优点

Fig 2 不同阶数的矩阵A的两种方法耗时对比最后总的来说，Matlab对于A\\b的优化简直丧心病狂，无论速度还是精度均是比较好。我猜测对于矩阵的阶数更大的情况，CG法应该是占优势的，因为CG法在理论上不考略舍入误差的情况下，最大迭代步数（矩阵的阶数）即可得到精确解，并且其复杂度为O(N^2)。另外说一下，Matlab对于稀疏矩阵A\\b优化的也是非常丧心病狂，感兴趣的同学可以测试一下。至于到底CG法在什么时候会反超A\\b，有心者可以自己进行一下试验，顺便告诉我 。
下面附上测试的Matlab代码，本次测试是在2015年Macbook Air。
%matlab求解线性方程组性能测试：A\\b与cg%精确解是各个分量为1%比较A\\b和cg法之间的速度和精度%测试机器2015年macbook airclear,clct=cell(2,8);e1=cell(2,8);e2=cell(2,8);%测试矩阵A的维数为10,50,100,200,500,1000,2000，5000Asize=;for i=1:8 A=diag(rand(1,Asize(i))); M=rand(Asize(i)); =qr(M); A=Q*A*Q\u0026#39;; b=sum(A,2); tic x1=A\\b; e1{1,i}=norm(b-A*x1); t{1,i}=toc; tic =cgs(A,b,1e-10,Asize(i)); t{2,i}=toc;end
■网友
用于解维度高的稀疏线性方程组（当 Cholesky 分解计算上不可行时），且数值比较稳定。
【用共轭梯度法解形如 Ax = b 的方程时有啥优点】 也可以在解无约束的优化问题时用来求解梯度下降方向（牛顿共轭梯度法；Newton CG method）或用来在置信域内求解下一迭代的点（Steihaug truncated CG step）。


    推荐阅读


    上一篇：你心目中最想要但还未开发出来的app是怎么样的

    下一篇：unix/linux IPC机制对象(如:信号量,共享内存等),为啥没有引用计数?应该咋使用这些对象?