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

线性方程组的直接法

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

线性方程组迭代法

迭代法就是用某种极限过程去逐步逼近线性方程组精确解的方法.该方法具有对计算机的存贮单元需求少,程序设计简单、原始系数矩阵在计算过程中不变等优点,是求解大型稀疏矩阵方程组的重要方法.迭代法不是用有限步运算求精确解,而是通过迭代产生近似解逼近精确解.如Jacobi迭代、Gauss— Seidel迭代、SOR迭代法等。

1. 线性方程组的直接法

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

1.1 Cramer法则

Cramer法则用于判断具有n个未知数的n个线性方程的方程组解的情况。当方程组的系数行列式不等于零时,方程组有解且解唯一。如果方程组无解或者有两个不同的解时,则系数行列式必为零。如果齐次线性方程组的系数行列式不等于零,则没有非零解。如果齐次线性方程组有非零解,则系数行列式必为零。

定理1如果方程组Axb中D

解为x1

A0,xb则A

有解,且解事唯一的,

DD1D

,x22,...xnn,Di是D中第i列换成向量b所得的行列式。 DDD

Cramer法则解n元方程组有两个前提条件: 1、未知数的个数等于方程的个数。 2、系数行列式不等于零 例1 a取何值时,线性方程组

x1x2x3a

ax1x2x31有唯一解。 xxax1

231

111

1

1

1

解:Aa1101a1a(a1)2 11a00a1所以当a

1时,方程组有唯一解。

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

定理3齐次线性方程组Ax0有非零解A0。 1.2 Gauss消元法

Gauss消元法是线性代数中的一个算法,可用来为线性方程组求解,求出矩阵的秩,以及求出可逆方阵的逆矩阵。当用于一个矩阵时,高斯消元法会产生出一个“行梯阵式”。

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

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

2xyz8L1

3xy2z11L2 2xy2z3L3

这个算法的原理是:首先,要将L1以下的等式中的

x消除,然后再将L2

以下的等式中的y消除。这样可使整个方程组变成一个三角形似的格式。之后再将已得出的答案一个个地代入已被简化的等式中的未知数中,就可求出其余的答案了。

3

在刚才的例子中,我们将L1和L2相加,就可以将L2中的x消除了。

2

然后再将1和

L

L3相加,就可以将L3中的x消除。

方程组则变为:

2xyz811

yz1 222yz5

现在将4L2和L3相加,就可将L3中的

y消除,方程组变为:

2xyz811

yz1

22

z1

这样就完成了整个算法的初步,一个三角形的格式(指:变量的格式而言,上例中的变量各为3,2,1个)出现了。第二步,就是由尾至头地将已知的答案代入其他等式中的未知数。第一个答案就是得出第二个答案:

z1。然后直接带入,立即就可

y3和最后一个答案x2。这样,我们利用高斯消元法

解决了这个方程组。

2. 线性方程组迭代法

迭代法就是用某种极限过程去逐步逼近线性方程组精确解的方法.该方法具有对计算机的存贮单元需求少,程序设计简单、原始系数矩阵在计算过程中不变等优点,是求解大型稀疏矩阵方程组的重要方法.迭代法不是用有限步运算求精确解,而是通过迭代产生近似解逼近精确解.如Jacobi迭代、Gauss— Seidel迭代、SOR迭代法等。

2.1 Jacobi迭代法

0a210a31a320L

............

an1,1an1,2...0

an,2an,n10an,1

a11a22a33

D

...

an1,n1

an,n

0a12a13...a1.n1a1,n0a23...a2,n1a2,n0a34...a3,nU

...

0

0

对于线性方程组Ax

b则ALDU,即将A分解为一个严格下三

角矩阵、一个对角阵和一个严格上三角矩阵之和,从而可写出Jacobi迭代格式

(k1)1(k)(1)

xD(LU)xDb,其迭代矩阵

的矩阵表示形式为:

JD1(LU))称为雅可比迭代矩阵.

将线性方程组Ax

b变为一个通解方程组xBxf

,对其进行迭代式

