1、 y=x y y=)(x y=x 1)(0*x 0)(1*x P0 P2P* Q1 Q2 x1 x0 x2 x* x y x0 x x1 x2 x3 x* y=)(x)(x P* P1 數(shù)值分析數(shù)值分析Numerical Analysis第七章非線性方程（組）的數(shù)值解法鄭州大學(xué)研究生課程鄭州大學(xué)研究生課程 （2014-20152014-2015學(xué)年第一學(xué)期）學(xué)年第一學(xué)期） 2/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis第七章 非線性方程（組）的數(shù)值解法 7.1 7.1 引言引言7.2 7.2 二分區(qū)間法二分區(qū)間法7.3 7.3 迭代法及其加速

2、迭代法及其加速7.4 7.4 牛頓迭代法牛頓迭代法7.5 7.5 弦截法弦截法7.6 7.6 解非線性方程組的迭代解法解非線性方程組的迭代解法3/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis7.1 引言 在科學(xué)研究和工程設(shè)計(jì)中在科學(xué)研究和工程設(shè)計(jì)中, 經(jīng)常會(huì)遇到的一大類經(jīng)常會(huì)遇到的一大類問題是問題是非線性方程非線性方程 f (x)=0 的求根問題，其中的求根問題，其中f (x)為非為非線性函數(shù)。線性函數(shù)。 方程方程f ( x) =0的根的根, 亦稱為函數(shù)亦稱為函數(shù) f(x) 的的零點(diǎn)零點(diǎn)。 非線性方程的例子（1）在光的衍射理論中,需要求x-ta

3、nx=0=0的根（2）在行星軌道的計(jì)算中, 需要求x-asinx=b的根4/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis7.1 引言 當(dāng)當(dāng) f (x)不是不是x x的線性函數(shù)時(shí)，稱對(duì)應(yīng)的函數(shù)方程的線性函數(shù)時(shí)，稱對(duì)應(yīng)的函數(shù)方程 f (x)=0為為非線性方程非線性方程。 如果如果 f(x(x) )是多項(xiàng)式函數(shù)，則稱為是多項(xiàng)式函數(shù)，則稱為代數(shù)方程代數(shù)方程。 否則為否則為超越方程超越方程（三角方程，指數(shù)、對(duì)數(shù)方程（三角方程，指數(shù)、對(duì)數(shù)方程等）。一般稱等）。一般稱n次多項(xiàng)式構(gòu)成的方程次多項(xiàng)式構(gòu)成的方程 )0(00111nnnnnaaxaxaxa為為n次代

4、數(shù)方程次代數(shù)方程, ,當(dāng)當(dāng)n n1 1時(shí)時(shí), ,方程顯然是非線性的方程顯然是非線性的5/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis7.1 引言如果如果f (x)可以分解成可以分解成 , ,其中其中m為為正整數(shù)且正整數(shù)且 , ,則稱則稱x* *是是f(x)(x)的的m重零點(diǎn)重零點(diǎn), ,或或稱方程稱方程f (x)=0的的m重根重根。當(dāng)。當(dāng)m=1時(shí)稱時(shí)稱x* *為為單根單根。 )()()(*xgxxxfm0)(*xg 求方程根的問題，就幾何上講求方程根的問題，就幾何上講,是求曲線是求曲線 y=f (x)與與 x軸軸交點(diǎn)交點(diǎn)的橫坐標(biāo)。的橫坐標(biāo)。6/8

5、7 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis7.1 引言 公元前公元前17001700年的古巴比倫人有關(guān)于一、二次代數(shù)方程的解年的古巴比倫人有關(guān)于一、二次代數(shù)方程的解法。法。九章算術(shù)九章算術(shù)( (公元前公元前5010050100年年) )其中其中“方程術(shù)方程術(shù)”有聯(lián)有聯(lián)立一次方程組的一般解法。立一次方程組的一般解法。 15351535年意大利數(shù)學(xué)家坦特格里亞年意大利數(shù)學(xué)家坦特格里亞(TorTaglia)(TorTaglia)發(fā)現(xiàn)了三次代數(shù)發(fā)現(xiàn)了三次代數(shù)方程的解法，卡當(dāng)方程的解法，卡當(dāng)(HCardano)(HCardano)從他那里得到了這種解法，

6、從他那里得到了這種解法，于于15451545年在其名著年在其名著大法大法中公布了三次方程的公式解，中公布了三次方程的公式解，稱為卡當(dāng)算法。稱為卡當(dāng)算法。 后來卡當(dāng)?shù)膶W(xué)生弗瑞里后來卡當(dāng)?shù)膶W(xué)生弗瑞里(Ferrari)(Ferrari)又提出了四次代數(shù)方程的解又提出了四次代數(shù)方程的解法。此成果更激發(fā)了數(shù)學(xué)家們的情緒，但在以后的二個(gè)世法。此成果更激發(fā)了數(shù)學(xué)家們的情緒，但在以后的二個(gè)世紀(jì)中，求索工作始終沒有成效，導(dǎo)致人們對(duì)高次代數(shù)方程紀(jì)中，求索工作始終沒有成效，導(dǎo)致人們對(duì)高次代數(shù)方程解的存在性產(chǎn)生了懷疑。解的存在性產(chǎn)生了懷疑。代數(shù)方程求根的歷史7/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析

