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

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

2、a xa xba xa xa xba xa xa xb 其中其中nxxx,21未知量未知量ija第第i i个方程第个方程第j j个个未知量未知量x xj j的系数的系数常数项常数项全为全为0 0齐次线性方程组齐次线性方程组否则为非齐次否则为非齐次线性方程组线性方程组4上述线性方程组表示成矩阵形式为：上述线性方程组表示成矩阵形式为：bAx 系数矩阵系数矩阵未知量列向量未知量列向量常数项列向量常数项列向量问题：问题：(1) 方程组是否有解方程组是否有解?(2) 如果有解如果有解, 如何求出它的所有解如何求出它的所有解?求解求解Axb为增广矩阵为增广矩阵 bAA 引言引言5det( ) 0A 克莱姆

3、法则：当且仅当克莱姆法则：当且仅当时，有唯一的解，而且解为：时，有唯一的解，而且解为：nnninninniiiiiaabaaaabaaDADDDx11111111111det),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!次乘法）次乘法）. . （2 2）做）做n n次除法才能算出次除法才能算出x xi i(i=1, n).(i=1, n).（3 3）用此法

4、，需作乘除法的运算：）用此法，需作乘除法的运算： N=(nN=(n2 2-1)n!+n-1)n!+n例如例如, ,当当n=10(n=10(即求解一个含即求解一个含1010个未知量的方程组个未知量的方程组), ), 次数共为次数共为3265921032659210次；当次；当n n100100，10103333次次/ /秒的计算机要算秒的计算机要算1010120120年年克莱姆法则不能用于计算方程组的解克莱姆法则不能用于计算方程组的解引言引言6解线性方程组的方法可以分为解线性方程组的方法可以分为2类：类：迭代法：迭代法：是将方程组的解看作某种极限过程的向量极限的值，用迭代过程完成计算极限，在用迭

5、代算法时，不可能将极限过程算到底，只能将迭代进行有限多次，得到满足一定精度要求的方程组的近似解。特点：特点：速度快，但有误差直接法：直接法：经过有限次四则运算，假定每一步运算过程没有舍入误差，最后得到方程组的解是精确解。特点：特点：准确，可靠，理论上得到的解是精确的一般地：对低阶方程组用直接法，对高一般地：对低阶方程组用直接法，对高阶方程组和稀疏方程组用迭代法求解。阶方程组和稀疏方程组用迭代法求解。引言引言7迭代法迭代法Jacobi迭代法迭代法迭代格式：迭代格式：设有设有n 阶方程组阶方程组 其中系数矩阵非奇异，且其中系数矩阵非奇异，且 ，i=1,2，niia0 将上式变形为将上式变形为nnn

6、nnnnn nnnnnxa xa xa xbaxa xa xaxbaxa xaxaxba11221331111221123322221122,111()1()1() nnnnnnnnnna xa xa xba xa xa xba xa xa xb11112211211222221122 8建立迭代格式建立迭代格式kkkknnkkkknnkkkknnnn nnnnnxa xa xaxbaxa xaxaxbaxaxaxaxba(1)()()()11221331111(1)()()()22112332222(1)()()()1122,111()1()1() 上面的迭代式称为上面的迭代式称为雅可比（雅

7、可比（Jacobi）迭代格式）迭代格式。迭代法迭代法nkkiiijjjiij ixba xina(1)( )11(),1,2, 9迭代法迭代法高斯高斯-塞德尔迭代法塞德尔迭代法假设已知近似值（假设已知近似值（x1(k), x2(k), x3(k), , xn(k), ）, 则迭代格式：则迭代格式： 其中系数矩阵非奇异，且其中系数矩阵非奇异，且 ，i=1,2，niia0 kkkkkkkknnkknnnnn nnnknknna xa xaxbaaa xaxbaaaabaxxxxxxx()()()1221331111()()212(1)1(1)(1)21(1)(1)(1)(1)12332222121

8、,11()1()1() inkkkiiijjijjjj iiixba xa xina1(1)(1)( )111(),1,2, 10迭代法迭代法超松弛法超松弛法实际上是高斯实际上是高斯-赛德尔迭代公式的一种加速方法。赛德尔迭代公式的一种加速方法。inkkkiiijjijjjj iiixba xa xa1(1)(1)( )111() 迭代：in1,2, kkkiiixxx(1)(1)( )=(1) 加速：松弛因子松弛因子11向量和矩阵的范数向量和矩阵的范数向量的范数：向量向量的范数：向量“大小大小”的某种衡量的某种衡量Tnxxxxx12(,) , 任给向量其范数记为基本性质：基本性质：p对于任意向