(k1)(k)

xBxf,k0,1,2....矩阵B为迭代矩阵 改写,

a11x1a12x2a1nxnb1axaxaxb2112222nn2

I



an1x1an2x2annxnbn

由方程组(I)的第i个方程解出x1(i1,2,n),得到一个同解方程组:

1

x1aa12x2a13x3a1nxnb111

1

a21x2a23x3a2nxnb2x2a22(II) 

1

xnaan1xnan2x2annxnbnnn

构造相应的迭代公式

(k1)1(k)(k)(k)xaxaxaxb111221331nna11

1(k1)(k)(k)(k)

xaxaxaxb222122332nn

a22(III)



1(k1)(k)(k)(k)

xaxaxaxbnn1nn22nnnn

ann

取初始向量x

(k)

(0)

x,x,x

(0)

1

(0)2(0)Tn

,利用(III)反复迭代可以得到一个向

量序列x,利用此迭代格式求解方程组的解法称为Jacobi迭代法。

用Jacobi迭代求解下列方程组

4x13x224

3x13x2x330 x4x24

23

输入

A=[4 3 0;3 3 -1;0 -1 4]; b=[24;30;-24];

[x, k, index]=Jacobi(A, b, 1e-5, 100) 输出: x = -2.9998 11.9987 -3.0001 k = 100 index = 0

所以解为:x1=-2.9998, x2=11.9987, x3=-3.0001

2.2 Gauss-Seide迭代

若L、 U、 D为上述的L、 U、 D。则Gauss—Seidel迭代法的矩阵表示

(k1)1(k1)(k)(k1)xD(LxUxb)x为:,现将显示化由

(DL)x(k1)Ux(k)b得:x(k1)(DL)1Ux(k)(DL)1b,令

(k1)(k)G(DL)1,g(DL)1b,xGxg,则得:此即为Gauss

—Seidel迭代法的矩阵表示形式,G称为迭代阵。

由Jacobi迭代法中,每一次的迭代只用到前一次的迭代值,若每一次迭代充分利用当前最新的迭代值,即在计算第

i个分量xi

x

(k)

(k1)

时,用最新分量

x1

(k1)

x,2

(k1)

xi-1

(k1)

代替旧分量1

x2

(k)

xi-1

(k)

,就得到

所谓解方程组的Gauss-Seidel迭代法。其迭代格式为

(0)(0)(0)Tx(0)(x1,x2,,xn) (初始向量),

x

(i1)

i

i1i1

1(k1)

(biaijxjaijx(jk))aiij1ji1

(k0,1,2,;i0,1,2,n)

或者写为

xi(k1)xi(k)xi(kk0,1,2,;i0,1,2,n)

i1i1

1(i1)(k1)xi(biaijxjaijx(jk))

aiij1ji1

1(k1)(k)(k)(k)

xaxaxaxb111221331nna11

1(k1)(k1)(k)(k)

xaxaxaxb222112332nna22



(IV)

1xi(k1)ai1x1(k1)ai2x2(k1)ai,i1xi1(k1)ai,i1xi1(k)ainxn(k)biaii1xn(k1)an1xn(k1)an2x2(k1)annxn(k1)bnann

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

4x13x224

3x13x2x330 x4x24

23

输入

A=[4 3 0;3 3 -1;0 -1 4]; b=[24;30;-24]; x0=[0;0;0];

[v,sN,vChain]=gaussSeidel(A,b,x0,0.00001,11) 输出: v = 0.6169 11.1962 -4.2056 sN = 11 vChain =

6.0000 10.0000 -6.0000 -1.5000 2.0000 -3.5000 4.5000 10.3333 -5.5000 -1.7500 3.6667 -3.4167 3.2500 10.6111 -5.0833 -1.9583 5.0556 -3.3472 2.2083 10.8426 -4.7361 -2.1319 6.2130 -3.2894 1.3403 11.0355 -4.4468 -2.2766 7.1775 -3.2411 0.6169 11.1962 -4.2056 0 0 0 0 0 0 0 0 0 0 0 0 所以结果为:

