計(jì)算方法 第2章 一元線性方程的解法

1、第2章 一元線性方程的解發(fā) 計(jì)算方法 第2章 一元非線性方程的解法 1 二分法二分法 2 迭代法迭代法 3 切線法切線法(牛頓法牛頓法) 4 弦截法弦截法 5 加速迭代法加速迭代法 第2章 一元線性方程的解發(fā) 計(jì)算方法 y a+1 a -50 O 50 x 50,50 2 )( x eea y a x a x 第2章 一元線性方程的解發(fā) 計(jì)算方法 記筆記記筆記 由題設(shè)知曲線的最底點(diǎn)由題設(shè)知曲線的最底點(diǎn)(0,y(0)(0,y(0)與最高點(diǎn)與最高點(diǎn) (50,y(50)(50,y(50)之間的高度差為之間的高度差為1m,1m,所以應(yīng)有所以應(yīng)有 y(50)=y(0)+1,y(50)=y(0)+1,即即

2、 1 2 )( 5050 a eea a x a y a+1 a -50 O 50 x 要計(jì)算電纜的長(zhǎng)度要計(jì)算電纜的長(zhǎng)度, ,必須必須 先求出上述方程中先求出上述方程中 的的a ,a ,由于它是關(guān)于由于它是關(guān)于a a的非線性方程的非線性方程, ,沒(méi)有現(xiàn)成的公沒(méi)有現(xiàn)成的公 式可用式可用,因此只能尋求其他解法因此只能尋求其他解法. . 第2章 一元線性方程的解發(fā) 計(jì)算方法 在實(shí)際應(yīng)用中有許多非線性方程的例子，例如 求求f(xf(x)=0)=0的根的根 （1）在光的衍射理論（the theory of diffraction of light)中,我們 需要求x-tanx=0的根 （2）在行星軌道（

3、 planetary orbits）的計(jì)算中,對(duì)任意的a和b， 我們需要求x-asinx=b的根 （3）在數(shù)學(xué)中，需要求n次多項(xiàng)式xn + a1 xn-1+.+an-1 x + an 0 的根 第2章 一元線性方程的解發(fā) 計(jì)算方法 滿(mǎn)足方程的滿(mǎn)足方程的x值通常叫做值通常叫做方程的根或解方程的根或解， 也叫函數(shù)也叫函數(shù)f( (x)=0)=0的零點(diǎn)。的零點(diǎn)。 非線性方程的一般形式：非線性方程的一般形式：f(x)=0 這里這里f( (x) )是單變量是單變量x 的函數(shù)。的函數(shù)。 u 代數(shù)多項(xiàng)式：代數(shù)多項(xiàng)式： f( (x)=)=a0+a1x+anxn (an0) cos0 3 x x e 非線性方程可

4、分為兩種：非線性方程可分為兩種： u 超越函數(shù)超越函數(shù)，即不能表示為上述形式的函數(shù)。，即不能表示為上述形式的函數(shù)。 第2章 一元線性方程的解發(fā) 計(jì)算方法 l 遠(yuǎn)在公元前遠(yuǎn)在公元前1700年的古巴比倫人就已有關(guān)于一、二次方程的年的古巴比倫人就已有關(guān)于一、二次方程的 解法。解法。 l 1535年意大利數(shù)學(xué)家坦特格里亞年意大利數(shù)學(xué)家坦特格里亞(TorTaglia)發(fā)現(xiàn)了三次方程發(fā)現(xiàn)了三次方程 的解法，卡當(dāng)?shù)慕夥ǎó?dāng)(HCardano)從他那里得到了這種解法，于從他那里得到了這種解法，于 1545年在其名著年在其名著大法大法中公布了三次方程的公式解，稱(chēng)為中公布了三次方程的公式解，稱(chēng)為 卡當(dāng)算法?？ó?dāng)

5、算法。 l 后來(lái)卡當(dāng)?shù)膶W(xué)生弗瑞里后來(lái)卡當(dāng)?shù)膶W(xué)生弗瑞里(Ferrari)又提出了四次方程的解法。又提出了四次方程的解法。 第2章 一元線性方程的解發(fā) 計(jì)算方法 l 1799年，高斯證明了代數(shù)方程必有一個(gè)實(shí)根或復(fù)根的定理，年，高斯證明了代數(shù)方程必有一個(gè)實(shí)根或復(fù)根的定理， 稱(chēng)此為代數(shù)基本定理，并由此可以立刻推理稱(chēng)此為代數(shù)基本定理，并由此可以立刻推理n次代數(shù)方程必次代數(shù)方程必 有有n個(gè)實(shí)根或復(fù)根。個(gè)實(shí)根或復(fù)根。 l 但求解五次方程時(shí)未能如愿但求解五次方程時(shí)未能如愿,開(kāi)始意識(shí)到有潛藏其中的奧妙開(kāi)始意識(shí)到有潛藏其中的奧妙, 用現(xiàn)代術(shù)語(yǔ)表示就是置換群理論問(wèn)題。用現(xiàn)代術(shù)語(yǔ)表示就是置換群理論問(wèn)題。 l 在繼續(xù)探

