數(shù)值方法第二章非線性方程的近似解法

數(shù)值方法第二章非線性方程的近似解法第1頁，課件共65頁，創(chuàng)作于2023年2月第二章非線性方程的近似解法§2.0簡介§2.1二分法（對分法）§2.2簡單迭代法§2.3Newton迭代法第2頁，課件共65頁，創(chuàng)作于2023年2月§2.0簡介求解非線性方程f(x)=0

一、問題困難：方程的解難以用公式表達(dá)。例如:1)多項(xiàng)式方程：需要一定精度的近似解！2)超越方程:第3頁，課件共65頁，創(chuàng)作于2023年2月方程的解稱為方程的根或稱為的零點(diǎn)。二、概念方程可能有多個(gè)實(shí)根，我們只能逐個(gè)求出來。第4頁，課件共65頁，創(chuàng)作于2023年2月二、概念設(shè)在區(qū)間[a,b]上方程有一個(gè)根，則稱該區(qū)間為方程的一個(gè)有根區(qū)間。若在區(qū)間[a,b]上方程只有一個(gè)根，則稱該區(qū)間為方程隔根區(qū)間。Remark：若能把有根區(qū)間不斷縮小，則可以得出根的近似值。第5頁，課件共65頁，創(chuàng)作于2023年2月三、根的隔離基于函數(shù)f(x)的連續(xù)性質(zhì)，常用的根的隔離的方法有：描圖法與逐步搜索法。1、描圖法：畫出y=f(x)的簡圖，從曲線與x軸交點(diǎn)的位置確定出隔根區(qū)間，或者將方程等價(jià)變形為g1(x)=g2(x)，畫出函數(shù)y=g1(x)和y=g2(x)的簡圖，從兩條曲線交點(diǎn)的橫坐標(biāo)的位置確定隔根區(qū)間。2、逐步搜索法：先確定方程f(x)=0的所有實(shí)根所在區(qū)間[a,b]，再按照選定的步長（n為正整數(shù)），取點(diǎn)xk=a+kh(k=0,1,…,n)，逐步計(jì)算函數(shù)值f(xk)，依據(jù)函數(shù)值異號以及實(shí)根的個(gè)數(shù)確定隔根區(qū)間。必要時(shí)可調(diào)整步長h，總可把隔根區(qū)間全部找出。第6頁，課件共65頁，創(chuàng)作于2023年2月三、根的隔離第7頁，課件共65頁，創(chuàng)作于2023年2月三、根的隔離問題：掃描間距？第8頁，課件共65頁，創(chuàng)作于2023年2月§2.1二分法（對分法）關(guān)于求解算法:算法多樣：比如剛才的逐步搜索法考慮因素：1．穩(wěn)定性；2．收斂性；3．…第9頁，課件共65頁，創(chuàng)作于2023年2月§2.1二分法（對分法）一、算法設(shè)在[a,b]上連續(xù)，f(a)f(b)<0且在[a,b]內(nèi)f(x)=0僅有一個(gè)實(shí)根。二分法的基本思想是：逐步將有根區(qū)間分半，通過判別函數(shù)值的符號，進(jìn)一步搜索有根區(qū)間，將有根區(qū)間縮小到充分小，從而求出滿足給定精度的根的近似值。執(zhí)行步驟：1．計(jì)算f(x)在有解區(qū)間[a,b]端點(diǎn)處的值，f(a)，f(b)。2．計(jì)算f(x)在區(qū)間中點(diǎn)處的值f(x1)。第10頁，課件共65頁，創(chuàng)作于2023年2月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。4.反復(fù)執(zhí)行步驟2、3，便可得到一系列有根區(qū)間：

(a,b),(a1,b1),…,(ak,bk),…當(dāng)時(shí)則即為方程的近似根第11頁，課件共65頁，創(chuàng)作于2023年2月二、誤差估計(jì)定理1：給定方程f(x)=0，設(shè)f(x)在區(qū)間[a,b]上連續(xù)，且f(a)f(b)<0，則由二分法產(chǎn)生的序列{xk}收斂于方程的根x*，且具有誤差估計(jì)：第12頁，課件共65頁，創(chuàng)作于2023年2月三、收斂準(zhǔn)則1.事先誤差估計(jì)：

利用誤差估計(jì)定理，令得

