3线性方程组解法

1、第 3 章 线性方程组的解法本章讨论线性方程组a11x1a12x2La1nxnb1a21x1a22x2La2nxnb2Man1x1an2x2Lannxnbn的求解问题 .线性方程组的矩阵表示Ax b式中 A 称为系数矩阵， b 称为右端项69数值分析中，线性方程组的数值解法 主要分为 直接法 和 迭代法 两大类。直接法是用有限次计算就能求出线性 方程组“准确解”的方法（不考虑舍入误 差）；迭代法是由线性方程组构造出迭代计 算公式，然后以一个猜测的向量作为迭代 计算的初始向量逐步迭代计算，来获得满 足精度要求的近似解。迭代法是一种逐次逼近的方法。1 线性方程组的迭代解法线性方程组迭代解法有 Jo

2、cobi 迭代法、Gauss-Seidel迭代法及SOR法等基本思想（ 与简单迭代法类比 ）将线性方程组 Ax b 等价变形为x Bx以构造向量迭代格式k1xkBx kg用算出的迭代向量序列1 x,x 2 ,L去逼近解a11x1a12x2La1nxnb1a21x1a22x2La2n xnb2Man1x1an2x2Lannxnbn1. 构造原理(1) Jacobi迭代法将线性方程组的第i个变元焉用其他n-1个变元表出，可得Xiai1a13X3La1n Xn )X21a22(b2a?1 X|a23X3La2nXn)Xn1ann(bnan1 X1an2 X2Lann 1 Xn 1)Jacobi迭代格

3、式:(k1)1(b小(k)c(k)小(k)Xi*12X2*13X3-a! nXn )3i1x2k1)1(b(k)a?1Xa23x3k)(k) -a2 nxn)a22X,1)1(h(k) amXan2x2k)-ann 1Xn )ann(3)取定初始向量x° Xi°必°丄，x；，代入，可逐次算出向量序列xkk kkXi , X2 丄,XnX1 ,X2 ,L ,xk L，这里To(2) Gauss-Seidel 迭代法Seidel迭代格式：x；k 1)丄(biaii1(b2a22ai2x2k)ai3x3k)-亦 xnk)(k 1)(k)(k)、a21X1a23X3-a2

4、nXn )xnk 1)(k 1)an1X1an2X2k 1)0 lXnki1)例 1 对线性方程组x1 +2x2 2x3 =1x1 x2+x3 =22x1 +2x2 x3 =3写出 Jacobi 迭代格式和 Gauss-Seidel 迭代 格式.3) SOR 法SOR法的迭代格式k 1XikXibaiii 1k 1 a x ij jj ink a x ij jj i,i1,2,L ,n式中参数 称为松弛因子，当=1时，SOR法就是Seidel迭代法.2. 迭代分析及向量收敛1）三种迭代法的向量迭代格式对Ax=b，将系数矩阵A作如下分解ADLUa11Da22Oa.Jnn00L00a12La?10

5、L000LL,UMMOMMMOan1an2L000L则Ax=b可以写成aina2nM0Jacobi迭代的向量迭代格式k 1f kxBjXgjBj D 1(L U)， gj D 1b. Bj 为 Jacobi 迭代法的 迭代矩阵.Seidel向量迭代格式Bs d l 1u , gs d l 1b .Bs 为 Seidel 迭代法 的迭代矩阵.SOR法的向量迭代格式k 1kx B x gB D L 11 D U , g D L 1b . B为超松弛迭代法的迭代矩阵。三种迭代格式可写成迭代格式k 1kx B x g2）向量收敛定义定义 1 设向量序列 x k x1k ,x2k ,L ,xnk 及 向

6、量 x* x1*,x*2,L ,x*n T 都是 Rn 中的向量，如果有k*lim xixi ,i 1,2,L ,nk成立 ,则称 x(k) 收敛于 x* .简记为k*lim x kx* 。3) 范数定义与科学计算中的常用范数定义2设L是数域K上的一个线性空 间，如果定义在L上的实值函数P(x)满足1) xL，有 P(x) 0,且P(x) 0x 0 ；2) xL, K，有 P( x) P x ；3) x, y L，有 P(x y) P x P y ,则称P()是L上的一个范数，称P(x)为x的 一个范数。范数的定义很象绝对值函数，故常用 I Ip或| |表示范数，而范数P(X)常记为Ml p或

