1、科大研究生学位课程1第第2 2章章 解线性方程组的迭代法解线性方程组的迭代法n元线性方程组nnnnnnnnnnbxaxaxabxaxaxabxaxaxa.22112222212111212111（2.1）或 Ax=b思思路路与解与解 f(x)=0 的不动点迭代相似的不动点迭代相似,将将Ax=b等价改写为等价改写为x=Mx+f,建立迭代建立迭代x(k+1)=Mx(k)+f,从从初值初值x(0)出发，得到序列出发，得到序列x(k).研究研究 内容：内容：如何建立迭代格式？如何建立迭代格式？收敛速度？收敛速度？向量序列的收敛条件？向量序列的收敛条件？误差估计？误差估计？（2.2）科大研究生学位课程2
2、2.1 迭代法的一般理论 为了研究线性方程组近似解的误差估计和迭代法的收敛性，我们需要对Rn(n维向量空间)中的向量或Rnxn中矩阵的“大小”引入一种度量，向量和矩阵的范数。在一维数轴上，实轴上任意一点x到原点的距离用|x|表示。而任意两点x1，x2之间距离用|x1-x2|表示。科大研究生学位课程3向量和矩阵的范数 而在二维平面上，平面上任意一点P(x,y)到原点的距离用 表示。而平面上任意两点P1(x1,y1),P2(x2,y2)的距离用 表示。推广到n维空间，则称为向量范数。|22OPyx22122121)()(|yyxxPP科大研究生学位课程42.1.1 2.1.1 向量和矩阵的范数向量
3、和矩阵的范数向量的范数向量的范数 定义定义2.2 2.2 设是向量空间Rn上的实值函数,且满足条件:(1)非负性非负性:对任何向量xRn,x0,且x=0当 且仅当x=0 0 (2)齐次性齐次性:对任何向量x Rn 和实数,x=|x (3)三角不等式三角不等式:对任何向量x,yRn x+yx+y则称为空间Rn上的范数,x为向量x的范数.科大研究生学位课程5 记x=(x1,x2,xn)T,常用的向量范数有:向量的向量的1-1-范数范数:x1=|x1|+|x2|+|xn|向量的向量的2-2-范数范数:x2=22221nxxx 向量的向量的-范数范数:x=|max1inix 例例 设向量x=(2,-4
4、,3,1)T,求向量范数xp,p=1,2,.解解 由定义x1=10,x2=30,x=4.虽然不同范数的值可能不同，但它们间存在等价关系.定理定理 (范数的等价性范数的等价性)对于 Rn 上的任何两种范数和,存在正常数m,M,使得 m x x M x,xRn科大研究生学位课程6 常用的三种向量范数满足如下等价关系 x x1 nx,xRnnRnxxxx,2nRnxxxx,212 定义定义 设向量序列,),()()(2)(1)(Tknkkkxxxx k=1,2,向量,),(*2*1*Tnxxxx如果 0lim*)(xxkk则称向量序列x(k)收敛于向量x*,记作 )(,lim*)(*)(kkkkxx
5、xx或易见,nixxikik,2,1,*)(*)(xx科大研究生学位课程72.2.矩阵的范数矩阵的范数 定义定义2.3 2.3 设是以n阶方阵为变量的实值函数,且满足条件:(1)非负性非负性:A0,且A=0当且仅当A=0 0 (2)齐次性齐次性:A=|A,R (3)三角不等式三角不等式:A+BA+B (4)相容性相容性:ABAB则称A为矩阵A的范数.记A=(aij),常用的矩阵范数有:矩阵的矩阵的1-1-范数范数:A1 niijnja11max,也称矩阵的列范数列范数.矩阵的矩阵的2-2-范数范数:A2)(maxAAT,也称为谱范数谱范数.科大研究生学位课程8 矩阵的矩阵的-范数范数:A nj
6、ijnia11max,也称为行范数行范数.矩阵的矩阵的F F-范数范数:AF njiija1,2例例 设矩阵3211A求矩阵A的范数Ap,p=1,2,F.解解 A1=4,A=5,AF 151055532113121AAT010555令25515,25515,21得255152A所以科大研究生学位课程9 设是一种向量范数,则定义AxxAxAx0 x1maxmax 称之为由向量范数派生的矩阵算子范数矩阵算子范数.矩阵的算子范数满足 AxAx,xRn把满足上式的矩阵范数称为与向量范数与向量范数相容相容的矩阵范数的矩阵范数.对于p=1,2,矩阵范数Ap是由向量范数xp派生的矩阵算子范数,所以Ap是与x
7、p相容的矩阵范数.但AF不是一种算子范数,却与x2是相容的.设是一种算子范数,则1max xxII0 xnIF，但科大研究生学位课程10 矩阵的范数与矩阵的特征值之间也有密切的联系.设是矩阵A的特征值,x是对应的特征向量,则有 Ax=x利用向量和矩阵范数的相容性,则得|x=x=AxAx 于是|A 设n阶矩阵A的n个特征值为1,2,n,则称 ini1max)(A为矩阵A的谱半径谱半径.对矩阵的任何一种相容范数都有 (A)A 另外,0,一种相容范数,使 A(A)+科大研究生学位课程11 任何两种矩阵范数也具有等价性 m A A M A,ARnn 矩阵序列的收敛性也定义为矩阵序列的收敛性也定义为0l
8、imlim*)(*)(AAAAkkkk njiaaijkij,1,*)(。的充分必要条件是则设定理1)(0lim,AkAkRAnn科大研究生学位课程1212.3:|1,1|()|1|AIAIAA定理如果则为非奇异，且000det(-)0(-)00IAIA xxAxx证明：（反证法）若有非零解，即，使得0000|1|AxAxAxx而|1,A从而与假设矛盾-1(-)(-)IA IAI又11()()I IAA IAI11()()IAIA IA11|()|()|IAIAIA11|()|1|IAA科大研究生学位课程13把n元线性方程组nnnnnnnnnnbxaxaxabxaxaxabxaxaxa.221
9、12222212111212111（2.1）或 Ax=b改写成等价的方程组 nnnnnnnnnnnfxmxmxmxfxmxmxmxfxmxmxmx2211222221212112121111 或 x=Mx+f2.1.2 迭代格式的构造（2.2）科大研究生学位课程14由此建立方程组的迭代格式 x(k+1)=Mx(k)+f,k=0,1,2,(2.5)其中M称为迭代矩阵迭代矩阵。对任意取定的初始向量x(0),由(2.5)式可逐次算出迭代向量x(k),k=1,2,如果向量序列x(k)收敛于x*,由(2.5)式可得 x*=Mx*+f 从而x*是方程组x=Mx+f 的解,也就是方程组Ax=b的解.对迭代格
10、式(2.5),定义误差向量 e(k)=x(k)-x*,则迭代法收敛就是e(k)0 0.由于 x(k+1)=Mx(k)+f k=0,1,2,x*=Mx*+f k=0,1,2,科大研究生学位课程15 x(k+1)=Mx(k)+f k=0,1,2,x*=Mx*+f k=0,1,2,所以 e(k+1)=Me(k),k=0,1,2,递推可得 e(k)=Mke(0),k=0,1,2,可见,当k时,e e(k)0 0 Mk O O.对任意初始向量x(0),迭代法收敛(M)1.定理定理2.4证证:(必要性）若(M)0,使得(M)+1.则由定理2.2MkMk(M)+)k 0.若Mk0,k(M)=(Mk)Mk0,
11、所以(M)1.科大研究生学位课程16 若若M1,则对任意x(0),迭代法收敛,而且 定理定理2.5-6)9.2(0)(1)k*(k)xxM1Mxx)10.2(1)1()(*)(kkkxxMMxx 证证 由于 x(k+1)=Mx(k)+f,x(k)=Mx(k-1)+f x*=Mx*+f所以 x(k+1)-x(k)=M(x(k)-x(k-1),x(k+1)x*=M(x(k)x*)于是有 x(k+1)-x(k)Mx(k)-x(k-1)x(k+1)x*Mx(k)x*x(k+1)-x(k)=(x(k+1)x*)-(x(k)x*)x(k)x*-x(k+1)x*(1-M)x(k)x*科大研究生学位课程17所
12、以)()1(*)(11kkkxxMxx)1()(1kkxxMM)0()1(1xxMMk 上述定理只是收敛的充分条件,并不必要,如7.005.08.0M则M1=1.2,M=1.3,M2=1.09,MF=1.17但(M)=0.81,所以迭代法是收敛的.由由(2.10)(2.10)式可见式可见,M越小收敛越快越小收敛越快,且当且当x(k)-x(k-1)很小很小时时,x(k)x*就很小就很小,实际上用实际上用x(k)-x(k-1)作为作为迭代终止迭代终止的条件的条件.科大研究生学位课程18 ,即若使x(k)x*,只需)0()1(1xxMMkM(0)(1)xx)M(1ln/)ln(k可以事先估计达到某一
13、精度需要迭代多少步可以事先估计达到某一精度需要迭代多少步.线性方程组的迭代法主要有线性方程组的迭代法主要有Jocobi迭代法、迭代法、Gauss-Seidel迭代法和超松弛迭代法和超松弛(Sor)迭代法迭代法.科大研究生学位课程19nnnnnnnnnnbxaxaxabxaxaxabxaxaxa221122222121112121112.2雅克比（雅克比（Jacobi）迭代法）迭代法若系数矩阵非奇异，且若系数矩阵非奇异，且 (i=1,2,n)，将方程组将方程组0iia改成改成11,221112323121222213132121111111nnnnnnnnnnnnnxaxaxabaxxaxaxa
14、baxxaxaxabax科大研究生学位课程20然后写成迭代格式然后写成迭代格式)(11,)(22)(11)1()(2)(323)(121122)1(2)(1)(313)(212111)1(1111knnnknknnnnknknnkkkknnkkkxaxaxabaxxaxaxabaxxaxaxabax（2.11）（2.11）式也可以简单地写为式也可以简单地写为),2,1(1)(1)1(nixabaxkjnijjijiiiki（2.11）科大研究生学位课程21写成写成矩阵形式矩阵形式：A=LUDBfJacobi 迭代迭代阵阵bDxULDxkk1)(1)1()(2.12)bxULDxbxULDbAx
15、 )()(bDxULDx11)(科大研究生学位课程22Jacobi迭代法的计算过程如下：(0)(0)(0)(0)112(0)1(0)(0)1.(),(,),(,),.2.1.3.1,2,()/4.,55.,1,(1,2,),3 ijnnniiijjiijj iiiAabbbn xxxxNkinxba xaxxxkNkk xxin 输入维数最大容许迭代次数置对若输出 停机；否则转。若置转；否则，输出失败信息，停机。()(1,kkMxx）评价：公式简单，每迭代一次只需计算一次矩阵和向量的乘法，不改变的稀疏性，需两组工作单元，存。程序见P19。科大研究生学位课程232.2.2 Jacobi迭代法的收
16、敛条件迭代法的收敛条件 迭代格式收敛(B)1。若B1迭代法收敛.定理：若A满足下列条件之一，则Jacobi迭代收敛。A为行对角占优阵 A为列对角占优阵 A满足ijijiiaajiijjjaa1 jiiiijaa对于Jacobi迭代，我们有一些保证收敛的充分条件.引理引理 若A是严格对角占优矩阵,则det(A)0.证证 A=D-L-U=D(I-D-1(L+U)=D(I-B)因为A是严格对角占优矩阵,所以det(D)0,而且科大研究生学位课程24证明：)(1ULDB iiijijijiiijiaaaaB 1max1max1 jiiiijiaaB A为列对角占优阵，则AT为行对角占优阵，有1)(1T
17、ADI1)()(11 TADIADI 证毕1max11nijjiiijniaaB因此,(B)B1,故=1不是B B的特征值,det(E E-B B)0.所以,det(A)0.科大研究生学位课程25 为了加快收敛速度，同时为了节省计算机的内存，我们作如下的改进：每算出一个分量的近似值，立即用到下一个分量的计算中去，即用迭代格式：iinijkjijijkjijikiaxaxabx1)1(11)()(2.3 .3 高斯高斯赛得尔赛得尔(Gauss-Seidel)迭代法迭代法逐一写出来即为科大研究生学位课程26)(1)(1)(414)(313)(212111)1(1knnkkkkxaxaxaxabax
18、)(1)(2)(424)(323)1(121222)1(2knnkkkkxaxaxaxabax)(1)(3)(434)1(232)1(131333)1(3knnkkkkxaxaxaxabax)(1)1(11)1(33)1(22)1(11)1(knnnknknknnnnknxaxaxaxabax 只存一组向量即可。只存一组向量即可。写成写成矩阵形式矩阵形式：bDUxLxDxkkk1)()1(1)1()(bUxxLDkk )()1()(bLDUxLDxkk1)(1)1()()(B fGauss-Seidel 迭代阵迭代阵2.3 .3 高斯高斯赛得尔赛得尔(Gauss-Seidel)迭代法迭代法(2
19、.14)(2.16)科大研究生学位课程27Gauss-Seidel迭代法的计算过程如下：(0)(0)(0)(0)112(0)1111121(0)111.(),(,),(,),.2.1.3.()/()/(2,1)(ijnnnjjjiniiijjijjiijjinnAabbbn xxxxNkxba xaxba xa xainxba 输入维数最大容许迭代次数置计算11(0)(0)/4.,55.,1,(1,2,),3nnjjnnjiixaxxxkNkk xxin若输出停机；否则转。若置转；否则，输出失败信息，停机。程序见P23。科大研究生学位课程28 例例 用雅可比迭代法解方程组用雅可比迭代法解方程组
20、 2.453.82102.7210321321321xxxxxxxxx 3.12.11.1x )2.4(51)3.82(101)2.72(101)(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx解：雅解：雅 可可 比比 迭迭 代代 格式为格式为科大研究生学位课程29kx1(k)x2(k)x3(k)10.720.830.8420.9711.071.15 11 1.099993 1.199993 1.29999112 1.099998 1.199998 1.299997 取取计算如下计算如下 Tx)0,0,0()0()2.4(51)3.82(101)2
21、.72(101)(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx科大研究生学位课程30 解：解：Gauss-Seidel 迭代格式为迭代格式为 )2.4(51)3.82(101)2.72(101)1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx 例例 用用GaussSeidel 迭代法解上题。迭代法解上题。2.453.82102.7210321321321xxxxxxxxx科大研究生学位课程31取取 x(0)=(0,0,0)T 计算如下：计算如下：kx1(k)x2(k)x3(k)10.720.90
22、21.1644 81.0999981.1999991.3 )2.4(51)3.82(101)2.72(101)1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx科大研究生学位课程322.3.2 收敛条件收敛条件我们看一下Gauss-Seidel迭代法收敛的充分条件定理：若A满足下列条件之一，则Seidel i迭代收敛。A为行或列对角占优阵A对称正定阵（证略）迭代格式收敛(B)1。若B1迭代法收敛.det(I-B)=det(I-(D-L)-1U)证明：=det(D-L)-1)det(D-L)-U)=0所以有 det(D-L)-U)=0nnnnnn
23、aaaaaaaaa212222111211UL)(D科大研究生学位课程33nnnnnnaaaaaaaaa212222111211UL)(D 若|1,则矩阵(D-L)-U 是严格对角占优矩阵,这与 det(D-L)-U)=0矛盾,所以|1,于是(B)1.二种方法都存在二种方法都存在收敛性问题收敛性问题。有例子表明：有例子表明：Gauss-Seidel法收敛时，法收敛时，Jacobi法可能法可能不收敛；而不收敛；而Jacobi法收敛时，法收敛时，Gauss-Seidel法也可能法也可能不收敛。不收敛。科大研究生学位课程342.4 逐次超松弛迭代法逐次超松弛迭代法记)()1()(kkkxxx则)()
24、()1(kkkxxx可以看作在前一步上加一个修正量。若在修正量前乘以一个因子，有)()()1(kkkxxx)()()1(1)1(bUxLxDxkkk对GaussSeidel迭代格式)()()1()()1(kkkkxxxx)()(1)(1)1(1)()1(kkkkkxbDUxDLxDxx)()1(1)(1)1(1)()1(bDUxDLxDxxkkkk(2.22)bDxUDIxLDIkk1)(1)1(1)1()(科大研究生学位课程35故故SOR的迭代格式的迭代格式bDxUDIxLDIkk1)(1)1(1)1()(bDLDIxUDILDIxkk111)(111)1()()1()(bLDfUDLDB1
25、1)()1()(bLDxUDLDxkk1)(1)1()()1()(（2.23）SOR的迭代矩阵的迭代矩阵科大研究生学位课程36)(1)1(11)1(1kjnijijkjijijiiikixaxabax),2,1()1()1()()1(nixxxkikiki)(1)1(11)()1()1(kjnijijkjijijiiikikixaxabaxx写成分量形式，设写成分量形式，设加速加速（迭代公式）（迭代公式）是松驰因子是松驰因子(02),当01时叫超松弛，=1时，就是Gauss-Seidel迭代法。科大研究生学位课程37松弛法计算过程如下：(0)(0)(0)(0)112(0)(0)11111121
26、(0)(0)111.(),(,),(,),.2.1.3.(1)()/(1)()/ijnnnjjjiniiiijjijjiijjiAabbbn xxxxNkxxbaxaxxba xa xa 输 入维 数最 大 容 许 迭 代 次 数，参 数置计 算1(0)1(0)(0)(2,1)(1)()/4.,55.,1,(1,2,),3nnnnnjjnnjiiinxxbaxaxxxkNkk xxin若输 出停 机；否 则 转。若置转；否 则，输 出 失 败 信 息，停 机。程序见P28。科大研究生学位课程38(0)12123231(1)(1)()11(1)()()112(1)()22 1.4,(1,1,1)
27、,21 2021.8 (1)()0.40.7(1)0.4Tinkkkkiiiijjijjjj iiikkkkkxxxxxxxxxxba xa xaxxxxx 例：取用超松弛法解方程组解：由(1)()13(1)()(1)332(0)(9)0.7()(0,1,2,)0.40.7(1.8)(1,1,1)(1.200,1.3996,1.6001)(1.2,1.4,1.6)kkkkkTTTxxkxxxxxx 将代入上式开始迭代，精确解科大研究生学位课程392.4.2 SOR迭代法的收敛条件迭代法的收敛条件 迭代格式收敛(B)1。若B1迭代法收敛.对于SOR迭代，我们有一些收敛的结果.定理定理2.102.
28、10 若SORSOR方法收敛的必要条件是02.证证 设SORSOR方法收敛,则(B)1,所以|det(B)|=|12 n|1而 det(B)=det(D-L)-1(1-)D+U)=det(I-D-1L)-1 det(1-)I+D-1U)=(1-)n于是|1-|1,或 02科大研究生学位课程40 定理定理2.112.11 设A是对称正定矩阵,则当00科大研究生学位课程41(Dy,y)=0 (Uy,y)=(y,Ly)=(Ly,y)=-i 0(Ay,y)=(Dy,y)-(Ly,y)-(Uy,y)=-2所以)()()1(ii2222222)()(|当02时,有 (-+)2-(-)2=(2-)(2-)=
29、(2-)(2-)0所以|21,因此(B)1,即S0R方法收敛.科大研究生学位课程42 推论推论2.12.1 A是对称正定矩阵,Jacobi迭代法收敛的充要条件是2D-A也对称正定。证证设是Jacobi迭代矩阵B的任一特征值,y是对应的特征向量,则(L+U)y=Dy于是 (Ly,y)+(Uy,y)=(Dy,y)可得 =2/当A对称正定时,即2-0时,|0而 (2D-A)y,y)=(Dy,y)+(Ly,y)+(Uy,y)=+2即,当A对称正定时,JacobiJacobi迭代法收敛2D-A正定.科大研究生学位课程43 SORSOR方法收敛的快慢与松弛因子的选择有密切关系.但是如何选取最佳松弛因子,即
30、选取=*,使(B)达到最小,是一个尚未很好解决的问题.实际上可采用试算的方法来确定较好的松弛因子.经验上可取1.41.6.科大研究生学位课程44用SORSOR方法解线性方程组7910431017210424321321321xxxxxxxxx 解解 SORSOR方法迭代公式为方程组的精确解是x x*=(2,1,-1)T.例例4)91047(9)101723(17)42410(4)(3)1(2)1(1)(3)1(3)(3)(2)1(1)(2)1(2)(3)(2)(1)(1)1(1kkkkkkkkkkkkkkkxxxxxxxxxxxxxxx取x x(0)=(0,0,0)T,=1.46,计算结果如下
31、:科大研究生学位课程45kx1(k)x2(k)x3(k)01232003.652.321669102.56613991.999998700.88458820.42309390.69482611.00000130-0.2021098-0.22243214-0.4952594-1.0000034 从结果可见,迭代20次时已获得精确到小数点后五位的近似解.如果取=1.25,则需要迭代56次才能得到具有同样精度的近似解;如果取=1,则需迭代110次以上.科大研究生学位课程46TnxfxfxfxF)(),(),()(21 设含有设含有n个未知数的个未知数的n个方程的非线性方程组为个方程的非线性方程组为
32、(6.20)其中其中 为为n维列向量，维列向量，0)(xFTnxxxx),(21 非线性方程组的数值解法非线性方程组的数值解法),2,1)(nixfi 中至少有一个是中至少有一个是x的非线性函数，的非线性函数，并假设自变量和函数值都是实数。多元非线性方程组并假设自变量和函数值都是实数。多元非线性方程组(6.20)与一元非线性方程与一元非线性方程f(x)=0具有相同的形式，可以与具有相同的形式，可以与一元非线性方程并行地讨论它的迭代解法。例如不动点一元非线性方程并行地讨论它的迭代解法。例如不动点迭代法和迭代法和Newton型迭代法。但是，这里某些定理的证型迭代法。但是，这里某些定理的证明较为复杂
33、，我们将略去其证明。明较为复杂，我们将略去其证明。科大研究生学位课程47Tnxxxxx)(,),(),()(21(6.21)并构造迭代格式并构造迭代格式,1,0),()()1(kxxkk(6.22)把方程组把方程组(6.20)改写成下面便于迭代的等价形式：改写成下面便于迭代的等价形式：的解。的解。是方程组是方程组 从而从而 的不动点，的不动点，是迭代函数是迭代函数 即即 满足满足 连续函数。则连续函数。则 的的 是自变量是自变量 是连续的，即是连续的，即 且且 收敛，收敛，若由此生成的序列若由此生成的序列 对于给定的初始点对于给定的初始点)20.6()(),(,)(,),(),()(,*2 1
34、 2 1)0(x x x x x x x x x x x x x x n n f f f f f f KK)(kx*)(limxxkk 6.3.1 一般迭代法一般迭代法科大研究生学位课程48例例6.3.1 设有非线性方程组设有非线性方程组 081008102122122121xxxxxxx(6.24)把它写成等价形式把它写成等价形式)8(101),()8(101),(1211212222212111xxxxxxxxxxx并由此构造迭代并由此构造迭代 公式公式 8)(101),(8)()(101),()(122)(1)(2)(12)1(22)(22)(1)(2)(11)1(1kkkkkkkkkk
35、kxxxxxxxxxxx,1,0k(6.25)科大研究生学位课程49)(1kx)(2kx取初始点取初始点 。计算结果列于下表，可见迭代收敛到方。计算结果列于下表，可见迭代收敛到方程的解程的解 Tx)0,0()0(Tx)1,1(*表表k 0 1 2 18 19 0 0.8 0.928 0.999999972 0.999999989 0 0.8 0.931 0.999999972 0.999999989 函数也称映射，若函数函数也称映射，若函数 的定义域为的定义域为 ，则可，则可用映射符号用映射符号 简便地表示为简便地表示为 。为了讨论不动。为了讨论不动点迭代法（点迭代法（6.22）的收敛性，先定
36、义向量值函数的映内性）的收敛性，先定义向量值函数的映内性和压缩性。和压缩性。)(xnRDnnRRD:科大研究生学位课程50定义定义 设有函数设有函数 若若 则称则称 在在D D上是映内的，记做上是映内的，记做 ，又若存在常数，又若存在常数 ，使得，使得 nnRRD:DxDx,)()(xDD)()1,0(LDyxyxLyx,)()(则称则称 在在D上是压缩的，上是压缩的，L称为压缩系数称为压缩系数)(x 压缩性与所用的向量范数有关，函数压缩性与所用的向量范数有关，函数 对某种范数是压对某种范数是压缩的，对另一种范数可能不是压缩的。缩的，对另一种范数可能不是压缩的。)(x定理定理（压缩映射定理压缩
37、映射定理）设函数）设函数 在闭集在闭集 上是映内的，并且对某一种范数是压缩的，压缩系数上是映内的，并且对某一种范数是压缩的，压缩系数为为L，则，则（1）在在 上存在唯一的不动点上存在唯一的不动点 。（2）对任何初值）对任何初值 迭代法（迭代法（6.22）生成的序列）生成的序列 且收敛到且收敛到 ，并且有误差估计式，并且有误差估计式 nnRRD:DD 0)(x0D*x0)0(Dx0)(Dxk*x科大研究生学位课程51)1()(*)(1kkkxxLLxx例例6.3.2 对于例对于例6.3.1，设，设 试证：对任何初始点试证：对任何初始点 ，由迭代法（，由迭代法（6.25）生成的序列的都）生成的序列
38、的都收敛到方程（收敛到方程（6,24）在）在 中的唯一解中的唯一解 5.1,5.1:),(21210 xxxxDT0)0(Dx0DTx)1,1(*0D证：首先容易算出，对于任何证：首先容易算出，对于任何 ，都有，都有 因此，迭代函数因此，迭代函数 在在 上是映内的。进而，对于任何上是映内的。进而，对于任何 都有都有021),(DxxxT25.1),(8.0211xx2875.1),(3125.0212xx021),(DxxxT021),(DyyyT)()(101)()(2222111111yxyxyxyxyx122113.0)(103yxyxyx科大研究生学位课程522222211122101
39、)()(yyxxyxyx22122122122111101yyxyxyxxyx)()(1(101222211122yxyxyyxx)5.425.3(1012211yxyx145.0yx 从而从而)()()()()()(22211yxyxyxyx 75.0 可见，函数可见，函数 在上在上 是压缩的。因此，由定理得知结是压缩的。因此，由定理得知结论成立。论成立。0D 以上讨论了迭代法在以上讨论了迭代法在 的收敛性，实用的是讨论局部的收敛性，实用的是讨论局部收敛性。收敛性。0D科大研究生学位课程53定义定义 设设 为为 的不动点，若存在的不动点，若存在 的一个领域的一个领域 ，对一，对一切切 ，由（
40、，由（6.22）式产生的序列）式产生的序列 且且 ，则称则称 具有局部收敛性。具有局部收敛性。*x*xDS Sx)0(Sxk)(*)(limxxkk)(kx与单个方程的情形类似，有时可以用关于导数的条件代替压缩与单个方程的情形类似，有时可以用关于导数的条件代替压缩条件来判别收敛性条件来判别收敛性 科大研究生学位课程54定理定理6.3.1 设设 ，在在D内有一不动点内有一不动点 ，且，且 在在 处处可导，且谱半径可导，且谱半径 ，则迭代法（则迭代法（6.22）在点）在点 处处局部收敛，其中，函数局部收敛，其中，函数 的导数为的导数为Jacobi矩阵（见矩阵（见*式）式）利用谱半径与范数的关系利用
41、谱半径与范数的关系 ，我们可用，我们可用 代替定理代替定理6.3.1中的条件中的条件 nnRRD:*x*x1)(*x*x)(xAA)(1*x1)(*x科大研究生学位课程55 nnnnnnTnTTxxxxxxxxxxxxxxxxxxxxxx21222121211121)()()()()()()()(（*）例如，对于例例如，对于例6.3.1有有 对于例对于例6.3.2所取的区域所取的区域 的不动点的不动点 在它的内部。容易验在它的内部。容易验 证，在证，在 上有上有 ，因此，迭代法（，因此，迭代法（6.25）在点）在点 处处局部收敛。局部收敛。2122212212101)(xxxxxx,0D*x0
42、D 75.0*x*x科大研究生学位课程56对于非线性方程组，也可以构造类似于一元方程的对于非线性方程组，也可以构造类似于一元方程的Newton迭代迭代法。设法。设 是方程组（是方程组（6.20）的解，）的解，是方程组的一个近似解。是方程组的一个近似解。用点用点 处的一阶处的一阶Taylaor展开式近似每一个分量函数值展开式近似每一个分量函数值 ，有有*x)(kx)(kx0)(*xfi njkjjjkikiinixxxxfxfxf1)(*)()(*,2,1),()()()(其中其中 为为 的的Jacobi矩阵矩阵 在的在的 值，而值，而 写成向量形式有写成向量形式有)()()()(*)()(*k
43、jkkxxxFxFxF )()(kxF)(xF)(xF)(kx6.3.2 非线性方程组的非线性方程组的Newton法法 科大研究生学位课程57 nnnnnnTnTTxxfxxfxxfxxfxxfxxfxxfxxfxxfxfxfxfxF21222121211121)()()()()()()()(若矩阵若矩阵 非奇异，则可以用使（非奇异，则可以用使（6.4.6）右端为零的向量作）右端为零的向量作为为 新的一个近似值，记为新的一个近似值，记为 ，于是得到，于是得到Newton迭代法迭代法)()(kxF*x)1(kx,2,0),()(1)()1(kxFxFxxkk（6.4.7)0(x)()(1kkxx
44、其中其中 是给定的初值向量。如果写成一般不动点迭代是给定的初值向量。如果写成一般不动点迭代 的形式，则的形式，则Newton迭代函数为迭代函数为 )()()(1xFxFxx(6.4.8)科大研究生学位课程58在在Newton法实际计算过程中，第法实际计算过程中，第k步是先解线性方程组步是先解线性方程组 解出解出 后，再令后，再令 ，其中包括了计其中包括了计算向量算向量 和矩阵和矩阵)()()()()(kkkxFxxF(6.4.9)(kxkkkxxx)1()()(kxF)()(kxF例例6.13 用用Newton法解例法解例6.11的方程组（的方程组（6.4.4）解解 对该方程组有对该方程组有
45、取初始向量取初始向量 ，解方程组，解方程组 ，即，即 810810)(2122122121xxxxxxxxF10212102)(212221xxxxxxFTx)0,0()0()()()0()0()0(xFxxF88101010)0(x科大研究生学位课程59求出求出 后，后，。同理计算。同理计算 结果结果列于表列于表610。可见，。可见，Newton法的收敛速度比例法的收敛速度比例6.11中的迭代中的迭代法（法（6.4.5）要快的多。）要快的多。)0(xTxxx)88.0,8.0()0()0()1(,)2(x表表 6-10kx2kx1k 0 1 2 3 4 0 0.80 0.991787221
46、0.999975229 1.00000000 0 0.88 0.991711737 0.999968524 1.00000000 关于关于Newton法的收敛性，有下面的局部收敛性定理法的收敛性，有下面的局部收敛性定理 科大研究生学位课程60定理定理6.11 设设 ，满足满足 。若有。若有 的开邻的开邻域域 ，在其上连续，在其上连续，可逆，则可逆，则 nnRRDF:*x0)(*xF*xDS 0)(xF)(*xF(2)Newton迭代序列迭代序列 在在S上收敛于上收敛于 ，且是超线性收敛，且是超线性收敛。)(kx*x(1)(1)存在以存在以 为中心，为中心，为半径的闭球为半径的闭球 ,使使 （6
47、.4.8）式中的）式中的 对所有对所有 都有意义，并且都有意义，并且 。*x00*),(SxSS)(xSxSx)(（3）若还有常数若还有常数 ，使，使 则则Newton迭代序列迭代序列 至少二阶收敛于至少二阶收敛于 。0SxxxxFxF,)()(*)(kx*x 虽然虽然Newton法具有二阶局部收敛性，但它要求法具有二阶局部收敛性，但它要求 非奇非奇异。如果矩阵异。如果矩阵 奇异或病态，那么奇异或病态，那么 也可能奇异或病也可能奇异或病态，从而可能导致数值计算失败或产生数值步稳定。这时可采态，从而可能导致数值计算失败或产生数值步稳定。这时可采用用“阻尼阻尼Newton法法”，即把（，即把（6.
48、4.9）改成）改成)(*xF)(*xF)()(kxF科大研究生学位课程61其中的参数其中的参数 称为阻尼因子，称为阻尼因子，称为阻尼项，解出称为阻尼项，解出 后，后，令令 。加进阻尼项的目的，是使线性方程的系数矩。加进阻尼项的目的，是使线性方程的系数矩阵非奇异并良态。当阵非奇异并良态。当 选的很合适时，阻尼选的很合适时，阻尼Newton法时线性法时线性收敛的。收敛的。kIk)(kx)()()1(kkkxxxk例例614 用用Newton法和阻尼法和阻尼Newton法求解方程法求解方程 ，其，其中中 0)(xF2102310)(2122122121xxxxxxxxF解：易知该方程有一个解是解：易
49、知该方程有一个解是 。由于。由于 Tx)1,4(*,1,0),()()()()(kxFxIxFkkkk科大研究生学位课程622222)(*xF，），（法有按）（TxNewton438461538.1538461538.31Tkx)5.2,5.2(.10)0(5若取是奇异的，取阻尼因子。，Tx)000000025.1,000000025.4()25(,)438461083.1,538463160.3()1(TxNewton法计算有在按阻尼。Tx)000000286.1,000000286.4(,)29(定性问题，没有出现奇异或数值稳法仍非奇异，奇异，只要可见，即使矩阵NewtonxFxFk)()
50、()(*法并小，。因为次例题的维数太收敛，但收敛是线形的Newton科大研究生学位课程63作用，反而使迭代法不仅没有显示出它的从而阻尼 Newton法是线形收敛的。，阻尼次数更多。但可以看出Newton初值关重要。程时，初始值的选取至用迭代法求解非线形方敛到不同的解。同的初值可能收，而当方程有解时，不不仅影响迭代是否收敛。1)5.0()2(1)(2221221xxxxxF15.6例其中法求解用,0)(xFNewton21221)201xxx与圆（物线该方程组的实数解是抛解,)0000.1,0625.1(,)0,0()1()0(KTTxx那么有如果取初时向量。和TTx)391176313.1,5
