第7章非線性方程求根

第7章非線性方程求根方程是在科學(xué)研究中不可缺少的工具方程求解是科學(xué)計(jì)算中一個(gè)重要的研究對(duì)象幾百年前就已經(jīng)找到了代數(shù)方程中二次至五次方程的求解公式但是,對(duì)于更高次數(shù)的代數(shù)方程目前仍無(wú)有效的精確解法對(duì)于無(wú)規(guī)律的非代數(shù)方程的求解也無(wú)精確解法因此,研究非線性方程的數(shù)值解法成為必然設(shè)非線性方程--------(1)本節(jié)主要研究單根區(qū)間上的求解方法一、簡(jiǎn)單迭代法(基本迭代法)--------(2)將非線性方程(1)化為一個(gè)同解方程繼續(xù)--------(3)稱(chēng)(3)式為求解非線性方程(2)的簡(jiǎn)單迭代法則稱(chēng)迭代法(3)收斂,否則稱(chēng)為發(fā)散--------(4)如果將(2)式表示為與方程(2)同解收斂例1.解:(1)將原方程化為等價(jià)方程發(fā)散顯然迭代法發(fā)散(2)如果將原方程化為等價(jià)方程仍取初值x2=0.9644x3=0.9940x4=0.9990x5=0.9998x6=1.0000x7=1.0000依此類(lèi)推,得已經(jīng)收斂,故原方程的解為同樣的方程不同的迭代格式有不同的結(jié)果什么形式的迭代法能夠收斂呢?迭代函數(shù)的構(gòu)造有關(guān)定理1.--------(5)--------(6)--------(7)(局部收斂性)證:由條件(1)由根的存在定理,由由微分中值定理證畢.定理1指出,由(6)式,只要因此,當(dāng)?shù)涂梢越K止,只要構(gòu)造的迭代函數(shù)滿足此時(shí)雖收斂但不一定是唯一根--------(8)例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-006<1e-6因此原方程的解為x7=0.090525x1=0.1000000x2=0.0894829x3=0.0906391x4=0.0905126x5=0.0905265x6=0.0905250x7=0.0905251由定理1的(7)式出,迭代法收斂就越快定義1.--------(9)不可能直接確定定理2.

例3.為線性收斂證明:所以例4.至少是平方收斂的由定義1注意例4與例3的迭代法是相同的,兩例有何區(qū)別?證明:令則所以由定理2該迭代法至少是平方收斂的二、Newton迭代法如果將非線性方程令化為等價(jià)方程如果令即則于是取--------(10)--------(11)--------(12)(12)式稱(chēng)為Newton迭代法參見(jiàn)例4，可知Newton迭代法至少平方收斂局部收斂性例5.用Newton迭代法求方程的根:解:由Newton迭代法x0=0.5;x1=0.3333333333x2=0.3472222222x3=0.3472963532x4=0.3472963553迭代四次精度達(dá)10-8

Newtonddf.mNewton迭代法需要求每個(gè)迭代點(diǎn)處的導(dǎo)數(shù)復(fù)雜！--------(12)--------(13)這種格式稱(chēng)為簡(jiǎn)化Newton迭代法精度稍低三、Newton迭代法的變形則Newton迭代法變?yōu)?-------(14)這種格式稱(chēng)為弦截法收斂階約為1.618幾何意義例6.用簡(jiǎn)化Newton法和弦截法解例(5)中方程的根，解:由簡(jiǎn)化Newton法并和Newton迭代法比較由弦截法x0=0.5x1=0.3333333333x2=0.3497942387x3=0.3468683325x4=0.3473702799x5=0.3472836048x6=0.3472985550x7=0.3472959759x8=0.3472964208x9=0.3472963440x10=0.3472963572x11=0.3472963553x0=0.5;x1=0.4;x2=0.3430962343x3=0.3473897274x4=0.3472965093x5=0.3472963553x6=0.3472963553簡(jiǎn)化Newton法由弦截法要達(dá)到精度10-8

