计算方法第三章解线性方程组的

1、第三章 解线性方程组的数值方法 把一般线性方程组化为系数矩阵为三角矩阵的线性方程组来求解。 直接方法：若计算过程中没有舍入误差，经过矩阵的线性方程组。的精确解的方法。主要用于解系数矩阵是低阶稠密有限次的算术运算，可求得方程组 Ax=b （|A|0）基本思想：基本思想：) 13 (2222211212111 nnnnnnnnbxubxuxubxuxuxu,nnnnubx 112111,uxubxnjjj 如: 上三角矩阵所对应的线性方程组,)1)(1()1(11 nnnnnnnuxubx解为) 23 (221122221211111 nnnnnnbylylylbylylbyl,1111lby 下

2、三角矩阵所对应的线性方程组,2212122lylby ,计算量（乘除法的主要部分）为 n2/2.解为nnnjjjnnlylby 111第一节 消元法 一、Gauss顺序消元法按自然顺序进行的消元法。记记 Ax=b Ax=b 为为 A(1)x=b (1) A(1)x=b (1) ，即即 nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111 )1()1(2)1(21)1(11)1(2)1(22)1(221)1(21)1(1)1(12)1(121)1(11nnnnnnnnnbxaxaxabxaxaxabxaxaxa 1、基本思想：将化为与之等价的三角

3、形方程组来求解，具体步骤如下： )2()2(2)2(2)2(2)2(22)2(22)1(1)1(12)1(121)1(11nnnnnnnnnbxaxabxaxabxaxaxa 若a11(1)0，记 li1= ai1(1) /a11(1), i=2 , 3 , , n , 第i个方程减去第一个方程乘以- li1得 若用矩阵表示，相当于用一个初等矩阵 L1 左乘 10111211nllLA(1) 和和 b(1) , 即即 L1A(1) =A(2) , L1 b(1)=b(2)，其中其中 )2()2(2)1(1)2(nbbbb 若akk(k)0，记 lik= aik(k) /akk(k), i=k+

4、1 , k+2 , , n 第 i 个 方 程 减 去 第 k 个 方 程 乘 以 - l i k ， 用 矩 阵 表 示 ， 111, 1knkkkllLb(k) , 分别得到分别得到LkA(k) =A(k+1) , Lk b(k)=b(k+1)，其中其中相当于用一个初等相当于用一个初等矩阵矩阵Lk 左乘左乘A(k)和和最后得最后得即即 A(n)x=b (n)方程组的的解为：方程组的的解为：1,2,1, 1,1)()()()()( nnixabaxabxnijjiijiiiiiinnnnnn前面称为消元的过程，后面称为回代的过程。前面称为消元的过程，后面称为回代的过程。 )()()2(2)2

5、(22)2(22)1(1)1(12)1(121)1(11nnnnnnnnnnbxabxaxabxaxaxa以上以上n-1步消元过程就是步消元过程就是)()1(1221nnnAALLLL 11221)( LLLLLnnL 为单为单位下三位下三角矩阵角矩阵 11111,21323121nnnnllllllL令令 )() 1(, 1) 1(1, 1) 2(2) 2(12) 2(22) 1(1) 1(11) 1(12) 1(11)(nnnnnnnnnnnnnnaaaaaaaaaaAU)()1(1221nnnbbLLLL U为上三角矩阵为上三角矩阵即即 A=LU 其中其中 L 为单位下三角矩阵为单位下三

6、角矩阵 , U为上三角矩阵。从而得求为上三角矩阵。从而得求矩阵行列式的计算公式矩阵行列式的计算公式)33()det(1)()()1(11)2(22)1(11 niiiinnnnnnaaaaaA )1()1()1(2)1(1)1(2)1(2)1(22)1(21)1(1)1(1)1(12)1(11nnnnnnnbaaabaaabaaa nnnniirrlnirrl1)1(22, 3其中其中lik= aik(k) /akk(k), k=1,2,n ,i=k+1 , k+2 , , n,计算量为计算量为 n3/3。nirrlii, 211 )2()2()2(2)2(2)2(2)2(22)1(1)1(1

7、)1(12)1(11nnnnnnbaabaabaaa )()()2(2)2(2)2(22)1(1)1(1)1(12)1(11nnnnnnnbabaabaaa2、高斯消元法可用矩阵表示为：、高斯消元法可用矩阵表示为：例例1 解方程组解方程组 02115472321321321xxxxxxxxx解：消元解：消元 0121111547112回代得回代得, 3263 x 3235 . 2rr 620033307112 5 . 35 . 05 . 203330711231212124rrrr , 233332 xx127321 xxx 3、高斯消元法的条件与算法量定理定理1 如果在消元过程中如果在消元过

8、程中 A的主元素不为零，即的主元素不为零，即 （ k=1,2,n) ,则可通过高斯消元法出则可通过高斯消元法出Ax=b 的解。的解。引理引理 在高斯消元过程中在高斯消元过程中A的主元素不为零，即的主元素不为零，即 （k=1,12,n)的充要条件是矩阵的充要条件是矩阵A的各的各阶阶顺序主子式不为零，即顺序主子式不为零，即定理定理2 Ax=b 高高 斯消元法求解的充分必要条件是：斯消元法求解的充分必要条件是： 系数矩阵系数矩阵 A 的各阶顺序主子式均不为零。的各阶顺序主子式均不为零。 0)1(kkka0)1(kkka0111 aDnkaaaaDkkkkk, 3 , 2, 01111|max|)()

