计算方法Chapter05 - 线性方程组的解法

1、五线性方程组的解法 2 线性方程组的解法线性方程组的解法 线性方程组求解概述线性方程组求解概述 迭代法迭代法 消元法基本思想消元法基本思想 高斯消去法高斯消去法 高斯高斯-约当消去法约当消去法 列主元消去法列主元消去法 方程组的病态问题方程组的病态问题 3 引言引言 实际中，实际中，存在大量的解线性方程组的问题。存在大量的解线性方程组的问题。 很多数值方法到最后也会涉及到线性方程组的求解问题：如很多数值方法到最后也会涉及到线性方程组的求解问题：如 样条插值的样条插值的M和和m关系式，曲线拟合的正则方程组等问题。关系式，曲线拟合的正则方程组等问题。 11 112211 21 122222 1 1

2、22 , , . nn nn nnnnnn a xa xa xb a xa xa xb a xa xa xb 其中其中 n xxx, 21 未知量未知量 ij a 第第i i个方程第个方程第j j个个 未知量未知量x xj j的系数的系数 常数项常数项 全为全为0 0 齐次线性方程组齐次线性方程组 否则为非齐次否则为非齐次 线性方程组线性方程组 4 上述线性方程组表示成矩阵形式为：上述线性方程组表示成矩阵形式为： bAx 系数矩阵系数矩阵 未知量列向量未知量列向量 常数项列向量常数项列向量 问题：问题： (1) 方程组是否有解方程组是否有解? (2) 如果有解如果有解, 如何求出它的所有解如何

