非線性方程求根

非線性方程求根第1頁，共91頁，2023年，2月20日，星期三問題驅(qū)動(dòng)：全球定位系統(tǒng)（GPS）

人類對導(dǎo)航和定位的需求是伴隨著人類整個(gè)文明歷史的進(jìn)步而發(fā)展的，中國古代“四大發(fā)明”之一的指南針是最早的定位儀器和系統(tǒng)，其后還有經(jīng)緯儀以及近代的雷達(dá)。如圖9.1.1所示全球定位系統(tǒng)（GPS）是基于衛(wèi)星的導(dǎo)航系統(tǒng)，最早由美國和前蘇聯(lián)分別在80年代研制，并于1993年正式投入使用?，F(xiàn)代社會(huì)中全球定位系統(tǒng)越來越深入到人們生活的方方面面。例如市場上出售的手持型GPS，定位的精度可以達(dá)到10米以內(nèi)，這無疑給旅行者提供了方便；安裝有GPS的兒童手表，家長在家里的計(jì)算機(jī)上可以追蹤到孩子的位置，防止兒童走失；安裝有GPS系統(tǒng)的汽車可以幫助新司機(jī)辨識道路等等。第2頁，共91頁，2023年，2月20日，星期三圖6.1.1衛(wèi)星定位示意圖

美國和前蘇聯(lián)的GPS都包括有24顆衛(wèi)星，它們不斷地向地球發(fā)射信號報(bào)告當(dāng)前位置和發(fā)出信號的時(shí)間，衛(wèi)星分布如圖6.1.2所示。它的基本原理是：在地球的任何一個(gè)位置，至少同時(shí)收到4顆以上衛(wèi)星發(fā)射的信號。發(fā)射的信號，

設(shè)地球上一個(gè)點(diǎn)R，同時(shí)收到衛(wèi)星

第3頁，共91頁，2023年，2月20日，星期三假設(shè)接收的信息如表6.1.1所示。請?jiān)O(shè)法確定R點(diǎn)的位置。圖6.1.2衛(wèi)星分布圖表6.1.1GPS導(dǎo)航問題可歸結(jié)為求解非線性代數(shù)數(shù)方程組,當(dāng)時(shí)就是單個(gè)方程.（6.1.1）

第4頁，共91頁，2023年，2月20日，星期三。.其中，可以是代數(shù)方程，也可以是超越方程。使成立的x

值稱為方程的根，或稱為計(jì)算中，如電路和電力系統(tǒng)計(jì)算、非線性力學(xué)、非線性微（積分）方程、非線性規(guī)劃（優(yōu)化）等眾多領(lǐng)域中，問題的求解和模擬最終往往都要解決求根或優(yōu)化問題。前一種情形要求出方程（組）的根；后一種情形則要求找出函數(shù)取最大或最小的點(diǎn)。即使是對實(shí)驗(yàn)數(shù)據(jù)進(jìn)行擬合或數(shù)值求解微分方程，也總是將問題簡化成上述兩類問題。上述除少數(shù)特殊方程外，大多數(shù)非線性代數(shù)方程（組）很難使用解析法求解精確解，一般需要通過一些數(shù)值方法逼近方程的解。這里主要介紹單個(gè)方程的數(shù)值解法，方程組也可以采用類似的方法，將放在后面討論。的零點(diǎn)。科學(xué)與工程第5頁，共91頁，2023年，2月20日，星期三1．根的存在性。方程有沒有根？如果有，有幾個(gè)根？2．根的搜索。這些根大致在哪里？如何把根隔離開？3．根的精確化。f(x)=0（6.2.1）第6頁，共91頁，2023年，2月20日，星期三1.根的存在性定理1：設(shè)函數(shù)f(x)在區(qū)間[a,b]上連續(xù)，如果f(a)

f(b)<0，

則方程f(x)=0在[a,b]內(nèi)至少有一實(shí)根x*。

