线性方程组的直接法和迭代法

线性方程组的直接法

直接法就是经过有限步算术运算，无需迭代可直接求得方程组精确解的方法。

线性方程组迭代法

送代法就是用某种极限过程去逐步逼近线性方程组精确解的方法.该方法具有对计算机的

存贮单元需求少，程序设计简单、原始系数矩阵在计算过程中不变等优点，是求解大型稀

疏矩阵方程组的重要方法.迭代法不是用有限步运算求精确解，而是通过迭代产生近似解

逼近精确解.如Jacobi迭代、Gauss—Seidel迭代、SOR迭代法等。

1.线性方程组的直接法

直接法就是经过有限步算术运算，无需迭代可直接求得方程组精确解的方法。

1.1Cramer法则

Cramer法则用于判断具有n个未知数的n个线性方程的方程组解的情况。当方程组

的系数行列式不等于零时，方程组有解且解唯一。如果方程组无解或者有两个不同的解时，

那么系数行列式必为零。如果齐次线性方程组的系数行列式不等于零，那么没有非零解。

如果齐次线性方程组有非零解，那么系数行列式必为零。

定理1如果方程组中0=|司0°,那么Ax=〃有解，且解事唯一的，解为

%=力,工2=V%=方，D］是D中第i列换成向量b所得的行列式。

Cramer法则解n元方程组有两个前提条件:

1、未知数的个数等于方程的个数。

2、系数行列式不等于零

例1a取何值时，线性方程组

玉+/+玉=a

＜axl+x2+x3=l有唯一解。

X1+巧+aX3—1

111111

解：11=0\-a\-a

1\a00a-\

所以当4Wl时，方程组有唯一解。

定理2当齐次线性方程组Ax=0,Id。0时该方程组有唯一的零解。

定理3齐次线性方程组AE=O有非零解＜=＞同=0。

1.2Gauss消元法

Gauss消元法是线性代数中的一个算法，可用来为线性方程组求解，求出矩阵的秩,

以及求出可逆方阵的逆矩阵。当用于一个矩阵时，高斯消元法会产生出一个“行梯阵式”。

12.1用Gauss消元法为线性方程组求解

eg：Gauss消元法可用来找出以下方程组的解或其解的限制：

2x+y-z=8（Lj

*—3x-y+2z=_]]（乙2）

—2x+y+2z=-3（4）

这个算法的原理是：首先，要将乙以下的等式中的1消除，然后再将乙2以下的等

式中的y消除。这样可使整个方程组变成一个三角形似的格式。之后再将已得出的答案一

个个地代入已被简化的等式中的未知数中，就可求出其余的答案了。

在刚刚的例子中，我们将;。和L2相加，就可以将L?中的X消除了。然后再将LI

和乙3相加，就可以将乙3中的X消除。

方程组那么变为：

2x+y-z=8

11।

<—y+—Z=1

22

2y+z=5

现在将-4右和4相加，就可将4中的V消除，方程组变为：

2x+y-z=8

11।

<—y+—z=1

22

-z=1

这样就完成了整个算法的初步，一个三角形的格式（指:变量的格式而言，上例中的变

量各为3,2,1个）出现了。第二步，就是由尾至头地将的答案代入其他等式中的未知数。第

一个答案就是z=—1。然后直接带入，立即就可得出第二个答案：y=3和最后一个答

案x=2。这样，我们利用高斯消元法解决了这个方程组。

2.线性方程组迭代法

迭代法就是用某种极限过程去逐步逼近线性方程组精确解的方法.该方法具有对计算

机的存贮单元需求少，程序设计简单、原始系数矩阵在计算过程中不变等优点，是求解大

型稀疏矩阵方程组的重要方法.迭代法不是用有限步运算求精确解，而是通过迭代产生近

似解逼近精确解.如Jacobi迭代、Gauss—Seidel迭代、SOR迭代法等。

2.1Jacobi迭代法

-0-

an0

431Q320

L=

•••••••••

Clii_1,1Cln—1,2...0

Cln,1Cln,2Cln,n-10

aw

C122

Q33

D=

•••

Cln-1,-1

Cln.n

0Q12a\3...a\.n-1a\,n

0Q23...a2,n-\a2,n

0434...Q3,〃

U=

0

0

对于线性方程组Ar=b那么A=L+0+u,即将A分解为一个严格下三角矩阵、

一个对角阵和一个严格上三角矩阵之和，从而可写出Jacobi迭代格式的矩阵表示形式为:

