計(jì)算方法電子教案：第二章 非線性方程的數(shù)值解法

1、第二章 非線性方程的數(shù)值解法,2.1 二分法 2.2 一般迭代法 2.3 牛頓迭代法 2.4 弦截法,（1）確定初始含根區(qū)間,數(shù)值計(jì)算方法主要分為兩大類。,第一類是區(qū)間收縮法。,（2）收縮含根區(qū)間,第二類是迭代法。,（1）選定根的初始近似值,（2）按某種原則生成收斂于根的近似點(diǎn)列,2.1 二分法,基本假設(shè) :,2.1.1 二分法的計(jì)算步驟,常用終止原則為:,2.1.2 二分法的收斂性與事前誤差估計(jì),所以，二分法總是收斂的,故可取初始區(qū)間,解,2.1.3 二分法評(píng)述,優(yōu)點(diǎn)：簡(jiǎn)單可靠，易于編程實(shí)現(xiàn)，它對(duì)函數(shù)要求低，適 用于的奇數(shù)重根情形。,缺點(diǎn)：不能直接用于求偶重根，不能用于求復(fù)根，也難 以向方程

2、組推廣使用，收斂速度慢。,2.2 一般迭代法,迭代法的算法思想為：,(1) 把（2-2）等價(jià)變換為如下形式,(2) 建立迭代格式,或更一般地建立迭代格式,(3) 適當(dāng)選取初始值，遞推計(jì)算出所需的解。,2.2.1 迭代法的算法思想,2.2.2 迭代法的收斂性,命題得證。,證,定理2.1 設(shè) x*= g(x*), g(x) 在閉區(qū)間 ： 內(nèi)李普希茲連續(xù)，則對(duì)任何初值 由迭代格式 xk+1= g(xk) 計(jì)算得到的解序列 收斂于 x* ( 這時(shí)我們稱迭代格式 xk+1= g(xk)在 x* 的鄰域 上局部收斂）。,（1）首先用數(shù)學(xué)歸納法證明：,由假設(shè)知,又設(shè) ，則,綜上，由歸納法原理知，結(jié)論成立。,

3、證,因此， ，定理得證。,反設(shè)存在,矛盾。所以結(jié)論成立。,2) 迭代函數(shù)在 x* 附近李普希茲連續(xù)從而收斂的迭代格式統(tǒng)稱為皮卡（Picard）迭代,(2) 由（1）的結(jié)論和 g(x) 在 內(nèi)李普希茲連續(xù)的假設(shè)，可遞推得到,注 1) g(x) 在內(nèi)李普希茲連續(xù)的條件保證了x* 為 f (x)=0 在 內(nèi)的唯一根。,證,推論 設(shè) x*= g(x*) ， 若 g(x) 在 x* 附近連續(xù)可微且 ，則迭代格式 xk+1= g(xk) 在 x* 附近局部收斂。,注 由于 x* 事先未知，故實(shí)際應(yīng)用時(shí)，代之以近似判則 。 但需注意，這實(shí)際上是假設(shè)了x0充分接近 x* ，若 x0 離 x* 較遠(yuǎn)，迭代格式可

4、能不收斂。,定理2.2 （非局部收斂定理）如果 在 上連續(xù)可微且以下條件滿足：,注 雖然定理2.1的條件是充分條件，但其條件并不很強(qiáng)，實(shí)際上，我們易證如下命題。,命題2.2 若在區(qū)間 內(nèi) ，則對(duì)任何 ，迭代格式 不收斂。,2.2.3 迭代法的誤差估計(jì),故對(duì)正整數(shù) p，有,（2）事后誤差估計(jì),由此，對(duì)給定的精度 可進(jìn)行,(1) 事前誤差估計(jì),簡(jiǎn)單地代之以,或,例 2.2 試建立收斂的迭代格式求解 在區(qū)間(2,3)內(nèi)滿足精度要求 的根。,首先可簡(jiǎn)單的把 等價(jià)化為,由此建立迭代格式,所以該迭代格式在內(nèi)不收斂，不可取。,為建立收斂的迭代格式，我們把 等價(jià)化為,從而建立迭代格式,解,易知在 x 0時(shí) g

