《线性代数》课件D2-1线性方程组的直接解法（1）.ppt

1、第二章第二章 线性方程组的数值解法线性方程组的数值解法2 线性方程组的迭代解法线性方程组的迭代解法3 迭代法的迭代法的收敛性收敛性1 线性方程组的直接解法线性方程组的直接解法2023-4-24第二章 第一节 线性方程组的直接解法2 线性方程组的数值解法一般有两类：线性方程组的数值解法一般有两类：1.直接法直接法 经过有限步算术运算，可求得方程组精经过有限步算术运算，可求得方程组精确解的方法确解的方法(若计算过程中没有舍入误差若计算过程中没有舍入误差).但但实际计算中由于舍入误差的存在和影响，这实际计算中由于舍入误差的存在和影响，这种方法也只能求得线性方程组的近似解种方法也只能求得线性方程组的近

2、似解.2.迭代法迭代法 是用某种极限过程去逐步逼近线性方程组是用某种极限过程去逐步逼近线性方程组精确解的方法精确解的方法.只能求得线性方程组的近似解只能求得线性方程组的近似解.2023-4-24第二章 第一节 线性方程组的直接解法3第二章第二章1 线性方程组的直接解法线性方程组的直接解法三、选主元消去法的应用三、选主元消去法的应用四、矩阵的三角分解四、矩阵的三角分解五、平方根法及改进的平方根法五、平方根法及改进的平方根法六、六、追赶法追赶法二、二、Gauss全主元消去法全主元消去法一、一、Gauss列主元消去法列主元消去法七、七、列主元三角分解法列主元三角分解法2023-4-24第二章 第一节

3、 线性方程组的直接解法4一、一、Gauss列主元消去法列主元消去法123123123332 4,(1)2 3,(2)32511.(3)xxxxxxxxx 例例1 1 求求解解下下列列 元元线线性性方方程程组组1237(2)-2(1)(3)-(2)(3)-3(1)52323324,(1)555,(2)7 1.(3)xxxxxxx 2023-4-24第二章 第一节 线性方程组的直接解法51232,:0,1.xxx 回回代代,得得方方程程组组的的解解为为1237(3)-(2)5233324,(1)555,(2)66.(3)xxxxxx 以以上上的的求求解解方方法法称称为为高高斯斯消消去去法法.202

4、3-4-24第二章 第一节 线性方程组的直接解法6,AXb 把把方方程程组组写写成成矩矩阵阵形形式式:则则(,)AA b 广广矩矩阵阵进进行行的的,以以上上的的求求解解过过程程实实际际上上是是对对方方程程组组的的增增(2)-2(1)(3)-3(1)1324211332511A =2023-4-24第二章 第一节 线性方程组的直接解法77(3)-(2)5132405550711 132405550066 阶阶梯梯型型矩矩阵阵阶阶梯梯形形方方程程组组123233324,555,66.xxxxxx 2023-4-24第二章 第一节 线性方程组的直接解法81(2)51(3)6132405550066

5、(2)(3)(1)2(3)132401110011 回回代代过过程程也也可可改改为为继继续续消消元元：2023-4-24第二章 第一节 线性方程组的直接解法9(1)3(2)130201000011 100201000011 1232,0,1.xxx 这这种种方方法法称称为为高高斯斯若若当当消消去去法法.2023-4-24第二章 第一节 线性方程组的直接解法10求解求解bxA 高斯消元法：高斯消元法：思思路路首先将首先将A化为上三角阵化为上三角阵 ，再回代求解，再回代求解 。=Gauss消去法分析消去法分析2023-4-24第二章 第一节 线性方程组的直接解法11消元消元记记(1)(1)(1)1