定義：如果存在使得，則稱為方程（6.2.1）的根或函數(shù)的零點(diǎn)。第7頁，共91頁，2023年，2月20日，星期三m重根若其中，為正整數(shù)，則當(dāng)m=1時(shí)，稱為方程（6.2.1）的單根或函數(shù)的單零點(diǎn)。稱為方程（6.2.1）的m重根或函數(shù)的m重零點(diǎn)。當(dāng)時(shí)，第8頁，共91頁，2023年，2月20日，星期三2.根的搜索(1)圖解法（利用作圖軟件如Matlab)(2)解析法(3)近似方程法(4)定步長搜索法第9頁，共91頁，2023年，2月20日，星期三abx*f(x)1．畫出f(x)的略圖，從而看出曲線與x軸交點(diǎn)的位置。2．從左端點(diǎn)x=a出發(fā)，按某個(gè)預(yù)先選定的步長h一步一步地向右跨，每跨一步都檢驗(yàn)每步起點(diǎn)x0和終點(diǎn)x0+h的函數(shù)值，若那么所求的根x*必在x0與x0+h之間，這里可取x0或x0+h作為根的初始近似。第10頁，共91頁，2023年，2月20日，星期三

開始讀入a,ha

x0f(x0)

y0x0+h

x0f(x0)

y0>0打印結(jié)束否是繼續(xù)掃描

第11頁，共91頁，2023年，2月20日，星期三例1：考察方程x00.51.01.5f(x)的符號－－－＋第12頁，共91頁，2023年，2月20日，星期三abx1x2ab或不能保證

x

的精度x*2xx*§1二分法第13頁，共91頁，2023年，2月20日，星期三

執(zhí)行步驟1．計(jì)算f(x)在有解區(qū)間[a,b]端點(diǎn)處的值，f(a)，f(b)。2．計(jì)算f(x)在區(qū)間中點(diǎn)處的值f(x1)。3．判斷若f(x1)=0，則x1即是根，否則檢驗(yàn)：（1）若f(x1)與f(a)異號，則知解位于區(qū)間[a,x1]，

b1=x1,a1=a;（2）若f(x1)與f(a)同號，則知解位于區(qū)間[x1,b]，

a1=x1,b1=b。反復(fù)執(zhí)行步驟2、3，便可得到一系列有根區(qū)間：

第14頁，共91頁，2023年，2月20日，星期三4、當(dāng)時(shí)，停止；即為根的近似。當(dāng)時(shí)，，即這些區(qū)間必將收縮于一點(diǎn)，也就是方程的根。在實(shí)際計(jì)算中，只要的區(qū)間長度小于預(yù)定容許誤差就可以停止搜索，即然后取其中點(diǎn)作為方程的一個(gè)根的近似值。注：第15頁，共91頁，2023年，2月20日，星期三例2證明方程存在唯一的實(shí)根用二分法求出此根，要求誤差不超過。解：記，則對任意

，因而，是嚴(yán)格單調(diào)的，最多有一個(gè)根，所以，有唯一實(shí)根又因?yàn)?/p>

第16頁，共91頁，2023年，2月20日，星期三用二分法求解，要使，只要解得，取。所以只要二等分7次，即可求得滿足精度要求的根。計(jì)算過程如表6.2.1所示k

f(ak)及符號f(xk)及符號f(bk)及符號012345670(－)0(－)0(－)0(－)0.0625(－)0.0625(－)0.078125(－)0.0859375(－)0.5(+)0.25(+)0.125(+)0.0625(－)0.09375(+)0.078125(－)0.0859375(－)1(+)0.5(+)0.25(+)0.125(+)0.125(+)0.09375(+)0.09375(+)0.09375(+)表6.2.1所以，第17頁，共91頁，2023年，2月20日，星期三①簡單;②對f(x)

要求不高(只要連續(xù)即可).①無法求復(fù)根及偶重根②收斂慢

二分法的優(yōu)缺點(diǎn)第18頁，共91頁，2023年，2月20日，星期三