7、 Numerical Analysis7.1 引言代數(shù)方程求根的歷史 17991799年，高斯證明了代數(shù)方程必有一個(gè)實(shí)根或復(fù)根的定理，年，高斯證明了代數(shù)方程必有一個(gè)實(shí)根或復(fù)根的定理，稱此為稱此為代數(shù)基本定理代數(shù)基本定理，并由此可以立刻推理，并由此可以立刻推理n n次代數(shù)方程次代數(shù)方程必有必有n n個(gè)實(shí)根或復(fù)根。個(gè)實(shí)根或復(fù)根。 但在以后的幾十年中仍然沒有找出高次代數(shù)方程的公式解。但在以后的幾十年中仍然沒有找出高次代數(shù)方程的公式解。一直到一直到1818世紀(jì)，法國(guó)數(shù)學(xué)家拉格朗日用根置換方法統(tǒng)一了世紀(jì)，法國(guó)數(shù)學(xué)家拉格朗日用根置換方法統(tǒng)一了二、三、四次方程的解法。二、三、四次方程的解法。 在繼續(xù)探索在繼

8、續(xù)探索5 5次以上方程解的艱難歷程中，第一個(gè)重大突次以上方程解的艱難歷程中，第一個(gè)重大突破的是挪威數(shù)學(xué)家阿貝爾破的是挪威數(shù)學(xué)家阿貝爾(N(NAbel1802-1829) 1824Abel1802-1829) 1824年阿年阿貝爾發(fā)表了貝爾發(fā)表了“五次方程的代數(shù)解法不可能存在五次方程的代數(shù)解法不可能存在”的論文，的論文，但并未受到重視，連數(shù)學(xué)大師高斯也未理解這項(xiàng)成果的重但并未受到重視，連數(shù)學(xué)大師高斯也未理解這項(xiàng)成果的重要意義。要意義。8/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis7.1 引言代數(shù)方程求根的歷史18281828年年1717歲的法國(guó)

9、數(shù)學(xué)家伽羅華歲的法國(guó)數(shù)學(xué)家伽羅華(E(EGalois 1811-1832)Galois 1811-1832)寫寫出了劃時(shí)代的論文出了劃時(shí)代的論文“關(guān)于五次方程的代數(shù)解法問題關(guān)于五次方程的代數(shù)解法問題”，指，指出即使在公式中容許用出即使在公式中容許用n n次方根，并次方根，并用類似算法求五次或更用類似算法求五次或更高次代數(shù)方程的根是不可能的。高次代數(shù)方程的根是不可能的。”，“他一勞永逸地發(fā)現(xiàn)了一個(gè)折磨了數(shù)學(xué)家?guī)讉€(gè)世紀(jì)的謎團(tuán)他一勞永逸地發(fā)現(xiàn)了一個(gè)折磨了數(shù)學(xué)家?guī)讉€(gè)世紀(jì)的謎團(tuán)的答案：在什么條件下一個(gè)方程有解？的答案：在什么條件下一個(gè)方程有解？” 9/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值

10、分析 Numerical Analysis7.1 引言理論上已證明，對(duì)于次數(shù)n=4的多項(xiàng)式方程,它的根可以用公式表示,而次數(shù)大于5的多項(xiàng)式方程,它的根一般不能用解析表達(dá)式表示.因此對(duì)于f(x)=0的函數(shù)方程,一般來說,不存在根的解析表達(dá)式,而實(shí)際應(yīng)用中,也不一定必需得到求根的解析表達(dá)式,只要得到滿足精度要求的根的近似值就可以了。常用的求根方法分為區(qū)間法和迭代法兩大類。求根問題包括：根的存在性、根的范圍和根的精確化。10/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis7.1 引言11/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Num

