数值分析迭代法

华长生制作1在用直接法解线性方程组时要对系数矩阵不断变换如果方程组的阶数很高,则运算量将会很大并且大量占用计算机资源因此对线性方程组bAx要求找寻更经济、适用的数值解法--------(1)华长生制作2对于大型线形代数方程组，常用迭代解法。它是从某些初始向量出发，用设计好的步骤逐次算出近似解向量，从而得到向量序列。一般的计算公式是称之为多步迭代法．若只与有关，且是线性的，即)(kx)(kx)1(kx(1)()(1)()(,,,),,1,.kkkkmkxFxxxkmm)1(kx)(kxkF,1,0,)()1(kfxBxkkkk其中，称为单步线性迭代法，称为迭代距阵。若和都与k无关，即)(nnkRBkBkBkf,1,0,)()1(kfBxxkk称为单步定常线性迭代法。本章主要讨论具有这种形式的各种迭代方法。华长生制作3如果能将线性方程组(1)变换为xBxf--------(2),,nnnnBRfRxR其中(1)式和(2)式同解时,我们称(1)(2)等价对线性方程组(2),采用以下步骤:可得代入取初始向量),2(,)0(xfBxx)0()1(依此类推nnnnRxRbRA,,设华长生制作4fBxx)1()2(fBxxkk)()1(),2,1,0(k--------(3)这种方式就称为迭代法,以上过程称为迭代过程迭代法产生一个序列0)(}{kx如果其极限存在,即*)(limxxkk则称迭代法收敛,否则称为发散华长生制作5从(1)式出发，可以由不同的途径得到各种不同的等价方程组（2），从而得到不同的迭代法（3）。例如，设A可以分解为，其中M非奇异，则Ax=b等价于NMA.11bMNxMx令就可以得到（2）的形式。不同的分解方式，可的不同的B和f。,,11bMfNxMBNMA华长生制作6迭代法的收敛性设解线性方程组的迭代格式fBxxkk)()1(则而方程组的精确解为*,xfBxx**--------(10)--------(11)将(10)与(11)相减,得**)()1(BxBxxxkk*)()(xxBk*)()(xxkk令,2,1,0k华长生制作7则)()1(kkB)1(2kB)0(1kB为非零常数向量注意*)0()0(xx因此迭代法收敛的充要条件*)(limlim)1()1(xxkkkk00lim1kkB可转变为定理1.迭代格式(10)收敛的充要条件为0limkkB--------(12)华长生制作8由上节知0limkkB1小于的所有特征值的绝对值B即1)(B因此定理2.迭代格式(10)收敛的充要条件为--------(13)1)(B定理3对任意矩阵有()BBnnBR其中是任一矩阵范数。B华长生制作9定理4设有简单迭代法对任一种矩阵范数，只要迭代矩阵B满足，则该简单迭代法关于任意初始向量收敛。由于范数容易计算，故实用中用作为收敛的充分条件较为方便。10,1,2,kkxBxfk1B0x1,BB111B或B华长生制作10定理5.1,kBx设方程x=Bx+f有惟一解x,若则由简单迭代法产生的向量序列满足()()(1)1011kkkkkBxxxxBBxxxxB证明:*)(xxk)(*)()1()1(kkkxxxx*)(xxk)()1()1(*kkkxxxx)(*)()1()()(kkkxxBxxB华长生制作11*)(xxk)1()()(*kkkxxBxxB所以*)(xxk)1()(1kkxxBB运用()(1)()(2)()(2)110()()kkkkkkkxxBxxBxxBxx即可得（5.2.3），定理得证。即可得证第二式。华长生制作12定理说明，若但不接近1，则当相邻两次迭代向量和很接近时，与精确解很靠近。因此，在实际计算中，用作为迭代终止条件是合理的。1B)1(kx)(kx)(kx)()1(kkxx可见对给定的精度要求，可以得到需要迭代的次数，并且，越小，序列收敛越快。由于依赖于所选择的范数，而且，我们以给出收敛速度的概念。B)(kxBBB)()(B定义称为迭代法的渐进收敛速度。ln()B由此定义可以看出，越小，就越大。1)(B华长生制作13高斯-赛德尔迭代法及其收敛性设有简单迭代将迭代矩阵分解为其中10,1,2,kkxBxfkijnnBb12BBB1112121222121200,0nnnnnnbbbbbbBBbbb华长生制作14则将其修改为称之为由简单迭代法导出的高斯-赛德尔迭代法，简称高斯-赛德尔迭代法。其分量形式为1120,1,2,kkkxBxBxfk11120,1,2,kkkxBxBxfk11111,2,inkkkiijjijjijjixbxbxfi华长生制作15高斯-赛德尔迭代法的特点是：计算第i个分量时，前边的i-1个分量用的是最新算出来的而不是旧值，这样可能提高收敛速度。另外，该方法可以转化为简单迭代法的形式，故可以使用简单迭代法收敛性的各种判别方法。1kix1111,,kkixx11,,kkixx华长生制作16定理设简单迭代法的迭代矩阵满足则相应的高斯-赛德尔迭代法关于任意初始向量收敛。可见，简单迭代法与相应的高斯-赛德尔迭代法同时关于任意初始向量收敛。12BBB111,BB或111BB或时，1kkxBxf0,1,2,k