數(shù)值分析 李慶揚(yáng) 第7章非線性方程與方程組的數(shù)值解法

1、數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日1第第7 7章章 非線性方程與方程組的數(shù)值解法非線性方程與方程組的數(shù)值解法7.1 7.1 方程求根與二分法方程求根與二分法7.1.1 7.1.1 引言引言方程求根的一般形式：方程求根的一般形式： 0 xf其中其中 ， Rx b,aCxf 如果實數(shù)如果實數(shù) 滿足滿足 ， 則稱則稱 是是方程的根方程的根，*x 0* xf*x或稱或稱 是函數(shù)是函數(shù) 的的零點(diǎn)零點(diǎn)。*x xf數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日2若若 可分解為：可分解為： xgxxxfm* xf其中其中 為正整數(shù)，且為正整數(shù)，且m 0* xg則

2、稱則稱 為方程的為方程的 重根重根，或，或 為為 的的 重零點(diǎn)重零點(diǎn)。*xm*x xfm 時為時為單根單根。1 m若若 為為 的的 重零點(diǎn)，且重零點(diǎn)，且 充分光滑，則充分光滑，則*x xfm xg 001* *m*m*xf,xfxfxf數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日3方程性質(zhì)不同，求解方法也有很大差異。方程性質(zhì)不同，求解方法也有很大差異。如果函數(shù)如果函數(shù) 是多項式：是多項式： xf nnnnaxaxaxaxf 1110其中其中 ， 為實數(shù)，則稱方程為為實數(shù)，則稱方程為 次代數(shù)方程次代數(shù)方程。00 aian 次代數(shù)方程在復(fù)數(shù)域有且只有次代數(shù)方程在復(fù)數(shù)域有且只有

3、個根（含重根）。個根（含重根）。nn當(dāng)當(dāng) 時不能用公式表示方程的根，只能數(shù)值求解。時不能用公式表示方程的根，只能數(shù)值求解。5 n數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日4有根區(qū)間有根區(qū)間：設(shè)函數(shù)設(shè)函數(shù) 在在 上連續(xù)，上連續(xù)， xf b,a 0 bfaf則方程則方程 在區(qū)間在區(qū)間 內(nèi)一定有實根，內(nèi)一定有實根， 0 xf b,a稱稱 為方程為方程 的有根區(qū)間。的有根區(qū)間。 b,a 0 xf xfx2x1xab對于對于超越方程超越方程，例如：，例如：010sin10 xex在整個在整個 軸上有無窮多個解，軸上有無窮多個解， 取值范圍不同，解也不同。取值范圍不同，解也不同。xx

4、超遠(yuǎn)方程只能通過數(shù)值求解。超遠(yuǎn)方程只能通過數(shù)值求解。數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日5逐次搜索法逐次搜索法：設(shè)連續(xù)函數(shù)設(shè)連續(xù)函數(shù) 存在有根區(qū)間存在有根區(qū)間 xf b,a 將將 等分，步長等分，步長 ； b,aNabh 端點(diǎn)端點(diǎn) ；khaxk N,k10 檢查節(jié)點(diǎn)函數(shù)值檢查節(jié)點(diǎn)函數(shù)值 ? kxf 若若 ，則可確定有根區(qū)間，則可確定有根區(qū)間 。 01 kkxfxf kkx,x1 a1 kxkxxN數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日6P213 例例1 求方程求方程 的有根區(qū)間。的有根區(qū)間。 0774183811123 .x.x.xxf解解

5、： ， 07410 .f 04376 .f 在區(qū)間在區(qū)間 內(nèi)至少有一個實根。內(nèi)至少有一個實根。 xf 60,取步長取步長 ，進(jìn)行搜索計算：，進(jìn)行搜索計算：1 h方程的有根區(qū)間為方程的有根區(qū)間為 ， ， 21, 43, 65, xfx6543210數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日77.1.2 7.1.2 二分法二分法計算方法：計算方法： af ? bf 計算區(qū)間中點(diǎn)函數(shù)值計算區(qū)間中點(diǎn)函數(shù)值 ?2 baf 若若 ，則根為，則根為 ， 02 baf2bax* 計算區(qū)間端點(diǎn)函數(shù)值計算區(qū)間端點(diǎn)函數(shù)值 、 否則：否則： 時時 ， ； 02 afbafbba 2 時時 ， ；

6、 02 bfbafaba 2數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日8 反復(fù)計算，直到反復(fù)計算，直到 ， ab（ 預(yù)定的精度）預(yù)定的精度） 最終取值：最終取值： 。 2bax* 誤差：取有根區(qū)間誤差：取有根區(qū)間 的中點(diǎn)的中點(diǎn) （ 二分次數(shù)）二分次數(shù)） kkb,ak作為近似根，則：作為近似根，則：2kkkbax 122 kkkk*ababxx特點(diǎn)：算法簡單，可保證收斂，但收斂太慢。用于求近似解。特點(diǎn)：算法簡單，可保證收斂，但收斂太慢。用于求近似解。數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日9P214例例2 求方程求方程 在區(qū)間在區(qū)間 內(nèi)的一個實根，內(nèi)