11、erical Analysis定理1(根的存在定理，介值定理介值定理) 假設(shè)函數(shù) y=f (x) C a,b ,且 f(a)f(b)0, 則至少存在一點(diǎn)x (a,b)使得 f(x)=0。定理2 假設(shè)函數(shù) y=f(x)在 a,b 上單調(diào)連續(xù),且f(a)f(b)0, 則恰好只存在一點(diǎn)x (a,b)使得 f(x)=0。定理3 假設(shè)函數(shù)y=f(x)在x=s的某一鄰域內(nèi)充分可微，則s是方程 f(x)=0的m重根的充分必要條件是 0)(, 0)()()()()1(sfsfsfsfmm7.1 引言y=f(x)abyx12/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Anal

12、ysis7.2 二分區(qū)間法 設(shè)函數(shù)設(shè)函數(shù)f( (x) )在閉區(qū)間在閉區(qū)間 a, ,b 上連續(xù)上連續(xù), ,且且f ( (a) )f( (b)0,)0,根據(jù)連續(xù)函數(shù)的性質(zhì)可知根據(jù)連續(xù)函數(shù)的性質(zhì)可知, , f ( (x)= 0)= 0在在( (a, ,b) )內(nèi)必有實(shí)內(nèi)必有實(shí)根根, ,稱區(qū)間稱區(qū)間 a, ,b 為為有根區(qū)間有根區(qū)間。 假定方程假定方程 f (x)= 0 0在區(qū)間在區(qū)間 a, ,b 內(nèi)有惟一實(shí)根內(nèi)有惟一實(shí)根x* *。 二分法的基本思想二分法的基本思想是是: : 首先確定一個(gè)有根區(qū)間首先確定一個(gè)有根區(qū)間, ,將將區(qū)間二等分區(qū)間二等分, , 通過判斷通過判斷f(x)在區(qū)間端點(diǎn)的符號(hào)在區(qū)間端

13、點(diǎn)的符號(hào), , 逐步將逐步將有根區(qū)間縮小有根區(qū)間縮小, , 直至直至有根區(qū)間足夠地小有根區(qū)間足夠地小, , 便可求出滿便可求出滿足精度要求的近似根。足精度要求的近似根。13/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis7.2 二分法q 基本思想將有根區(qū)間進(jìn)行對(duì)分，判斷出解在某個(gè)分段內(nèi)，然后將有根區(qū)間進(jìn)行對(duì)分，判斷出解在某個(gè)分段內(nèi)，然后再對(duì)該段對(duì)分，依次類推，直到滿足給定的精度為止再對(duì)該段對(duì)分，依次類推，直到滿足給定的精度為止q 適用范圍適用范圍求有根區(qū)間內(nèi)的求有根區(qū)間內(nèi)的 奇數(shù)重實(shí)根奇數(shù)重實(shí)根q 數(shù)學(xué)原理：數(shù)學(xué)原理：介值定理介值定理設(shè)設(shè) f(x

14、) 在在 a, b 上連續(xù)，且上連續(xù)，且 f(a) f(b)0，則由介值定，則由介值定理可得，在理可得，在 (a, b) 內(nèi)至少存在一點(diǎn)內(nèi)至少存在一點(diǎn) 使得使得 f( )=0ba2ba *x14/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis二分法是一種確定有根區(qū)間的方法二分法是一種確定有根區(qū)間的方法 為了確定根的初值，首先必須圈定根所在的范圍，為了確定根的初值，首先必須圈定根所在的范圍， 稱為稱為圈定根圈定根或或根的隔離根的隔離。 在上述基礎(chǔ)上，采取適當(dāng)?shù)臄?shù)值方法確定具有一定在上述基礎(chǔ)上，采取適當(dāng)?shù)臄?shù)值方法確定具有一定 精度要求的初值。精度要求

15、的初值。 對(duì)于代數(shù)方程，其根的個(gè)數(shù)（實(shí)或復(fù)的）與其次數(shù)對(duì)于代數(shù)方程，其根的個(gè)數(shù)（實(shí)或復(fù)的）與其次數(shù) 相同相同。至于超越方程，其根可能是一個(gè)、幾個(gè)或無。至于超越方程，其根可能是一個(gè)、幾個(gè)或無 解，并沒有什么固定的圈根方法解，并沒有什么固定的圈根方法15/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis7.2 區(qū)間法 設(shè)設(shè)f (x)為區(qū)間為區(qū)間a,b上的連續(xù)函數(shù)上的連續(xù)函數(shù), 如果如果f (a)f (b)0 , 則則a,b中至少有一個(gè)實(shí)根。中至少有一個(gè)實(shí)根。 如果如果f (x)在在a,b上還是單調(diào)地遞增或遞減，則僅有上還是單調(diào)地遞增或遞減，則僅有一個(gè)實(shí)

16、根。一個(gè)實(shí)根。y=f(x)abyx16/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis7.2 區(qū)間法n由此可大體確定根所在子區(qū)間，方法有：由此可大體確定根所在子區(qū)間，方法有： (1) 畫圖法畫圖法 (2) 逐步搜索法逐步搜索法確定有根區(qū)間的方法確定有根區(qū)間的方法17/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis7.2 區(qū)間法(1) 畫圖法畫圖法 畫出畫出y = f (x)的略圖，從而看出曲線與的略圖，從而看出曲線與x軸交點(diǎn)的軸交點(diǎn)的 大致位置。大致位置。 也可將也可將f (x) = 0分解為分解為

17、 1(x)= 2(x)的形式，的形式， 1(x) 與與 2(x)兩曲線交點(diǎn)的橫坐標(biāo)所在的子區(qū)間即為含根兩曲線交點(diǎn)的橫坐標(biāo)所在的子區(qū)間即為含根 區(qū)間。區(qū)間。例如例如 xlogx-1= 0= 0可以改寫為可以改寫為logx= =1/x畫出對(duì)數(shù)曲線畫出對(duì)數(shù)曲線y=logx, ,與雙曲線與雙曲線y= 1/x,它們交它們交 點(diǎn)的橫坐標(biāo)位于區(qū)間點(diǎn)的橫坐標(biāo)位于區(qū)間2,32,3內(nèi)內(nèi)確定有根區(qū)間的方法確定有根區(qū)間的方法18/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis7.2 區(qū)間法(1) 畫圖法畫圖法xy1gxy 023yx確定有根區(qū)間的方法確定有根區(qū)間的方法1

