第7章 非線性方程求根

1、非線性方程的迭代法求根基本概念n非線性方程f(x)=0的根(解) x*,也稱為非線性函數(shù)f(x)的零點(diǎn)，f(x*)=0。nf(x)=0的m重根定義：f(x)=(x-x*)mg(x), g(x*)0，則稱x*為f(x)=0的m重根，或f(x)的m重零點(diǎn)。nm重根的判定條件： x*為f(x)=0的m重根當(dāng)且僅當(dāng). 0)(; 0)()()(*)(*)1(*xfxfxfxfmm非線性方程的迭代法求根基本概念n即使對(duì)于代數(shù)方程f(x)=0 (f(x)為多項(xiàng)式)，當(dāng)其次數(shù)超過4時(shí)也沒有公式解，而3次、4次代數(shù)方程有公式解但很復(fù)雜。n若區(qū)間a,b內(nèi)存在f(x)=0的根，則稱a,b為f(x)=0的有根區(qū)間。判

2、定條件：若f(a)f(b)0,則a,b為f(x)=0的有根區(qū)間。非線性方程的迭代法求根非線性方程的迭代法求根基本步驟：(1)在f(x)=0的有根區(qū)間a,b內(nèi)任取一初始近似值x0;(2)取與f(x)=0等價(jià)的方程 ，形成迭代序列xk：(3)若xk收斂，則極限為f(x)=0的準(zhǔn)確解，而有限步迭代結(jié)果xn為近似解。由迭代終止 條件決定n的選取，得近似解xn,結(jié)束迭代過程。)(xx);, 1 , 0()(1kxxkk非線性方程求根的二分法二分法基本步驟：(1)考查f(x)=0的有根區(qū)間a,b的中點(diǎn)(2)若x0不為f(x)=0的根，則a,x0或x0,b之一為f(x)=0的有根區(qū)間(由f(a)f(x0)0

3、或f(x0)f(b) 0判定)：若f(a)f(x0)1 稱超線性收斂。 )(xx)(1kkxx),0(lim1CCeepkkk,*xxekk收斂階Th4 對(duì)迭代過程 如果在所求根x*的某鄰域內(nèi)連續(xù)，且則該迭代過程是p階收斂的。),(1kkxx)()(xp, 0)(, 0)()()(*)(*)1(* xxxxppTh4證明證明 局部收斂性由 證得。 將 在x*處泰勒展開，有 10)(* x)(kx,)(!)()()(!)()()!1()()()()(*)(*)(1*)1(*pkppkppkpkkxxpxxxpxxpxxxxxxTh4證明故證得迭代過程p階收斂。.!)(!)(limlim,!)()

