計算方法3-線性方程組迭代解法

線性方程組迭代解法IterativeTechniquesforSolvingLinearSystems(2.1)迭代法：不是用有限步運(yùn)算求精確解，通過迭代產(chǎn)生近似解逼近精確解?！狫acobi迭代,Gauss-Seidel迭代思路：構(gòu)造一個向量序列{X(n)}，使其收斂在某個極限向量X*，而X*就是(2.1)式的準(zhǔn)確解。如何構(gòu)造迭代序列{X(n)}?{X(n)}在什么條件下收斂?收斂速率如何?誤差估計.3.1向量和矩陣的范數(shù)

NormsofVectorsandMatrices數(shù)值分析中,經(jīng)常要用向量和矩陣,為了應(yīng)用的需要(誤差分析),引入衡量向量和矩陣大小的度量——范數(shù).

對于實數(shù)x∈R,我們定義了絕對值,滿足

|x|≥0

非負(fù)性|αx|=|α|·|x|

齊次性|x+y|≤|x|+|y|

三角不等式類似地,定義向量范數(shù)Def3.1

在實n維線性空間Rn中定義一個映射,它使任意X∈

Rn

有一個非負(fù)實數(shù)與之對應(yīng),記為||X||,且該映射滿足:

正定性

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

齊次性

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

三角不等式

任意X,Y∈

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

則稱該映射在Rn中定義了一個向量范數(shù).

注:

Rn中的范數(shù)不唯一.

常用的范數(shù)有三種:設(shè)X=(x1,x2,…,xn)T∈Rn.則

注:(1)用范數(shù)的定義可驗證上述皆為向量范數(shù)

(2)

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

即為||X||1,||X||2.

(3)

任意x∈Rn:

定理3.2

設(shè)||?||α和||?||β是Rn上任意兩種范數(shù)，則存在正常數(shù)C1和C2，使得對一切X∈

Rn

有

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

C2||X||α注:Rn中范數(shù)的等價性表明,雖范數(shù)值不同,但考慮到向量序列收斂性時,卻有明顯的一致性.

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）都有注：向量序列收斂實際上是按分量收斂（數(shù)列收斂）利用向量范數(shù)，也可以說明向量序列收斂的概念。

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

的充要條件是則向量X*＝(x1*,x2*,…,xn*)T稱為{X(k)}的極限，記做矩陣的范數(shù)類似于向量范數(shù)，給出矩陣范數(shù)的定義。

Def3.6

在線性空間Rn×n中定義一個映射，使任意A∈Rn×n對應(yīng)一個非負(fù)實數(shù)，記做||A||.如果該映射滿足：

1.正定性：

（4.是矩陣乘法的需要，而1.2.3.為向量范數(shù)的推廣。）

2.齊次性：3.三角不等性：4.相容性：在Rn×n中可定義多種范數(shù)。例1A=(aij)n×n∈Rn×n

稱為frobenius范數(shù)

3.2常用的迭代格式

簡單迭代法（Jacobi迭代）(3.1)設(shè)有方程組用矩陣表示(3.1’)其中A是系數(shù)矩陣，非奇異，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，一直進(jìn)行下去，迭代格式

X(n+1)=BX(n)+Gn=0,1,2,…以上過程產(chǎn)生向量序列{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迭代格式為計算結(jié)果可列表如下注意：未必Seidel方法一定比Jacobi方法好。松弛法松弛法可認(rèn)為是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,…

其中，ω稱為松弛因子，當(dāng)ω>1時叫超松弛，當(dāng)ω<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),和常數(shù)項f,由迭代格式

X(k+1)=MX(k)+fk=0,1,2,…產(chǎn)生的解向量序列{X(k)}收斂且與初值無關(guān)的充要條件是

ρ(M)<1ρ(M)是矩陣M的譜半徑k0123x1k011-69-499x2k0-1481-374x3k0-366-4293.4判別收斂的幾個常用條件Jac