問題雖然二分法計(jì)算簡單，能夠保證收斂，但是它對于方程單根存在區(qū)域信息要求太高，一般情況下很難實(shí)現(xiàn)，并且不能求偶重根、復(fù)根和虛根。在實(shí)際應(yīng)用中，用來求解方程根的主要方法是迭代法。使用迭代法求解非線性代數(shù)方程的步驟為：(1)迭代格式的構(gòu)造；(2)迭代格式的收斂性分析；(3)迭代格式的收斂速度與誤差分析。§2

迭代法第19頁，共91頁，2023年，2月20日，星期三1．簡單迭代法f(x)=0x=

(x)等價(jià)變換其中

(x)是連續(xù)函數(shù)。方程（6.3.1）稱為不動(dòng)點(diǎn)方程，滿足（6.3.1）式的點(diǎn)稱為不動(dòng)點(diǎn)，這樣就將求（6.3.1）的零點(diǎn)問題轉(zhuǎn)化為求的不動(dòng)點(diǎn)問題。稱這種迭代格式為不動(dòng)點(diǎn)迭代。以不動(dòng)點(diǎn)方程為原型構(gòu)造迭代格式第20頁，共91頁，2023年，2月20日，星期三解：從方程可以看出1是方程的一個(gè)根，在[0,1.5]之間。例3求方程的根：方法一：將方程等價(jià)變形為：取迭代初始值：迭代過程：顯然迭代發(fā)散第21頁，共91頁，2023年，2月20日，星期三依此類推,得

