线性代数方程组的直接解法课件.ppt

1、线性代数方程组的直接解法线性方程组的数值解法一般有两类：线性方程组的数值解法一般有两类：1.1.直接法：就是经过有限步算术运算，可求得方程直接法：就是经过有限步算术运算，可求得方程组精确解的方法（若计算过程中没有舍入误差）组精确解的方法（若计算过程中没有舍入误差），如克莱姆法则就是一种直接法，直接法中具有，如克莱姆法则就是一种直接法，直接法中具有代表性的算法是高斯代表性的算法是高斯(Gauss)(Gauss)消去法。消去法。2.2.迭代法迭代法:(第四章介绍）就是用某种极限过程去逐第四章介绍）就是用某种极限过程去逐步逼近线性方程组的精确解的方法。也就是步逼近线性方程组的精确解的方法。也就是从解

2、从解的某个近似值出发，通过构造一个无穷序列去逼的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法。近精确解的方法。(一般有限步内得不到精确解一般有限步内得不到精确解)3.2 解线性方程组的直接法（高斯消去法）解线性方程组的直接法（高斯消去法）3.2.1 高斯消去法的基本思想高斯消去法的基本思想例例3.1 3.1 解线性方程组解线性方程组 72452413221321321xxxxxxxx解解:该方程组的求解过程实际上是将中学学过的消该方程组的求解过程实际上是将中学学过的消元法标准化元法标准化,将一个方程乘或除以某个常数将一个方程乘或除以某个常数,然后将然后将两个方程相加减两个方程相加减,

3、逐步减少方程中的未知数逐步减少方程中的未知数,最终使最终使每个方程只含有一个未知数每个方程只含有一个未知数,从而得出所求的解。从而得出所求的解。整个过程分为消元和回代两个部分。整个过程分为消元和回代两个部分。（1 1）消元过程）消元过程第第1 1步步:将方程乘上将方程乘上(-2)(-2)加到方程加到方程 上去上去,将将方程方程 乘上乘上 加到方程加到方程 上去上去,这样就消这样就消去了第去了第2 2、3 3个方程的个方程的 项项,于是就得到等价方于是就得到等价方程组程组 211x213232524132232321xxxxxx第第2步：将方程步：将方程 乘上乘上 加到方程加到方程 上去，上去，

4、这样就消去了第这样就消去了第3个方程的个方程的 项，于是就得项，于是就得到等价方程组到等价方程组 852x4218724132332321xxxxxx这样，消元过程就是把原方程组化为上三角这样，消元过程就是把原方程组化为上三角形方程组，其系数矩阵是上三角矩阵。形方程组，其系数矩阵是上三角矩阵。（2）回代过程）回代过程回代过程是将上述三角形方程组自下而上求回代过程是将上述三角形方程组自下而上求解，从而求得原方程组的解：解，从而求得原方程组的解：6,1,9321xxx前述的消元过程相当于对原方程组前述的消元过程相当于对原方程组 741021524312321xxx的增广矩阵进行下列变换的增广矩阵进

5、行下列变换(表示增广矩阵的第表示增广矩阵的第 行）行）702145241312bAA21323250214013121213)2()21(rrrr42187002140131223)85(rr同样可得到与原方程同样可得到与原方程组等价的方程组组等价的方程组 iri 由此看出由此看出,高斯消去法解方程组基本思想是设高斯消去法解方程组基本思想是设法消去方程组的系数矩阵法消去方程组的系数矩阵A A的主对角线下的元素的主对角线下的元素,而而将将Ax=bAx=b化为等价的上三角形方程组化为等价的上三角形方程组,然后再通过回代然后再通过回代过程便可获得方程组的解。换一种说法就是用矩阵过程便可获得方程组的解

6、。换一种说法就是用矩阵行的初等变换将原方程组系数矩阵化为上三角形矩行的初等变换将原方程组系数矩阵化为上三角形矩阵阵,而以上三角形矩阵为系数的方程组的求解比较简而以上三角形矩阵为系数的方程组的求解比较简单单,可以从最后一个方程开始可以从最后一个方程开始,依次向前代入求出未依次向前代入求出未知变量知变量 这种求解上三角方程组的方这种求解上三角方程组的方法称为法称为回代回代,通过一个方程乘或除以某个常数通过一个方程乘或除以某个常数,以及以及将两个方程相加减将两个方程相加减,逐步减少方程中的变元数逐步减少方程中的变元数,最终最终将方程组化成上三角方程组将方程组化成上三角方程组,一般将这一过程称为一般将

7、这一过程称为消消元元,然后再回代求解。然后再回代求解。11,xxxnn通常把按照先消元通常把按照先消元,后回代两个步骤求解线性后回代两个步骤求解线性方程组的方法称为方程组的方法称为高斯高斯（Gauss）消去法。消去法。3.2.2 高斯消去法算法构造高斯消去法算法构造 线性方程组线性方程组(3.1)用矩阵形式表示为用矩阵形式表示为 nnnnnnnnbbbxxxaaaaaaaaa2121212222111211(3.3)解线性方程组（）的高斯（解线性方程组（）的高斯（Gauss）消去法的消元过）消去法的消元过程就是对程就是对(3.3)的增广矩阵进行行初等变换。将例中的增广矩阵进行行初等变换。将例中

8、解三阶线性方程组的消去法推广到一般的解三阶线性方程组的消去法推广到一般的 阶线阶线性方程组并记性方程组并记则高斯消去法的算法构造归纳为：则高斯消去法的算法构造归纳为：nn),2,1,(,)1()1(njibbaaiiijij 消元过程消元过程,高斯消去法的消元过程由高斯消去法的消元过程由n-1n-1步组成：步组成：第第1 1步步 设设 ,把把(3.3)(3.3)中的第一列中元素中的第一列中元素 消为零消为零,令令 0)1(11a)1(1)1(31)1(21,naaa),3,2(,)1(11)1(11niaamii用用 乘以第乘以第1 1个方程后加到第个方程后加到第 个方程上去个方程上去,消去消

9、去第第2 2n n个方程的未知数个方程的未知数 ,得到得到 即即 1 imi1x)2()2(bxA)2()2(2)1(121)2()2(2)2(2)2(22)1(1)1(12)1(11nnnnnnnbbbxxxaaaaaaanjibmbbamaaiiijiijij,3,2,)1(11)1()2()1(11)1()2(其中其中 第第k步步 （k=2,3,n-1）继续上述消元过程，设）继续上述消元过程，设第第k-1次消元已经完成，得到与原方程组等价的次消元已经完成，得到与原方程组等价的方程组方程组 knkknkknnknkkknkkknnbbbbxxxxaaaaaaaaa)()2(2)1(121)

10、()()()()2(2)2(22)1(1)1(12)1(11nkjibmbbamaakkikkikikkjikkijkij,1,)()()1()()()1(),1()()(nkiaamkkkkikik记为记为 其中其中)()(kkbxA只要只要 ,消元过程就可以进行下去消元过程就可以进行下去,直到直到经过经过n-1n-1次消元之后，消元过程结束，得到与次消元之后，消元过程结束，得到与原方程组等价的上三角形方程组原方程组等价的上三角形方程组,记为记为 0)(kkka)()(nnbxA或者写成或者写成)()2(2)1(121)()2(2)2(22)1(1)1(12)1(11nnnnnnnnbbbx

11、xxaaaaaa)()()2(2)2(22)2(22)1(1)1(12)1(121)1(11nnnnnnnnnnbxabxaxabxaxaxa即即(3.7)（2）回代过程）回代过程就是对上三角方程组（）自下而上逐步回代解方程就是对上三角方程组（）自下而上逐步回代解方程组计算，即组计算，即)1,2,1(,)(1)()()()(niaxabxabxiiijnijiijiiinnnnnn（3 3）高斯消去法的计算步骤：）高斯消去法的计算步骤：消元过程消元过程;设设 计算计算 1,2,1,0)(nkakkk对nkkjibmbbamaaaamkkikkikikkjikkijkijkkkkikik,2,1

12、,)()()1()()()1()()(回代过程回代过程 1,2,1)(1)()()()(nniaxabxabxiiijnijiijiiinnnnnn(4)(4)高斯消去法流程图高斯消去法流程图，见，见P P4242(5)(5)GaussGauss消去法计算量消去法计算量 331n 消元计算消元计算:aij(k+1)=aij(k)-mik akj(k)(i,j=k+1,k+2,n)第一第一 步计算乘数步计算乘数mik,mik=ai1/a11(i=2,3,n)需要需要n-1次除法运算次除法运算,计算计算 aij(2）(i,j=2,3,n)需要需要(n-1)2次乘法运算及次乘法运算及(n-1)2次加

13、减法运次加减法运 算算,第第k 步步加减法次加减法次数数乘法次数乘法次数除法次数除法次数123n-1(n-1)2(n-2)2(n-3)21(n-1)2(n-2)2(n-3)21(n-1)(n-2)(n-3)1合计合计n(n-1)(2n-1)/6n(n-1)(2n-1)/6n(n-1)/2乘除法次数：乘除法次数：MD=n(n-1)(2n-1)/6+n(n-1)/2=1/3 n(n2-1)加减法次数：加减法次数：AS=n(n-1)(2n-1)/63.2.3 3.2.3 高斯消去法的适用条件高斯消去法的适用条件 定理定理3.1 3.1 方程组系数矩阵的顺序主子式全不方程组系数矩阵的顺序主子式全不 为

14、零则高斯消去法能实现方程组的为零则高斯消去法能实现方程组的 求解。求解。证明证明 上三角形方程组是从原方程组出发，通上三角形方程组是从原方程组出发，通过逐次进行过逐次进行“一行乘一数加到另一行一行乘一数加到另一行”而得出而得出的，该变换不改变系数矩阵顺序主子式的值。的，该变换不改变系数矩阵顺序主子式的值。设方程组系数矩阵设方程组系数矩阵 ，其顺序主子式，其顺序主子式 nijaA)(01111mmmmmaaaaA（m=1,2,m=1,2,，n n）经变换得到的上三角形方程组的顺序主子式经变换得到的上三角形方程组的顺序主子式 0)()2(22)1(11)()2(2)2(22)1(1)1(12)1(

15、11mmmmmmmmmaaaaaaaaaA所以能实现高斯消去法求解所以能实现高斯消去法求解 （m=1,2,m=1,2,，n n）定义定义3.1 3.1 设矩阵设矩阵 每一行对角元素每一行对角元素的绝对值都大于同行其他元素绝对值之和的绝对值都大于同行其他元素绝对值之和 nijaA)(niaanijjijii,2,1,1则称则称A A为严格对角占优矩阵。为严格对角占优矩阵。定理定理3.2 3.2 若方程组若方程组 的系数矩阵的系数矩阵A A为严为严格对角占优，则用高斯消去法求解时，格对角占优，则用高斯消去法求解时，全全不为零。不为零。bAx)(kkka证证:先考察消元过程的第先考察消元过程的第1

16、1步步,因因A为严格对角占为严格对角占 优优,故故 故故 ,又根据高斯消又根据高斯消 去公式得去公式得 于是于是 njjaa2111011)1(11 aanjiaaaaajiijij,3,2,1111)2(nijjjinijjijnijjijaaaaa2111122)2()(12111111injjiinijjijaaaaaa再利用方程组的对角占优性再利用方程组的对角占优性,由上式可进一步得由上式可进一步得 111111111112)2()(aaaaaaaaaaaiiiiiiiiinijjij又由又由 njiaaaaajiijij,3,2,1111)2(得得 11111111)2(aaaaaa

17、aaaiiiiiiiiii故有故有 niaaiinijjij,3,2,)2(2)2(当当A A为严格对角占优时为严格对角占优时,余下的子阵仍是余下的子阵仍是对角占优的，从而又有对角占优的，从而又有 。依次类推全不。依次类推全不为零。为零。定理证毕。定理证毕。011)1(11aa0)2(22a 一般线性方程组使用高斯消去法求解时，一般线性方程组使用高斯消去法求解时，在消元过程中可能会出现在消元过程中可能会出现 的情况，这的情况，这时消去法将无法进行；即使时消去法将无法进行；即使 ，但它的，但它的绝对值很小时，用其作除数，会导致其他元素绝对值很小时，用其作除数，会导致其他元素数量级的严重增长和舍入

18、误差的扩散，将严重数量级的严重增长和舍入误差的扩散，将严重影响计算结果的精度。影响计算结果的精度。实际计算时必须避免这实际计算时必须避免这类情况的发生。主元素消去法就可弥补这一缺类情况的发生。主元素消去法就可弥补这一缺陷。陷。0)(kkka0)(kkka 交换原则：通过方程或变量次序的交换交换原则：通过方程或变量次序的交换，使在对角线位置上获得绝对值尽可能，使在对角线位置上获得绝对值尽可能大的系数作为大的系数作为akk(k)，称这样的，称这样的akk(k)为为主主元素元素，并称使用主元素的消元法，并称使用主元素的消元法为主元为主元素法素法 根据主元素选取范围分为：列主元素法根据主元素选取范围分

19、为：列主元素法、行主元素法、全主元素法、行主元素法、全主元素法记笔记记笔记3.2.4 3.2.4 高斯主元素消去法高斯主元素消去法主元素法的意义主元素法的意义例例3.2 用高斯消去法求下列方程组的解用高斯消去法求下列方程组的解 211021215xxxx解：解：确定乘数确定乘数 ，再计算系数，再计算系数 52110m5)2(25122122)2(22102101bamaa假设计算在假设计算在4 4位浮点十进值的计算机上求解位浮点十进值的计算机上求解,则有则有 5555555510101000002.010210101000001.0101，这时方程组的实际形式是这时方程组的实际形式是 5252

20、151010110 xxx由此回代解出由此回代解出 ,但这个解不满足原但这个解不满足原方程组方程组,解是错误的。这是因为所用的除数太小解是错误的。这是因为所用的除数太小使得上式在消元过程中使得上式在消元过程中“吃掉吃掉”了下式，解决了下式，解决这个问题的方法之一就是采用列选主元高斯消这个问题的方法之一就是采用列选主元高斯消元法。即按列选绝对值大的系数作为主元素，元法。即按列选绝对值大的系数作为主元素，则将方程组中的两个方程相交换，原方程组变则将方程组中的两个方程相交换，原方程组变为为 1,021xx110221521xxxx得到消元后的方程组得到消元后的方程组 525211021)101(2x

21、xx这时这时 5555555510101000002.010210101000001.0101，因而方程组的实际形式是因而方程组的实际形式是 12221xxx由此回代解出由此回代解出 ,这个结果是正确的这个结果是正确的 1,121xx 可见用高斯消去法解方程组时可见用高斯消去法解方程组时,小主元可小主元可能导致计算失败能导致计算失败,因为用绝对值很小的数作除因为用绝对值很小的数作除数数,乘数很大乘数很大,引起约化中间结果数量级严重增引起约化中间结果数量级严重增长长,再舍入就使得计算结果不可靠了再舍入就使得计算结果不可靠了,故避免采故避免采用绝对值很小的主元素。以便减少计算过程中用绝对值很小的主

22、元素。以便减少计算过程中舍入误差对计算解的影响。舍入误差对计算解的影响。全主元素消去法全主元素消去法 是通过方程或变量次序的交换，使在是通过方程或变量次序的交换，使在对角线位置上获得绝对值尽可能大的系数作对角线位置上获得绝对值尽可能大的系数作为为 ，称这样的，称这样的 为主元素。尽管它的为主元素。尽管它的算法更稳定，但计算量较大，实际应用中大多算法更稳定，但计算量较大，实际应用中大多数使用列主元素消去法即可满足需要。数使用列主元素消去法即可满足需要。)(kkka)(kkka不是按列选主元素，而是在全体不是按列选主元素，而是在全体待选系数中选取，则得待选系数中选取，则得全主元素法。全主元素法。例

23、例3.3 用用全主元素法解下列线组全主元素法解下列线组 10 x1-19x2-2x3=3 (1)-20 x1+40 x2+x3=4 (2)x1+4x2+5x3=5 (3)n解：选择所有系数中绝对值最大的解：选择所有系数中绝对值最大的40作为作为主主元素，交换第一、二行和交换第一、二列使元素，交换第一、二行和交换第一、二列使该主元素位于对角线的第一个位置上，得该主元素位于对角线的第一个位置上，得40 x2-20 x1+x3=4 (4)-19x2+10 x1-2x3=3 (5)4x2+x1+5x3=5 (6)记笔记记笔记计算计算m21=-19/40，m31=4/40(5)-m21(4),(6)-m

24、31(4)消去消去x2 得得 0.5x1 1.525 x3=4.9 (7)3x1+4.9 x3=4.6 (8)4.9 x3+3x1=4.6 (9)1.525 x3+0.5x1=4.9 (10)计算计算m32，(10)-m32(9)消去消去x2得得1=6.33161 (11)记笔记记笔记保留有主元素的方程保留有主元素的方程40 x2-20 x1+x3 =4 (4)4.9x3+3x1=4.6 (9)1.43366x1=6.33161 (11)进行回代进行回代x1=4.41634 x3=-1.76511x2=2.352303.2.4.1 列主元素法列主元素法 列主元素法就是在待消元的所在列中选取主列

25、主元素法就是在待消元的所在列中选取主元，经方程的行交换，置主元素于对角线位元，经方程的行交换，置主元素于对角线位置后进行消元的方法。置后进行消元的方法。例例3.4 用用列主元素法解下列线性方程组列主元素法解下列线性方程组 10 x1-19x2-2x3=3 (1)-20 x1+40 x2+x3=4 (2)x1+4x2+5x3=5 (3)n解：选择解：选择-20作为该列的作为该列的主元素主元素，-20 x1+40 x2+x3=3 (4)10 x1-19x2-2x3=4 (5)x1+4x2+5x3=5 (6)计算计算m21=10/-20 m31=1/-20(5)-m21(4),(6)-m31(4)得

26、得 x2 1.5x3=5 (7)6x2+5.05x3=5.2 (8)选选6为主元素为主元素6x2+5.05x3=5.2 (9)x2 1.5x3=5 (10)计算计算m32=1/6，(10)-m32(9)得得3=4.13332 (11)记笔记记笔记保留有主元素的方程保留有主元素的方程-20 x1+40 x2+x3 =4 (4)6x2+5.05x3 =5.2 (9)-2.34168x3=4.13332 (11)进行回代进行回代x3=-1.76511x2=2.35230 x1=4.41634记笔记记笔记 列选主元素的计算方法与高斯消去法完全一样列选主元素的计算方法与高斯消去法完全一样,不同的是在每步

27、消元之前要按列选出主元不同的是在每步消元之前要按列选出主元例例3.5 3.5 用矩阵的初等行变换求解解方程组用矩阵的初等行变换求解解方程组 754217743322321321321xxxxxxxxx 解解:用矩阵的初等行变换求解用矩阵的初等行变换求解,对增广矩阵对增广矩阵 (下面带下划线元素为主元素下面带下划线元素为主元素)2.12.1005.65.85.7017745.25.05.105.65.85.7017745.65.85.705.25.05.101774754233221774754217743322232313121251_2121_)1(rrrrrrrrrrbAA3.3 矩阵三角

28、分解法矩阵三角分解法 3.3.1 3.3.1 矩阵三角分解原理矩阵三角分解原理 应用高斯消去法解应用高斯消去法解n阶线性方程组阶线性方程组Ax=b,经过经过n步消元之后步消元之后,得出一个等价的上三角型方程组得出一个等价的上三角型方程组A(n)x=b(n),对上三角形方程组用逐步回代就可以求对上三角形方程组用逐步回代就可以求出解来。上述过程可通过矩阵分解来实现。出解来。上述过程可通过矩阵分解来实现。将非奇异阵将非奇异阵A分解成一个下三角阵分解成一个下三角阵L和一个上三和一个上三角阵角阵U的乘积的乘积 A=LU 称为对称为对矩阵矩阵A A的三角分解，又称的三角分解，又称LU分解分解)()3(3)

29、3(33)2(2)2(23)2(22)1(1)1(13)1(12)1(1121323121,1111nnnnnnnnaaaaaaaaaaUmmmmmLLUaaaaaaaaaaaaaaaaAnnnnnnnn321333323122322211131211其中其中方程组方程组Ax=b的系数矩阵的系数矩阵A经过顺序消元逐步化经过顺序消元逐步化为上三角型为上三角型A(n),相当于用一系列初等变换左乘相当于用一系列初等变换左乘A的结果。事实上，第的结果。事实上，第1列消元将列消元将A(1)=A化为化为A(2)，若令：，若令：10000100010001131211nmmmL),3,2(,)1(11)1(

30、11niaamii则根据距阵左乘有则根据距阵左乘有L1A(1)=A(2)第第2列消元将列消元将A(2)化为化为A(3)，若令：，若令：1000010001000012322nmmL),4,3(,)2(22)2(22niaamii经计算可知经计算可知 L2A(2)=A(3),依此类推依此类推,一般有一般有LkA(k)=A(k+1)11111,1nkkkkmmLmi1=a(1)i1/a(1)11 i=2,3,n于是矩阵于是矩阵 经过消元化为上三角阵经过消元化为上三角阵 的过程可表示为的过程可表示为上述矩阵上述矩阵 是一类初等矩阵是一类初等矩阵,它们都是单位下三角阵，且其逆矩阵也是单位它们都是单位下

31、三角阵，且其逆矩阵也是单位下三角阵下三角阵,只需将只需将 改为改为 ,就得到就得到 。即。即 )1(AA)(nA)(1221nnnAALLLL)1,2,1(nkLkikm),2,1(nkkimik1kL11111,11nkkkkmmL于是有于是有 LUULLLALLLAnnn)()(111211)(111211)()3(3)3(33)2(2)2(23)2(22)1(1)1(13)1(12)1(1121323121,1111nnnnnnnnaaaaaaaaaaUmmmmmL其中其中 L L为由乘数构成的单位下三角阵，为由乘数构成的单位下三角阵，U U为上三角阵，为上三角阵，由此可见，在由此可见，

32、在 的条件下，的条件下，高斯消去法实质上是将方程组的系数矩阵高斯消去法实质上是将方程组的系数矩阵A A分解分解为两个三角矩阵的乘积为两个三角矩阵的乘积A=LUA=LU。这种把非奇异矩阵。这种把非奇异矩阵A A分解成一个下三角矩阵分解成一个下三角矩阵L L和一个上三角矩阵和一个上三角矩阵U U的的乘积称为矩阵的三角分解，又称乘积称为矩阵的三角分解，又称LULU分解。分解。显然，如果显然，如果 ,由行列式由行列式的性质知，方程组系数矩阵的性质知，方程组系数矩阵A A的前的前n-1n-1个顺序主子个顺序主子矩阵矩阵 非奇异，非奇异，即顺序主子即顺序主子式不等于零，即式不等于零，即()0(1,2,1)

33、kkkakn)1,2,1(0)(nkakkk)1,2,1(nkAk0)det()1(111 aA),3,2(0)det()()2(22)1(11kiaaaAiiii其中其中 iiiiiaaaaAaA1111111),(（A A的主子阵）的主子阵）反之反之,可用归纳法证明可用归纳法证明,如果如果A A的顺序主子式的顺序主子式 ),2,1(0)det()()2(22)1(11kiaaaAiiii则则 ),2,1(0)(kiaiii于是得到下述定理：于是得到下述定理：定理定理3.5 3.5 设设 。如果。如果A顺序各阶主子式顺序各阶主子式,则则A可惟一地分解成可惟一地分解成 一个单位下三角阵一个单位

34、下三角阵L和一个非奇异的上三角和一个非奇异的上三角阵阵U的乘积。的乘积。证：由于证：由于A A各阶主子式不为零各阶主子式不为零,则消元过程能则消元过程能进行到底进行到底,前面已证明将方程组的系数矩阵前面已证明将方程组的系数矩阵A A用初等变换的方法分解成两个三角矩阵的乘用初等变换的方法分解成两个三角矩阵的乘积积A=LUA=LU的过程。的过程。现仅证明分解的惟一性。现仅证明分解的惟一性。设设A A有两种有两种LULU分解分解 nnRA)1,2,1(0)det(niAiULLUA其中其中 为单位下三角阵，为单位下三角阵，为上三角阵为上三角阵 A A的行列式的行列式 均为非奇异矩阵均为非奇异矩阵,有

35、有上式两边左边同乘上式两边左边同乘 ，右边同乘，右边同乘 得得上式左边为单位下三角阵上式左边为单位下三角阵,右边为上三角阵右边为上三角阵,故应为故应为单位阵单位阵,即即 惟一性得证。惟一性得证。LL,UU,ULULA,0ULLU 1L1U11UULLUULL,所以 ,从而所以 ,从而显然,当 时,解Ax=b直接三角分解法计算才能完成。线性方程组的数值解法一般有两类：向量范数是用来度量向量长度的,它可以看成是二、三维解析几何中向量长度概念的推广。解:用矩阵的初等行变换求解,对增广矩阵证:先考察消元过程的第1步,因A为严格对角占证:先考察消元过程的第1步,因A为严格对角占直接法：就是经过有限步算术

36、运算，可求得方程组精确解的方法（若计算过程中没有舍入误差），如克莱姆法则就是一种直接法，直接法中具有代表性的算法是高斯(Gauss)消去法。A(n)x=b(n),对上三角形方程组用逐步回代就可以求出解来。1 高斯消去法的基本思想9x3+3x1=4.当方程组的系数矩阵A非奇异和常数项b为非零向量时，且同时有扰动A，b，满足 ，若x和x+x分别是方程组以便减少计算过程中舍入误差对计算解的影响。9x3+3x1=4.把把A分解成一个单位上三角阵分解成一个单位上三角阵L和一个下和一个下三角阵三角阵U的乘积称为的乘积称为杜利特尔（杜利特尔（Doolittle）分解分解。其中其中 nnnnnnuuuuuuU

37、lllL222112112121,111若把若把A分解成一个下三角阵分解成一个下三角阵L和一个单位上和一个单位上三角阵三角阵U的乘积称为的乘积称为克克洛特分解洛特分解Crout）其中其中 111,211221222111nnnnnnuuuUllllllL3.3.2 用三角分解法解方程组用三角分解法解方程组 求求解线性方程组解线性方程组Ax=b时时,先对非奇异矩阵先对非奇异矩阵A进行进行LU分解使分解使A=LU，那么方程组就化为，那么方程组就化为 LU x=b从而使问题转化为求解两个简单的的三角方从而使问题转化为求解两个简单的的三角方程组程组 L y=b 求解求解 y U x=y 求解求解 x这

38、就是求解线性方程组的三角分解法的基本这就是求解线性方程组的三角分解法的基本思想。下面只介绍杜利特尔（思想。下面只介绍杜利特尔（Doolittle）分）分解法。解法。设设A=LU为为nnnnnnnnnnnuuuuuulllaaaaaaaaa2221121121212122221111111111 由矩阵乘法规则由矩阵乘法规则niuaii,2,111niulaii,3,21111 由此可得由此可得U的第的第1行元素和行元素和L的第的第1列元素列元素niauii,2,111niualii,3,21111 再确定再确定U的第的第k行元素与行元素与L的第的第k列元素列元素,对对于于k=2,3,n计算：计

39、算：计算计算U的第的第k行元素行元素 11krrjkrkjkjulau（j=k,k+1,j=k,k+1,n,n）计算计算L L的第的第k k列元素列元素 kkkrrkirikikuulal11（i=k,k+1,i=k,k+1,n,n）nnnnnnnnnnnuuuuuulllaaaaaaaaa2221121121212122221111111111利用上述计算公式便可逐步求出利用上述计算公式便可逐步求出U与与L的各元素的各元素求解求解 Ly=b,Ly=b,即计算即计算:1111),3,2(ikkikiiniylbyby 求解求解 Ux=y,Ux=y,即计算：即计算：)1,2,1(1niuxuyx

40、uyxiinikkikiinnnn 显然显然,当当 时时,解解Ax=b直接三角分解法计算才能完成。设直接三角分解法计算才能完成。设A为非奇异矩阵为非奇异矩阵,当当 时计算将中断或者时计算将中断或者当当 绝对值很小时，按分解公式计算可绝对值很小时，按分解公式计算可能引起舍入误差的积累，因此可采用与列能引起舍入误差的积累，因此可采用与列主元消去法类似的方法，对矩阵进行行交主元消去法类似的方法，对矩阵进行行交换，则再实现矩阵的三角分解。换，则再实现矩阵的三角分解。用直接三角分解法解用直接三角分解法解Ax=b大约需要大约需要 次乘除法。次乘除法。),2,1(0nkukk0kkukku3/3n例例3.8

41、 用三角分解法解方程组用三角分解法解方程组 542631531321321xxx332322131211323121111631531321uuuuuulll113213121131211lluuu121312212222ulau231513212323ulau11/)213(/)(2212313232uulal121316233213313333ululau121321111111UL求解求解 Ly=b 得得 y=2，2，1T 求解求解 Ux=y 得得 x=-1，0，1 T所以方程组的解为所以方程组的解为 101321xxx3.5 追赶法追赶法在数值计算中在数值计算中,有一种系数矩阵是三对角

42、方程组有一种系数矩阵是三对角方程组 nnnnnnnnnfffffxxxxxbacbacbacbacb1321132111133322211简记为简记为Ax=f,AAx=f,A满足条件满足条件 （1 1）（2 2）（3 3）011 cb)1,3,2,0(nicacabiiiii0nnab 用归纳法可以证明，满足上述条件的三对角用归纳法可以证明，满足上述条件的三对角线性方程组的系数矩阵线性方程组的系数矩阵A非奇异，所以可以利用矩非奇异，所以可以利用矩阵的直接三角分解法来推导解三对角线性方程组阵的直接三角分解法来推导解三对角线性方程组的计算公式，用克洛特分解法，将的计算公式，用克洛特分解法，将A分解

43、成两个三分解成两个三角阵的乘积，设角阵的乘积，设A=LU 11112122111122211nnnnnnnnuuulalalbacbacbacb按乘法展开按乘法展开 1,2,111111niluabulclbiiiiiii1,2,1/11111niuabllcubliiiiiiinnluulul12211则可计算则可计算 可依次计算可依次计算 当，当，由上式可惟由上式可惟一确定一确定L和和U。0il例例3.9 用追赶法求解三对角方程组用追赶法求解三对角方程组 501352242231124321xxxx解解 21211111lcubl54252221222lcuuabl565123332333

44、lcuuabl253444uabl16515412112525122251252242231121,5.12321222111lyafylfy1,654344432333lyafylyafy0,1433344xuyxyx2,121113222xuyxxuyx由由Ly=f 解出解出y又由又由Ux=y解出解出x 记笔记记笔记向量范数是用来度量向量长度的向量范数是用来度量向量长度的,它可以看成它可以看成是二、三维解析几何中向量长度概念的推是二、三维解析几何中向量长度概念的推广。广。用用Rn表示表示n维实向量空间。维实向量空间。记笔记记笔记定义定义3.2 对任一向量对任一向量X Rn,按照一定规则确定

45、一个实按照一定规则确定一个实数与它对应数与它对应,该实数记为该实数记为|X|,若若|X|满足下面三个满足下面三个性质性质:(1)|X|0；|X|=0当且仅当当且仅当X=0；(2)对任意实数对任意实数，|X|=|X|；(3)对任意向量对任意向量Y Rn，|X+Y|X|+|Y|则称该实数则称该实数|X|为向量为向量X的的范数范数记笔记记笔记|max|,.,|,max|)(.|.|X|12121122222121211ininniinniinxxxxXxxxxXxxxx 当不需要指明使用哪一种向量范数时，就用记号当不需要指明使用哪一种向量范数时，就用记号|.|泛指任何一种向量范数。泛指任何一种向量范

46、数。有了向量的范数就可以用它来衡量向量的大小和表示有了向量的范数就可以用它来衡量向量的大小和表示向量的误差。向量的误差。设设x*为为Ax=b的精确解，的精确解，x为其近似解，则其绝对误差为其近似解，则其绝对误差可表示成可表示成|x-x*|，其相对误差可表示成，其相对误差可表示成的特例范数上述范数都是pnipipxXp11)|(|记笔记记笔记*xxx xxx*或或yxyxyyxyyxxyxyxxxxxxx)()3()2(101:证时，当）（具有以下性质向量范数例例3.11 设设x=(1,0,-1,2)T,计算计算 21,xxx解解:=1+0+|-1|+2=41x62)1(0122222x2)2,

47、1,0,1max(x定理定理3.7 3.7 对于任意向量对于任意向量x,有有证证:xxppliminixx1maxppinipnipippinixnxxx111111maxmax即即 xnxxpp1当当 p，11pn xxpplim定义定义3.4 (向量序列的极限向量序列的极限)设设 为为 中的中的一向量序列，一向量序列，,记记 。如果。如果 (i=1,2,n)，则称则称 收敛于向量收敛于向量 ，记为，记为)(kxnRnRx*Tknkkkxxxx)()(2)(1)(,Tnxxxx*2*1*,*)(limikikxx)(kx*x*)(limxxkk 定理定理3.8（向量范数的等价性）设（向量范数

48、的等价性）设 为为 上任意两种向量范数上任意两种向量范数,则存在常数则存在常数C1,C20,使得对任意使得对任意 恒有恒有qpxx,nRnRxpqpxCxxC21（证（证:略）略）定理定理 其中其中 为向量中的任一种范数。为向量中的任一种范数。*)(limxxkk 0lim*)(xxkk证证 由于由于*)(limxxkk 0lim*)(xxkk知存在常数知存在常数C1，C2，使，使 nR*)(2*)(*)(1xxCxxxxCkkk于是可得于是可得 0lim0lim*)(*)(xxxxkkkk从而定理得证。从而定理得证。定义（矩阵的范数）如果矩阵定义（矩阵的范数）如果矩阵 的某的某个个非负的实值

49、函数非负的实值函数 ，满足，满足 BAABRBABABAAAAAAnn4320001，对任意矩阵三角不等式（齐次性）对任意实数（正定性）时，且仅当nnRAAAN)(则称则称 是是 上的一个矩阵范数上的一个矩阵范数(或模或模)(ANnnR 0)(2()(max(max)10.3maxmax211111AAEfAAAAAAAAAaAAaAaAnTTTTniijnjnjijninij即的最大特征值表示其中范数）的称为的列范数）称为的行范数）称为（阶方阵对定理矩阵范数计算公式定义定义3.7（矩阵的谱半径）设（矩阵的谱半径）设 的特征的特征 值为值为 ,称称 为为A的的谱半径。谱半径。例例 3.12 3

50、.12 计算方阵计算方阵 nnRA),2,1(niiiniA1max)(420420001A的三种常用范数的三种常用范数 ),2,1(pAp例例3.12 3.12 计算方阵计算方阵 420420001A的三种范数的三种范数 解解 88,4,1maxmax31311iijjaA66,6,1maxmax3131jijiaA)(max2AAA先计算先计算 3200080001420420001440220001AA所以所以 ,从而从而 32)(maxAA24322A定理定理3.11 设设A为为n阶方阵阶方阵,则对任意矩阵范数则对任意矩阵范数都有都有证证:设设 为为A的特征值，的特征值，x是是 对应于