6、索在繼續(xù)探索5次以上方程解的艱難歷程中，第一個(gè)重大突破次以上方程解的艱難歷程中，第一個(gè)重大突破 的是挪威數(shù)學(xué)家阿貝爾的是挪威數(shù)學(xué)家阿貝爾(NAbel1802-1829) 1824年阿貝爾發(fā)年阿貝爾發(fā) 表了表了“五次方程代數(shù)解法不可能存在五次方程代數(shù)解法不可能存在”的論文，但并未受的論文，但并未受 到重視，連數(shù)學(xué)大師高斯也未理解這項(xiàng)成果的重要意義。到重視，連數(shù)學(xué)大師高斯也未理解這項(xiàng)成果的重要意義。 第2章 一元線性方程的解發(fā) 計(jì)算方法 l 十四年后，法國(guó)數(shù)學(xué)家劉維爾十四年后，法國(guó)數(shù)學(xué)家劉維爾(JLiouville)整理并發(fā)表了整理并發(fā)表了 伽羅華的遺作，人們才意識(shí)到這項(xiàng)近代數(shù)學(xué)發(fā)展史上的重伽羅華

7、的遺作，人們才意識(shí)到這項(xiàng)近代數(shù)學(xué)發(fā)展史上的重 要成果的寶貴。要成果的寶貴。 l 38年后，即年后，即1870年，法國(guó)數(shù)學(xué)家若當(dāng)年，法國(guó)數(shù)學(xué)家若當(dāng)(CJordan)在專(zhuān)著在專(zhuān)著 論置換與代數(shù)方程論置換與代數(shù)方程中闡發(fā)了伽羅華的思想，一門(mén)現(xiàn)代中闡發(fā)了伽羅華的思想，一門(mén)現(xiàn)代 數(shù)學(xué)的分支數(shù)學(xué)的分支群論誕生了。群論誕生了。 l 在前幾個(gè)世紀(jì)中，曾開(kāi)發(fā)出一些求解代數(shù)方程的有效算法，在前幾個(gè)世紀(jì)中，曾開(kāi)發(fā)出一些求解代數(shù)方程的有效算法， 它們構(gòu)成了數(shù)值分析中的古典算法。至于超越方程則不存它們構(gòu)成了數(shù)值分析中的古典算法。至于超越方程則不存 在一般的求根方式。在一般的求根方式。 第2章 一元線性方程的解發(fā) 計(jì)算方

8、法 方程根的數(shù)值計(jì)算步驟方程根的數(shù)值計(jì)算步驟 u判斷根的存在判斷根的存在 u確定根的分布范圍確定根的分布范圍 u根的精確化根的精確化 第2章 一元線性方程的解發(fā) 計(jì)算方法 根的存在定理根的存在定理( (零點(diǎn)定理零點(diǎn)定理) )： f(x)為為 a,b 上的連續(xù)函數(shù)，若上的連續(xù)函數(shù)，若 f(a)f(b)0 0，則，則 a,b 中至少有一個(gè)實(shí)根。如果中至少有一個(gè)實(shí)根。如果f(x)在在 a,b 上還是單上還是單 調(diào)遞增或遞減的，則調(diào)遞增或遞減的，則f(x)=0 0僅有一個(gè)實(shí)根。僅有一個(gè)實(shí)根。 第2章 一元線性方程的解發(fā) 計(jì)算方法 根的分布范圍根的分布范圍: : 在用近似方法時(shí)，需要知道方程的根所在區(qū)間

9、。在用近似方法時(shí)，需要知道方程的根所在區(qū)間。 若區(qū)間若區(qū)間 a,b 含有方程含有方程f(x)=0 0的根，則稱(chēng)的根，則稱(chēng) a,b 為為f(x)=0 的的有根區(qū)間有根區(qū)間；若區(qū)間若區(qū)間 a,b 僅含方程僅含方程f(x)= 0 0的一個(gè)根，的一個(gè)根， 則稱(chēng)則稱(chēng) a,b 為為f(x)= 0的一個(gè)的一個(gè)隔根區(qū)間。隔根區(qū)間。求隔根區(qū)間有求隔根區(qū)間有 兩種方法：兩種方法： 第2章 一元線性方程的解發(fā) 計(jì)算方法 例如，求方程例如，求方程3 3x-1-1-cosx=0 0的隔根區(qū)間。的隔根區(qū)間。 將方程等價(jià)變形為將方程等價(jià)變形為3 3x-1=-1=cosx ，易見(jiàn)，易見(jiàn)y=3 3x-1-1與與 y=cosx的