x1= 0.6169, x2=11.1962, x3=-4.2056 。

2.3 SOR迭代

在很多情况下,Jacobi和Gauss—Seidel法收敛速度较慢,SOR法是Gauss—Seidel法的一种加速方法,需要施加合适的松弛因子。

若L、 U、 D为上述的L、 U、 D 。SOR迭代公式为X其中

(k1)

LwX(k)f,

Lw(DL)1((1)DU),f(DL)1b,[1,2]。

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

0.76x10.01x20.14x30.16x40.680.01x0.88x0.03x0.06x1.181234 0.14x0.03x1.01x0.12x0.1212340.16x10.06x20.12x30.72x40.74

取初始点x输入

A=[0.76 -0.01 -0.14 -0.16;-0.01 0.88 -0.03 0.06; -0.14 -0.03 1.01 -0.12;-0.16 0.06 -0.12 0.72]; B=[0.68 1.18 0.12 0.72]; X0=[0;0;0;0]; W=1.05

[x,n]=SOR(A,b,x0,w) 输出 x=

1.2715 1.2844 0.4858 1.2843 n=

7

有上述结果得出:经过7次迭代后,该方程组的解为 x1=1.2715, x2=1.2844, x3=0.4858, x4=1.2843

(0)

(0,0,0,0)T松弛因子1.05,精度要求106。

2.4 迭代法收敛

k

limA0的充要条件为(A)1((A)为引理:设A为n阶方阵,则x

普半径)。

k

limA0

证明:必要性若

x

k

limA0有因为(A)A所以0(A)A 由矩阵收敛的定义知x

由夹逼定理可得出

lim[(A)]k0,又因为(Ak)[(A)]k所以由x

lim[A(k)]可得出0(A)1 x

充分性:若

(A)1,取

1(A)

0,存在矩阵范

数2

,使得

k1(A)

A(A)1则有:limA0,

x2

由算子范数相容性可得:0AA

k

k1

AA

k

A由夹逼定理可得出limx

定理1: 迭代公式x

(k1)

k

0。

Bx(k)f,k0,1,2....收敛的充分必要条件是迭代

矩阵B的谱半径(B)1 证明:必要性

设存在n维向量x,使得limx由迭代公式得出

xkx,则x满足xBxkf

xkx

Bx(k1)fBxfBx(k1)xB

2

Bk

x

x

(k2)(0)

x

x

B所以limx

因为

k

x

(0)

xlimxkx0

x

x

(0)

k

limB0 为任意n维向量,因此上式成立必须

x

由引理可得出(B)1。 充分性:若(B)1,则

1不是B的特征值,因而有IB0,于是对

xxBxf 有唯一解,记为。即:

任意的n维向量f,方程组(IB)xf

k

limB0,又因为 且x

xkx

Bx(k1)fBxfBx(k1)xB2x(k2)xBkx(0)x

(0)kk(0)

x所以,对任意初始向量都有limxxlimBxx0

xx

即迭代公式x

(k1)

Bx(k)f,k0,1,2....收敛。

1in

注解: 代矩阵B的谱半径(B)maxi(B)这里的i(B)是矩阵B的特征值。

定理2:若迭代矩阵的一种范数

(k1)(k)

xBxf迭代格式

B1

(0)fx,则对任意的初始向量和任意

均收敛。

迭代法收敛与否只决定于迭代矩阵的普半径,于初始向量及右端项无关。对于同一方程组,由于不同的迭代法迭代矩阵不同,可能出现有的方法收敛,有的发散的情形。

n

n

A

注解:三种常用矩阵范数为:

maxaij

i

j1

A1maxaij

j

i1

A2T(1是AA的最大特征值)。

由上述两个定理可得:Jacobi迭代收敛的充分必要条件是(B)1,收敛的充分条件是任一种范数B1,Gauss—Seidel迭代收敛的充分必要条件是(B)1,收敛的充分条件是任一种范数B1。

x定理3:对角占优线性方程组Axb的Jacobi迭代格式

