西安石油大學現(xiàn)代數(shù)值計算方法第3章ppt課件

1、第三章 方程的近似解法,3.0 簡介 3.1 二分法（對分法） 3.2 迭代法 3.3 Newton迭代法 3.4 弦截法,3.0 簡介,求解非線性方程 f(x)=0,一、問題,困難：方程的解難以用公式表達。,例如:1)多項式方程：,需要一定精度的近似解！,2)超越方程:,方程 的解 稱為方程 的根或稱為 的零點。,二、概念,方程可能有多個實根，我們只能逐個求出來。,設(shè)在區(qū)間a,b上方程有一個根，則稱該區(qū)間為方程的一個有根區(qū)間。若在區(qū)間a,b上方程只有一個根，則稱該區(qū)間為方程隔根區(qū)間。,Remark：若能把有根區(qū)間不斷縮小，則可以得出根的近似值。,三、根的隔離,基于函數(shù)f(x)的連續(xù)性質(zhì)，常用

2、的根的隔離的方法有：描圖法與逐步搜索法。,1、描圖法：畫出y=f(x)的簡圖，從曲線與x軸交點的位置確定出隔根區(qū)間，或者將方程等價變形為g1(x)=g2(x)，畫出函數(shù)y= g1(x)和y=g2(x)的簡圖，從兩條曲線交點的橫坐標的位置確定隔根區(qū)間。 P79例1糾錯！,2、逐步搜索法：先確定方程f(x)=0的所有實根所在區(qū)間a,b，再按照選定的步長 （n為正整數(shù)），取點xk=a+kh(k=0,1,n)，逐步計算函數(shù)值f(xk)，依據(jù)函數(shù)值異號以及實根的個數(shù)確定隔根區(qū)間。必要時可調(diào)整步長h，總可把隔根區(qū)間全部找出。,一個有用的結(jié)論：,對于m次代數(shù)方程,其根的模的上下界有如下結(jié)論：,（1）若 ，則

3、方程根的模小于+1。,（2）若 ，則方程根的 模大于 。,P80例2,若 則,3.1 二分法（對分法）,一、算法,設(shè) 在a,b上連續(xù)，f(a)f(b)0且在a,b內(nèi)f(x)=0僅有一個實根 。二分法的基本思想是：逐步將有根區(qū)間分半，通過判別函數(shù)值的符號，進一步搜索有根區(qū)間，將有根區(qū)間縮小到充分小，從而求出滿足給定精度的根 的近似值。,具體算法：,Step1: 計算 中點 的函數(shù)值 。,或 ，則 ，令 ，,Step2:再計算 中點 的函數(shù)值 。,新的有根區(qū)間 的長度為 。,新的有根區(qū)間 的長度為,否則，若有 則 ，,令 。,若 則 ，否則 則 ，,由 及,當對分過程無限繼續(xù)下去，則有根區(qū)間必收斂

4、到一點，即,且,如此對分下去則得到一系列的有根區(qū)間,二、誤差估計,定理1：給定方程 f(x)=0，設(shè) f(x)在區(qū)間a,b上連續(xù)，且f(a)f(b)0，則由二分法產(chǎn)生的序列xk收斂于方程的根x*，且具有誤差估計：,P81例3糾錯！,三、收斂準則,1.事先誤差估計：,利用誤差估計定理，令,得,從而得到對分次數(shù)k1，取xk作為根得近似值x*。,2.事后誤差估計：,給定，每步檢查 ，若成立，則取 ，否則繼續(xù)對分。,Remark3：二分法的優(yōu)點是方法及相應(yīng)的程序均簡單，且對f(x)性質(zhì)要求不高，只要連續(xù)即可。但二分法不能用于求復(fù)數(shù)根和偶數(shù)重根，且收斂速度比較慢。因此，一般常用該方法求根的初始近似值，然

