第二节高斯消元法及其计算机实现

《第二节高斯消元法及其计算机实现》由会员分享，可在线阅读，更多相关《第二节高斯消元法及其计算机实现（40页珍藏版）》请在装配图网上搜索。

1、数值分析数值分析数值分析数值分析第二节第二节 高斯消元法及其计算机实现高斯消元法及其计算机实现第三节第三节 用矩阵分解法求解线性方程组用矩阵分解法求解线性方程组第四节第四节 误差分析和解的精度改进误差分析和解的精度改进第五节第五节 大型稀疏方程组的迭代法大型稀疏方程组的迭代法第三章第三章 线性代数方程组的数值解法线性代数方程组的数值解法n第一节第一节 求解线性代数方程组的基本定理求解线性代数方程组的基本定理第六节第六节 极小化方法极小化方法数值分析数值分析数值分析数值分析线性代数方程组的一般形式线性代数方程组的一般形式(1)mnAxbAR 用用矩矩阵阵形形式式表表示示为为其其增增广广矩矩阵阵记

2、记为为 11112211211222221122 nnnnmmmnnma xa xa xba xa xaxbaxaxaxb 11121121222212,nnmmmnmaaabaaabAA baaab 第一节第一节 求解线性代数方程组的基本定理求解线性代数方程组的基本定理数值分析数值分析数值分析数值分析AxbAA 线线性性方方程程组组 有有解解的的充充分分必必定定理理1 1 （线线性性代代数数方方程程组组要要条条件件是是：秩秩（ ）= =秩秩有有解解判判定定理理（别别）(1)( )( ),AxbAArnAxb 线线性性方方程程组组有有解解（即即相相容容）时时，秩秩定定理理2 2秩秩则则方方程程

3、组组存存在在唯唯一一解解。(2) ( )( ),r Ar ArnAxb 方方程程组组有有无无穷穷多多解解。通通解解原原方方程程组组一一个个特特解解对对应应齐齐次次方方程程组组的的基基础础解解系系的的线线性性组组合合。222,|min|mnAxbxxxxAxb 常常见见是是，称称为为欠欠定定方方程程组组（方方程程数数少少于于未未知知数数）此此时时，从从的的无无穷穷多多个个解解中中需需求求出出范范数数最最小小的的解解。即即求求使使， 满满足足。数值分析数值分析数值分析数值分析22()()()|minr Ar AAxbmnbAR AxxbAx 方方程程组组无无解解（即即不不相相容容）。常常见见是是，

4、称称为为超超定定方方程程组组（又又称称矛矛盾盾方方程程组组）此此时时，向向量量 不不在在 的的列列空空间间之之中中，原原方方程程组组无无解解，但但可可求求出出最最小小二二乘乘意意义义下下的的解解 。即即求求 使使MATLAB实现实现: x=Ab11112211211222221122 nnnnnnnnnnna xa xa xba xa xaxba xaxaxb 本本章章介介绍绍求求解解 阶阶线线性性方方程程组组的的数数值值方方法法数值分析数值分析数值分析数值分析 数值求解方法有以下三条途径（三种框架）数值求解方法有以下三条途径（三种框架） 直接法：利用直接法：利用Gauss消元或矩阵分解，通过

5、有限次运算消元或矩阵分解，通过有限次运算 可求出精确解。可求出精确解。迭代法：构造迭代格式，产生迭代序列，通过无限迭代法：构造迭代格式，产生迭代序列，通过无限 次迭代过程求解。有限次截断得近似解。次迭代过程求解。有限次截断得近似解。极小化方法：构造二次模函数，用迭代过程求二次极小化方法：构造二次模函数，用迭代过程求二次 模函数的极小化问题，即变分法（经模函数的极小化问题，即变分法（经n 次运算，理论上得精确解）要求次运算，理论上得精确解）要求A 对称正定对称正定(S.P.D)数值分析数值分析数值分析数值分析 用增广矩阵表示为用增广矩阵表示为同解同解初等变换初等变换组组化为同解的上三角方程化为同