從而得到對分次數(shù)k＋1，取xk＋1作為根得近似值x*。2.事后誤差估計(jì)：

給定ε，每步檢查，若成立，則取，否則繼續(xù)對分。第13頁，課件共65頁，創(chuàng)作于2023年2月Remark2：也可以使用來控制誤差。Remark3：二分法的優(yōu)點(diǎn)是方法及相應(yīng)的程序均簡單，且對f(x)性質(zhì)要求不高，只要連續(xù)即可。但二分法不能用于求復(fù)數(shù)根和偶數(shù)重根，且收斂速度比較慢。因此，一般常用該方法求根的初始近似值，然后再用其它的求根方法精確化。Remark1：由于，故也可以用來控制誤差（最常用）第14頁，課件共65頁，創(chuàng)作于2023年2月定義f(x)f(a)

f(b)>0f(a)

f(b)=0f(a)=0打印b,k打印a,k結(jié)束是是是否否否m=(a+b)/2|a-b|<f(a)f(m)>0打印m,ka=mb=m結(jié)束k=K+1是是否否輸入k=0算法(二分法)第15頁，課件共65頁，創(chuàng)作于2023年2月§2.2迭代法即序列的極限為的根。

當(dāng)連續(xù)時(shí)，有或。

即

一、迭代法1.基本思想：

令方程,將其變成一個(gè)等價(jià)的方程,構(gòu)造,

稱為迭代數(shù)列，或迭代過程。稱為迭代函數(shù),稱為迭代公式

因此，我們可以通過求迭代數(shù)列的極限的方法來求得方程f(x)=0的根。第16頁，課件共65頁，創(chuàng)作于2023年2月Remark：可以通過不同的途徑將f(x)=0化為x=φ(x)的形式，從而構(gòu)造不同的迭代公式，得到不同的迭代序列。在所有這些構(gòu)造的迭代公式中形成的序列中，有的序列是收斂的，而有些是發(fā)散的。問題：如何選取合適的迭代函數(shù)φ(x)？