x3=0.9940x4=0.9990x5=0.9998x6=1.0000x7=1.0000迭代過程：同樣的方程不同的迭代公式有不同的結(jié)果什么形式的迭代法能夠收斂呢?初值：等價(jià)方程變換為：方法二：收斂于1說明：①迭代函數(shù)不唯一；②迭代點(diǎn)列可能收斂，也可能發(fā)散，迭代收斂與否不僅與迭代函數(shù)有關(guān)，還與初始點(diǎn)有關(guān)。第22頁，共91頁，2023年，2月20日，星期三xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=(x)y=(x)y=(x)y=(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1第23頁，共91頁，2023年，2月20日，星期三定理6.1：如果

(x)滿足下列條件 （1）當(dāng)x[a,b]時(shí)，(x)[a,b]

（2）當(dāng)任意x[a,b]，存在0<L<1，使

則方程x=

(x)在[a,b]上有唯一的根x*,且對任意初值

x0[a,b]，迭代序列xk+1=

(xk)

(k=0,1,…)收斂于x*。(6.3.2)[注]

此處L可以看成是在區(qū)間[a,b]內(nèi)的最大值。2．迭代過程的收斂性第24頁，共91頁，2023年，2月20日，星期三由遞推公式：可以得到：微分中值定理定理的條件2證明：由得注：L越小，收斂越快。反復(fù)迭代：上公式即為：收斂于方程的根

第25頁，共91頁，2023年，2月20日，星期三3．迭代法的誤差估計(jì)

在定理6.1的條件下，簡單迭代法產(chǎn)生的迭代點(diǎn)列有如下誤差估計(jì)式：停機(jī)準(zhǔn)則。（6.3.3）或第26頁，共91頁，2023年，2月20日，星期三②①由收斂性證明得到的遞推公式進(jìn)行推理：注：只要前后兩次迭代值的誤差值足夠小，即可保證近似值具有足夠的精度，因此常常通過來判斷是否滿足迭代精度。第27頁，共91頁，2023年，2月20日，星期三求方程在內(nèi)的根例4：。解：原方程可以等價(jià)變形為下列三個(gè)迭代格式第28頁，共91頁，2023年，2月20日，星期三由迭代格式（1）

取初值得

結(jié)果是發(fā)散的？！第29頁，共91頁，2023年，2月20日，星期三由迭代格式（2）

取初值得

結(jié)果精確到四位有效數(shù)字，迭代到得到收斂結(jié)果。

十步才能得到收斂的結(jié)果！第30頁，共91頁，2023年，2月20日，星期三

由迭代格式（3）

取初值得

結(jié)果精確到四位有效數(shù)字，迭代到得到收斂結(jié)果。四步就能得到收斂的結(jié)果了！第31頁，共91頁，2023年，2月20日，星期三迭代格式（1）的迭代函數(shù)為

求導(dǎo)得

當(dāng)時(shí)故迭代格式（1）是發(fā)散的。分析:第32頁，共91頁，2023年，2月20日，星期三

迭代格式（2）的迭代函數(shù)為

當(dāng)時(shí)由第33頁，共91頁，2023年，2月20日，星期三知當(dāng)時(shí)，

所以迭代格式（2）是收斂的。第34頁，共91頁，2023年，2月20日，星期三迭代格式（3）的迭代函數(shù)為當(dāng)時(shí)

第35頁，共91頁，2023年，2月20日，星期三由時(shí)，

知當(dāng)所以迭代格式（3）也是收斂的。第36頁，共91頁，2023年，2月20日，星期三結(jié)論:

通過以上算例可以看出對迭代函數(shù)所得到的若小于1，則收斂；且上界越小收斂速度越快。求導(dǎo)，的上界若是大于1，則迭代格式發(fā)散；第37頁，共91頁，2023年，2月20日，星期三迭代法的計(jì)算步驟(P145頁)：（1）準(zhǔn)備提供迭代初始值（2）迭代計(jì)算迭代值（3）控制

轉(zhuǎn)（2）；停，第38頁，共91頁，2023年，2月20日，星期三4．迭代過程的局部收斂性定義6.1定理6.2若存在的某個(gè)鄰域R：則稱迭代過程使迭代過程對任意初值均收斂，在鄰近具有局部收斂性。則迭代過程在鄰近具有局部收斂性。設(shè)為方程的根，在的鄰近連續(xù)且第39頁，共91頁，2023年，2月20日，星期三

5.加速收斂技術(shù)

L越小迭代法的收斂速度越快，因此，可以從尋找較小的L來改進(jìn)迭代格式以加快收斂速度。思路(1).松弛法引入待定參數(shù)，將

作等價(jià)變形為（6.3.4）將方程右端記為，則得到新的迭代格式第40頁，共91頁，2023年，2月20日，星期三由定理6.1知為了使新的迭代格式比原來迭代格式收斂得更快，只要滿足且越小，所獲取的L就越小，迭代法收斂的就越快，因此我們希望。第41頁，共91頁，2023年，2月20日，星期三可取

，若記則（6.3.4）式可改寫為

稱為松弛因子，這種方法稱為松弛法。為使迭代速度加快，需要邊計(jì)算邊調(diào)整松弛因子。由于計(jì)算松弛因子需要用到微商，在實(shí)際應(yīng)用中不便使用，具有一定局限性。若迭代法是線性收斂的，當(dāng)計(jì)算不方便時(shí)，可以采用埃特金加速公式。第42頁，共91頁，2023年，2月20日，星期三(2).埃特金加速公式設(shè)迭代法是線性收斂，由定義知成立，故當(dāng)時(shí)有由此可得的近似值（6.3.5）第43頁，共91頁，2023年，2月20日，星期三由此獲得比和更好的近似值，利用（6.3.5）序列的方法稱為(3).Steffensen加速法：

將Aitken加速公式與不動(dòng)點(diǎn)迭代相結(jié)合，可得（6.3.6）式構(gòu)造埃特金（Aitken）加速方法。利用（6.3.6）式構(gòu)造序列的方法稱為Steffensen加速方法。即每進(jìn)行兩次不動(dòng)點(diǎn)迭代，就執(zhí)行一次Aitken加速。第44頁，共91頁，2023年，2月20日，星期三例5試用簡單迭代法和Steffensen加速法求方程在附近的根，精確至四位有效數(shù)。解：記，簡單迭代法公式為：計(jì)算得kxkkxkkxk00.570.5584380140.567118810.606530680.5664094150.567157120.545239290.5675596160.567135430.5797031100.5669072170.567147740.5600646110.5672772180.567140750.5711721120.567067360.5648629130.5671863第45頁，共91頁，2023年，2月20日，星期三Aitken加速公式計(jì)算得所以,。第46頁，共91頁，2023年，2月20日，星期三§3牛頓法一、牛頓法的迭代公式考慮非線性方程原理：將非線性方程線性化—Taylor展開取x0

x*，將f(x)在x0

做一階Taylor展開:，在x0

和x

之間。第47頁，共91頁，2023年，2月20日，星期三將(x*

x0)2

看成高階小量，則有：只要f

C1，且每步迭代都有，而且則

x*就是f(x)的根。公式（6.4.1）稱為牛頓迭代公式。(6.4.1)構(gòu)造迭代公式第48頁，共91頁，2023年，2月20日，星期三x*x0x1x2xyf(x)二、牛頓法的幾何意義第49頁，共91頁，2023年，2月20日，星期三定理：設(shè)f(x)在[a,b]上存在二階連續(xù)導(dǎo)數(shù)且滿足下列條件： （1）f(a)

f(b)<0； （2）f’(x)0； （3）f(x)在區(qū)間[a,b]上不變號； （4）取x0[a,b]，使得f(x)f(x0)>0則由（6.4.1）確定的牛頓迭代序列{xk}二階收斂于f(x)在[a,b]上的唯一單根x*。三、牛頓法的收斂性1.牛頓法收斂的條件第50頁，共91頁，2023年，2月20日，星期三第51頁，共91頁，2023年，2月20日，星期三注：Newton法的收斂性依賴于x0

的選取。x*x0x0x0Newton法是局部收斂的算法！第52頁，共91頁，2023年，2月20日，星期三2.迭代過程的收斂速度

設(shè)由某方法確定的序列{xk}收斂于方程的根x*，如果存在正實(shí)數(shù)p，使得

（C為非零常數(shù)）定義6.2：則稱序列{xk}收斂于x*的收斂速度是p階的，或稱該方法具有p階收斂速度。當(dāng)p=1時(shí)，稱該方法為線性（一次）收斂；當(dāng)p=2時(shí)，稱方法為平方（二次）收斂；當(dāng)1<p<2或C=0,p=1時(shí)，稱方法為超線性收斂。

第53頁，共91頁，2023年，2月20日，星期三3.迭代法收斂階的判別定理6.3

如果在附近的某個(gè)領(lǐng)域內(nèi)有p()階連續(xù)導(dǎo)數(shù)，且則迭代格式在

附近是p階局部收斂的，且有第54頁，共91頁，2023年，2月20日，星期三4.牛頓迭代法的局部收斂性與收斂速度

,且即在包含的一個(gè)區(qū)間二階連續(xù)可導(dǎo)，則Newton迭代法至少二階收斂，值得注意的是，當(dāng)充分光滑且是的重根時(shí)，的附近是線性收斂的。即且其中，為牛頓迭代函數(shù)。法在牛頓即若是

的一個(gè)單根，第55頁，共91頁，2023年，2月20日，星期三例6用牛頓法求方程的根：解：由牛頓迭代公式：取初值x0=0.5注：可與P146頁例6.4比較，牛頓法的收斂速度比較快的。得第56頁，共91頁，2023年，2月20日，星期三并得出了是該方程的一個(gè)根，無人知道他用什么方法得出的，在當(dāng)時(shí)這是一個(gè)非常有名的結(jié)果，試用牛頓法求出此結(jié)果。解：記則當(dāng)時(shí)，，又所以有唯一實(shí)根

，并改寫例7Leonardo于1225年研究了方程第57頁，共91頁，2023年，2月20日，星期三用牛頓迭代格式所以，。第58頁，共91頁，2023年，2月20日，星期三注：牛頓迭代法的優(yōu)缺點(diǎn):優(yōu)點(diǎn):公式簡單,使用方便,易于編程,收斂速度快,易于求解缺點(diǎn):計(jì)算量大,每次迭代都要計(jì)算函數(shù)值與導(dǎo)數(shù)值.5.牛頓法的計(jì)算步驟：1步準(zhǔn)備2步迭代3步控制4步修改若迭代次數(shù)>N，或方法失敗，否則，繼續(xù)。否則轉(zhuǎn)4步第59頁，共91頁，2023年，2月20日，星期三6.牛頓法應(yīng)用舉例設(shè)C>0,解：令

f(x)=x2–C收斂分析：ek+1ek2平方根迭代公式①求正數(shù)平方根算法：若則第60頁，共91頁，2023年，2月20日，星期三例8求解：取x0=10,c=15,

迭代三次便有很好的結(jié)果注：求正數(shù)平方根算法是局部收斂的，它要求初值>0第61頁，共91頁，2023年，2月20日，星期三②求倒數(shù)算法：用牛頓法解方程不用除法有一定的實(shí)際意義解：收斂分析：ek+1ek求倒數(shù)算法要求初值x0滿足：第62頁，共91頁，2023年，2月20日，星期三四、求m重根的牛頓法-修正牛頓法修正格式一：構(gòu)造迭代格式(6.4.2)注：重?cái)?shù)m的確定則迭代格式（6.4.2)