7、的一個實根，要求準(zhǔn)確到小數(shù)點(diǎn)后的第二位。要求準(zhǔn)確到小數(shù)點(diǎn)后的第二位。 013 xxxf 5101.,.解解：注：注： ，即，即12 kk*abxx0040250166.xx* 0101 .f， 0875051 .f數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日107.2 7.2 不動點(diǎn)迭代法及其收斂性不動點(diǎn)迭代法及其收斂性7.2.1 7.2.1 不動點(diǎn)與不動點(diǎn)迭代法不動點(diǎn)與不動點(diǎn)迭代法將方程將方程 改寫成等價形式：改寫成等價形式： 0 xf xx 若要求若要求 滿足滿足 ，則，則 ；反之亦然。；反之亦然。*x 0 *xf *xx 稱稱 為函數(shù)為函數(shù) 的一個的一個不動點(diǎn)不動點(diǎn)。

8、*x x 因此，求因此，求 的零點(diǎn)就等價于求的零點(diǎn)就等價于求 的不動點(diǎn)。的不動點(diǎn)。 xf x 數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日11 選擇一個初始近似值選擇一個初始近似值 ，代入，代入迭代函數(shù)迭代函數(shù) ：0 x 01xx 將新值將新值 作為近似值，再次代入迭代函數(shù)：作為近似值，再次代入迭代函數(shù)：1x 12xx 反復(fù)迭代，反復(fù)迭代，迭代方程迭代方程： kkxx 1,k10 ， 迭代存在極限：迭代存在極限：*kkxx lim不動點(diǎn)迭代法不動點(diǎn)迭代法： x 則稱迭代方程則稱迭代方程收斂收斂，且，且 為為 的不動點(diǎn)。的不動點(diǎn)。 *xx x 數(shù)值分析數(shù)值分析 黃龍主講黃龍主

9、講 2021年年10月月13日日12實質(zhì)：將隱式方程實質(zhì)：將隱式方程 ，通過迭代逐步顯式化，通過迭代逐步顯式化逐次逼近法逐次逼近法。 xx 幾何意義：幾何意義：直線直線 與曲線與曲線xy xy 其交點(diǎn)橫坐標(biāo)就是方程的根。其交點(diǎn)橫坐標(biāo)就是方程的根。逐次逼近：逐次逼近：0 x 00 xy 10 xy 1x 11xy 21xy kkxx 1*x（迭代收斂）（迭代收斂）數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日13P215例例3 求方程求方程 在在 附近的根附近的根 。 013 xxxf510.x *x解解：迭代公式：迭代公式311 kkxx，,k10 注意：如果迭代公式為注意：

10、如果迭代公式為 ，則，則迭代發(fā)散迭代發(fā)散。131 kkxx數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日147.2.2 7.2.2 不動點(diǎn)的存在性與迭代法的收斂性不動點(diǎn)的存在性與迭代法的收斂性定理定理1 1 設(shè)函數(shù)設(shè)函數(shù) 滿足以下兩個條件：滿足以下兩個條件：（1 1） 對于任意對于任意 ，有，有 b,aCx b,ax bxa （2 2） 存在正常數(shù)存在正常數(shù) ，使對任意，使對任意 都有都有 b,ay,x 1 L yxLyx （迭代函數(shù)在（迭代函數(shù)在 上）上） b,a（迭代函數(shù)的增量小于自變量的增量）（迭代函數(shù)的增量小于自變量的增量）則則 在在 上存在唯一的不動點(diǎn)上存在唯一的不

11、動點(diǎn) 。 x b,a*x數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日15證明證明：先證不動點(diǎn)存在性。：先證不動點(diǎn)存在性。若若 ，或，或 ： aa bb 則則 在在 上存在不動點(diǎn)。（不動點(diǎn)特點(diǎn)上存在不動點(diǎn)。（不動點(diǎn)特點(diǎn) ） x b,a *xx 因因 ，以下設(shè)，以下設(shè) 及及 ，定義：，定義： bxa aa bb xxxf 顯然顯然 ，且滿足，且滿足 b,aCxf 0 aaaf ， 0 bbbf 由連續(xù)函數(shù)性質(zhì)可知：存在由連續(xù)函數(shù)性質(zhì)可知：存在 使使 b,ax* 0 *xf即即 ， 為為 的不動點(diǎn)。的不動點(diǎn)。 *xx *x x 數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10

