7线性方程组迭代法3省公开课一等奖全国示范课微课金奖课件

§4迭代法收敛性/*ConvergenceofIterativemethods*/收敛条件充分条件:||B||<1必要条件:？定义设：AAkk=

lim是指ijkijkaa=

)(lim对全部1

i,j

n成立。等价于对任何算子范数有第1页对任意非零向量成立§4ConvergenceofIterativemethods定理设存在唯一解，则从任意出发，迭代收敛

0

kB证实：Bk

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

收敛Buthey,youdon’tseriouslyexpectmetocomputeBk

wheneverIwanttochecktheconvergence,doyou?第2页§4ConvergenceofIterativemethods定理

Bk0

(B)<1证实：“

”若

是Beigenvalue,则

k是Bkeigenvalue。

则[

(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为Aeigenvalue。令，则有易证：是由导出算子范数。所以只要取

<

，就有||A||

<

(A)+

。第3页§4ConvergenceofIterativemethods定理

（充分条件）若存在一个矩阵范数使得||B||=q<1,则迭代收敛，且有以下误差预计：①②证实：①

②第4页§4ConvergenceofIterativemethods定理

（充分条件）若A为严格对角占优阵

/*strictlydiagonallydominantmatrix*/则解Jacobi和Gauss-Seidel迭代均收敛。证实：首先需要一个引理/*Lemma*/若A为SDD阵，则det(A)0，且全部aii0。证实：若不然，即det(A)=0，则A是奇异阵。存在非零向量使得记显然我们需要对Jacobi迭代和Gauss-Seidel迭代分别证实：任何一个|

|1都不可能是对应迭代阵特征根，即|IB|0

。Jacobi:BJ=D

1(L+U)aii0假如|

|1则是SDD阵|IB|0

HW:p.76#1关于Gauss-Seidel迭代证实与这类似(p.73)。另一个证实引理方法利用GeršgorinDiscTheorem(p.72)。第5页§5松弛法/*RelaxationMethods*/换个角度看Gauss-Seidel方法：其中ri(k+1)=/*residual*/相当于在基础上加个余项生成。下面令，希望经过选取适当

来加速收敛，这就是松弛法/*RelaxationMethods*/

。iikikikiarxx)1()()1(+++=w0<

<1低松弛法

/*Under-Relaxationmethods*/

=1Gauss-Seidel法

>1(渐次)超松弛法

/*SuccessiveOver-Relaxationmethods*/第6页§5RelaxationMethods写成矩阵形式：松弛迭代阵定理设A可逆，且aii0，松弛法从任意出发对某个

收敛

(H

)<1。Ooooohcomeon!It’swaytoocomplicatedtocomputeH

,andyoucan’texpectmetogetitsspectralradiusright!There’sgottabeashortcut…第7页§5RelaxationMethods定理

（Kahan必要条件）设A可逆，且aii0，松弛法从任意出发收敛

0<

<2。证实：从出发利用，而且收敛|

i|<1总成立可知收敛

|det(H

)|<1|det(H

)|=|1

|n<10<

<2

第8页§5RelaxationMethods定理

（Ostrowski-Reich充分条件）若A对称正定，且有0<

<2，则松弛法从任意出发收敛。Q:Whatfactordeterminesthespeedofconvergence?考查迭代：设B有特征根

1、…、

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

Thesmaller

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

使得

(H

)

最小。第9页§5RelaxationMethods定理若A为对称正定三对角阵，则且SOR最正确松弛因子

/*optimalchoiceof

forSORmethod*/为，此时。例：，考虑迭代格式问：

取何值可使迭代收敛？

取何值时迭代收敛最快？解：考查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.77#5#7第10页§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.第11页§5RelaxationMethodsOutput(

representsaspace)Foreach

,theremustbeasetofoutputsinthefollowingformat:

The1stlinecontainsan

andthecorrespondingnumberofiterationstaken.IntheCprintf:fprintf(outfile,"%4.2f

%d\n",omega,iter_no);Thecorrespondingsolutionorerrormessagesaretobeprintedasthefollowing:

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

IfthematrixAhasazerocolumn,printthemessage“Matrix

has

a

zero

column.

No

unique

solution

exists.\n”.

IfthemethodfailstogiveasolutionafterNiterations,printthemessage“Maximum

number

of

iterations

exceeded.\n”.

Ifthereisanentryofthatiso