研究生數(shù)值分析(3-4)

1、數(shù)值分析數(shù)值分析第第4 4章章非線性方程與非線性方程與非線性方程組的迭代解法非線性方程組的迭代解法1 非線性方程的迭代解法非線性方程的迭代解法 設(shè)非線性方程設(shè)非線性方程 ，如果有數(shù)，如果有數(shù) 使使 ，則稱，則稱 為方程的根，或稱為函數(shù)為方程的根，或稱為函數(shù)的零點。的零點。( )0f x *x*()0f x*x 描述工程和科學(xué)技術(shù)實際問題的數(shù)學(xué)模描述工程和科學(xué)技術(shù)實際問題的數(shù)學(xué)模型，通常都難以獲得根的簡單易用的顯式表達(dá)型，通常都難以獲得根的簡單易用的顯式表達(dá)式，因此，要研究求近似根的方法，并討論這式，因此，要研究求近似根的方法，并討論這些方法的收斂性和收斂速度。些方法的收斂性和收斂速度。求方程近

2、似根的問題，一般分兩步進(jìn)行：求方程近似根的問題，一般分兩步進(jìn)行： （1）求根的隔離區(qū)間。確定根所在的區(qū)間，）求根的隔離區(qū)間。確定根所在的區(qū)間，使方程在這個小區(qū)間有且僅有一個根。所求的隔離使方程在這個小區(qū)間有且僅有一個根。所求的隔離區(qū)間越小越好。區(qū)間越小越好。 （2）將近似根精確化。用求方程根的數(shù)值方）將近似根精確化。用求方程根的數(shù)值方法，使求得的近似根逐步精確化，使其滿足給定的法，使求得的近似根逐步精確化，使其滿足給定的精度要求。精度要求。在方程求近似根的方法中，最直觀、最簡單在方程求近似根的方法中，最直觀、最簡單的方法就是二分法。的方法就是二分法。 設(shè)函數(shù)設(shè)函數(shù) 在在 上連續(xù)，嚴(yán)格單調(diào)，上連

3、續(xù)，嚴(yán)格單調(diào)，且且 ，則，則 為為 的一個有根的一個有根區(qū)間。區(qū)間。( )0f x , a b( ) ( )0f a f b , a b( )0f x 對分法的基本思想是：對分法的基本思想是： 用對分區(qū)間的方法根據(jù)分點處函數(shù)用對分區(qū)間的方法根據(jù)分點處函數(shù) 的符的符號逐步將有根區(qū)間縮小，使在足夠小的區(qū)間內(nèi)，號逐步將有根區(qū)間縮小，使在足夠小的區(qū)間內(nèi)，方程有且只有方程有且只有1個實根。個實根。( )f x1 對分法對分法 首先取首先取 的中點的中點 ，將區(qū)間，將區(qū)間 分為兩半。若分為兩半。若 ，則，則 就是就是 的實根的實根 ；否則檢查否則檢查 與與 是否異號，即是否是否異號，即是否 成立。成立。,

4、ab02abx,a b0()0f x0 x( )0f x *x0()f x( )f a0( ) ()0f a f x 如果成立，則如果成立，則 必在必在 的左側(cè)，這時取的左側(cè)，這時取110,aa bx ；否則；否則 必在必在 的右側(cè)，這時取的右側(cè)，這時取101,ax bb 。這樣，就得到一個新的有根區(qū)間。這樣，就得到一個新的有根區(qū)間11,ab ，其長度僅是，其長度僅是 的一半。的一半。,a b*x0 x*x0 x 對于縮小了的有根區(qū)間對于縮小了的有根區(qū)間 ，又可實施同樣的，又可實施同樣的11,ab1112abx11,ab1x11()()0f af x*x1x22,ab11,ab手續(xù)，即用中點手

5、續(xù)，即用中點 將區(qū)間將區(qū)間 再分為兩半，再分為兩半，然后判斷然后判斷 是不是根，并用是不是根，并用 是否成立，是否成立，判斷所求根判斷所求根 在在 的哪一側(cè)，從而確定一個新的的哪一側(cè)，從而確定一個新的有根區(qū)間有根區(qū)間 ，其長度是，其長度是 的一半。的一半。 如此反復(fù)下去，進(jìn)行如此反復(fù)下去，進(jìn)行 次對分之后，就得到次對分之后，就得到一組不斷縮小的有根區(qū)間一組不斷縮小的有根區(qū)間k1122 , ,kka ba ba ba b從而從而 的長度的長度 如果無限繼續(xù)下去，如果無限繼續(xù)下去，,kka b2kkkabba這些區(qū)間最終必收縮于一點這些區(qū)間最終必收縮于一點 ，該點就是要求的根。，該點就是要求的根。