7、 |x|。这样，上面范数定义中的 3个条件常 写为1) X L，有 |x|0,且 |x|0 x 0 ；2) x L, K，有 | x Ix ；3) x, y L，有 |xy|x|y|将其与绝对值比较，是否很象? 实际上，很多有关绝对值的运算和结论可 以平行引进到有关范数的运算和证明问题 中。数值分析中常用的线性空间有n维向量空间Rna|aaa2丄，a“ ,ak R矩阵空间Rm nAm n 1 Am naij, aijRm nJ连续函数空间C a,b f x | f x 在a,b上连续函数空间C a,b是由闭区间a,b上所有 连续函数组成的集合，其线性运算定义为加法 f g: f g x f x

8、 g x数乘 f :f X f X， 为数在这些空间上，数值分析中常用的范数 有(1)Rn的向量范数3)IWI7副兀式中向量xXi，X2 丄T,Xn例2计算向量x 1, 2,3 T的各种范数A 0B| ；Rn n的矩阵范数矩阵范数要满足如下四条1) A Rnn，有 IAI 0,且IAI 02) A Rnn,K ,有 I A3) A,B Rnn，有 |A B| |A4) A,B Rnn，有 |AB A由于线性方程组求解问题中，系数矩 阵总是与向量联系在一起的，为描述这种 联系，引入如下的算子范数概念 .定义3设矩阵A Rnn，称ApmaxR|Ax|p为矩阵A的算子范数容易证明，矩阵 A的算子范数

9、也是矩阵范数，且满足不等式关系|Ax|p |A|p |x|p例3设|为矩阵的算子范数，证明若IB 1，则I B为非奇异矩阵，且1 B 1|11 |B证：用反证法。若I B为奇异矩阵，则其对应的方程组I B x 0有非零解X，即有x 0，使1 B x 0，得BX XBX II 刘 |X两边取范数并作范数运算B XQ X 0 B 1，矛盾，得1 B非奇异Q I BI1BII B1I1B I B丨1 B1IllBI B111b|II B11常用的矩阵范数有如下n1）列范数:IIAIi maxx lai 1n2) 行范数:IIA max laji3) F 范数：Af D4) 2范数：WA2 J max

10、 , max是A A最大特 征值。以上4个矩阵范数中，IIaMAIAI是算子 范数，|AF不是算子范数。例4计算矩阵A13 4的各种范数.3）范数等价与向量极限定义4设II II pj llq是线性空间L上的两 个范数，若存在正常数 m和M，成立ml|x|p |x|q M|x|p, x L则称范数丨p，lq是等价范数。定理1Rn上的所有范数都是等价的。定理 2 lim xk x lim xk x 0。式中H是Rn上任何一种范数624）谱半径及其与范数的关系定义 5 设 A R n , k，k h2,L ,n 是 A 的n个特征值，称A max k1 k n为矩阵A的谱半径。注意k如果是复数，k

11、表示复数模。79定理3设a|表示A的某种算子范数, 则有A A引理4设A Rn n，则kimAk 0 A 13. 迭代法的收敛条件与误差估计1）收敛条件定理5:对任意初始向量X0 ,由迭代格式xk 1 B xk g产生的向量序列xk都收敛的充要条件是(B) 1.证明必要性设 kim xk x*，在 xk 1 Bxk g 中令 k ，得x* B x* g ,于是有B2 xk2由limxk x*及x0的任意性，有lim Bk 0.再 由引理，可得 (B) 1.充分性因为 (B) 1，则有 I-B 非奇异(这里 I 为单位矩阵) ，从而线性方程组 I B x g 有 唯一解 x* ，即有*I B x

12、* g展开有 x* B x* g . 类似必要性处理，有x k x* Bk x 0 x*由引理，由 (B) 1有 lkim Bk 0 ，上式取极 限，得 lkim x k x* .判别条件Ib是矩阵b若|b| 1，则迭代法收敛 的某种算子范数.定义6设ARnn ,1）如果A的主对角元素满足nlakkllaj ,k 1,2,L ,nj1k则称矩阵A是严格行对角占优阵；2）如果A的主对角元素满足nakkaiki 1i k,k 1,2,L ,n则称矩阵A是严格列对角占优.严格行对角占优阵和严格列对角占优 阵统称为严格对角占优阵.定理 严格对角占优阵是非奇异矩阵。证明不妨设矩阵A aj nn是严格行对