10、圖像只有一個(gè)交點(diǎn)位于的圖像只有一個(gè)交點(diǎn)位于0.50.5，11內(nèi)內(nèi)。 畫(huà)出畫(huà)出y= =f( (x) )的略圖，從而看出曲線與的略圖，從而看出曲線與x軸交點(diǎn)軸交點(diǎn) 的大致位置。也可將的大致位置。也可將f( (x)=0)=0等價(jià)變形為等價(jià)變形為g1 1( (x)=)=g2 2( (x) ) 的形式，的形式，y= =g1 1( (x) )與與y= =g2 2( (x) )兩曲線交點(diǎn)的橫坐標(biāo)所兩曲線交點(diǎn)的橫坐標(biāo)所 在的子區(qū)間即為含根區(qū)間。在的子區(qū)間即為含根區(qū)間。 (1)描圖法描圖法 第2章 一元線性方程的解發(fā) 計(jì)算方法 (2)逐步搜索法逐步搜索法 運(yùn)用零點(diǎn)定理可以得到如下逐步搜索法：運(yùn)用零點(diǎn)定理可以得到

11、如下逐步搜索法： 先確定方程先確定方程f( (x)=0)=0的所有實(shí)根所在的區(qū)間的所有實(shí)根所在的區(qū)間 為為 a, ,b,從從x0 0= =a 出發(fā)出發(fā), ,以步長(zhǎng)以步長(zhǎng) h=( (b-a) )/n 其中其中n是正整數(shù)，在是正整數(shù)，在 a, ,b 內(nèi)取定節(jié)點(diǎn)：內(nèi)取定節(jié)點(diǎn)： xi=x0 0ih ( (i=0,1,2=0,1,2，n) ) 計(jì)算計(jì)算f( (xi) )的值的值, ,依據(jù)函數(shù)值異號(hào)及實(shí)根的個(gè)數(shù)確依據(jù)函數(shù)值異號(hào)及實(shí)根的個(gè)數(shù)確 定隔根區(qū)間定隔根區(qū)間, ,通過(guò)調(diào)整步長(zhǎng)，總可找到所有隔根通過(guò)調(diào)整步長(zhǎng)，總可找到所有隔根 區(qū)間。區(qū)間。 第2章 一元線性方程的解發(fā) 計(jì)算方法 例例1 1 方程方程f(x

12、f(x)=x)=x3 3-x-1=0 -x-1=0 確定其有根區(qū)間確定其有根區(qū)間 解：用試湊的方法，不難發(fā)現(xiàn)解：用試湊的方法，不難發(fā)現(xiàn) f(0)0f(0)0 在區(qū)間（在區(qū)間（0 0，2 2）內(nèi)至少有一個(gè)實(shí)根）內(nèi)至少有一個(gè)實(shí)根 設(shè)從設(shè)從x=0 x=0出發(fā)出發(fā), ,取取h=0.5h=0.5為步長(zhǎng)向右進(jìn)行根的為步長(zhǎng)向右進(jìn)行根的 搜索搜索, ,列表如下列表如下 x x f(xf(x) ) 0 0.5 1.0 1.5 20 0.5 1.0 1.5 2 + + + + 可以看出，在可以看出，在1.0,1.51.0,1.5內(nèi)必有一根內(nèi)必有一根 第2章 一元線性方程的解發(fā) 計(jì)算方法 1二分法二分法 設(shè)函數(shù)設(shè)函

13、數(shù)f(x)在區(qū)間在區(qū)間a,b上單調(diào)連續(xù)上單調(diào)連續(xù),且且 f(a)f(b)0 則方程在區(qū)間則方程在區(qū)間(a,b)內(nèi)有且僅有一個(gè)實(shí)根內(nèi)有且僅有一個(gè)實(shí)根x。 下面在有根區(qū)間下面在有根區(qū)間(a,b)內(nèi)介紹二分法的基本思想。內(nèi)介紹二分法的基本思想。 第2章 一元線性方程的解發(fā) 計(jì)算方法 x0= (a+b) 2 若若: f(a)f(x0)0 則，令則，令 a1=a，b1=x0 否則，令否則，令 a1=x0，b1=b 第2章 一元線性方程的解發(fā) 計(jì)算方法 如此逐次往復(fù)下去,便得到一系列有根區(qū)間 (a,b),(a1,b1),(a2,b2),(ak,bk), 其中 11 1 () 2 1 () 2 kkkk k

