数值分析课件：NA04c

§4迭代法的收敛性/*ConvergenceofIterativemethods*/的收敛条件充分条件:||B||<1必要条件:？定义设：AAkk=lim是指ijkijkaa=)(lim对所有1i,jn

成立。等价于对任何算子范数有对任意非零向量成立§4ConvergenceofIterativemethods定理设存在唯一解，则从任意出发，迭代收敛0kB证明：Bk

0||Bk||0“”：对任意非零向量有“”：取则第i位对任意非零向量成立从任意出发，记，则ask

收敛

Buthey,youdon’tseriouslyexpectmetocomputeBk

wheneverIwanttochecktheconvergence,doyou?§4ConvergenceofIterativemethods定理

Bk0(B)<1证明：“”若是B

的eigenvalue,则k

是Bk

的eigenvalue。

则[(B)]k=[max||]k=|mk|(Bk)

||Bk||0(B)<1“”首先需要一个引理/*Lemma*/对任意>0,存在算子范数||·||使得||A||(A)+

。

由(B)<1可知存在算子范数||·||使得||B||<1。||Bk||||B||k0ask

Bk

0迭代从任意向量出发收敛Bk0(B)<1证明：对A

做Jordan分解，有，其中，，i

为A的eigenvalue。

令，则有易证：是由导出的算子范数。所以只要取<，就有||A||<(A)+

。§4ConvergenceofIterativemethods定理

（充分条件）若存在一个矩阵范数使得||B||=q<1,

则迭代收敛，且有下列误差估计：①②证明：①②§4ConvergenceofIterativemethods定理

（充分条件）若A

为严格对角占优阵

/*strictlydiagonallydominantmatrix*/

则解的Jacobi和Gauss-Seidel迭代均收敛。证明：首先需要一个引理/*Lemma*/若A

为SDD阵，则det(A)0，且所有的aii

0。证明：若不然，即det(A)=0，则A

是奇异阵。存在非零向量使得记显然我们需要对Jacobi迭代和Gauss-Seidel迭代分别证明：任何一个||1都不可能是对应迭代阵的特征根，即|IB|0

。Jacobi:BJ=D1(L+U)aii0如果||1则是SDD阵|IB|0HW:p.135#7关于Gauss-Seidel迭代的证明与此类似。§5松弛法/*RelaxationMethods*/换个角度看Gauss-Seidel方法：其中ri(k+1)=/*residual*/相当于在的基础上加个余项生成。下面令，希望通过选取合适的来加速收敛，这就是松弛法/*RelaxationMethods*/

。iikikikiarxx)1()()1(+++=w0<<1低松弛法

/*Under-Relaxationmethods*/=1Gauss-Seidel法>1(渐次)超松弛法

/*SuccessiveOver-Relaxationmethods*/§5RelaxationMethods写成矩阵形式：松弛迭代阵定理设A

可逆，且aii0，松弛法从任意出发对某个收敛(H)<1。

Ooooohcomeon!It’swaytoocomplicatedtocomputeH,andyoucan’texpectmetogetitsspectralradiusright!There’sgottabeashortcut…§5RelaxationMethods定理

（Kahan

必要条件）设A

可逆，且aii0，松弛法从任意出发收敛0<<2。证明：从出发利用，而且收敛|i|<1总成立可知收敛|det(H)|<1|det(H)|=|1|n<10<<2

§5RelaxationMethods定理

（Ostrowski-Reich充分条件）若A对称正定，且有0<<2，则松弛法从任意出发收敛。Q:Whatfactordeterminesthespeedofconvergence?考察迭代：设B有特征根1、…、n

对应n个线性无关的特征向量。则从任意出发，可表为的线性组合，即~A:

Thesmaller

(B)is,thefastertheiterationswillconverge.对于SOR法，希望找使得(H)

最小。§5RelaxationMethods定理若A

为对称正定三对角阵，则且SOR的最佳松弛因子

/*optimalchoiceofforSORmethod*/为，此时。例：，考虑迭代格式问：取何值可使迭代收敛？

取何值时迭代收敛最快？解：考察B=I+A

的特征根1=1+,2=1+3

收敛要求(B)<1-2/3<<0(B)=

max{|1+

|,|1+3

|}

当取何值时最小？-2/3-1/30=-1/2HW:p.136#11§5RelaxationMethodsLab08.SORMethod UsetheSORmethodtosolveagivenn×n

linearsystemwithaninitialapproximationandasetof’s.

Input Thereareseveralsetsofinputs.Foreachset: The1stlinecontainsaninteger100

n

0whichisthesizeofamatrix.n=1signalstheendoffile. Thefollowingnlinescontaintheaugmentedmatrixinthefollowingformat:Thenumbersareseparatedbyspacesandnewlines.ThenextlinecontainsarealnumberTOL,whichisthetolerancefor||·||norm,andanintegerN

0whichisthemaximumnumberofiterations.Thelastlineofeachtestcasecontainsanintegerm>0,followedbymreal’s.§5RelaxationMethodsOutput

(representsaspace)Foreach,theremustbeasetofoutputsinthefollowingformat:

The1stlinecontainsanandthecorrespondingnumberofiterationstaken.IntheCprintf:fprintf(outfile,"%4.2f%d\n",omega,iter_no);

Thecorrespondingsolutionorerrormessagesaretobeprintedasthefollowing:

EachentryofthesolutionistobeprintedasintheCfprintf:fprintf(outfile,"%12.8f\n",x);

IfthematrixAhasazerocolumn,printthemessage“Matrixhasazerocolumn.Nouniquesolutionexists.\n”.

IfthemethodfailstogiveasolutionafterNiterations,printthemessage“Maximumnumberofiterationsexceeded.\n”.

Ifthereisanentryofthatisoutoftherange[