计算方法3-线性方程组迭代解法

线性方程组迭代解法IterativeTechniquesforSolvingLinearSystems(2.1)迭代法：不是用有限步运算求精确解，通过迭代产生近似解逼近精确解。——Jacobi迭代,Gauss-Seidel迭代思路：构造一个向量序列{X(n)}，使其收敛在某个极限向量X*，而X*就是(2.1)式的准确解。如何构造迭代序列{X(n)}?{X(n)}在什么条件下收敛?收敛速率如何?误差估计.3.1向量和矩阵的范数

NormsofVectorsandMatrices数值分析中,经常要用向量和矩阵,为了应用的需要(误差分析),引入衡量向量和矩阵大小的度量——范数.

对于实数x∈R,我们定义了绝对值,满足

|x|≥0

非负性|αx|=|α|·|x|

齐次性|x+y|≤|x|+|y|

三角不等式类似地,定义向量范数Def3.1

在实n维线性空间Rn中定义一个映射,它使任意X∈

Rn

有一个非负实数与之对应,记为||X||,且该映射满足:

正定性

任意X∈Rn,||X||≥0,ifandonlyifX=0时,||X||=0

齐次性

任意X∈Rn,λ∈R,有||λX||=|λ|·||X||

三角不等式

任意X,Y∈

Rn,有||X+Y||≤||X||+||Y||

则称该映射在Rn中定义了一个向量范数.

注:

Rn中的范数不唯一.

常用的范数有三种:设X=(x1,x2,…,xn)T∈Rn.则

注:(1)用范数的定义可验证上述皆为向量范数

(2)

p=1,2,||X||p

即为||X||1,||X||2.

(3)

任意x∈Rn:

定理3.2

设||•||α和||•||β是Rn上任意两种范数，则存在正常数C1和C2，使得对一切X∈

Rn

有

C1||X||α||X||β

C2||X||α注:Rn中范数的等价性表明,虽范数值不同,但考虑到向量序列收敛性时,却有明显的一致性.

Def3.3

Rn中X＝(x1,x2,…,xn)T和Y＝(y1,y2,…,yn)T则有有解

(x1,x2,x3)T＝(1,1,1)T，用Gauss消去法得到近似解Def3.4Rn中的向量序列{X(k)},即X0,X1,…XK,…其中XK＝(x1(k),x2(k),…,xn(k))T.若对任意i（i=1,2,…,n）都有注：向量序列收敛实际上是按分量收敛（数列收敛）利用向量范数，也可以说明向量序列收敛的概念。

定理3.5向量序列{X(k)}依分量收敛于X*

的充要条件是则向量X*＝(x1*,x2*,…,xn*)T称为{X(k)}的极限，记做矩阵的范数类似于向量范数，给出矩阵范数的定义。

Def3.6

在线性空间Rn×n中定义一个映射，使任意A∈Rn×n对应一个非负实数，记做||A||.如果该映射满足：

1.正定性：

（4.是矩阵乘法的需要，而1.2.3.为向量范数的推广。）

2.齐次性：3.三角不等性：4.相容性：在Rn×n中可定义多种范数。例1A=(aij)n×n∈Rn×n

称为frobenius范数

3.2常用的迭代格式

简单迭代法（Jacobi迭代）(3.1)设有方程组用矩阵表示(3.1’)其中A是系数矩阵，非奇异，X是解向量，B是右端项。(3.2)(3.3)若令则有

B=D-1(D-A)=I-D-1A,G=D-1B方程(3.3)可记为

X=BX+G方程(3.3)可记为

X=BX+G选取初始向量X0＝(x10,x20,…,xn0)T，代入方程(3.3)右端，可得到一个新向量，记为X1＝(x11,x21,…,xn1)T，一直进行下去，迭代格式

X(n+1)=BX(n)+Gn=0,1,2,…以上过程产生向量序列{X(k)},若收敛于X*，则有

X*=BX*+G(I-B)X*=G=D-1BAX*=B即X*是方程(3.1)的解(3.4)k012310x1k0.00000.60001.04730.93261.0001x2k0.00002.27271.71592.0531.9998x3k0.0000-1.1000-0.8052-1.0493-0.9998x4k0.00001.87500.88521.13090.9998唯一解X＝(1,2,-1,1)TGauss-seidel迭代法简单迭代法用X(k)计算X(k+1)时,需要同时保留X(k)和X(k+1)(3.5)若令则(3.5)式可写成

X(k+1)=LX(k+1)+UX(k)+Gk=0,1,2,…也可记为

X(k+1)=(I-L)-1UX(k)+(I-L)-1G称(I-L)-1U为Seidel迭代法的迭代矩阵(3.6)(3.7)[例3.4]

用Seidel迭代法求解方程组解：取初始向量,要求时迭代终止。

Seidel迭代格式为计算结果可列表如下注意：未必Seidel方法一定比Jacobi方法好。松弛法松弛法可认为是Seidel法的加速Seidel法

X(k+1)=LX(k+1)+UX(k)+Gk=0,1,2,…令

ΔX=X(k+1)－X(k)=LX(k+1)+UX(k)+G－X(k)X(k+1)=

X(k)＋ΔX松弛法思想

X(k+1)=

X(k)＋ωΔX松弛法

X(k+1)=(1-ω)X(k)＋ω(LX(k+1)+UX(k)+G)k=0,1,2,…

其中，ω称为松弛因子，当ω>1时叫超松弛，当ω<1时叫低松弛也可记为

X(k+1)=(I-ωL)-1((1-ω)I+ωU)X(k)+ω(I-ωL)-1G称(I-ωL)-1((1-ω)I+ωU)为松弛法的迭代矩阵(3.8)(3.9)(3.10)唯一解X＝(3,4,-5)Tk01237x1k15.2500003.14062503.08789063.0134110x2k13.8125003.88281253.92675783.9888241x3k1-5.046875-5.0292969-5.0183105-5.0027940Seidel法k01237x1k16.3125002.62231453.13330273.0000498x2k13.51953133.95852664.01026464.0002586x3k1-6.6501465-4.6004238-5.0966863-5.0003486SOR法ω=1.253.3迭代法的收敛性和误差估计

定理3.10对任何初始向量X(0),和常数项f,由迭代格式

X(k+1)=MX(k)+fk=0,1,2,…产生的解向量序列{X(k)}收敛且与初值无关的充要条件是

ρ(M)<1ρ(M)是矩阵M的谱半径k0123x1k011-69-499x2k0-1481-374x3k0-366-4293.4判别收敛的几个常用条件Jac