12、月月13日日16再證唯一性。再證唯一性。設(shè)設(shè) 及及 都是都是 的不動點(diǎn)，則：的不動點(diǎn)，則：*x1 x b,ax* 2 *xxxxLxxxx21212121 引出矛盾。故引出矛盾。故 的不動點(diǎn)只能是唯一的。的不動點(diǎn)只能是唯一的。 x 在在 的不動點(diǎn)唯一的情況下，可得到迭代法收斂的充分條件。的不動點(diǎn)唯一的情況下，可得到迭代法收斂的充分條件。 x 數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 收斂到收斂到 的不動點(diǎn)的不動點(diǎn) ，并有誤差估計，并有誤差估計2021年年10月月13日日17定理定理2 2 設(shè)函數(shù)設(shè)函數(shù) 滿足以下兩個條件：滿足以下兩個條件：（1 1） 對于任意對于任意 ，有，有 b,aCx b,ax

13、bxa （2 2） 存在正常數(shù)存在正常數(shù) ，使對任意，使對任意 都有都有 b,ay,x 1 L yxLyx 則對任意則對任意 ： b,ax 0 x *x由由 得到的迭代序列得到的迭代序列 kkxx 1 kx011xxLLxxk*k 數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日18證明證明：設(shè)：設(shè) 是是 在在 上的唯一不動點(diǎn)。上的唯一不動點(diǎn)。 b,ax* x b,a由定理條件（由定理條件（1 1）可知：）可知： b,axk *k*k*kxxLxxxx 11 由定理條件（由定理條件（2 2）可得：）可得：反復(fù)應(yīng)用上述結(jié)論：反復(fù)應(yīng)用上述結(jié)論：*k*k*k*kxxLxxLxxLxx

14、 0221因因 ：故當(dāng)：故當(dāng) 時時10 L k00 *kkxx,L，序列，序列 收斂到收斂到 。 kx*x數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日19再由定理條件（再由定理條件（2 2）得：）得： 111 kkkkkkxxLxxxx 如此反復(fù)遞推得：如此反復(fù)遞推得：011xxLxxkkk 于是對于任意正整數(shù)于是對于任意正整數(shù) 有：有：pkkpkpkpkpkkpkxxxxxxxx 1211 0101211xxLLxxLLLkkpkpk 在上式令在上式令 ，注意到，注意到 ： p*pkpxx lim011xxLLxxk*k 數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年1

15、0月月13日日20討論一討論一：因正常數(shù)：因正常數(shù) 未知，上述誤差估計無法使用。未知，上述誤差估計無法使用。L對于任意正整數(shù)對于任意正整數(shù) 有：有：pkkpkpkpkpkkpkxxxxxxxx 1211 kkkkppxxLxxLL 1121111令令 可得：可得： pkkkxxLxx 1*11即：只要相鄰兩次計算結(jié)果的偏差即：只要相鄰兩次計算結(jié)果的偏差 足夠小，足夠小， 就能保證近似值就能保證近似值 具有足夠的精度。具有足夠的精度。kkxx 1kx數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日21討論二討論二：在某些情形下可求得：在某些情形下可求得 。L如果如果 且對任意且對

16、任意 有有 b,aCx1 b,ax 1 Lx 則，由中值定理可得：對則，由中值定理可得：對 有有 b,ay,x b,a,yxLyxyx 因此，可將上述因此，可將上述定理定理 和和定理定理 中的條件（中的條件（2 2）改為：）改為：12 1 Lx 數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日22P215例例3 求方程求方程 在在 附近的根附近的根 。 013 xxxf510.x *x例如：例如：（1 1）當(dāng)）當(dāng) 時，在區(qū)間時，在區(qū)間 有：有： 31 xx 12311313232 xx 21, 232133 x 由定理由定理2 2可得：迭代法是收斂的?？傻茫旱ㄊ鞘諗康?。（2

17、 2）當(dāng)）當(dāng) 時，在區(qū)間時，在區(qū)間 有：有： 13 xx 21, 132 xx 不滿足定理的條件，無法保證迭代收斂。不滿足定理的條件，無法保證迭代收斂。數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日237.2.3 7.2.3 局部收斂性與收斂階局部收斂性與收斂階對于區(qū)間對于區(qū)間 上的任意上的任意 ，所產(chǎn)生的迭代序列，所產(chǎn)生的迭代序列 都收斂，都收斂，稱為稱為全局收斂全局收斂。 b,a0 x kx實際應(yīng)用時，通常只在不動點(diǎn)實際應(yīng)用時，通常只在不動點(diǎn) 鄰居考察其收斂性，鄰居考察其收斂性，稱為稱為局部收斂局部收斂。*x定義定義1 1 設(shè)設(shè) 有不動點(diǎn)有不動點(diǎn) ，如果存在，如果存在 的