φ(x)應(yīng)滿足什么條件，序列{xk}收斂？ 怎樣加速序列{xk}的收斂？第17頁，課件共65頁，創(chuàng)作于2023年2月xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=φ(x)y=φ(x)y=φ(x)y=φ(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1第18頁，課件共65頁，創(chuàng)作于2023年2月2.迭代法的收斂定理（2）對任意初值x0[a,b]由迭代公式則有:定理1.（全局收斂定理）設(shè)方程，如果滿足（3）存在常數(shù)0<L<1,使對任意（1）迭代函數(shù)在區(qū)間[a,b]上可導(dǎo)；（2）當(dāng)x[a,b]時(shí)，；（1）方程在區(qū)間[a,b]上有唯一的根；（3）誤差估計(jì)產(chǎn)生的序列必收斂于方程的根；第19頁，課件共65頁，創(chuàng)作于2023年2月證明：

由于上連續(xù)，作輔助函數(shù)

故由連續(xù)函數(shù)的介值定理知，至少存在又設(shè)即有唯一的根。(1)先證方程根的存在性。，即是方程的根。故由拉格朗日中值定理知，第20頁，課件共65頁，創(chuàng)作于2023年2月（2）由拉格朗日中值定理,有因其中ξ介于之間，故有第21頁，課件共65頁，創(chuàng)作于2023年2月（3）由證畢第22頁，課件共65頁，創(chuàng)作于2023年2月則對于任意的初值x0S，迭代公式產(chǎn)生的序列必收斂于方程的根。3.迭代法的局部收斂定理迭代法的全局收斂性定理給出的是區(qū)間[a,b]上的收斂性，稱之為全局收斂性，一般不易驗(yàn)證，并且在較大的隔根區(qū)間上此定理的條件不一定成立，而只能在根的一個(gè)較小的鄰域內(nèi)成立。下面給出局部收斂定理：定理2.（局部收斂定理）設(shè)是方程的根，若滿足：

（1）迭代函數(shù)在的鄰域可導(dǎo)；（2）在的某個(gè)鄰域，對于任意xS，有：第23頁，課件共65頁，創(chuàng)作于2023年2月當(dāng)xS，即時(shí)，由Lagrange中值定理有將前述定理1中的[a,b]取為，則只需證明即可。其中在x與x*之間，即S。證明：證畢

故第24頁，課件共65頁，創(chuàng)作于2023年2月Remark2：可以證明，若在根的鄰域中，則可以以鄰域內(nèi)任何一點(diǎn)為初始值，用迭代過程產(chǎn)生的序列就一定不會收斂于。事實(shí)上，Remark3：當(dāng)不取在的鄰域內(nèi)時(shí)可能不收斂。Remark1：全局與局部收斂定理中的條件都是充分條件，條件滿足則迭代法收斂，不滿足則不能判定，此時(shí)可以用試算來判定迭代法的是收斂性。Remark4：全局收斂定理中的兩個(gè)誤差估計(jì)式實(shí)際上給出了迭代收斂的兩個(gè)準(zhǔn)則：事后誤差估計(jì)與事先誤差估計(jì)（利用估計(jì)式可以預(yù)先求出迭代次數(shù)k）。第25頁，課件共65頁，創(chuàng)作于2023年2月4.迭代收斂準(zhǔn)則方法一、事先誤差估計(jì)法方法二、事后誤差估計(jì)法先計(jì)算滿足誤差要求的迭代次數(shù)k，再進(jìn)行迭代。有由由因此可以用來控制迭代過程。只要使，就可使

，

對于較為復(fù)雜的迭代函數(shù)，其導(dǎo)數(shù)也較為復(fù)雜，使得L難以取得，因而實(shí)際中不常用此方法。第26頁，課件共65頁，創(chuàng)作于2023年2月Remark1:迭代方法的優(yōu)點(diǎn)是計(jì)算程序簡單，并且雖然是以求解非線性方程的實(shí)根來討論的，但類似的結(jié)果完全可以推廣到求方程的復(fù)數(shù)根的情形。Remark2：由全局收斂定理知，若L1，則{xk}必然收斂較慢；若L<<1，則收斂速度快。第27頁，課件共65頁，創(chuàng)作于2023年2月例

求x3-2x-5=0在[1.5，2.5]上的根。解1）2）若將迭代格式寫為：第28頁，課件共65頁，創(chuàng)作于2023年2月實(shí)驗(yàn)題目：用迭代法求方程在[0,1]內(nèi)的根。為了獲得較快的收斂速度你認(rèn)為應(yīng)該寫成怎樣的等價(jià)方程？第29頁，課件共65頁，創(chuàng)作于2023年2月第30頁，課件共65頁，創(chuàng)作于2023年2月Remark1:以特定的圖形符號加上說明，表示算法的圖，稱為流程圖或框圖。Remark2：為便于識別，繪制習(xí)慣做法是： 圓角矩形表示“開始”與“結(jié)束”； 矩形表示工作環(huán)節(jié)用； 菱形表示問題判斷（審核）環(huán)節(jié)； 平行四邊形表示輸入輸出； 箭頭代表工作流方向。關(guān)于流程圖第31頁，課件共65頁，創(chuàng)作于2023年2月時(shí)間表控制流程圖第32頁，課件共65頁，創(chuàng)作于2023年2月k<m是輸出k=k+1是否輸入k=0算法(迭代法)定義已到最大迭代次數(shù)否結(jié)束開始第33頁，課件共65頁，創(chuàng)作于2023年2月二、迭代法的收斂階若0<C<1,p=1稱為線性收斂；p>1稱為超線性收斂；p＝2稱為平方收斂（二次收斂）。p

越大，收斂速度越快；反之，p越小，收斂速度就越慢。因此，迭代法的收斂階是對迭代法收斂速度的一種度量。（C稱為漸近誤差常數(shù)）定義：設(shè)收斂于，令迭代誤差，如果存在實(shí)數(shù)及非零正常數(shù)C使得則稱該迭代過程以及該迭代式是p階收斂的，也稱相應(yīng)的迭代法是p階方法。第34頁，課件共65頁，創(chuàng)作于2023年2月1.迭代-加速公式記，則由微分中值定理有三、迭代法的加速其中在xk與x*之間。假定在根x*附近變化不大，可設(shè)，由迭代收斂條件有，故上式可寫為：整理為：第35頁，課件共65頁，創(chuàng)作于2023年2月得到迭代加速公式上式說明，把作為根的近似值時(shí)，其絕對誤差大致為。如果把該誤差值作為對的一種補(bǔ)償，便可以得到更好的近似值記第36頁，課件共65頁，創(chuàng)作于2023年2月Remark3：該方法的缺點(diǎn)是需估計(jì)的近似值。Remark1：該迭代法對原迭代式的各近似值在根x*的兩側(cè)往復(fù)地趨于x*時(shí)較為有效。在這種情況下，不但能加快新序列的收斂，還能有效地防止死循環(huán)的出現(xiàn)。Remark2：若序列{xk}單調(diào)趨于x*時(shí)，上式不能起到加速收斂的作用。第37頁，課件共65頁，創(chuàng)作于2023年2月xyy=xx*y=φ(x)x0p0x1p1第38頁，課件共65頁，創(chuàng)作于2023年2月2．埃特金（Aitken）加速方法記用平均變化率代替迭代加速公式中的，于是有則從上式可以看出，第二項(xiàng)是對的一種補(bǔ)償。第39頁，課件共65頁，創(chuàng)作于2023年2月因此可以得下述Aitken加速方法：

Remark：因?yàn)榈^程xk+1=