14、k k baba baba 這里a0=a, b0=b顯然有 當(dāng)k時(shí),區(qū)間(ak,bk)最終必收斂于一點(diǎn),該點(diǎn)就 是所求方程的根x。 第2章 一元線性方程的解發(fā) 計(jì)算方法 a b x0 x1 a b 什么時(shí)候停止？ x* k xx 第2章 一元線性方程的解發(fā) 計(jì)算方法 誤差誤差 分析：分析： 第第1步產(chǎn)生的步產(chǎn)生的 0 2 a b x 有誤差有誤差 0 2 b a |x x | 第第 k 步產(chǎn)生的步產(chǎn)生的 xk 有誤差有誤差 1 22 kk k k baba | xx| 對(duì)于給定的精度對(duì)于給定的精度 ,可估計(jì)二分法所需的步數(shù)可估計(jì)二分法所需的步數(shù) k ： 1 lnln 1 2ln 2 k ba

15、ba k 第2章 一元線性方程的解發(fā) 計(jì)算方法 計(jì)算步驟 ： 輸入有根區(qū)間的端點(diǎn)a、b及預(yù)先給定的精度; (a+b)/2 x; 若f(a)f(x)0，則x b，轉(zhuǎn)向;否則x a，轉(zhuǎn)向。 若b-a,則輸出方程滿(mǎn)足精度的根x，結(jié)束；否則轉(zhuǎn)向。 二分法具有簡(jiǎn)單和易操作的優(yōu)點(diǎn)。 第2章 一元線性方程的解發(fā) 計(jì)算方法 第2章 一元線性方程的解發(fā) 計(jì)算方法 例1 求方程 f(x)=x3-x-1=0 在區(qū)間(1,1.5)內(nèi)的根。要求用四位小數(shù)計(jì)算,精確到 10-2。 解： 這里 a=1，b=1.5 取區(qū)間(1，1.5)的中點(diǎn) 0 1 (1 1.5)1.25 2 x 第2章 一元線性方程的解發(fā) 計(jì)算方法 由于

16、f（1）0，f（1.5）0 f(1.25)0,則令 a1=1.25, b1=1.5 得到新的有根區(qū)間(1.25,1.5) 第2章 一元線性方程的解發(fā) 計(jì)算方法 2 迭代法迭代法 迭代法的基本思想是: 首先將方程f(x)改寫(xiě)成某種等價(jià)形式，由等價(jià)形式構(gòu)造 相應(yīng)的迭代公式，然后選取方程的某個(gè)初始近似根x0， 代入迭代公式反復(fù)校正根的近似值，直到滿(mǎn)足精度要 求為止。迭代法是一種數(shù)值計(jì)算中重要的逐次逼近方 法。 f (x) = x- g (x) =0 x = g (x) 等價(jià)變換等價(jià)變換 f (x) 的根的根g (x) 的不動(dòng)點(diǎn)的不動(dòng)點(diǎn) 第2章 一元線性方程的解發(fā) 計(jì)算方法 例：求方程 x3-x-1=

17、0 在x=1.5附近的一個(gè)根(用六位有效數(shù)字計(jì)算)。 第2章 一元線性方程的解發(fā) 計(jì)算方法 首先將原方程改寫(xiě)成等價(jià)形式 3 1xx 用初始近似根 x0=1.5 代入上式的右端可得 3 0 11.35721xx 3 21 10,1,2,xxk 第2章 一元線性方程的解發(fā) 計(jì)算方法 第2章 一元線性方程的解發(fā) 計(jì)算方法 雖然迭代法的基本思想很簡(jiǎn)單，但效果并不總是令人 滿(mǎn)意的。對(duì)于上例，若按方程寫(xiě)成另一種等價(jià)形式 x=x3-1 建立迭代公式 xk+1=x3k-1, k=0,1,2, 仍取初始值x0=1.5, 則迭代結(jié)果為 x1=2.375 x2=12.3976 第2章 一元線性方程的解發(fā) 計(jì)算方法