18、9/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis7.2 區(qū)間法(1) 畫圖法畫圖法y0 xy=f(x)y=kf(x)確定有根區(qū)間的方法確定有根區(qū)間的方法20/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis7.2 區(qū)間法y0 xABa1b1a2b2(2) 搜索法 對(duì)于給定的對(duì)于給定的f (x),設(shè)有根區(qū)間為設(shè)有根區(qū)間為A, ,B,從從x0=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=x0ih (i=0,1,2, ,n),從左至右檢查

19、從左至右檢查f (xi)的符號(hào)的符號(hào), ,如發(fā)現(xiàn)如發(fā)現(xiàn)xi與端點(diǎn)與端點(diǎn)x0的函數(shù)值異號(hào)的函數(shù)值異號(hào), ,則得到一個(gè)縮小的有根子區(qū)間則得到一個(gè)縮小的有根子區(qū)間xi-1, ,xi。確定有根區(qū)間的方法確定有根區(qū)間的方法21/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis7.2 區(qū)間法例例7.2.17.2.1 方程方程f(x)=(x)=x3 3- -x-1=0 -1=0 確定其有根區(qū)間確定其有根區(qū)間解：用試湊的方法，不難發(fā)現(xiàn)解：用試湊的方法，不難發(fā)現(xiàn) f(0)0 (0)0(2)0 在區(qū)間（在區(qū)間（0 0，2 2）內(nèi)至少有一個(gè)實(shí)根）內(nèi)至少有一個(gè)實(shí)根 設(shè)從設(shè)

20、從x=0=0出發(fā)出發(fā), ,取取h=0.5=0.5為步長(zhǎng)向右進(jìn)行根的為步長(zhǎng)向右進(jìn)行根的 搜索搜索, ,列表如下列表如下確定有根區(qū)間的方法確定有根區(qū)間的方法22/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis7.2 區(qū)間法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)必有一根確定有根區(qū)間的方法確定有根區(qū)間的方法23/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis7.2 二分區(qū)間法二分法求根過程

21、二分法求根過程 取有根區(qū)間取有根區(qū)間a,b之中點(diǎn)之中點(diǎn), 將它分為兩半將它分為兩半,分點(diǎn)分點(diǎn) ,這樣就可得縮小有根區(qū)間這樣就可得縮小有根區(qū)間20bax y y=f(x) y=f(x) x* a x1 x* x0 b a x0 x1 b a1 b1 a1 b1 a2 b2 a2 b2 11,ba24/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis7.2 二分區(qū)間法 對(duì)壓縮了的有根區(qū)間對(duì)壓縮了的有根區(qū)間 施行同樣的手法施行同樣的手法, , 即取中點(diǎn)即取中點(diǎn) , ,將區(qū)間將區(qū)間 再分為兩半再分為兩半, ,然然 后再確定有根區(qū)間后再確定有根區(qū)間 , ,其