18、某個領(lǐng)域的某個領(lǐng)域 ： x *x*xR *xx對任意對任意 ，迭代產(chǎn)生序列，迭代產(chǎn)生序列 ，且收斂到，且收斂到 ，Rx 0 Rxk *x則稱迭代法則稱迭代法局部收斂局部收斂。數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 且且 ，則迭代法，則迭代法 局部收斂。局部收斂。定理定理3 3 設(shè)設(shè) 為為 的不動點(diǎn)，的不動點(diǎn)， 在在 的某個領(lǐng)域連續(xù)，的某個領(lǐng)域連續(xù)，2021年年10月月13日日24 x *x*x x 1* x kkxx 1證明證明：由連續(xù)函數(shù)的性質(zhì)，存在：由連續(xù)函數(shù)的性質(zhì)，存在 的某個領(lǐng)域的某個領(lǐng)域 ：*xR *xx使對于任意使對于任意 有下式成立：有下式成立：Rx 1 Lx 此外，對于任意此外，對

19、于任意 ，總有，總有 ，這是因為：，這是因為：Rx Rx *xxxxxx *xxxxL依據(jù)定理依據(jù)定理2 2 ：迭代過程對于任意：迭代過程對于任意 均收斂。均收斂。Rx 0數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日25P218題題4 用不同方法求方程用不同方法求方程 的根的根 。03-2 x3 *x解：這里解：這里 ，可改寫成不同的等價形式可改寫成不同的等價形式 ，其不動點(diǎn)為，其不動點(diǎn)為 32 xxf xx 3 *x（1 1）321 kkkxxx， 32 xxx 12 xx ， 11323 *x（2 2）kkxx31 ， xx3 23xx ， 13 *x數(shù)值分析數(shù)值分析

20、黃龍主講黃龍主講 2021年年10月月13日日26（3 3） 34121 kkkxxx， 3412 xxx xx211 ， 11340231 .x* （4 4） kkkxxx3211， xxx321 23121xx ， 03 *x取取 ，對上述，對上述4 4種迭代法，計算三步的結(jié)果如下表。種迭代法，計算三步的結(jié)果如下表。20 x數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日27 7320511732361151873732143173475129275175151312222043213210.x.x.xxxkk迭迭代代法法迭迭代代法法迭迭代代法法迭迭代代法法說明：說明： 精

21、確值精確值 ，732050813. 迭代法（迭代法（1 1）和（）和（2 2）不收斂，迭代法（）不收斂，迭代法（3 3）和（）和（4 4）收斂；）收斂； 迭代法（迭代法（4 4）中）中 比迭代法（比迭代法（3 3）小，）小，迭代法（迭代法（4 4）比迭代法（）比迭代法（3 3）收斂速度快。）收斂速度快。 0 *x 數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日28定義定義2 2 設(shè)迭代過程設(shè)迭代過程 收斂于方程收斂于方程 的根的根 ， kkxx 1 xx *x如果當(dāng)如果當(dāng) 時迭代誤差時迭代誤差 滿足漸進(jìn)關(guān)系式滿足漸進(jìn)關(guān)系式 k*kkxxe Ceepkk 1，常數(shù)，常數(shù)0 C則

22、稱該迭代過程是則稱該迭代過程是 階收斂階收斂的。的。特別地，特別地， 時稱為時稱為線性收斂線性收斂， 時為時為超線性收斂超線性收斂， 時為時為平方收斂平方收斂。p 11 Cp1 p2 p數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日29定理定理4 4 對于對于迭代過程迭代過程 及正整數(shù)及正整數(shù) ， kkxx 1p如果如果 在所求根在所求根 的鄰近連續(xù)，且的鄰近連續(xù)，且 xp *x 01 *p*xxx 0 *px 則該迭代過程在點(diǎn)則該迭代過程在點(diǎn) 鄰近是鄰近是 階收斂的。階收斂的。*xp證明：由于證明：由于 ，根據(jù)定理，根據(jù)定理3 3可得：可得： 0 *x 迭代過程迭代過程 具

23、有局部收斂性。具有局部收斂性。 kkxx 1數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 再將再將 在根在根 處泰勒展開，利用定理條件：處泰勒展開，利用定理條件：2021年年10月月13日日30 kx *x p*kp*kxxpxx ! ， 在在 與與 之間之間 kx*x注意到注意到 ， ： 1 kkxx *xx p*kp*kxxpxx !1 因此對迭代誤差，當(dāng)因此對迭代誤差，當(dāng) 時有：時有： k !1pxee*ppkk 這表明迭代過程這表明迭代過程 確實為確實為 階收斂。階收斂。 kkxx 1p數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 迭代過程的收斂速度依賴于迭代函數(shù)迭代過程的收斂速度依賴于迭代函數(shù) 的選取。