18、幾何意義幾何意義: ( )yxyg x和的交點(diǎn) x = g (x) 第2章 一元線性方程的解發(fā) 計(jì)算方法 x y y = x x y y = x x y y = x x y y = x x*x* x*x* y=g(x) y=g(x) y=g(x) y=(x) x0 p0 x1 p1 x0 p0 x1 p1 x0 p0 x1 p1 x0 p0 x1 p1 第2章 一元線性方程的解發(fā) 計(jì)算方法 同樣的方程同樣的方程 不同的迭代格式不同的迭代格式 有不同的結(jié)果有不同的結(jié)果 什么形式的迭代什么形式的迭代 法能夠收斂呢法能夠收斂呢? ? 如何構(gòu)造迭代函如何構(gòu)造迭代函 數(shù)呢?cái)?shù)呢? ? 第2章 一元線性方程

19、的解發(fā) 計(jì)算方法 若從任何可取的初值出發(fā)都能保證收斂，則稱(chēng)它若從任何可取的初值出發(fā)都能保證收斂，則稱(chēng)它 為為大范圍收斂大范圍收斂。如若為了保證收斂性必須選取初值充。如若為了保證收斂性必須選取初值充 分接近于所要求的根，則稱(chēng)它為分接近于所要求的根，則稱(chēng)它為局部收斂局部收斂。 通常局部收斂方法比大范圍收斂方法收斂得快。通常局部收斂方法比大范圍收斂方法收斂得快。 因此，一個(gè)合理的算法是先用一種大范圍收斂方法求因此，一個(gè)合理的算法是先用一種大范圍收斂方法求 得接近于根的近似值（如對(duì)分法），再以其作為新的得接近于根的近似值（如對(duì)分法），再以其作為新的 初值使用局部收斂法（如迭代法）。初值使用局部收斂法（

20、如迭代法）。 這里討論迭代法的收斂性時(shí)，均指的是局部收斂這里討論迭代法的收斂性時(shí)，均指的是局部收斂 性。性。 第2章 一元線性方程的解發(fā) 計(jì)算方法 1212 ()()g xg xq xx 1. 則方程在則方程在(a,b)內(nèi)有唯一的根；內(nèi)有唯一的根； 110 11 k kkk qq xxxxxx qq 定理定理/收斂定理收斂定理/壓縮映像原理壓縮映像原理 l 設(shè)方程設(shè)方程x=g(x)在在(a,b)內(nèi)有根內(nèi)有根x* l g(x)滿(mǎn)足李普希茨滿(mǎn)足李普希茨(Lipschitz)條件條件:即對(duì)即對(duì)(a,b)內(nèi)任意的內(nèi)任意的x1 和和x2都有：都有： q為某個(gè)確定的正數(shù)，為某個(gè)確定的正數(shù)，q1 條件條件

21、結(jié)果結(jié)果 3. 還有誤差估計(jì)式還有誤差估計(jì)式 2. 且迭代公式且迭代公式 xk+1=g(xk) 對(duì)對(duì)任意任意初始近似值初始近似值x0均收斂于均收斂于 方程的根方程的根x； 第2章 一元線性方程的解發(fā) 計(jì)算方法 由已知條件知，由已知條件知，x*為方程為方程x=g(x)的根，即的根，即x*=g(x*) () () xg x yg y 設(shè)設(shè) 也是方程的根，即也是方程的根，即xy 于是，由李普希茨條件得于是，由李普希茨條件得 ()()xyg xg yq xy 因?yàn)橐驗(yàn)閝1，所以上式矛盾，故必有，所以上式矛盾，故必有 xy 證 1. 有唯一根 第2章 一元線性方程的解發(fā) 計(jì)算方法 考慮迭代公式 x k+

22、1=g(xk) , k=0,1,2, 由李普希茨條件 1 0 ()() kk k xxg xg x q xx 證 2. 迭代公式收斂 因?yàn)閝1，當(dāng)k時(shí)，qk0，即有 1 0 k xx lim k k xx 所以 第2章 一元線性方程的解發(fā) 計(jì)算方法 證 3. 誤差 |xk-x*|= |xk-xk-1| = |g(xk-1)-g(xk-2)| |xk-x*| q/(1- q)|xk-xk-1| |xk-x*| qk/(1- q) |x1-x0| 可用可用 來(lái)來(lái) 控制收斂精度控制收斂精度 | 1kk xx 1212 ()()g xg xq xx 李普希茨李普希茨(Lipschitz)條件條件 |g

23、(xk-1)-g(x*)| q |xk-1-x*| q (|xk-xk-1|+|xk-x*|) q |x k-1-xk-2| qk-1|x1-x0| 第2章 一元線性方程的解發(fā) 計(jì)算方法 要驗(yàn)證要驗(yàn)證g(x)是否滿(mǎn)足李氏條件一般比較困難，若是否滿(mǎn)足李氏條件一般比較困難，若g(x)可可 微，可用條件微，可用條件 來(lái)判斷迭代公式是否收斂。來(lái)判斷迭代公式是否收斂。 ( )1g xq 必須說(shuō)明兩點(diǎn)必須說(shuō)明兩點(diǎn): 對(duì)于收斂的迭代過(guò)程，誤差估計(jì)式說(shuō)明迭代值的偏 差xk-xk-1相當(dāng)小，就能保證迭代誤差x-xk足夠 小。因此在具體計(jì)算時(shí)常常用條件 xk-xk-1 來(lái)控制迭代過(guò)程結(jié)束。 第2章 一元線性方程的