13、角占优 阵.用反证法证明.若A是奇异的，则由矩阵理论可知，齐次线性方程组Ax 0有非零解x*，即存在* T*将AX* 0的第m个等式 a；kXk 0写为 k 1x Xi,X2,L ,Xn0，满足 Ax 0 .1，有*Xm0,*Xm*Xk,k 1,2丄，nn*n* *ammXmamkXkk 1k m等式两边取绝对值有ammI Xm*amm Xmn*amk Xkk 1k m*amk Xkamk*Xkk 1k 1k mk mnn因为|x；| 0，上式同除|x；|，有nnammamk|xk/x；|amkk 1k 1k mk m此与A是严格行对角占优阵矛盾.故若A是 非奇异的.设矩阵A是严格对角占优阵，

14、则解线性 方程组Ax b的Jacobi迭代法和Seidel迭代 法均收敛.证明 只对A是行对角占优情况证之 设矩阵A是严格行对角占优阵，则有ak韵点1,2,L ,nj ij k1 nI_Ilakjl 1,k 1,2丄，nakk j 1j kJacobi迭代矩阵Bj I D A，故有|Bj|max1 k nj 1 akk j k1 n =max1 k n由判别条件I,可得 Jacobi迭代的收敛性对Seidel迭代，其迭代矩阵BsD L 1U，设k是矩阵Bs的任一特征值，则有特征方程1det kI Bs det D L det k D L U 0因det D L 1 0,故矩阵Bs的特征方程变为

15、det k D L U 0这个行列式方程对应的矩阵BSk d l ukai1ai2La 1nka21ka22 La2nM MOMkannkan2如果k 1,利用矩阵A的行对角占优定 义，可以得出如下不等式nkakkk| |akk|kakjj 1j kk 1nkakj|aj ,k 1,2,L ,nj 1j k 1这说明矩阵BS也是行严格对角占优阵，由 定理，有det% 0,矛盾，故应有丨k 1成立. 由k的任意性有谱半径Bs 1，于是可得Seidel迭代的收敛性.定理7 SOR法收敛的必要条件是松弛 因子满足0< <2.证明因为SOR法的迭代矩阵为1B D L 1 D U有1detB

16、 det D L det 1 D U1ndet D 1 det 1 D 1 n设k,k 1,2丄，n是B的n个特征值，则有 detB i 2L n 1 n，若 SOR收敛，必 有 B 1,注意到| i 2L nl b n，得nnl 1 l B 1. 解之得 02.判别条件 III设 Ax b ，如果（1） A 对称正定，（2） 02，则解Ax b的SOR迭代法收敛.设 A 是对称正定矩阵，则解 Ax b 的Seidel 迭代法收敛 .判别条件 IV设 Ax b ，如果（1） A为严格对角占优阵，（ 2） 01 ，则解Ax b的SOR迭代法收敛.2 )误差估计定理8设矩阵B的某种算子范数IB 1

17、,则由式 xk1 Bxk g算出的序列xk与线性方程组*x B x g的准确解x有如下的误差估计xkxk1xk1 IIBII1)x0Bi IIb2)证明可以参照非线性方程求根定理的证明，注意将 那里的绝对值换成这里的范数，那里的函数换成这 里的矩阵，并注意范数关系的使用即可。77练习 1 设方程组为6x1 +2x2 x3 = 11x1 7x2 +2x3 =202x1 3x2 14x3 =5写出 Jacobi 迭代格式和 Gauss-Seidel 迭代 格式，判别这两种迭代法的收敛性 .练习 2 设方程组为x1 +2x2 = 13x1 x2=2判别 Jacobi 迭代法和 Gauss-Seide

18、l 迭代法 的收敛性 .练习 3 设方程组为x1 x2 +2 x3 =5x1 3x2 = 12x1 7x3 2判别 Jacobi 迭代法和 Gauss-Seidel 迭代法 的收敛性 .练习 4 方程组 Ax b ，其中1 a a A 4a 1 0a 0 1确定使Jacobi迭代法和Gauss-Seidel迭代 法均收敛的a的取值范围.练习5证明矩阵1 a aA a 1 aa a 11正定的充要条件是2 a匕而Jacobi迭1 1代只对2 a 2,是收敛的.3.4线性方程组的直接解法解线性方程组的直接法有 Gauss 消元 法，LU分解法及一些特殊线性方程组的解 法等，其中 Gauss 消元法

