實(shí)用數(shù)值計(jì)算方法方程求根

1、計(jì)計(jì) 算算 方方 法法授課老師：聶德明 仰儀北樓606計(jì)量測試工程學(xué)院計(jì)量測試工程學(xué)院Numerical Method 方程求根方程求根1 問題的提出問題的提出2 二分法二分法3 迭代法迭代法4 牛頓法及割線法牛頓法及割線法預(yù)備知識預(yù)備知識1. Taylor公式公式( )20000000( )000( )1( )( )( )( -)( )( -).( -).2!( )( -)( )!kkikikifxf xf xf xx xfxx xx xkfxx xr xi (1)100( )( )( -), () ,(1)!kkkfr xx xksix xk拉格朗日余項(xiàng)：拉格朗日余項(xiàng)：2. 拉格朗日中值定

2、理拉格朗日中值定理( )()()fbfafba預(yù)備知識預(yù)備知識若若f(x)在在a, b上連續(xù)，且上連續(xù)，且f(x)在在(a, b)內(nèi)可導(dǎo)，則存在內(nèi)可導(dǎo)，則存在a, b，使：，使：或或( )( )()(), ,f bfafbaa b設(shè)函數(shù)設(shè)函數(shù)f(x)在區(qū)間在區(qū)間a, b上連續(xù)，在上連續(xù)，在(a, b)內(nèi)可導(dǎo)，則內(nèi)可導(dǎo)，則f(x)在在a, b上單調(diào)遞增上單調(diào)遞增(遞減遞減)的充要條件是的充要條件是3. 函數(shù)的單調(diào)性函數(shù)的單調(diào)性預(yù)備知識預(yù)備知識(a, b), f (x)0(f (x)0)x1 問題的提出問題的提出方程的一般形式：f(x)=0 ，滿足方程的x值通常叫做方程的根或解，也叫函數(shù)f(x)的

3、零點(diǎn)。 實(shí)際問題實(shí)際問題n 代數(shù)方程代數(shù)方程5次以上的方程無求根公式次以上的方程無求根公式 n 超越方程：包含超越函數(shù)，如超越方程：包含超越函數(shù)，如 sinx, lnx, ex近似求解近似求解1 問題的提出問題的提出u 求根的隔離區(qū)間隔離區(qū)間 ，即確定根所在區(qū)間u 根的精確化。粗糙的近似值-滿足精度的近似值 方程求根步驟：方程求根步驟：1 問題的提出問題的提出求根的求根的隔離區(qū)間隔離區(qū)間設(shè)函數(shù)f(x)在a, b內(nèi)連續(xù)，嚴(yán)格單調(diào)，且有f(a)f(b)0，則在a, b內(nèi)方程f(x)=0有且僅有一個(gè)實(shí)根。 u 函數(shù)函數(shù)y=f(x)與橫軸與橫軸( (y=0) )交點(diǎn)交點(diǎn)u f(x)=0 f1(x)=f

4、2(x)，函數(shù)，函數(shù)f1(x)與與f2(x)的交點(diǎn)的交點(diǎn)u 區(qū)間區(qū)間a, b內(nèi)選擇內(nèi)選擇x1, x2, x3, x4 ，根據(jù)，根據(jù)f(x)在這些在這些 點(diǎn)上值的符號確定點(diǎn)上值的符號確定 2 二分法二分法二分法二分法也稱對分區(qū)間法、對分法等，是最簡單的求根也稱對分區(qū)間法、對分法等，是最簡單的求根方法，屬于區(qū)間法求根類型。方法，屬于區(qū)間法求根類型。 設(shè)函數(shù)f(x)在a, b內(nèi)連續(xù)，嚴(yán)格單調(diào)，且有f(a)f(b)0，則在a, b內(nèi)方程f(x)=0有且僅有一個(gè)實(shí)根。 *111()()22kkkkxxbaba2 二分法二分法誤差估計(jì)誤差估計(jì)對于所給定的精度對于所給定的精度 ，則可得，則可得11ln()l

5、n()12ln 2kbabak2 二分法二分法32( )210f xxxx例例3 用二分法求下列方程在區(qū)間用二分法求下列方程在區(qū)間0, 1內(nèi)的實(shí)根，要內(nèi)的實(shí)根，要求有求有3位有效數(shù)字。位有效數(shù)字。1. (0)10,(1)10ff 2172.( )3()0,0,123fxxx3. (0.1)0f*0.1,1x*3111()1022kxxba3 迭代法迭代法基本思想：逐次逼近基本思想：逐次逼近粗糙的初值粗糙的初值校正后的近似值校正后的近似值迭代公式迭代公式END滿足精度滿足精度不滿足精度不滿足精度3 迭代法迭代法( )0( )f xxx0 , ,xa b取用遞推公式1()kkxx可得序列可得序列