24、解發(fā) 計(jì)算方法 例例 求方程 x=e-x 在x=0.5附近的一個(gè)根。按五位小數(shù)計(jì)算,計(jì)算結(jié)果 的精度要求為=10-3。 ()0.61 x e 解 過(guò)x=0.5以步長(zhǎng)h=0.1計(jì)算 f(x)=x-e-x 由于 f(0.5)0，f(0.6)0 故所求的根在區(qū)間(0.5,0.6)內(nèi),且在x=0.5附近 第2章 一元線性方程的解發(fā) 計(jì)算方法 10 xx 10 xx 01 ()g xx 開(kāi)始開(kāi)始 結(jié)束結(jié)束 0, x輸入輸入 1 x輸出輸出 F T 第2章 一元線性方程的解發(fā) 計(jì)算方法 g(x)=e-x 第2章 一元線性方程的解發(fā) 計(jì)算方法 因此用迭代公式 由表可見(jiàn) 1 k x k xe 10 x xx

25、xe 為方程 的根 第2章 一元線性方程的解發(fā) 計(jì)算方法 最一般的形式可以寫(xiě)成 x=x+(x)f(x) 這里(x)為任意一個(gè)正(或負(fù))的函數(shù)。于是 g(x)=x+(x)f(x) 這樣只要合理選取(x),使得迭代公式滿(mǎn)足收斂條件 ( )1g xq 如何構(gòu)造迭代函數(shù)如何構(gòu)造迭代函數(shù)g(x)呢呢? ? 第2章 一元線性方程的解發(fā) 計(jì)算方法 切線迭代公式：切線迭代公式： 1 1 ( ),1,2, ( )() k k xx a xk f xf x 弦截迭代公式：弦截迭代公式： 1 ( ) ( ) a x fx 第2章 一元線性方程的解發(fā) 計(jì)算方法 設(shè)x * 是方程f (x ) = 0的根，又x0 為x