22、長(zhǎng)度是其長(zhǎng)度是 的的 二分之一。二分之一。 11,ba2111bax11,ba22,ba11,ba y y=f(x) y=f(x) x* a x1 x* x0 b a x0 x1 b a1 b1 a1 b1 a2 b2 a2 b2 25/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis7.2 二分區(qū)間法 如此反復(fù)下去如此反復(fù)下去, ,若不出現(xiàn)若不出現(xiàn) , ,即可得出一即可得出一 系列有根區(qū)間序列：系列有根區(qū)間序列： 上述每個(gè)區(qū)間都是前一個(gè)區(qū)間的一半上述每個(gè)區(qū)間都是前一個(gè)區(qū)間的一半, ,因此因此 的長(zhǎng)度的長(zhǎng)度0)(kxfkkbabababa,2211

23、)(21)(2111abababkkkkk 當(dāng)當(dāng)k時(shí)趨于零時(shí)趨于零, ,這些區(qū)間最終收斂于一點(diǎn)這些區(qū)間最終收斂于一點(diǎn)x* * 即為即為 所求的根所求的根 。26/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis7.2 二分區(qū)間法每次二分后每次二分后, ,取有根區(qū)間取有根區(qū)間 的中點(diǎn)的中點(diǎn)作為根的近似值，得到一個(gè)近似根的序列作為根的近似值，得到一個(gè)近似根的序列 該序列以根該序列以根x x* *為極限為極限 只要二分足夠多次只要二分足夠多次( (即即k足夠大足夠大),),便有便有這里這里為給定精度為給定精度, ,由于由于 , ,則則 kkba ,)(2

24、1kkkbax,210kxxxxkxx*kkbax,*27/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis7.2 二分區(qū)間法11122kkkkkababab1*22kkkkababxx28/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis7.2 二分區(qū)間法當(dāng)給定精度當(dāng)給定精度0 0后后, ,要想要想 成立成立, ,只要只要取取k滿足滿足 即可，亦即當(dāng)即可，亦即當(dāng): kxx*)(211abklg()lg1lg 2bakK時(shí)時(shí), ,做到第做到第K+1次二分次二分, ,計(jì)算得到的計(jì)算得到的 就是就是滿足精度

25、要求的近似根滿足精度要求的近似根 。 kx29/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis y n 開 始 輸 入 a , b, (a+b)/2 x f(a) f(x )0 ? xb x a |b-a|0 輸 出 x 結(jié) 束 y n 二分區(qū)間法算法實(shí)現(xiàn)二分區(qū)間法算法實(shí)現(xiàn)30/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis 例例7.2.2 7.2.2 證明方程證明方程 在區(qū)間在區(qū)間2, 3內(nèi)有一內(nèi)有一個(gè)根個(gè)根 , 使用二分法求誤差不超過使用二分法求誤差不超過0.510-3 的根要二的根要二 分多少

26、次？分多少次？證明證明 令令 0523 xx且且f(x)f(x)在在2, 3上連續(xù)上連續(xù), ,故方程故方程f(x)=0f(x)=0在在2,32,3內(nèi)至少內(nèi)至少有一個(gè)根。又有一個(gè)根。又 當(dāng)時(shí)當(dāng)時(shí)時(shí)，時(shí)， , ,故故f(x)f(x)在在2, 32, 3上是單調(diào)遞增函數(shù)上是單調(diào)遞增函數(shù), ,從而從而f(x)f(x)在在2, 32, 3上有且僅有一根。上有且僅有一根。23)(2xxf3 , 2x0)( xf 給定誤差限給定誤差限 0.510-3 , ,使用二分法時(shí)使用二分法時(shí)52)(3xxxf016)3(, 01)2(ff31/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerica

27、l Analysis7.2 二分區(qū)間法 誤差限為誤差限為 只要取只要取k滿足滿足 )(211*abxxkk311021)(21 abk即可，亦即即可，亦即 3102 k97.92110lg3gk所以需二分所以需二分1010次便可達(dá)到要求。次便可達(dá)到要求。 32/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis7.2 二分區(qū)間法二分法的優(yōu)點(diǎn)二分法的優(yōu)點(diǎn)不管有根區(qū)間不管有根區(qū)間 多大多大, ,總能求出滿足精度要求的總能求出滿足精度要求的根根, ,且對(duì)函數(shù)且對(duì)函數(shù)f( (x) )的要求不高的要求不高, ,只要連續(xù)即可只要連續(xù)即可, ,計(jì)算亦計(jì)算亦簡(jiǎn)單簡(jiǎn)單

28、; ;二分法的二分法的局限性局限性只能用于求函數(shù)的實(shí)根只能用于求函數(shù)的實(shí)根, ,不能用于求復(fù)根及偶數(shù)重根不能用于求復(fù)根及偶數(shù)重根, ,它的收斂速度與比值為它的收斂速度與比值為 的等比級(jí)數(shù)相同。的等比級(jí)數(shù)相同。 ba ,2133/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis 例7.2.3 求方程f(x)= x 3 e-x =0的一個(gè)實(shí)根。 因?yàn)?f(0)0。 故f(x)在(0,1)內(nèi)有根用二分法解之，(a,b）=（0,1)計(jì)算結(jié)果如表：kak bk xk f(xk)符號(hào)00 1 0.5000 10.5000 0.7500 20.7500 0.87

29、50 3 0.87500.8125 4 0.81250.7812 5 0.7812 0.7656 60.7656 0.7734 7 0.7734 0.7695 8 0.7695 0.7714 90.7714 0.7724 100.7724 0.7729 取x10=0.7729，誤差為| x* -x10|=1/211 。 34/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis7.3 迭代法及其加速為求解非線性方程為求解非線性方程f( (x)=0)=0的根，先將其寫成便于迭代的根，先將其寫成便于迭代的的等價(jià)方程等價(jià)方程 其中其中 為為x的連續(xù)函數(shù)的連續(xù)