9、(klknlkkikaa 二、主元素消元法（条件det A0） 1.列主元素消元法列主元素消元法 当当akk(k)=0 时，高斯消元法无法进行；或时，高斯消元法无法进行；或 | akk(k) |1时，带来舍入误差的扩散。时，带来舍入误差的扩散。第第 k 步先选列主元步先选列主元aik(k) , 其次将其次将aik(k)（行对换）换（行对换）换到到 akk(k)的位置上，再消元，其中的位置上，再消元，其中|max|)(,)(klsnslkkijaa 2.全主元素消元法全主元素消元法 第第 k 步先选主元步先选主元aij(k) , 其次将其次将aij(k) （行、列对换）（行、列对换）换到换到 a

10、kk(k)的位置上的位置上, 再消元再消元,其中其中 113200001. 100001. 02121xxxxx 103000. 0101000. 0102000. 0101000. 0101000. 0101000. 040, 1101000. 012 xx解：高解：高斯消元法斯消元法例例2 216102 . 0rr 664102000. 0102000. 0101000. 0101000. 0101000. 0 列主元消元法 101000. 0101000. 0101000. 0101000. 0101000. 0101000. 0101000. 0101000. 0103000. 010

11、1000. 0102000. 044A. 1101000. 0, 1101000. 012 xx21rr 21105 . 05rr 例例3 分别用高斯消分别用高斯消元法和列主元消元法元法和列主元消元法求矩阵的行列式。求矩阵的行列式。 643. 5072. 12623. 4712. 3132108A0det000103 . 0102 . 003210106 . 0104 . 00103 . 0102 . 00321099899998 AA解：解：高高斯斯消消元元法法91210 rr913102 rr232rr 大数大数“吃掉吃掉”了小数了小数列列主主元元消消元元法法84997.11det1018

12、6555. 0001018018. 0103176. 00643. 5072. 12103 . 0102 . 001018018. 0103176. 00643. 5072. 123210623. 4712. 31643. 5072. 12831 ArrA1 AEEA矩矩阵阵的的初初等等行行变变换换约约当当消消元元法法高高斯斯三、高斯三、高斯约当消元法（约当消元法（det A0） 1 高斯高斯-若当消元法若当消元法 在高斯消元过程中，先将主元素化为在高斯消元过程中，先将主元素化为1，而后，而后将主元所在列的其它元素均化为零，最后将系数矩将主元所在列的其它元素均化为零，最后将系数矩阵化为单位矩阵

13、阵化为单位矩阵 E，无需回代就可求得原方程的解，无需回代就可求得原方程的解，此法称为高斯此法称为高斯约当消元法。约当消元法。2 逆矩阵逆矩阵第二节 矩阵的三角分解 一、LU分解法 消元法的实质是对增广矩阵作初等行交换消元法的实质是对增广矩阵作初等行交换,而初等而初等变换是可以用矩阵运算来描述的变换是可以用矩阵运算来描述的.消元过程相当于下述消元过程相当于下述矩阵乘法运算。矩阵乘法运算。 yUbALLLLnn 1221因此，由分块矩阵乘法可得因此，由分块矩阵乘法可得ybLLLLUALLLLnnnn 12211221令令11221)( LLLLLnn可得可得bLyLUA 可见只要消元过程能进行到底

14、，就有以下等价关系可见只要消元过程能进行到底，就有以下等价关系 LUA Uxy 令令bAx bLUx )53( yUxbLy)43( 消元过程相当于分解消元过程相当于分解 A为为单位下三角阵单位下三角阵L与上三角与上三角阵阵U的乘积，解方程组的乘积，解方程组Ly=b，回代过程就是解，回代过程就是解方程组方程组Ux=y。其中。其中 11112121nnlllL )()1(, 1)1(1, 1)2(2)2(12)2(22)1(1)1(11)1(12)1(11nnnnnnnnnnnnnaaaaaaaaaaU的的L为为n阶单位阶单位下三角阵、下三角阵、U为为上三角阵上三角阵. 称式称式(3-4)为矩阵

15、为矩阵A的的LU分解或三角状分解。等价关分解或三角状分解。等价关系（系（3-5）说明，要解线性方程组）说明，要解线性方程组 Ax=b，可利用矩，可利用矩阵阵A的的LU分解转化为解两个三角形方程组，这种解分解转化为解两个三角形方程组，这种解方程组的方法称为方程组的方法称为LU分解法或三角状分解法。分解法或三角状分解法。定理定理2 若矩阵若矩阵A非奇异，则非奇异，则A能分解为能分解为LU的充分必的充分必要条件是要条件是A的顺序主子式不为的顺序主子式不为0，即，即 1. LU分解的条件分解的条件, 0, 0222112112111 aaaaa0,1111 nnnnnaaaa定理定理3 若非奇异矩阵若

16、非奇异矩阵A有有LU分解分解,则此分解是唯一的。则此分解是唯一的。2 LU分解的计算公式分解的计算公式 nnnnnnnnuuuuuuuuuuUllllllL3332232211312113213231211111令令 比较式比较式 A=LU 两端的元素两端的元素, 按图按图3-1所示顺序逐框进行所示顺序逐框进行,先求先求 ukj 后求后求 lik . 由第一框可得由第一框可得), 3, 2(), 2, 1(111111niualnjauiijj a11 a12 a1k a1n u11 u12 u1k u1n 第第1框框a21 a22 a2k a2n l21 u22 u2k u2n 第第2框框

17、ak1 ak2 akk akn lk1 lk2 ukk ukn 第第k框框 an1 an2 ank ann ln1 ln2 lnk unn 第第n框框图（图（3-1）框图）框图 1111),2,1(),1,(kskkikskisikkskjskkskjnkkiululankkjuula得得 )63(, 2, 1, 1,1111 nkki/uulalnkkjulaukkksskisikikkssjkskjkj假设前假设前k -1框元素已求出，则由框元素已求出，则由 有了矩阵有了矩阵 A 的的LU分解计算公式分解计算公式 (3-6), 解线性方程解线性方程组组 Ax=b 就转化为依次解下三角方程组

18、就转化为依次解下三角方程组 Ly=b 与上三角与上三角方程组方程组 Ux=y, 其计算公式如下：其计算公式如下： ) 73(1 , 1,/, 2 , 1111 nnkuxuyxnkylbykknKsskskkksskskk Ly=b Ux=y例例3 求矩阵求矩阵 1256144412解解 用紧凑格式用紧凑格式的的LU分解。分解。 u11=2 u12=1 u13=4 1213532 l22421 l32631 l212422u542123u7)7(1431233u所以所以 700720412113012001LUA 当矩阵当矩阵 A 对称且对称且 其顺序主子式均不为其顺序主子式均不为0时由定理时

19、由定理2可知其可知其LU分解必存在。分解必存在。且且二、二、 LDLT (Cholesky) 分解法分解法 11122211111122211uuuuuuuuuUnnnnDM 于是于是 A=LU=LDM. 又据又据A的对称性有的对称性有 TTTDLMAA 其中其中 M T 为单位下三角阵为单位下三角阵, DLT 为上三角阵为上三角阵, 因此上因此上式也是式也是A的的 LU 分解分解.由由 LU 分解的唯一性可知分解的唯一性可知, 应有应有TTLMLM 定理定理4 设矩阵设矩阵 A 对称且各阶顺序主子式均不为对称且各阶顺序主子式均不为0时，时，则必存在单位下三角阵则必存在单位下三角阵 L 及对角

20、阵及对角阵D , 使使 A=LDLT (3-8) 式（式（3-8）称为对称矩阵的）称为对称矩阵的 LDLT 分解分解.由由 A 的的 LU 分解式分解式(3-6)可得乔累斯基分解的计算公式可得乔累斯基分解的计算公式 11112)1, 2 , 1()(), 2 , 1(kskkjijjikikijijjiiiikdlldalnildad此时此时, 解方程组解方程组 Ax=b 等价于解等价于解LDLTx=b，而后者可，而后者可转化为依次解两个三角形方程组转化为依次解两个三角形方程组 Ly=b , LTx=D-1y，其计算公式如下其计算公式如下 ) 93(1 , 1, 2 , 1111 nkjjjk

21、kkkkjjkjkknnkxldyxnkylby这种解方程组的方法称为乔累斯基分解法或这种解方程组的方法称为乔累斯基分解法或 LDLT 分解法。分解法。 三、平方根法（三、平方根法（LLT 分解法）分解法） 当矩阵当矩阵 A 对称正定时对称正定时 , 其顺序主子式均大于其顺序主子式均大于0,由由定理定理4可知其可知其 LDLT 分解存在，且分解存在，且 niuii,2,10 2122112211DuuuuuuDnnnn 11LDL记记则则TLLA11 L1为下三角矩阵为下三角矩阵.则则 A=LDLT =LD1D1LT= (LD1)( LD1)T nnnnuuulll22112121111定理定

22、理5 设矩阵设矩阵 A 对称正定对称正定,则必存在下三角阵则必存在下三角阵 L, 使使 A=LLT (3 10) 式（式（3-10）称为正定矩阵的）称为正定矩阵的 LLT 分解分解.同同 LU 分解公式的求法分解公式的求法,可得可得LLT分解的计算公分解的计算公式式)113(), 2 , 1(), 2; 1, 1()(2111211 nilalniiklllalijijiiiikjkkkjijikik当当 A 对称正定时对称正定时, 解方程组解方程组 Ax=b 等价于解等价于解LLTx=b,而而后者可转化为依次解两个三角形方程组后者可转化为依次解两个三角形方程组 Ly=b , LTx=y，其计

23、算公式如下其计算公式如下 )123(1, 1,(, 2 , 1/ )(111 nkjjjkkkkjkkjkjkknnkxlyxnklylby这种解方程组的方法称为平方根法或这种解方程组的方法称为平方根法或LLT 分解法。分解法。 四、追赶法四、追赶法 当矩阵当矩阵A为三对角矩阵，即为三对角矩阵，即 nnnnnnndddddbacbacbacbA12111122211在在 A 的的LU 分解中分解中, L取下三角阵取下三角阵, U 取单位上三角取单位上三角阵阵,这样求解方程组这样求解方程组Ax=d的方法称为追赶法的方法称为追赶法.第四节第四节 方程组的性态和条件数方程组的性态和条件数一、向量与矩

24、阵的范数一、向量与矩阵的范数 平面上任何一向量平面上任何一向量 a=(a1 , a2)T 的长度为的长度为 2221aa a |a|0 ，等号仅当，等号仅当 a=0 时成立：时成立： 对任意实数对任意实数 , | a|=| | |a| |a+b|a|+|b| （三角不等式）。（三角不等式）。 ，具以下性质：，具以下性质： |x|0 ，等号仅当，等号仅当 x=0 时成立；时成立； 对任何实数对任何实数 , | x|=| | |x|； |x+y| |x| +|y| （三角不等式）（三角不等式） ；则称则称 |x| 为向量为向量 x 的范数或模。的范数或模。定义定义1 对任意对任意 n 维向量维向量

25、 x Rn，若对应非负实，若对应非负实数数 |x| ，满足，满足设设 x = ( x1 , x2 , , xn)T ，常用的向量范数有，常用的向量范数有 inixx 1maxnxxxx 211222212nxxxx 它们分别叫做向量的它们分别叫做向量的-范数、范数、1-范数、范数、2-范数、范数、p -范范数（数（0p+）。）。 ppnpppxxxx121)( 不难证明这几种范数满足下述关系不难证明这几种范数满足下述关系 xnxxxnxx21 事实上，对 Rn 上任意两种向量范数 |x| , |x| ，都存在与 x 无关的正常数 c1 , c2 使 这种性质称为向量范数的等价性。这种性质称为向

26、量范数的等价性。 xcxxc21 定义定义2 对任意对任意n阶方阵阶方阵 A=(aij)nn，若对应一个非，若对应一个非负实数负实数 |A| ，满足，满足 非负性非负性 |A| 0 且且|A|=0当且仅当当且仅当A=0；齐次性齐次性 对任意实数对任意实数 , | A|=| | |A|；三角不等式三角不等式 对任意两个对任意两个n阶方阵阶方阵A与与B, 有有|A+B| |A|+|B|；相容性相容性 |AB| |A| |B|则称则称 |A| 为矩阵为矩阵A的范数。的范数。 常用的矩阵范数有常用的矩阵范数有)(maxmaxmax211111AAAaAaATniijnjnjijni 它们分别叫做矩阵的它们分别叫做矩阵的-范数、范数、1-范数、范数、2-范数。范数。 （矩阵的行范数）（矩阵的行范数）（矩阵的列范数）（矩阵的列范数）max(ATA)为为ATA的最大特征值的最大特征值,由于矩阵由于矩阵2-范数与范数与ATA 的特征值有关，所以又称为谱范数。的特征值有关，所以又称为谱范数。例例4 设设 4321