第六章线性方程组的数值解法

第六章线性方程组的数值解法南京中医药大学信息技术学院制作:张季第六章线性方程组的数值解法6.1迭代法6.2约当消去法6.3高斯消去法6.4追赶法内容提要：本章主要介绍线性方程组的两种数值解法－－迭代法和直接法。迭代法重点介绍高斯－塞德尔(Gauss-Seidel)迭代法；直接法主要介绍一般的约当消去法、高斯消去法，选主约当消去法、选主高斯消去法以及追赶法。迭代法•需要一个初始向量x(0)•要构造出一种迭代式，能够由x(k-1)计算出x(k)•判断由迭代式计算出的向量序列{x(k)}是否收敛•若x*是方程组的解，那么迭代的终止条件是什么？迭代法的基本思想是，对于给定的线性方程组AX=b经过等价变换构造出一个等价方程组X=GX+d将上式改写成迭代式X(k+1)=GX(k)+d选定初始X(0),反复不断地使用迭代式校正方程组根的近似值，并在此过程中求取符合计算精确度要求的方程组的近似值。迭代法的基本思想迭代法的计算公式x1=(b1-a12x2-a13x3-…-a1,n-1xn-1-a1nxn)/a11x2=(b2-a21x1-a23x3-…-a2,n-1xn-1-a2nxn)/a22……xn=(bn-an1x1-an2x2-…-an,n-2xn-2-an,n-1xn-1)/ann若令gij=-aij/aii,i,j=1,2,…,n,且i≠jdi=bj/aii,i=1,2,…,n则方程可改写为：X=GX+dG=0g12g13…g1,n-1g1ng210g23…g2,n-1g2n………………gn1gn2gn3…gn,n-10X=(x1,x2,…,xn)T,d=(d1,d2,…,dn)T由此可得到迭代式：X(k+1)=GX(k)+d或者表示为：xi(k+1)=∑gijxj(k)+di(i=1,2,…,n)j=1n由上所述可以看出：在计算X2(k+1)时，X1(k+1)已经计算出来。对于收敛的迭代过程来说，X1(k+1)常常比X1(k)更准确些。因此，可用X1(k+1)来代替X1(k)做进一步计算，因此迭代式可表示为：xi(k+1)=di-(gijxj(k+1)+gijxj(k)),(i=1,2,…,n)∑nj=i∑i-1j=1算法设计1)用迭代公式求出方程组的近似根值.2)判断近似解是否达到计算精度，即使用条件max|xi(k+1)-xi(k)|e若满足条件，终止迭代，程序转去输出而归于结束。若条件不满足，继续迭代。3)判断迭代次数是否超过lm，可使用条件判断并执行相应的操作。Klm若满足，继续迭代。若不满足，程序结束，并打印出“经过lm次迭代，仍未收敛”的信息。l≤i≤n程序框图设计使用迭代法求解线性方程组的近似根。定义并输入在for(i=1;ilm;i++)循环中使用迭代法求解线性方程组的近似根。输出使用|x[i]-t|r作为判别式，选取前后两次迭代根差值绝对值中的最大值。使用re作为判别式，若满足则转出循环进行输出，否则继续循环。T=x[i],q=0使用迭代法求线性方程组新的近似根。Jordan(约当)消元法2-252343-13x1x2x3=132010A(0)=2-2513234203-1310A(1)=2-251305-1702-9/2-19/2A(2)=2023/579/505-1700-41/10-19/2A(3)=20020501000-41/10-123/220005000-41/10x1x2x3=210-123/10X1=2/2=1X2=10/5=2X3=(-123/10)/(-41/10)=3简单约当消去法基本思想a11x1+a12x2+…+a1nxn=a1,n+1a21x1+a22x2+…+a2nxn=a2,n+1…an1x1+an2x2+…+annxn=an,n+1a11a12…a1na21a22…a2n…an1an2…annx1x2…xna1,n+1a2,n+1…an,n+1=通过消去计算，即矩阵的初等变换，将方程组变换成为如下等价的方程组：a110…00a22…0…00…annx1x2…xna1,n+1a2,n+1…an,n+1=Xi=ai,n+1/aii,i=1,2,…,n基本思想：将线性方程组的系数矩阵通过初等变换，化为一个等价的对角阵，从而方便地求出方程的解。计算过程第一步：消去第一列中除a11之外的的其他元素1）第一行保持不变2）对于其他行的元素进行如下处理：将第1行的元素除以a11，再乘上其他行第1列的ai1，所得乘积的负值加到这一行上。第二步，消去第二列中除a22之外的其他元素…重复上述过程程序框图设计使用简单的约当消去法求解线性方程组的解。输入使用简单的约当消去法求解线性方程组的解。输出将系数矩阵经过消去计算变换为等价的对角阵。求根选主元约当消去法必要性：简单的消元法能否顺利进行，取决于每一步能否满足akk≠0，否则，简单的消元法不能进行。此外，a极小时有可能会造成上溢而中断程序，或者使误差放大很多倍。列主消元法的求根过程1.选主元，即在一批元素中把绝对值最大的元素挑选出来。2.通过换行将所选的主元置于a11的位置上，然后进行第一次消元计算，如此一直进行下去……，直到完成第n次选主元和第n次消元计算。算法设计1)在第k列的第k个~第n个元素的范围内选主元，并通过换行，将当前主元换到第akk的位置上。2)判断akk是否为零3)将第k列除akk元外的其他元素均消去为0。4)求方程组的近似解。若满足，则输出程序无法执行的信息。若不满足，执行后继语句。程序框图设计使用列主元约当消去法求解线性方程组的解。输入使用列主元约当消去法求解线性方程组的解。输出消元计算求根在第k列的第k行~第n行的范围内选主元apk将第k行与第p行交换位置对第k列进行消元计算，除akk以外的元素均消去为0高斯消去法首先把系数矩阵变换为一个上三角矩阵，此过程仍为消去过程，最后一步把上三角矩阵化为单位矩阵，称为回代过程。a11a12…a1na21a22…a2n…an1an2…annx1x2…xna1,n+1a2,n+1…an,n+1=a11a12…a1n0a22…a2n…00…annx1x2…xna1,n+1a2,n+1…an,n+1=ri1=ai1/a11,i=2,3,…,naij=aij-ri1∙a1j,i=2,3,…,n,j=1,2,…,n,n+1追赶法针对三对角阵来说，只要对集中在三条对角线上的非零元素进行消去计算并将其值存放起来，再通过回代即可将方程组的根解算出来。计算公式先利用方程组式的第一个方程消去第二个方程中的x1，然后再利用第二个方程消去第三个方程中的x2，以此类推。x1+c1/b1∙x2=d1/b1,r1=c1/b1,y1=d1/b1x1+r1x2=y1x2+(c2/b2-a2r1)∙x3=(d2-a2y1)/(b2-a2r1),r2=c2/b2-a2r1,y2=(d2-a2y1)/(b2-a2r1)x2+r2x3=y2x1=y1-r1x2代入第二个方程a2∙(y1-r1x2)+b2x2+c2x3=d2…….xk-1+rk-1xk=yk-1于是：xk+ck/(bk-akrk-1)xk+1=(dk-akyk-1)/(bk-akrk-1)xk-1=yk-1-rk-1xk代入第k个方程ak∙(yk-1-rk-1xk)+bkxk+ckxk+1=dk若令：rk=ck/(bk-akrk-1),yk=(dk-akyk-1)/(bk-akrk-1)则第k个方程可化为：xk+rkxk+1=yk如此经过n-1次变换后可得：xn-1+rn-1xn=yn-1由此求得：xn=(dn-anyn-1)/(bn-anrn-1)xn-1=yn-1-rn-1xn代入第n个方程an∙(yn-1-rn-1xn)+bnxn=dn若令：yn=(dn-anyn-1)/(bn-anrn-1)则第n个方程化为：xn=ynx1+r1x2=y1x2+r2x3=y2……xk+rkxk+1=yk……xn-1+rn-1xn=yn-1xn=ynr1=c1/b1,y1=d1/b1ri=ci/(bi-airi-1),i=2,3,…,n-1yi=(di-aiyi-1)/(bi-airi-1),i=2,3,…,n-1将上述简化后的方程集中起来：其中：算法设计1)追的过程（消去过程）：顺序计算出系数r1,r2,…,rn-1,以及y1,y2,…,yn.2)赶的过程（回代过程）：逆序求出xn,xn-1,…,x1.程序框图设计使用追赶法求解线性方程组的解。输入使用追赶法求解线性方程组的解。输出使用公式对三对角阵进行消元计算，将原方程组变成为式的形式。使用公式进行回代，按逆序求出线性方程组的近似解。小结求解线性方程组有两种方法－－直接法与迭代法，直接法又称为消去法。本章介绍的雅可比迭代法与高斯－塞德尔迭代法是最简单的迭代法。约当消去法与高斯消去法是解线性方程组的两种基本方法，此外，本章还介绍了一种特殊的线性方程组－－三对角方程组的算法及程序。