26、* 附近的一個(gè) 值 ，將f (x ) 在x0附近做泰勒展式 之間和在其中 0 2 0000 )()( 2 1 )()()()( xx fxxxfxxxfxf * xx )()( 2 1 )()()()(0 2 0 * 00 * 0 * fxxxfxxxfxf 3 切線法切線法(牛頓法牛頓法) 令 ，則 第2章 一元線性方程的解發(fā) 計(jì)算方法 去掉 的二次項(xiàng)，有： 0 * xx 0)()()( 000 * 0 xfxxfxxf * 0 0 0 () () f x xx fx 1 x 即 以x1代替x0重復(fù)以上的過(guò)程，繼續(xù)下去得： 第2章 一元線性方程的解發(fā) 計(jì)算方法 ,.1 , 0 )( )( 1

27、 n xf xf xx n n nn 以此產(chǎn)生的序列以此產(chǎn)生的序列xn得到得到f(x)=0的近似解，稱(chēng)為的近似解，稱(chēng)為 Newton法，又叫切線法。法，又叫切線法。 第2章 一元線性方程的解發(fā) 計(jì)算方法 牛頓法的幾何意義牛頓法的幾何意義 x y x* x0 0 10 0 () () fx xx fx x 1 x 2 000 ()()()yf xfxxx 1 21 1 () () fx xx fx 牛頓法也稱(chēng)為切線法牛頓法也稱(chēng)為切線法 ,.1 , 0 )( )( 1 n xf xf xx n n nn ( )f x 第2章 一元線性方程的解發(fā) 計(jì)算方法 Newton迭代的方程為：迭代的方程為：

28、)( )( )(0)( xf xf xxxxf 所以所以 2)( )( )( ) )( )( ()( xf xfxf xf xf xx 若若f(x)在在x*處為單根，則處為單根，則( *)0,( *)0,( *)0f xfxx 所以，迭代格式收斂。所以，迭代格式收斂。 Newton迭代法的收斂性迭代法的收斂性 第2章 一元線性方程的解發(fā) 計(jì)算方法 Newtons Method 收斂性依賴(lài)于收斂性依賴(lài)于x0 的選取。的選取。 x* x0 x0 x0 第2章 一元線性方程的解發(fā) 計(jì)算方法 (1) (1) 選定初值選定初值x0 、 (3) (3) 按迭代公式得新的近似值按迭代公式得新的近似值xk+1

29、 (4) (4) 判定誤差判定誤差，決定是否決定是否終止迭代。終止迭代。 (2) (2) 計(jì)算計(jì)算f (x) Newton迭代法的步驟迭代法的步驟 第2章 一元線性方程的解發(fā) 計(jì)算方法 Newton迭代法的步驟迭代法的步驟 10 xx 10 xx 0 10 () () f x xx fx 結(jié)束結(jié)束 1,2,kN I 輸出輸出 F 0, , xN 輸入輸入 0 ()0fx 1I 0I 1I 11 ,( ),xf xk 輸出輸出 00 ( ),( )f xf x求求 kN F T T 允許精度允許精度 最大迭代最大迭代 次數(shù)次數(shù) 第2章 一元線性方程的解發(fā) 計(jì)算方法 例例 用用NewtonNewt

30、on迭代法求方程迭代法求方程xexex x-1=0-1=0在在0.50.5附近的根附近的根, , 精度要求精度要求 =10=10-5 -5. . 解：解：NewtonNewton迭代格式為迭代格式為 , 2 , 1 , 0, 1 1 1 k x ex x exe ex xx k x k k x k x x k kk k kk k kxk(xk)|xk-xk-1| 0 1 2 3 4 0.5 0.57102044 0.56715557 0.56714329 0.56714329 -0.17563936 0.01074751 0.00003393 0.0000000003 0.0000000003

31、 0.07102044 0.00386487 0.00001228 0.00000000 第2章 一元線性方程的解發(fā) 計(jì)算方法 1 1、優(yōu)點(diǎn)：牛頓迭代法具有平方收斂的速度，所以在迭代過(guò)、優(yōu)點(diǎn)：牛頓迭代法具有平方收斂的速度，所以在迭代過(guò) 程中只要迭代幾次就會(huì)得到很精確的解。這是牛頓迭代法比程中只要迭代幾次就會(huì)得到很精確的解。這是牛頓迭代法比 簡(jiǎn)單迭代法優(yōu)越的地方。簡(jiǎn)單迭代法優(yōu)越的地方。 2 2、缺點(diǎn)：選定的初值要接近方程的解，否則有可能得不到、缺點(diǎn)：選定的初值要接近方程的解，否則有可能得不到 收斂的結(jié)果。再者，牛頓迭代法計(jì)算量比較大。因每次迭代收斂的結(jié)果。再者，牛頓迭代法計(jì)算量比較大。因每次迭代

32、 除計(jì)算函數(shù)值外還要計(jì)算微商值。除計(jì)算函數(shù)值外還要計(jì)算微商值。 第2章 一元線性方程的解發(fā) 計(jì)算方法 將將Newton迭代中的導(dǎo)數(shù)，用差商代替，有格式迭代中的導(dǎo)數(shù)，用差商代替，有格式 1 1 1 () ()() k kk kk kk f x xx f xf x xx 是是2步格式。收斂速度比步格式。收斂速度比Newton迭代慢迭代慢 x0 x1 切線切線 割線割線 4 弦截法弦截法 x2x2 第2章 一元線性方程的解發(fā) 計(jì)算方法 點(diǎn)xk+1是滿(mǎn)足該弦的方程的點(diǎn)，即有 1 1 ()() ()() kk kk kk f xf x yf xxx xx 1 1 1 ()() 0()() kk kkk

33、kk f xf x f xxx xx 從而可求得弦截迭代公式 11 1 () () ()() k kkkk kk f x xxxx f xf x (223) 第2章 一元線性方程的解發(fā) 計(jì)算方法 例4 用弦截法解方程 xex-1=0 解 取x0=0.5,x1=0.6作為初始近似根,令 f(x)=x-e-x=0 利用上面公式得到弦截迭代公式為 1 11 1 () ()() k kk x k kkkk xx kk xe xxxx xxxe 計(jì)算結(jié)果見(jiàn)下頁(yè)表。 可以看出弦截法的收斂速度也是比較快的。 第2章 一元線性方程的解發(fā) 計(jì)算方法 第2章 一元線性方程的解發(fā) 計(jì)算方法 5 加速迭代法加速迭代法

34、 已知方程的近似根xk，按迭代公式可求得xk+1?，F(xiàn) 考慮把xk+1作為過(guò)渡值,記為 1 () kk xg x 11kkk xmxnx 第2章 一元線性方程的解發(fā) 計(jì)算方法 仍然設(shè)仍然設(shè)x*為方程的根，即為方程的根，即 由迭代公式有：由迭代公式有： ()xg x 1 1 ()() ( )() kk kk xxg xg x xxgxx a 也即也即 1 () kk xxa xx 第2章 一元線性方程的解發(fā) 計(jì)算方法 1 1 11 1 , 11 kk a xxx aa a mn aa 整理得到 于是,只要取 這樣可得到加速迭代公式 1 11 () 1 11 kk kkk xg x a xxx aa

35、 第2章 一元線性方程的解發(fā) 計(jì)算方法 例例5 用加速迭代公式求方程 x=e-x 在x=0.5附近的一個(gè)根。 1 11 10.6 1.61.6 k x k kkk xe xxx 解 因?yàn)樵趚=0.5附近 g(x)=-e-x g(0.5)=-e-0.5-0.6 故加速迭代公式的具體形式為： 第2章 一元線性方程的解發(fā) 計(jì)算方法 第2章 一元線性方程的解發(fā) 計(jì)算方法 與例2（P35）比較： 例2：迭代十次 滿(mǎn)足精度=10-3 例5：迭代三次 滿(mǎn)足精度=10-5 第2章 一元線性方程的解發(fā) 計(jì)算方法 上述迭代法需要計(jì)算導(dǎo)數(shù)ag(x)， 下面介紹埃特金(Aitken)迭代方法。它也是一種加速迭代法。

36、11 11 1 () ()() () kk kk k xg x xxg xg x a xx 1 () kk xxa xx 埃特金迭代法 第2章 一元線性方程的解發(fā) 計(jì)算方法 將上兩式聯(lián)立消去a得到 可解出 1 11 kk kk xxxx xxxx 11 11 2 11 1 11 2 () 2 kkk kkk kk k kkk x xx x xxx xx x xxx 第2章 一元線性方程的解發(fā) 計(jì)算方法 這樣得到埃特金迭代公式 1 11 2 11 11 11 () () () 2 kk kk kk kk kkk xg x xg x xx xx xxx 第2章 一元線性方程的解發(fā) 計(jì)算方法 例例6

37、 用埃特金迭代法求 x3-x-1=0 在(1,1.5)內(nèi)的根。 解解 前面已經(jīng)提到,迭代公式 xk+1=x3k-1, k=0,1,2, 是發(fā)散的。 現(xiàn)用埃特金算法來(lái)求根,其迭代公式為 第2章 一元線性方程的解發(fā) 計(jì)算方法 仍取x0=1.5,計(jì)算結(jié)果見(jiàn)下表。 3 1 3 11 2 11 11 11 1 1 () 2 kk kk kk kk kkk xx xx xx xx xxx 第2章 一元線性方程的解發(fā) 計(jì)算方法 第2章 一元線性方程的解發(fā) 計(jì)算方法 定義定義2.2.1 設(shè)序列 收斂到 ，若有實(shí)數(shù) 和非零常數(shù)C，使得 其中 ， ，則稱(chēng)該序列是p 階收 斂的，C 稱(chēng)為漸進(jìn)誤差常數(shù)。 0n x *

38、 x 1p C e e p n n n 1 lim * xxe nn 迭代法收斂的階迭代法收斂的階 第2章 一元線性方程的解發(fā) 計(jì)算方法 當(dāng)p=1時(shí)，稱(chēng)為線性收斂； 當(dāng)p1時(shí)，稱(chēng)為超線性收斂； 當(dāng)p=2時(shí)，稱(chēng)為平方收斂或二次收斂。 第2章 一元線性方程的解發(fā) 計(jì)算方法 一般迭代法是線性收斂一般迭代法是線性收斂 線性收斂到 。 0)( )()( limlim * * * 1 n x xx xx e e n n n n n 因?yàn)?0 n x所以 * x 第2章 一元線性方程的解發(fā) 計(jì)算方法 迭代法的收斂速度迭代法的收斂速度 )(0)( 0)(.)()( )(,)( * 0 10 *)( *) 1(* * xpx xxxx xxx xxxx n kk p p D 階收斂速度收斂到，以列 產(chǎn)生的序，由，則而 鄰域內(nèi)連續(xù)，且有 的不動(dòng)點(diǎn)是設(shè) 定理定理 )(p 在x*的 第2章 一元線性方程的解發(fā) 計(jì)算方法 證：證： ( ) 0 ( ) ()( *)(*) ! p P kk xxxx P xx 其中 在 和 之間 ! )( )( lim *)( * * 1 p x xx xx p p n n n 將 (x ) 在x*附近做泰勒展式： 因?yàn)橛校?1 ( )