(k1)(k)xGxg收敛。 Gauss—Seidel迭代格式均(k1)Bx(k)f和

注解:n阶方阵A,如果其主对角线元素的绝对值大于同行其他元素绝对值之和,则称A是对角占优的.

虽然定理1是充分必要条件,可是需要计算迭代矩阵B的特征值,我们在线性代数上看到一个大型矩阵的特征值是非常难求的,计算量是很大的。定理2和定理3的计算量相对定理1来说是相当小的,因为它们只是简单的加减乘除;但是他们是充分条件,不满足时需要再改用定理1来判断。所以收敛的判断可先采用定理2和定理3,不行再选择定理1。

预处理是用来加速迭代法收敛的一个重要手段。值得注意的是,经典的求解线性方程组的迭代法也都能够看作是求解采用不同的因子预处理之后得到的线性方程组的迭代法。换句话来说,原线性方程组的松弛迭代法等价于预处理之后的方程组的定点迭代法。谱条件数是反映预处理因子性态是否良好的一个有效指标。在估计特征值和条件数的界的研究领域,虽然已经有了很多的研究成果,但是支持理论还是一个全新的概念。支撑理论是一个用于分析预处理方程组的最大(或最小)特征值和条件数的代数架构,它最初产生于对称正定的线性方程组(7)

2.5 迭代法收敛的应用

用Jacobi迭代,Gauss—Seidel迭代两种方法求解下列方程组是否收敛。 x12x22x31x1x2x32 2x2xx3231

解:因为迭代法收敛与否只决定于迭代矩阵的普半径。所以求普半径是否小于1.

122100,010A111D

221001

000022001L100U, 220000

Jacobi迭代矩阵BD1(LU)

022BD1(LU)101 220

其特征方程

所以1221302IB12 230,所以(B)01所以Jacobi迭代法收敛。

1Gauss—Seidel迭代矩阵B(DL)

022B(DL)1023 002

所以特征值为1

代法发散。 2023(2)20 IB02其特征方程20,232所以(B)21所以Gauss—Seidel迭

上述例子说明对于同一方程组,由于不同的迭代法迭代矩阵不同,可能出现有的方法收敛,有的发散的情形。

线性方程组的直接法

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

线性方程组迭代法

迭代法就是用某种极限过程去逐步逼近线性方程组精确解的方法.该方法具有对计算机的存贮单元需求少,程序设计简单、原始系数矩阵在计算过程中不变等优点,是求解大型稀疏矩阵方程组的重要方法.迭代法不是用有限步运算求精确解,而是通过迭代产生近似解逼近精确解.如Jacobi迭代、Gauss— Seidel迭代、SOR迭代法等。

1. 线性方程组的直接法

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

1.1 Cramer法则

Cramer法则用于判断具有n个未知数的n个线性方程的方程组解的情况。当方程组的系数行列式不等于零时,方程组有解且解唯一。如果方程组无解或者有两个不同的解时,则系数行列式必为零。如果齐次线性方程组的系数行列式不等于零,则没有非零解。如果齐次线性方程组有非零解,则系数行列式必为零。

定理1如果方程组Axb中D

解为x1

A0,xb则A

有解,且解事唯一的,

DD1D

,x22,...xnn,Di是D中第i列换成向量b所得的行列式。 DDD

Cramer法则解n元方程组有两个前提条件: 1、未知数的个数等于方程的个数。 2、系数行列式不等于零 例1 a取何值时,线性方程组

x1x2x3a

ax1x2x31有唯一解。 xxax1

231

111

1

1

1

解:Aa1101a1a(a1)2 11a00a1所以当a

1时,方程组有唯一解。

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

定理3齐次线性方程组Ax0有非零解A0。 1.2 Gauss消元法

Gauss消元法是线性代数中的一个算法,可用来为线性方程组求解,求出矩阵的秩,以及求出可逆方阵的逆矩阵。当用于一个矩阵时,高斯消元法会产生出一个“行梯阵式”。

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

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

2xyz8L1

3xy2z11L2 2xy2z3L3