5、后再用其它的求根方法精確化。,Remark2：也可以使用 來控制誤差。,Remark1：由于 ， 故也可以用 來控制誤差。（最常用）,3.2 迭代法,即序列 的極限 為 的根。,一、迭代法,1.基本思想：,因此，我們可以通過求迭代數(shù)列的極限的方法來求得方程f(x)=0的根。,迭代法的幾何意義,收斂的迭代法,發(fā)散的迭代法,Remark：可以通過不同的途徑將f(x)=0化為x=(x)的形式，從而構(gòu)造不同的迭代公式，得到不同的迭代序列。在所有這些構(gòu)造的迭代公式中形成的序列中，有的序列是收斂的，而有些是發(fā)散的。,問題：如何選取合適的迭代函數(shù)(x) ？ 迭代函數(shù)(x)應(yīng)滿足什么條件，序列xk收斂？ 怎樣

6、加速序列xk的收斂？,2.迭代法的收斂定理（P87）,（2）對任意初值x0a,b由迭代公式 產(chǎn)生的序列 必收斂于方程的根 ；,則有,定理1.（全局收斂定理）設(shè)方程 ，如果滿足,（2）存在常數(shù)0L1,使對任意,（1）當xa,b時， ；,（1）方程 在區(qū)間a,b上有唯一的根 ；,（3）誤差估計,證明：,由于 上連續(xù)，作輔助函數(shù),故由連續(xù)函數(shù)的介值定理知，至少存在,又設(shè),即 有唯一的根。,(1) 先證方程根的存在性。,，即 是方程 的根。,故由拉格朗日中值定理知，,（2）,移項，兩邊除以1-L得,（3）由,證畢,3.迭代法的局部收斂定理,迭代法的全局收斂性定理給出的是區(qū)間a,b上的收斂性，稱之為全局

7、收斂性，一般不易驗證，并且在較大的隔根區(qū)間上此定理的條件不一定成立，而只能在根的一個較小的鄰域內(nèi)成立。下面給出局部收斂定理：,則對于任意的初值x0S，迭代公式 產(chǎn)生的序列 必收斂于方程的根 。,當xS，即 時，由Lagrange中值定理有,將前述定理1中的a,b取為 ，則只需證明 即可。,其中在x與x*之間，即S。,證明：,證畢,故,局部收斂定理如何使用?,Remark2：可以證明，若在根 的鄰域中 ，則可以以鄰域內(nèi)任何一點 為初始值，用迭代過程產(chǎn)生的序列就一定不會收斂于 。事實上，,Remark3：當 不取在 的鄰域內(nèi)時可能不收斂。,Remark1：全局與局部收斂定理中的條件都是充分 條件，

8、條件滿足則迭代法收斂，不滿足則不能判定， 此時可以用試算來判定迭代法的是收斂性。,Remark4：全局收斂定理中的兩個誤差估計式實際上 給出了迭代收斂的兩個準則：事后誤差估計與事先誤 差估計（利用估計式可以預(yù)先求出迭代次數(shù)k）。,4.迭代收斂準則,方法一、事先誤差估計法,方法二、事后誤差估計法,先計算滿足誤差要求的迭代次數(shù)k，再進行迭代。,有,由,由,因此可以用 來控制迭代過程。,只要使 ，就可使 ，,對于較為復(fù)雜的迭代函數(shù)，其導(dǎo)數(shù)也較為復(fù)雜，使得L難以取得，因而實際中不常用此方法。,Remark1:迭代方法的優(yōu)點是計算程序簡單，并且雖然是以求解非線性方程的實根來討論的，但類似的結(jié)果完全可以推

9、廣到求方程的復(fù)數(shù)根的情形。,Remark2：由全局收斂定理知，若L1，則xk必然收斂較慢；若L1，則收斂速度快。,1.迭代-加速公式,記 ，則由微分中值定理有,二、迭代加速公式,其中在xk與x*之間。,假定 在根x*附近變化不大，可設(shè) ，由 迭代收斂條件有 ，故上式可寫為：,整理為：,得到迭代加速公式,上式說明，把 作為根的近似值時，其絕對誤差大致為 。如果把該誤差值作為對 的一種補償，便可以得到更好的近似值,記,Remark1：該迭代法對原迭代式的各近似值在根x*的兩側(cè)往復(fù)地趨于x*時較為有效。在這種情況下，不但能加快新序列的收斂，還能有效地防止死循環(huán)的出現(xiàn)。,Remark2：若序列xk單調(diào)

