科學計算4非線性方程

計算機基礎教育系第4章非線性方程的數值解法第2章非線性方程的數值解法求方程f(x)=0的實根本章恒設f(x)連續(xù)主要內容何謂數值解法根的存在性——介值定理根的存在范圍——根的隔離根的精確化方法重點算法：對分法、迭代法和牛頓法Step1Step2非線性方程的求解過程1、判斷是否有根，確定根的存在范圍n次的代數方程最多有n個根，可能有一對共軛復根2、根的隔離，求隔根區(qū)間試值法、作圖法、掃描法3、根的精確化對分法、迭代法、牛頓法、弦割法4.2根的隔離-試值法根據函數的性質，進行一些試算。例2.1求方程的隔根區(qū)間。，其定義域為其導函數為所以當時，，函數單調上升；當時，，函數單調下降；當時，解設，函數單調上升。試值法于是在每個區(qū)間上至多只有一個根。取幾個特殊的點計算函數值，f(-4)=-40，f(-3)=1，f(-1)=5，f(0)=-8，f(2)=-4，f(3)=37

所以，隔根區(qū)間可取為(-4,-3)、(-1,0)和(2,3)。由于f(x)為三次多項式，至多有3個實根。因此方程f(x)=0所有的隔根區(qū)間為(-4,-3)、(-1,0)和(2,3)。的函數曲線f(x)=0所有的隔根區(qū)間為(-4,-3)、(-1,0)和(2,3)2.2根的隔離-作圖法例2.2求方程的隔根區(qū)間。

解，，當x<0時，；當x>0時，，畫出的草圖如圖2-1，從圖中可大致確定隔根區(qū)間為(-2,-1)、(-1,1)和(1,2)。y=x3-3x-1的曲線圖4.2根的隔離——掃描法掃描法就是將有根區(qū)間等分為若干個子區(qū)間，然后逐個小區(qū)間檢驗是不是隔根區(qū)間，檢驗的辦法就是判斷區(qū)間端點的函數值是否異號。連續(xù)函數的介值定理：掃描法ab令x=a,取步長h，檢驗區(qū)間[x,x+h]上是否有根x+hx[x,x+h]為一隔根區(qū)間，繼續(xù)看下一個區(qū)間是否有根x+2hxx+h直到x>b為止掃描法的算法輸入有根區(qū)間的端點a,b及子區(qū)間長度h；

(3)若，則；輸出隔根區(qū)間(4)(5)若x<b-h/2，則返回(3)；否則結束。代數方程的實根的上、下界對于代數方程設，則其實根的上、下界分別為和由此即可確定其有根區(qū)間[a,b]。4.3對分法已知[a,b]為一個隔根區(qū)間，即有且僅有一個跟，且f(a)*f(b)<0abccab什么時候停止？或x*每次縮小一倍的區(qū)間，收斂速度為1/2，較慢，且只能求一個根，使用條件限制較大

2xx*不能保證x

的精度對分法的算法

(1)輸入隔根區(qū)間的端點a,b及預先給定的精度要求eps；

(2)(a+b)/2=>c；

(3)若f(c)=0，則輸出c，結束；否則若，則否則(4)若b-a<eps，則輸出根的近似值c，結束；否則轉向(2)繼續(xù)。2.4迭代法f(x)=x3-x-1，將x3-x-1=0改寫為：1.x=x3-1，

x=x3-1

φ

(x)=x3-12.x3=x+1x=(x+1)1/3φ

(x)=

(x+1)1/33.x(x2-1)=1x=1/(x2-1)

φ

(x)=1/(x2-1)

4.x(x2-1)=1x=(1+1/x)1/2φ(x)=(1+1/x)1/2………第3和第4種改法不可取，因為函數φ(x)不再連續(xù)。f(x)=0x=φ(x)等價變換取x0帶入x1=

φ(x0)

x2=

φ(x1)

x3=

φ(x2)

……xk=

φ(xk-1)

從一個初值x0

出發(fā)，計算x1

=φ(x0),x2

=φ(x1),…,xk+1

=φ(xk),…若收斂，即存在x*使得

且φ

連續(xù)，則由可知x*=φ(x*)，即x*是φ

的不動點，也就是f

的根。2.4迭代法f(x)=0x=φ(x)等價變換f(x)的根φ(x)的不動點迭代法舉例(1)將方程改寫成等價形式則迭代公式為取初始近似值為x0=1.5，迭代結果見下表。(k=0,1,2,…)k1234xk2.37512.39651904.00286902441984由表可見，迭代是發(fā)散的。例2.3求方程在x0=1.5附近的根的近似值，精度要求為10-4。迭代法舉例例2.3求方程在x0=1.5附近的根的近似值，精度要求為10-4。解：(2)可將方程改寫成等價形式于是有迭代公式(k=0,1,2,…)將初值x0=1.5代入，可得迭代序列x1,x2,…，例2.3k123456xk1.3572091.3308611.3258841.3249391.3247601.324726可見迭代法(2.4)是收斂的，就是滿足精度要求的一個近似根。取初值x0=1.5迭代法的收斂性什么因素影響收斂？Φ(x)不同兩種方法的區(qū)別？迭代收斂定理對于同一個方程，不同的做法收斂性是不一樣的，那么，收斂還是發(fā)散受什么條件的影響？兩種做法主要的區(qū)別在什么地方？Φ(x)滿足什么條件會收斂？