6、1121(1)(1)(1)(1)21222(1)(1)(1)12,nnnnnnn naaaaaaAAaaa )1()1(1)1(.nbbbb第第1步：步：设设 ，计算因子，计算因子(1)110a).,2(/)1(11)1(11niaalii将增广矩阵将增广矩阵第第 i 行行 li1 第第1 1行行，得到，得到(2)(1)(1)(2)(1)(1)1111,2,3,.ijijijiiiaal abbl bi jn其中其中(1)(1)(1)11121(2)(2)(2)222(2)(2)20,0nnnnnn naaaaaAaa(1)1(2)(2)2(2)nbbbb2023-4-24第二章 第一节 线性

7、方程组的直接解法12 11111111211122222222()()1,1,1,knkknkkkkkkkknkkkkkkknkkkkn knnnn naaaabaaabAbaabaabaab第第k步：步：设设 ,计算因子计算因子()0kkka()()/(1,.,)kkikikkklaaikn将增广矩阵将增广矩阵第第 i 行行 lik 第第k k行行，得到，得到(1)()()(1)()(),1,.kkkkkkijijikkjiiikkaal abbl bi jkn如果k-1步消元已经完成2023-4-24第二章 第一节 线性方程组的直接解法13 111111112111222222222(),

8、.knknnnkkkkkknknnnnnn naaaabaaabAbaabab如果计算过程中均有()0,1,2,1.kkkakn共进行共进行？步，有步，有n 12023-4-24第二章 第一节 线性方程组的直接解法14回代回代)()(/nnnnnnabx )1.,1()(1)()(niaxabxiiinijjiijiii相对的三角形方程组相对的三角形方程组 )()2(2)1(121)()2(2)2(22)1(1)1(12)1(11.nnnnnnnnbbbxxxaaaaaa2023-4-24第二章 第一节 线性方程组的直接解法15上述过程意味着，只有上述过程意味着，只有()0,1,2,1,kkk

9、akn 消元过程才能进行到底，也即可用消元法解线性方消元过程才能进行到底，也即可用消元法解线性方程组。程组。定理定理 若若A消元过程满足消元过程满足 则可用高斯消元法将方程组化为三角形方程组，且求出唯一则可用高斯消元法将方程组化为三角形方程组，且求出唯一解。解。()0,1,2,1,kkkakn2023-4-24第二章 第一节 线性方程组的直接解法16Step k：设设 ，计算因子，计算因子且计算且计算0)(kkka).,1(/)()(nkiaamkkkkikik ).,1,()()()1()()()1(nkjibmbbamaakkikkikikkjikkijkij 共进行共进行n 1步步 )(

10、)2(2)1(121)()2(2)2(22)1(1)1(12)1(11.nnnnnnnnbbbxxxaaaaaa 算法算法运算量运算量由于计算机中乘除由于计算机中乘除 运算的时间远远超过加减运算的时间远远超过加减 运算的时间，故运算的时间，故估计某种算法的运算量时，往往只估计估计某种算法的运算量时，往往只估计乘除的次数乘除的次数，而且通常以，而且通常以乘除次数乘除次数的的最高次幂最高次幂为运算量的为运算量的数量级数量级。Gauss 消去法消去法:)()(/nnnnnnabx)1.,1()(1)()(niaxabxiiinijjiijiii(n k)次次(n k)2 次次(n k)次次(n k)

11、(n k+2)次次nnnknknnk6523)2)(2311 消元乘除次数：消元乘除次数：1 次次(n i+1)次次22)1(1211nninni 回代乘除次数：回代乘除次数：Gauss 消去法消去法 的总乘除次数为的总乘除次数为 ，运算量为，运算量为 级。级。nnn31323 33n2023-4-24第二章 第一节 线性方程组的直接解法17123123123332 4,(1)2 3,(2)32511.3)6(xxxxxxxxx 例例 求求解解下下列列 元元线线性性方方程程组组123(2)-2(1)(3)-3(1)2323324,(1)55,(2)7 1.(3)0 xxxxxxx :高高斯斯消

12、消去去法法可可能能出出现现两两个个问问题题?(2)(3).应应当当交交换换两两个个方方程程2023-4-24第二章 第一节 线性方程组的直接解法18512(2)-10(1)120.0000122,3.xxxx 例例 求求解解下下列列2 2元元线线性性方方程程组组412662100.1000100.2000100.2000,100.2000100.2000,xxx 12(,)(0,1).xx 回回代代得得:12(,)(2.0000100000,0.999898999).xx 精精确确解解:,.问问题题除除数数太太小小 大大数数 吃吃掉掉 小小数数计算准确到小数点后计算准确到小数点后5 5位位20

13、23-4-24第二章 第一节 线性方程组的直接解法19(1)(2):应应当当交交换换两两个个方方程程512(2)-10(1)12 3,0.0000122.xxxx 122 3,1.999991.99997.xxx (2.0000100000,0.999898999).12(,)(2.00001,0.99999)xx(精精确确解解)2023-4-24第二章 第一节 线性方程组的直接解法20解决此问题的策略之一解决此问题的策略之一-列主元消去法列主元消去法每一步消元前，选绝对值最大的元素为主元素，每一步消元前，选绝对值最大的元素为主元素，|1ikl使得。,|m a x|0;kkkikikkinaa

14、 If ik k then 交换第交换第 k 行与第行与第 ik 行行;消元消元第第 k次消元次消元:选取选取2023-4-24第二章 第一节 线性方程组的直接解法21高高斯斯列列主主元元消消去去法法3 用用 种种初初等等行行变变换换把把方方程程组组的的增增广广矩矩阵阵化化为为阶阶梯梯型型矩矩阵阵,再再用用回回代代过过程程求求解解.实实际际上上在在线线性性代代数数课课程程中中已已经经学学过过.线线性性代代数数方方法法与与数数值值计计算算方方法法的的差差别别:线线性性代代数数:按按列列选选主主元元时时,通通常常选选取取绝绝对对值值最最的的元元素素作作为为小小主主元元素素;数数值值计计算算:按按列

15、列选选主主元元时时,通通常常选选取取绝绝对对值值最最的的元元素素作作为为大大主主元元素素.2023-4-24第二章 第一节 线性方程组的直接解法22123123123232 4,(1)2 3,(2)32511.(3)xxxxxxxxx 例例 用用高高斯斯列列主主元元消消去去法法解解方方程程组组1324 211332511A 解解=(1)(3)2023-4-24第二章 第一节 线性方程组的直接解法233251121131324 2(2)(1)31(3)(1)3 3251101/313/313/307/31/31/3 (2)(3)2023-4-24第二章 第一节 线性方程组的直接解法2432511

16、07/31/31/301/313/313/3 1(3)+(2)7 3251107/31/31/30044 1(3)4 2023-4-24第二章 第一节 线性方程组的直接解法253251107/31/31/30011 1(2)+(3)3 3251107/3000011 3(2)7 2023-4-24第二章 第一节 线性方程组的直接解法26300601000011 (1)+5(3)(1)2(2)3251101000011 100201000011 1(1)2 1232,0,1.xxx 2023-4-24第二章 第一节 线性方程组的直接解法27l高斯全主元消去法选取主元的范围更大，对增广矩阵A(1)

17、,b(1)来说，第1步是在整个系数矩阵中选主元，即将绝对值最大的元素经过行列交换使其置于a11(1)元素的位置，然后进行消元过程；第2步是在A(2),b(2)中划掉第1行第1列后剩余的子系数矩阵中选主元，并通过行列交换使其置于a22(2)元素的位置，然后再进行消元过程；以后各步类似进行，最后得到一个上三角矩阵，再由回代过程求得解。二、二、Gauss全主元消去法全主元消去法2023-4-24第二章 第一节 线性方程组的直接解法28l求解结果比高斯列主元消去法更可靠l花时间比高斯列主元消去法更多l算法比高斯列主元消去法更复杂l高斯列主元消去法简单，又能满足精度要求、达到较好的数值稳定性，是实际中常

18、用算法。2023-4-24第二章 第一节 线性方程组的直接解法29l求逆矩阵 在A E中用高斯列主元消去法对A进行消元，再用高斯-若当消去法将左边的矩阵A化为单位矩阵，则右边的矩阵E化为A的逆矩阵。三、选主元消去法的应用三、选主元消去法的应用l求方阵的行列式 用高斯列主元消去法将A化为上三角形矩阵B，则B的主对角线元素的乘积等于B的行列式。|A|=|B|或|A|=c|B|.2023-4-24第二章 第一节 线性方程组的直接解法30121100 1100 1 0223001A E 解解=(1)(3)3 -121 110.223A 例例用用按按列列选选主主元元的的高高斯斯 若若当当法法求求矩矩阵阵

19、=的的逆逆阵阵和和行行列列式式2023-4-24第二章 第一节 线性方程组的直接解法312230011100 1 0121100 1(2)-(1)21(3)+(1)2 223001023/20 1 1/2035/2101/2 (2)(3)2023-4-24第二章 第一节 线性方程组的直接解法32223001035/21 0 1/2023/2011/2 2(3)+(2)3 223001035/21 0 1/2001/62/311/6 6(3)|1.A 2023-4-24第二章 第一节 线性方程组的直接解法33223001035/21 0 1/2001461 5(2)-(3)2(1)-3(3)220121840309 15 3001461 1(2)3 2023-4-24第二章 第一节 线性方程组的直接解法34220121840103 5 1001461 (1)-2(2)2006820103 5 1001461 1(1)2 2023-4-24第二章 第一节 线性方程组的直接解法351003410103 5 1.001461 1341 351.461A 2023-4-24第二章 第一节 线性方程组的直接解法363412461,1.3511Ab 2023-4-24第二章 第一节 线性方程组的直接解法37