的零點。-read

1、第5章 方程求根,5.1 二分法5.2 迭代法5.3 加速迭代法5.4 牛頓法5.5 弦截法,第5章 方程求根,在科學(xué)研究和工程設(shè)計中, 經(jīng)常會遇到的一大類問題是非線性方程: f(x)=0 (5.1)的求根問題，其中f(x)為非線性函數(shù)。 方程f(x)=0的根, 亦稱為

2、函數(shù)f(x)的零點。,,,,如果 f(x) 可以分解成： 其中 m 為正整數(shù)且 ,則稱 x* 是f(x)的m重零點, 或稱方程 f(x)=0 的 m 重根。 當m=1時稱x*為單根。若f(x)存在m階導(dǎo)數(shù),則x*是方程f(x)=0的m重根(m>1) 當且僅當：,,,,記筆記,當f(x)不是x的線性函數(shù)時，稱對應(yīng)的函數(shù)方程為非線性方程。如果f(x)是

3、多項式函數(shù)，則稱為代數(shù)方程，否則稱為超越方程（三角方程，指數(shù)、對數(shù)方程等）。 一般稱n次多項式構(gòu)成的方程：,,為n次代數(shù)方程,當n＞1時,方程顯然是非線性的 一般稍微復(fù)雜的3次以上的代數(shù)方程或超越方程,很難甚至無法求得精確解。本章將介紹常用的求解非線性方程的近似根的幾種數(shù)值解法。,記筆記,,,通常方程根的數(shù)值解法大致分為三個步驟進行：① 判定根的存在性。即方程有沒有根？如果有 根，有幾個根？②

4、 確定根的分布范圍。即將每一個根用區(qū)間隔 離開來，這個過程實際上是獲得方程各根的 初始近似值。③ 根的精確化。將根的初始近似值按某種方法 逐步精確化，直到滿足預(yù)先要求的精度為止。,本章介紹方程的迭代解法，它既可以用來求解代數(shù)方程，也可以用來解超越方程，并且僅限于求方程的實根。運用迭代法求解方程的根應(yīng)解決以下兩個問題：確定根的初值;將根進一步精確化到所需要的精度。,記筆記,5.1 二分法,二分法

5、又稱二分區(qū)間法,是求解方程(5.1)的近似根的一種常用的簡單方法。 設(shè)函數(shù)f(x)在閉區(qū)間[a,b]上連續(xù),且f(a)f(b)<0, 根據(jù)連續(xù)函數(shù)的性質(zhì)可知, 方程 f(x)= 0 在(a,b)內(nèi)必有實根,稱區(qū)間[a,b]為有根區(qū)間。 為明確起見,假定方程 f(x)= 0 在區(qū)間[a,b]內(nèi)有惟一實根x*。 二分法的基本思想是: 首先確定有根區(qū)間,將區(qū)間二等分, 通過判斷f(x)的符號, 逐步將有根區(qū)間縮小

6、, 直至有根區(qū)間足夠地小, 便可求出滿足精度要求的近似根。,5.1.1 有根區(qū)間的確定,為了確定根的初值，首先必須圈定根所在的范圍， 稱為圈定根或根的隔離。 在上述基礎(chǔ)上，采取適當?shù)臄?shù)值方法確定具有一定 精度要求的初值。 對于代數(shù)方程，其根的個數(shù)（實或復(fù)的）與其次數(shù) 相同。至于超越方程，其根可能是一個、幾個或無 解，并沒有什么固定的圈根方法 求方程根的問題，就幾何上講,是求曲線 y=f (x)與

7、 x軸交點的橫坐標。,由高等數(shù)學(xué)知識可知, 設(shè) f (x) 為區(qū)間 [a,b] 上的單值連續(xù)函數(shù), 如果 f (a)·f (b)<0 , 則[a,b]中至少有一個實根。如果 f (x) 在[a,b]上還是單調(diào)遞增或遞減函數(shù)，則方程f (x)=0僅有一個實根。,記筆記,由此可大體確定根所在子區(qū)間，方法有： (1) 畫圖法 (2) 逐步搜索法,,y=f(x),,,,,,a,b

