您的当前位置:首页正文

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

2021-06-18 来源:步旅网


线性方程组的几种解法

线性方程组形式如下:

常记为矩阵形式

其中

一、高斯消元法

高斯(Gauss)消元法的基本思想是:通过一系列的加减消元运算,也就是代数中的加减消去法,将方程组化为上三角矩阵;然后,再逐一回代求解出x向量。现举例说明如下:

(一)消元过程

第一步:将(1)/3使x1的系数化为1 得

(1)

再将(2)、(3)式中x1的系数都化为零,即由(2)-2×(1)得

x1

由(3)-4×(1)得

(1)

21x2 x32......(1)(1)3324x2x30......(2)(1)33

(1)

1410x2x36......(3)(1) 33第二步:将(2)除以2/3,使x2系数化为1,得

x22x30......(2)(2)

再将(3)式中x2系数化为零,即 由(3)-(-14/3)*(2) ,得

(1)

(2)

(1)

18x3 6......(3)(2)3第三步:将(3)除以18/3,使x3系数化为1,得

(2)

x3 1......(3)(3)经消元后,得到如下三角代数方程组:

(二)回代过程

由(3)得 x3=1, 将x3代入(2)得x2=-2, 将x2 、x3代入(1)得x2=1 所以,本题解为[x]=[1,2,-1] (三)、用矩阵演示进行消元过程

第一步: 先将方程写成增广矩阵的形式

T

(1)

(2)

(3)

第二步:然后对矩阵进行初等行变换

初等行变换包含如下操作

(1) 将某行同乘或同除一个非零实数

(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) ≠ 0

xn = 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,iD1= a11(1)

D2= a11(1) a22(2) ……

Dk= a11(1) a22(2)…ak,k(k)

有递推公式

D1= a11(1) Di= Di-1 aii(i) (i=2,3,…,n)

所以有

定理:高斯消元法消元过程能进行到底的充要条件是系数阵A的1到n-1阶的顺序主子式不为0。 (六)选主消元

因为在高斯消元的过程中,要做乘法和除法运算,因此会产生误差。当| akk(k)|<<1,此时用它作除数。会导致其他元素数量级严重增加,带来误差扩散,使结果严重失真。

例如:

0.00001x1+x2 = 1.00001

2x1+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,且r二、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,…,n ai1 = li1u11 , i=1,2,…,n

推出

u1j = a1j, j=1,2,…,n li1 = ai1/u11, i=1,2,…,n

这样就定出了U的第一行元素和L的第一列元素。

设已定出了U的前k-1行和L的前k-1列,现在确定U的第k行和L的第k列。由矩阵乘法:

akjlkrurjr1

当r>k时,lkr=0, 且lkk=1,因为

nakjukjl krurjr1n所以,

ukjakjlkrurjr1njk,k1,...,n

同理可推出计算L的第k列的公式:

lik(aiklkrurj)/ukkr1nik,k1,...,n因此得到如下算法——杜利特(Doolittle)算法: (1) 将矩阵分解为A=LU,对k=1,2,…,n

njk,k1,...,nukjakjlkrurjr1n公式1:ik,k1,...,n lik(aiklkrurj)/ukkr1lkk1

(2) 解Ly=b

公式2:ykbklkryr k1,2,...,nr1k1(3) 解Ux=y

公式3:xk(ykrk1unkrrx)/ukkkn,n1,...,1例:求解方程组

 2 4 2 6 x192 9 6 5x223 2 6 9 18x22

36 15 1 40x474

解:

由公式1得出

 1 1 2 L  ,1 2 1 3 3 2 1于是化为两个方程组

2 4 2 6 1 2 3  U  3 6  1  1 y191 y2232 1 2 1 y3223 3 2 1y4742 4 2 6 x1y11 2 3 x2y2  3 6 x3y3  1x4y4

利用公式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)。 数据输出:

第一行:输出能否配制,若能输出Yes,否则输出No

第二行:若能配制,则输出G个整数,其中第i个整数Gi,表示第i种维他命所取的数量,若有多种配置方案,输出一种即可。若不能配制,则第二行为空。

样例:

input.txt 4

100 200 300 400 4

50 50 50 50 30 100 100 100 20 50 150 250 50 100 150 200 output.txt Yes

1 1 1 0

分析:因为不知道每种维他命的数量,如果采用枚举,很难估计每种维他命的上界,而且时间复杂度很高,下面我们尝试用解方程的方法。

设需要配制的维他命每种数量分别为x1,…xn,其中n<=15,根据题意,可列出如下方程。

用高斯消元法求解:

这里,虽然x4可取任意值,显然,表示x4的数量与答案无关,因此x4=0,代入,可得x3=1, x2=1, x1=1,因此,原问题的解为(1,1,1,0)。

50 30 20 50 x1100x50 100 50 100 200250 100 150 150 x300350 100 250 200 x4004

100(1)105 3 2 5 1050 30 20 50 0 7 3 5 10(2)50(3)(2) (3)50(4)(2)(1)与(2)交换50 100 50 100 2001 2 1 2 41 2 1 2 4(4)50(2)5(1)(4)-(3)*2 50 100 150 150 3001 2 3 3 60 0 2 1 2  50 100 250 200 4001 2 5 4 80 0 4 2 4 1 2 41 2 41 2 1 2 (2)71 3/7 5/7 10/7 0 7 3 5 10(3)20 0 0 2 0 0 1 21 1/2 1 0 0 0 0 0 00 0 0 0 

问题2:虫食算(NOIP2005)

给出一个N (N<=26)进制的加法算式,如下:

ABCED

+ BDACE EBBAA

