数值分析课件

1、第 3 章 线性方程组的解法本章探讨大型线性方程组计算机求解 的常用数值方法的构造和原理， 主要介绍在 计算机上有效快速地求解线性方程组的有 关知识和方法 .重点论述Jacobi迭代法、Seidel迭代法、 Guass 消元法 及 LU 分解法 的原理、构造、 收敛性等内容。3.1 实际案例3.2 问题的描述与根本概念 解线性方程组问题在线性代数中已有 很优美的行列式解法， 但对大型的线性方程 组阶数n>40的求解问题使用价值并不大， 因为其计算量太大。 实际问题中经常遇到自 变量个数 n 都很大的线性方程组求解问题， 这些线性方程组要借助计算机的帮助才能 求出解。n个变元Xi,X2,

2、,Xn的线性方程组的一般 形式为a11x1a12x2La1nxnb1a21x1a22x2La2nxnb2M3.3am1x1am2x2Lamnxnbm式中， aij 称为系数， bi 称为右端项，它们都 是的常数。 如果有 x1 x1* , x2 x2*,L ,xn x*n 使方程组 3.3成立，那么称值* * *x1* ,x2*,L ,xn*为线性方程组的 3.3的一组解。主要讨本章在不作特别说明的情况下，论 m=n 的线性方程组a11x1a12x2La1nxnb1a21x1a22x2La2nxnb2Man1x1an2x2Lannxnbn的求解问题，且假设它有唯一解。线性方程组的矩阵表示Ax

3、b式中 A 称为系数矩阵， b 称为右端项数值分析中， 线性方程组的数值解法主 要分为 直接法 和 迭代法 两大类。直接法是用有限次计算就能求出线性 方程组“准确解 的方法不考虑舍入误差 ； 迭代法是由线性方程组构造出迭代计算公 式，然后以一个猜想的向量作为迭代计算的 初始向量逐步迭代计算， 来获得满足精度要 求的近似解。迭代法是一种逐次逼近的方法。3.3 线性方程组的迭代解法线性方程组迭代解法有 Jocobi 迭代法、 Seidel 迭代法及 Sor 法等根本思想 与简单迭代法类比 将线性方程组 Ax b 等价变形为x Bx g以构造向量迭代格式k1xBx kg用算出的向量迭代序列1 x2,

4、x 2 ,L 去逼近解 。1.构造原理1 Jacobi迭代法1将线性方程组3.4 的第i个变元X用其他n-1个变元表出，可得1亠x(b1a11X2丄a21 X1a221八Xn(bnan1 X1anna13X3La1n Xn )a23X3La2n Xn )an2X2Lann 1Xn 1 )(3.5)称3.5 为不动点方程组(2)将(3.5 )式写成迭代格式x1k1)丄 Q ai2x2k) 43x3k)(k) y nQaiix2k 1) (b2a>ixjk)a23x3k)(k)-a2 nXn )a22(3.6)xnk 1) (bna1ix(k)an2x2k)-ann ix!k!)annJac

5、obi迭代格式(3)取定初始向量x00 0 , 0 T xi ,X2, L ,Xn,代入，可逐次算出向量序列 这里 x k Xik ,X2k 丄，xnk 。12k .X ,x ,L ,x L ,(k 1)Xi(b1a111 (b2 a221 Qann(k 1)an1 X1an2X2k 1)0 lXnki1)2) Seidel迭代法(k)(k)(k)、62X2，ax；丿-a1nxn;)(k 1)(k)(k)、a21X1a23X3-a2nXn )Seidel迭代格式Seidel迭代并不能取代Jacobi迭代3) Sor 法用Seidel迭代算出的 X 1与xk相减得到 差向量x Wo 1 xk采用