(xk)總是在根x*附近進(jìn)行，因此用平均變化率代替迭代加速公式中的是有意義的。記第40頁，課件共65頁，創(chuàng)作于2023年2月對于埃特金（Aitken）加速方法有如下的定理：定理3：如果由迭代公式xk+1=

(xk)產(chǎn)生的數(shù)列{xk}滿足：（1）收斂于根x*；（2）則由埃特金（Aitken）加速公式產(chǎn)生的數(shù)列比數(shù)列{xk}較快的收斂于根x*，即第41頁，課件共65頁，創(chuàng)作于2023年2月取前兩項(xiàng)近似代替得近似的線性方程一、Newton迭代法1.牛頓法的基本思想同Newton-Raphson公式§2.3Newton迭代法設(shè)是的一個(gè)近似根，則基本思想：將非線性方程轉(zhuǎn)化為線性方程來求解。第42頁，課件共65頁，創(chuàng)作于2023年2月由知是處的切線

與軸交點(diǎn)的橫坐標(biāo)，故Newton法的幾何意義是逐次用切線代替曲線，求切線與橫坐標(biāo)軸的交點(diǎn)。

Newton法亦稱為切線法。（如下圖）設(shè)

,令解為得顯然是的同解方程。

上式稱為的Newton迭代法，對應(yīng)的方程第43頁，課件共65頁，創(chuàng)作于2023年2月x*x0x1x2xyf(x)Newton迭代法逼近過程第44頁，課件共65頁，創(chuàng)作于2023年2月證明：只需證滿足迭代法局部收斂定理的兩個(gè)條件。2.局部收斂性及條件（1）（2）知，(x)在x*的鄰域可導(dǎo)。定理（Newton迭代法局部收斂性）：設(shè)為的根，如果：（1）函數(shù)f(x)在的鄰域具有連續(xù)的二階導(dǎo)數(shù)；（2）在的鄰域。則存在的某個(gè)鄰域，對于任意的初始值x0S，由Newton迭代公式產(chǎn)生的數(shù)列收斂于根。由迭代函數(shù)得:第45頁，課件共65頁，創(chuàng)作于2023年2月根據(jù)連續(xù)函數(shù)的性質(zhì)，一定存在x*的某個(gè)鄰域，對于任意的xS，有Remark：上述定理對于初值x0的要求比較高，只有當(dāng)初值選的充分靠近時(shí)，才能保證序列收斂。證畢顯然又有第46頁，課件共65頁，創(chuàng)作于2023年2月3.非局部收斂性

定理（Newton迭代法的非局部收斂性）：設(shè)x*是方程f(x)=0在隔根區(qū)間[a,b]內(nèi)的根，如果滿足（2）取使（1）對于x[a,b]，連續(xù)且不變號；

