第六章非線性方程求根

第六章非線性方程求根第一頁，共六十二頁，編輯于2023年，星期五

公元前1700年的古巴比倫人就已有關(guān)于一、二次方程的解法。

《九章算術(shù)》(公元前50~100年)其中“方程術(shù)”有聯(lián)立一次方程組的一般解法。

1535年意大利數(shù)學(xué)家尼柯洛馮塔納找到了一元三次方程一般形式的求根方法。這個(gè)成就，使他在幾次公開的數(shù)學(xué)較量中大獲全勝，從此名揚(yáng)歐洲。但是馮塔納不愿意將他的這個(gè)重要發(fā)現(xiàn)公之于世.第二頁，共六十二頁，編輯于2023年，星期五

當(dāng)時(shí)的另一位意大利數(shù)學(xué)家兼醫(yī)生卡爾丹諾，對(duì)馮塔納的發(fā)現(xiàn)非常感興趣。他幾次誠懇地登門請(qǐng)教，希望獲得馮塔納的求根公式。后來，馮塔納終于用一種隱晦得如同咒語般的語言，把三次方程的解法“透露”給了卡爾丹諾。馮塔納認(rèn)為卡爾丹諾很難破解他的“咒語”，可是卡爾丹諾通過解三次方程的對(duì)比實(shí)踐，很快就徹底破譯了馮塔納的秘密。第三頁，共六十二頁，編輯于2023年，星期五卡爾丹諾把馮塔納的三次方程求根公式，寫進(jìn)了自己的學(xué)術(shù)著作《大法》中，但并未提到馮塔納的名字。由于第一個(gè)發(fā)表三次方程求根公式的人確實(shí)是卡爾丹諾，因此后人就把這種求解方法稱為“卡爾丹諾公式”。第四頁，共六十二頁，編輯于2023年，星期五

后來，卡爾丹諾的學(xué)生弗瑞里(Ferrari)又提出了四次方程的解法。但對(duì)于五次方程求根，求索工作始終沒有成效，導(dǎo)致人們對(duì)高次代數(shù)方程解的存在性產(chǎn)生了懷疑。1828年17歲的法國數(shù)學(xué)家伽羅華(E·Galois1811-1832)寫出了劃時(shí)代的論文“關(guān)于五次方程的代數(shù)解法問題”，指出即使在公式中容許用n次方根，并用類似算法求五次或更高次代數(shù)方程的根是不可能的第五頁，共六十二頁，編輯于2023年，星期五文章呈交法蘭西科學(xué)院后，因輩份太低遭到冷遇，且文稿丟失。1830年伽羅華再進(jìn)科學(xué)院遞稿，得到泊松院士的判詞“完全不能理解”。后來伽羅華命運(yùn)不佳，投考名校巴黎工科大學(xué)落榜，屈就高等師院，并卷入政事兩次入獄，被開除學(xué)籍，又決斗受傷，死于1832年。決斗前，他把關(guān)于五次代數(shù)求解的研究成果寫成長信，留了下來。第六頁，共六十二頁，編輯于2023年，星期五

十四年后，法國數(shù)學(xué)家劉維爾(J·Liouville)整理并發(fā)表了伽羅華的遺作，人們才意識(shí)到這項(xiàng)近代數(shù)學(xué)發(fā)展史上的重要成果的寶貴。38年后，即1870年，法國數(shù)學(xué)家若當(dāng)(C·Jordan)在專著《論置換與代數(shù)方程》中闡發(fā)了伽羅華的思想，一門現(xiàn)代數(shù)學(xué)的分支—群論誕生了。在前幾個(gè)世紀(jì)中，曾開發(fā)出一些求解代數(shù)方程的有效算法，它們構(gòu)成了數(shù)值分析中的古典算法。至于超越方程則不存在一般的求根方式。第七頁，共六十二頁，編輯于2023年，星期五求根問題包括下面三個(gè)問題：根的存在性：即f(x)=0有沒有根？若有，有幾個(gè)根？哪兒有根？確定有根區(qū)間根的精確化：已知一個(gè)根的近似值后，能否將它精確到足夠精度？本章假設(shè)f