这个算法的原理是:首先,要将L1以下的等式中的

x消除,然后再将L2

以下的等式中的y消除。这样可使整个方程组变成一个三角形似的格式。之后再将已得出的答案一个个地代入已被简化的等式中的未知数中,就可求出其余的答案了。

3

在刚才的例子中,我们将L1和L2相加,就可以将L2中的x消除了。

2

然后再将1和

L

L3相加,就可以将L3中的x消除。

方程组则变为:

2xyz811

yz1 222yz5

现在将4L2和L3相加,就可将L3中的

y消除,方程组变为:

2xyz811

yz1

22

z1

这样就完成了整个算法的初步,一个三角形的格式(指:变量的格式而言,上例中的变量各为3,2,1个)出现了。第二步,就是由尾至头地将已知的答案代入其他等式中的未知数。第一个答案就是得出第二个答案:

z1。然后直接带入,立即就可

y3和最后一个答案x2。这样,我们利用高斯消元法

解决了这个方程组。

2. 线性方程组迭代法

迭代法就是用某种极限过程去逐步逼近线性方程组精确解的方法.该方法具有对计算机的存贮单元需求少,程序设计简单、原始系数矩阵在计算过程中不变等优点,是求解大型稀疏矩阵方程组的重要方法.迭代法不是用有限步运算求精确解,而是通过迭代产生近似解逼近精确解.如Jacobi迭代、Gauss— Seidel迭代、SOR迭代法等。

2.1 Jacobi迭代法

0a210a31a320L

............

an1,1an1,2...0

an,2an,n10an,1

a11a22a33

D

...

an1,n1

an,n

0a12a13...a1.n1a1,n0a23...a2,n1a2,n0a34...a3,nU

...

0

0

对于线性方程组Ax

b则ALDU,即将A分解为一个严格下三

角矩阵、一个对角阵和一个严格上三角矩阵之和,从而可写出Jacobi迭代格式

(k1)1(k)(1)

xD(LU)xDb,其迭代矩阵

的矩阵表示形式为:

JD1(LU))称为雅可比迭代矩阵.

将线性方程组Ax

b变为一个通解方程组xBxf

,对其进行迭代式

(k1)(k)

xBxf,k0,1,2....矩阵B为迭代矩阵 改写,

a11x1a12x2a1nxnb1axaxaxb2112222nn2

I



an1x1an2x2annxnbn

由方程组(I)的第i个方程解出x1(i1,2,n),得到一个同解方程组:

1

x1aa12x2a13x3a1nxnb111

1

a21x2a23x3a2nxnb2x2a22(II) 

1

xnaan1xnan2x2annxnbnnn

构造相应的迭代公式

(k1)1(k)(k)(k)xaxaxaxb111221331nna11

1(k1)(k)(k)(k)

xaxaxaxb222122332nn

a22(III)



1(k1)(k)(k)(k)

xaxaxaxbnn1nn22nnnn

ann

取初始向量x

(k)

(0)

x,x,x

(0)

1

(0)2(0)Tn

,利用(III)反复迭代可以得到一个向

量序列x,利用此迭代格式求解方程组的解法称为Jacobi迭代法。

用Jacobi迭代求解下列方程组

4x13x224

3x13x2x330 x4x24

23

输入

A=[4 3 0;3 3 -1;0 -1 4]; b=[24;30;-24];

[x, k, index]=Jacobi(A, b, 1e-5, 100) 输出: x = -2.9998 11.9987 -3.0001 k = 100 index = 0

所以解为:x1=-2.9998, x2=11.9987, x3=-3.0001

2.2 Gauss-Seide迭代

若L、 U、 D为上述的L、 U、 D。则Gauss—Seidel迭代法的矩阵表示

(k1)1(k1)(k)(k1)xD(LxUxb)x为:,现将显示化由

(DL)x(k1)Ux(k)b得:x(k1)(DL)1Ux(k)(DL)1b,令

(k1)(k)G(DL)1,g(DL)1b,xGxg,则得:此即为Gauss