至少2階收斂。

設(shè)

令

則第63頁，共91頁，2023年，2月20日，星期三修正格式二：

令

則是的單根，

即構(gòu)造迭代格式(6.4.3)則迭代格式（6.4.3)

至少2階收斂。第64頁，共91頁，2023年，2月20日，星期三由于Newton迭代法的收斂性依賴于初值的選取，如果離方程的根較遠(yuǎn)，則Newton迭代法可能發(fā)散。為了防止迭代發(fā)散，可以將Newton迭代法與下山法結(jié)合起來使用，放寬初值的選取范圍，即將（6.4.1）式修改為：其中，稱為下山因子，選擇下山因子時(shí)，希望滿足下山法具有的單調(diào)性，即這種算法稱為Newton下山法。在實(shí)際應(yīng)用中，可選擇。五、牛頓法的變形1、牛頓下山法第65頁，共91頁，2023年，2月20日，星期三2.牛頓下山法的計(jì)算步驟：（1）選取初始近似值x0；（2）取下山因子

=1；（3）計(jì)算（4）計(jì)算f(xk+1)，并比較與的大小，分以下二種情況 1）若，則當(dāng)時(shí)，取x*

xk+1，計(jì)算過程結(jié)束；當(dāng)時(shí)，則把xk+1作為新的近似值，并返回到（3）。2）若，則當(dāng)≤且|f(xk+1)|<，取x*