24、的選取。2021年年10月月13日日31說明說明 定理表明：定理表明： x 如果如果 時時 ：則該迭代過程只可能是線性收斂的。則該迭代過程只可能是線性收斂的。 b,ax 0 x 在例在例4 4中：中：迭代法（迭代法（3 3）的）的 ，故它只能是線性收斂；，故它只能是線性收斂； 0* x 迭代法（迭代法（4 4）的）的 ， ，迭代為二階收斂。，迭代為二階收斂。 0* x 0* x 數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日327.3 7.3 迭代收斂的加速方法迭代收斂的加速方法7.3.1 7.3.1 埃特金加速收斂方法埃特金加速收斂方法設(shè)設(shè) 是根是根 的某個近似值，用迭代公

25、式迭代一次：的某個近似值，用迭代公式迭代一次：0 x*x 01xx 由微分中值定理：由微分中值定理： *xxxxxx 001 （ 在在 與與 之間之間 ） 0 x*x假定假定 變化不大：變化不大： x Lx *xxLxx 01，數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日33將校正值將校正值 再迭代一次：再迭代一次： 01xx 12xx 因而有：因而有： *xxLxx 01 *xxLxx 12消去消去 ：L*xxxxxxxx 1021可推得：可推得： 0122010012212022xxxxxxxxxxxxx* 注意：注意： 上式是對兩次迭代值加權(quán)平均后的結(jié)果，可加速迭代；

26、上式是對兩次迭代值加權(quán)平均后的結(jié)果，可加速迭代； 適用任何求根序列適用任何求根序列 ，不只局限于不動點(diǎn)迭代序列。，不只局限于不動點(diǎn)迭代序列。 kx數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 已知求根序列已知求根序列 ，其三個相鄰值為，其三個相鄰值為2021年年10月月13日日34埃特金加速法埃特金加速法（ 加速法加速法）：）：kx1 kx2 kx加速計算，得到新值加速計算，得到新值 ,k,xxxxxxxxxxkkkkkkkkkk1022212211 kx，kkkxxx 1點(diǎn)點(diǎn) 的一階差分；的一階差分；kx kkkkkxxxxx 1122點(diǎn)點(diǎn) 的二階差分；的二階差分；kx2 可以證明：新序列可以證明：新

27、序列 的收斂速度比的收斂速度比 的收斂速度快的收斂速度快 kx kx0lim1 *k*kkxxxx數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日357.3.2 7.3.2 斯特芬森迭代法斯特芬森迭代法把埃特金加速法與不動點(diǎn)迭代結(jié)合，就可得到把埃特金加速法與不動點(diǎn)迭代結(jié)合，就可得到斯特芬森迭代法斯特芬森迭代法： kkkkyz,xy ,kxyzxyxxkkkkkkk10221 ，斯特芬森迭代法是將兩步迭代合成一步得到的：斯特芬森迭代法是將兩步迭代合成一步得到的： ,k,xxkk101 xxxxxxx 22數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日36斯特芬森

28、迭代法思路：斯特芬森迭代法思路：為求解為求解 的根的根 ，令，令 ： xx *x xxx 0 *xxx 已知已知 的近似值的近似值 及及 ，其誤差分別為：，其誤差分別為：*xkxky kkkkkxyxxx kkkkkyzyyy 把誤差把誤差 “ “外推到零外推到零”：即過即過 及及 兩點(diǎn)做線性插值函數(shù)，兩點(diǎn)做線性插值函數(shù)， kkx,x kky,y 它與它與 軸交點(diǎn)就是軸交點(diǎn)就是 。 x x1 kx數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日37即求解方程：即求解方程： 0 kkkkkkxxxyxyx 其解為：其解為： kkkkkkkkkkkkxyzxyxxyxyxxx 22

29、 即：即： kkkkkkkxyzxyxx 221數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日38定理定理5 5 對于斯特芬森迭代法對于斯特芬森迭代法 ,k,xxkk101 xxxxxxx 22若若 為迭代函數(shù)為迭代函數(shù) 的不動點(diǎn)，則的不動點(diǎn)，則 也為也為 的不動點(diǎn)。的不動點(diǎn)。*x x *x x 反之，若反之，若 為為 的不動點(diǎn)，設(shè)的不動點(diǎn)，設(shè) 存在，存在，*x x x 1 *x 則則 也是也是 的不動點(diǎn)，且斯特芬森迭代法是二階收斂的。的不動點(diǎn)，且斯特芬森迭代法是二階收斂的。*x x 數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日39P221例例5 5 用斯

30、特芬森法求解方程用斯特芬森法求解方程 。 013 xxxf解解：用迭代公式：用迭代公式 求解方程是發(fā)散的。求解方程是發(fā)散的。131 kkxx改進(jìn)上述迭代公式，斯特芬森迭代法：改進(jìn)上述迭代公式，斯特芬森迭代法：13 kkxy13 kkyz， kkkkkkkxyzxyxx 22132472153271413251813248014444351347101328951331728249140135565122388858409214162911396512375002510.zyxkkkk數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 因因 ， ，2021年年10月月13日日40P222例例6 6 求方程求方程

