科學(xué)計(jì)算4非線性方程

計(jì)算機(jī)基礎(chǔ)教育系第4章非線性方程的數(shù)值解法第2章非線性方程的數(shù)值解法求方程f(x)=0的實(shí)根本章恒設(shè)f(x)連續(xù)主要內(nèi)容何謂數(shù)值解法根的存在性——介值定理根的存在范圍——根的隔離根的精確化方法重點(diǎn)算法：對(duì)分法、迭代法和牛頓法Step1Step2非線性方程的求解過程1、判斷是否有根，確定根的存在范圍n次的代數(shù)方程最多有n個(gè)根，可能有一對(duì)共軛復(fù)根2、根的隔離，求隔根區(qū)間試值法、作圖法、掃描法3、根的精確化對(duì)分法、迭代法、牛頓法、弦割法4.2根的隔離-試值法根據(jù)函數(shù)的性質(zhì)，進(jìn)行一些試算。例2.1求方程的隔根區(qū)間。，其定義域?yàn)槠鋵?dǎo)函數(shù)為所以當(dāng)時(shí)，，函數(shù)單調(diào)上升；當(dāng)時(shí)，，函數(shù)單調(diào)下降；當(dāng)時(shí)，解設(shè)，函數(shù)單調(diào)上升。試值法于是在每個(gè)區(qū)間上至多只有一個(gè)根。取幾個(gè)特殊的點(diǎn)計(jì)算函數(shù)值，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)為三次多項(xiàng)式，至多有3個(gè)實(shí)根。因此方程f(x)=0所有的隔根區(qū)間為(-4,-3)、(-1,0)和(2,3)。的函數(shù)曲線f(x)=0所有的隔根區(qū)間為(-4,-3)、(-1,0)和(2,3)2.2根的隔離-作圖法例2.2求方程的隔根區(qū)間。

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

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

2xx*不能保證x

的精度對(duì)分法的算法

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

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

(3)若f(c)=0，則輸出c，結(jié)束；否則若，則否則(4)若b-a<eps，則輸出根的近似值c，結(jié)束；否則轉(zhuǎn)向(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種改法不可取，因?yàn)楹瘮?shù)φ(x)不再連續(xù)。f(x)=0x=φ(x)等價(jià)變換取x0帶入x1=

φ(x0)

x2=

φ(x1)

x3=

φ(x2)

……xk=

φ(xk-1)

從一個(gè)初值x0

出發(fā)，計(jì)算x1

=φ(x0),x2

=φ(x1),…,xk+1

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

且φ

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

的不動(dòng)點(diǎn)，也就是f

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

敘述證明思考關(guān)于不動(dòng)點(diǎn)原理取一個(gè)淺盒和一張紙，紙恰好蓋住盒內(nèi)的底面?？上攵藭r(shí)紙上的每個(gè)點(diǎn)與正在它下面的盒底上的那些點(diǎn)配成對(duì)。把這張紙拿起來，隨機(jī)地揉成一個(gè)小球，再把小球扔進(jìn)盒里。拓?fù)鋵W(xué)家已經(jīng)證明，不管小球是怎樣揉成的，也不管它落在盒底的什么地方，在揉成小球的紙上至少有一個(gè)這樣的點(diǎn)，它恰好處在它盒底原來配對(duì)點(diǎn)的正上方。迭代收斂定理

定理2.1

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

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

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

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

xyy=xx*y=g(x)x0p0x1p1

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

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

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

，若存在實(shí)數(shù)及非零常數(shù)c，使得

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

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

x0

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

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

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

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

割線

非線性方程數(shù)值解法經(jīng)典算法：對(duì)分法迭代法牛頓法弦割法MATLAB函