—Seidel迭代法的矩阵表示形式,G称为迭代阵。

由Jacobi迭代法中,每一次的迭代只用到前一次的迭代值,若每一次迭代充分利用当前最新的迭代值,即在计算第

i个分量xi

x

(k)

(k1)

时,用最新分量

x1

(k1)

x,2

(k1)

xi-1

(k1)

代替旧分量1

x2

(k)

xi-1

(k)

,就得到

所谓解方程组的Gauss-Seidel迭代法。其迭代格式为

(0)(0)(0)Tx(0)(x1,x2,,xn) (初始向量),

x

(i1)

i

i1i1

1(k1)

(biaijxjaijx(jk))aiij1ji1

(k0,1,2,;i0,1,2,n)

或者写为

xi(k1)xi(k)xi(kk0,1,2,;i0,1,2,n)

i1i1

1(i1)(k1)xi(biaijxjaijx(jk))

aiij1ji1

1(k1)(k)(k)(k)

xaxaxaxb111221331nna11

1(k1)(k1)(k)(k)

xaxaxaxb222112332nna22



(IV)

1xi(k1)ai1x1(k1)ai2x2(k1)ai,i1xi1(k1)ai,i1xi1(k)ainxn(k)biaii1xn(k1)an1xn(k1)an2x2(k1)annxn(k1)bnann

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

4x13x224

3x13x2x330 x4x24

23

输入

A=[4 3 0;3 3 -1;0 -1 4]; b=[24;30;-24]; x0=[0;0;0];

[v,sN,vChain]=gaussSeidel(A,b,x0,0.00001,11) 输出: v = 0.6169 11.1962 -4.2056 sN = 11 vChain =

6.0000 10.0000 -6.0000 -1.5000 2.0000 -3.5000 4.5000 10.3333 -5.5000 -1.7500 3.6667 -3.4167 3.2500 10.6111 -5.0833 -1.9583 5.0556 -3.3472 2.2083 10.8426 -4.7361 -2.1319 6.2130 -3.2894 1.3403 11.0355 -4.4468 -2.2766 7.1775 -3.2411 0.6169 11.1962 -4.2056 0 0 0 0 0 0 0 0 0 0 0 0 所以结果为:

x1= 0.6169, x2=11.1962, x3=-4.2056 。

2.3 SOR迭代

在很多情况下,Jacobi和Gauss—Seidel法收敛速度较慢,SOR法是Gauss—Seidel法的一种加速方法,需要施加合适的松弛因子。

若L、 U、 D为上述的L、 U、 D 。SOR迭代公式为X其中

(k1)

LwX(k)f,

Lw(DL)1((1)DU),f(DL)1b,[1,2]。

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

0.76x10.01x20.14x30.16x40.680.01x0.88x0.03x0.06x1.181234 0.14x0.03x1.01x0.12x0.1212340.16x10.06x20.12x30.72x40.74

取初始点x输入

A=[0.76 -0.01 -0.14 -0.16;-0.01 0.88 -0.03 0.06; -0.14 -0.03 1.01 -0.12;-0.16 0.06 -0.12 0.72]; B=[0.68 1.18 0.12 0.72]; X0=[0;0;0;0]; W=1.05

[x,n]=SOR(A,b,x0,w) 输出 x=

1.2715 1.2844 0.4858 1.2843 n=

7

有上述结果得出:经过7次迭代后,该方程组的解为 x1=1.2715, x2=1.2844, x3=0.4858, x4=1.2843

(0)

(0,0,0,0)T松弛因子1.05,精度要求106。

2.4 迭代法收敛

k

limA0的充要条件为(A)1((A)为引理:设A为n阶方阵,则x

普半径)。

k

limA0

证明:必要性若

x

k

limA0有因为(A)A所以0(A)A 由矩阵收敛的定义知x

由夹逼定理可得出

lim[(A)]k0,又因为(Ak)[(A)]k所以由x

lim[A(k)]可得出0(A)1 x

充分性:若

(A)1,取

1(A)

0,存在矩阵范

数2

,使得