6、加速技术做下一步迭代：k 1kx x x得Sor法的迭代格式kx aiii 1nk 1k z iajXjajXj,i 1,2丄,nj 1j i 1式中参数称为松弛因子，可以任意选取，当 =1时，Sor法就是Seidel迭代法(例如对线性方程组10x1x22X37.2x110 x22X38.3x1x25X34.2先将其写成不动点方程组1x1(7.21 10x22x3)1x2(8.3x1X3)1X35(4.2X1X2)Jacobi迭代x1k1)110(7.2x2k)2x3k)x2k 1)1(8.3 x(k)x3k)10x3k 1)1(4.2 x!k)x2k)5Seidel迭代扣2 x2k)2x3k

7、)101 (8.3 x1k1) x3k)10 11(4.2 x1k1) x2k1)5Sor迭代1)1kX1(7.210x2k) 2x3k)x2k1)1kX2 (8.310(k 1)X1x3k)xT1)1kX1(4.25(k 1) x()x2k 1)2.迭代分析及向量收敛1) 三种迭代法的向量迭格式 对 Ax=b ，将系数矩阵 A 作如下分解ADLUa11a22Oann0a12 La1na21 M0L0MOMa2n Man1an2 L 0那么Ax=b可以写成D L U x b。假设d 1存 在，得Ax=b的等价方程组x D 1 L U x D 1b由此可得到Jacobi迭代的向量迭代格式|xk1

8、 D 1 L U xk D 1bk 1kxBjXgjBj D 1 L U ,gj D 1b，Bj 称为 Jacobi 迭代 矩阵。Seidel向量迭代格式k 1kxBsXgs式中矩阵Bs称为Seidel迭代矩阵,1 1Bs D L U,gs DLb。Sor法的向量迭代格式k 1kx B x g式中矩阵B称为超松弛迭代矩阵，1 1B D L 1 DU , g DLb。三种迭代格式可用一个迭代格式Xk 1 Bxk g2) 向量收敛定义定义31设向量序列Xkx/k丄，Xnk及量为向 limx1* , x*2 ,L ,x*n 都是 Rn 中的向量，如果有*Xi,i 1,2丄，n成立，,那么称x(k)收

9、敛于x 。k*简记为 lkim x x3) 范数定义与科学计算中的常用范数定义3.2 设L是数域K上的一个线性空 间，如果定义在L上的实值函数p(x)满足1) 任取 x L，有 P(x) 0,且 P(x) 0 x 0 ；2) 任取 x L, K，有 p( x) | | p x ；3) 任取 x,y L ,有 P(x y) P x P y ,那么称P()是L上的一个范数，称P(x)为x的 一个范数。范数的定义很象绝对值函数,故常用II IIp或 II表示范数，而范数px常记为IIx P或I x。这 样，上面范数定义中的 3个条件常写为1任取 x L，有 |x| 0,且 |x|0 x 0 ；2任取

10、 x L, K，有 | | H ；3任取 x,y L，有 |x y| |x| |y|将其与绝对值比拟，是否很象？实际上，很多有关绝对值的运算和结论可以 平行引进到有关范数的运算和证明问题中。数值分析中常用的线性空间有n维向量空间连续函数空C a,b f x | f x 在a,b上连续函数空间C a,b是由闭区间 a,b上所有 连续函数组成的集合，其线性运算定义为 加法 f g: f g x f x g x 数乘 f ： f x f x， 为数在这些空间上，数值分析中常用的范数有(1)Rn的向量范数n1) Ilxll1lxk ,k 1，3制mkax|x<|式中向量x Xi，X2丄,xn 。

11、(2) Rn n的矩阵范数矩阵范数要满足如下四条1任取 ARnn，有IA0,且IA0A 0；2任取 ARnn,K ,有 | Al丨 IIIAI ;3任取 A,B Rnn，有 |A B J A |B|4 任取 A,B Rnn，有 | AB IA | B| 相容性与向量范数做比照由于线性方程组求解问题中，系数矩阵总 是与向量联系在一起的，为描述这种联系， 引入如下的算子范数概念。定义3.3设矩阵A Rnn，称Apmaxx Rnx 0Ax|p为矩阵A的算子范数容易证明，矩阵A的算子范数也是矩阵范数，且满足不等式关系IIAxip blip Mp.常用的矩阵范数有如下 4种n1) 列范数:IIAIi m

