高等数值分析课程设计--求解线性方程组Ax=b的极小化方法比较

《高等数值分析课程设计--求解线性方程组Ax=b的极小化方法比较》由会员分享，可在线阅读，更多相关《高等数值分析课程设计--求解线性方程组Ax=b的极小化方法比较（15页珍藏版）》请在毕设资料网上搜索。

1、任课教师评语： 签名： 年 月 日 课程考核论文 课程名称：课程名称： 高等数值分析高等数值分析 论文题目：论文题目： 求解求解线性方程组线性方程组 Ax=b的的极极 小化方法比较小化方法比较 姓姓 名：名： 学学 号：号： 成成 绩：绩： 摘要摘要 本文对求解线性方程组 Ax=b 的极小化方法进行了理论上的阐述，并且选取 三种具有代表性的方法：最速下降法、共轭梯度法（CG） 、预处理共轭梯度法 （PCG） ，使用 Matlab 编程并分别求解相同的线性方程组，在准确性和收敛速度 方面进行比较。结果表明，如果预处理矩阵选择得当，使用预处理共轭梯度法 （PCG）效果最好。 1 1、 极小化方法极

2、小化方法 极小化方法的基本原理是变分原理。 设 A 对称正定，求解的方程组为 Axb (1.1) 其中() nn ij AaR ， 1 (,) T n xxx， 1 (,) T n bbb。考虑 2 次函数: n RR， 定义为 111 1 ()(,)( ,) 2 1 2 nnn ijijjj ijj xAx xb x ax xb x (1.2) 有如下性质 对一切 n xR， ()xA xb (1.3) 对一切, n x yRR， 2 1 ()(),)( ,) 2 =()(,)(,) 2 xyA xyxyb xy xAxb yAy y (1.4) 设 1 xAb 为(1.1)的解，则 11

3、11 ()( ,)(,) 22 xb AbxAx 而且对一切 n xR，有 11 ()()(,)(,)(,) 22 1 (),) 2 xxAx xAxxAxx A xxxx (1.5) 则有定理：设 A 对称正定，则x 为（1.1）解的充分必要条件是x 满足 ()m in() n xR xx 求 n xR，使()x取最小，这就是求解等价于方程组（1.1）的变分问题。求解 的方法一般是构造一个向量序列 ()k x，使 () ()min( ) k xx。 1.1 最速下降法最速下降法 可通过求泛函()x的极小点来获得式（1.1）的解。为此，可以从任一 ()k x出 发，沿着泛函()x在 ()k x

4、处下降最快的方向搜索下一个近似点 (1)k x ，使得 (1 ) () k x 在该方向上达到极小值。 由多元微积分知识，()x在 ()k x处下降最快的方向是在该点的负梯度方向， 经过简单计算，得： () ()() ( ) |: k kk xx xbAxr , 此处， ()k r也称为近似点 ()k x对应的残量。取 (1)()()kkk xxr ， 确定的值使 (1) () k x 取得极小值。由式（1.4） ，令 ()() (+ 0 kk dxr d , 得 ()()()() (,)(,)0 kkkk rrArr 从上式求出并记为 k ： ()() ()() (,) (,) kk k k

5、k rr Arr (1.6) 综合上述推导过程，可得最速下降法的算法描述： 给定初始点 0 n xR，容许误差0，置:0k 。 计算 ()()kk rbAx，若 ()k r，停算，输出 ()k x作为近似解。 按式（1.6）计算步长因子 k ，置 (1)()()kkk k xxr ，:1kk，转步骤 。 最速下降法在理论上是可以收敛的，但是收敛可能会比较缓慢，而且由于舍 入误差存在，实际算出的 ()k r与理论上的最速下降方向可能有很大差别，使计算 时出现数值不稳定性。最速下降法在现代科学与工程中不再具有实用价值。 1.2 共轭梯度法（共轭梯度法（CG） 当线性方程组 Ax=b 的系数矩阵 A 是对称正定矩阵， 可以采用共轭梯度法对 该方程组进行求解，可以证明，式(1.7)所示的 n元二次函数 1 () 2 TT fxxAxbx (1.7) 取得极小值点 x*是方程 Ax=b 的解。共轭梯度法是把求解线性方程组的问题转化 为求解一个与之等价的二次函数极小化的问题。从任意给定的初始点出发，沿一 组关于矩阵 A 的共轭方向进行线性搜索，在无舍入误差的假定下，最多迭代 n次 （其中 n 为矩阵 A 的阶数） ，就可求得二次函数的极小点，也就求得线性方程组 Ax = b 的解。其迭代格式为公