數(shù)值計(jì)算方法(第2章)

1、 第2章 非線性方程與方程組的數(shù)值解法 本章重點(diǎn)介紹求解非線性方程 的幾種常見(jiàn)和有效的數(shù)值方法,同時(shí)也對(duì)非線性方程組 求解,簡(jiǎn)單介紹一些最基本的解法.無(wú)論在理論上,還是在實(shí)際應(yīng)用中,這些數(shù)值解法都是對(duì)經(jīng)典的解析方法的突破性開(kāi)拓和補(bǔ)充,許多問(wèn)題的求解,在解析方法無(wú)能為力時(shí),數(shù)值方法則可以借助于計(jì)算機(jī)出色完成.2.1二分法求非線性方程 確定方程的有根區(qū)間 計(jì)算根的近似值的根的方法分為兩步：首先確定有限區(qū)間：依據(jù)零點(diǎn)定理。 設(shè) ，且 ，則方程 在區(qū)間 上至少有一個(gè)根。如果 在 上恒正或恒負(fù)，則此根唯一。等步長(zhǎng)掃描法求有根區(qū)間 用計(jì)算機(jī)求有根區(qū)間：等步長(zhǎng)掃描法。 設(shè)h0是給定的步長(zhǎng)，取 ，若 則掃描成

2、功；否則令 ，繼續(xù)上述方法，直到成功。如果 則掃描失敗。再將h 縮小，繼續(xù)以上步驟。等步長(zhǎng)掃描算法 算法：（求方程 的有根區(qū)間）(1) 輸入 ；(2) ； (3) ，若 輸出失敗信息，停機(jī)。(4)若 。輸出 ，已算出方程的一個(gè)根，停機(jī)。等步長(zhǎng)掃描算法(5) 若 。輸出 為有根區(qū)間，停機(jī)(6) ，轉(zhuǎn) 3）注：如果對(duì)足夠小的步長(zhǎng)h掃描失敗。說(shuō)明：在 內(nèi)無(wú)根在 內(nèi)有偶重根二分法 用二分法(將區(qū)間對(duì)平分)求解。 令 若 ，則 為有根區(qū)間，否則 為有根區(qū)間 記新的有根區(qū)間為 ， 則 且 二分法對(duì) 重復(fù)上述做法得且 二分法 設(shè) 所求的根為 ， 則 即 取 為 的近似解 求方程f(x)=0的根的二分法算法求

3、方程f(x)=0的全部實(shí)根的二分法算法求方程f(x)=0的全部實(shí)根的二分法算法例題例1 設(shè)方程 解：取h=0.1,掃描得： 又 即 在 有唯一根。 2.2一般迭代法2.2.1 迭代法及收斂性 對(duì)于 有時(shí)可以寫成 形式 如： 迭代法及收斂性 考察方程 。這種方程是隱式方程，因而不能直接求出它的根，但如果給出根的某個(gè)猜測(cè)值 ， 代入 中的右端得到 ，再以 為一個(gè)猜測(cè)值，代入 的右端得 反復(fù)迭代得迭代法及收斂性 若 收斂，即 則得 是 的一個(gè)根迭代法的幾何意義 交點(diǎn)的橫坐標(biāo) y=x簡(jiǎn)單迭代法 將 變?yōu)榱硪环N等價(jià)形式 。選取 的某一近似值 ，則按遞推關(guān)系 產(chǎn)生的迭代序列 。這種方法算為簡(jiǎn)單迭代法。例題

4、 例2.2.1 試用迭代法求方程 在區(qū)間(1，2)內(nèi)的實(shí)根。 解：由 建立迭代關(guān)系 k=10,1,2,3.計(jì)算結(jié)果如下:例題精確到小數(shù)點(diǎn)后五位例題但如果由 建立迭代公式 仍取 ，則有 ， 顯然結(jié)果越來(lái)越大， 是發(fā)散序列迭代法的收斂性定理2.2.1（壓縮映像原理）設(shè)迭代函數(shù) 在閉區(qū)間 上滿足（1）（2） 滿足Lipschitz條件即 有且 。壓縮映像原理則 在 上存在 唯一解 ，且對(duì) ，由 產(chǎn)生的序列 收斂于 。 壓縮映像原理證明：不失一般性,不妨設(shè) 否則 為方程的根。首先證明根的存在性 令 壓縮映像原理 則 ， 即 由條件2） 是 上的連續(xù)函數(shù) 是 上的連續(xù)函數(shù)。故由零點(diǎn)定理 在 上至少有一根