簡(jiǎn)化Newton法迭代11次弦截法迭代5次Newton迭代法迭代4次無(wú)論前面哪種迭代法：Newton迭代法簡(jiǎn)化Newton法弦截法Newton迭代法x0=2x1=-3.54x2=13.95x3=-279.34x4=122017是否收斂均與初值的位置有關(guān)如x0=1x1=-0.5708x2=0.1169x3=-0.0011x4=7.9631e-010x5=0收斂發(fā)散--------(15)這種方法稱(chēng)為Newton下山法，例7.解:1.先用Newton迭代法x4=9.70724x5=6.54091x6=4.46497x7=3.13384x8=2.32607x9=1.90230x10=1.75248x11=1.73240x12=1.73205x13=1.73205迭代13次才達(dá)到精度要求2.用Newton下山法,結(jié)果如下k=0x0=-0.99fx0=0.666567k=1x1=32.505829f(x)=11416.4w=0.5x1=15.757915f(x)=1288.5w=0.25x1=7.383958f(x)=126.8w=0.125x1=3.196979f(x)=7.69w=0.0625x1=1.103489f(x)=-0.655k=2x2=4.115071f(x)=19.1w=0.5x2=2.60928f(x)=3.31w=0.25x2=1.85638f(x)=0.27k=3x3=1.74352f(x)=0.023k=4x4=1.73216f(x)=0.00024k=5x5=1.73205f(x)=0.00000k=6x6=1.73205f(x)=0.000000四、多根區(qū)間上的逐次逼近法有唯一根有多根所有根均為單根有重根用迭代法求解然后在每個(gè)區(qū)間上判斷是否有根若成立統(tǒng)計(jì)根的個(gè)數(shù)則所有的有根區(qū)間均為單根區(qū)間則繼續(xù)對(duì)分區(qū)間,并重新判斷直到找到所有根的所在區(qū)間然后在每個(gè)有根區(qū)間進(jìn)行求根可得一系列的小區(qū)間和中點(diǎn)小區(qū)間中點(diǎn)顯然每個(gè)小區(qū)間都有單根搜索法—二分法例8.解:由于可知方程的解在區(qū)間[0,10]內(nèi)將區(qū)間[0,10]等分成三等份[0,3.33][3.33,6.67][6.67,10][0,3.33]內(nèi)至少有一個(gè)根[5,6.67][3.33,5]將[3.33,6.67]再分成兩個(gè)區(qū)間[5,6.67]內(nèi)至少有一個(gè)根[3.33,5]內(nèi)至少有一個(gè)根[0,3.33][5,6.67][3.33,5]因此找到了三個(gè)有單根的區(qū)間依此類(lèi)推結(jié)果為對(duì)分故有且由例3.對(duì)于Newton迭代法趨于零Newton迭代法也只是線性收斂此時(shí)Newton迭代法可能不收斂考察函數(shù)而應(yīng)該用定義求導(dǎo)Tailor展開(kāi)所以由定理2，迭代法至少是二階收斂二、非線性方程迭代法的加速對(duì)于迭代法上式的迭代函數(shù)令迭代改變量即求導(dǎo)并令----(9)得因此有松弛迭代法:--------(10)從后面的例子可以看出,加速效果是明顯的甚至一些不收斂的迭代法經(jīng)過(guò)松弛加速后也能收斂不方便中值定理差商近似代替導(dǎo)數(shù)即于是可以得到迭代格式:其中-------(11)上組公式稱(chēng)為Altken公式或Altken加速將(11)式綜合后可得一個(gè)解析式表示的迭代法:----(12)上式稱(chēng)為Steffensen迭代法Altken公式與Steffensen公式是等價(jià)的加速效果也是很明顯的例2中將比較不同加速方法例2.對(duì)迭代格式進(jìn)行加速解方程組解:x0=0.5x1=0.375x2=0.3509115x3=0.3477369x4=0.3473496x5=0.3473028x6=0.3472971x7=0.3472964(1)直接使用迭代格式迭代7次,得到滿足精度的解(2)對(duì)迭代格式進(jìn)行松弛加速x0=0.5x1=0.3333333x2=0.3472222x3=0.3472964x4=0.3472964迭代4次,得到滿足精度的解(3)對(duì)迭代格式進(jìn)行Altken加速(11)式x0=0.5x1=0.3451613x2=0.3472961x3=0.3472964迭代3次,得到滿足精度的解從以上3種結(jié)果可見(jiàn),迭代法加速技術(shù)效果比較明顯迭代格式顯然不收斂x0=1.5x1=1.5350706x2=1.5321124x3=1.5320889x4=1.5320889迭代4次,得到滿足精度的解對(duì)迭代格式進(jìn)行松弛加速x=1.5x=1.5333333x=1.5320906x=1.5320889x=1.5320889迭代4次,得到滿足精度的解對(duì)迭代格式進(jìn)行Altken加速可見(jiàn)加速技術(shù)可能將不收斂的迭代法加速為收斂§3Fixed-PointIteration改進(jìn)、加速收斂/*acceleratingconvergence*/

待定參數(shù)法：若

|g’(x)|1，則將x=g(x)等價(jià)地改造為求K，使得例：求在(1,2)的實(shí)根。如果