xk，計(jì)算過程結(jié)束；否則若≤，而時(shí)，則把xk+1加上一個(gè)適當(dāng)選定的小正數(shù)，即取xk+1+作為新的xk值，并轉(zhuǎn)向（3）重復(fù)計(jì)算；當(dāng)＞且時(shí)，則將下山因子縮小一半，取/2代入，并轉(zhuǎn)向（3）重復(fù)計(jì)算。第66頁，共91頁，2023年，2月20日，星期三【例9】求方程f(x)=x3–x–1=0的根。

x0

=0.6牛頓下山法的計(jì)算結(jié)果：kxk010.611/251.14063211.36681311.32628411.32472第67頁，共91頁，2023年，2月20日，星期三牛頓迭代法每迭代一次都需計(jì)算函數(shù)值和導(dǎo)數(shù)值計(jì)算量比較大；且迭代過程中計(jì)算時(shí)，僅利用了點(diǎn)的信息，而沒有充分利用已經(jīng)求出的；在導(dǎo)數(shù)計(jì)算比較麻煩或難以求出時(shí)，

迭代格式構(gòu)造(2)構(gòu)造方法：將Newton迭代格式中的導(dǎo)數(shù)用差商代替。1、割線法：(1)構(gòu)造思想：用割線的斜率代替牛頓迭代法中切線的斜率；設(shè)法避開導(dǎo)數(shù)值的計(jì)算，因此可以采用離散牛頓法（割線法）。