6、 *x,kka b 以以 的中點的中點 作為所求根的近似值，作為所求根的近似值，2kkkabxk122kkkkabbaxx0k12kbakx則第則第 個根的誤差估計式個根的誤差估計式對于所給精度對于所給精度 ，只要數(shù)，只要數(shù) 滿足滿足則則 就是一個滿足精度要求的近似根。就是一個滿足精度要求的近似根。 例例1：用二分法求方程：用二分法求方程2( )sin04xf xx210的非零實根的近似值，使誤差不超過的非零實根的近似值，使誤差不超過 。( )cos2xfxx1.62x( )0,( )fxf x解：因為解：因為當(dāng)當(dāng) 時時， 為單調(diào)減少函數(shù)為單調(diào)減少函數(shù)(1.6)0, (2)0ff( )0f x

7、 1.6, 22121.6102kln 405.332ln 2k 001.6,2ab又又 ，因此，因此 在在只有只有1個非零實根。由個非零實根。由求得求得所以只要二分所以只要二分6次，才能得到滿足精度要求的根。次，才能得到滿足精度要求的根。0()1.82abx0()0.1640f x因為因為 ，所以取，所以取00( ) ()0f b f x10101.8,2axbb再令再令 ，則，則1111.92abx1()0.0440f x11( ) ( ) 0f b f x 21211.9,2axbb如此繼續(xù)下去，即得計算結(jié)果如下表。如此繼續(xù)下去，即得計算結(jié)果如下表。記記 ，令，令 ，則，則因為因為 ，所

8、以取，所以取取取 ，即可滿足精度要求。，即可滿足精度要求。*6661.934375 1.932abxxkka()kf akx( )kf xkb( )kf b 的符號的符號 的符號的符號 的符號的符號01234561.6(+)1.8(+)1.9(+)1.9(+)1.925(+)1.925(+)1.93125(+)1.8(+)1.9(+)1.95(-)1.925(+)1.9375(-)1.93125(+)1.934375(-)2(-)2(-)2(-)1.95(-)1.95(-)1.9375(-)1.9375(-)( )f x12對分法的優(yōu)點：對分法的優(yōu)點：計算簡單，方法可靠，只要求計算簡單，方法可

9、靠，只要求 連續(xù)，對連續(xù)，對函數(shù)的性質(zhì)要求較低。函數(shù)的性質(zhì)要求較低。它的缺點是：它的缺點是：不能求偶數(shù)重根，也不能求復(fù)根，收斂速度與以不能求偶數(shù)重根，也不能求復(fù)根，收斂速度與以為公比的等比級數(shù)相同，不算太快。為公比的等比級數(shù)相同，不算太快。 一般求方程的近似根，不大單獨使用，常用一般求方程的近似根，不大單獨使用，常用來為其它方法求方程近似根提供好的初值。方程來為其它方法求方程近似根提供好的初值。方程求根最常用的方法是迭代法。求根最常用的方法是迭代法。2 簡單迭代法及其收斂性簡單迭代法及其收斂性 迭代法是數(shù)值計算中一類典型方法，不僅用迭代法是數(shù)值計算中一類典型方法，不僅用于方程求根，而且用于方程

10、組求解，矩陣求特征于方程求根，而且用于方程組求解，矩陣求特征值。值。 迭代法的基本思想是一種逐次逼近的方法，迭代法的基本思想是一種逐次逼近的方法，首先給定一個粗糙的初值，然后用同一個迭代公首先給定一個粗糙的初值，然后用同一個迭代公式，反復(fù)校正這個初值，直到滿足預(yù)先給出的精式，反復(fù)校正這個初值，直到滿足預(yù)先給出的精度要求。度要求。 下面的各種求根方法，實質(zhì)上就是如何構(gòu)造下面的各種求根方法，實質(zhì)上就是如何構(gòu)造一個合適的迭代公式。一個合適的迭代公式。( )0f x ,a b( )xg x 0 , xa b1()kkxg x 012,xxxk kx*x( )g x*x*()xg x*x(1) 簡單迭代

11、法簡單迭代法已知方程已知方程 （1）在）在 內(nèi)有內(nèi)有1個根。個根。將方程（將方程（1）改寫成等價形式）改寫成等價形式 （2）取取 ，用遞推公式，用遞推公式 （3）可得序列可得序列 ，如果當(dāng)，如果當(dāng) 時，序列時，序列有極限有極限 ，且，且 在在 連續(xù)，則在（連續(xù)，則在（3）式兩邊）式兩邊取極限，得取極限，得 ，因而，因而 是方程（是方程（2）的根。）的根。*x由于方程（由于方程（2）與方程（）與方程（1）等價，因而）等價，因而也是方程（也是方程（1）的根。這種求方程近似根的方法稱）的根。這種求方程近似根的方法稱為簡單迭代法。為簡單迭代法。( )g x0 xkxkx*0 xxkx,a b稱為迭代函