30、函數(shù))(x)(xx迭代法的基本思想迭代法的基本思想 如果數(shù)如果數(shù) 使使 f(x*)=0, 則也有則也有 , 反之反之, 若若 , 則也有則也有 , 稱稱 為為迭代函數(shù)迭代函數(shù)，而，而稱稱x* 為為 的的不動(dòng)點(diǎn)不動(dòng)點(diǎn)。 *x)(*xx)(*xx0)(*xf)(x)(x35/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis7.3 迭代法及其加速任取一個(gè)初值任取一個(gè)初值 , 代入式代入式 的右端的右端, 得得到到 0 x)(xx)(01xx再將再將 代入式代入式 的右端的右端, 得到得到 ,依此類推依此類推, 得到一個(gè)數(shù)列得到一個(gè)數(shù)列 ， 其一般表示其一

31、般表示 1x)(xx)(12xx)(23xx), 2 , 1 , 0()(1kxxkk稱為求解非線性方程的稱為求解非線性方程的簡(jiǎn)單迭代法簡(jiǎn)單迭代法。 36/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis7.3 迭代法及其加速如果由迭代格式如果由迭代格式 產(chǎn)生的序列產(chǎn)生的序列 收斂收斂, ,即即 nx)(1kkxx*limxxnn則稱則稱迭代法收斂迭代法收斂。 37/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis7.3 迭代法及其加速 實(shí)際計(jì)算中當(dāng)然不可能也沒必要無窮多步地做實(shí)際計(jì)算中當(dāng)然不可能也沒必

32、要無窮多步地做下去下去, , 對(duì)預(yù)先給定的精度要求對(duì)預(yù)先給定的精度要求，只要某個(gè)，只要某個(gè)k k滿足滿足1kkxx即可結(jié)束計(jì)算并取即可結(jié)束計(jì)算并取 kxx*38/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis7.3 迭代法及其加速例例7.3.1 用迭代法求方程用迭代法求方程 在在x=1.5附近的一個(gè)根附近的一個(gè)根解解 將方程改寫成如下兩種等價(jià)形式將方程改寫成如下兩種等價(jià)形式 013 xx1)(1)(3231xxxxxx相應(yīng)地可得到兩個(gè)迭代公式相應(yīng)地可得到兩個(gè)迭代公式1)(1)(321311kkkkkkxxxxxx39/87 鄭州大學(xué)研究生2014

33、-2015學(xué)年課程 數(shù)值分析 Numerical Analysis7.3 迭代法及其加速如果取初始值如果取初始值 1.51.5，用上述兩個(gè)迭代公，用上述兩個(gè)迭代公式分別迭代，計(jì)算結(jié)果為式分別迭代，計(jì)算結(jié)果為 0 x40/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis7.3 迭代法及其加速迭代法的幾何意義迭代法的幾何意義 通常將方程通常將方程f( (x)=0)=0化為與它同解的方程化為與它同解的方程的方法不止一種的方法不止一種, ,有的收斂有的收斂, ,有的不收斂有的不收斂, ,這取決于這取決于 的性態(tài)。的性態(tài)。 方程方程 的求根問題在幾何上就是確

34、定曲線的求根問題在幾何上就是確定曲線 與直線與直線y=x的交點(diǎn)的交點(diǎn)P*的橫坐標(biāo)。的橫坐標(biāo)。 )(xx)(x)(xx( )yx41/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis7.3 迭代法及其加速 y=x y y=)(x y=x 1)(0*x 0)(1*x P0 P2P* Q1 Q2 x1 x0 x2 x* x y x0 x x1 x2 x3 x* y=)(x)(x P* P1 迭代法的幾何意義迭代法的幾何意義 42/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis7.3 迭代法及其加速 y=x

35、y y=x y=)(x 1)(* x 1)(* x （c） （d） P* x1 x0 x y x0 x x1 x2 x3 x* y=)(x)(x x* x2 P* 迭代法的幾何意義迭代法的幾何意義 43/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis7.3 迭代法及其加速迭代法的收斂性迭代法的收斂性 對(duì)方程對(duì)方程f(x)=0可以構(gòu)造不同的迭代公式可以構(gòu)造不同的迭代公式, 但迭代公式但迭代公式并非總是收斂。那么并非總是收斂。那么, ,當(dāng)?shù)瘮?shù)當(dāng)?shù)瘮?shù) 滿足什滿足什么條件時(shí)，相應(yīng)的迭代公式才收斂呢？么條件時(shí)，相應(yīng)的迭代公式才收斂呢？ ),2, 1

36、 ,0()(1kxxkk)(x44/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis定理定理7.3.1 設(shè)函數(shù)設(shè)函數(shù) 在在a,b上有連續(xù)的一階導(dǎo)上有連續(xù)的一階導(dǎo) 數(shù)數(shù), 且滿足且滿足 （1）對(duì)所有的）對(duì)所有的xa,b 有有 a,b(映內(nèi)映內(nèi)) （2）存在）存在 0 L 1 ,使所有的使所有的xa,b有有 L （壓縮性）（壓縮性）則方程則方程 在在a,b上的解上的解 存在且唯一存在且唯一，對(duì)，對(duì)任意的初值任意的初值 a ,b ，迭代過程，迭代過程均收斂于均收斂于 。并有誤差估計(jì)式。并有誤差估計(jì)式 )(x)(x)(x)(xx*x0 x)(1kkxx*x

37、1*1kkkxxLLxx01*1xxLLxxkk 45/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis由連續(xù)函數(shù)介值定理知由連續(xù)函數(shù)介值定理知, 必有必有 a, b, 使使 所以有解存在所以有解存在, 即即假設(shè)有兩個(gè)解假設(shè)有兩個(gè)解 和和 , , a, b，則，則 ，由微分中值定理有由微分中值定理有其中其中是介于是介于x*和和 之間的點(diǎn)之間的點(diǎn) 從而有從而有a,b，進(jìn)，進(jìn)而有而有 由條件由條件(2)有有 1, 所所以以 - =0，即，即 = ，解唯一。，解唯一。證證: 構(gòu)造函數(shù)構(gòu)造函數(shù) ,由條件由條件對(duì)任意的對(duì)任意的xa, b a, b有有xxx)