4、(!)()()(*)()(1)(*)(*11Cpxpeeepxxpxxxxeppkpkkkpkppkpkkk加速迭代法n加速迭代法基本思想： 在己有收斂迭代法基礎(chǔ)上改造得到一個(gè)收斂更快的迭代法。n埃特金加速迭代法：(近似推導(dǎo)) ).(),(),()(),(*1*212*0*0*101xxMxxxxxxMxxxxxx加速迭代法消去M得由此得埃特金加速法,2)(2,210201001221201*1*0*2*1xxxxxxxxxxxxxxxxxxxxxx), 1 , 0(.)(2)(2221211kxxxxxxxxxxkkkkkkkkkk埃特金加速法可證：故 比 收斂的更快。, 0lim*1xxx

5、xkkkkxkx斯蒂芬森迭代法n結(jié)合埃特金加速法和不動(dòng)點(diǎn)迭代法形成斯蒂芬森迭代法：)., 1 , 0(2)(),(),(21kxyzxyxxyzxykkkkkkkkkkk斯蒂芬森迭代法幾何意義 定義x點(diǎn)關(guān)于方程 的誤差為：則該方程的根x*的誤差而xk,yk作為 的近似根,其誤差不為0,且.)()(,)()(kkkkkkkkkkyzyyyxyxxx)(xx)(xx. 0)()(*xxx.)()(xxx斯蒂芬森迭代法幾何意義由二點(diǎn) 擬合的直線為該直線上的點(diǎn) 可解釋為：y近似為x點(diǎn)關(guān)于 的誤差。故該直線與x-軸的交點(diǎn)則為誤差近似為零的點(diǎn)。 該直線與x-軸的交點(diǎn)x滿足)(,( ,)(,(kkkkyyx

6、x)()()()(kkkkkkxxxyxyyy),(yx.)()(xxx斯蒂芬森迭代法幾何意義 解得. 0)()()()(kkkkkkxxxyxyy.)2)()()()()()()()(122kkkkkkkkkkkkkkkkkkkkxxyzxyxxyyzxyxxyxyyxx斯蒂芬森迭代法幾何意義 即斯蒂芬森迭代法的xk+1點(diǎn)是按xk,yk點(diǎn)的誤差的線性擬合基礎(chǔ)上獲得改善的點(diǎn)。 斯蒂芬森迭代法也可寫為：)5 . 3(.)(2)()()(), 1 , 0()(21xxxxxxxkxxkk斯蒂芬森迭代法收斂定理Th5 若x*為(3.5)式迭代函數(shù) 的不動(dòng)點(diǎn), 則x*也為 的不動(dòng)點(diǎn)。反之，若x*為的不

7、動(dòng)點(diǎn), 且 存在， 則x*也為 的不動(dòng)點(diǎn)，且斯蒂芬森迭代法(3.5)收斂。(略證) )(x)(x)(x)(x , 1)(* x)(x牛頓迭代法n牛頓迭代法推導(dǎo)： 設(shè)xk為方程f(x)=0的近似根，在xk處把f(x)展開為于是f(x)=0近似為線性方程該線性方程的根xk+1則為f(x)=0的更近似的根.),)()()(kkkxxxfxfxf. 0)()(kkkxxxfxf牛頓迭代法 (假設(shè) )即為牛頓迭代法。其幾何意義即為“以切線代替曲線”,故牛頓迭代法又稱切線法。其迭代函數(shù)為)., 1 , 0()()(, 0)()(11kxfxfxxxxxfxfkkkkkkkk0)(kxf. )()()(xf

8、xfxx牛頓迭代法的收斂速度牛頓迭代法的迭代函數(shù)的導(dǎo)函數(shù)為在x*為f(x)=0的單根的假設(shè)下： 故牛頓迭代法是平方收斂的。又 2)()()()(xfxfxfx . 0)(, 0)(*xfxf. 0)(* x,)()()(*xfxfx .)(2)(! 2)()(lim*2*1Cxfxfxxxxxkkk 簡(jiǎn)化牛頓迭代法n牛頓迭代法收斂快(2階)但計(jì)算量大。每次迭代時(shí)求 幾乎又需要有算法。n牛頓迭代法為局部收收斂，初值需在根的適當(dāng)鄰域內(nèi)選取。n簡(jiǎn)化牛頓法即取與牛頓法類似但更簡(jiǎn)單的迭代形式 )(),(kkxfxf), 1 , 0()()()(01kxfxfxxCfxxkkkkk簡(jiǎn)化牛頓迭代法n牛頓下山

9、法即在牛頓迭代法基礎(chǔ)上增加下降性要求： 。用牛頓法加速收斂速度；用下降性保證單調(diào)收斂。記)()(1kkxfxf)., 1 , 0; 10()()()1 ( ,)()(111kxfxfxxxxxfxfxxkkkkkkkkkk簡(jiǎn)化牛頓迭代法 稱為下山因子，從=1開始，逐次減半試驗(yàn)，直到某使下降性條件 成立，則選該及該下的 繼續(xù)迭代法.問題 總存在使下降性條件成立嗎?不一定. )()(1kkxfxf.1kx重根情形牛頓迭代法n設(shè)f(x)=(x-x*)mg(x), g(x*)0，x*為f(x)=0的m重根，此時(shí)，f(x*)= f(m-1)(x*)=0, f(m)(x*)0. 此時(shí)，只要 牛頓迭代法仍可

10、用，但迭代函數(shù)只有線性收斂。 而取迭代函數(shù), 0)(kxf. 111)(,)()()(*mxxfxfxx,)()()(xfxfmxx重根情形牛頓迭代法則所構(gòu)造迭代法有2階收斂 ，但需知道重根的重?cái)?shù)。), 1 , 0()()(1kxfxfmxxkkkk)0)(* x弦截法與拋物線法n解決牛頓迭代法中計(jì)算 困難，用其它量來代替，如用 代替 -以弦代替切線，形成弦截法等。)., 1 , 0()()(1kxfxfxxkkkk)(kxf 11)()(kkkkxxxfxf)(kxf 弦截法n設(shè) 則過的直線的根 ,可作為 的近似根：由 得到弦截法。 , 0)(, 0)(1kkxfxf)(,(),(,(11k

11、kkkxfxxfx)()()()()(111kkkkkkxxxxxfxfxfxp1kx0)(11kxp0)(xf. 0)(1kxf), 2 , 1()()()()(111kxxxfxfxfxxkkkkkkk弦截法n弦截法需給定兩個(gè)初值 方可迭代下去.nTh6 假設(shè)f(x)在x*的某鄰域內(nèi)具有二階連續(xù)導(dǎo)數(shù)，且在上， 又初值則當(dāng)充分小時(shí)，弦截法按階收斂到x*。10,xx. 0)( xf,10 xx618. 1251p拋物線法n拋物線法基本思想： 對(duì)f(x)=0的三個(gè)近似根xk， xk-1， xk-2，構(gòu)造過三個(gè)節(jié)點(diǎn)(xk ,f(xk)， (xk-1 ,f(xk-1)， (xk-2 ,f(xk-2)的二次插值多項(xiàng)式p2(x),以p2(x)=0的適當(dāng)根xk+1作為f(x)=0的根。拋物線法 )(,)()()(,)()()(,)(,)()()(,)(,)()(,)(,)()(12112211211221121112112kxkkkkkkkkkkkkkkxkkkkkkkkkkxxkkkkkkkkkkkkkkkkkxxxxxfxxfxfxxxxxxxfxfxxxxxxxfxxfxxxxxfxxxxxxxxxfxxxxfxfxxxxxxxfxxxxfxfxp拋物線法p2(x)=0的兩個(gè)零點(diǎn)：,2,)(4,2,)(4)(