C[a,b]，且f(a)·f(b)<0，則f

在(a,b)上至少有一根，(a,b)即為有根區(qū)間。問題1、2得到解決。第八頁，共六十二頁，編輯于2023年，星期五(1)圖解法（利用作圖軟件如Matlab)(2)掃描法（逐步搜索法）(3)二分法*§2根的搜索第九頁，共六十二頁，編輯于2023年，星期五

（1）(描)做圖法

畫出y=f(x)

的草圖,由f(x)與橫軸交點(diǎn)的大概位置來確定隔根區(qū)間;或者利用導(dǎo)函數(shù)f(x)的正、負(fù)與函數(shù)f(x)的單調(diào)性的關(guān)系確定根的大概位置.

若f(x)比較復(fù)雜,還可將方程f(x)=0化為一個(gè)等價(jià)方程(x)=(x),

則曲線y=(x)與y=(x)之交點(diǎn)A(x*,y*)的橫坐標(biāo)x*即為原方程之根,據(jù)此也可通過作圖求得x*的隔根區(qū)間.第十頁，共六十二頁，編輯于2023年，星期五如求解方程的近似根

方法1:將方程同解變換成然后畫兩條曲線第十一頁，共六十二頁，編輯于2023年，星期五023yx這兩條曲線的交點(diǎn)的橫座標(biāo)大致為x=2.5第十二頁，共六十二頁，編輯于2023年，星期五1.逐步搜索法§2根的搜索

2.逐步搜索法設(shè)f(a)<0,f(b)>0，有根區(qū)間為(a,b)，從x0=a出發(fā)，按某個(gè)預(yù)定步長(例如h=(b-a)/N)一步一步向右跨，每跨一步進(jìn)行一次根的搜索，即判別f(xk)=f(a+kh)的符號(hào)，若f(xk)>0(而f(xk-1)<0),則有根區(qū)間縮小為[xk-1,xk](若f(xk)=0，xk即為所求根),然后從xk-1出發(fā)，把搜索步長再縮小，重復(fù)上面步驟，直到滿足精度：|xk-xk-1|<為止，此時(shí)取x*≈(xk+xk-1)/2作為近似根。①無法求復(fù)根及偶重根②計(jì)算量大，收斂慢①簡(jiǎn)單;②對(duì)f(x)

要求不高

(只要連續(xù)即可).x0=abxk-1xkx*第十三頁，共六十二頁，編輯于2023年，星期五2.BisectionMethod

3.二分法

/*BisectionMethod*/(逐步搜索法的改進(jìn))設(shè)f(x)的有根區(qū)間為[a,b]=[a0,b0],f(a)<0,f(b)>0.將[a0,b0],對(duì)分，中點(diǎn)x0=((a0+b0)/2),計(jì)算f(x0),

若f(x0)=0,x*=x0

<0,有根區(qū)間:[a1,b1]=[x0,b]>0,有根區(qū)間:[a1,b1]=[a,x0]對(duì)[a1,b1]對(duì)分，如此反復(fù)進(jìn)行，得到一系列有根區(qū)間：

f(ak)0,f(bk)0,f(x*)=limf(ak)=limf(bk)abx1x2x*第十四頁，共六十二頁，編輯于2023年，星期五Whentostop?取xk=(ak+bk)/2([ak,bk]的中點(diǎn))，顯然有l(wèi)imxk=x*.——算法和收斂性說明?；虿荒鼙ＷC

xk的精度abx1x2x*2xkx*2.BisectionMethod第十五頁，共六十二頁，編輯于2023年，星期五第1步產(chǎn)生的有誤差第k步產(chǎn)生的xk

有誤差對(duì)于給定的精度

,可估計(jì)二分法所需的步數(shù)k：①簡(jiǎn)單，總收斂;②對(duì)f(x)

要求不高(只要連續(xù)即可).①無法求復(fù)根及偶重根②收斂慢注：用二分法求根，最好先給出f(x)