k1(A)

A(A)1则有:limA0,

x2

由算子范数相容性可得:0AA

k

k1

AA

k

A由夹逼定理可得出limx

定理1: 迭代公式x

(k1)

k

0。

Bx(k)f,k0,1,2....收敛的充分必要条件是迭代

矩阵B的谱半径(B)1 证明:必要性

设存在n维向量x,使得limx由迭代公式得出

xkx,则x满足xBxkf

xkx

Bx(k1)fBxfBx(k1)xB

2

Bk

x

x

(k2)(0)

x

x

B所以limx

因为

k

x

(0)

xlimxkx0

x

x

(0)

k

limB0 为任意n维向量,因此上式成立必须

x

由引理可得出(B)1。 充分性:若(B)1,则

1不是B的特征值,因而有IB0,于是对

xxBxf 有唯一解,记为。即:

任意的n维向量f,方程组(IB)xf

k

limB0,又因为 且x

xkx

Bx(k1)fBxfBx(k1)xB2x(k2)xBkx(0)x

(0)kk(0)

x所以,对任意初始向量都有limxxlimBxx0

xx

即迭代公式x

(k1)

Bx(k)f,k0,1,2....收敛。

1in

注解: 代矩阵B的谱半径(B)maxi(B)这里的i(B)是矩阵B的特征值。

定理2:若迭代矩阵的一种范数

(k1)(k)

xBxf迭代格式

B1

(0)fx,则对任意的初始向量和任意

均收敛。

迭代法收敛与否只决定于迭代矩阵的普半径,于初始向量及右端项无关。对于同一方程组,由于不同的迭代法迭代矩阵不同,可能出现有的方法收敛,有的发散的情形。

n

n

A

注解:三种常用矩阵范数为:

maxaij

i

j1

A1maxaij

j

i1

A2T(1是AA的最大特征值)。

由上述两个定理可得:Jacobi迭代收敛的充分必要条件是(B)1,收敛的充分条件是任一种范数B1,Gauss—Seidel迭代收敛的充分必要条件是(B)1,收敛的充分条件是任一种范数B1。

x定理3:对角占优线性方程组Axb的Jacobi迭代格式

(k1)(k)xGxg收敛。 Gauss—Seidel迭代格式均(k1)Bx(k)f和

注解:n阶方阵A,如果其主对角线元素的绝对值大于同行其他元素绝对值之和,则称A是对角占优的.

虽然定理1是充分必要条件,可是需要计算迭代矩阵B的特征值,我们在线性代数上看到一个大型矩阵的特征值是非常难求的,计算量是很大的。定理2和定理3的计算量相对定理1来说是相当小的,因为它们只是简单的加减乘除;但是他们是充分条件,不满足时需要再改用定理1来判断。所以收敛的判断可先采用定理2和定理3,不行再选择定理1。

预处理是用来加速迭代法收敛的一个重要手段。值得注意的是,经典的求解线性方程组的迭代法也都能够看作是求解采用不同的因子预处理之后得到的线性方程组的迭代法。换句话来说,原线性方程组的松弛迭代法等价于预处理之后的方程组的定点迭代法。谱条件数是反映预处理因子性态是否良好的一个有效指标。在估计特征值和条件数的界的研究领域,虽然已经有了很多的研究成果,但是支持理论还是一个全新的概念。支撑理论是一个用于分析预处理方程组的最大(或最小)特征值和条件数的代数架构,它最初产生于对称正定的线性方程组(7)

2.5 迭代法收敛的应用

用Jacobi迭代,Gauss—Seidel迭代两种方法求解下列方程组是否收敛。 x12x22x31x1x2x32 2x2xx3231

解:因为迭代法收敛与否只决定于迭代矩阵的普半径。所以求普半径是否小于1.

122100,010A111D

221001

000022001L100U, 220000

Jacobi迭代矩阵BD1(LU)

022BD1(LU)101 220

其特征方程

所以1221302IB12 230,所以(B)01所以Jacobi迭代法收敛。

1Gauss—Seidel迭代矩阵B(DL)