則由Newton迭代公式產(chǎn)生的數(shù)列收斂于根x*。Remark：定理的幾何解釋見下圖。滿足定理?xiàng)l件的情況只有4種。第47頁，課件共65頁，創(chuàng)作于2023年2月yx0aby=f(x)x0(a)x0取靠近b一側(cè)yx0aby=f(x)x0(b)x0取靠近a一側(cè)yx0aby=f(x)x0(c)x0取靠近a一側(cè)yx0aby=f(x)x0(d)x0取靠近b一側(cè)第48頁，課件共65頁，創(chuàng)作于2023年2月證明：僅就圖(c)的情況進(jìn)行證明。此時(shí)，有要證，應(yīng)證數(shù)列{xk}單調(diào)遞增上有界。（1）用數(shù)學(xué)歸納法證明數(shù)列上有界，即證xk<x*。k＝0時(shí)，xk<x*成立。一般的，設(shè)xk<x*成立，再證xk＋1<x*成立即可。將f(x)在xk處作一階Taylor展開，其中k在x與xk之間。因?yàn)閤，xk[a,b],所以k(a,b)。第49頁，課件共65頁，創(chuàng)作于2023年2月將x=x*代入上式，有于是有由已知條件知，上式右端第二項(xiàng)小于零，從而有xk＋1<x*成立。故由數(shù)學(xué)歸納法知，xk<x*（k=0,1,2,…）成立。第50頁，課件共65頁，創(chuàng)作于2023年2月(2)再證明數(shù)列單調(diào)遞增。因?yàn)?，所以，于是Newton迭代公式中的第二項(xiàng)小于零，從而有于是即數(shù)列{xk}是單調(diào)遞增有上界的數(shù)列，且上界為x*。第51頁，課件共65頁，創(chuàng)作于2023年2月設(shè)該數(shù)列的極限為A，則對Newton迭代公式兩邊取極限，有從而得f(A)=0。因?yàn)榉匠蘤(x)=0在隔根區(qū)間[a,b]中只有一個(gè)根，故A＝x*，即（3）證明。證畢第52頁，課件共65頁，創(chuàng)作于2023年2月4.例題

用Newton迭代法建立平方根的迭代公式。解：令，則x2-c=0，這樣把開平方問題轉(zhuǎn)化為求方程f(x)=x2-c=0的正根。Newton迭代公式為：容易證明，只要選取初值x0>0，則可以保證Newton迭代法的收斂性。

第53頁，課件共65頁，創(chuàng)作于2023年2月二、迭代法的收斂階若0<C<1,p=1稱為線性收斂；p>1稱為超線性收斂；p＝2稱為平方收斂（二次收斂）。p

越大，收斂速度越快；反之，p越小，收斂速度就越慢。因此，迭代法的收斂階是對迭代法收斂速度的一種度量。（C稱為漸近誤差常數(shù)）定義：設(shè)收斂于，令迭代誤差，如果存在實(shí)數(shù)及非零正常數(shù)C使得則稱該迭代過程以及該迭代式是p階收斂的，也稱相應(yīng)的迭代法是p階方法。第54頁，課件共65頁，創(chuàng)作于2023年2月定理：（1）在迭代法的局部收斂定理的條件下，即x*是方程的根，滿足迭代函數(shù)在x*

的鄰域內(nèi)可導(dǎo)，且在根x*的某個(gè)鄰域內(nèi)，對于任意xS，有，則迭代法是線性收斂的。（2）由Newton迭代公式xk+1=

(xk)產(chǎn)生的數(shù)列{xk}若滿足Newton迭代法的非局部收斂定理，則Newton迭代法是平方收斂的。證明：（1）因?yàn)榈瘮?shù)(x)在根x*的鄰域內(nèi)可導(dǎo)，故由Lagrange中值定理有其中在xk與x*之間。第55頁，課件共65頁，創(chuàng)作于2023年2月由知，迭代法是線性收斂的。（2）由Newton迭代法的非局部收斂定理證明過程知，即因?yàn)樵卩徲騼?nèi)不變號，故有

即Newton迭代法是平方收斂的。證畢第56頁，課件共65頁，創(chuàng)作于2023年2月三、牛頓迭代法的變形Newton迭代優(yōu)點(diǎn)：

格式構(gòu)造容易；

迭代收斂速度快；Newton迭代缺點(diǎn)：對初值的選取比較敏感，要求初值充

分接近真解；對重根收斂速度較慢；當(dāng)函數(shù)復(fù)雜時(shí)，導(dǎo)數(shù)計(jì)算工作量大．第57頁，課件共65頁，創(chuàng)作于2023年2月1．牛頓下山法牛頓迭代法依賴于x