高校工程數(shù)學(xué)迭代法求方程根教學(xué)課件

1、2.3 迭代法求方程根迭代法求方程根迭代法是一種重要的逐次逼近方法。這種方法用迭代法是一種重要的逐次逼近方法。這種方法用某個(gè)固定公式反復(fù)校正根的近似值，使之逐步精某個(gè)固定公式反復(fù)校正根的近似值，使之逐步精確化，最后得到滿足精度要求的結(jié)果。確化，最后得到滿足精度要求的結(jié)果。主要內(nèi)容：主要內(nèi)容： 1、迭代法原理、迭代法原理 2、迭代的收斂性、迭代的收斂性一、迭代法原理一、迭代法原理f (x) = 0 x = g (x)等價(jià)變換等價(jià)變換f (x) 的根的根 g(x) 的不動(dòng)點(diǎn)的不動(dòng)點(diǎn)1101333xxxxxx思思路路從一個(gè)初值從一個(gè)初值 x0 出發(fā)出發(fā),計(jì)算計(jì)算 x1 = g(x0), x2 = g

2、(x1), , xk+1 = g(xk), 若若 xk 收斂，即存在收斂，即存在 x* 使得使得 ，只要，只要g 連連續(xù)，則續(xù)，則 ，也就是，也就是 x* = g(x* )，即，即x* 是是 g 的根，也就是的根，也就是f 的根。若的根。若 xk發(fā)散，則迭代發(fā)散，則迭代 法失敗。法失敗。*limxxkk kkkkxgx limlim1xxxxcos0cos迭代法原理迭代法原理例例2-3-1 求方程求方程f(x0)=x3x1=0 （2.3.1）在在x=1.5附近的一個(gè)根。附近的一個(gè)根。解解 將方程（將方程（2.3.1）改寫(xiě)成下列形式）改寫(xiě)成下列形式 （2.3.2）用所給的初始近似用所給的初始近似

3、x0=1.5代入代入(2.3.2)的右端，得到的右端，得到計(jì)算結(jié)果說(shuō)明，計(jì)算結(jié)果說(shuō)明，x0并不滿足方程。如果改用并不滿足方程。如果改用x1作為近似值作為近似值代入代入(2.3.2)的右端，又得：的右端，又得：例例2-3-1由于由于x2與與x1仍有偏差，我們?cè)偃∪杂衅睿覀冊(cè)偃2作為近似值，作為近似值，并重復(fù)這個(gè)步驟。如此續(xù)下去，這種逐步校正的并重復(fù)這個(gè)步驟。如此續(xù)下去，這種逐步校正的過(guò)程稱作迭代過(guò)程，這里迭代公式：過(guò)程稱作迭代過(guò)程，這里迭代公式： （2.3.3）表表2-3記錄了各步迭代的結(jié)果。我們看到，如果記錄了各步迭代的結(jié)果。我們看到，如果僅取六位數(shù)字，那么結(jié)果僅取六位數(shù)字，那么結(jié)果x7

4、與與x8完全相同，這時(shí)完全相同，這時(shí)可認(rèn)為可認(rèn)為x7實(shí)際上已滿足方程實(shí)際上已滿足方程(2.3.2)，從而得到所，從而得到所求的根為：求的根為：x*=1.32472例例2-3-1精確到小數(shù)點(diǎn)后五位精確到小數(shù)點(diǎn)后五位5102132472. 1x迭代法的原理迭代法的原理對(duì)于一般形式的方程對(duì)于一般形式的方程f(x)=0，我們先設(shè)法將它化為，我們先設(shè)法將它化為下列形式：下列形式：x=g(x) （2.3.4）方程方程(2.3.4)的右端含有未知的的右端含有未知的x，因此稱之為隱式，因此稱之為隱式的。求根的困難正是在于方程的。求根的困難正是在于方程(2.3.4)具有隱式的形具有隱式的形式。式。如果給出根的某

