7線性方程組迭代法3省公開課一等獎(jiǎng)全國示范課微課金獎(jiǎng)?wù)n件

§4迭代法收斂性/*ConvergenceofIterativemethods*/收斂條件充分條件:||B||<1必要條件:？定義設(shè)：AAkk=

lim是指ijkijkaa=

)(lim對全部1

i,j

n成立。等價(jià)于對任何算子范數(shù)有第1頁對任意非零向量成立§4ConvergenceofIterativemethods定理設(shè)存在唯一解，則從任意出發(fā)，迭代收斂

0

kB證實(shí)：Bk

0||Bk||0“”：對任意非零向量有“”：取則第i位對任意非零向量成立從任意出發(fā)，記，則ask

收斂Buthey,youdon’tseriouslyexpectmetocomputeBk

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

Bk0

(B)<1證實(shí)：“

”若

是Beigenvalue,則

k是Bkeigenvalue。

則[

(B)]k=[max|

|]k=|

mk|

(Bk)

||Bk||0

(B)<1

“

”首先需要一個(gè)引理/*Lemma*/對任意

>0,存在算子范數(shù)||·||使得||A||

(A)+

。

由

(B)<1可知存在算子范數(shù)||·||使得||B||<1。||Bk||||B||k0ask

Bk

0迭代從任意向量出發(fā)收斂Bk0

(B)<1證實(shí)：對A做Jordan分解，有，其中，，

i為Aeigenvalue。令，則有易證：是由導(dǎo)出算子范數(shù)。所以只要取

<

，就有||A||

<

(A)+

。第3頁§4ConvergenceofIterativemethods定理

（充分條件）若存在一個(gè)矩陣范數(shù)使得||B||=q<1,則迭代收斂，且有以下誤差預(yù)計(jì)：①②證實(shí)：①

②第4頁§4ConvergenceofIterativemethods定理

（充分條件）若A為嚴(yán)格對角占優(yōu)陣

/*strictlydiagonallydominantmatrix*/則解Jacobi和Gauss-Seidel迭代均收斂。證實(shí)：首先需要一個(gè)引理/*Lemma*/若A為SDD陣，則det(A)0，且全部aii0。證實(shí)：若不然，即det(A)=0，則A是奇異陣。存在非零向量使得記顯然我們需要對Jacobi迭代和Gauss-Seidel迭代分別證實(shí)：任何一個(gè)|

|1都不可能是對應(yīng)迭代陣特征根，即|IB|0

。Jacobi:BJ=D

1(L+U)aii0假如|

|1則是SDD陣|IB|0

HW:p.76#1關(guān)于Gauss-Seidel迭代證實(shí)與這類似(p.73)。另一個(gè)證實(shí)引理方法利用Ger?gorinDiscTheorem(p.72)。第5頁§5松弛法/*RelaxationMethods*/換個(gè)角度看Gauss-Seidel方法：其中ri(k+1)=/*residual*/相當(dāng)于在基礎(chǔ)上加個(gè)余項(xiàng)生成。下面令，希望經(jīng)過選取適當(dāng)

來加速收斂，這就是松弛法/*RelaxationMethods*/

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

<1低松弛法

/*Under-Relaxationmethods*/

=1Gauss-Seidel法

>1(漸次)超松弛法

/*SuccessiveOver-Relaxationmethods*/第6頁§5RelaxationMethods寫成矩陣形式：松弛迭代陣定理設(shè)A可逆，且aii0，松弛法從任意出發(fā)對某個(gè)

收斂

(H

)<1。Ooooohcomeon!It’swaytoocomplicatedtocomputeH

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

（Kahan必要條件）設(shè)A可逆，且aii0，松弛法從任意出發(fā)收斂

0<

<2。證實(shí)：從出發(fā)利用，而且收斂|

i|<1總成立可知收斂

|det(H

)|<1|det(H

)|=|1

|n<10<

<2

第8頁§5RelaxationMethods定理

（Ostrowski-Reich充分條件）若A對稱正定，且有0<

<2，則松弛法從任意出發(fā)收斂。Q:Whatfactordeterminesthespeedofconvergence?考查迭代：設(shè)B有特征根

1、…、

n對應(yīng)n個(gè)線性無關(guān)特征向量。則從任意出發(fā)，可表為線性組合，即~A:

Thesmaller

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

使得

(H

)

最小。第9頁§5RelaxationMethods定理若A為對稱正定三對角陣，則且SOR最正確松弛因子

/*optimalchoiceof

forSORmethod*/為，此時(shí)。例：，考慮迭代格式問：

取何值可使迭代收斂？

取何值時(shí)迭代收斂最快？解：考查B=I+

A特征根

1=1+

,

2=1+3

收斂要求

(B)<1-2/3<

<0

(B)=

max{|1+

|,|1+3

|}

當(dāng)

取何值時(shí)最??？-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