10、趨于x*時，上式不能起到加速收斂的作用。,Remark3：該方法的缺點是需估計 的近似值。,2埃特金（Aitken）加速方法,記,用平均變化率,代替迭代加速公式中的 ，于是有,則,從上式可以看出，第二項是對 的一種補償。,因此可以得下述Aitken加速方法：,Remark：因為迭代過程xk+1= (xk)總是在根x*附近進行，因此用平均變化率代替迭代加速公式中 的是有意義的。,記,對于埃特金（Aitken）加速方法有如下的定理：,定理3：如果由迭代公式xk+1= (xk)產(chǎn)生的數(shù)列xk 滿足：,（1）收斂于根x*；,（2）,則由埃特金（Aitken）加速公式產(chǎn)生的數(shù)列 比數(shù)列xk較快的收斂于根

11、x*，即,一、Newton迭代法,1牛頓法的基本思想與Newton-Raphson公式,取前兩項近似代替 得近似 的線性方程,3.3 Newton迭代法,設(shè) 是 的一個近似根，則,基本思想：將非線性方程轉(zhuǎn)化為線性方程來求解。,由 知 是 處 的 切線 與 軸交點的橫坐標，,故Newton法的幾何意義是逐次用切線代替曲線， 求切線與橫坐標軸的交點。 Newton法亦稱為切線法。（如下圖）,y,x,0,a,b,x0,x1,x2,x*,y=f(x),Newton迭代法逼近過程,證明：只需證滿足迭代法局部收斂定理的兩個條件。,2.局部收斂性(P97定理1),及條件（1）（2）知，(x)在x*的鄰域可導(dǎo)

12、。,定理（Newton迭代法局部收斂性）：設(shè) 為 的根，如果：（1）函數(shù)f(x)在 的鄰域具有連續(xù)的二階導(dǎo)數(shù)；（2）在 的鄰域 。,則存在 的某個鄰域 ，對于任意的初始值x0S，由Newton迭代公式產(chǎn)生的數(shù)列收斂于根 。,由迭代函數(shù) 得:,Remark：上述定理對于初值x0的要求比較高，只有當初值選的充分靠近 時， 才能保證序列收斂。,證畢,根據(jù)連續(xù)函數(shù)的性質(zhì)，一定存在x*的某個鄰域 ，對于任意的xS，有,顯然又有,3.非局部收斂性（P98定理2）,定理（Newton迭代法的非局部收斂性）：設(shè)x*是方程f(x)=0在隔根區(qū)間a,b內(nèi)的根，如果滿足,（2）取 使,（1）對于xa,b， 連續(xù)且不

13、變號；,則由Newton迭代公式產(chǎn)生的數(shù)列收斂于根x*。,Remark：定理的幾何解釋見下圖。滿足定理條件的情況只有4種。,證明：僅就圖(c)的情況進行證明。此時，有,要證 ，應(yīng)證數(shù)列xk單調(diào)遞增上有界。,（1）用數(shù)學歸納法證明數(shù)列上有界，即證xkx*。,k0時，xkx*成立。,一般的，設(shè)xkx*成立，再證xk1x*成立即可。,將f(x)在xk處作一階Taylor展開，,其中k在x與xk之間。因為x， xka,b,所以k(a,b)。,將x=x*代入上式，有,于是有,由已知條件知，上式右端第二項小于零，從而有xk1x*成立。,故由數(shù)學歸納法知，xkx*（k=0,1,2,）成立。,(2)再證明數(shù)列