5、個(gè)近似值如果給出根的某個(gè)近似值xk，將它代入，將它代入(2.3.4)的右的右端，則端，則(2.3.4)式立即變成顯式的：式立即變成顯式的：xk+1=g(xk) （2.3.5）迭代法原理迭代法原理這樣，從給定的初始近似值這樣，從給定的初始近似值x0出發(fā)，按顯式公式出發(fā)，按顯式公式(2.3.5)可以得到一個(gè)數(shù)列可以得到一個(gè)數(shù)列x0, x1, x2, , xk, 如果這個(gè)數(shù)列有極限，則稱迭代格式如果這個(gè)數(shù)列有極限，則稱迭代格式(2.3.5)是收斂是收斂的，這時(shí)數(shù)列的，這時(shí)數(shù)列xk的極限的極限就是方程就是方程x=g(x) 的根。的根。迭代法原理迭代法原理xk+1=g(xk)稱為迭代格式，稱為迭代格式，

6、g(x)稱為迭代函數(shù)；稱為迭代函數(shù)；x0稱稱為迭代初值，數(shù)列為迭代初值，數(shù)列xk稱為迭代序列。稱為迭代序列。迭代法迭代法思想：思想：將隱式方程式將隱式方程式 f(x)=0的求根問(wèn)題歸結(jié)為計(jì)的求根問(wèn)題歸結(jié)為計(jì)算一組顯式算一組顯式xk+1 = g(xk) ，也就是說(shuō)，迭代過(guò)程是一個(gè)逐，也就是說(shuō)，迭代過(guò)程是一個(gè)逐步顯式化的過(guò)程。步顯式化的過(guò)程。迭代法迭代法：是一種逐次逼近的方法。是一種逐次逼近的方法。它是它是用某個(gè)固定公式反用某個(gè)固定公式反復(fù)校正根的近似值，使之逐步精確，最后得到滿足精度要復(fù)校正根的近似值，使之逐步精確，最后得到滿足精度要求的結(jié)果。求的結(jié)果。 迭迭代代過(guò)過(guò)程程可以用幾何圖象來(lái)表明迭代

7、過(guò)程?？梢杂脦缀螆D象來(lái)表明迭代過(guò)程。方程方程x=g(x)的求根問(wèn)題在幾何上就是要確定曲線的求根問(wèn)題在幾何上就是要確定曲線y=g(x)與直與直線線y=x的交點(diǎn)的交點(diǎn)P*（如圖）。（如圖）。對(duì)于對(duì)于x*的某個(gè)初始近似的某個(gè)初始近似x0，在曲線，在曲線y=g(x)上作出以上作出以x0為橫坐為橫坐標(biāo)的一點(diǎn)標(biāo)的一點(diǎn)P0，點(diǎn)，點(diǎn)P0的縱坐標(biāo)為的縱坐標(biāo)為g(x0)=x1。迭迭代代過(guò)過(guò)程程過(guò)過(guò)P0引平行于引平行于x軸的直線，設(shè)交直線軸的直線，設(shè)交直線y=x于點(diǎn)于點(diǎn)Q1。過(guò)。過(guò)Q1再作平再作平行于行于y軸的直線，它與曲線軸的直線，它與曲線y=g(x)的交點(diǎn)記作的交點(diǎn)記作P1。容易看出，近似值容易看出，近似值x1

8、=g(x0)即為點(diǎn)即為點(diǎn)P1的橫坐標(biāo)。按圖中箭頭所的橫坐標(biāo)。按圖中箭頭所示的路徑繼續(xù)作下去，在曲線示的路徑繼續(xù)作下去，在曲線y=g(x)上得到一個(gè)點(diǎn)列上得到一個(gè)點(diǎn)列P1,P2,，其橫坐標(biāo)分別等于依格式其橫坐標(biāo)分別等于依格式xk+1=g(xk)求得的近似值求得的近似值x1, x2, 。如。如果迭代收斂，則點(diǎn)列果迭代收斂，則點(diǎn)列P1, P2,將越來(lái)越逼近所求的交點(diǎn)將越來(lái)越逼近所求的交點(diǎn)P*。簡(jiǎn)單迭代法的幾何意義：簡(jiǎn)單迭代法的幾何意義：把求方程把求方程f(x)=0的根的問(wèn)題，轉(zhuǎn)化為求的根的問(wèn)題，轉(zhuǎn)化為求y=g(x)和和y=x兩條曲線的交點(diǎn)問(wèn)題，交點(diǎn)的橫坐標(biāo)就是兩條曲線的交點(diǎn)問(wèn)題，交點(diǎn)的橫坐標(biāo)就是方程