31、 在在 中的解中的解 。033 xex 43,解解：由方程得：由方程得 ，并取對數(shù)，并取對數(shù)23xex xxxx 3lnln23ln2可構(gòu)造迭代法可構(gòu)造迭代法 xx2 132max43 xx 且且 時，時， ，由定理，由定理2 2此迭代法是收斂的。此迭代法是收斂的。3lnln21 kkxx 43,x 43,x 若取若取 迭代迭代1616次得次得 ，有六位有效數(shù)字。，有六位有效數(shù)字。530.x 73307316.x 73308327345937359037383531662783604143530.zyxkkkk若用斯特芬森若用斯特芬森迭代法加速：迭代法加速：數(shù)值分析數(shù)值分析 黃龍主講黃龍主講

32、2021年年10月月13日日417.4 7.4 牛頓法牛頓法7.4.1 7.4.1 牛頓法及其收斂性牛頓法及其收斂性牛頓法基本思想：將非線性方程轉(zhuǎn)化線性方程求解。牛頓法基本思想：將非線性方程轉(zhuǎn)化線性方程求解。設(shè)已知方程設(shè)已知方程 有近似根有近似根 ， 0 xfkx 0 kxf將函數(shù)將函數(shù) 在點(diǎn)在點(diǎn) 展開展開 xfkx kkkxxxfxfxf 于是方程于是方程 可近似表示為可近似表示為 0 xf 0 kkkxxxfxf這是個線性方程，其根為這是個線性方程，其根為 （牛頓法牛頓法）1 kx ,k,xfxfxxkkkk101 數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日42牛頓法

33、的幾何解釋牛頓法的幾何解釋：方程方程 的根的根 為為 0 xf*x曲線曲線 與與 軸交點(diǎn)的橫坐標(biāo)。軸交點(diǎn)的橫坐標(biāo)。 xfy x設(shè)設(shè) 是根是根 的某個近似值，的某個近似值，kx*x過曲線過曲線 上點(diǎn)上點(diǎn) 引切線，引切線， xfy kky,x切線與切線與 軸交點(diǎn)的橫坐標(biāo)軸交點(diǎn)的橫坐標(biāo) 作為新解作為新解x1 kx切線方程：（切線方程：（ 點(diǎn)斜式方程）點(diǎn)斜式方程） kkkxxxfxfy 其根為牛頓法的近似解其根為牛頓法的近似解切線法切線法。數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日43討論：牛頓法的收斂性。討論：牛頓法的收斂性。 xfxfxx ， 2xfxfxfx 42xfxfx

34、fxfx 假定假定 是是 的一個單根：的一個單根：*x xf 0 *xf， 0 *xf代入上式，可得：代入上式，可得： 0 *x ， 0 *x 因此：牛頓法在根因此：牛頓法在根 鄰近是平方收斂的。鄰近是平方收斂的。*x數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日44P223例例7 用牛頓法解方程用牛頓法解方程 。01 xxe解解：牛頓公式為：牛頓公式為 1 xxexf xexxf 1 kkkkxfxfxx 1kxkkxexxk 1取迭代初值取迭代初值500.x 567140356716025710201500.xkk數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月1

35、3日日45牛頓法計算步驟牛頓法計算步驟：第一步第一步 準(zhǔn)備準(zhǔn)備：選定初值：選定初值 ，0 x計算計算 ， 00 xff 00 xff 第二步第二步 迭代迭代：迭代一次：迭代一次 ，0001ffxx 計算計算 ， 11xff 11xff 第三步第三步 控制控制：計算迭代誤差：計算迭代誤差 ，（，（ 控制常數(shù)控制常數(shù)） 01xx ，當(dāng)，當(dāng) 時時Cx 1101xxx ，當(dāng)，當(dāng) 時時Cx 11 C數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日46否則以否則以 代替代替 ，或者或者 ，則方法失??；，則方法失?。坏谒牟降谒牟?修改修改：如果迭代次數(shù)達(dá)到預(yù)先指定的次數(shù)：如果迭代次數(shù)達(dá)到預(yù)先

36、指定的次數(shù) ， 111f,f,x 如果如果 滿足：滿足：N01 f1x1 或或 （ 、 允許誤差）允許誤差）21 f1 2 則迭代收斂，以則迭代收斂，以 作為所求的根，否則轉(zhuǎn)第四步。作為所求的根，否則轉(zhuǎn)第四步。1x 000f,f,x 轉(zhuǎn)第二步繼續(xù)迭代。轉(zhuǎn)第二步繼續(xù)迭代。數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日477.4.2 7.4.2 牛頓牛頓法應(yīng)用舉例法應(yīng)用舉例對于給定正數(shù)對于給定正數(shù) ，開方計算，開方計算 C? C轉(zhuǎn)變?yōu)閼?yīng)用牛頓法解方程轉(zhuǎn)變?yōu)閼?yīng)用牛頓法解方程 。 02 Cx Cxxf 2， xxf2 kkkkxfxfxx 1 kkkxCxx211可以證明：對于任意初

