线性方程组的直接法
直接法就是经过有限步算术运算,无需迭代可直接求得方程组精确解的方法。
线性方程组迭代法
迭代法就是用某种极限过程去逐步逼近线性方程组精确解的方法.该方法具有对计算机的存贮单元需求少,程序设计简单、原始系数矩阵在计算过程中不变等优点,是求解大型稀疏矩阵方程组的重要方法.迭代法不是用有限步运算求精确解,而是通过迭代产生近似解逼近精确解.如Jacobi迭代、Gauss— Seidel迭代、SOR迭代法等。
1. 线性方程组的直接法
直接法就是经过有限步算术运算,无需迭代可直接求得方程组精确解的方法。
1.1 Cramer法则
Cramer法则用于判断具有n个未知数的n个线性方程的方程组解的情况。当方程组的系数行列式不等于零时,方程组有解且解唯一。如果方程组无解或者有两个不同的解时,则系数行列式必为零。如果齐次线性方程组的系数行列式不等于零,则没有非零解。如果齐次线性方程组有非零解,则系数行列式必为零。
定理1如果方程组Axb中D
解为x1
A0,xb则A
有解,且解事唯一的,
DD1D
,x22,...xnn,Di是D中第i列换成向量b所得的行列式。 DDD
Cramer法则解n元方程组有两个前提条件: 1、未知数的个数等于方程的个数。 2、系数行列式不等于零 例1 a取何值时,线性方程组
x1x2x3a
ax1x2x31有唯一解。 xxax1
231
111
1
1
1
解:Aa1101a1a(a1)2 11a00a1所以当a
1时,方程组有唯一解。
定理2当齐次线性方程组Ax0,A0时该方程组有唯一的零解。
定理3齐次线性方程组Ax0有非零解A0。 1.2 Gauss消元法
Gauss消元法是线性代数中的一个算法,可用来为线性方程组求解,求出矩阵的秩,以及求出可逆方阵的逆矩阵。当用于一个矩阵时,高斯消元法会产生出一个“行梯阵式”。
1.2.1 用Gauss消元法为线性方程组求解
eg:Gauss消元法可用来找出下列方程组的解或其解的限制:
2xyz8L1
3xy2z11L2 2xy2z3L3
这个算法的原理是:首先,要将L1以下的等式中的
x消除,然后再将L2
以下的等式中的y消除。这样可使整个方程组变成一个三角形似的格式。之后再将已得出的答案一个个地代入已被简化的等式中的未知数中,就可求出其余的答案了。
3
在刚才的例子中,我们将L1和L2相加,就可以将L2中的x消除了。
2
然后再将1和
L
L3相加,就可以将L3中的x消除。
方程组则变为:
2xyz811
yz1 222yz5
现在将4L2和L3相加,就可将L3中的
y消除,方程组变为:
2xyz811
yz1
22
z1
这样就完成了整个算法的初步,一个三角形的格式(指:变量的格式而言,上例中的变量各为3,2,1个)出现了。第二步,就是由尾至头地将已知的答案代入其他等式中的未知数。第一个答案就是得出第二个答案:
z1。然后直接带入,立即就可
y3和最后一个答案x2。这样,我们利用高斯消元法
解决了这个方程组。
2. 线性方程组迭代法
迭代法就是用某种极限过程去逐步逼近线性方程组精确解的方法.该方法具有对计算机的存贮单元需求少,程序设计简单、原始系数矩阵在计算过程中不变等优点,是求解大型稀疏矩阵方程组的重要方法.迭代法不是用有限步运算求精确解,而是通过迭代产生近似解逼近精确解.如Jacobi迭代、Gauss— Seidel迭代、SOR迭代法等。
2.1 Jacobi迭代法
0a210a31a320L
............
an1,1an1,2...0
an,2an,n10an,1
a11a22a33
D
...
an1,n1
an,n
0a12a13...a1.n1a1,n0a23...a2,n1a2,n0a34...a3,nU
...
0
0
对于线性方程组Ax
b则ALDU,即将A分解为一个严格下三
角矩阵、一个对角阵和一个严格上三角矩阵之和,从而可写出Jacobi迭代格式
(k1)1(k)(1)
xD(LU)xDb,其迭代矩阵
的矩阵表示形式为:
JD1(LU))称为雅可比迭代矩阵.
将线性方程组Ax
b变为一个通解方程组xBxf
,对其进行迭代式
(k1)(k)
xBxf,k0,1,2....矩阵B为迭代矩阵 改写,
a11x1a12x2a1nxnb1axaxaxb2112222nn2
I
an1x1an2x2annxnbn
由方程组(I)的第i个方程解出x1(i1,2,n),得到一个同解方程组:
1
x1aa12x2a13x3a1nxnb111
1
a21x2a23x3a2nxnb2x2a22(II)
1
xnaan1xnan2x2annxnbnnn
构造相应的迭代公式
(k1)1(k)(k)(k)xaxaxaxb111221331nna11
1(k1)(k)(k)(k)
xaxaxaxb222122332nn
a22(III)
1(k1)(k)(k)(k)
xaxaxaxbnn1nn22nnnn
ann
取初始向量x
(k)
(0)
x,x,x
(0)
1
(0)2(0)Tn
,利用(III)反复迭代可以得到一个向
量序列x,利用此迭代格式求解方程组的解法称为Jacobi迭代法。
用Jacobi迭代求解下列方程组
4x13x224
3x13x2x330 x4x24
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迭代法的矩阵表示
(k1)1(k1)(k)(k1)xD(LxUxb)x为:,现将显示化由
(DL)x(k1)Ux(k)b得:x(k1)(DL)1Ux(k)(DL)1b,令
(k1)(k)G(DL)1,g(DL)1b,xGxg,则得:此即为Gauss
—Seidel迭代法的矩阵表示形式,G称为迭代阵。
由Jacobi迭代法中,每一次的迭代只用到前一次的迭代值,若每一次迭代充分利用当前最新的迭代值,即在计算第
i个分量xi
x
(k)
(k1)
时,用最新分量
x1
(k1)
x,2
(k1)
xi-1
(k1)
代替旧分量1
,
x2
(k)
xi-1
(k)
,就得到
所谓解方程组的Gauss-Seidel迭代法。其迭代格式为
(0)(0)(0)Tx(0)(x1,x2,,xn) (初始向量),
x
(i1)
i
i1i1
1(k1)
(biaijxjaijx(jk))aiij1ji1
(k0,1,2,;i0,1,2,n)
或者写为
xi(k1)xi(k)xi(kk0,1,2,;i0,1,2,n)
i1i1
1(i1)(k1)xi(biaijxjaijx(jk))
aiij1ji1
1(k1)(k)(k)(k)
xaxaxaxb111221331nna11
1(k1)(k1)(k)(k)
xaxaxaxb222112332nna22
(IV)
1xi(k1)ai1x1(k1)ai2x2(k1)ai,i1xi1(k1)ai,i1xi1(k)ainxn(k)biaii1xn(k1)an1xn(k1)an2x2(k1)annxn(k1)bnann
用Gauss-Seide迭代求解下列方程组
4x13x224
3x13x2x330 x4x24
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其中
(k1)
LwX(k)f,
Lw(DL)1((1)DU),f(DL)1b,[1,2]。
用SOR迭代求解下列方程组。
0.76x10.01x20.14x30.16x40.680.01x0.88x0.03x0.06x1.181234 0.14x0.03x1.01x0.12x0.1212340.16x10.06x20.12x30.72x40.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,精度要求106。
2.4 迭代法收敛
k
limA0的充要条件为(A)1((A)为引理:设A为n阶方阵,则x
普半径)。
k
limA0
证明:必要性若
x
k
limA0有因为(A)A所以0(A)A 由矩阵收敛的定义知x
由夹逼定理可得出
lim[(A)]k0,又因为(Ak)[(A)]k所以由x
lim[A(k)]可得出0(A)1 x
充分性:若
(A)1,取
1(A)
0,存在矩阵范
数2
,使得
k1(A)
A(A)1则有:limA0,
x2
由算子范数相容性可得:0AA
k
k1
AA
k
A由夹逼定理可得出limx
定理1: 迭代公式x
(k1)
k
0。
Bx(k)f,k0,1,2....收敛的充分必要条件是迭代
矩阵B的谱半径(B)1 证明:必要性
设存在n维向量x,使得limx由迭代公式得出
xkx,则x满足xBxkf
xkx
Bx(k1)fBxfBx(k1)xB
2
Bk
x
x
(k2)(0)
x
x
B所以limx
因为
k
x
(0)
xlimxkx0
x
x
(0)
k
limB0 为任意n维向量,因此上式成立必须
x
由引理可得出(B)1。 充分性:若(B)1,则
1不是B的特征值,因而有IB0,于是对
xxBxf 有唯一解,记为。即:
任意的n维向量f,方程组(IB)xf
k
limB0,又因为 且x
xkx
Bx(k1)fBxfBx(k1)xB2x(k2)xBkx(0)x
(0)kk(0)
x所以,对任意初始向量都有limxxlimBxx0
xx
即迭代公式x
(k1)
Bx(k)f,k0,1,2....收敛。
1in
注解: 代矩阵B的谱半径(B)maxi(B)这里的i(B)是矩阵B的特征值。
定理2:若迭代矩阵的一种范数
(k1)(k)
xBxf迭代格式
B1
(0)fx,则对任意的初始向量和任意
。
均收敛。
迭代法收敛与否只决定于迭代矩阵的普半径,于初始向量及右端项无关。对于同一方程组,由于不同的迭代法迭代矩阵不同,可能出现有的方法收敛,有的发散的情形。
n
n
A
注解:三种常用矩阵范数为:
maxaij
i
j1
,
A1maxaij
j
i1
,
A2T(1是AA的最大特征值)。
由上述两个定理可得:Jacobi迭代收敛的充分必要条件是(B)1,收敛的充分条件是任一种范数B1,Gauss—Seidel迭代收敛的充分必要条件是(B)1,收敛的充分条件是任一种范数B1。
x定理3:对角占优线性方程组Axb的Jacobi迭代格式
(k1)(k)xGxg收敛。 Gauss—Seidel迭代格式均(k1)Bx(k)f和
注解:n阶方阵A,如果其主对角线元素的绝对值大于同行其他元素绝对值之和,则称A是对角占优的.
虽然定理1是充分必要条件,可是需要计算迭代矩阵B的特征值,我们在线性代数上看到一个大型矩阵的特征值是非常难求的,计算量是很大的。定理2和定理3的计算量相对定理1来说是相当小的,因为它们只是简单的加减乘除;但是他们是充分条件,不满足时需要再改用定理1来判断。所以收敛的判断可先采用定理2和定理3,不行再选择定理1。
预处理是用来加速迭代法收敛的一个重要手段。值得注意的是,经典的求解线性方程组的迭代法也都能够看作是求解采用不同的因子预处理之后得到的线性方程组的迭代法。换句话来说,原线性方程组的松弛迭代法等价于预处理之后的方程组的定点迭代法。谱条件数是反映预处理因子性态是否良好的一个有效指标。在估计特征值和条件数的界的研究领域,虽然已经有了很多的研究成果,但是支持理论还是一个全新的概念。支撑理论是一个用于分析预处理方程组的最大(或最小)特征值和条件数的代数架构,它最初产生于对称正定的线性方程组(7)
2.5 迭代法收敛的应用
用Jacobi迭代,Gauss—Seidel迭代两种方法求解下列方程组是否收敛。 x12x22x31x1x2x32 2x2xx3231
解:因为迭代法收敛与否只决定于迭代矩阵的普半径。所以求普半径是否小于1.
122100,010A111D
221001
000022001L100U, 220000
Jacobi迭代矩阵BD1(LU)
022BD1(LU)101 220
其特征方程
所以1221302IB12 230,所以(B)01所以Jacobi迭代法收敛。
1Gauss—Seidel迭代矩阵B(DL)
022B(DL)1023 002
所以特征值为1
代法发散。 2023(2)20 IB02其特征方程20,232所以(B)21所以Gauss—Seidel迭
上述例子说明对于同一方程组,由于不同的迭代法迭代矩阵不同,可能出现有的方法收敛,有的发散的情形。
线性方程组的直接法
直接法就是经过有限步算术运算,无需迭代可直接求得方程组精确解的方法。
线性方程组迭代法
迭代法就是用某种极限过程去逐步逼近线性方程组精确解的方法.该方法具有对计算机的存贮单元需求少,程序设计简单、原始系数矩阵在计算过程中不变等优点,是求解大型稀疏矩阵方程组的重要方法.迭代法不是用有限步运算求精确解,而是通过迭代产生近似解逼近精确解.如Jacobi迭代、Gauss— Seidel迭代、SOR迭代法等。
1. 线性方程组的直接法
直接法就是经过有限步算术运算,无需迭代可直接求得方程组精确解的方法。
1.1 Cramer法则
Cramer法则用于判断具有n个未知数的n个线性方程的方程组解的情况。当方程组的系数行列式不等于零时,方程组有解且解唯一。如果方程组无解或者有两个不同的解时,则系数行列式必为零。如果齐次线性方程组的系数行列式不等于零,则没有非零解。如果齐次线性方程组有非零解,则系数行列式必为零。
定理1如果方程组Axb中D
解为x1
A0,xb则A
有解,且解事唯一的,
DD1D
,x22,...xnn,Di是D中第i列换成向量b所得的行列式。 DDD
Cramer法则解n元方程组有两个前提条件: 1、未知数的个数等于方程的个数。 2、系数行列式不等于零 例1 a取何值时,线性方程组
x1x2x3a
ax1x2x31有唯一解。 xxax1
231
111
1
1
1
解:Aa1101a1a(a1)2 11a00a1所以当a
1时,方程组有唯一解。
定理2当齐次线性方程组Ax0,A0时该方程组有唯一的零解。
定理3齐次线性方程组Ax0有非零解A0。 1.2 Gauss消元法
Gauss消元法是线性代数中的一个算法,可用来为线性方程组求解,求出矩阵的秩,以及求出可逆方阵的逆矩阵。当用于一个矩阵时,高斯消元法会产生出一个“行梯阵式”。
1.2.1 用Gauss消元法为线性方程组求解
eg:Gauss消元法可用来找出下列方程组的解或其解的限制:
2xyz8L1
3xy2z11L2 2xy2z3L3
这个算法的原理是:首先,要将L1以下的等式中的
x消除,然后再将L2
以下的等式中的y消除。这样可使整个方程组变成一个三角形似的格式。之后再将已得出的答案一个个地代入已被简化的等式中的未知数中,就可求出其余的答案了。
3
在刚才的例子中,我们将L1和L2相加,就可以将L2中的x消除了。
2
然后再将1和
L
L3相加,就可以将L3中的x消除。
方程组则变为:
2xyz811
yz1 222yz5
现在将4L2和L3相加,就可将L3中的
y消除,方程组变为:
2xyz811
yz1
22
z1
这样就完成了整个算法的初步,一个三角形的格式(指:变量的格式而言,上例中的变量各为3,2,1个)出现了。第二步,就是由尾至头地将已知的答案代入其他等式中的未知数。第一个答案就是得出第二个答案:
z1。然后直接带入,立即就可
y3和最后一个答案x2。这样,我们利用高斯消元法
解决了这个方程组。
2. 线性方程组迭代法
迭代法就是用某种极限过程去逐步逼近线性方程组精确解的方法.该方法具有对计算机的存贮单元需求少,程序设计简单、原始系数矩阵在计算过程中不变等优点,是求解大型稀疏矩阵方程组的重要方法.迭代法不是用有限步运算求精确解,而是通过迭代产生近似解逼近精确解.如Jacobi迭代、Gauss— Seidel迭代、SOR迭代法等。
2.1 Jacobi迭代法
0a210a31a320L
............
an1,1an1,2...0
an,2an,n10an,1
a11a22a33
D
...
an1,n1
an,n
0a12a13...a1.n1a1,n0a23...a2,n1a2,n0a34...a3,nU
...
0
0
对于线性方程组Ax
b则ALDU,即将A分解为一个严格下三
角矩阵、一个对角阵和一个严格上三角矩阵之和,从而可写出Jacobi迭代格式
(k1)1(k)(1)
xD(LU)xDb,其迭代矩阵
的矩阵表示形式为:
JD1(LU))称为雅可比迭代矩阵.
将线性方程组Ax
b变为一个通解方程组xBxf
,对其进行迭代式
(k1)(k)
xBxf,k0,1,2....矩阵B为迭代矩阵 改写,
a11x1a12x2a1nxnb1axaxaxb2112222nn2
I
an1x1an2x2annxnbn
由方程组(I)的第i个方程解出x1(i1,2,n),得到一个同解方程组:
1
x1aa12x2a13x3a1nxnb111
1
a21x2a23x3a2nxnb2x2a22(II)
1
xnaan1xnan2x2annxnbnnn
构造相应的迭代公式
(k1)1(k)(k)(k)xaxaxaxb111221331nna11
1(k1)(k)(k)(k)
xaxaxaxb222122332nn
a22(III)
1(k1)(k)(k)(k)
xaxaxaxbnn1nn22nnnn
ann
取初始向量x
(k)
(0)
x,x,x
(0)
1
(0)2(0)Tn
,利用(III)反复迭代可以得到一个向
量序列x,利用此迭代格式求解方程组的解法称为Jacobi迭代法。
用Jacobi迭代求解下列方程组
4x13x224
3x13x2x330 x4x24
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迭代法的矩阵表示
(k1)1(k1)(k)(k1)xD(LxUxb)x为:,现将显示化由
(DL)x(k1)Ux(k)b得:x(k1)(DL)1Ux(k)(DL)1b,令
(k1)(k)G(DL)1,g(DL)1b,xGxg,则得:此即为Gauss
—Seidel迭代法的矩阵表示形式,G称为迭代阵。
由Jacobi迭代法中,每一次的迭代只用到前一次的迭代值,若每一次迭代充分利用当前最新的迭代值,即在计算第
i个分量xi
x
(k)
(k1)
时,用最新分量
x1
(k1)
x,2
(k1)
xi-1
(k1)
代替旧分量1
,
x2
(k)
xi-1
(k)
,就得到
所谓解方程组的Gauss-Seidel迭代法。其迭代格式为
(0)(0)(0)Tx(0)(x1,x2,,xn) (初始向量),
x
(i1)
i
i1i1
1(k1)
(biaijxjaijx(jk))aiij1ji1
(k0,1,2,;i0,1,2,n)
或者写为
xi(k1)xi(k)xi(kk0,1,2,;i0,1,2,n)
i1i1
1(i1)(k1)xi(biaijxjaijx(jk))
aiij1ji1
1(k1)(k)(k)(k)
xaxaxaxb111221331nna11
1(k1)(k1)(k)(k)
xaxaxaxb222112332nna22
(IV)
1xi(k1)ai1x1(k1)ai2x2(k1)ai,i1xi1(k1)ai,i1xi1(k)ainxn(k)biaii1xn(k1)an1xn(k1)an2x2(k1)annxn(k1)bnann
用Gauss-Seide迭代求解下列方程组
4x13x224
3x13x2x330 x4x24
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其中
(k1)
LwX(k)f,
Lw(DL)1((1)DU),f(DL)1b,[1,2]。
用SOR迭代求解下列方程组。
0.76x10.01x20.14x30.16x40.680.01x0.88x0.03x0.06x1.181234 0.14x0.03x1.01x0.12x0.1212340.16x10.06x20.12x30.72x40.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,精度要求106。
2.4 迭代法收敛
k
limA0的充要条件为(A)1((A)为引理:设A为n阶方阵,则x
普半径)。
k
limA0
证明:必要性若
x
k
limA0有因为(A)A所以0(A)A 由矩阵收敛的定义知x
由夹逼定理可得出
lim[(A)]k0,又因为(Ak)[(A)]k所以由x
lim[A(k)]可得出0(A)1 x
充分性:若
(A)1,取
1(A)
0,存在矩阵范
数2
,使得
k1(A)
A(A)1则有:limA0,
x2
由算子范数相容性可得:0AA
k
k1
AA
k
A由夹逼定理可得出limx
定理1: 迭代公式x
(k1)
k
0。
Bx(k)f,k0,1,2....收敛的充分必要条件是迭代
矩阵B的谱半径(B)1 证明:必要性
设存在n维向量x,使得limx由迭代公式得出
xkx,则x满足xBxkf
xkx
Bx(k1)fBxfBx(k1)xB
2
Bk
x
x
(k2)(0)
x
x
B所以limx
因为
k
x
(0)
xlimxkx0
x
x
(0)
k
limB0 为任意n维向量,因此上式成立必须
x
由引理可得出(B)1。 充分性:若(B)1,则
1不是B的特征值,因而有IB0,于是对
xxBxf 有唯一解,记为。即:
任意的n维向量f,方程组(IB)xf
k
limB0,又因为 且x
xkx
Bx(k1)fBxfBx(k1)xB2x(k2)xBkx(0)x
(0)kk(0)
x所以,对任意初始向量都有limxxlimBxx0
xx
即迭代公式x
(k1)
Bx(k)f,k0,1,2....收敛。
1in
注解: 代矩阵B的谱半径(B)maxi(B)这里的i(B)是矩阵B的特征值。
定理2:若迭代矩阵的一种范数
(k1)(k)
xBxf迭代格式
B1
(0)fx,则对任意的初始向量和任意
。
均收敛。
迭代法收敛与否只决定于迭代矩阵的普半径,于初始向量及右端项无关。对于同一方程组,由于不同的迭代法迭代矩阵不同,可能出现有的方法收敛,有的发散的情形。
n
n
A
注解:三种常用矩阵范数为:
maxaij
i
j1
,
A1maxaij
j
i1
,
A2T(1是AA的最大特征值)。
由上述两个定理可得:Jacobi迭代收敛的充分必要条件是(B)1,收敛的充分条件是任一种范数B1,Gauss—Seidel迭代收敛的充分必要条件是(B)1,收敛的充分条件是任一种范数B1。
x定理3:对角占优线性方程组Axb的Jacobi迭代格式
(k1)(k)xGxg收敛。 Gauss—Seidel迭代格式均(k1)Bx(k)f和
注解:n阶方阵A,如果其主对角线元素的绝对值大于同行其他元素绝对值之和,则称A是对角占优的.
虽然定理1是充分必要条件,可是需要计算迭代矩阵B的特征值,我们在线性代数上看到一个大型矩阵的特征值是非常难求的,计算量是很大的。定理2和定理3的计算量相对定理1来说是相当小的,因为它们只是简单的加减乘除;但是他们是充分条件,不满足时需要再改用定理1来判断。所以收敛的判断可先采用定理2和定理3,不行再选择定理1。
预处理是用来加速迭代法收敛的一个重要手段。值得注意的是,经典的求解线性方程组的迭代法也都能够看作是求解采用不同的因子预处理之后得到的线性方程组的迭代法。换句话来说,原线性方程组的松弛迭代法等价于预处理之后的方程组的定点迭代法。谱条件数是反映预处理因子性态是否良好的一个有效指标。在估计特征值和条件数的界的研究领域,虽然已经有了很多的研究成果,但是支持理论还是一个全新的概念。支撑理论是一个用于分析预处理方程组的最大(或最小)特征值和条件数的代数架构,它最初产生于对称正定的线性方程组(7)
2.5 迭代法收敛的应用
用Jacobi迭代,Gauss—Seidel迭代两种方法求解下列方程组是否收敛。 x12x22x31x1x2x32 2x2xx3231
解:因为迭代法收敛与否只决定于迭代矩阵的普半径。所以求普半径是否小于1.
122100,010A111D
221001
000022001L100U, 220000
Jacobi迭代矩阵BD1(LU)
022BD1(LU)101 220
其特征方程
所以1221302IB12 230,所以(B)01所以Jacobi迭代法收敛。
1Gauss—Seidel迭代矩阵B(DL)
022B(DL)1023 002
所以特征值为1
代法发散。 2023(2)20 IB02其特征方程20,232所以(B)21所以Gauss—Seidel迭
上述例子说明对于同一方程组,由于不同的迭代法迭代矩阵不同,可能出现有的方法收敛,有的发散的情形。