3、求出它的所有解? 求解求解Axb 为增广矩阵为增广矩阵 bAA 引言引言 5 det( ) 0A 克莱姆法则：当且仅当克莱姆法则：当且仅当时，有唯一的解，而且解为：时，有唯一的解，而且解为： nnninnin nii i i i aabaa aabaa DAD D D x 111 11111111 det),det(, （1 1）计算）计算n+1n+1个个n n阶行列式阶行列式. . （计算一个（计算一个n n阶行列式就需要做阶行列式就需要做(n-1)n!(n-1)n!次乘法次乘法. . 要计算要计算n+1n+1个个n n阶行列式阶行列式, , 共需做共需做(n(n2 2-1)n!-1)n!次

4、乘法）次乘法）. . （2 2）做）做n n次除法才能算出次除法才能算出x xi i(i=1, n).(i=1, n). （3 3）用此法，需作乘除法的运算：）用此法，需作乘除法的运算： N=(nN=(n2 2-1)n!+n-1)n!+n 例如例如, ,当当n=10(n=10(即求解一个含即求解一个含1010个未知量的方程组个未知量的方程组), ), 次数共为次数共为3265921032659210 次；当次；当n n100100，101033 33次 次/ /秒的计算机要算秒的计算机要算1010120 120年 年 克莱姆法则不能用于计算方程组的解克莱姆法则不能用于计算方程组的解 引言引言

5、6 解线性方程组的方法可以分为解线性方程组的方法可以分为2类：类： 迭代法：迭代法：是将方程组的解看作某种极限过程的向量极限的值， 用迭代过程完成计算极限，在用迭代算法时，不可能将极限 过程算到底，只能将迭代进行有限多次，得到满足一定精度 要求的方程组的近似解。 特点：特点：速度快，但有误差 直接法：直接法：经过有限次四则运算，假定每一步运算过程没有舍 入误差，最后得到方程组的解是精确解。 特点：特点：准确，可靠，理论上得到的解是精确的 一般地：对低阶方程组用直接法，对高一般地：对低阶方程组用直接法，对高 阶方程组和稀疏方程组用迭代法求解。阶方程组和稀疏方程组用迭代法求解。 引言引言 7 迭代

6、法迭代法 Jacobi迭代法迭代法 迭代格式：迭代格式： 设有设有n 阶方程组阶方程组 其中系数矩阵非奇异，且其中系数矩阵非奇异，且 ，i=1,2，n ii a0 将上式变形为将上式变形为 nn nn nnnn nnn nn xa xa xa xb a xa xa xaxb a xa xaxaxb a 112213311 11 221123322 22 1122,11 1 () 1 () 1 () nn nn nnnnnn a xa xa xb a xa xa xb a xa xa xb 11112211 21122222 1122 8 建立迭代格式建立迭代格式 kkkk nn kkkk nn

7、 kkkk nnnn nnn nn xa xa xaxb a xa xaxaxb a xaxaxaxb a (1)()()() 112213311 11 (1)()()() 221123322 22 (1)()()() 1122,11 1 () 1 () 1 () 上面的迭代式称为上面的迭代式称为雅可比（雅可比（Jacobi）迭代格式）迭代格式。 迭代法迭代法 n kk iiijj j ii j i xba xin a (1)( ) 1 1 (),1,2, 9 迭代法迭代法 高斯高斯-塞德尔迭代法塞德尔迭代法 假设已知近似值（假设已知近似值（x1(k), x2(k), x3(k), , xn(

8、k), ）, 则迭代格式：则迭代格式： 其中系数矩阵非奇异，且其中系数矩阵非奇异，且 ，i=1,2，n ii a0 k kk kk kkk nn kk nn nnn n nn k n k nn a xa xaxb a aa xaxb a aaab a x xx xxxx ()()() 12213311 11 ()() 212 (1) 1 (1)(1) 21 (1)(1)(1)(1) 12 3322 22 121,1 1 () 1 () 1 () in kkk iiijjijj jj i ii xba xa xin a 1 (1)(1)( ) 11 1 (),1,2, 10 迭代法迭代法 超松弛

9、法超松弛法 实际上是高斯实际上是高斯-赛德尔迭代公式的一种加速方法。赛德尔迭代公式的一种加速方法。 in kkk iiijjijj jj i ii xba xa x a 1 (1)(1)( ) 11 1 () 迭代： in1,2, kkk iii xxx (1)(1)( ) =(1) 加速： 松弛因子松弛因子 11 向量和矩阵的范数向量和矩阵的范数 向量的范数：向量向量的范数：向量“大小大小”的某种衡量的某种衡量 T n xxxxx 12 (,) , 任给向量其范数记为 基本性质：基本性质： p对于任意向量对于任意向量x，| x |0，当且仅当，当且仅当x=0时，时， | x |=0 p对于任

10、意实数对于任意实数及任意向量及任意向量x，有，有 | x |=| | | x | p对于任意向量对于任意向量x和和y，有，有 | x+ y | x |+| y | 12 向量和矩阵的范数向量和矩阵的范数 3种常用范数：种常用范数： p2-范数（长度）范数（长度） p1-范数范数 p-范数范数 n i i xx 2 1/2 2 1 () n i i xx 1 1 i i n xx 1 max 13 向量和矩阵的范数向量和矩阵的范数 矩阵的范数：矩阵的范数： AxAx A n/对于给定的 阶方阵 ，将比值的 矩阵 上确界 称为的范数 直接由定义知，对于任意向量直接由定义知，对于任意向量x，有：，有

11、：| A x | A | | x | 基本性质：基本性质： p对于任意方阵对于任意方阵A，| A |0，当且仅当，当且仅当A=0时，时， | A |=0 p对于任意实数对于任意实数及任意方阵及任意方阵A ，有，有 | A |=| | | A | p对于任意方阵对于任意方阵A和和B，有，有 | A+ B | A|+| B | | AB | A| | B | 14 消元法消元法 1.三角方程组的解三角方程组的解 ni a b xaaadiagA ii i inn , 1,),( 2211 11 11 2222 nnnn a xb a xb a xb 对角形方程组：对角形方程组： 下面有3种方程的解

12、我们可以直接求出： 15 ni l xlb x lll ll l A ii i j jiji i nnnn , 1, 1 1 21 2221 11 下三角形方程组：下三角形方程组： 11 11 21 12222 1 122nnnnnn l xb l xl xb l xl xl xb 消元法消元法 16 1 , 1222 11211 ni u xub x u uu uuu A ii n ij jiji i nn n n 11112211 22222 nn nn nnnn uxuxuxb uxuxb uxb 上三角形方程组：上三角形方程组： 消元法消元法 17 例：解方程组例：解方程组 12 12

13、 1 328 xx xx 方程方程（3 3）加到方程中得：）加到方程中得： 2 1x 12 2 1 055 xx x 代入得代入得 1 2x 相当于对方程组得增广矩阵做行的初等变换：相当于对方程组得增广矩阵做行的初等变换： 111111 328055 AAbAb 消元法消元法 18 对方程组，作如下的变换，解不变对方程组，作如下的变换，解不变 交换两个方程的次序交换两个方程的次序 一个方程的两边同时乘以一个非一个方程的两边同时乘以一个非0 0的数的数 一个方程的两边同时乘以一个非一个方程的两边同时乘以一个非0 0数，加到另一个方程数，加到另一个方程 因此，对应的对增广矩阵因此，对应的对增广矩阵

14、(A，b)，作如下的变换，解不变，作如下的变换，解不变 交换矩阵的两行交换矩阵的两行 某一行乘以一个非某一行乘以一个非0 0的数的数 某一个乘以一个非某一个乘以一个非0 0的数，加到另一行的数，加到另一行 消元法消元法 ：就是对增广矩阵作上述行的初等变换，变：就是对增广矩阵作上述行的初等变换，变 为我们已知的为我们已知的3种类型之一，而后求根种类型之一，而后求根 消元法的基本思想消元法的基本思想 思路：首先将思路：首先将A化为上三角阵化为上三角阵 ，再回代求解。，再回代求解。 = nnnnn n n baaa baaa baaa 21 222221 111211 (1)(1)(1)(1)(1)

15、 11121311 (2)(2)(2)(2) 222322 (3)(3)(3) 3333 ( )( ) 0 00 000 n n n nn nnn aaaab aaab aab ab 高斯消去法高斯消去法 Step 1：设：设 ，计算因子，计算因子0 )1( 11 a (1)(1) 1111 /(2,., ) ii maain 将增广矩阵将增广矩阵第第 i 行行 + mi1 第第1行行， (2)(1)(1) 11 (2)(1)(1) 1 1 ( ,2,., ) ijijij iii aam a i jn bbm b 其中其中 nnnnn n n baaa baaa baaa 21 222221

16、 111211 )2()2()2( 2 )2( 2 )2( 2 )2( 22 111211 0 0 nnnn n n baa baa baaa 实施步骤如下：实施步骤如下： 运算量运算量 ：(n-1)(1+n) （n-1）次运算 （n-1）（n-1）次运算 （n-1）次运算 高斯消去法高斯消去法 )3()3()3( 3 )3( 3 )3( 3 )3( 33 )2( 2 )2( 2 )2( 23 )2( 22 11131211 00 00 0 nnnn n n n baa baa baaa baaaa 运算量运算量 ：(n-2)(1+n-1) =(n-2)n )2()2()2( 2 )2( 2

17、)2( 2 )2( 22 111211 0 0 nnnn n n baa baa baaa Step 2：设：设 ，计算因子，计算因子 (2) 22 0a (2)(2) 2222 /(3,., ) ii maain 将增广矩阵将增广矩阵第第 i 行行 mi2 第第2行行， (3)(2)(2) 22 (3)(2)(2) 22 ( ,3, .,) ijijij iii aam a i jn bbm b 其中其中 （n-2）次运算 （n-2）（n-2）次运算 （n-2）次运算 高斯消去法高斯消去法 Step k：设：设 ，计算因子，计算因子 且计算且计算 0 )( k kk a ( )( ) /(1

18、,., ) kk ikikkk maaikn (1)( )( ) (1)( )( ) ( ,1,., ) kkk ijijikkj kkk iiikk aam a bbm b i jkn 将增广矩阵将增广矩阵第第 i 行行 mik 第第k行行。 运算量：运算量：(nk)(1nk1) =(nk)(nk2) （n-k）次运算 （n-k）（n-k）次运算 （n-k）次运算 高斯消去法高斯消去法 共进行共进行(n-1)步步 )( )2( 2 )1( 1 2 1 )( )2( 2 )2( 22 )1( 1 )1( 12 )1( 11 . . . . . . . . . . . . n n n n nn

19、n n b b b x x x a aa aaa )()( )3( 3 )3( 3 )3( 33 )2( 2 )2( 2 )2( 23 )2( 22 11131211 000 00 0 n n n nn n n n ba baa baaa baaaa 消元的运算量为：消元的运算量为： 32 1 1 5 ()(2) 326 n k nnn nk nk 高斯消去法高斯消去法 回代回代: : )()( / n nn n nn abx ) 1., 1( )( 1 )()( ni a xab x i ii n ij j i ij i i i 回代的运算量为：回代的运算量为： 总运算量为：总运算量为： G

20、aussian Elimination 的总乘除次数为的总乘除次数为 ，运算量为，运算量为 级。级。 nn n 3 1 3 2 3 3 3 n （n1）n/2 32 1 1 5 ()(2) 326 n k nnn nk nk 消元的运算量为：消元的运算量为： 高斯消去法高斯消去法 注意到，计算过程中注意到，计算过程中 ( )k kk a处在被除的位置，因此整个计算过程要保证它不为处在被除的位置，因此整个计算过程要保证它不为0 所以，所以，Gauss消元法的可行条件为：消元法的可行条件为： ( ) 0 k kk a 即，要求即，要求A的所有顺序主子式均不为的所有顺序主子式均不为0: ni aa

21、aa iii i , 1, 0det 1 111 p 因此，有些有解的问题，不能用因此，有些有解的问题，不能用Gauss消元求解消元求解 p 若若A的所有顺序主子式的所有顺序主子式 均不为均不为0，则高斯消元无需换行即可进行到底，则高斯消元无需换行即可进行到底， 得到唯一解。得到唯一解。 事实上，只要事实上，只要 A 非奇异，即非奇异，即 A 1 存在，则可通过逐次消存在，则可通过逐次消 元及行交换，将方程组化为三角形方程组，求出唯一解。元及行交换，将方程组化为三角形方程组，求出唯一解。 高斯消去法高斯消去法 与与 Gaussian Elimination 的主要区别：的主要区别： 每步作第每

22、步作第k行行 mik第第i行；行； 把把 akk(k) 所在列的上、下元素全消为所在列的上、下元素全消为0; ( ) ( ) ,1,1,1, k ik ik k kk a mikkn a 将该行上三角地部分也变为将该行上三角地部分也变为0 0 运算次数比运算次数比Gauss消元多，约为消元多，约为(n3/2)量级。量级。 高斯高斯-约当消去法约当消去法 例：单精度解方程组例：单精度解方程组 2 110 21 21 9 xx xx /* 精确解为精确解为 和和 */ .1000.00. 1 101 1 9 1 x 8个个 .8999.99. 02 12 xx 8个个 用高斯消去法计算：用高斯消去

23、法计算： 9 212111 /10maa 999 2221 110.0.01 101010am 8个个 9 221 2110bm 99 9 10100 1110 0, 1 12 xx 小可能导致计算失小可能导致计算失 败。败。 另外，如果某个另外，如果某个 ( )k kk a很小的话，会引入大的误差很小的话，会引入大的误差 列主元消去法列主元消去法 每次仅选一列中最大的元每次仅选一列中最大的元 在在Gauss消元第消元第k步之前，做如下的事情：步之前，做如下的事情： |max )()(k jk k ik nik aa 若若交换交换k行和行和j行行 行的交换，不改变方程组的解，同时又有效地克服了

24、行的交换，不改变方程组的解，同时又有效地克服了Gauss 消元地缺陷消元地缺陷 例：例： 1,1 12 xx 211 1110 9 110 211 1110 211 9 列主元消去法列主元消去法 29 方程组的病态问题方程组的病态问题 矩阵的条件数与线性方程组的性态矩阵的条件数与线性方程组的性态 给定线性方程组给定线性方程组 Ax =b，现在考察，系数矩阵，现在考察，系数矩阵 A 和常数列和常数列 b 有了微小变化有了微小变化 A，b ，它如何影，它如何影 响解向量响解向量 x，即，解向量，即，解向量 x 的变化量的变化量 x 何样？何样？ 由于由于A （或（或 b）的元素是测量得到的，或者是

25、）的元素是测量得到的，或者是 计算的结果，在前种情况下，计算的结果，在前种情况下， A （或（或 b）常常带有）常常带有 某些观测误差，在后种情况下，某些观测误差，在后种情况下， A （或（或 b）包含舍）包含舍 入误差，因此我们处理的实际矩阵是入误差，因此我们处理的实际矩阵是A + A （或（或 b+ b ）。）。 30 11 22 112112 , 11.0001211.00012.0001 xx xx 精确解 (2, 0) 精确解 (1, 1) 考察方程组考察方程组 Ax = b, 当当 A 或或 b 有微小扰动时有微小扰动时, 对对 解的影响，首先看一个例子：解的影响，首先看一个例子： 方程组的病态问题方程组的病态问题 31 方程组的病态问题方程组的病态问题 定义定义 如果矩阵如果矩阵 A 或常数项或常数项 b 的微小变化，引起的微小变化，引起 方程组方程组 Ax =b 的解的巨大变化，则称方程组为的解的巨大变化，则称方程组为“病病 态态”方程组方程组，矩阵，矩阵 A 称为称为“病态病态”矩阵矩阵；否则称方；