9、的方程的x*。迭代法的幾何意義迭代法的幾何意義迭迭代代法法的的幾幾何何意意義義xyy = xxyy = xxyy = xxyy = xx*x*x*x*y= g(x)y= g(x)y= g(x)y= g(x)x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p1迭代過(guò)程迭代過(guò)程然而迭代法的效果并不是總能令人滿意的。然而迭代法的效果并不是總能令人滿意的。例例2-3-1a 求方程求方程 f(x0)=x3x1=0 （2.3.1）在在x=1.5附近的一個(gè)根。附近的一個(gè)根。解解 將方程（將方程（2.3.1）改寫(xiě)成另一種等價(jià)形式：）改寫(xiě)成另一種等價(jià)形式：x=x31建立迭代格式：建立迭代

10、格式：例例2-3-1a 迭代初值仍取迭代初值仍取x0=1.5，則有：，則有：x1=2.375x2=12.3976繼續(xù)迭代下去已經(jīng)沒(méi)有必要，因?yàn)榻Y(jié)果顯然會(huì)越繼續(xù)迭代下去已經(jīng)沒(méi)有必要，因?yàn)榻Y(jié)果顯然會(huì)越來(lái)越大，不可能趨向于某個(gè)極限。這種不收斂的來(lái)越大，不可能趨向于某個(gè)極限。這種不收斂的迭代過(guò)程稱作是發(fā)散的。迭代過(guò)程稱作是發(fā)散的。 一個(gè)發(fā)散的迭代過(guò)程，縱使進(jìn)行了千百次迭代，一個(gè)發(fā)散的迭代過(guò)程，縱使進(jìn)行了千百次迭代，其結(jié)果也是毫無(wú)價(jià)值的。其結(jié)果也是毫無(wú)價(jià)值的。補(bǔ)充補(bǔ)充例例1 例例1 用簡(jiǎn)單迭代法求區(qū)間用簡(jiǎn)單迭代法求區(qū)間(2,3)內(nèi)方程內(nèi)方程x3-2x-5=0的根的根解一解一 將方程兩邊同加將方程兩邊同加

11、2x+5,再開(kāi)三次方，得式再開(kāi)三次方，得式(5-4)型同解方程型同解方程 x=作迭代格式作迭代格式 xk+1= k=0,1,取取x0=2.5,迭代得迭代得 x1=2.154434690,x2=2.103612029,x3=2.095927410X4=2.094760545,x5=2.094583250,x6=2.0945563091limkkx352 x352kxX7=2.094552215,x8=2.094551593,x9=2.094551498X10=2.094551484,x11=2.094551482=x12由于由于x12=x11,再迭代已無(wú)變化，可見(jiàn)再迭代已無(wú)變化，可見(jiàn) x11補(bǔ)充

12、補(bǔ)充例例1 補(bǔ)充補(bǔ)充例例1 解二解二 將方程將方程x3-2x-5=0兩邊同加兩邊同加2x3+5,再同除再同除3x2-2,得同解方得同解方程程 x=(2x3+5)/(3x2-2)作迭代格式作迭代格式 xk+1=(2xk3+5)/(3xk2-2)取取x0=2.5,得迭代序得迭代序列列:x1=2.164179104,x2=2.097135356,x3=2.094555232,X4=2.094551482=x5,故故 x4補(bǔ)充補(bǔ)充例例1 作迭代格式作迭代格式 xk+1=(xk3-5)/2令令x0=2.5,得迭代序列得迭代序列:x1=5.3125,x2=72.46643066,X3=190272.011

13、8,x4=3.444250536 1016,x5=2.0429333981046,計(jì)算計(jì)算x6時(shí)溢出時(shí)溢出二、迭代的收斂性二、迭代的收斂性現(xiàn)在研究格式現(xiàn)在研究格式xk+1=g(xk)的收斂性。設(shè)的收斂性。設(shè)x*為方程為方程(2.3.4)的根，的根，x*=g(x*)利用微分中值定理，有利用微分中值定理，有x*xk+1=g(x*)g(xk)=g()(x*xk) （2.3.6）其中，其中，是是x*與與xk之間某一點(diǎn)。于是，如果存在正之間某一點(diǎn)。于是，如果存在正數(shù)數(shù)q1，使得，使得|g(x)|q1 （2.3.7）收斂性收斂性則由則由(2.3.6)式得：式得：|x*xk+1|q|x*xk|令令ek=|x