一個(gè)自然的想法就是在充分利用“舊信息”的同時(shí)，§4弦截法與拋物線法第68頁，共91頁，2023年，2月20日，星期三（1）割線法的幾何意義x0x1切線

割線

切線斜率

割線斜率x2割線法迭代格式：第69頁，共91頁，2023年，2月20日，星期三（2）割線法的局部收斂性與收斂速度

設(shè)，在,且的某一鄰域內(nèi)二階連續(xù)可微，當(dāng)時(shí)，由割線法產(chǎn)生的序列收斂于，且收斂階至少為1.312。

割線法是超線性收斂的！第70頁，共91頁，2023年，2月20日，星期三2、雙點(diǎn)弦截法：切線斜率

割線斜率初值x0

和x1。x0x1x2第71頁，共91頁，2023年，2月20日，星期三雙點(diǎn)弦截法的局部收斂性與收斂速度

設(shè)，在,且的某一鄰域內(nèi)二階連續(xù)可微，且對任意的則當(dāng)時(shí)，由弦截法產(chǎn)生的序列收斂于且收斂階至少為1.618。定理6.5，雙點(diǎn)弦截法也是超線性收斂的！第72頁，共91頁，2023年，2月20日，星期三計(jì)算結(jié)果k

xk

xk-xk-100.510.60.120.56532-0.0346830.567090.0017740.567140.00005從表中可以看出弦截法的收斂速度也是相當(dāng)快的，迭代到第4步就得到精度的結(jié)果.例10用弦截法解方程第73頁，共91頁，2023年，2月20日，星期三雙點(diǎn)弦截法的計(jì)算步驟：1步準(zhǔn)備2步迭代3步控制4步修改若迭代次數(shù)>N，失敗，否則，繼續(xù)。否則轉(zhuǎn)4步；第74頁，共91頁，2023年，2月20日，星期三3.拋物線法此迭代過程稱為拋物線法，亦稱為密勒(Müller)法.（1）基本思想：以f(x)=0的三個(gè)近似根xk,xk-1,xk-2為插值節(jié)點(diǎn)構(gòu)造二次插值多項(xiàng)式P2(x)，并以的零點(diǎn)作為的一個(gè)新的近似根。第75頁，共91頁，2023年，2月20日，星期三yxk-2xk-1xkxk+1xy=f(x)y=P2(x)x*O（2）拋物線法的幾何意義第76頁，共91頁，2023年，2月20日，星期三（3）拋物線法計(jì)算公式的推導(dǎo)：兩個(gè)零點(diǎn)：其中，P2(x)與x

軸有兩個(gè)交點(diǎn),取哪個(gè)點(diǎn)為f(x)的根的近似？

注：在xk,xk-1,xk-2三個(gè)近似值中，自然假定xk更接近x*，為保證精度，我們選上式中接近xk的一個(gè)值作為新的近似根xk+1.為此，只要取根式前的符號與ω的符號相同.第77頁，共91頁，2023年，2月20日，星期三yxk-2xk-1xkxk+1xy=f(x)y=P2(x)x*O第78頁，共91頁，2023年，2月20日，星期三例11

用拋物線法求解方程f(x)=xex-1=0.解：取x0=0.5,x1=0.6,x2=0.56532開始，計(jì)算得f(x0)=-0.175639,f(x1)=0.093271,f(x2)=-0.005031.f[x1,x0]=2.68910,f[x2,x1]=2.83373,f[x2,x1,x0]=2.21418.故：代入公式以上計(jì)算表明，拋物線法比弦截法收斂更快！求得第79頁，共91頁，2023年，2月20日，星期三拋物線法的迭代誤差有下列漸近關(guān)系式

由此式可見拋物線法也是超線性收斂的，其收斂階是p=1.840(是方程λ3-λ2-λ-1=0的根)，收斂速度比弦截法更接近于牛頓法.（5）拋物線法的計(jì)算步驟（P156頁）（4）拋物線法的局部收斂性與誤差估計(jì)第80頁，共91頁，2023年，2月20日，星期三

如果f(x)是多項(xiàng)式，那么