草圖以確定根的大概位置。或用搜索程序，將[a,b]分為若干小區(qū)間，對(duì)每一個(gè)滿足f(ak)·f(bk)<0的區(qū)間調(diào)用二分法程序，可找出區(qū)間[a,b]內(nèi)的多個(gè)根，且不必要求f(a)·f(b)<0。誤差分析2.BisectionMethod第十六頁，共六十二頁，編輯于2023年，星期五Fixed-PointIterationf(x)=0x=φ(x)，e.g.,φ(x)=f(x)+x等價(jià)變換f(x)=0的根

φ

(x)的不動(dòng)點(diǎn)一、迭代算法的原理f(x*)=0x*=φ(x*)被這個(gè)函數(shù)映射到其自身一個(gè)點(diǎn)！第十七頁，共六十二頁，編輯于2023年，星期五二、迭代算法的思路

從一個(gè)初值x0出發(fā)，計(jì)算

x1=φ(x0),

x2=φ(x1),

…,

xk+1=φ(xk),

…若收斂，即存在x*使得

，x*是φ(x)的不動(dòng)點(diǎn)，也就是f(x)=0

的根。xk+1=φ(xk)φ(x*)x*φ(x)連續(xù)=迭代函數(shù)迭代格式第十八頁，共六十二頁，編輯于2023年，星期五注意x*為的解，即這兩個(gè)函數(shù)圖象交點(diǎn)的橫坐標(biāo)。迭代法三、迭代算法的幾何意義第十九頁，共六十二頁，編輯于2023年，星期五xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1§3.Fixed-PointIteration第二十頁，共六十二頁，編輯于2023年，星期五例2用不動(dòng)點(diǎn)迭代法求方程x4+2x2-x-3=0在[1,1.2]內(nèi)的實(shí)根，取x0=1,精確到小數(shù)點(diǎn)后面6位。解迭代格式

發(fā)散法一第二十一頁，共六十二頁，編輯于2023年，星期五解法二迭代格式

收斂第二十二頁，共六十二頁，編輯于2023年，星期五迭代格式

收斂快解法三第二十三頁，共六十二頁，編輯于2023年，星期五四、結(jié)論可見，f(x)=0的迭代函數(shù)（1）不唯一；（2）發(fā)散或者收斂；（3）收斂速度有快慢之分。五、問題（1）迭代函數(shù)收斂的條件是什么？（2）收斂速度如何評(píng)價(jià)？第二十四頁，共六十二頁，編輯于2023年，星期五定理1(迭代收斂條件)考慮方程x=g(x),g(x)C[a,b],若(I)

x[a,b]，g(x)[a,b]；(II)0L<1,s.t.

x[a,b],|g(x)|L.(k=1,2,…)且存在極限k事后誤差估計(jì)事先誤差估計(jì)§3.Fixed-PointIteration則任取初值x0[a,b]，由xk+1=g(xk)

得到的序列收斂于g(x)在[a,b]上的唯一不動(dòng)點(diǎn)，并且有誤差估計(jì)式：第二十五頁，共六十二頁，編輯于2023年，星期五§3Fixed-PointIteration證明：①g(x)在[a,b]上存在不動(dòng)點(diǎn)？令有根②不動(dòng)點(diǎn)唯一？反證：若不然，設(shè)還有，則在和之間。而③當(dāng)k

時(shí)，

xk收斂到x*？第二十六頁，共六十二頁，編輯于2023年，星期五④⑤⑥可用來控制收斂精度L越收斂越快小注：定理?xiàng)l件非必要條件，可將[a,b]縮小，定義局部收斂性§3.Fixed-PointIterationDef1.Ifthereexistsaneighborhoodofx*,e.g.,B

={x||xx*|}，s.t.x0B,

xk+1=g(xk)converges,thenwesaytheiterationconvergeslocallyaroundx*.