9、量对于任意向量x，| x |0，当且仅当，当且仅当x=0时，时， | x |=0p对于任意实数对于任意实数及任意向量及任意向量x，有，有 | x |=| | | x |p对于任意向量对于任意向量x和和y，有，有 | x+ y | x |+| y |12向量和矩阵的范数向量和矩阵的范数3种常用范数：种常用范数：p2-范数（长度）范数（长度）p1-范数范数p-范数范数niixx2 1/221() niixx11 ii nxx1max 13向量和矩阵的范数向量和矩阵的范数矩阵的范数：矩阵的范数：AxAxAn/对于给定的 阶方阵 ，将比值的矩阵上确界称为的范数直接由定义知，对于任意向量直接由定义知，对

10、于任意向量x，有：，有：| A x | A | | x |基本性质：基本性质：p对于任意方阵对于任意方阵A，| A |0，当且仅当，当且仅当A=0时，时， | A |=0p对于任意实数对于任意实数及任意方阵及任意方阵A ，有，有 | A |=| | | A |p对于任意方阵对于任意方阵A和和B，有，有 | A+ B | A|+| B | AB | A| | B |14消元法消元法1.三角方程组的解三角方程组的解niabxaaadiagAiiiinn, 1,),(221111 112222nnnna xba xba xb对角形方程组：对角形方程组：下面有3种方程的解我们可以直接求出：15nilx

11、lbxllllllAiiijjijiinnnn, 1,1121222111下三角形方程组：下三角形方程组：11 1121 122221 122nnnnnnl xbl xl xbl xl xl xb消元法消元法161 ,122211211niuxubxuuuuuuAiinijjijiinnnn1111221122222nnnnnnnnuxuxuxbuxuxbuxb上三角形方程组：上三角形方程组：消元法消元法17例：解方程组例：解方程组12121328xxxx方程方程（3 3）加到方程中得：）加到方程中得：21x 1221055xxx代入得代入得12x 相当于对方程组得增广矩阵做行的初等变换：相当

12、于对方程组得增广矩阵做行的初等变换：111111328055AAbAb消元法消元法18对方程组，作如下的变换，解不变对方程组，作如下的变换，解不变交换两个方程的次序交换两个方程的次序一个方程的两边同时乘以一个非一个方程的两边同时乘以一个非0 0的数的数一个方程的两边同时乘以一个非一个方程的两边同时乘以一个非0 0数，加到另一个方程数，加到另一个方程因此，对应的对增广矩阵因此，对应的对增广矩阵(A，b)，作如下的变换，解不变，作如下的变换，解不变交换矩阵的两行交换矩阵的两行某一行乘以一个非某一行乘以一个非0 0的数的数某一个乘以一个非某一个乘以一个非0 0的数，加到另一行的数，加到另一行消元法消

13、元法 ：就是对增广矩阵作上述行的初等变换，变：就是对增广矩阵作上述行的初等变换，变为我们已知的为我们已知的3种类型之一，而后求根种类型之一，而后求根消元法的基本思想消元法的基本思想思路：首先将思路：首先将A化为上三角阵化为上三角阵 ，再回代求解。，再回代求解。=nnnnnnnbaaabaaabaaa21222221111211(1)(1)(1)(1)(1)11121311(2)(2)(2)(2)222322(3)(3)(3)3333( )( )000000nnnnnnnnaaaabaaabaabab高斯消去法高斯消去法Step 1：设：设 ，计算因子，计算因子0)1(11 a(1)(1)111

14、1/(2,., )iimaain 将增广矩阵将增广矩阵第第 i 行行 + mi1 第第1行行，(2)(1)(1)11(2)(1)(1)1 1( ,2,., )ijijijiiiaam ai jnbbm b其中其中nnnnnnnbaaabaaabaaa21222221111211)2()2()2(2)2(2)2(2)2(2211121100nnnnnnbaabaabaaa实施步骤如下：实施步骤如下：运算量运算量 ：(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(2211

15nnnnnnbaabaabaaabaaaa运算量运算量 ：(n-2)(1+n-1)=(n-2)n)2()2()2(2)2(2)2(2)2(2211121100nnnnnnbaabaabaaaStep 2：设：设 ，计算因子，计算因子(2)220a(2)(2)2222/(3,., )iimaain 将增广矩阵将增广矩阵第第 i 行行 mi2 第第2行行，(3)(2)(2)22(3)(2)(2)22( ,3, .,)ijijijiiiaam ai jnbbm b其中其中（n-2）次运算（n-2）（n-2）次运算（n-2）次运算高斯消去法高斯消去法Step k：设：设 ，计算

16、因子，计算因子且计算且计算0)( kkka( )( )/(1,., )kkikikkkmaaikn (1)( )( )(1)( )( )( ,1,., )kkkijijikkjkkkiiikkaam abbm bi jkn将增广矩阵将增广矩阵第第 i 行行 mik 第第k行行。运算量：运算量：(nk)(1nk1)=(nk)(nk2)（n-k）次运算（n-k）（n-k）次运算（n-k）次运算高斯消去法高斯消去法共进行共进行(n-1)步步 )()2(2)1(121)()2(2)2(22)1(1)1(12)1(11.nnnnnnnnbbbxxxaaaaaa)()()3(3)3(3)3(33)2(2)

17、2(2)2(23)2(2211131211000000nnnnnnnnbabaabaaabaaaa消元的运算量为：消元的运算量为：32115()(2)326nknnnnk nk高斯消去法高斯消去法回代回代: :)()(/nnnnnnabx ) 1., 1()(1)()( niaxabxiiinijjiijiii回代的运算量为：回代的运算量为：总运算量为：总运算量为：Gaussian Elimination 的总乘除次数为的总乘除次数为 ，运算量为，运算量为 级。级。nnn31323 33n（n1）n/232115()(2)326nknnnnk nk消元的运算量为：消元的运算量为：高斯消去法高斯

18、消去法注意到，计算过程中注意到，计算过程中( )kkka处在被除的位置，因此整个计算过程要保证它不为处在被除的位置，因此整个计算过程要保证它不为0所以，所以，Gauss消元法的可行条件为：消元法的可行条件为：( )0kkka即，要求即，要求A的所有顺序主子式均不为的所有顺序主子式均不为0:niaaaaiiii, 1, 0det1111p 因此，有些有解的问题，不能用因此，有些有解的问题，不能用Gauss消元求解消元求解p 若若A的所有顺序主子式的所有顺序主子式 均不为均不为0，则高斯消元无需换行即可进行到底，则高斯消元无需换行即可进行到底，得到唯一解。得到唯一解。事实上，只要事实上，只要 A

19、非奇异，即非奇异，即 A 1 存在，则可通过逐次消存在，则可通过逐次消元及行交换，将方程组化为三角形方程组，求出唯一解。元及行交换，将方程组化为三角形方程组，求出唯一解。高斯消去法高斯消去法与与 Gaussian Elimination 的主要区别：的主要区别： 每步作第每步作第k行行 mik第第i行；行； 把把 akk(k) 所在列的上、下元素全消为所在列的上、下元素全消为0;( )( ),1,1,1,kikikkkkamikkna将该行上三角地部分也变为将该行上三角地部分也变为0 0 运算次数比运算次数比Gauss消元多，约为消元多，约为(n3/2)量级。量级。高斯高斯-约当消去法约当消去

20、法例：单精度解方程组例：单精度解方程组 211021219xxxx/* 精确解为精确解为 和和 */.1000.00. 1101191 x8个个.8999.99. 0212 xx8个个用高斯消去法计算：用高斯消去法计算：9212111/10maa 9992221110.0.01 101010am 8个个92212110bm 9991010011100, 112 xx小可能导致计算失小可能导致计算失败。败。另外，如果某个另外，如果某个( )kkka很小的话，会引入大的误差很小的话，会引入大的误差列主元消去法列主元消去法每次仅选一列中最大的元每次仅选一列中最大的元在在Gauss消元第消元第k步之前

21、，做如下的事情：步之前，做如下的事情：|max)()(kjkkiknikaa若若交换交换k行和行和j行行行的交换，不改变方程组的解，同时又有效地克服了行的交换，不改变方程组的解，同时又有效地克服了Gauss消元地缺陷消元地缺陷例：例：1,112 xx 21111109 110211 11102119 列主元消去法列主元消去法29方程组的病态问题方程组的病态问题矩阵的条件数与线性方程组的性态矩阵的条件数与线性方程组的性态 给定线性方程组给定线性方程组 Ax =b，现在考察，系数矩阵，现在考察，系数矩阵 A 和常数列和常数列 b 有了微小变化有了微小变化 A，b ，它如何影，它如何影响解向量响解向

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