X(^1)=-D|(£+。)科+£>(1%,其迭代矩阵J=+称为雅可比迭代

矩阵.

将线性方程组Ar=＞变为一个通解方程组x=&:+7,对其进行迭代式改写,

/+D=加"）+/,%=0,1,2..・.矩阵B为迭代矩阵

%1玉+anx2H------FaXnxn=by

a2\X\+a22X2"I。2〃%〃="2/八

<V)

〃〃西+凡2%2+3+4〃占="

由方程组（I）的第i个方程解出％（，=1,2,・・・〃），得到一个同解方程组:

玉=—(-di2x2-ai3x3-------aXnxn+/?,)

aw

工2二—(一。21%—%3工3--------a2nXn+4),〃、

%2(〃)

1

皿二一一。〃/〃一42%2…-%〃Z+2)

凡〃

构造相应的迭代公式

汇八"=’（-它/-。,〃产…+a）

T

取初始向量小）二（靖），芯°’，…燎）），利用（III）反复迭代可以得到一个向量序列

｛九（"）｝,利用此迭代格式求解方程组的解法称为Jacobi迭代法。

用Jacobi迭代求解以下方程组

4%+3X2=24

石+

<33X2-x3=30

—

x2+4&=-24

输入

A=[430;33-l;0-14]；

b=[24;30;-24]；

[x,k,index]=Jacobi(A,b,le-5,100)

输出:

x=

-2.9998

11.9987

-3.0001

k=

100

index二

0

所以解为：%)=-2.9998,x2=l1.9987,x3=-3.0001

2.2Gauss-Seide迭代

假设L、U、D为上述的L、U、D。那么Gauss—Seidel迭代法的矩阵表示为：

Xr(A+1)-Un-1{(-LXrU+1)_U［茂Xk)+力叫)现将xY(&+D显示化由

(£>+L)W+D=-&(幻+」得.X(X+1)=-(D+1)-1Ux(k)+(£>+Lyxb令

G=-(。+L),g=(。+L)-'b,那么得：V=G”+g,此即为Gauss—Seidel

迭代法的矩阵表示形式，G称为迭代阵。

由Jacobi迭代法中，每一次的迭代只用到前一次的迭代值，假设每一次迭代充分利

；(八1)(2+1)(八1)

用当前最新的迭代值，即在计算第"个分量入’时，用最新分量〜，42•••

("D丫(〃)y⑹丫*)

川代替旧分量1,看…人知,就得到所谓解方程组的Gauss-Seidel迭

(o)_/(0)(0)(0)xT

代法。其迭代格式为Xr丐r''2'…，Zr)(初始向量)，

1I

吏）

一气一(A:=0,1,2,--•；i=0,1,2,--n)

丁2

或者写为

+1)-x;)+Axz(k=k=0,1,2,•••；i=0,1,2,•••/?)

x1+i)=^_(,乙—z%x产)—£%w)

a

、iij=\j=i+l

用Gauss-Seide迭代求解以下方程组

4%+3X2=24

否+

v33X2-x3=30

—

x9+4%3=—24

输入

A=[430;33-l;0-14]；

b=[24;30;-24]；

x0=[0;0;0]；

[v,sN,vChain]=gaussSeidel(A,b,xO,0.00001,11)

输出：

v=

0.6169

11.1962

-4.2056

sN=

11

vChain二

6.000010.0000-6.0000

-1.50002.0000-3.5000

4.500010.3333-5.5000

-1.75003.6667-3.4167

3.250010.6111-5.0833

-1.95835.0556-3.3472

2.208310.8426-4.7361

-2.13196.2130-3.2894

1.340311.0355-4.4468

-2.27667.1775-3.2411

0.616911.1962-4.2056

000

000

000

000

所以结果为:为二0.6169,%2=11.1962,*3=4.2056。

2.3SOR迭代

在很多情况下，Jacobi和Gauss—Seidel法收敛速度较慢，S0R法是Gauss—Seidel

法的一种加速方法，需要施加适宜的松弛因子。

假设L、U、D为上述的L、I.KD。SOR迭代公式为=⑻+/,其中