第二十七頁，共六十二頁，編輯于2023年，星期五證明:注：由于事先x*未知，所以無法檢驗(yàn)條件|g'(x*)|<1.只能用搜索法初步確定x*所在區(qū)間，驗(yàn)證該區(qū)間內(nèi)任一點(diǎn)是否有|g'(x*)|<1.所以Th2實(shí)際上沒什么應(yīng)用價(jià)值，但在理論上是對(duì)g(x)的一個(gè)改進(jìn)。

§3.Fixed-PointIterationTh2.若在x*的某領(lǐng)域B={x||xx*|}有g(shù)C1[a,b]且|g'(x*)|<1，則由x0B

開始的迭代收斂。即調(diào)整初值可得到收斂的結(jié)果。注：局部收斂性定理對(duì)迭代函數(shù)的要求較弱，但對(duì)初始點(diǎn)要求較高，即初始點(diǎn)必須選在精確解的附近第二十八頁，共六十二頁，編輯于2023年，星期五Algorithm:Fixed-PointIterationFindasolutiontox=g(x)givenaninitialapproximationx0.Input:initialapproximationx0;toleranceTOL;maximumnumberofiterationsNmax.Output:approximatesolutionxormessageoffailure.Step1Seti=1;Step2While(iNmax)dosteps3-6

Step3Setx=g(x0);/*computexi*/

Step4If|xx0|<TOLthenOutput(x);/*successful*/ STOP;

Step5Seti++;

Step6Setx0=x;/*updatex0*/Step7Output(ThemethodfailedafterNmaxiterations);/*unsuccessful*/ STOP.當(dāng)x很大時(shí)，此處可改為§3.Fixed-PointIteration第二十九頁，共六十二頁，編輯于2023年，星期五§3.Fixed-PointIteration改進(jìn)、加速收斂

/*acceleratingconvergence*/有些迭代過程雖收斂，但速度很慢。為了達(dá)到所要求的精度，需要迭代的次數(shù)很多，由此必須設(shè)法加速迭代過程。1.基本思想上式說明，將預(yù)測(cè)值x0和校正值x1

作線性組合作為x*的一個(gè)新近似值，可能比x1更好。令：

ξ介于x0與x*之間，設(shè)變化不大，，則有微分中值定理x0----x*的預(yù)測(cè)值第三十頁，共六十二頁，編輯于2023年，星期五一般地，有LinearcombinationUpdateresidual第三十一頁，共六十二頁，編輯于2023年，星期五

2.Aitken加速：在方法1中含有L，實(shí)際應(yīng)用中不便。下面設(shè)法消除L得到一種新的加速方法---Aitken（埃特金）方法。

x0——prediction推廣，有下面一般計(jì)算公式：

x1=g(x0)——updatingx2=g(x1)——further

updating第三十二頁，共六十二頁，編輯于2023年，星期五predictionAitken’saccelerationxkupdatingFurtherupdatingimprove第三十三頁，共六十二頁，編輯于2023年，星期五也稱為埃特金(Aitken)外推法.可以證明:為線性收斂,則埃特金法為平方收斂；

這個(gè)加速迭代法也可寫成下面格式若為p(p>1)階收斂，導(dǎo)數(shù)連續(xù)，則埃特金法為2p–1

階收斂.的

p

階若第三十四頁，共六十二頁，編輯于2023年，星期五

例題求方程x=e–x

在x=0.5

附近的根.

解取x0=0.5,迭代格式x25=x26=0.5671433

若對(duì)此格式用埃特金法,則

得第三十五頁，共六十二頁，編輯于2023年，星期五仍取x0=0.5,得由此可見,埃特金法加速收斂效果是相當(dāng)顯著的.第三十六頁，共六十二頁，編輯于2023年，星期五§3Fixed-PointIterationxyy=xy=g(x)x*x0P(x0,x1)x1x2P(x1,x2)Generally,wehave比收斂得略快。3.Steffensen加速：Atkin’smethodfromanotherpointofviewx*x*第三十七頁，共六十二頁，編輯于2023年，星期五

4.待定參數(shù)法：若