5、(x) 單調(diào)增，故有 2 g(2) g(x) g(3) 3,故由定理2.2得：任取x0 2,3，該迭代格式收斂。,取 x0=2 計(jì)算，結(jié)果見表 2-2（書17頁(yè)）。,2.2.4 迭代法的收斂速度與加速收斂技巧,則稱該迭代格式是p 階收斂的。特別地，p=1時(shí)稱為線性收斂， 1p2 時(shí)稱為超線性收斂，p=2 時(shí)稱為平方收斂。,定義2.2 設(shè)迭代格式 的解序列 收斂于 的根 ，如果迭代誤差 當(dāng) 時(shí)滿足漸近關(guān)系式,對(duì)于線性收斂的計(jì)算格式，可采用以下介紹的埃特肯（Aitken）加速技巧來提高收斂速度。,設(shè)序列 線性收斂于 ，即有 ，則近似地有,兩式相除得,解得,把埃特肯加速技巧應(yīng)用于單步迭代法 便構(gòu)成了

6、Steffensen算法。,據(jù)此，我們可取修正值 作為 的新近似值以提高精度。這一技巧便稱為埃特肯加速技巧。,例 2.3 試用Steffensen算法求解 在區(qū)間（2，3）內(nèi)滿足精度要求 的根。,對(duì)例2.2 的迭代格式 取 用算法計(jì)算，結(jié)果見表 2-3 。,解,2.3 牛頓迭代法,2.3.1 牛頓迭代公式的構(gòu)造,設(shè) f (x) 在其零點(diǎn) 附近連續(xù)可微，已知 為的第k次近似值，則,取 的根作為 的第k+1次近似值,其迭代函數(shù)為,2.3.2 牛頓迭代法的收斂性與收斂速度,定理 2.3 給定 f (x)=0，如果在根 附近 f (x)二階連續(xù)，且 為 f (x)=0的單根，則牛頓迭代法在 附近至少是

7、平方收斂的。,首先證明牛頓迭代法的收斂性：,而單根條件保證了,因此由定理2.1知，牛頓迭代法局部收斂。,證,其次證明牛頓迭代法的收斂速度：,整理得,可見，當(dāng) 時(shí)，牛頓迭代法為平方收斂；當(dāng) 時(shí)，牛頓迭代法超平方收斂。,例 2.4 試用牛頓迭代法求解 在區(qū)間 (2,3) 內(nèi)滿足精度要求 的根。,相應(yīng)于該方程的牛頓迭代公式為,取 x0 = 2 ，計(jì)算結(jié)果見表2-4。,解,牛頓迭代法評(píng)述,優(yōu)點(diǎn)：是收斂速度比較快,缺點(diǎn)：(1) 局部收斂，對(duì)初始值的要求比較高。為解決這一問題，可采用二分法來提供足夠“好”的近似值作為迭代初值，或通過增加“下山”限制來放寬對(duì)初值的要求，即把牛頓迭代法修改為,其中 的選取使得

8、 （這稱為“下山”限制）。該方法稱為牛頓下山法。,（2）當(dāng) 為 重根時(shí)，牛頓迭代法僅僅線性收斂。,（3）由于涉及 的計(jì)算，導(dǎo)致了對(duì)函數(shù)的要求高，并增加了每一迭代步的計(jì)算量，這在一定程度上減弱了該迭代法收斂快的優(yōu)越性，而且在向非線性方程組推廣時(shí)，使計(jì)算量和對(duì)函數(shù)的要求大大增加。因此，人們致力于研究建立牛頓迭代法的修改格式以回避對(duì)函數(shù)導(dǎo)數(shù)值的計(jì)算。本章僅對(duì)非線性方程介紹一種較為有效的修改算法弦截法。,2.4 弦截法,計(jì)算思想是：若已知 x* 的兩個(gè)近似值 xk 和 xk-1，則以 f (x) 在 xk 與 xk-1 之間的平均變化率(差商) 近似代替 ，據(jù)此把牛頓迭代法修改為,定理 2.4 設(shè) f (x) 在其零點(diǎn) x* 的鄰域 內(nèi)二階連續(xù)，且對(duì) ，則對(duì) ，相應(yīng)的弦截法是 階收斂的。,該定理說明弦截法是超線性收斂的算法，也是局部收斂的方法，其迭代初始值亦可用二分法提供。,例 2.5 試用弦截法求解 在區(qū)間內(nèi)滿足精度要求 的根。,相應(yīng)于該方程的弦截法公式為,取 計(jì)算，結(jié)果見表2-5。,解,例 2.6 試討論函數(shù)方程 的根的分布情況， 分別用