37、值可以證明：對于任意初值 迭代都收斂。迭代都收斂。 00 x數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日48證明證明：由迭代公式：由迭代公式： 212121CxxCxCxCxkkkkk 212121CxxCxCxCxkkkkk 兩式相除：兩式相除： 2211211CxCxCxCxCxCxkkkkkk反復(fù)遞推：反復(fù)遞推：kCxCxCxCxkk200 數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日49假設(shè)：假設(shè)：CxCxq 00解出：解出：Cqqxkkk2211 因此：因此：kkqqCCxk2212 對于任意對于任意 ，總有，總有 ，00 x1 q當(dāng)當(dāng) 時，時

38、， ，即迭代過程恒收斂。，即迭代過程恒收斂。 kCxk數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 迭代函數(shù)為迭代函數(shù)為 ，要求，要求2021年年10月月13日日507.4.3 7.4.3 簡化牛頓法與牛頓簡化牛頓法與牛頓下山法下山法牛頓法缺點(diǎn)：牛頓法缺點(diǎn)： 每次迭代都要計算每次迭代都要計算 及及 ，有時計算，有時計算 困難。困難。 kxf kxf kxf 初始值初始值 在根在根 附近才能保證收斂，取值不合適可能不收斂。附近才能保證收斂，取值不合適可能不收斂。0 x*x（1 1）簡化牛頓法簡化牛頓法（平行弦法平行弦法）迭代公式為迭代公式為 ,k,xCfxxkkk101 xCfxx 0 C其中常量其中常量

39、 ，并保證迭代收斂，并保證迭代收斂 11 xfCx ，即，即 20 xfC若上式在根若上式在根 附近成立，則該迭代法局部收斂。附近成立，則該迭代法局部收斂。*x數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 0 x1x2021年年10月月13日日51若若 取為取為 處之值處之值 ，則有，則有簡化牛頓法簡化牛頓法C0 x 01xfC ,k,xfxfxxkkk1001 特點(diǎn)：節(jié)省了計算量，但只有線性收斂。特點(diǎn)：節(jié)省了計算量，但只有線性收斂。幾何意義：幾何意義：用斜率為用斜率為 的平行弦的平行弦與與 軸的交點(diǎn)作為軸的交點(diǎn)作為 的近似。的近似。 0 xf x*x數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10

40、月月13日日52（2 2）牛頓下山法牛頓下山法問題：牛頓法的收斂性依賴于初值問題：牛頓法的收斂性依賴于初值 。0 x例如：用牛頓法求解方程例如：用牛頓法求解方程 013 xx公式：公式： 131231 kkkkkkkkxxxxxfxfxx如果：取迭代初值如果：取迭代初值510.x 3478311.x 3252012.x *x.x 3247213，如果：取迭代初值如果：取迭代初值600.x 9171.x 2x，結(jié)果偏離了根，結(jié)果偏離了根324721.x* 數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日53為防止迭代發(fā)散，要求迭代過程具有單調(diào)性為防止迭代發(fā)散，要求迭代過程具有單調(diào)

41、性 kkxfxf 1下山法下山法牛頓下山法牛頓下山法：下山法保證函數(shù)值穩(wěn)定下降，牛頓法加速收斂：下山法保證函數(shù)值穩(wěn)定下降，牛頓法加速收斂先用牛頓法初步迭代先用牛頓法初步迭代 kkkkxfxfxx 1在將近似值在將近似值 與與 加權(quán)平均加權(quán)平均kx1 kx kkkkkkxfxfxxxx 111其中其中下山因子下山因子 ：10 數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日54下山因子選擇下山因子選擇：從：從 開始，逐次減半試算，開始，逐次減半試算，1 直到滿足下山法要求直到滿足下山法要求 kkxfxf 1例如：求解方程例如：求解方程 ，牛頓下山法公式為，牛頓下山法公式為 013

42、 xxxf當(dāng)當(dāng) ， 時，求得時，求得 ，且，且131231 kkkkkxxxxx 600.x 1 9171.x 01xfxf 結(jié)果不滿足下山法要求，無法繼續(xù)迭代，需改進(jìn)結(jié)果不滿足下山法要求，無法繼續(xù)迭代，需改進(jìn) 值。值。 數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日55逐次對逐次對 減半試算：當(dāng)減半試算：當(dāng) 時，求得時，求得 321 1406511.x 01xfxf 以以 為初值，取為初值，取 ，迭代收斂，迭代收斂1406511.x 1 1866036181122.xf,.x 00667032628133.xf,.x 00000860324721144.xf,.x 注意：下

