《线性方程组的几种求解方法》由会员分享，可在线阅读，更多相关《线性方程组的几种求解方法（15页珍藏版）》请在金锄头文库上搜索。
1、线性方程组的几种解法线性方程组形式如下:口陋的I勺产式句+%#?+,+/=%常记为矩阵形式Ax=B其中町鼻瓦、高斯消元法高斯(Gauss)消元法的基本思想是：通过一系列的加减消元运算，也就是代数中的加减消去法，将方程组化为上三角矩阵；然后，再逐一回代求解出x向量。现举例说明如下:311+2+其36(1)w2兀1+2叼+2啊=4(2)4兀1-2x3-2$-2(3)(一)消元过程第一步：将(1)/3使xi的系数化为1得再将(2)、(3)式中xi的系数都化为零，即由(2)-2X(1)得21XiX2X3=2.(1)()332X24X3=0(2)33由(3)-4X(1)得1410人-x2-x3=-633
2、第二步：将(2)除以2/3,使X2系数化为1,得x22x3=0.(2)再将(3)式中x2系数化为零，即由(3)-(-14/3)*(2)，得138x3=6(3)第三步：将除以18/3,使x3系数化为1,得x3-1.(3)经消元后，得到如下三角代数方程组：(二)回代过程由(3)(3)得x3=1,将x3代入(2)得x2=-2,将*2、*3代入(1)得*2=1所以，本题解为x=1,2,-1(三)、用矩阵演示进行消元过程第一步：先将方程写成增广矩阵的形式第二步：然后对矩阵进行初等行变换初等行变换包含如下操作(1)将某行同乘或同除一个非零实数(2)将某行加入到另一行(3)将任意两行互换第三步：将增广矩阵变
3、换成上三角矩阵，即主对角线全为1,左下三角矩阵全为0,形式如下：01必产.心小示例:(四)高斯消元的公式综合以上讨论，不难看出，高斯消元法解方程组的公式为1.消元2132123132240心H甲、02A03333-2-22-014T10T.610213312斌f231i3220一0。33601-1(1)令a/1)=aij,(i,j=1,2,3，,n)bi(1)=bi,(i=1,2,3，,n)(2)对k=1到n-1,若akk(k)w0,进行lik=aik(k)/akk(k),(i=k+1,k+2,n)aij(k+1)=aij(k)-lik*akj(k),(i,j=k+1,k+2,n)bi(k+1
4、)=bi(k)-lik*bk(k),(i=k+1,k+2,n)2.回代若ann(n)0Xn=bn(n)/ann(n)Xi=(bi(i)-sgm(aj(i)*Xj)/-aii(i),(i=n-1,n-2,，1),(j=i+1,i+2,n)(五)高斯消元法的条件消元过程要求4才0(i=1,2,n),回代过程则进一步要求.W0,但就方程组Ax=b讲，.是否等于0时无法事先看出来的。注意A的顺序主子式Di(i=1,2,n),在消元的过程中不变，这是因为消元所作的变换是“将某行的若干倍加到另一行”。若高斯消元法的过程进行了k-1步(%w0,ik),这时计算的A(k)顺序主子式Di=aiiD2=311(1
5、)出(1)(2)(k)Dk-311322.3k,k有递推公式Di=aii(1)Di=Dma.(i=2,3,，n)所以有定理：高斯消元法消元过程能进行到底的充要条件是系数阵A的1到n-1阶的顺序主子式不为0。(六)选主消元因为在高斯消元的过程中，要做乘法和除法运算，因此会产生误差。当|3kk(k)|1,此时用它作除数。会导致其他元素数量级严重增加，带来误差扩散，使结果严重失真。例如：0.00001xi+X2=1.000012xi+X2=3解：0X000111000011fl100000213JQl100001/1000003J10199999100001、199997)3网10000010000
6、1、QiI；代入得到Xi=0,X2=1o显然，严重失真换主元，将两行交换，如下，10000113W705L00001J0.0000111、,10515、t-Tl网QQQ011.00001J1011；代入得到Xi=1,X2=1，答案正确。总结：在消元的过程中，如果出现主元相差比较大的情况，应选择如下图方框中的最大数作为主元。甚至可以在整个矩阵中找最大数作为主元，但此时需要做列变换，要记住个分量的顺序。(六)解的判断(必要是可设方程组的增广矩阵记为A,则A经过初等行变换可化为如下的阶梯形矩阵重新排列未知量的顺序)：C12匕我03c”勺Jt心iBiBillll!ll!tililiBiD0,Og】%0
7、000口r+1000000.一.鼻00Q000,其中Cii题(i=i,2,r),于是可知:(1) .当dr+i=0,且r=n时，原方程组有唯一解.(2) .当dr+i=0,且rk时，1kr=0,且1kk=i,因为nakj二ukj1krurjri所以，7nukj=akjIkrurjj=k,ki,，nri同理可推出计算L的第k列的公式：nlik=(aik1krurj)/ukki=k,ki,.,nri因此得到如下算法一一杜利特(Doo1itt1e)算法：(i)将矩阵分解为A=LU,对k=i,2,n，nukj=akj-工1kr%j=k,k+i,.,nrin公式i：/k=区兀叫)i=k,k+i,.,nr
8、T1kk=i(2)解Ly=bk4公式2:yk=bk-v1kryrk=i,2,.,nri1、21V2121y33219、2322(3)解lk=y公式3:Xk=(yk-%ukrxr)/ukk例：求解方程组2426、X1、2965X22326918X322915140)1X4/r-1解:由公式1得出2426123361于是化为两个方程组利用公式2,3可解y=(9,5,3,-1)T,x=(0.5,2,3,-1)T三、应用问题1:维他命的配方维他命是一种好的药品，人们都需要摄入一定量的各种维生素，现在有若干种维他命,问能否利用这些维他命配制出适合人需求的各种维生素。数据输入：第一行：人们需补充的V(1=
9、V=25)种维生素。第二行：V个数，第i个数为Vi,表示人体对第i种维生素的需求量。(1=Vi=1000)第三行：已知的G(1=G=15)种维他命。以下G*V的整数矩阵：第i行第j个数为Aij,表示第i种维他命中所含的第j种维生素的含量(1=Aij=1000)。数据输出:第一行：输出能否配制，若能输出Yes,否则输出No第二行：若能配制，则输出G个整数，其中第i个整数Gi,表示第i种维他命所取的数量，若有多种配置方案，输出一种即可。若不能配制，则第二行为空。样例：input.txt410020030040045050505030100100100205015025050100150200out
10、put.txtYes1110分析：因为不知道每种维他命的数量，如果采用枚举，很难估计每种维他命的上界，而且时间复杂度很高，下面我们尝试用解方程的方法。设需要配制的维他命每种数量分别为X1,xn,其中n=15，根据题意，可列出如下方程。,50302050、Xi100,5010050100x220050100150150x3300150100250200Jx4)400J用高斯消元法求解：这里，虽然x4可取任意值，显然，表示x4的数量与答案无关，因此x4=0,代入，可得x3=1,x2=1,Xi=1,因此，原问题的解为(1,1,1,0)。勺0302050100(1向0(2)-=50532510(3)-(2)5010050100200(3)-60的j50T12124(4)-(2)(2)J1)5010015015030012336卸100250200400/02548J1212412124073510力(3)2.013/75/710/7002120011/21Q0000)0000)071200、003510、424,与(2)交换(4)-(3)*2问题2:虫食算（NOIP2005）给出一个N（N=26）进制的加法算式，如下：ABCED+BDACEEBBAA其中有些是数