14、*xk|（k=0,1,2,）表示迭代的誤差，則由）表示迭代的誤差，則由上式可得：上式可得：ek+1qek利用這一誤差關(guān)系式反復(fù)遞推，即得利用這一誤差關(guān)系式反復(fù)遞推，即得ekqke0因而當(dāng)因而當(dāng)k時(shí)將有時(shí)將有ek0。收斂性條件收斂性條件有下述論斷：有下述論斷：如果如果g(x)具有連續(xù)的一階導(dǎo)數(shù)，并且對(duì)所有的具有連續(xù)的一階導(dǎo)數(shù)，并且對(duì)所有的x，|g(x)|q1（q為某個(gè)定數(shù)），那么，格式為某個(gè)定數(shù)），那么，格式xk+1=g(xk)對(duì)于任意初值對(duì)于任意初值x0均收斂，并且，均收斂，并且，q的值越小，收斂的速度越快。的值越小，收斂的速度越快。對(duì)于一個(gè)收斂的迭代過(guò)程，雖然理論上作為迭代值對(duì)于一個(gè)收斂的迭

15、代過(guò)程，雖然理論上作為迭代值xk的極限可以得到準(zhǔn)確解，但在實(shí)際計(jì)算時(shí)，我們只能的極限可以得到準(zhǔn)確解，但在實(shí)際計(jì)算時(shí)，我們只能迭代有限多次，因此有個(gè)控制迭代次數(shù)的問(wèn)題。迭代有限多次，因此有個(gè)控制迭代次數(shù)的問(wèn)題。收斂性收斂性利用收斂性條件利用收斂性條件(2.3.7)，可得：，可得：|xk+1xk|=|g(xk)g(xk-1)|q|xkxk-1|據(jù)此關(guān)系式反復(fù)遞推，對(duì)任意正整數(shù)據(jù)此關(guān)系式反復(fù)遞推，對(duì)任意正整數(shù)r，有，有|xk+rxk+r-1|qr|xkxk-1|于是對(duì)任意正整數(shù)于是對(duì)任意正整數(shù)p，有，有|xk+pxk|xk+pxk+p-1|+|xk+p-1xk+p-2|+|xk+1xk|(qp+qp

16、-1+q)|xkxk-1|q/(1q)|xkxk-1|收斂性收斂性令令p，由上式可得，由上式可得|x*xk|q/(1q)|xkxk-1|這個(gè)誤差估計(jì)式說(shuō)明，只要迭代值的偏差這個(gè)誤差估計(jì)式說(shuō)明，只要迭代值的偏差|xkxk-1|相當(dāng)小，就可以保證迭代誤差相當(dāng)小，就可以保證迭代誤差|x*xk|足夠小，因此足夠小，因此可用條件：可用條件：|xkxk-1|來(lái)控制迭代過(guò)程的結(jié)束。來(lái)控制迭代過(guò)程的結(jié)束。迭代法框圖迭代法框圖迭代法的一個(gè)突迭代法的一個(gè)突出優(yōu)點(diǎn)是算法的出優(yōu)點(diǎn)是算法的邏輯結(jié)構(gòu)簡(jiǎn)單。邏輯結(jié)構(gòu)簡(jiǎn)單。圖圖2-6描述了迭代描述了迭代格式格式xk+1=g(xk)的的計(jì)算過(guò)程，其中計(jì)算過(guò)程，其中x0，x1分別表示每分別表示每次迭代的初值和次迭代的初值和終值。終值。迭代收斂條件迭代收斂條件上面給出了保證迭代收斂的條件，即要求對(duì)所有上面給出了保證迭代收斂的條件，即要求對(duì)所有的的x應(yīng)成立應(yīng)成立|g (x)|q1。很明顯，這個(gè)要求是相當(dāng)。很明顯，這個(gè)要求是相當(dāng)苛刻的?？量痰?。設(shè)在根設(shè)在根x*處進(jìn)行考察，如果處進(jìn)行考察，如果|g(x*)|1，那么在根，那么在根x*的某個(gè)鄰域內(nèi)有的某個(gè)鄰域內(nèi)有|g(x)|q1，這時(shí)，只要迭代值，這時(shí)，只要迭代值xk均屬于這個(gè)鄰域，即可保證迭代格式均屬于這個(gè)鄰域，即可保證迭代格式xk+1=g(xk)