43、山因子減半試算，只為確定使迭代收斂的初值注意：下山因子減半試算，只為確定使迭代收斂的初值 。0 x數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日567.4.4 7.4.4 重根情形重根情形設(shè)設(shè) ，整數(shù)，整數(shù) ， xgxxxfm* 2 m 0 *xg則則 為方程為方程 的的 重根，此時有：重根，此時有：*x 0 xfm 001 *m*m*xf,xfxfxf方法方法1 1：只要：只要 仍可用牛頓法仍可用牛頓法 0 kxf此時迭代函數(shù)為此時迭代函數(shù)為 ，其導(dǎo)數(shù)為，其導(dǎo)數(shù)為 xfxfxx 011 mx* ，且，且 1 *x 所以牛頓法求重根只是線性收斂。所以牛頓法求重根只是線性收斂。

44、數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日57改進(jìn)迭代函數(shù)改進(jìn)迭代函數(shù) xfxfmxx 此時有此時有 0011 *x,mmx 因此，用改進(jìn)的迭代公式求重根具有二階收斂性。因此，用改進(jìn)的迭代公式求重根具有二階收斂性。改進(jìn)的迭代公式為改進(jìn)的迭代公式為 ,k,xfxfmxxkkkk101 缺點(diǎn)：需要知道缺點(diǎn)：需要知道 的重根數(shù)的重根數(shù) 。*xm數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日58方法方法2 2：重新構(gòu)造求重根的迭代法：重新構(gòu)造求重根的迭代法令令 ，若，若 是是 的的 重根重根 xfxfx *x 0 xfm xgxxxmgxgxxx* 故故 是是

45、的單根。的單根。*x 0 x 由此應(yīng)用牛頓法，迭代函數(shù)為由此應(yīng)用牛頓法，迭代函數(shù)為 xfxfxfxfxfxxxxx 2 從而可構(gòu)造二階收斂的迭代法從而可構(gòu)造二階收斂的迭代法 ,k,xfxfxfxfxfxxkkkkkkk1021 特點(diǎn)：無需知道特點(diǎn)：無需知道 值，但要計算值，但要計算 。m xf 數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日59P227例例9 方程方程 的根的根 是二重根是二重根 。 用上述三種方法求根。用上述三種方法求根。04424 xx解解：三種方法的迭代公式為：三種方法的迭代公式為2 *x（1 1）牛頓法）牛頓法 kkkkkkkxxxxfxfxx4221

46、 （2 2）改進(jìn)法）改進(jìn)法 kkkkkkkxxxxfxfmxx2221 （3 3）重構(gòu)法）重構(gòu)法 22221 kkkkkkkkxxxxxxxx 數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日60取初值取初值 ，計算結(jié)果如下，計算結(jié)果如下: :510.x 414213562141421356214254976191341421143814142156861436607143124117647061416666667145833333311321321.x.x.xxkk）方方法法（）方方法法（）方方法法（注意：方法（注意：方法（2 2）和（）和（3)3)均達(dá)到均達(dá)到1010位有效

47、數(shù)字，位有效數(shù)字，而牛頓法達(dá)到同樣精度需迭代而牛頓法達(dá)到同樣精度需迭代3030次。次。數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日617.5 7.5 弦截法與拋物線法弦截法與拋物線法7.5.1 7.5.1 弦截法弦截法牛頓法問題：每步需計算牛頓法問題：每步需計算 ，當(dāng)函數(shù)復(fù)雜時較困難。，當(dāng)函數(shù)復(fù)雜時較困難。設(shè)設(shè) 、 是是 的近似根的近似根 kxf kx 0 xf1 kx由由 、 構(gòu)造一次插值多項式構(gòu)造一次插值多項式 kxf 1 kxf xp1 kkkkkkxxxxxfxfxfxp 111用用 的根作為的根作為 的新的近似根的新的近似根 01 xp 0 xf1 kx 111 kkkkkkkxxxfxfxfxx數(shù)值分析數(shù)值分析 黃龍主講黃龍主講 2021年年10月月13日日62代入牛頓公式，即得弦截法結(jié)果：代入牛頓公式，即得弦截法結(jié)果： 111 kkkkkkkkkkxxxfxfxfxxfxfxx用差商取代導(dǎo)數(shù)：用差商取代導(dǎo)數(shù)： 11 kkkkkxxxfxfxf弦截法幾何意義：弦截法幾何意義：過曲線過曲線 上橫坐標(biāo)為上橫坐標(biāo)為 的兩點(diǎn)的兩點(diǎn) xfy 作弦線作弦線 ，其方程為，其方程為1 kkx,