[

Lw=(D-coL)-((1一。)。+M),f=co{D-。£)一名初w[1,2]。

用SOR迭代求解以下方程组。

0.76%,-0.0lx2-0.14^3-0.16X4=0.68

-0.0Lv,+().88%2.003/+0.06X4=1.18

—

-0.14%1—0.03X2+1.01%30.12X4=0.12

-0.16%+0.06X2-0.12X3+0.72X4=0.74

取初始点x(0)=(0,0,0,0)丁松弛因子g=1.05,精度要求£=1(T6。

输入

A=[0.76-0.01-0.14-0.16；-0.010.88-0.030.06；

-0.14-0.031.01-0.12；-0.160.06-0.120.72];

B-[0.681.180.120.72];

xo-[o；o；o；o]；

W=1.05

[x,n]=SOR(A,b,xO,w)

输出

x=

1.2715

1.2844

0.4858

1.2843

n=

7

有上述结果得出：经过7次迭代后，该方程组的解为

xl=1.2715,x2=1.2844,x3=0.4858,x4=1.2843

2.4迭代法收敛

引理：设A为n阶方阵，那么limA"二°的充要条件为夕(A)<1(夕(A)为普半径)。

.XT8

证明：必要性假设limA"=0

X—>8

由矩阵收敛的定义知阿犷|=0有因为夕(A)<|川所以。<夕⑷KMil

由夹逼定理可得出1加[2(4)『=0,又因为"(屋)=[夕缶)「所以由lim[p(A)『二0

可得出夕(A)vl

充分性：假设夕(4)<1,取"一；()〉0,存在矩阵范数||||,使得

|同区夕(A)+£=l—f)<1那么有:limpid=0,

由算子范数相容性可得：041AAi引M|<•<|

由夹逼定理可得出limA4二0。

定理1：迭代公式x"句)=Bx⑹+/,Z=0,1,2.…收敛的充分必要条件是迭代矩阵B的

谱半径夕(8)<1

证明：必要性

设存在n维向量X*,使得limx"'=x*,那么X*满足工*二①人+/

K—>8

由迭代公式得出

xk-x

=Bx(J)+f_Bx*_f

=8(X"TT)

…

=Bk(xw-x)

所以limBk(x(0)-x*)=lim(xA-x*)=0

Xf8\fXTOO\

因为”为任意n维向量，因此上式成立必须则加=0

由引理可得出夕(B)vl。

充分性：假设夕(8)vl,那么4=1不是B的特征值，因而有|/一可。0,于是对任意

的n维向量f,方程组(/-6)%=/有唯一解，记为即：x*=Bf+/

目更S"=0.又因为

X-X

=Bx(k-1)+f-Bx-f

=B(­)

"(

07

所以，对任意初始向量公°)都有lim(f-/)=1而公(。°)-/)=0

即迭代公式=Bx"k)”,k=0,1,2….收敛。

注解：代矩阵B的谱半径"①)=max九(B)这里的旗硝是矩阵8的特征值。

B<1v（o）f

定理2：假设迭代矩阵的一种范数，那么对任意的初始向量工和任意JO迭

丫"+1）囱严+，均收敛。

代格式工

迭代法收敛与否只决定于迭代矩阵的普半径，于初始向量及右端项无关。对于同一方

程组，由于不同的迭代法迭代矩阵不同，可能出现有的方法收敛，有的发散的情形。

M||8=maxZ同Mil।=max£|俏

注解：三种常用矩阵范数为：‘六।

是的最大特征值）。

由上述两个定理可得：Jacobi迭代收敛的充分必要条件是夕（B）<1,收敛的充分条件是任

D<1

一种范数,Gauss—Seidel迭代收敛的充分必要条件是Q（B）<1,收敛的充分条

件是任-种范数怛I"

定理3：对角占优线性方程组Av=b的Jacobi迭代格式"2）=Bx（k）+/和Gauss

-Seidel迭代格式均"""=G""+g收敛。

注解：n阶方阵A,如果其主对角线元素的绝对值大于同行其他元素绝对值之和，那么称A

是对角占优的.

虽然定理1是充分必要条件，可是需要计算迭代矩阵B的特征值，我们在线性代数上

看到一个大型矩阵的特征值是非常难求的，计算量是很大的。定理2和定理3的计算量相

对定理1来说是相当小的，因为它们只是简单的加减乘除；但是他们是充分条件，不满足

时需要再改用定理I来判断。所以收敛的判断可先采用定理2和定理3,不行再选拦定理1。

预处理是用来加速迭代法收敛的一个重要手段。值得注意的是，经典的求解线性方程

组的迭代法也都能够看作是求解采用不同的因子预处理之后得到的线性方程组的迭代法。

换句话来说，原线性方程组的松弛迭代法等价于预处理之后的方程组的定点迭代法。谱条

件数是反映预处理因子性态是否良好的一个有效指标。在估计特征值和条件数的界的研究

领域，虽然已经有了很多的研究成果，但是