12、axx I aJ i 1n2) 行范数:iia maxx怙i3) F 范数：af g4) 2 范数：, max 是 A A 最大 特征值以上4个矩阵范数中，|A|i，|A|2，|A|是算子 范数，I A| F不是算子范数。3范数等价与向量极限定义3.4设llpJllq是线性空间L上的 两个范数，假设存在正常数m和M，成立叫x|p |x|q M|x|p, X L那么称范数I定理3.1定理3.2|q是等价范数。Rn上的所有范数都是等价的I 0。XX m NkXX Im != k式中II II是Rn上任何一种范数4谱半径及其与范数的关系定义 3.5 设 A Rn n , k,k 1,2,L ,n 是

13、 A 的 n个特征值，那么称实数A mk剛 ki为矩阵A的谱半径。注意k如果是复数，| k 表示复数模。kI A kIkAx|ax丨kxAxk kxk因为|xk| 0，上式同除|xk|，得I J IAI由k的任意性可得 A A。k定理3.3设A Rn n，那么有 A A , A|为 矩阵A的任意算子范数。证明 设k是A的任意一个特征值，xk为 对应的特征向量，那么有取范数，得3.迭代法的收敛条件与误差估计1收敛条件定理：线性迭代格式kk 1 Bxk g对任意初 始向量x0都收敛的充要条件是迭代矩阵谱 半径B 1。引理3.4设A Rn n，贝Ulim Ak0 A 1证明必要性设 kim xk x

14、*，在 xk 1 B xk g 中令 k , 得x Bx g，两式相减并把k+1记为k, 得xk x* B xk 1 x* B2 xk 2 x* L Bk x0 x由kimxk X*及x0 ,x*的任意性，有kim Bk 0 由引理，可得 (B) 1。充分性因为 (B) 1，那么有 I B 非奇异(这里 I 为单位矩阵)，从而线性方程组I B x g有唯一解X*，即有I B x* g，展开有 x* B x* g 。类似必要性处理，有k * k 0 *x x B x x由引理， 由 (B) 1有 lkim Bk 0 ，上式取极限， 得 lkim x k x* 。谱半径 (B) 一般不易计算， 因

15、此充要定理 通常只用在理论上。但由充要定理，可以得到如下易于计算的 判别迭代收敛条件 ，但要注意它们都是 充分 条件！判别条件I假设IB 1，那么迭代格式xk 1 Bxk g对任 意初始向量X0都收敛于线性方程组x B x g的唯一解。IIB是矩阵B的某种算子范数。定义3.6设A Rn n,1如果A的主对角元素满足nakk|aj ,k 0,1 丄，nj k那么称矩阵A是严格行对角占优阵；2)如果A的主对角元素满足n(3 18)akk|陽| ,k 0,1,L ,ni 1i k那么称矩阵A是严格列对角占优。严格行对角占优阵和严格列对角占优 阵统称为严格对角占优阵。定理严格对角占优阵是非奇异矩阵。证