38、()(0)()(0)()(bbbaaa)(x*x0)()(*xxx*xx*xx)(*xx)(xx)()()(*xxxxxxx0)(1)(*xx)(x*xx*xx46/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis按迭代過程按迭代過程 ,有有 )(1kkxx)()()(1*1*kkkxxxxxx1*1*)(kkkxxLxxxx0*2*21*xxLxxLxxLxxkkkk 由于由于L1,L1,所以有所以有 , ,可見可見L L越小越小, ,收斂越快收斂越快 *limxxkk再證誤差估計(jì)式再證誤差估計(jì)式 1*1kkkxxLLxx01*1xxLLxxkk

39、 47/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis 1*1*kkkkkxxxxLxxLxx)(1*kkkxxxxL1*)1 (kkkxxLxxL1*1kkkxxLLxx 即即 得證。得證。 2121211)()()(kkkkkkkkxxLxxxxxx2*11210111kkkkkkLLLxxxxxxxxLLL即即 得證。得證。 48/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis 10)(xx 開 始 輸 入 x0,N 1 kk+ 1 k x1 x0 輸 出 近 似 根 x1 |x1- x0|?

40、 輸 出 迭 代 失 敗 標(biāo) 志 結(jié) 束 n k0c0），使），使 )(1kkxx)(xx*xkkxxe*迭代法的收斂速度迭代法的收斂速度ceepkkk1lim則稱序列則稱序列 是是 p 階收斂階收斂的的, ,c稱稱漸近誤差常數(shù)漸近誤差常數(shù)。特別地特別地, ,p=1=1時(shí)稱為時(shí)稱為線性收斂線性收斂, ,p=2=2時(shí)稱為時(shí)稱為平方收平方收斂斂。1 1 p 2 0 xn+1X*ayx0Bf(x)0a=x0yx0B=x0f(x)0ayx0Bf(x)0a =x0牛頓迭代法的收斂性牛頓迭代法的收斂性68/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis7.4

41、 牛頓(Newton)迭代法 牛頓迭代法對(duì)初值牛頓迭代法對(duì)初值x x0 0的選取要求比較高。的選取要求比較高。 x x0 0必須充必須充分靠近分靠近x x* *才能保證局部收斂。才能保證局部收斂。定理定理7.4.2 如果在有根區(qū)間如果在有根區(qū)間a,b上上連續(xù)且不變號(hào)，在連續(xù)且不變號(hào)，在a,b上取初始近似根上取初始近似根x0滿足，滿足，則牛頓迭代法產(chǎn)生的迭代序列單調(diào)收斂于方程則牛頓迭代法產(chǎn)生的迭代序列單調(diào)收斂于方程f(x)=0在該區(qū)間上的唯一解。在該區(qū)間上的唯一解。)(, 0)(, 0)()(xfxfbfaf 0)()(00 xfxf69/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析

42、 Numerical AnalysisNewton法的收斂性依賴于法的收斂性依賴于x0 的選取。的選取。x*x0 x0 x0 不滿足迭代條件時(shí)，可能導(dǎo)致迭代值遠(yuǎn)離不滿足迭代條件時(shí)，可能導(dǎo)致迭代值遠(yuǎn)離根的情況而找不到根或死循環(huán)的情況根的情況而找不到根或死循環(huán)的情況70/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis ?0)(0 xf 1000)()(xxfxfx ?01 xx 開 始 輸 入 x0,N 1k k+1 k x1 x0 輸出x1 輸出迭代 失敗標(biāo)志 結(jié) 束 n kN? n n y 輸出奇 異標(biāo)志 y y 牛頓迭代法的算法實(shí)現(xiàn)牛頓迭代法的

43、算法實(shí)現(xiàn)71/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysisq 牛頓法的優(yōu)點(diǎn)q 牛頓法是目前求解非線性方程 (組) 的主要方法至少二階局部收斂，收斂速度較快，特別是當(dāng)?shù)辽俣A局部收斂，收斂速度較快，特別是當(dāng)?shù)c(diǎn)充分靠近精確解時(shí)。可求重根和復(fù)根。代點(diǎn)充分靠近精確解時(shí)。可求重根和復(fù)根。q 牛頓的缺點(diǎn)l 對(duì)重根收斂速度較慢（線性收斂）對(duì)重根收斂速度較慢（線性收斂）l 對(duì)初值的選取很敏感，要求初值相當(dāng)接近真解對(duì)初值的選取很敏感，要求初值相當(dāng)接近真解在實(shí)際計(jì)算中，可以先用其它方法獲得真解的一個(gè)粗在實(shí)際計(jì)算中，可以先用其它方法獲得真解的一個(gè)粗糙近似，然后

44、再用牛頓法求解。糙近似，然后再用牛頓法求解。72/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis7.5 弦截法牛頓迭代法雖然具有牛頓迭代法雖然具有收斂速度快收斂速度快的優(yōu)點(diǎn)，但的優(yōu)點(diǎn)，但每迭代一次都要計(jì)算導(dǎo)數(shù)每迭代一次都要計(jì)算導(dǎo)數(shù) , 當(dāng)當(dāng) 比較比較復(fù)雜時(shí)復(fù)雜時(shí), 不僅每次計(jì)算不僅每次計(jì)算 帶來很多不便，帶來很多不便，而且還可能十分麻煩，如果用不計(jì)算導(dǎo)數(shù)的而且還可能十分麻煩，如果用不計(jì)算導(dǎo)數(shù)的迭代方法，往往只有線性收斂的速度。本節(jié)迭代方法，往往只有線性收斂的速度。本節(jié)介紹的弦截法便是一種不必進(jìn)行導(dǎo)數(shù)運(yùn)算的介紹的弦截法便是一種不必進(jìn)行導(dǎo)數(shù)運(yùn)算的求根