19、是直接法的基础 本章的重点是在一般公式推导上，要注 意学习和体会 .1271. Gauss 消元法基本思想先将线性方程组通过消元方法化为同 解的上三角方程组，然后从该三角方程组 中按第n个方程、第n-1个方程、第1 个方程的顺序，逐步回代求出线性方程组 的解.1) 构造原理Gauss 消元法的求解过程分为两个 :“消元 ”：把原方程组化为上三角方程组； “回代 ”：求上三角方程组的解 .为推导公式的方便，记要求解的原方 程组为0ai1 X0a21 X10b10b200ai2 X2L ain Xn00a22 X2L a2n XnM0 0 0 0an1 X1an2 X2L ann XnbnGaus

20、s消元法的算法构造如下一、消元过程i）设 ai00,令乘数 miiaii0 /aii ,做（消去第i个方程组的xi）操作mii第i个方程+第i个方程(i =2,3,)则第i个方程变为iai2 x2iiLain xnb这样消去第2, 3, 后，原线性方程组变为，n个方程的变元xi0ai0a2 x?0Lain xnbi0i a?2 x?La2n xnb2iMian2x2iLann xnbnii aij的计算公式为mi0aii/ 0 /aiibiibi0.0mihaija.0 ij0miaij,i, j 2,3,L ,n式中 mii,bi1,这样就完成了第i步消元.2）对所得线性方程组中由第2, 3

21、,，n个方 程组成的n-1元线性方程组做同样的处理，可得到第 2步消元后的线性方程组式中口2山2©2的计算公式为“2ai2/ a220 00L0.0a1 X|a2 x?a13 X3a1n Xnb111L1,1a?2 X2a23 X3a2n Xnbz2L2.2a33 X3a3n Xnb3M2L2.29n3X3ann Xnbn211bibimi2b22 1 1 aijaijm(2a2j , i, j 3,4 L , n3）第k步消元过程的计算公式1, k 1mkaik/akkk1,k 1bbmudk a ij1 aijBka,1 , i, j k 1,k 2,L ,nGuass 消当做到

22、第n-1步消元后，就完成了 元过程，得到上三角方程组0aii xioa2 X?1a?2 x?1a2nXnOn 1bnnann Xn二、回代过程1）在上三角方程组的最后一个方程中解出 xn，得 xnbyi）/ann1）2）将Xn的值代入倒数第2个方程，再解 出Xn 1，得Xn i （bnni2） anni2nxn）/anni2n i3）依次回代，得计算xk的公式为Xk (bkk1)akk 1)Xj)/akk 1) (k n 2,n 3,L ,1)j k 1当k 1时，就完成了回代过程，从而完成了Gauss消元法的全过程，得到所求解.要注意的是，计算公式中分母不能为 零，于是可以得到如下 Gaus

23、s消元法计算公 式。Gauss消元法计算公式1.对k1,2, ,n 1，计算k 1k 1k 1mikaik/ akkakk0,k , k 1, k 1bibimik bkkk 1k 1ajaijmikakj, i, j k 1,k2丄,n2对 k n, n 1,L ,1，计算nXk (bkk1)aj/akk1)j k 12)分析(1) Gauss消元法的计算量Gauss消元法由消元过程和回代过程两 部分组成，消元过程的计算量来自计算 a(k)， bi(k)所用的乘法和计算 mik所用的除 法。容易得出Gauss消元法的消元过程计算 量为消元步 12n 1乘法次数(n 1)n (n 2)(n 1

24、)除法次数n 1n 2因此消元过程计算量为n 1n 1n21N 消k(k 1)k ；(n2 1) j(n 1)k 1k 132类似地可算出Gauss消元法的回代过程的计 算量n回1n（n 1）,于是得Gauss消元法的计算量为3n2 nNn333当n很大时，n牛由于科学计算中，变元个数n都很大，因此也 常说Gauss消元法的计算量为n3(2) Gauss消元法的矩阵解释借助矩阵的理论，能更清楚地看到 Gauss消元法的本质，也可得出易于推广的内容。Gauss消元法过程实际是对Ax b的增广矩阵 (A，b)做第三种行初等变换，它对应着用第三种初 等矩阵1stM ikpst n n , pstmi

