不動(dòng)點(diǎn)迭代法及其收斂定理ppt課件.ppt

6.2不動(dòng)點(diǎn)迭代法及其收斂定理,第6章方程與方程組的迭代解法,一、迭代法原理,-(2),將非線性方程f(x)=0化為一個(gè)同解方程,繼續(xù),-(3),稱(3)式為求解非線性方程(2)的簡單迭代法,則稱迭代法(3)收斂,否則稱為發(fā)散,-(4),例1.,解:,(1)將原方程化為等價(jià)方程,顯然迭代法發(fā)散,(2)如果將原方程化為等價(jià)方程,仍取初值,x2=0.9644x3=0.9940 x4=0.9990 x5=0.9998x6=1.0000 x7=1.0000,依此類推,得,已經(jīng)收斂,故原方程的解為,同樣的方程不同的迭代格式有不同的結(jié)果,什么形式的迭代法能夠收斂呢?,迭代函數(shù)的構(gòu)造有關(guān),如果將(2)式表示為,與方程(2)同解,收斂,發(fā)散,定理1.,-(5),-(6),-(7),(局部收斂性),迭代過程的收斂性,證:,由條件(1),由根的存在定理,證:,由,由微分中值定理,證畢.,定理1指出,只要構(gòu)造的迭代函數(shù)滿足,由(6)式,只要,因此,當(dāng),迭代就可以終止,-(8),定義1：如果存在的某個(gè)鄰域，使迭代過程對(duì)于任意初值均收斂，則稱迭代過程在根鄰近具有局部收斂性。,例2.,用迭代法求方程的近似解,精確到小數(shù)點(diǎn)后6位,解:,本題迭代函數(shù)有兩種構(gòu)造形式,因此采用迭代函數(shù),d1=0.1000000d2=-0.0105171d3=0.1156e-002d4=-0.1265e-003d5=0.1390e-004d6=-0.1500e-005d7=0.1000e-006,由于|d7|=0.1000e-0061),則利用m構(gòu)造新的迭代公式:此時(shí),至少2階收斂.不實(shí)用:m往往不確定.方法二.取,再對(duì)函數(shù)F(x)用Newton迭代:此時(shí),X*為F(x)的單根,所以是2階收斂.但要用到二階導(dǎo)數(shù).,6.Newton法的改進(jìn)(I)-重根情形,Newton迭代法,需要求每個(gè)迭代點(diǎn)處的導(dǎo)數(shù)f(xk),復(fù)雜！,這種格式稱為簡化Newton迭代法,精度稍低,6.Newton法的改進(jìn)(II),則Newton迭代法變?yōu)?這種格式稱為弦截法,收斂階約為1.618,例4用簡化Newton法和弦截法解下面方程的根，并和Newton迭代法比較,解:,由簡化Newton法,由弦截法,由Newton迭代法,x0=0.5x1=0.3333333333x2=0.3497942387x3=0.3468683325x4=0.3473702799x5=0.3472836048x6=0.3472985550 x7=0.3472959759x8=0.3472964208x9=0.3472963440 x10=0.3472963572x11=0.3472963553,x0=0.5;x1=0.4;x2=0.3430962343x3=0.3473897274x4=0.3472965093x5=0.3472963553x6=0.3472963553,簡化Newton法,由弦截法,要達(dá)到精度10-8,簡化Newton法迭代11次,弦截法迭代5次,Newton迭代法迭代4次,x0=0.5;x1=0.3333333333x2=0.3472222222x3=0.3472963532x4=0.3472963553,由Newton迭代法,無論哪種迭代法：,Newton迭代法,簡化Newton法,弦截法,用Newton迭代法求解:,x0=2x1=-3.54x2=13.95x3=-279.34x4=122017,是否收斂均與初值的位置有關(guān).,例:,x0=1x1=-0.5708x2=0.1169x3=-0.0011x4=7.963110-10 x5=0,收斂,發(fā)散,迭代法的局部收斂性,6.Newton法的改進(jìn)(III):牛頓下山法,一般地說，牛頓法的收斂性依賴于初值的選取，如果偏離較遠(yuǎn)，則牛頓法可能發(fā)散。為了防止發(fā)散，通常對(duì)迭代過程再附加一項(xiàng)要求，即保證函數(shù)值單調(diào)下降：滿足這項(xiàng)要求的算法稱為下山法。牛頓下山法采用以下迭代公式：其中稱為下山因子。,牛頓下山法只有線性收斂.,例7.,解:,1.先用Newton迭代法,x4=9.70724x5=6.54091x6=4.46497x7=3.13384x8=2.32607x9=1.90230 x10=1.75248x11=1.73240 x12=1.73205x13=1.73205,迭代13次才達(dá)到精度要求,2.用Newton下山法,結(jié)果如下,故有,且,由例3.,對(duì)于Newton迭代法,趨于零,Newton迭代法也只是線性收斂,此時(shí)Newton迭代法可能不收斂,由定理2，迭代法,至少是二階收斂,NumericalValueAnalysis,Steffensen方法,第6章方程與方程組的迭代解法,簡單迭代公式的加速,設(shè)是根的某個(gè)近似值，用迭代公式校正一次得假設(shè)，則有據(jù)此可導(dǎo)出如下加速公式：其一步分為兩個(gè)環(huán)節(jié)：迭代:改進(jìn):,埃特金迭代法求方程的實(shí)根,定理設(shè)序列線性收斂于x*,則的Aitken序列存在,且