6、解的上三角方程将原方程组将原方程组求解求解gUxbAxgUxbAxRAbAxnn 第二节第二节 高斯消元法及其计算机实现高斯消元法及其计算机实现数值分析数值分析数值分析数值分析 A b U g )1()1()1(2)1(1)1(2)1(2)1(22)1(21)1(1)1(1)1(12)1(11nnnnnnnbaaabaaabaaa )()()2(2)2(2)2(22)1(1)1(1)1(12)1(11nnnnnnnbabaabaaa数值分析数值分析数值分析数值分析 三角形方程组包括上三角形方程组和下三角三角形方程组包括上三角形方程组和下三角形方程组，是最简单的线性方程组之一。上三角形方程组，是

7、最简单的线性方程组之一。上三角方程组的一般形式是方程组的一般形式是： ),.,2 , 1(0.111112222211212111niabxabxaxabxaxabxaxaxaiinnnnnnnnnnnnnnn 其其中中一、三角形方程组的解法一、三角形方程组的解法数值分析数值分析数值分析数值分析1242343444573131313131xxxxxxxxx 用用回回代代法法求求解解线线性性方方程程组组例例43424314212341(1313)/ 30( 75)( 750)244121,)(1 ,2,0:,1)TTxxxxxxxxxxxxx 所所以以，解解为为（解解数值分析数值分析数值分析数值

8、分析1 , 1/ )(/1 niaxabxabxnikiikikiinnnn 为求解上三角方程组，从最后一个方程入手，先为求解上三角方程组，从最后一个方程入手，先解出解出 x xn n=b=bn n/a/annnn, , 然后按方程由后向前的顺序，从方然后按方程由后向前的顺序，从方程中依次解出程中依次解出x xn-1n-1,x,xn-2n-2,x,x1 1。这样就完成了上三角方这样就完成了上三角方程组的求解过程。这个过程被称为回代过程其计算步程组的求解过程。这个过程被称为回代过程其计算步骤如下：骤如下：数值分析数值分析数值分析数值分析1 , 1/ )(/1 niaxabxabxnikiikik

9、iinnnn function X=backsub(A,b)%InputA is an nn upper- triangular nonsingullar matrix% -b is an n1 matrix%OutputX is the solution to the system AX=b函数名返回变量参数表n=length(b);X=zeros(n,1);X(n)=b(n)/A(n,n);for i=n-1:-1:1 X(i)=(b(i)-A(i,i+1:n)* X(i+1:n)/A(i,i);endA的第i行、第i+1到n列元素构成的行向量数值分析数值分析数值分析数值分析1121232

10、2232429xxxxxx 用用回回代代法法求求解解线线性性例例 、方方程程组组1231232/ 21(21)/11(93121)/ 41,)(1 ,1 , ):1xxxxxx 所所以以，解解为为（解解21111)(1)22ninin nn 求解一个三角形方程组需 次除法与求解一个三角形方程组需 次除法与（次乘法。（次乘法。数值分析数值分析数值分析数值分析12111111,/()/(2,3, )niiiikkiikxxxxbaxba xain 下下三三角角形形方方程程组组可可以以参参照照上上三三角角形形方方程程组组的的解解法法来来求求解解，下下三三角角形形方方程程组组的的求求解解顺顺序序是是从

11、从第第一一个个方方程程开开始始，按按从从上上到到下下的的顺顺序序，依依次次解解出出：其其计计算算公公式式为为：如如上上解解三三角角形形方方程程组组的的方方法法称称为为回回代代法法. .1111211222211220,1,2,nnnnnniia xbaxaxbaxaxaxbain 下下三三角角方方程程组组的的一一般般形形式式为为：其其中中数值分析数值分析数值分析数值分析 高斯消元法是一个古老的直接法高斯消元法是一个古老的直接法, ,由它改进得到由它改进得到的选主元法的选主元法, ,是目前计算机上常用于求低阶稠密矩阵是目前计算机上常用于求低阶稠密矩阵方程组的有效方法方程组的有效方法, ,其特点就