敘述證明思考關于不動點原理取一個淺盒和一張紙，紙恰好蓋住盒內的底面。可想而知此時紙上的每個點與正在它下面的盒底上的那些點配成對。把這張紙拿起來，隨機地揉成一個小球，再把小球扔進盒里。拓撲學家已經證明，不管小球是怎樣揉成的，也不管它落在盒底的什么地方，在揉成小球的紙上至少有一個這樣的點，它恰好處在它盒底原來配對點的正上方。迭代收斂定理

定理2.1

設迭代函數滿足時，(2)存在正數L<1，對任意，均有則在[a,b]內存在唯一根，并且對任意初始值，迭代法(k=0,1,2,…)①②(1)當收斂于，且（2.6）（2.7）定理內容已知條件-迭代函數Φ(x)有界（有界性）迭代函數的導數有界，小于1（壓縮性）結論迭代收斂迭代序列的極限就是方程的根兩個不等式的意義誤差事后估計的依據收斂速度和L的關系123定理分析

證：先證根的存在性，由條件(1)知，在區(qū)間[a,b]上有

當F(a)=0或F(b)=0時，a或b就是方程的根，否則有因連續(xù)，所以F(x)也連續(xù)，由連續(xù)函數性質可知，存在，使，即，于是是方程的根。作輔助函數迭代收斂定理的證明可知，F(xiàn)(x)在區(qū)間[a,b]上嚴格單調上升，所以F(x)在此區(qū)間上至多有一個根，根的唯一性得證。

再證根的唯一性。最后證明迭代序列的極限就是方程的根。由根據微分中值定理，必存在ξ介于xk與α之間，及介于xk與xk-1之間，使得由條件(2)知(2.8)于是整理可得此即(1)式。將上式代入(2.6)式后，即得此即(2.7)式。再反復利用(2.8)式的第2式，可得由可知必有即故迭代法收斂于方程的根得證。1、等價形式Φ(x)2、初值選取x0定理的應用滿足時，(2)存在正數L<1，對任意，均有(1)當構造滿足定理條件的等價形式一般難于做到：局部收斂定理迭代過程往往就在根的附近進行，只要假定在附近連續(xù)，且滿足，則根據連續(xù)函數的性質，一定存在的某鄰域S：，使得在S上滿足定理2.1的條件，故在S中任取初始值x0，迭代公式必將收斂于方程的根這種收斂稱為局部收斂。迭代法的算法(1)輸入初始近似值x0，精度要求eps，控制最大迭代次數M；(3)當k<M且>eps時做循環(huán)，，(4)如果eps，則輸出x1；否則輸出迭代失敗信息。(2)xyy=xx*y=g(x)x0p0x1p1

xyy=xx*y=g(x)x0p0x1p1

迭代法的幾何意義迭代法的加速（選學）如何加快迭代收斂的速度？根據不等式②知L越小，收斂速度越快加快收斂速度的辦法就是設法讓L變小迭代法的加速1松弛法在x=φ(x)的兩端同時加上λx，得變形為：相當于根據迭代收斂定理，導數要盡可能地小，所以取迭代法的加速這樣，迭代公式變?yōu)椋毫顒t此即松弛法，不收斂的迭代函數，經加速后一般也能獲得收斂。迭代法的加速2埃特金法（Altken）松弛法中計算導數不方便，用差商代替導數，用

代替得得迭代公式埃特金公式有時可能使一個本來不收斂的迭代格式獲得收斂。4.5牛頓法“以直代曲”的思想，將f(x)在初值處作Taylor展開取線性部分作為f(x)的近似，有：若，則有記為類似，我們可以得到xyx*x0可以得到迭代序列Newton迭代的等價方程為：所以若f(x)在a處為單根，則所以，根據局部收斂定理，迭代格式收斂2.5牛頓法收斂速度

定義2.1設由迭代公式產生的迭代序列(k=0,1,2,…)收斂于方程的根，記

，若存在實數及非零常數c，使得

則稱迭代過程是p階收斂的。當p=1時，稱為線性收斂；當p>1時，稱為超線性收斂；當p=2時，稱為平方收斂。顯然，p越大收斂速度越快。簡單迭代的收斂速度

由微分中值定理可知，必存在一點介于xk與之間，使得于是由此可知，簡單迭代法至少是線性收斂的。函數在a處作Taylor展開即牛頓迭代收斂速度快，格式簡單，應用廣泛牛頓法的收斂速度x*x0

x0

x0注：牛頓法初值選擇的規(guī)則：f"(x0)f(x0)>0牛頓法初值的選取規(guī)則牛頓法舉例例2.4用牛頓法求

解將求轉化為求方程則相應的牛頓迭代公式為(k=0,1,2,…)(2.12)可選取任意大于的數，比如2作為根的初始近似值

的根可選取任意大于的數，比如2作為根的初始近似值

的近似值，誤差要求為10-54.6弦割法將Newton迭代中的導數，用差商代替，有格式是2步格式。收斂速度比Newton迭代慢x0x1切線

割線

非線性方程數值解法經典算法：對分法迭代法牛頓法弦割法MATLAB函