|g'(x)|1，則將x=g(x)等價(jià)地改造為求K，使得例：求在(1,2)的實(shí)根。如果用進(jìn)行迭代，則在(1,2)中有現(xiàn)令希望，即在(1,2)上可取任意，例如K=0.5，則對(duì)應(yīng)即產(chǎn)生收斂序列。第三十八頁，共六十二頁，編輯于2023年，星期五§4牛頓迭代法

/*Newton-RaphsonMethod*/Newton’smethodfromthepointofviewofaccelerationpredictupdateM=L-1f'(x)簡(jiǎn)單牛頓公式Newton’smethod第三十九頁，共六十二頁，編輯于2023年，星期五牛頓法是解非線性方程（組）的一種常用迭代方法，基本思想是將非線性方程（組）轉(zhuǎn)化為易于求解的線性方程（組）來求解。——

Taylor展開/*Taylor’sexpansion*/設(shè)x*有近似解xk

x*，將f(x)在xk

做一階Taylor展開，將x=

x*代入，有，在x*

和xk

之間。linearequation只要f

C1，每一步迭代都有f(xk)0，而且，則

x*就是f

的根。截取線性項(xiàng)，得xyx*xkTangentmethodNewton’smethodfromthepointofviewoflinearization第四十頁，共六十二頁，編輯于2023年，星期五§4Newton-RaphsonMethod定理

（牛頓法收斂的充分條件）設(shè)f

C2[a,b]，若(1)f(a)f(b)<0；(2)在整個(gè)[a,b]上f不變號(hào)且f(x)0；(3)選取x0

[a,b]使得f(x0)f

(x0)>0；則Newton’sMethod產(chǎn)生的序列{xk}收斂到f(x)在[a,b]的唯一根。有根只有單根，根唯一產(chǎn)生的序列單調(diào)有界，保證收斂。定理

（局部收斂性）設(shè)f

C2[a,b]，若x*

為f(x)在[a,b]上的根，且f(x*)0，則存在x*的鄰域使得任取初值，Newton’sMethod產(chǎn)生的序列{xk}收斂到x*，且滿足第四十一頁，共六十二頁，編輯于2023年，星期五§4Newton-RaphsonMethod證明：Newton’sMethod事實(shí)上是一種特殊的不動(dòng)點(diǎn)迭代其中，則收斂由Taylor展開：在單根

/*simpleroot*/

附近收斂快（平方收斂）第四十二頁，共六十二頁，編輯于2023年，星期五§4Newton-RaphsonMethod注：Newton’sMethod收斂性依賴于x0

的選取。x*x0x0x0第四十三頁，共六十二頁，編輯于2023年，星期五牛頓法應(yīng)用舉例

第四十四頁，共六十二頁，編輯于2023年，星期五第四十五頁，共六十二頁，編輯于2023年，星期五§4Newton-RaphsonMethod改進(jìn)與推廣/*improvementandgeneralization*/

重根/*multipleroot*/

加速收斂法：Q1:

若，Newton’sMethod是否仍收斂？設(shè)x*是f

的n

重根，則：且對(duì)于牛頓法，A1:

有局部收斂性,但重?cái)?shù)n越高,g(x*

)越接近于1,收斂越慢。Q2:

如何加速重根的收斂？A2:

將求

f

的重根轉(zhuǎn)化為求另一函數(shù)的單根。令，則f

的重根=

的單根。重根的處理見《矩陣計(jì)算與方程求根》－曹志潔等；P.208對(duì)f(x)求1,2階導(dǎo)代入即得第四十六頁，共六十二頁，編輯于2023年，星期五§4Newton-RaphsonMethod

正割法/*SecantMethod*/

：Newton’sMethod

一步要計(jì)算f

和f，相當(dāng)于2個(gè)函數(shù)值，比較費(fèi)時(shí)?，F(xiàn)用f

的值近似f

，可少算一個(gè)函數(shù)值。x0x1切線

/*tangentline*/割線

/*secantline*/切線斜率

割線斜率需要2個(gè)初值x0

和x1。收斂比Newton’sMethod慢，且對(duì)初值要求同樣高。第四十七頁，共六十二頁，編輯于2023年，星期五§4Newton-RaphsonMethod

下山法/*DescentMethod*/