12、是通过消元将其特点就是通过消元将一般线性一般线性方程组方程组的求解问题转化为的求解问题转化为三角方程组三角方程组的求解问题。的求解问题。 高斯消元法的求解过程高斯消元法的求解过程, ,可大致分为两个阶段可大致分为两个阶段: :首先首先, ,把原方程组化为上三角形方程组把原方程组化为上三角形方程组, ,称之为称之为“消消元元”过程过程; ;然后然后, ,用逆次序逐一求出上三角方程组用逆次序逐一求出上三角方程组( (原原方程组的等价方程组方程组的等价方程组) )的解的解, ,称之为称之为“回代回代”过程过程. . 高斯高斯“消消元元”过程过程可通过矩阵运算来实现。具可通过矩阵运算来实现。具体过程如

13、下：体过程如下：二、高斯消元法二、高斯消元法数值分析数值分析数值分析数值分析12312312323623493263Gaussxxxxxxxxx 用用消消元元法法求求解解方方程程例例组组11/1/21/2/01, 362319432632111313111212111)1( aamaamanbAA增增广广矩矩阵阵：解：解：11121,:11L AxL b 1 1L L = =, ,完完成成第第一一步步消消元元 得得数值分析数值分析数值分析数值分析(2)(2)(2)223232222212110,/1/( 1)111,11amaaLL L AxL L b = =, ,完完成成第第二二步步消消元元

14、 得得 3332632332321xxxxxx3231231233 /31( 32)( 321)16236213111,1,1xxxxxxxxx 回回代代求求得得故故所所求求解解为为 011032106321)2(A 330032106321)3(A数值分析数值分析数值分析数值分析将方程组将方程组Ax=b的系数矩阵与右端项合并为的系数矩阵与右端项合并为 11121121222212,nnnnnnnaaabaaabA bAaaab (1)(1)(1)1111(1)(1)(1)(1)(1)12(1)(1)(1)1.,.,.nnnnnnaabAAbaab记记 (1)(1)1(1)11111,0,.,

15、0.TALLa 对的第一列构对的第一列构造使造使1(1)11111110,2,.,iiaamina（ ）（ ）（ ）（ ）：设取：设取第一步第一步2111111nmLm 数值分析数值分析数值分析数值分析(1)(1)(1)(1)111211(2)(2)(2)(1)(2)(2)(2)(2)(2)2222112(2)(2)(2)2.0.,.,0.nnnnnnnaaabaabL AAbaab (2)(1)(1)1 1(2)(1)(1)1 12, ,2,2,ijijijiiiaam ain jnbbm bin (1)(1)1(1)(1)11AxbLL AxL b 对对方方程程组组从从左左边边乘乘以以(1

16、)(1)(1)1111(1)211(1)(1)(1)111.1.1nnnnnnaabmL Aaabm 数值分析数值分析数值分析数值分析(2)(2)2222(2)2203,.,iiaamina：设，：设，第二步第二步取取(2)(2)32222(1)(1)(1)(1)(1)1112131,1(2)(2)(2)(2)22232,2(2)(1)(3)(3)(3)(3)221333,3(3)(3)(3)3,111,100000nnnnnn nnmALmaaaabaaabL AL L AaaAbaab - -对的第二列构造对的第二列构造- -使使数值分析数值分析数值分析数值分析(2)22(2)22,iia

17、ma (1)(1)2121L L AxL L b (3)(2)(2)22(3)(2)(2)22,3,3,4,.,ijijijiiiaam ai jnbbm bin (1)(1)(1)(1)111211(2)(2)(2)(2)2222322(2)(2)(2)22(1)(1)(1)(1)1112131,(2)(2)(2)22232,(3)(3)333,(331.10.10.100000nnnnnnnnnnnaaabaabmL Aaabmaaaaaaaaaa - - -(1)1(2)2(3)(3)3)(3)(3),n nnbbAbab 数值分析数值分析数值分析数值分析进行到第进行到第k步消元时步消元

18、时( )(1)( )kkkAAAk 下下一一步步消消元元，从从，将将的的第第 列列的的对对角角元元以以下下的的元元素素化化为为零零。(1)(1)(1)(1)(1)11121311(2)(2)(2)(2)222322(3)(3)(3)3333()()()()1()()()1,1,11()()()(),1.nnnkkkkkkkkkkkkkkkkkkkkknkn knnnaaaabaaabaabAaabaabaaab 数值分析数值分析数值分析数值分析( )( )( )0,(1,., )kkikkkkikkkkaamaiknGaussL 设设取取，构构造造变变换换阵阵,111111Tkkkkn kIl

19、 emm (1)()kkkAL A 消消元元计计算算递递推推公公式式：()(1,2,1)kkkakn 称称为为主主元元素素. .( )( )(1)( )( )(1)( )( )1,1/21,3kkikikkkkkkijijikkjkkkiiikkiknmaaaam ajknbbm b （）（ ），（ ）数值分析数值分析数值分析数值分析(1)(1)(1)(1)11112211(2)(2)(2)22222()()nnnnnnnnnnaxaxaxbaxaxbaxb 即即 用回代过程求解上三角方程组，即可得解向量用回代过程求解上三角方程组，即可得解向量 ( x1*,x2*, ,xn* ) )T T.

