【正文】 ? kk babababa , 2211)(2 1)(21 11 ababab kkkkk ?????? ?? ? 當 k→∞ 時趨于零 ,這些區(qū)間最終收斂于一點 x* 即為 所求的根 。 二分區(qū)間法 當給定精度 ε ＞ 0后 ,要想 成立 ,只要 取 k滿足 即可，亦即當 : ??? kxx *???? )(2 1 1 abkl g( ) l g 1l g 2bakK ?????時 ,做到第 K+1次二分 ,計算得到的 就是滿足精度要求的近似根 。 二分區(qū)間法 誤差限為 只要取 k滿足 )(2 1 1* abxx kk ??? ?31 1021)(21 ?? ??? abk即可，亦即 3102 ?k 10lg3 ??gk所以需二分 10次便可達到要求。 ? ?ba,2133/87 鄭州大學研究生 20222022學年課程 數(shù)值分析 Numerical Analysis 例 求方程 f(x)= x 3 –ex =0的一個實 根 。 迭代法及其加速 為求解非線性方程 f(x)=0的根，先將其寫成便于迭代的 等價方程 其中 為 x的連續(xù)函數(shù) )(x?)( xx ??迭代法的基本思想 如果數(shù) 使 f(x*)=0, 則也有 , 反之 , 若 , 則也有 , 稱 為 迭代函數(shù) ，而稱 x* 為 的 不動點 。 迭代法及其加速 如果由迭代格式 產生的序列 收斂 ,即 ? ?nx)(1 kk xx ???*lim xxnn ???則稱 迭代法收斂 。 迭代法及其加速 如果取初始值 ＝ ，用上述兩個迭代公式分別迭代，計算結果為 0x40/87 鄭州大學研究生 20222022學年課程 數(shù)值分析 Numerical Analysis 167。 迭代法及其加速 y= x y y = )( x? y= x 1)(0*??? x? 0)(1*???? x? P 0 P 2 P* Q 1 Q 2 x 1 x 0 x 2 x* x y x 0 x x 1 x 2 x 3 x* y = )( x?)( x? P* P 1 迭代法的幾何意義 42/87 鄭州大學研究生 20222022學年課程 數(shù)值分析 Numerical Analysis 167。并有誤差估計式 )(x?)(x?)(x??)( xx ?? *x0x )(1 kk xx ???*x1*1 ????? kkk xxLLxx01*1 xxLLxx kk ????① ② 45/87 鄭州大學研究生 20222022學年課程 數(shù)值分析 Numerical Analysis 由連續(xù)函數(shù)介值定理知 , 必有 ∈ [a, b], 使 所以有解存在 , 即 假設有兩個解 和 , , ∈ [a, b]，則 ， 由微分中值定理有 其中 ξ 是介于 x*和 之間的點 從而有 ξ ∈ [a,b]，進而有 由條件 (2)有 1, 所以 =0，即 = ，解唯一。 迭代法及其加速 例 對方程 ,構造收斂的迭代格式 , 求其最小正根。 ② ,即 此時迭代公式滿足迭代收斂條件 。 )(1 kk xx ???52/87 鄭州大學研究生 20222022學年課程 數(shù)值分析 Numerical Analysis 167。 迭代法及其加速 定義 設迭代過程 收斂于 的根 ,記迭代誤差 若存在常數(shù) p（ p≥ 1） 和 c（ c0） ， 使 )(1 kk xx ??? )( xx ??*xkk xxe ?? *迭代法的收斂速度 ceepkkk????1lim則稱序列 是 p 階收斂 的 ,c稱 漸近誤差常數(shù) 。 迭代法及其加速 數(shù) p的大小反映了迭代法收斂的速度的快慢，p愈大，則收斂的速度愈快，故迭代法的收斂階是對迭代法收斂速度的一種度量。 證 : 迭代公式相應的迭代函數(shù)為 21132kkk xxx ??? 3* 3?x2132)(xxx ???436)(232)(xxxx ?????? ?? ，根據(jù) 定理 ，迭代公式平方收斂。這就是本節(jié)要介紹的牛頓迭代法 . 0)( ?xf0)( ?xf )(xx ?? )(x?60/87 鄭州大學研究生 20222022學年課程 數(shù)值分析 Numerical Analysis 167。 牛頓 (Newton)迭代法 牛頓迭代法的幾何意義 方程 f(x)=0的根 x*是曲線 y=f(x)與 x軸交點的橫坐標 ,設 xk是根 x*的某個近似值 ,過曲線 y=f(x)的橫坐標為xk的點 Pk=(xk, f (xk))引切線交 x軸于 xk+1 , 并將其作為 x* 新的近似值 ,重復上述過程 ,可見一次次用切線方程來求解方程 f(x)=0的根 ,所以亦稱為 牛頓切線法 。又由 定理 , 迭代公式至少具有二階收斂速度。180。180。 牛頓 (Newton)迭代法 牛頓迭代法對初值 x0的選取要求比較高。 x* x0 ? x0 ? x0 ? 不滿足迭代條件時，可能導致迭代值遠離根的情況而找不到根或死循環(huán)的情況 70/87 鄭州大學研究生 20222022學年課程 數(shù)值分析 Numerical Analysis ?0)(0?? xf 1000)()(xxfxfx ??? ?01??? xx 開 始 輸 入 x0, ε ,N 1 ? k k+ 1 ? k x1 ? x0 輸出 x1 輸出迭代 失敗標志 結 束 n kN ? n n y 輸出奇 異標志 y y 牛頓迭代法的算法實現(xiàn) 71/87 鄭州大學研究生 20222022學年課程 數(shù)值分析 Numerical Analysis ? 牛頓法的優(yōu)點 ? 牛頓法是目前求解非線性方程 (組 ) 的主要方法 至少二階局部收斂，收斂速度較快，特別是當?shù)c充分靠近精確解時。 弦截 法 牛頓迭代法雖然具有 收斂速度快 的優(yōu)點，但每迭代一次都要計算導數(shù) , 當 比較復雜時 , 不僅每次計算 帶來很多不便，而且還可能十分麻煩，如果用不計算導數(shù)的迭代方法，往往只有線性收斂的速度。 稱之為 多點迭代法 。 弦截 法 弦截法的幾何意義 弦截法也稱割線法 ,其幾何意義是用過曲線上兩點 、 的割線來代替曲線 ,用割線與 x軸交點的橫座標作為方程的近似根 再過 ))(,( 000 xfxP ))(,( 111 xfxP2x P 1 y=f (x) x 0 x 2 x 3 x 1 x* P 3 P 0 P 2 P1點和點 作割線求出 ,再過 P2點和點 作割線求出 ,余此類推，當收斂時可求出滿足精度要求的 ))(,( 222 xfxP3x))(,( 333 xfxP 4xkx76/87 鄭州大學研究生 20222022學年課程 數(shù)值分析 Numerical Analysis 167。 弦截 法 例 用弦截法求方程 在 初始 值鄰近的一個根。 解非線性方程組的迭代解法 1 0 0 1 0 00 0 1 0 02 0 0 2 0 00 0 2 0 0( , ) ( , )( ) ( ) ( , )( , ) ( , )( ) ( ) ( , )f x y f x yx x y y f x yxyf x y f x yx x y y f x yxy???? ? ? ? ?? ??????? ? ? ? ? ?????整 理 得這是 關于 x,y的線性方程組 。 解非線性方程組的迭代解法 000 0 0 0110022( , )001 0 01 0 0 , , ( , ) 0 , ( , ) . xyx x x y y yffxyJ x yffxyxyx x x xy y y y??????? ? ? ???????????? ? ???? ? ??令 如 果則 前 面 線 性 方 程 組 具 有 唯 一 解 則 迭 代 一 步83/87 鄭州大學研究生 20222022學年課程 數(shù)值分析 Numerical Analysis 167。 解非線性方程組的迭代解法 0000( , )1 0 02 0 022 2 3 . 4( , )2 . 7 1 8 2 8 11( , ) 0 . 1 1( , ) 0 . 0 1 8 2 8xxyxyJ x yef x yf x y?? ???? ???? ???????? ?????? ??? ?????????10102 256 28 28 8461 256 = 425 6 846 849x y xx y yx x xy y y? ? ?? ? ???? ? ? ? ??????? ? ? ? ? ???? ? ? ??? ?? ? ? ? ? ? ?? 繼續(xù)做下去，直到 時停止。 FindRoot[{f1[x,y],f2[x,y]},{{x,},{y,}}] {x= ,y= } FindRoot[{f1[x,y],f2[x,y]},{{x,},{y,}}] {x= ,y= } 87/87 鄭州大學研究生 20222022學年課程 數(shù)值分析 Numerical Analysis 非線性方程的解通常叫做方程的根 ,也叫做函數(shù)的零點 ,本章討論了求解非線性方程近似根常用的一些數(shù)值方法 。迭代法是一種逐次逼近的方法 ,起著把根的精確值一步一步算出來的作用