數(shù)值分析(7-2)第2章一元線性方程的解法

第 2章 非 線 性 方 程 求 根 數(shù)值分析 第 2章 一 元 線 性 方 程 的 解 發(fā)1 二分法2 迭代法3 切線法(牛頓法)4 弦截法5 加速迭代法 第 2章 非 線 性 方 程 求 根 數(shù)值分析1二分法 我們已經(jīng)熟悉求解一元一次方程、一元二次方程以及某些特殊類型的高次代數(shù)方程或非線性方程的方法。這些方法都是代數(shù)解法,求出的根是方程的準(zhǔn)確根。但是在許多實際問題中遇到的方程,例如代數(shù)方程 x 3-x-1=0 或超越方程 cos 03x xe 第 2章 非 線 性 方 程 求 根 數(shù)值分析 等等,看上去形式簡單,但卻不易求其準(zhǔn)確根。為此,只能求方程達到一定精度的近似根。 方程的形式很多,我們主要討論一元非線性方程,也即 f(x)=0 (21) 第 2章 非 線 性 方 程 求 根 數(shù)值分析 方程(21)可以有實根,也可以有復(fù)根或者重根等。本章主要討論它的實根的數(shù)值計算問題。 方程根的數(shù)值計算大致可分三個步驟進行: (1) 判定根的存在性。 (2)確定根的分布范圍,即將每一個根用區(qū)間隔離開來。 (3)根的精確化,即根據(jù)根的初始近似值按某種方法逐步精確化,直至滿足預(yù)先要求的精度為止。 第 2章 非 線 性 方 程 求 根 數(shù)值分析 設(shè)f(x)為定義在某區(qū)間上的連續(xù)函數(shù),方程(21)存在實根。雖然方程(21)的根的分布范圍一般比較復(fù)雜,但我們不難將函數(shù)f(x)的定義域分成若干個只含一個實根的區(qū)間。 例如考慮方程 x2-2x-1=0 由圖2.1所示,該方程的一個負(fù)實根在-1和0之間,另一個正實根在2和3之間。 第 2章 非 線 性 方 程 求 根 數(shù)值分析 圖 2.1 第 2章 非 線 性 方 程 求 根 數(shù)值分析 這樣,我們總可以假設(shè)方程(21)(a,b)內(nèi)有且僅有一個單實根x*。由連續(xù)函數(shù)的介值定理知 f(a)f(b)0 若數(shù)值b-a較小,那么我們可在(a,b)上任取一點x0作為方程的初始近似根。 例如,方程 f(x)=x 3-x-1=0 由于f(1)0,f(1.5)0,又f(x)在區(qū)間(1,1.5)上單調(diào)連續(xù),故可知在(1,1.5)內(nèi)有且僅有一個實根。于是可取某個端點或區(qū)間內(nèi)某一個點的值作為根的初始近似值。 第 2章 非 線 性 方 程 求 根 數(shù)值分析 設(shè)函數(shù)f(x)在區(qū)間a,b上單調(diào)連續(xù),且 f(a)f(b)0 則方程(21)在區(qū)間(a,b)內(nèi)有且僅有一個實根x。下面在有根區(qū)間(a,b)內(nèi)介紹二分法的基本思想。 取x0 =(a+b)/2.計算f(a)與f(x0),若 f(a)f(x0)0 則根x (a, x 0 ),令 a1=a,b1=x0 否則x (x0,b),令 a1=x0,b1=b 第 2章 非 線 性 方 程 求 根 數(shù)值分析 圖 2 .2 第 2章 非 線 性 方 程 求 根 數(shù)值分析 如此逐次往復(fù)下去,便得到一系列有根區(qū)間 (a,b),(a1,b1),(a2,b2),(ak,bk), 其中1 11( )21 ( )2k k k k k k kb a b ab a b a 這里a0=a, b0=b顯然有 (22) 當(dāng)k時,區(qū)間(ak,bk)最終必收斂于一點,該點就是所求方程(21)的根x。 第 2章 非 線 性 方 程 求 根 數(shù)值分析 我們把每次二分后的有根區(qū)間(ak,bk)的中點 1( )2k k kx a b 作為所求根x的近似值,這樣獲得一個近似根的序列 x0,x1,x2,xk,該序列必以根x為極限,即lim kk x x 1 11( )2k k k k kx x b a b a (23) 故對于預(yù)先給定的精度,若有1 1k kb a 第 2章 非 線 性 方 程 求 根 數(shù)值分析 則結(jié)果xk就是方程(21)滿足預(yù)給精度的近似根,也即kx x 由式(22)和(23)還可得到誤差估計式為 11 ( )2k kx x b a (24) 對于確定的精度,從式(24)易求得需要二等分的次數(shù)k。 二分法具有簡單和易操作的優(yōu)點。其計算步驟如下,框圖如圖2.3所示。 第 2章 非 線 性 方 程 求 根 數(shù)值分析 1.計算步驟 輸入有根區(qū)間的端點a,b及預(yù)先給定的精度;(a+b)/2 x;若f(a)f(x)0,則x=b,轉(zhuǎn)向;否則x=a,轉(zhuǎn)向。若b-a,則輸出方程滿足精度的根x,結(jié)束;否則轉(zhuǎn)向。 第 2章 非 線 性 方 程 求 根 數(shù)值分析 2. 計算框圖 (見下頁） 例1 求方程 f(x)=x3-x-1=0 在區(qū)間(1,1.5)內(nèi)的根。要求用四位小數(shù)計算,精確到x-2。 解 這里 a=1,b=1.5 取區(qū)間(1,1.5)的中點 0 1(1 1.5) 1.252x 第 2章 非 線 性 方 程 求 根 數(shù)值分析 圖 2.3 第 2章 非 線 性 方 程 求 根 數(shù)值分析 由于f(1)0,f(1.25)0,則令 a1=1.25, b1=1.5 得到新的有根區(qū)間(1.25,1.5) 第 2章 非 線 性 方 程 求 根 數(shù)值分析 表 21 取x 6=1.3242，誤差限| x6-x*|0.5/(27)0.005,故x6即為所求近似根，實際上根x*=1.324717 第 2章 非 線 性 方 程 求 根 數(shù)值分析二分法優(yōu)點：計算簡單，收斂性有保證； 缺點：收斂不夠快，特別是精度要求高時，工作 量大，而且不能夠求復(fù)根及雙重根。 第 2章 非 線 性 方 程 求 根 數(shù)值分析2 迭代法 迭代法的基本思想是:首先將方程(21)改寫成某種等價形式,由等價形式構(gòu)造相應(yīng)的迭代公式,然后選取方程的某個初始近似根x0,代入迭代公式反復(fù)校正根的近似值,直到滿足精度要求為止。迭代法是一種數(shù)值計算中重要的逐次逼近方法。 例如,求方程 x 3-x-1=0 第 2章 非 線 性 方 程 求 根 數(shù)值分析 在x=1.5附近的一個根(用六位有效數(shù)字計算)。 首先將原方程改寫成等價形式3 1x x 用初始近似根 x0=1.5 代入式(25)的右端可得 3 0 1 1.35721x x 第 2章 非 線 性 方 程 求 根 數(shù)值分析 x1與x0相差較大,如果改用x1作為近似根代入式(25)的右端得32 1 1 0,1,2,x x k 第 2章 非 線 性 方 程 求 根 數(shù)值分析 表 22 第 2章 非 線 性 方 程 求 根 數(shù)值分析 對于一般形式的方程(21),首先我們設(shè)法將其化為下列等價形式 x=g(x) (27) 然后按(27)構(gòu)造迭代公式 (28) 從給定的初始近似根x0出發(fā),按迭代公式(28)可以得到一個數(shù)列 x 0,x1,x2,xk, 若這個數(shù)列xk有極限,則迭代公式(28)是收斂的。此時數(shù)列的極限1 ( ), 0,1,2,k kx g x k lim kkx x 第 2章 非 線 性 方 程 求 根 數(shù)值分析 就是原方程(21)的根。 雖然迭代法的基本思想很簡單,但效果并不總是令人滿意的。對于上例,若按方程寫成另一種等價形式 x=x3-1 (29) 建立迭代公式 xk+1=x3k-1, k=0,1,2, 仍取初始值x0=1.5, 則迭代結(jié)果為 x 1=2.375 x2=12.3976 第 2章 非 線 性 方 程 求 根 數(shù)值分析 定理設(shè)方程x=g(x)在(a,b)內(nèi)有根x, g(x)滿足李普希茨(Lipschitz)條件:即對(a,b)內(nèi)任意的x1和x2都有1 2 1 2( ) ( )g x g x q x x q為某個確定的正數(shù),若q1,則方程在(a,b)內(nèi)有唯一的根;且迭代公式 x k+1=g(xk) 對任意初始近似值x0均收斂于方程的根x;還有誤差估計式1 1 01 1 kk k kq qx x x x x xq q (211) 第 2章 非 線 性 方 程 求 根 數(shù)值分析 證 由已知條件知,x為方程x=g(x)的根,即x=g(x)( )( )x g xy g y 設(shè) 也是方程的根,即x y于是,由李普希茨條件得 1 1 01 1 kk k kq qx x x x x xq qq x y 因為q1,所以上式矛盾,故必有x y 第 2章 非 線 性 方 程 求 根 數(shù)值分析 亦即方程在(a,b)內(nèi)有唯一的根。 再考慮迭代公式 x k+1=g(xk) , k=0,1,2, 由李普希茨條件 1 0( ) ( )k kkx x g x g xq x x (212) 第 2章 非 線 性 方 程 求 根 數(shù)值分析 因為q1,當(dāng)k時,qk0,即有 1 0kx x lim kk x x 所以 也就是對任意初始值x0迭代公式收斂。利用李普希茨條件 1 11( )k k k kk kx x gx g xq x x 第 2章 非 線 性 方 程 求 根 數(shù)值分析 對任意正整數(shù)p有 )( |1 |)( |)( | 01 111 11 1121 pxxqq xxqqqq xxqqq xxxxxxxx k kkkpp kkpp kkkkpkpkkpk 第 2章 非 線 性 方 程 求 根 數(shù)值分析 迭代法的幾何意義:把方程(21)求根的問題改寫成(27)變?yōu)榍髷?shù)列xn的極限,實際上是把求根問題轉(zhuǎn)化為求( )y xy g x 第 2章 非 線 性 方 程 求 根 數(shù)值分析 圖 2.4 第 2章 非 線 性 方 程 求 根 數(shù)值分析 迭代過程(28)就是在x軸取初始近似值x0,過x0作y軸的平行線交曲線y=g(x)于p0,p0的橫坐標(biāo)為x0,縱坐標(biāo)為g(x0)(g(x0)=x1),也即 p0(x0,x1) 再在x軸上取x1作為新的近似值,過x1作y軸的平行線交曲線y=g(x)于p1,p1的橫坐標(biāo)為x1,縱坐標(biāo)為 g(x 1)(g(x1)=x2),也即 p1(x1,x2) 而這相當(dāng)于過p0引平行于x軸的直線交y=x于 Q1(x1,x2) 第 2章 非 線 性 方 程 求 根 數(shù)值分析 再過Q1引平行于y軸的直線交曲線y=g(x)于 p1(x1,x2) 仿此可得到點列 p0(x0,x1),p1(x1,x2),p2(x2,x3), 若limlim kk kk p px x 第 2章 非 線 性 方 程 求 根 數(shù)值分析 則迭代法收斂,見圖2.4(a);否則迭代法發(fā)散,見圖2.4(b)。 必須說明兩點: 要驗證g(x)是否滿足李氏條件一般比較困難,若g(x)可微,可用充分條件( ) 1g x q 第 2章 非 線 性 方 程 求 根 數(shù)值分析 來代替。這里q1是非常重要的條件,否則不能保證迭代收斂。 對于收斂的迭代過程,誤差估計式(211)說明迭代值的偏差xk-xk-1相當(dāng)小,就能保證迭代誤差x-xk足夠小。因此在具體計算時常常用條件 xk-x k-1 (215) 來控制迭代過程結(jié)束。 第 2章 非 線 性 方 程 求 根 數(shù)值分析 迭代法的突出優(yōu)點是算法的邏輯結(jié)構(gòu)簡單,且在計算時,中間結(jié)果若有擾動,仍不會影響計算結(jié)果。其計算步驟為: (1)確定方程f(x)=0的等價形式x=g(x),為確保迭代過程的收斂,要求g(x)滿足李普希茨條件(或g(x)q1); (2)選取初始值x0,按公式 x k+1=g(xk), k=0,1,2, 進行迭代; (3)若x k+1-xk,則停止計算,xx k+1。 第 2章 非 線 性 方 程 求 根 數(shù)值分析 例2 求方程 x=e-x 在x=0.5附近的一個根。按五位小數(shù)計算,計算結(jié)果 的精度要求為=10-3。 解 過x=0.5以步長h=0.1計算 f(x)=x-e-x 由于 f(0.5)0,f(0.6)0 故所求的根在區(qū)間(0.5,0.6)內(nèi),且在x=0.5附近 ( ) 0.6 1xe 第 2章 非 線 性 方 程 求 根 數(shù)值分析 圖 2.5 第 2章 非 線 性 方 程 求 根 數(shù)值分析 表 23 第 2章 非 線 性 方 程 求 根 數(shù)值分析 因此用迭代公式 由表可見 kxk ex 110* xx 第 2章 非 線 性 方 程 求 根 數(shù)值分析 最后,我們給出一個說明,在將方程(21)化為等價形式(27)時,g(x)的形式是多種多樣的,選取不當(dāng),迭代公式(28)就不會收斂。最一般的形式可以寫成 x=x+(x)f(x) (216) 這里(x)為任意一個正(或負(fù))的函數(shù)。于是 g(x)=x+(x)f(x) (217) 這樣可根據(jù)式(217)選取(x),使得迭代公式 (28)滿足收斂條件 ( ) 11( ) ( )g x qa x f x 特別當(dāng)取 (218) 第 2章 非 線 性 方 程 求 根 數(shù)值分析 時,由式(216)構(gòu)造的迭代公式為下面要介紹的切線迭代公式;當(dāng)取1 1( ) , 1,2,( ) ( )k kx xa x kf x f x (219) 時,可得到弦截迭代公式。 第 2章 非 線 性 方 程 求 根 數(shù)值分析3 切線法(牛頓法) 切線法是求解方程(21)的一種重要迭代方法。如圖2.6,曲線y=f(x)與x軸的交點x就是方程(21)的根。 第 2章 非 線 性 方 程 求 根 數(shù)值分析 圖 2.6 第 2章 非 線 性 方 程 求 根 數(shù)值分析 與x軸的交點為x k+1,其方程為1( ) ( )( )0 ( ) ( )( )k k kk k k ky f x f x x xf x f x x x 點xk+1滿足該切線方程,即可得到切線迭代公式(或牛頓迭代公式) 1 ( ), 0,1,2,( )kk k kf xx x kf x (220) 第 2章 非 線 性 方 程 求 根 數(shù)值分析 切線法是非線性方程線性化的方法。其計算步驟為: 給出初始近似根x0及精度。 計算 若x1-x0,則轉(zhuǎn)向;否則x1 x0,轉(zhuǎn)向。 輸出滿足精度的根x1,結(jié)束。 切線法的計算框圖見圖2.7。 00 10( )( )f xx xf x 第 2章 非 線 性 方 程 求 根 數(shù)值分析 圖 2.7 第 2章 非 線 性 方 程 求 根 數(shù)值分析 例3 用切線法求方程 xex-1=0 的根(取五位小數(shù)計算)。 取x0=0.5,迭代結(jié)果如表24所示。 1 1 kxkk k kx ex x x 第 2章 非 線 性 方 程 求 根 數(shù)值分析 表 24 第 2章 非 線 性 方 程 求 根 數(shù)值分析 切線迭代公式(220)對應(yīng)著(21)的等價方程( ) ( )( )f xx x g xf x 由于 2( ) ( )( ) ( )f x f xg x f x (221) 若 是方程(21)的一個單實根,即x ( ) 0, ( ) 0( ) 0f x f xg x 第 2章 非 線 性 方 程 求 根 數(shù)值分析 所以,在點 附近切線法收斂,而且收斂速度比較快。 根據(jù)式(221)易得切線迭代公式的收斂條件為 x 2( ) ( )( ) 1 ( )f x f xg x f x 第 2章 非 線 性 方 程 求 根 數(shù)值分析4 弦截法 切線法迭代簡單,收斂速度也較快,但就是需要計算導(dǎo)數(shù)f(x),有時使用會帶來麻煩。這一節(jié)介紹的弦截法就避免了切線法的不足。 第 2章 非 線 性 方 程 求 根 數(shù)值分析 點xk+1滿足該弦的方程,即有11( ) ( )( ) ( )k kk kk kf x f xy f x x xx x 1 11( ) ( )0 ( ) ( )k kk k kk kf x f xf x x xx x 從而可求得弦截迭代公式 1 11( ) ( )( ) ( )kk k k kk kf xx x x xf x f x (223) 第 2章 非 線 性 方 程 求 根 數(shù)值分析 圖 2.8 第 2章 非 線 性 方 程 求 根 數(shù)值分析表 25 第 2章 非 線 性 方 程 求 根 數(shù)值分析 例4 用弦截法解方程 xex-1=0 解 取x0=0.5,x1=0.6作為初始近似根,令 f(x)=x-e-x=0 利用公式(223)得到弦截迭代公式為 11 11 ( )( ) ( )kk kxkk k k kx xk k x ex x x xx x x e 計算結(jié)果見表25。 與切線法的計算結(jié)果比較,可以看出弦截法的收斂速度也是比較快的。 第 2章 非 線 性 方 程 求 根 數(shù)值分析5 加速迭代法 已知方程(21)的近似根xk,按迭代公式(28)可求得x k+1?，F(xiàn)考慮把x k+1作為過渡值,記為 1 ( )k kx g x (224) 1 1k k kx mx nx (225) 第 2章 非 線 性 方 程 求 根 數(shù)值分析 還是設(shè)x為方程(21)的一個實根,即 由式(224)和(226)得到 ( )x g x 11 ( ) ( )( )( )k kk kx x g x g xx x g x x 第 2章 非 線 性 方 程 求 根 數(shù)值分析也即 1 1( )11 11 ,1 1k kk k k x x a x xax x xa aam n xa a 整理得到 于是,只要取 (227) (228) (229) 第 2章 非 線 性 方 程 求 根 數(shù)值分析 這樣可得到加速迭代公式 11 1( )11 1k kk k kx g x ax x xa a (230) 第 2章 非 線 性 方 程 求 根 數(shù)值分析 例5 用加速迭代公式求方程 x=e-x 在x=0.5附近的一個根。 解 因為在x=0.5附近 g(x)=-e-x g(0.5)=-e-0.5-0.6 故加速迭代公式的具體形式為 11 11 0.61.6 1.6kxkk k kx ex x x 第 2章 非 線 性 方 程 求 根 數(shù)值分析表 26 第 2章 非 線 性 方 程 求 根 數(shù)值分析 圖 2.9 第 2章 非 線 性 方 程 求 根 數(shù)值分析 與例2比較,同一例用一般迭代法要迭代十次才能得到滿足精度=10-3的結(jié)果,而這里僅迭代三次便可達到=10-5的高精度結(jié)果。這種加速過程取得的效果極為顯著。 為了避免計算導(dǎo)數(shù)ag(x),下面介紹埃特金(Aitken)迭代方法。它也是一種加速迭代法。 1 11 11( )( ) ( )( )k kk kkx g xx x g x g xa x x (231) 第 2章 非 線 性 方 程 求 根 數(shù)值分析 將式(227)與式(231)聯(lián)立消去a得到11 1k kk kx x x xx x x x 可解出 2 1 11 1 21 11 1 12 ( )2k k kk k kk kk k k kx x xx x x xx xx x x x (232) (233) 第 2章 非 線 性 方 程 求 根 數(shù)值分析 這樣得到埃特金迭代公式)332( 2 )()( )( 11 21111 111 kkk kkkk kk kk xxx xxxx xgx xgx 第 2章 非 線 性 方 程 求 根 數(shù)值分析 例6用埃特金迭代法求 x3-x-1=0 在(1,1.5)內(nèi)的根。 解 前面已經(jīng)提到,迭代公式 x k+1=x3k-1, k=0,1,2, 是發(fā)散的。 現(xiàn)用埃特金算法來求根,其迭代公式為 第 2章 非 線 性 方 程 求 根 數(shù)值分析 21 31 1 2 1 11 1 1 111( )2k kk k k kk k k k kx xx x x xx x x x x 仍取x0=1.5,計算結(jié)果見表27。 第 2章 非 線 性 方 程 求 根 數(shù)值分析表 27