16、明不妨设矩阵A aj nn是严格行对 角占优阵。用反正法。假设A是奇异的，那么由矩阵理论可知，齐 次线性方程组Ax 0有非零解x*，即存在* T*xXi，X2，L ,xn0，满足 Ax 0。记 |x；| |x| ，有 xm 0x； |x：|,k 1,2,L ,n。n将Ax 0的第m个等式amkxk 0写为k 1ammXmamkXkk 1k m等式两边取绝对值有ammXm*a xmm八mn*amk Xkk 1k mn*amk Xkk 1k mn*amk Xkk 1k m因为|x；| 0，上式同除|x；|，有nnammk 1amk*Xk/*Xmk 1amkk mk m此与A是严格行对角占优阵矛盾。

17、故假设 A 是非奇异的。设矩阵 A 是严格对角占优阵，那么线性方 程组 Ax b 的 Jacobi 迭代和 Seidel 迭代对任 意初始向量 x0 都收敛。判别条件 III设 A 是对称正定矩阵，那么 Ax b 的Seidel 迭代对任意初始向量 x 都收敛判别条件II的证明证明只对A是行对角占优情况证之设矩阵A是严格行对角占优阵，那么有nakkakj ，k O,1丄，n，将不等式两边同除j 17j k1 nakk，成立|akjjlakj1，k 0,1，L，nj kJacobi迭代矩阵BjI D 1A，故有nakj1 nmaxmax .akj1 k nj 1akk1 k n bkkl j 1

18、BJj kj k1由判别条件I,可得 Jacobi迭代的收敛性。对Seidel迭代，其迭代矩阵Bs d l 1u , 设k是矩阵Bs的任一特征值，那么有特征方程1det kI Bs det D L det k D L U 0因det D L 1 0，故矩阵Bs的特征方程变为det k D L U 0写出这个行列式方程对应的矩阵kai1a12La1nbsk D L Uka21ka22La2nMMOMk an1kan2Lkann如果丨k 1,利用矩阵A的行对角占优的不等 式，可以得出如下不等式kakkklakknkakjk 1kakjnakj,k 0,1丄,nj 1j 1j k 1j k这说明矩阵

19、%也是行严格对角占优阵，由定 理，有detBS 0。矛盾，故应有丨讣1成立。由k的任意性有谱半径Bs 1，于是可得Seidel迭代的收敛性。定理 3.7 Sor 法收敛的必要条件是松弛因 子 满足 0< <2。证明 因为 Sor 法的迭代矩阵为1BDL1 D U有detBdet D1L 1 det 1 D UdetD1 det 1D 1 n设 k ,k1,2,L,n 是 B的 n 个特征值，那么有detB1 2Ln1，假设 Sor 收敛，必有B1，注意到 12L n B ，得n1nBn1。解之得 0 2 。2误差估计定理3.8设矩阵B的某种矩阵范数| B1,那么由式xk 1 B x

20、k g算出的序列x k与线性方程组*x B x g的准确解x有如下的误差估计xk*xBillxkxk1|1IlBllII1事后估计式B1 l|B|2事先估计式证明可以参照非线性方程求根定理的证明，注意将那里的绝对值换成这里的范数，那里的函数换成这 里的矩阵，并注意范数关系的使用即可。要求误差I解此题的才1)2.4O.4x2k)O.6x3k)x2k 1)50.25x；k)O.5x3k)x3k 1)0.30.2x1k)0.3x2k)10 4XJacobi迭代格式为例3.1用Jacobi迭代法解线性方程组5xi+2x2+3x3= -12xi+4x2+2x3= 202xi-3x2+10X3= 3k 1

21、0.40.6它的Jacobi迭代矩阵为bj0.250o.50.2 0.30因为|Bj|f 0.981071<1,故此题的 Jacobi迭代 格式对任意初值x0都收敛。取初值X00,0,0 T进行迭代计算如下X12.4,5,0.3 T ,1 0XX0.5 10 42TX24.46,4.25,2.28,X2X12.06104Mx184.,2.99997,2. T ,X18x170.41L104 10故所求近似解为X14,X22.9997,X32。准确解为人4,X23, X32)1 22x1例3.2方程组111y22 21z31) 写出Jacobi和Seidel迭代格式;2) 判别两种迭代格式的收敛性。 解1)Jacobi迭代格式为x(k1)2y(k) 3z(k) 1y(k1)x(k) z(k) 2z(k1)2x(k) 2y(k) 3Seidel迭代格式为(k x1)2y(k)3z(