——Newton’sMethod

局部微調(diào)：原理若由xk

得到的xk+1不能使|f|減小，則在xk和xk+1之間找一個(gè)更好的點(diǎn)，使得。xkxk+1注：=1時(shí)就是Newton’sMethod公式。當(dāng)=1代入效果不好時(shí)，將減半計(jì)算。第四十八頁，共六十二頁，編輯于2023年，星期五

拋物線法

/*ParabolaMethod*/

——利用插值將非線性方程轉(zhuǎn)化為低次多項(xiàng)式求根x0x1切線

/*tangentline*/割線

/*secantline*/x2x3第四十九頁，共六十二頁，編輯于2023年，星期五§4Newton-RaphsonMethodAlgorithm:Newton’sDescentMethodFindasolutiontof(x)=0givenaninitialapproximationx0.Input:initialapproximationx0;f(x)andf’(x);minimumstepsizeofxmin;

toleranceTOL1forx;toleranceTOL2for

;maximumnumberofiterationsNmax.Output:approximatesolutionxormessageoffailure.Step1Setk=1;Step2While(kNmax)dosteps3-10

Step3Set=1;

Step4Set

;/*computexk*/

Step5If|xx0|<TOL1thenOutput(x);STOP;/*successful*/

Step6Ifthenx0=x;GOTOStep10;/*updatex0*/

Step7Set=/2;/*updatetodescend*/

Step8If>TOL2thenGOTOStep4;/*computeabetterxi*/

Step9Setx0=x0+xmin;/*moveforwardanywaytoavoiddeadlock*/

Step10Setk++;Step11Output(MethodfailedafterNmaxiterations);STOP./*unsuccessful*/計(jì)算量未見得減小第五十頁，共六十二頁，編輯于2023年，星期五§4Newton-RaphsonMethod

求復(fù)根/*FindingComplexRoots*/

——

Newton公式中的自變量可以是復(fù)數(shù)記z=x+iy,z0

為初值，同樣有設(shè)代入公式，令實(shí)、虛部對(duì)應(yīng)相等，可得第五十一頁，共六十二頁，編輯于2023年，星期五§5迭代法的收斂階

/*OrderofConvergence*/Def2.

設(shè)迭代xk+1=g(xk)收斂到g(x)的不動(dòng)點(diǎn)x*。設(shè)ek=xk

x*，若，則稱該迭代為p

階收斂，其中C

稱為漸進(jìn)誤差常數(shù)。/*{xk}convergesto

x*oforder

p,withasymptoticerrorconstant

C>0*/

p

=1----線性收斂，

p

>1-----超線性收斂，

p

=2----平方收斂。一種迭代法有效在接近收斂的過程中迭代誤差的下降速度。Strictdefinitionisgivenindef2.如何刻畫這種關(guān)系第五十二頁，共六十二頁，編輯于2023年，星期五

一般Fixed-PointIteration有，稱為線

性收斂

/*linearconvergence*/，這時(shí)p=1，0<C<1。注：超線性收斂不一定有p>1。例如xn

=1/nn超線性收斂到0，但對(duì)任何p>1都沒有

p

階收斂。Aitken加速有。稱為超線性收斂

/*superlinearconvergence*/。第五十三頁，共六十二頁，編輯于2023年，星期五§5OrderofConvergence

Steffensen加速有p=2，條件是，稱為平方收斂

/*quadraticconvergence*/。

Newton’sMethod有，只要，就有p

2。重根是線性收斂的。Q:

如何實(shí)際確定收斂階和漸進(jìn)誤差常數(shù)？定理

設(shè)x*

為x=g(x)的不動(dòng)點(diǎn)，若，p2；，且，則xk+1=g(xk)在內(nèi)p

階收斂。證明：x*k

CThisisaonelineproof...ifwestartsufficientlyfartotheleft.第五十四頁，共六十二頁，編輯于2023年，星期五Th3(relationbetweentheconvergencerateandtheiterationfunction)

fortheiterationprocess

xk+1=g(xk),if

g(p)(x)

iscontinuous

aro