25、ks i,t k0其它左乘要变换的增广矩阵 .Gauss消元过程的第一步消元的矩阵描 述为M n1M n 11 M 21(A,b) (A(1) ,b(1) 式中 A(1) 与 b(1) 是消元后的线性方程组的系 数矩阵和常数项。记M 1 M n1M n 11 M 21利用矩阵运算与相等定义，有M1A A(1) 和 M1b b(1)类似地，经过第 n-1 步消元后，可以得出M n 1M n 2 M1A A(n 1)M n 1M n 2 M1b b(n 1)式中 A(n 1) 是变换后的上三角方程组的系数 矩阵，若记 M MnlMn2 Mi，有 MA A(n 1) 和 Mb b(n 1) ，可以证

26、明 M 1是单位下三角矩 阵，且注意到 A(n 1) 是上三角矩阵 . 若令L M 1， U A(n 1)则有A LU (矩阵的一种分解形式) 这种矩阵分解为寻找新的线性方程组解法 创造了条件 .(3) Gauss消元法可使用的条件Gauss消元法要求akP 0(k 1,2,L ,n)，什么 样的线性方程组满足这个要求显得很重 要，下面不加证明地给出两个结果 .定理9 akk1) 0(k 1,2, , n)的充要条件是矩阵 A 的所有顺序主子式不为零定理10若线性方程组Ax b的系数矩阵 A 的顺序主子式都不为零，则可用 Gauss 消元法求解此方程组 .(4) Gauss消元法的改进缺点1:

27、必须在ak：10(k 1,2, , n)都成立时才能使 用，这不能令人满意；缺点2：在使用Gauss消元法进行计算机求解 时，人们发现有时求出的解是错误的.例5设线性方程组2x1 2x24x1 7x23x37x32x1 4x2 5x37试用Gauss消元法求解之例6研究下面线性方程组0.0001x1 x2 1x1 x2 2的 Gauss 消元法求解结果，假设计算在浮点十进制数的计算机上求解 .4位主元 .通常称消元法中用作分母的数为 列主元消元法 全主元消元法2. LU分解法基本思想将方程组Ax b的系数矩阵A分解为下 三角矩阵L与上三角矩阵U的乘积，即 A LU，使求解Ax b的问题变为求解

28、两个 系数矩阵为三角矩阵的|Ly b和Ux y的问 题.Ax b A LU LUx bLy bUx y1) 构造原理Gauss 消元法的矩阵解释说明矩阵 A 可以 分解为下三角矩阵与上三角矩阵相乘的形 式 . 知道矩阵有这种三角分解的结构后，我 们可以利用矩阵运算及相等的概念直接由 A 求出其分解矩阵 L 和 U.具体做法为先设出 L 和 U 的形式，再由A LU 求出 L 和 U 的元素 .矩阵的三角分解有如下几种常用形式(1)Doolittle 分解分解后 A LU ，L 和 U 的结构为1u11u12Lu1nl21 1u22Lu2nLl31 l321， U 22 2n， O Mln1 l

29、n2lnn 1 1unn(2)Grout 分解分解后A LU , L和U的结构为1 u12 u13 Lu1n11l21 l221u23Lu2n,Uln1 ln2 Lnnun 1n1(3) LDU 分解分解后 A LDU ，L、D 和 U 的结构为1l211Ll31l32O,DMM1ln1ln2Klnn 1 1d1d2Odn1 u12u13Lu1n1u23Lu2nU1OMOun 1n1Doolittle 分解算法构造过程由 A LU 及矩阵乘积和相等概念，有U2j%(1,0,0L,0) MUij(j 1,2L ,n)UnjUii0ai1(li1, li2,L , li, i 1,1,0,L ,0

30、)hiuii(i 2,3,L , n)M0得计算公式Uij aij (j 1,2,L , n), hi不/口行(i 2,3,L , n)当i j时，有Uijaij(hl,li2丄li, i 1,1,0丄，0)U2jMi 1likUkj uijk 1Unj从而得到矩阵U的计算公式i 1Uij aijlikUkjk 1同理有当i,可得到矩j ij 时，aijlikUkj hjUjjk 1阵L的计算公式j ilij (aijlik Ukj ) / Ujjk 1s若规定式中求和项在s 1时表示不求k 1和，则计算Doolittle分解的L和U元素的公式用后两个表示：i 1uijaijlikukji jk 1j 1lij (aijlik ukj ) / u jj i jk 1用算出的|j，回代求出Ly b的解y ;用算出的 uij 及 y ，回代求出 Ux y 的解 .用上述过程求解 Ax b 的方法称为Doolittle 分解 方法 .2) 分析(1)A 可以进行 Doolittle 分解的条件定理 11 若非奇异矩阵 A 有 Doolittle 分