8、,y,x,(1) 畫圖法,畫出 y = f (x) 的略圖，從而看出曲線與x軸交點的 大致位置。 也可將 f (x) = 0 分解為 ?1(x)= ?2(x) 的形式， ?1(x) 與 ?2(x) 兩曲線交點的橫坐標所在的子區(qū)間 即為含根區(qū)間。例如 x lgx - 1 = 0 可以改寫為 lgx = 1/x 畫出對數(shù)曲線 y = lgx,與雙曲

9、線 y= 1/x, 它們 交點的橫坐標位于區(qū)間[2,3]內(nèi)。,(1) 畫圖法,,,,,,0,2,3,y,x,對于某些看不清根的函數(shù)，可以擴大一下曲線,(1) 畫圖法,記筆記,A,,B,,(2) 逐步搜索法,(2) 搜索法,對于給定的f (x), 設(shè)有根區(qū)間為[A,B], 從x0=A出發(fā),以步長 h=(B-A)/n (n是正整數(shù)), 在[A,B]內(nèi)取定節(jié)點: xi=x0＋ih (i=0,1,2,…,n), 從左至右檢查f (xi

10、)的符號,如發(fā)現(xiàn) xi 與端點 x0 的函數(shù)值異號,則得到一個縮小的有根子區(qū)間［xi-1,xi］。,例1 方程f(x)=x3-x-1=0 確定其有根區(qū)間解：用試湊的方法，不難發(fā)現(xiàn) f(0)0 在區(qū)間（0，2）內(nèi)至少有一個實根 設(shè)從x=0出發(fā),取h=0.5為步長向右進行根的 搜索,列表如下,,,x,f(x),0 0.5 1.0 1.5 2,– – –

11、 + +,可以看出，在[1.0,1.5]內(nèi)必有一根,用逐步搜索法進行實根隔離的關(guān)鍵是選取步長h 要選擇適當h ，使之既能把根隔離開來，工作量 又不太大。 為獲取指定精度要求的初值,可在以上隔離根的 基礎(chǔ)上采用對分法繼續(xù)縮小該含根子區(qū)間。 二分法可以看作是搜索法的一種改進。,① 取有根區(qū)間[a,b]之中點, 將它分為兩半,分點 ,這樣就可

12、縮小有根區(qū)間。,5.1.2 二分法求根,,,,設(shè)方程f(x)=0在區(qū)間[a,b]內(nèi)有根,二分法就是逐步收縮有根區(qū)間，最后得出所求的根。具體過程如下：,,,,,,,,,② 對壓縮了的有根區(qū)間 施行同樣的手法, 即取中點 ,將區(qū)間 再分為 兩半,然后再確定有根區(qū)間 , 其長度是 的二分之一。 ③ 如此反復(fù)下去

13、,若不出現(xiàn) ,即可得出 一系列有根區(qū)間序列：,,,,,,,,,,,,,上述每個區(qū)間都是前一個區(qū)間的一半,因此 的長度：,,,,,,當k→∞時趨于零,這些區(qū)間最終收斂于一點 x* 即為所求的根 。,每次二分后,取有根區(qū)間 的中點作為根的近似值，得到一個近似根的序列： 該序列以根x*為極限　 只要二分足夠多次(即k足夠大),

14、便有這里ε為給定精度,由于 ,則：,,,,,,,,,,,,當給定精度ε＞0后,要想 成立,只要取k滿足 即可，亦即當:,,,,時,做到第 k+1 次二分,計算得到的 就是滿足精度要求的近似根 。 在程序中通常用相鄰的 與 的差的絕對值或 與 的差的絕對值是否小于ε來決定二分區(qū)間的次數(shù)。,,,,,,,,

15、二分法算法實現(xiàn),例2 證明方程 在區(qū)間[2, 3]內(nèi)有一個根 ,使用二分法求誤差不超過 0.5×10-3 的根要二分多少次？證明: 令 則,,,且 f(x) 在 [2, 3] 上連續(xù), 故方程 f(x)=0 在 [2,3]內(nèi)至少有一個根。 又 當

16、 時， 故 f(x) 在[2, 3]上是單調(diào)遞增函數(shù), 從而 f(x) 在[2, 3]上有且僅有一根。,誤差限為 只要取k滿足,,,,,,,,即可，亦即：,所以只需二分10次便可達到要求。,給定誤差限 ?＝ 0.5×10-3 ,使用二分法時，,,,,,,,,,,二分法的優(yōu)點是不管有根區(qū)間 多大,總能求出滿足精度

