数值分析9(迭代法收敛性证明)

迭代法收敛性条件迭代误差估计定理

《数值分析》9*总结:矩阵范数算子范数

算子范数

矩阵1范数,

矩阵无穷范数,矩阵2范数例4

设||.||为Rn×n

上任意一种矩阵范数,则对任意的A∈Rn×n,有证明:例5

设||.||为Rn×n

上任意一种矩阵范数,则对AX=b(M–N)X=bMX=NX+b记

(k)=X(k)–X*(k=0,1,2,···)则有

(k+1)=B(k)(k=0,1,2,···)迭代格式:X(k+1)=BX(k)+f(B=M-1N,f=M-1b)

X(k+1)–X*=B(X(k)–X*)设方程组的精确解为X*,则有X*=BX*+f*

||(k+1)

||=||B(k)||

≤||B||.||(k)||

(k=0,1,2,···)*迭代法构造收敛条件中止准则引理1

*参考:P.83引理2

*引理3

证:必要性,设迭代法产生的序列{X(k)}收敛,记X*是该序列的极限点,则X*=B

X*+f。

定理4.1对任意的f和任意的初始向量X(0)迭代法

X(k+1)=BX(k)+f

收敛的充分必要条件是由X(0)的任意性知

*充分性

*

谱半径小于1是迭代收敛的充要条件,但它不易计算,所以在实际使用中通常并不好用。推论4.1若||B||<1,则对任意的f和任意的初始向量X(0)迭代法

X(k+1)=BX(k)+f

收敛。*定理4.2

设X*为方程组

AX=b的解若||B||<1,则对迭代格式

X(k+1)=BX(k)+f

有(1)(2)证||X(k+1)–X*||=||B(X(k)–X*)||≤||B||||X(k)–X*||X(k+1)–X*=B(X(k)–X*

)*||X(k)–X*||=||(X(k)–X(k+1))+(X(k+1)

–X*

)||≤||X(k)–X(k+1)||+||X(k+1)

–X*||

≤||X(k)–X(k+1)||+||B||||X(k)–X*||**迭代法构造收敛条件(局部vs全局)中止准则统一的不动点框架定义4.1

A=(aij)n×n,如果则称A为严格对角占优阵。*性质2

A是严格对角占优矩阵,则D-L和D-U是严格对角占优矩阵。性质1

A是严格对角占优矩阵,则。记A=D-L-U性质3

A是严格对角占优矩阵,则当时则有和是严格对角占优矩阵。

严格对角占优矩阵定理4.3

若Ax=b的系数矩阵A是严格对角占优矩阵,则Jacobi迭代和Gauss-Seidel迭代收敛。证:由于矩阵A

严格对角占优*所以故Jacobi迭代矩阵BJ=D-1(D–A)第i行绝对值求和故Jacobi迭代

X(k+1)=BJX(k)+f

收敛。*推论A是严格对角占优矩阵,则A非奇异。Gauss-Seidel迭代矩阵为BGS=(D-L)-1U。由于A对角占优所以矩阵

也是对角占优的,则矩阵一定非奇异,矛盾。注释:考虑反证法新证:定理4.4方程组

Ax=b

中,若A是实对称正定矩阵,则Gauss-Seidel迭法收敛。证明:由

A=D–L–LT

BGS=(D–L)-1LTA正定,故

p=xTDx>0,记

xTLTx=a,则有xTAx=xT(D–L–LT)x=p–a–a=p–2a>0设

为BGS的任一特征值,x为其特征向量,则*所以迭代矩阵BGS的谱半径

(BGS)<1,从而当A是实对称正定矩阵时,

Gauss-Seidel迭代法收敛。*定理

方程组

Ax=b

中,若A是实对称正定矩阵,则Jacobi迭法收敛？(反例)定理4.5

设BJ元素均非负,则下列关系有且只有一个成立:参考文献:P.Stein,R.L.Rosenberg,Onthesolutionoflinearsimultaneousequationsbyiteration,J.LondonMath.Soc.**迭代法构造收敛条件(局部vs全局)中止准则统一的不动点框架直接法vs迭代法

基于高斯消元法的直接方法提供了有限步内就可以得到解的方法。*

寻求迭代方法的理由是什么呢？十阶百阶万阶百万阶亿阶小不大较大大超大迭代法优势1:

直接法运行一个完整LU分解才能得到解,迭代法从初始解开始每步对其加工改善使其更加精确。问题是在用户容忍的范围内需要多少步才能得到收敛性？*注释:运行一个完整LU分解花费O(n3)阶运算,一般地,迭代法每次迭代花费O(n2)阶运算,即每次迭代仅需要完整LU分解花费的一部分。迭代法优势2:

求解稀疏方程组是使用迭代法的主要理由。*注释:系数矩阵稀疏度为n,则求解稀疏方程组迭代法每步迭代花费O(n)阶运算。求解特殊结构方程组(如Toeplitz)迭代法每步迭代花费O(nlogn)阶运算。Poisson方程:令

h=1/(n+1),xi=ih(i

=0,1,···,n+1)记

ui=u(xi),(i

=0,1,···,n+1)迭代计算格式:差分格式:n=10000;e=ones(n,1);A=spdiags([e-2*ee],-1:1,n,n),spy(A)HB矩阵稀疏模式来源

TheoriginalHarwell-Boeingcollection来源:TheUniversityofFloridaSparseMatrixCollectionFreeFieldTechnologies矩阵稀疏模式来源3Dvibro-acousticproblem,

aircraftenginenacellevanHeukelum矩阵稀疏模式来源DNAelectrophoresisgaron2矩阵稀疏模式2DFEM,Navier-Stokes,CFD

n=10000;e=ones(n,1);n2=n/2;a=spdiags([-e3*e-e],-1:1,n,n);c=spdiags([e/2],0,n,n);c=fliplr(c);a=a+c;a(n2+1,n2)=-1;a(n2,n2+1)=-1;b=zeros(n,1);b(1)=2.5;b(n)=2.5;b(2:n-1)=1.5;b(n2:n2+1)=1;%%%JacobiMethod(IterativeMethod)ticd=diag(a);%extractdiagonalofar=a-diag(d);%ristheremainderx=zeros(n,1);%initializevectorxforj=1:50%loopforJacobiiterationx=(b-r*x)./d;endt1=toctic,x=full(a)\b,t2=toc%%

BackSlash(DirectMethod)Demo1

helpsparfunMatlab与大数据处理Elementarysparsematrices(例如spdiag