线性方程组的几种求解方法

线性方程组的几种解法线性方程组形式如下：常记为矩阵形式其中一、高斯消元法高斯（Gauss)消元法的基本思想是：通过一系列的加减消元运算，也就是代数中的加减消去法，将方程组化为上三角矩阵；然后，再逐一回代求解出x向量。现举例说明如下：（一）消元过程第一步：将(1)/3使x1的系数化为1得再将(2)、(3)式中x1的系数都化为零，即由(2)-2×(1)(1)得)1(32)2(......03432xx)1(321)1(......23132xxx由(3)-4×(1)(1)得第二步：将(2)(1)除以2/3，使x2系数化为1，得再将(3)(1)式中x2系数化为零，即由(3)(1)-(-14/3)*(2)(2)，得第三步：将(3)(2)除以18/3，使x3系数化为1，得经消元后，得到如下三角代数方程组：（二）回代过程由(3)(3)得x3=1,将x3代入(2)(2)得x2=-2,将x2、x3代入(1)(1)得x2=1所以，本题解为[x]=[1,2,-1]T（三）、用矩阵演示进行消元过程第一步：先将方程写成增广矩阵的形式第二步：然后对矩阵进行初等行变换初等行变换包含如下操作（1）将某行同乘或同除一个非零实数)3(3)3(......1x)2(3)3(......6318x)2(32)2(......02xx)1(32)3(......6310314xx（2）将某行加入到另一行（3）将任意两行互换第三步：将增广矩阵变换成上三角矩阵，即主对角线全为1，左下三角矩阵全为0，形式如下：示例：（四）高斯消元的公式综合以上讨论，不难看出，高斯消元法解方程组的公式为1．消元（1）令aij(1)=aij,（i,j=1,2,3,…,n）bi(1)=bi,（i=1,2,3,…,n）（2）对k=1到n-1，若akk(k)≠0，进行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)=bi(k)-lik*bk(k),（i=k+1,k+2,…,n）2．回代若ann(n)≠0xn=bn(n)/ann(n)xi=(bi(i)–sgm(aij(i)*xj)/-aii(i),（i=n-1,n-2,…,1）,(j=i+1,i+2,…,n)（五）高斯消元法的条件消元过程要求aii(i)≠0(i=1,2,…,n),回代过程则进一步要求ann(n)≠0,但就方程组Ax=b讲，aii(i)是否等于0时无法事先看出来的。注意A的顺序主子式Di（i=1,2,…,n）,在消元的过程中不变，这是因为消元所作的变换是“将某行的若干倍加到另一行”。若高斯消元法的过程进行了k-1步(aii(i)≠0,ik)，这时计算的A(k)顺序主子式:D1=a11(1)D2=a11(1)a22(2)……Dk=a11(1)a22(2)…ak,k(k)有递推公式D1=a11(1)Di=Di-1aii(i)(i=2,3,…,n)所以有定理：高斯消元法消元过程能进行到底的充要条件是系数阵A的1到n-1阶的顺序主子式不为0。（六）选主消元因为在高斯消元的过程中，要做乘法和除法运算，因此会产生误差。当|akk(k)|1，此时用它作除数。会导致其他元素数量级严重增加，带来误差扩散，使结果严重失真。例如：0.00001x1+x2=1.000012x1+x2=3解：代入得到x1=0,x2=1。显然，严重失真换主元，将两行交换，如下，代入得到x1=1,x2=1,答案正确。总结：在消元的过程中，如果出现主元相差比较大的情况，应选择如下图方框中的最大数作为主元。甚至可以在整个矩阵中找最大数作为主元，但此时需要做列变换，要记住个分量的顺序。（六）解的判断设方程组的增广矩阵记为A，则A经过初等行变换可化为如下的阶梯形矩阵(必要是可重新排列未知量的顺序)：其中cii0(i=1，2，…，r)．于是可知：(1).当dr+1=0，且r=n时，原方程组有唯一解．(2).当dr+1=0，且rn时，原方程组有无穷多解．(3).当dr+10，原方程组无解．二、LU分解法求解线性代数方程组除了高斯消元法外，还常用LU分解法（三角形分解法）。LU分解法的优点是当方程组左端系数矩阵不变，仅仅是方程组右端列向量改变，即外加激励信号变化时，能够方便地求解方程组。设n阶线性方程组Ax=b假设能将方程组左端系数矩阵A，分解成两个三角阵的乘积，即A=LU，式中，L为主对角线以上的元素均为零的下三角矩阵,且主对角线元素均为1的上三角矩阵；U为主对角线以下的元素均为零。所以有，LUx=b令Ux=y则Ly=b由A=LU,由矩阵的乘法公式：a1j=u1j,j=1,2,…,nai1=li1u11,i=1,2,…,n推出u1j=a1j,j=1,2,…,nli1=ai1/u11,i=1,2,…,n这样就定出了U的第一行元素和L的第一列元素。设已定出了U的前k-1行和L的前k-1列，现在确定U的第k行和L的第k列。由矩阵乘法：当rk时，lkr=0,且lkk=1，因为所以，同理可推出计算L的第k列的公式：因此得到如下算法——杜利特（Doolittle）算法:(1)将矩阵分解为A=LU,对k=1,2,…,n1,...,1,/)(,...,1,111kknrkkrjkrikiknrrjkrkjkjlnkkiuulalnkkjulau：公式(2)解Ly=b11,...,2,1:2krrkrkknkylby公式nrrjkrkjkjnkkjulau1,...,1,nrrjkrkjkjulua1nrkkrjkrikiknkkiuulal1,...,1,/)(nrrjkrkjula1(3)解Ux=y例：求解方程组472223940115618962569262424321xxxx解：由公式1得出1633216242,1233121121LU于是化为两个方程组432143214321163321624247222391233121121yyyyxxxxyyyy利用公式2，3可解y=(9,5,3,-1)T,x=(0.5,2,3,-1)T三、应用问题1：维他命的配方维他命是一种好的药品，人们都需要摄入一定量的各种维生素，现在有若干种维他命，问能否利用这些维他命配制出适合人需求的各种维生素。数据输入：第一行：人们需补充的V(1=V=25)种维生素。第二行：V个数，第i个数为Vi，表示人体对第i种维生素的需求量。（1=Vi=1000）第三行：已知的G(1=G=15)种维他命。以下G*V的整数矩阵：第i行第j个数为Aij，表示第i种维他命中所含的第j种维生素的含量（1=Aij=1000）。数据输出：nkrkkrkrkknnkuxuyx11,...,1,/)(3：公式第一行：输出能否配制，若能输出Yes，否则输出No第二行：若能配制，则输出G个整数，其中第i个整数Gi，表示第i种维他命所取的数量，若有多种配置方案，输出一种即可。若不能配制，则第二行为空。样例：input.txt410020030040045050505030100100100205015025050100150200output.txtYes1110分析：因为不知道每种维他命的数量，如果采用枚举，很难估计每种维他命的上界，而且时间复杂度很高，下面我们尝试用解方程的方法。设需要配制的维他命每种数量分别为x1,…xn,其中n=15,根据题意，可列出如下方程。用高斯消元法求解：这里，虽然x4可取任意值，显然，表示x4的数量与答案无关，因此x4=0,代入，可得x3=1,x2=1,x1=1,因此，原问题的解为（1，1，1，0）。0000011/210010/75/73/7104212100000212001053704212142400212004212110537084521633214212110523540020025010050300150150100502001005010050100502030502(3)7(2)2*(3)-(4))2((1))1(5)2()2()4()2()3(50)4(50)3(50)2(10)1(交换与40030020010020025010050150150100501005010050502030504321xxxx问题2：虫食算（NOIP2005）给出一个N(N=26)进制的加法算式，如下：ABCED+BDACEEBBAA其中有些是数字，有些是字母，字母可代表（1..N）中的任何一个数字，每个字母数字都不一样。你的任务是，对于给定的N进制加法算式，求出N个不同的字母分别导标的数字，使得该加法算式成立。输入数据保证有且仅有一组解。【数据规模】对于30%的数据，保证有N=10;对于50%的数据，保证有N=15;对于全部的数据，保证有N=26。分析：显然，我们很容易想到如下算法，枚举N个未知数，由于每个未知数的取数值范围为0~n-1,共n种，因此时间复杂度为nn,又因为每个未知数的数值都不相同，因此时间复杂度为n!，由于n可达到26，这样做显然比较高,因此需要寻找其他解法。仔细分析，上述思路的局限性在于没有充分利用加法等式这个条件。我们只要分析有没有进位，由于有N个变量因此可以列出N个方程，N个方程N个未知数，由于原问题有唯一解，因此方程应该有唯一解。如上例,可得如下方程组：D+E-A=x1E+C-A=x1+x2C+A-B=x2+x3B+D-B=x3+x4A+B-E=x4其中xi属于0、1，枚举每个xi，则时间复杂度为,2n-1，用LU分解方程的时间为n2,当然这个时间复杂度还是较高，可以利用一些已知条件，确定一些xi的值，如A+0=A，显然不可能有进位等等，加入这样一些剪枝条件即可。问题3：求最大异或值（SGU275）给你n个非负整数A1,A2,……,An集合，要你求出一个子集Ai1,Ai2,…,Aik（1=i1i2…ik=n），使得Ai1XORAi2XORAi3…XORAik的值最大。【数据规模】（1=n=100，Ai=1018）分析：设用“⊕”表示XOR操作。将问题进行转换成，求序列x1,x2,…,xn，使得：(x1*A1)⊕(x2*A2)…⊕(xn*An)最大，其中xi=0或1由于XOR操作时没有进位，所以我们把A1,…,An的每个二进制位分离出来考虑。设Ai=a(i,0)*20+a(i,1)*21+…+a(i,k)*2k可知，若答案的第k位是1，则a(1,k)*x1⊕a(2,k)*x2⊕…⊕a(n,k)*xn=1否则a(1,k)*x1⊕a(2,k)*x2⊕…⊕a(n,k)*xn=0由此，我们可以对答案进行枚举。首先设答案的最高为为1，得到一个方程，如果方程有解，则该位被确定为1，否则为0，继续枚举下面的每一位，直到每一位都确定为止。因此时间复杂度为log2(1018)*n2例如n=3，{Ai}={11，9，5}。首先我们把这三个数转成二进制，即：(11)10=(1011)2；(9)10=(1001)2；(5)10=(0101)2我们知道答案的最高位至多是第4位（也就是23位），我们设第4位为1，得到