022B(DL)1023 002

所以特征值为1

代法发散。 2023(2)20 IB02其特征方程20,232所以(B)21所以Gauss—Seidel迭

上述例子说明对于同一方程组,由于不同的迭代法迭代矩阵不同,可能出现有的方法收敛,有的发散的情形。


相关内容

  • 预处理共轭梯度法求解线性方程组
  • [摘 要]针对共轭梯度法求解线性方程组,提出一种预处理思想.基于次思想,首先给出预处理矩阵,然后求解预处理线性方程组,再使用共轭梯度法求解.最后通过几个数值试验,与直接使用共轭梯度法求解线性方程组相比较,本文的方法提高了收敛速度. [关键词]线性方程组,预处理,共轭梯度法 中图分类号:E911 文献 ...

  • 数值分析中牛顿迭代法的引入方法探讨
  • 第25卷第5期2010年lO月 天中学刊 JournalofTianzhong .,01.25No.5 oct.20lO 数值分析中牛顿迭代法的引入方法探讨 王霞,张启虎 (郑州轻工业学院数学与信息科学系,河南郑州450002) 摘要:数值分析中牛顿迭代法是求解非线性方程的基本方法.与一般教材上牛顿 ...

  • 求解三对角线性方程组两类并行算法的特点
  •  一、概述   三对角线性方程组的求解是许多科学和工程计算中最重要也是最基本的问题之一。在核物理、流体力学、油藏工程、石油地震数据处理及数值天气预报等许多领域的大规模科学工程和数值处理中都会遇到三对角系统的求解问题。很多三对角线性方程组的算法可以直接推广到求解块三对角及带状线性方程组。由于在理论和实 ...

  • 有无穷解的线性方程组的迭代法_田学全
  • 第16卷 第2期塔 里 木 农 垦 大 学 学 报Vol.16No.2 2004年6月JournalofTarimUniversityofAgriculturalReclamationJun.2004 ① 文章编号:1009-0568(2004)02-0055-02 有无穷解的线性方程组的迭代法 田 ...

  • 迭代法实验
  • 实验五 线性方程组的迭代法实验 一. 实验目的 (1)深入理解线性方程组的迭代法的设计思想,学会利用系数矩阵的性质以保证迭 代过程的收敛性,以及解决某些实际的线性方程组求解问题. (2)熟悉Matlab编程环境,利用Matlab解决具体的方程求根问题. 二. 实验要求 建立Jacobi迭代公式.Ga ...

  • C语言解决多元多次方程
  • 一 理论背景 我们先考虑线性方程,线性方程组的解便不难得出了. 与线性方程相比,非线性方程问题无论是从理论上还是从计算公式上,都要复杂得多.对于一般的非线性方程f (x ) =0,计算方程的根既无一定章程可寻也无直接法可言.例如,求解高次方程组7x -x +x -1.5=0的根,求解含有指数和正弦函 ...

  • 数值计算基础
  • 数值计算基础 实验指导书 2010年 目录 实验一 直接法解线性方程组的 ................................ 1 实验二 插值方法 ........................................... 10 实验三 数值积分 ............. ...

  • 高斯消去法高斯塞德尔迭代法
  • 数值计算 高斯消去法和高斯-塞德尔迭代法 摘要 虽然已学过加减消元法.代入消元法.矩阵变换法和Cramer 法则等,但是无法满足实际计算需要,故在此讨论在计算机上实现的有效而实用的解法.线性方程组的解法大致分2类:直接法(高斯消去法)和迭代法(高斯-赛德尔迭代法),在此对着此类算法进行比较分析. 一 ...

  • 有限元的发展历史现状及应用前景
  • 有限元分析的发展趋势 "有限元"这个名词第一次出现,到今天有限元在工程上得到广泛应用,经历了三十多年的发展历史,理论和 算法都已经日趋完善.有限元的核心思想是结构的离散化,就是将实际结构假想地离散为有限数目的规则单元组合体,实际结构的物理性能可以通过对离散体进行分 析,得出满足工 ...