17、要求的根,且對函數(shù)f(x)的要求不高,只要連續(xù)即可,計算亦簡單。 它的局限性是只能用于求函數(shù)的實根,不能用于求復(fù)根及重根,它的收斂速度與比值為 的等比級數(shù)相同。,,,5.2 迭代法,,對于一般的非線性方程，沒有通常所說的求根公式來求其精確解，需要設(shè)計近似求解方法，即迭代法。 它是一種逐次逼近的方法，即用某個固定公式反復(fù)校正根的近似值，使之逐步精確化，最后得到滿足精度要求的結(jié)果。,,,即如果數(shù)

18、 使 f(x)=0, 則也有 ,反之, 若 ,則也有 , 稱 為迭代函數(shù) 任取一個初值 , 代入式 的右端, 得到：,,5.2.1 迭代法的基本思想 為求解非線性方程f(x)=0的根，先將其寫

19、成便于迭代的等價方程： (2.3)其中 為x的連續(xù)函數(shù)。,,,,,,,,,,,再將 代入式 的右端, 得到 依此類推, 得到一個數(shù)列：其一般表示為：,,,,式(5.4)稱為求解非線性方程的簡單迭代法。,(5.4),如果由迭代格式

20、 產(chǎn)生的序列 收斂,即 ：,,,則稱迭代法收斂。,實際計算中當然不可能也沒必要無窮多步地做下去, 對預(yù)先給定的精度要求ε，只要某個 k 滿足：,,即可結(jié)束計算并取,,迭代函數(shù) 的構(gòu)造方法是多種多樣的。,,例3 用迭代法求方程 在 x=1.5 附近的一個根。解 將方程改寫成如下兩種等價形式：,,,相應(yīng)地可得到兩個迭代公式：,,如果取初始值 ＝1.5，可用上述兩個迭代公式分別

21、進行迭代。,,5.2.2 迭代法的幾何意義,通常將方程 f(x)=0 化為與它同解的方程 的方法不止一種,有的收斂,有的不收斂,這取決于 的性態(tài),方程 的求根問題在幾何上就是確定曲線y= 與直線 y=x 的交點P*的橫坐標。,,,,(a),(b),,,5.2.3 迭代法收斂的條件 對方程 f(x)=0 可以構(gòu)造不同的迭代公式, 但迭代公式：并非

22、總是收斂的。那么,當?shù)瘮?shù) 滿足什么條件時，相應(yīng)的迭代公式才收斂呢？即使迭代收斂時，我們也不可能迭代很多次，而是迭代有限次后就停止，這就需要估計迭代值的誤差，以便適時終止迭代。,,,定理5.1 設(shè)函數(shù) 在[a,b]上具有連續(xù)的一階導(dǎo)數(shù), 且滿足： （1）對所有的 x∈[a,b] 有 ∈[a,b] （2）存在 0 < L< 1 , 使所有的

23、 x∈[a,b] 有 ≤ L則方程 在[a,b]上的解 存在且唯一，對任意的 ∈[a ,b] ，迭代過程均收斂于 。并有誤差估計式：,,,,,,,,,,①,②,,,由連續(xù)函數(shù)介值定理知, 必有 ∈[a, b], 使： 所以有

24、解存在, 即：假設(shè)有兩個解 和 , , ∈[a, b]，則有：,證: 構(gòu)造函數(shù) 由條件①，對任意的 x∈[a, b] ， ∈[a, b]有：,由微分中值定理有： 其中 ξ 是介于 x* 和 之間的點， 從而有 ξ∈[a,b]， 進而有：

25、 由條件(2) 有 <1, 所以 即 ，解唯一。,,,,,,,,,,,,,,,,,,,,,,,按迭代過程 ,有：,,,,,由于L<1,所以有： 可見L越小,收斂越快。,,,,∵,,,,,即,① 得證。,② 得證。,∴,∵,∴,

26、,5.2.4 迭代法的算法框圖,例4 對方程 ,構(gòu)造收斂的迭代格式, 求其最小正根,計算過程保留4位小數(shù)。解 容易判斷[1,2]是方程的有根區(qū)間, 且在此區(qū)間 內(nèi) ,所以此方程在區(qū)間[1,2] 有且僅有一根。將原方程改寫成以下兩種等價形式。,,,① ,即： 不滿足收斂條