的零點(diǎn)。-read

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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