45、方法。求根方法。 )(kxf )(xf)(kxf73/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis7.5 弦截法 弦截法在迭代過程中不僅用到前一步弦截法在迭代過程中不僅用到前一步 處的處的函數(shù)值，而且還使用函數(shù)值，而且還使用 處的函數(shù)值來構(gòu)造處的函數(shù)值來構(gòu)造迭代函數(shù)，這樣做能提高迭代的收斂速度。迭代函數(shù)，這樣做能提高迭代的收斂速度。稱之為稱之為多點(diǎn)迭代法多點(diǎn)迭代法。kx1kx74/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis7.5 弦截法弦截法的基本思想弦截法的基本思想 為避免計(jì)算函數(shù)的導(dǎo)數(shù)為避

46、免計(jì)算函數(shù)的導(dǎo)數(shù) ，使用差商，使用差商 替代牛頓公式中的導(dǎo)數(shù)替代牛頓公式中的導(dǎo)數(shù) , ,便得到迭代公式便得到迭代公式 稱為稱為弦截迭代公式弦截迭代公式，相應(yīng)的迭代法稱為，相應(yīng)的迭代法稱為弦截法弦截法。)()()(11kkkkxxxfxf)(kxf 111()( )( )()kkkkkkkxxxxf xf xf x),2, 1(k)(kxf 75/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis7.5 弦截法弦截法的幾何意義弦截法的幾何意義 弦截法也稱割線法弦截法也稱割線法, ,其幾何意義是用過曲線上兩其幾何意義是用過曲線上兩點(diǎn)點(diǎn) 、 的割線來代替曲

47、線的割線來代替曲線, ,用割用割線與線與x軸交點(diǎn)的橫座標(biāo)作為方程的近似根軸交點(diǎn)的橫座標(biāo)作為方程的近似根 再過再過)(,(000 xfxP)(,(111xfxP2x P1 y=f(x) x0 x2 x3 x1 x* P3 P0 P2 P1點(diǎn)和點(diǎn)點(diǎn)和點(diǎn) 作割作割線求出線求出 , ,再過再過P2點(diǎn)和點(diǎn)點(diǎn)和點(diǎn) 作割線求出作割線求出 , ,余此類推，當(dāng)收斂時(shí)可求余此類推，當(dāng)收斂時(shí)可求出滿足精度要求的出滿足精度要求的)(,(222xfxP3x)(,(333xfxP4xkx76/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis7.5 弦截法 可以證明，弦截法具有

48、超線性收斂，收斂可以證明，弦截法具有超線性收斂，收斂的階約為的階約為1.618，它與前面介紹的一般迭代法，它與前面介紹的一般迭代法一樣都是線性化方法，但也有區(qū)別。即一般迭一樣都是線性化方法，但也有區(qū)別。即一般迭代法在計(jì)算代法在計(jì)算 時(shí)只用到前一步的值時(shí)只用到前一步的值 ，故稱，故稱之為之為單點(diǎn)迭代法單點(diǎn)迭代法；而弦截法在求；而弦截法在求 時(shí)要用到前時(shí)要用到前兩步的結(jié)果兩步的結(jié)果 和和 ，使用這種方法必須給出，使用這種方法必須給出兩個(gè)初始近似根兩個(gè)初始近似根 ，這種方法稱為，這種方法稱為多點(diǎn)迭多點(diǎn)迭代法代法。 1kxkx1kx1kxkx10,xx77/87 鄭州大學(xué)研究生2014-2015學(xué)年課

49、程 數(shù)值分析 Numerical Analysis ?0)(0 xf ?0)(1xf ?0)()(01xfxf 2010111)()()()(xxxxfxfxfx ?12 xx 輸 入 x0, x1,N 1k k+1 k x1 x0 x2 x1 f(x1)f(x0) f(x2) f(x1) 輸出x2 輸出迭代 失敗標(biāo)志 結(jié) 束 n kN? n n y 輸出奇 異標(biāo)志 y y x0 x2 x1 x2 n y y n 輸出x2 弦截法算法實(shí)現(xiàn)弦截法算法實(shí)現(xiàn) 78/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis7.5 弦截法例例7.5.1 用弦截法求方

50、程用弦截法求方程 在在 初始初始 值鄰近的一個(gè)根。要求值鄰近的一個(gè)根。要求解：取解：取 , , 令令 利用弦截迭代公式利用弦截迭代公式 易見取近似根易見取近似根 可滿足精度要求。可滿足精度要求。xex5 . 00 x0001. 01kkxx5 . 00 x6.01xxexxf)()()()()(1111kkxxkkxkkkxxeexxexxxkkk56714. 04x79/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis7.5 解非線性方程組的迭代解法考慮非線性方程組在點(diǎn)(x0,y0)作二元Taylor展開，并取線性部分12( , )0 ( , )

51、0f x yfx y100100110000200200220000(,)(,)( , )(,)()()0(,)(,)( , )(,)()()0f xyf xyf x yf xyxxyyxyfxyfxyfx yfxyxxyyxy80/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis7.5 解非線性方程組的迭代解法1001000010020020000200(,)(,)()()(,)(,)(,)()()(,)f xyf xyxxyyf xyxyfxyfxyxxyyfxyxy 整理得這是關(guān)于x,y的線性方程組。從而將非線性方程組進(jìn)行了線性化。這是目前解決非線性問題的主要方法。81/87 鄭州大學(xué)研究生2014-2015學(xué)年課程 數(shù)值分析 Numerical Analysis7.5 解非線性方程組的迭代解法000000110022(,)00