5、壓縮映像原理再證根的唯一性 設(shè)有 均為方程的根 則 因?yàn)?0L1 ，所以只可能 ， 即根是唯一的。壓縮映像原理最后證迭代序列的收斂性 與n 無(wú)關(guān)，而0L1時(shí)，稱為超線性收斂；當(dāng)p=2時(shí)，稱為平方收斂或二次收斂。迭代法收斂的階定理2.2.2 設(shè) 是方程 的不動(dòng)點(diǎn)， 若為足夠小的正數(shù) 。如果 且 ，則從任意 出發(fā)，由 產(chǎn)生的序列 收斂到 ，當(dāng) 時(shí)斂速是線性的。 迭代法收斂的階證明：滿足壓縮映像原理迭代法收斂的階 斂速是線性的 線性收斂到 。Steffensen迭代格式由線性收斂知 當(dāng)n充分大時(shí)有 即Steffensen迭代格式展開(kāi)有：Steffensen迭代格式已知 ，則 ，改成 n=0，1，2，

6、Steffensen迭代格式也可以改寫成其中迭代函數(shù)Steffensen迭代法收斂的充要條件定理2.2.3 Steffensen迭代法收斂的充要條件證明：必要性Steffensen迭代法收斂的充要條件充分性Steffensen算法的收斂速度 Steffensen算法的收斂速度定理2.2.5 在定理2.2.3假設(shè)下，若 產(chǎn)生的序列 至少平方收斂到 。 Steffensen算法的收斂速度Steffensen算法的收斂速度 Steffensen算法的收斂速度 Steffensen算法的收斂速度 由定理2.2.4知 至少以平方速度收斂到 。 也就是說(shuō)：簡(jiǎn)單迭代法是線性收斂；Steffensen迭代至少

7、平方以上收斂（加速收斂）。例題例2.2.3試用Steffensen算法求解方程解法一、取 ，由 n = 0，1，2，例題取初值 ，計(jì)算結(jié)果如下：NXnYnZn01.51.3572088081.33086095911.3248991811.3247523791.32472449621.3247179571.3247179571.324717957例題解法二、取 ，由對(duì)于該迭代函數(shù)在一般迭代法中是發(fā)散的，而Steffensen格式卻是收斂的。 n=0，1，2，例題取初值 ，計(jì)算結(jié)果如下：NXnYnZn01.52.3751.23964843711.4162929751.8409219155.2388

8、7276921.3556504421.4913982792.31727069931.3289487771.3470628831.44435122441.3248044891.3251735441.32711728151.3247179441.3247181521.32471898061.324717957Steffensen迭代格式幾何解釋 Steffensen迭代算法 Steffensen迭代算法 2.3 Newton迭代法設(shè)x * 是方程f (x ) = 0的根，又x0 為x * 附近的一個(gè)值 ，將f (x ) 在x0附近做泰勒展式 令 ，則 Newton迭代法去掉 的二次項(xiàng)，有：即以x1

9、代替x0重復(fù)以上的過(guò)程，繼續(xù)下去得：Newton迭代法以此產(chǎn)生的序列Xn得到f(x)=0的近似解，稱為Newton法，又叫切線法。Newton迭代法幾何解釋幾何意義例題例2.3.1 用Newton法求 的近似解。解：由零點(diǎn)定理。例題例題例2.3.2 用Newton法計(jì)算 。解：Newton迭代法算法框圖Newton迭代法算法Newton迭代法收斂性定理2.3.1 設(shè)函數(shù) ，且滿足 若初值 滿足 時(shí)，由Newton法產(chǎn)生的序列收斂到 在a,b上的唯一根。Newton迭代法收斂性證明： 根的存在性根的唯一性Newton迭代法收斂性收斂性Newton迭代法收斂性 Newton迭代法收斂性Newton

10、迭代法收斂性推論 在定理2.3.1條件下， Newton迭代法具有平方收斂速度。代數(shù)方程的Newton迭代法代數(shù)方程的Newton迭代法推導(dǎo)設(shè)n次代數(shù)方程用Newton迭代法求有限區(qū)間的實(shí)根，則要計(jì)算 ，一般采用秦九韶算法。代數(shù)方程的Newton迭代法由Taylor展式代數(shù)方程的Newton迭代法 代數(shù)方程的Newton迭代法同理 代數(shù)方程的Newton迭代法比較x的同次冪系數(shù)得：故代數(shù)方程的Newton迭代公式代數(shù)方程的Newton迭代法算法 2.4弦截法Newton迭代法有一個(gè)較強(qiáng)的要求是 且存在。因此，用弦的斜率 近似的替代 。 弦截法令y=0,解得弦與x軸的交點(diǎn)是坐標(biāo)x2弦截法弦截法的幾何解釋例題例2.4.1 用快速弦截法求方程在區(qū)間（1，2）內(nèi)的實(shí)根。解：取x0=1,x1=2,代入公式2.4.2計(jì)算結(jié)果,如表2.4.1所示。kxkf(xk)01-112521.1666666