其中有些是数字,有些是字母,字母可代表(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=x1 E+C-A=x1+x2 C+A-B=x2+x3 B+D-B=x3+x4 A+B-E=x4

其中xi属于0、1,枚举每个xi,则时间复杂度为,2,用LU分解方程的时间为n,当然这个时间复杂度还是较高,可以利用一些已知条件,确定一些xi的值,如A+0=A,显然不可能有进位等等,加入这样一些剪枝条件即可。

n-1

2

问题3: 求最大异或值(SGU275)

给你n个非负整数A1,A2,……,An集合,要你求出一个子集Ai1,Ai2,…,Aik

(1<=i1【数据规模】

(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,得到方程: x1⊕ x2=1 (1)

然后枚举第3位,设为1,得到方程: x3=1 (2)

然后枚举第2位,设为1,得到方程: x1=1 (3)

此时仍然可以将(1)(2)(3)联立而不发生矛盾,继续枚举最后一位,先设为1,得到方程:

x1⊕x2⊕x3=1 (4)

用(1)(2)(3)的主元对(4)进行消元,得到:

0=1 (4)(1) 矛盾!可知(4)无法和前三个方程联立。

所以最低位不能为1,只能为0。这样我们就得到了答案(1110)2=(14)10

问题4: Puzzle(SGU260)

有N个格子,每个格子可能是黑色或者白色。目前有N种操作方式,第i种操作可以将,Ai,1,Ai,2,......,Ai,ki这Ki个格子的颜色同时改变。(从黑到白,或者从白到黑)现在给出N个格子的初始状态,与这N种操作。请你判断是不是可以通过N种操作,将所有格子变成同一种颜色。如果可以请输出一种方案。

【数据规模】

(1<=n<=200)

分析:

通过一定的分析,就可以知道本题可以表示成一个N元逻辑方程。首先可以明确的是同一个操作使用超过两次是没有意义的。因为一个操作被使用了两次相当于什么都没有改变,于是可以:

设Xi表示第i种操作是否使用。如果使用则值为真,不使用则为假。

我们先判断是不是可以将所有的格子的颜色都变成黑,变成白则可以类似处理。

对于每个格子i,设可以将i的格子颜色改变的操作有C个,它们为B1,B2,…,BC。若i的初始颜色为黑,即我们不能让i颜色改变,所以有:

XB1XB2XB3......XBCFalse

若i的初始颜色为白,则有:

XB1XB2XB3......XBCTrue

总共有N个格子,即N个方程。有N种操作,即N个未知数。原问题就变成了判断N

元Xor方程组有没有解的问题了,可以在O(N)的时间复杂度内用高斯消元的方法解决。 问题5:Nikifor(Ural1041)

现在有M个N维向量P1..Pm,你需要从中“购买”N个向量,它们是线性无关的。同时每个向量有一个价格,在选出N个向量的同时,要求价格和最小。

所谓N个向量Q1..Qn线性无关,即对于其中任意N-1个向量(假设为Q1..Qn),方程:

3

Q1X1+Q2X2+…+Qn-1Xn-1 = Qn

没有实数解(X1,X2,…,Xn-1)。

【数据规模】 M<=2000 N<=50

分析:

本题我们采用贪心的方法。首先将所有向量按照价格从小到大排序。

之后从价格小的向量开始依次检查,倘若已经购买了的向量无法表示出当前检查的向量,则此向量也需要购买,否则就不需要购买。若发现已经购买了n个向量,就得到一组解,若检查完所有向量之后依然没有n个向量,就表示无解。

贪心正确性的证明:

首先我们需要证明购买的若干个向量是线性无关的。

考虑用数学归纳法,假设购买的前t个向量P1..Pt是线性无关的,现在发现向量Q也需要购买,我们证明P1..Pt,Q也是线性无关的:

由于Q需要购买,则方程P1X1+P2X2+…+PtXt = Q无解。

假设结论不成立,即存在(Y1,Y2,..,Yt)使得P1Y1+P2Y2+..+Pt-1Yt-1+QYt = Pt, 那么若Yt=0,即P1Y1+P2Y2+..+Pt-1Yt-1 = Pt,则与P1..Pt是线性无关矛盾;

若Yt不为0,于是有P1(Y1/Yt)+P2(Y2/Yt)+..+Pt-1(Yt-1/Yt)-Pt(1/Yt) = Q,则与“方程P1X1+P2X2+…+PtXt = Q无解”矛盾。

因此P1..Pt,Q也是线性无关的。

因此前t+1个向量也是线性无关,于是命题得证。

此外还有一个问题,在贪心过程中每次遇到需要购买的向量,我们就马上购买,但会不会造成之后无解呢?显然不会,下面我们再来证明一个结论:

设前t次购买的向量为P1..Pt,第t+1次购买的向量为Pt+1,那么若存在一组可行解(P1,P2,…,Pt,Q1,…,Qs),则一定会存在一组解(P1,P2,…,Pt+1,W1,…,Wk)。 证明:(P1,P2,…,Pt,Q1,…,Qs)是可行解,则它们一定可以表示所有的向量。

设P1X1+P2X2+…+PtXt+Q1Y1+…+QsYs = Pt+1,那么Y1..Ys不可能全为0。若全为0,则

方程简化为P1X1+P2X2+…+PtXt = Pt+1,但P1..Pt+1是线性无关的,因此这是不可能的。 不妨设Ys不为0,那么我们只须将Qs替换为Pt+1,则(P1,P2,…,Pt+1,Q1,…Qs-1)同样也为可行解。

因此结论得到证明。 每次判断一个向量需不需要购买,实际上就是判断一个方程组有没有实数解,整个算法

的时间复杂度为O(MN2)。

因篇幅问题不能全部显示,请点此查看更多更全内容