12、數(shù)稱為迭代函數(shù)稱為根的初始近似值稱為根的初始近似值稱為根的稱為根的k次近似值次近似值稱為迭代序列稱為迭代序列當(dāng)?shù)蛄惺諗?，則說迭代法收斂當(dāng)?shù)蛄惺諗?，則說迭代法收斂當(dāng)當(dāng) ，迭代序列，迭代序列 在在 內(nèi)無極限，內(nèi)無極限，則說迭代法發(fā)散則說迭代法發(fā)散。解：因為解：因為2( )31fxx(1,2)x( )0fx 1,2( )f x當(dāng)當(dāng) 時時,上單調(diào)增加函數(shù)上單調(diào)增加函數(shù) 有有1個實根個實根將原方程轉(zhuǎn)化為等價方程將原方程轉(zhuǎn)化為等價方程(1) ，這時，這時 , 取取 31xx3( )1g xx01.5x 311kkxx1,2,3k 由迭代公式由迭代公式求得求得所以在所以在例例2：求方程：求方程 的根

13、。的根。3( )10f xxx 3310332133323343335433653376338712.51.3572112.35721.3308612.330861.3258812.325881.3249412.324941.3247612.324761.3247312.324731.3247212.324721.32472xxxxxxxxxxxxxxxx可以看出，迭代序列收斂?？梢钥闯?，迭代序列收斂。kkx*1.32472x 當(dāng)當(dāng) 越來越大時，越來越大時， 接近方程的近似根接近方程的近似根 。（2） ，這時，這時31xx3( )1g xx仍取初值仍取初值 ，得迭代公式，得迭代公式01.5x

14、311kkxx 1,2,3k 123942.37512.39651904.016.90252 10 xxxx迭代序列發(fā)散。迭代序列發(fā)散。 按這一迭代公式計算下去，當(dāng)按這一迭代公式計算下去，當(dāng) 變大時，變大時， 遠(yuǎn)離的遠(yuǎn)離的 精確根。精確根。kkx( )0f x 用迭代法求方程近似根的基本問題用迭代法求方程近似根的基本問題( )g xkx就是就是 如何如何構(gòu)造才能使迭代序列構(gòu)造才能使迭代序列 收斂。收斂。yx( )yg xP*x迭代法的幾何意義迭代法的幾何意義求方程（求方程（2）的根，實質(zhì)上就是求直線）的根，實質(zhì)上就是求直線與曲線與曲線 的交點的交點 的橫坐標(biāo)的橫坐標(biāo) ，如圖。，如圖。1()kk

15、xg x( )yg x()1gx（2）如果迭代公式）如果迭代公式 發(fā)散，則迭代函數(shù)發(fā)散，則迭代函數(shù)1()kkxg x( )yg x( )1g x 從圖可以看出：從圖可以看出：（1）如果迭代公式）如果迭代公式 收斂，則迭代函數(shù)收斂，則迭代函數(shù)曲線走勢平坦，即曲線走勢平坦，即曲線走勢陡峭，即曲線走勢陡峭，即 注意：當(dāng)恒有注意：當(dāng)恒有 時，迭代公式時，迭代公式 一定是發(fā)散的。一定是發(fā)散的。( )1g x 1()kkxg x*0 xx1111( )()( )kkkkkkkkxxg xg xgxxxx1()kkxx110kkxxxx10 xxkx1()kkxg x因為對任意給定的初值因為對任意給定的初值