20、.是是高高斯斯消消元元的的前前提提。)1,2, 1( ,0)( nkakkk(1)(1)121121nnLL L AxLL L b (1)(1)(1)(1)111211(2)(2)(2)()2222()()000nnnnnnnnaaabaabAab 最最后后得得数值分析数值分析数值分析数值分析求解的全过程包括两个步骤：消元和回代求解的全过程包括两个步骤：消元和回代1 . 1 . 顺序消元顺序消元2 . 回代求解回代求解( )( )( )( )( )1/()/1,2,1nnnnnnnkkkkkkjjkkj kxbaxbaxaknn ( )( )(1)( )( )(1)( )( )1,11,1/2

21、1,3kkikikkkkkkijijikkjkkkiiikkkniknmaaaam ajknbbm b （）（ ），（ ）数值分析数值分析数值分析数值分析步步消消元元计计算算后后，第第的的二二维维数数组组存存放放一一个个用用用用动动态态存存储储方方式式。最最初初在在计计算算机机中中计计算算时时，采采存存储储方方式式kAnn ), 1;, 1(), 1()1()()(nkjnkiaankimakijkijikkik )()(1,)()(1,1)(,1)(1)()3(3)3(33)2(2)2(23)2(22)1(1)1(13)1(12)1(11)(.knnkknknkkkkkkkkkkkkknnn

22、kaaaaaaaaaaaaaaaaAikm) 1( kija数值分析数值分析数值分析数值分析UIL 消元过程全部完成后，原来的二维数组中存放的消元过程全部完成后，原来的二维数组中存放的元素实际上是一个新的矩阵，记为元素实际上是一个新的矩阵，记为FAFAA用动态形式表示为用动态形式表示为)(1,321)3(3)3(1, 3)3(333231)2(2)2(1,2)2(23)2(2221)1(1)1(1, 1)1(13)1(12)1(11nnnnnnnnnnnnnnFammmmaaammaaaamaaaaaA数值分析数值分析数值分析数值分析function X=gauss(A,b)%InputA i

23、s an nn nonsingullar matrix% -b is an n1 matrix%OutputX is the solution to the system AX=bMATLAB For Gaussian Eliminationn n=size(A); % 确定确定A的维数的维数X=zeros(n,1);for k=1:n-1 for i=k+1:n % 消元过程消元过程 m=A(i,k)/ A(k,k); % A(k,k) 0 A(i,k+1:n)= A(i,k+1:n)-m*A(k,k+1:n); b(i)= b(i)-m*b(k); endendX=backsub(A, b

24、); %回代求解回代求解数值分析数值分析数值分析数值分析function X=gauss(A,b)%InputA is an nn nonsingullar matrix% -b is an n1 matrix%OutputX is the solution to the system AX=bMATLAB For Gaussian Eliminationn n=size(A); % 确定确定A的维数的维数X=zeros(n,1);for k=1:n-1 for i=k+1:n % % 消元过程消元过程 A(i,k) =A(i,k)/ A(k,k); % A(k,k) 0 A(i,k+1:n)

25、= A(i,k+1:n)- A(i,k) *A(k,k+1:n); b(i)= b(i)- A(i,k) *b(k); endendX=backsub(A, b); %回代求解回代求解数值分析数值分析数值分析数值分析 高斯消元法的计算量分析高斯消元法的乘除总运算分析为分析为消元次数消元次数k k 消元乘法次数消元乘法次数 消元除法次数消元除法次数 回代乘除法次数回代乘除法次数 1 n(n-1) n-11 n(n-1) n-1 2 (n-1)(n-2) n-2 2 (n-1)(n-2) n-2 . . k (n-k+1)(n-k) n-k k (n-k+1)(n-k) n-k . . n-1 2

26、 n-1 2* *1 11 1 n(n+1)/2n(n+1)/2高斯消元法的计算量为高斯消元法的计算量为 232(1)(1)(1)32233n nn nn nnnNn 乘乘 除除 回代回代 当当 n n 充分大时为充分大时为 N Nn n3 3/3/3数值分析数值分析数值分析数值分析 消元法是解线性方程组的基本方法，具有计算简消元法是解线性方程组的基本方法，具有计算简单的优点，但有时由于主元过小，使得计算结果严重单的优点，但有时由于主元过小，使得计算结果严重失真失真, ,实际中常采用选主元高斯消元法。实际中常采用选主元高斯消元法。数值分析数值分析数值分析数值分析0.0001x1+x2=1 x1

27、+x2=2假设求解是在四位浮点十进制数假设求解是在四位浮点十进制数的计算机上进行的计算机上进行0.1000 10-3 x1 + 0.1000 101 x2 = 0.1000 1010.1000 101 x1 +0.1000 101 x2 = 0.2000 101 解解: :本题用机器数系表示为本题用机器数系表示为 a11 =0.0001, m21=a21/a11=1/0.0001= 104, 消元消元得得 回代解得回代解得 x2 2=1=1 , x1 1=0=0 严重失真严重失真! ! (本题的准确解为本题的准确解为 x1 1= = 10000/9999, x2 2= =9998/9999 ）

28、a22(2)= 0.1000 101 - 104 0.1000 101 = 0.00001 105 - 0.1000 105 (对阶计算对阶计算) = - 0.1000 105 0.1000 10-3 x1 + 0.1000 101 x2 = 0.1000 101 -0.1000 105 x2 = -0.1000 105 主元主元a11过小过小数值分析数值分析数值分析数值分析 选主元基本思想选主元基本思想 用高斯消元法求解线性方程组时用高斯消元法求解线性方程组时, ,为避免小的主元为避免小的主元. .在进在进行第行第k k步消元前步消元前, ,应该在第应该在第k k列元素列元素 ( (i=k,

29、ni=k,n) )中找出第中找出第一个出现的绝对值最大者一个出现的绝对值最大者, ,例如例如 ， 再把第再把第i ik k个方程与第个方程与第k k个方程组进行交换个方程组进行交换, ,使使 成为主元成为主元. .我们我们称这个过程为选主元称这个过程为选主元. .由于只在第由于只在第k k列元素中选主元列元素中选主元, ,通常通常也称为也称为按列选主元按列选主元. . )(kika()()maxkkki kikkinaa )(kija 如果在第如果在第k k步消元前步消元前, ,在第在第k k个方程到第个方程到第n n个方程所有个方程所有的的x xk k到到x xn n的系数的系数 ( (i=

30、k,n;j=k,ni=k,n;j=k,n) )中中, ,找出绝对值找出绝对值最大者最大者, ,例如例如 ( )kki ka三、选主元三、选主元高斯消元法高斯消元法数值分析数值分析数值分析数值分析再交换第再交换第k k, ,ikik两个方程和第两个方程和第k k, ,jkjk列列, ,使使 成为主元成为主元. . 称这个过程为称这个过程为完全选主元完全选主元. 不论是哪种方式选出主元不论是哪种方式选出主元, ,而后再按上面介绍的计而后再按上面介绍的计 算步算步骤进行消元的计算骤进行消元的计算, ,一般都称为选主元的高斯消元法一般都称为选主元的高斯消元法. .在在实际计算中实际计算中, ,常用按列

31、选主元的高斯消元法常用按列选主元的高斯消元法. .( )k kki ja( )( ),maxk kkki jijk i j naa 数值分析数值分析数值分析数值分析( )( )( )( )( )()()| max|,1,(1),(,2kkkkkkkkkkki kikk i nkkkkkkji jkjkji ji jkikkiikikinaaAAbikTikaajk knTaaaaTbbTb bbbT 对对每每一一步步 第第 步步 消消元元，分分两两步步确确定定使使对对增增广广矩矩阵阵使使列列主主元元高高斯斯消消元元法法具具体体做做法法是是：选选列列主主元元换换行行在在计计算算机机上上，用用一一

32、个个工工作作单单元元来来完完成成，对对，包包括括消消元元计计算算数值分析数值分析数值分析数值分析算法算法 列主元高斯消元法解线性方程组列主元高斯消元法解线性方程组 Ax = bAx = b停停机机。信信息息输输出出失失败败则则认认为为如如果果使使确确定定、选选列列主主元元步步。循循环环执执行行到到第第对对、置置, , 0det , 0 ,max 2 51, 2 , 1 1det 1 kikiiknikkikkkkaaaaink detdet , ), 1,( , 4 , 3 kkikjikjkbbnkkjaaki否否则则交交换换行行步步转转出出执执行行第第、如如果果具体执行行交换要通过工作单元

33、具体执行行交换要通过工作单元 T。TbbbbTTaaaaTkkkkiikkjijikjkj ; ; ; ;数值分析数值分析数值分析数值分析。、输输出出解解向向量量、否否则则停停机机。输输出出失失败败信信息息则则认认为为如如果果、回回代代求求解解、FTnnniinijjijiinnnnnnnnkkAAbbbxanniababbabbaaadet, ,),( 8detdet7)1 , 2 , 2, 1( / )( / , 0,6detdet 5211 (3) ), 1( (2) /(1) , 2, 14kikiikjikijijkkikikikbabbnkjaaaaaamankki 、消消元元计计

34、算算数值分析数值分析数值分析数值分析假设求解是在四假设求解是在四位浮点十进制数位浮点十进制数的计算机上进行的计算机上进行0.0001x1+x2=1 x1+x2=2将两个方程对调，得将两个方程对调，得 x1+x2=2 0.0001x1+x2=1在四位浮点十进制数的计算机上在四位浮点十进制数的计算机上,上式为上式为 x1+x2=2 即即 x1+x2=2 (0.1000101-0.00001 101x2=1 x2=1（1-0.0001) x2=1x1+x2=2消元，得消元，得解得：解得： x1=1， x2=1现在我们再用列主元法解例现在我们再用列主元法解例4数值分析数值分析数值分析数值分析例例5 5

35、 用列主元消去法解方程组用列主元消去法解方程组解解 第一次消元对第一次消元对 因列主元素为因列主元素为a a3131(1)(1), ,故先作行交换故先作行交换E E1 1 E E3 3, ,然后进行然后进行消元计算可得消元计算可得-0.002x1+2x2+2x3 =0.4 x1+0.78125x2 =1.38163.996x1+5.5625x2+4x3=7.4178 -0.002 2 2 0.4 A(1) |b(1) = 1 0.78125 0 1.3816 3.996 5.5625 4 7.4178 3.996 5.5625 4 7.4178 A(2) |b(2) = 0 -0.61077

36、-1.0010 -0.47471 0 2.0029 2.0020 0.40371数值分析数值分析数值分析数值分析 由此回代由此回代, ,得得x x=(1.9272,-0.69841,0.90038)=(1.9272,-0.69841,0.90038)T T与精确解与精确解 x x=(1.9273,-0.69850,0.90042)=(1.9273,-0.69850,0.90042)T T相相比较是比较准确的比较是比较准确的. . 3.996 5.5625 4 7.4178A(3) |b(3) = 0 2.0029 2.0020 0.40371 0 0 -0.39050 -0.35160 第二次消元对第二次消元对 A A(2)(2) | |b b(2)(2) , ,因列主元素为因列主元素为a a3232(2)(2) , ,故先故先作行交换作行交换E E2 2 E E3 3, ,然后进行消元计算可得然后进行消元计算可得数值分析数值分析数值分析数值分析二版习题二版习题 P113-6（1），），8（1）三三版版习题习题 P137-3（1），），5（1）1375(1)120211311PA