14、單調(diào)遞增。,因為 ，所以 ，,于是Newton迭代公式,中的第二項小于零，從而有,于是,即數(shù)列xk是單調(diào)遞增有上界的數(shù)列，且上界為x*。,設(shè)該數(shù)列的極限為c，則對Newton迭代公式兩邊取極限，有,從而得 f(c)=0。,因為方程f(x)=0在隔根區(qū)間a,b中只有一個根，故cx*，即,（3）證明 。,證畢,4.例題,用Newton迭代法建立平方根 的迭代公式。,解：,令 ，則x2-c=0，這樣把開平方問題轉(zhuǎn)化為求方程 f(x)=x2-c=0 的正根。,Newton迭代公式為：,容易證明，只要選取初值x00，則可以保證Newton迭代法的收斂性。 （ 見下圖 ） #,二、迭代法的收斂階,若01稱

15、為超線性收斂；p2稱為平方收斂（二次收斂）。 p 越大，收斂速度越快；反之，p越小，收斂速度就越慢。因此，迭代法的收斂階是對迭代法收斂速度的一種度量。,（ C稱為漸近誤差常數(shù)）,定義：設(shè) 收斂于 ，令迭代誤差 ，如果存在實數(shù) 及非零正常數(shù)C使得,則稱該迭代過程以及該迭代式是p階收斂的，也稱相應(yīng)的迭代法是p階方法。,定理：（1）在迭代法的局部收斂定理的條件下，即x*是方程 的根，滿足迭代函數(shù) 在x* 的鄰域內(nèi)可導(dǎo)，且在根x*的某個鄰域 內(nèi)，對于任意xS，有 ，則迭代法是線性收斂的。 （2）由Newton迭代公式xk+1= (xk)產(chǎn)生的數(shù)列xk 若滿足Newton迭代法的非局部收斂定理，則New

16、ton迭代法是平方收斂的。,證明：（1）因為迭代函數(shù)(x)在根x*的鄰域內(nèi)可導(dǎo)，故由Lagrange中值定理有,其中在xk與x*之間。,由 知，迭代法是線性收斂的。,（2）由Newton迭代法的非局部收斂定理證明過程知，,即,因為 在鄰域內(nèi)不變號，故有,即Newton迭代法是平方收斂的。,證畢,3.4 弦截法,一、單點弦截法,幾何意義：依次用弦線代替曲線，用線性函數(shù)的零點作為函數(shù)f(x)的根。,設(shè)方程f(x)=0，隔根區(qū)間為a,b。令y=f(x)，若 在(a,b)內(nèi)不變號，則圖形與Newton迭代法一樣有四種情況。取下圖為例來說明單點弦截法。,Step1:記b=x1，過點(a,f(a)， (x

17、1,f(x1)作直線，其方程為：,該直線與x軸的交點的橫坐標x2為,a=x0,b=x1,x,y,0,x2,x3,A,B,y=f(x),x*,單點弦截法逼近過程,利用后面將要學習的插值技術(shù)，可以證明f(x2)0，從而確定新的隔根區(qū)間為a,x2。,Step2:過點(a,f(a)，(x2,f(x2)作直線，方程為：,該直線與x軸的交點的橫坐標x3為,同理可以確定新的隔根區(qū)間為a,x3。, ,Stepn:過點(a,f(a)， (xk,f(xk)作直線，方程為：,該直線與x軸的交點的橫坐標xk+1為,由此得到近似根的序列xk。因為迭代公式中有a和f(a) ，所以稱點A(a,f(a)為不動點。在四種情況中，有兩種點A(a,f(a)為不動點，兩種點B(b,f(b)為不動點。記不動點的坐標為(x0,f(x0)，則迭代公式可以寫為：,定理（單點弦截法的收斂定理）：設(shè)x*是方程f(x)=0在隔根區(qū)間a,b內(nèi)的根，若 (1)對于xa,b， 連續(xù)且不變號； (2)選取初值x0a,b，使 ， x0選定a，b中的一個，則x1為另一個，則由單點弦截法迭代公式產(chǎn)生的數(shù)列單調(diào)收斂于根x*。,Remark：單點弦截法的收斂階為1。,二.雙點弦截法,xk,xk-1,x,y,0,xk1,y=f(x),x*,雙點弦截法基本思想,設(shè)xk-1，xk是根x*附近的兩點，過點(xk-1,f(xk-1)，(xk,f(xk)作直線