16、 ，由，由知知 ，而，而 為非零常數(shù)，所以迭代為非零常數(shù)，所以迭代序列序列 發(fā)散，即迭代公式發(fā)散，即迭代公式 是發(fā)散的。是發(fā)散的。 若迭代函數(shù) 滿足條件( )g x（1） 在區(qū)間 上 存在，且 , a b( )g x( )1g xL （2） 對任意 ，都有 , xa b( ) , g xa b則（10）對任意初始近似值 ，迭代法0 , xa b1()kkxg xkx( )xg x ,a b*x（20） （1） （30） （2）*101kkLxxxxL定理定理1 1（迭代法收斂的充分條件）產(chǎn)生的迭代序列 都收斂于方程 在上的唯一實根 ；kkkxxLxx111證證 （1）令）令)()(xgxxF，

17、則，則,)(baCxF由定理條件可知由定理條件可知,0)()(agaaF0)()(bgbbF若上面兩個不等式中有一個等號成立，若上面兩個不等式中有一個等號成立，則方程則方程)(xgx 有根有根ax 或或bx 否則，根據(jù)連續(xù)函數(shù)的介值定理否則，根據(jù)連續(xù)函數(shù)的介值定理必存在必存在),(bax ，使，使0)()(xgxxF即方程即方程)(xgx 有根有根),(bax 設(shè)有兩個不同的設(shè)有兩個不同的),(,21baxx使使)(11xgx，)(22xgx則由微分中值定理和定理條件有則由微分中值定理和定理條件有2121212121)()()(xxxxLxxgxgxgxx其中其中在在21xx之間。之間。上式出

18、現(xiàn)的矛盾說明上式出現(xiàn)的矛盾說明21xx 與（2）因）因0 , xa b，則由定理條件有，則由定理條件有,baxkxxLxxLxxgxgxgxxkkkkkk0111)()()(其中其中 在在之間，之間，xxk與1k因而因而),(bak。10 L，故有，故有 xxkklim因因（3）設(shè)）設(shè) mk，則有，則有11)(mkiiikmxxxx而而01111)()(xxLxxLxgxgxxiiiiiii于是有于是有011011111xxLLLxxLxxxxkmkmkiimkiiikm令令m，由于，由于10 L得到得到*101kkLxxxxL又由又由1111kkkiiiiixxLxxLxx得到得到11111

19、111kkkmmkikkkimkiiikmxxLLLxxLxxxx令令m，由上式得到，由上式得到kkkxxLxx111證畢。證畢。如例如例2 2中中 在區(qū)間1，2上滿足該定理條件3( )1g xx01.5x 311kkxx所以，對 ，迭代法 收斂。 從誤差估計式（2）知， 越小，收斂速度越快，且可用來估計迭代次數(shù)。 L例2中要求近似根 的誤差不超過kx510由23311( )(1)1334gxx將01311.5,1.35721,0.213 4xxL代入510101kLxxL求得6.28k ，迭代7次即可。( )g x 當(dāng)?shù)瘮?shù)當(dāng)?shù)瘮?shù) 比較復(fù)雜時，利用定理比較復(fù)雜時，利用定理1 1條條件判

20、斷迭代法收斂十分困難。在實際應(yīng)用中，常件判斷迭代法收斂十分困難。在實際應(yīng)用中，常根據(jù)局部收斂定理討論迭代法的收斂性。根據(jù)局部收斂定理討論迭代法的收斂性。，由LxxLkln)1 (ln01定理定理2 2（迭代法的局部收斂性）（迭代法的局部收斂性）若存在區(qū)間（若存在區(qū)間（c c，d d），使），使1 1、方程方程 在（在（c，d）內(nèi)有實根）內(nèi)有實根 ；( )xg x*x()gx2 2、 在（在（c c，d d）內(nèi)連續(xù)，且）內(nèi)連續(xù)，且 。( )1g x 則迭代法則迭代法1() (0,1,2,)kkxg xk在在 附近具有局部收斂性。附近具有局部收斂性。*x證明：（略）例例3 方程方程 有唯一實根有唯

21、一實根xxe*(0,1)x 試分析迭代過程試分析迭代過程 的收斂性。的收斂性。1kxkxe (0,1,2,)k 解：這里解：這里 ，在區(qū)間（，在區(qū)間（0 0，1 1）內(nèi)）內(nèi)( ),( )xxg xeg xe ( )g x連續(xù)，且連續(xù)，且 ，由定理，由定理2 2知，迭代法知，迭代法0( )1xg xee1kxkxe在在 附近具有局部收斂性，迭代過程收斂。附近具有局部收斂性，迭代過程收斂。*x練習(xí)：練習(xí)：已知方程已知方程 ，010423 xx在區(qū)間（在區(qū)間（1，2）內(nèi)有一個實根）內(nèi)有一個實根 ，x1、試用二分法求該根，使誤差限不超過、試用二分法求該根，使誤差限不超過 ， 210并問要使誤差限不超過

22、并問要使誤差限不超過 ，510作幾次對分才能求得滿足要求的近似根？作幾次對分才能求得滿足要求的近似根？2、試改變方程的形式，、試改變方程的形式，給出迭代函數(shù)相應(yīng)的迭代格式，給出迭代函數(shù)相應(yīng)的迭代格式，并取初值為并取初值為 ，5 . 10 x求出精確到小數(shù)點后六位的一個近似根。求出精確到小數(shù)點后六位的一個近似根。 一種迭代法具有實用價值，不但需要肯定它是一種迭代法具有實用價值，不但需要肯定它是收斂的，而且應(yīng)要求它收斂得比較快。迭代的收斂收斂的，而且應(yīng)要求它收斂得比較快。迭代的收斂速度就是指迭代誤差的下降速度。為此，我們引入速度就是指迭代誤差的下降速度。為此，我們引入收斂階的概念。收斂階的概念。3 3 簡單迭代法的收斂速