6、xk: x0, x1, x2, x3, 如果當(dāng)如果當(dāng)k時(shí)，序列時(shí)，序列xk有極限有極限x*，則，則x*是方程是方程f(x)=0的根。的根。 迭代公式迭代公式序列有極限：迭代公式收斂序列有極限：迭代公式收斂 序列無極限：迭代公式發(fā)散序列無極限：迭代公式發(fā)散用迭代法求下列方程在區(qū)間用迭代法求下列方程在區(qū)間2, 4的根。的根。2( )230f xxx3 迭代法迭代法12323kkxxxx取取x0 =4，則，則1023113.317xx21239.6343.104xx32239.2083.034xx43239.0683.011xx54239.0223.004xx收斂收斂3 迭代法迭代法22111(3)

7、(3)22kkxxxx取取x0 =4，則，則16.5x 219.625x 3191.070 x 發(fā)散發(fā)散幾何意義幾何意義3 迭代法迭代法( )0( )f xxx1122( )( )( )yfxxyfxx1yx2( )yx00( , ( )xx11( , ( )xx0 x2x1xpxy02( )yx1yxxy0*x0 x1x*x2x假設(shè)迭代函數(shù)假設(shè)迭代函數(shù) ( (x x) ) 在在a, b上具有一階連續(xù)的導(dǎo)數(shù)，且滿足上具有一階連續(xù)的導(dǎo)數(shù)，且滿足n 當(dāng)當(dāng) x a, b 時(shí)，時(shí)， ( (x x) ) a, b；n 存在正常數(shù)存在正常數(shù) L 1， 使得使得 | | (x) |(x) | L ; 則則u

8、 方程在方程在a, b上有唯一根上有唯一根 x*u 對任意對任意x0 a, b，迭代格式，迭代格式xk+1 = ( (x xk k) )都收斂到都收斂到 x* u u u 定理定理1*11kkkLxxxxL*101kkLxxxxL*1*lim()kkkxxxxx2( )230f xxx23( )xxx21(3)( )2xxx1( )23xx2, 4( )1(2)17xx( )xx2, 4( )(2)2xx定義定義1 ：局部收斂性：局部收斂性對于方程對于方程 x= (x)，若在，若在 x* 的某個(gè)領(lǐng)域的某個(gè)領(lǐng)域 S = x | x x* - , x* + 內(nèi)，對任意初值內(nèi)，對任意初值x0 S，迭

9、代格式，迭代格式xk+1 = (xk) 都收斂，都收斂，則稱該迭代格式在則稱該迭代格式在 x* 的附近是局部收斂的。的附近是局部收斂的。3 迭代法迭代法定理定理3 設(shè)方程設(shè)方程 x= (x)有根有根x*，且在，且在 x* 的某個(gè)領(lǐng)域的某個(gè)領(lǐng)域 S = x | x x* - , x* + 內(nèi)存在一階連續(xù)導(dǎo)數(shù)，則內(nèi)存在一階連續(xù)導(dǎo)數(shù)，則u 當(dāng)當(dāng)|(x*) |1時(shí)，迭代格式時(shí)，迭代格式xk+1 =(xk)發(fā)散發(fā)散 1yx2( )yx00( , ( )xx11( , ( )xx0 x2x1xpxy02( )yx1yxxy0*x0 x1x*x2x3 迭代法迭代法迭代法的收斂速度（收斂階）迭代法的收斂速度（

10、收斂階） u p=1，且，且0|c|1，稱為線性收斂，稱為線性收斂 u p=2，稱為平方收斂，稱為平方收斂假設(shè)迭代函數(shù)假設(shè)迭代函數(shù) (x)在在a, b上具有一階連續(xù)的導(dǎo)數(shù)，且滿足上具有一階連續(xù)的導(dǎo)數(shù)，且滿足n 當(dāng)當(dāng) x a, b 時(shí)，時(shí)， (x) a, b；n 存在正常數(shù)存在正常數(shù) L 1， 使得使得 | (x) | L ; 則則u 方程在方程在a, b上有唯一根上有唯一根 x*u 對任意對任意x0 a, b，迭代格式，迭代格式xk+1 = (xk)都收斂到都收斂到x* u u u 定理定理1*11kkkLxxxxL*101kkLxxxxL*1*lim()kkkxxxxx定理定理2.4 若若

11、(x)在在x*附近的某個(gè)領(lǐng)域內(nèi)有附近的某個(gè)領(lǐng)域內(nèi)有p階階(p1)連續(xù)導(dǎo)數(shù)，且連續(xù)導(dǎo)數(shù)，且(x*)= x*, (x*)= 0, (p-1)(x*)= 0, (p)(x*) 0, 則對一個(gè)任意靠近則對一個(gè)任意靠近x*的初始值的初始值x0，迭代公式，迭代公式xk+1 =(xk)是是p階收斂的，且有階收斂的，且有3 迭代法迭代法*()*1*()lim()!pkpkkxxxxxp3 迭代法迭代法迭代法的收斂速度（收斂階）迭代法的收斂速度（收斂階） u p=1，且，且0|c|1，稱為線性收斂，稱為線性收斂 u p=2，稱為平方收斂，稱為平方收斂假設(shè)迭代函數(shù)假設(shè)迭代函數(shù) (x)在在a, b上具有一階連續(xù)的導(dǎo)

12、數(shù)，且滿足上具有一階連續(xù)的導(dǎo)數(shù)，且滿足n 當(dāng)當(dāng) x a, b 時(shí)，時(shí)， (x) a, b；n 存在正常數(shù)存在正常數(shù) L 1， 使得使得 | (x) | L ; 則則u 方程在方程在a, b上有唯一根上有唯一根 x*u 對任意對任意x0 a, b，迭代格式，迭代格式xk+1 = (xk)都收斂到都收斂到x* u u u 定理定理1*11kkkLxxxxL*101kkLxxxxL*1*lim()kkkxxxxx定理定理2.4 若若 (x)在在x*附近的某個(gè)領(lǐng)域內(nèi)有附近的某個(gè)領(lǐng)域內(nèi)有p階階(p1)連續(xù)導(dǎo)數(shù)，且連續(xù)導(dǎo)數(shù)，且(x*)= x*, (x*)= 0, (p-1)(x*)= 0, (p)(x*)

13、 0, 則對一個(gè)任意靠近則對一個(gè)任意靠近x*的初始值的初始值x0，迭代公式，迭代公式xk+1 =(xk)是是p階收斂的，且有階收斂的，且有2.3 迭代法迭代法*()*1*()lim()!pkpkkxxxxxp2.4 牛頓法牛頓法()()()0kkkf xfxxx( )()()()kkkf xf xfxxx()()kkkf xxxfx1()()kkkkf xxxfx牛頓迭代公式牛頓迭代公式( )( )( )f xxxfx幾何意義幾何意義1()()kkkkf xxxfx()()()kkkyf xfxxxx2x0 x1x*牛頓迭代法牛頓迭代法x3y=f(x)4 牛頓法牛頓法局部收斂性局部收斂性定理定

14、理2.3 設(shè)方程設(shè)方程 x=(x)有根有根x，且在，且在 x* 的某個(gè)領(lǐng)域的某個(gè)領(lǐng)域 S = x | x x* - , x* + 內(nèi)存在一階連續(xù)導(dǎo)數(shù)，則內(nèi)存在一階連續(xù)導(dǎo)數(shù)，則u 當(dāng)當(dāng)|(x*) |1時(shí)，迭代格式時(shí)，迭代格式xk+1 =(xk)發(fā)散發(fā)散 4 牛頓法牛頓法局部收斂性局部收斂性( )( )( )f xxxfx2( )( )( )( )f x fxxfx*2()()()0()f xfxxfx定理定理4 若若 (x)在在x*附近的某個(gè)領(lǐng)域內(nèi)有附近的某個(gè)領(lǐng)域內(nèi)有p階階(p1)連續(xù)導(dǎo)數(shù)，且連續(xù)導(dǎo)數(shù)，且(x*)= x*, (x*)= 0, (p-1)(x*)= 0, (p)(x*) 0, 則對

15、一個(gè)任意靠近則對一個(gè)任意靠近x*的初始值的初始值x0，迭代公式，迭代公式xk+1 =(xk)是是p階收斂的，且有階收斂的，且有*()*1*()lim()!pkpkkxxxxxp2( )( )( )( )( )( )fxfxxf xfxfx( )( )( )f xxxfx2( )( )( )( )f x fxxfx*()()()fxxfx*()0 x*()0 x二階局部收斂二階局部收斂牛頓法牛頓法局部收斂性局部收斂性*11*2*11()limlim()()22()kkpkkkkxxefxxxxefx4 牛頓法牛頓法大范圍收斂性大范圍收斂性定理定理2.6 若若 f(x)在在a, b上存在二階導(dǎo)數(shù)，且滿足下列條件：上存在二階導(dǎo)數(shù)，且滿足下列條件：uf(a)f(b) 0則牛頓迭代序列則牛頓迭代序列xk收斂于方程收斂于方