1、第四章 方程求根的迭代法,高 云,方程求根需要考慮的問題,求 f (x) = 0 的根,代數(shù)方程： f (x) = a0 + a1x + . . . + anxn,超越方程： f (x) 含超越函數(shù)，如 sin(x), ex, lnx 等,實(shí)根與復(fù)根,根的重?cái)?shù),f (x) = ( x x*)m g(x) 且 g(x*) 0, 則 x* 為 f (x) 的 m 重根,有根區(qū)間：a, b 上存在 f (x) = 0 的一個(gè)實(shí)根,在有根的前提下求出方程的近似根。,迭代法的基本思想,基本思路,轉(zhuǎn)換例子,(1) x = 1(x) = x3-6x2+10 x-2 ;,(2) ;,(3) ;,(4) ;,？

2、哪種轉(zhuǎn)換方法好,幾何含義,幾何含義,壓縮映像定理,定理,設(shè) (x)Ca, b 且可導(dǎo)，若,(2) 0 L 1，使得 | (x) | L 對(duì) xa, b 成立,(1) a (x) b 對(duì)一切 xa, b 都成立,則有,(a) 對(duì)任意 x0a, b，由 xk+1 = (xk) 產(chǎn)生的迭代序列 均收斂到 (x) 在 a, b 中的唯一不動(dòng)點(diǎn) x*。,(b) 有如下的誤差估計(jì),壓縮映像定理證明,(a) 由壓縮映像定理可知，不動(dòng)點(diǎn) x* 存在且唯一。,壓縮映像定理證明,(b),又,全局收斂與局部收斂,定理的條件保證了不動(dòng)點(diǎn)迭代的全局收斂性。,即迭代的收斂性與初始點(diǎn)的選取無關(guān)。,這種在 x* 的鄰域內(nèi)具有

3、的收斂性稱為局部收斂性。,定理中的條件 | (x) | L 1 可以適當(dāng)放寬,(2) (x) 在 x* 的某個(gè)鄰域內(nèi)連續(xù)，且 | (x*) | 1,由 (x) 的連續(xù)性及 | (x*) | 1 即可推出：,存在 x* 的某個(gè) 鄰域 N(x*) =x*- , x* + , 使得對(duì) x N(x*)都有| (x) | L 1, 則由 x0 N(x*) 開始的迭代都收斂。,迭代過程的收斂速度,定義,則稱該迭代為 r 階收斂。,(1) 當(dāng) r =1 時(shí)稱為線性收斂，此時(shí) C 1；,(2) 當(dāng) r =2 時(shí)稱為二次收斂，或平方收斂；,(3) 當(dāng) r 1 時(shí)稱為超線性收斂。,二分法線性收斂,不動(dòng)點(diǎn)迭代中，若

4、 (x*) 0，則,取極限得,(C為常數(shù)),線性收斂,P階收斂,設(shè)迭代 xk+1 = (xk) ，若 (p)(x) 在 x* 的某鄰域內(nèi)連續(xù)，則該迭代法具有 p 階收斂的充要條件是,定理,并且有,證明：,充分性. 根據(jù)泰勒展開有,必要性的證明,必要性. 設(shè)迭代 xk+1 = (xk) 是 p 階收斂。,迭代兩邊取極限 ，由 (x) 的連續(xù)性可知 x* = (x*) 。,設(shè) p0 是滿足,的最小正整數(shù)。,由充分性的證明過程可知迭代 p0 階收斂。,又,若 p0 p， 與迭代 p 階收斂矛盾,p0 = p,迭代過程的加速,設(shè)有不動(dòng)點(diǎn)迭代：,設(shè)：,缺點(diǎn)：每次迭代需計(jì)算,埃特金算法,設(shè)：,Aitken

5、 加速,當(dāng) x 收斂到 x* 時(shí)，修正項(xiàng)分子趨于零。,一點(diǎn)注記,Newton迭代,基本思想：,將非線性方程線性化,設(shè) xk 是 f (x)=0 的近似根， 將 f (x) 在 xk 一階 Taylor 展開:,， 在 xk 和 x 之間。,條件： f(x) 0,Newton迭代,Newton 法可以看作下面的不動(dòng)點(diǎn)迭代：,其中,(x*) = 0,Newton 法至少 二階 局部收斂,定理,設(shè) f(x) 在其零點(diǎn) x* 的某個(gè)鄰域內(nèi)二階連續(xù)可導(dǎo)且 f(x) 0，則存在 x* 的某個(gè) 鄰域 N(x*) =x*- , x* + , 使得對(duì) x0 N(x*)，Newton 法產(chǎn)生的序列以不低于二階的收

6、斂速度收斂到 x* 。,Newton迭代,Newton 法也可以看作一類特殊的加速迭代,取 (x) = x-f(x),收斂性定理,定理,設(shè) f C2a, b，且 f 滿足,(1) f (a) f (b) 0,(2) 對(duì) xa, b， f(x) 0 且 f”(x) 0 ；,(3) 初始點(diǎn) x0 a, b 滿足 f (x0) f”(x0) 0；,則 Newton 法產(chǎn)生的序列收斂到 f 在 a, b 的唯一零點(diǎn) x*。,全局收斂性定理,定理,設(shè) f C2a, b，且 f 滿足,(1) f (a) f (b) 0,(2) 對(duì) xa, b， f(x) 0 且 f”(x) 0 ；,則對(duì)任意初始點(diǎn) x0

7、a, b，Newton 法產(chǎn)生的序列收斂到 f 在 a, b 的唯一零點(diǎn) x*。,(3),舉例（一）,例：設(shè)計(jì)一個(gè)二階收斂算法計(jì)算 (a 0)。,解：轉(zhuǎn)化為求 x2-a = 0 的正根,Newton 迭代：,二階收斂,mynewton.m,重根情形,設(shè) x* 是 f(x) 的 m(m2) 重根，Newton法是否收斂？,Taylor 展式,Newton 迭代：,線性收斂。,且重?cái)?shù) m 越高，收斂越慢。,提高收斂階,提高收斂速度,但 m 通常無法預(yù)先知道！,法一：取,法二：將求 f(x) 的重根轉(zhuǎn)化為求 另一個(gè)函數(shù) 的單根。,構(gòu)造針對(duì) (x) 的具有二階收斂的 Newton 迭代：,令 ，則 x

8、* 是 (x) 的單重根。,降低初始點(diǎn)的要求,例：求 sin(x)-x/6=0 的正根。,mynewton.m,Newton 下山法：,k,k 為數(shù)列 中滿足 的最大數(shù)。,算法 7.2 (Newton下山法),給定初始點(diǎn) x0，精度要求 ,1. 如果 | f (xk)| , 停機(jī)，輸出 xk,2. 計(jì)算 ， =1,3. 如果| f (xk+dk)| | f(xk)|，令 xk+1= xk+dk ，返回第1步； 否則 折半，重新計(jì)算第3步,Newton 法的收斂依賴于初始點(diǎn)的選取。,割線法,Newton法的缺點(diǎn)：每步迭代都要計(jì)算導(dǎo)數(shù)值,只需計(jì)算函數(shù)值，避免計(jì)算導(dǎo)數(shù)；,切線斜率 割線斜率,xk+1,xk+1,切線,割線,需要兩個(gè)初始點(diǎn)；,收斂比Newton法稍慢，但對(duì)初始點(diǎn)要求同樣高。,割線法公式,兩點(diǎn)割線法,單點(diǎn)割線法,誤差估計(jì),局部收斂