第二章 一元非線性方程的數(shù)值解法

1、第二章 一元非線性方程的數(shù)值解法 其次章 一元非線性方程的數(shù)值解法 在科學(xué)和工程計算中，如電路和電力系統(tǒng)計算、非線性微分和積分方程、非線性規(guī)劃、非線性力學(xué)等眾多領(lǐng)域中，常常會遇到求解非線性方程的問題非線性科學(xué)是當(dāng)今科學(xué)進展的一個重要的討論方向，而非線性方程的數(shù)值解法又是其中不行缺少的內(nèi)容 本章主要爭論一元非線性方程 f(x) 0 (5.0.1) 的數(shù)值解法，其中x r，f(x)為x的非線性函數(shù) 在方程(5.0.1)中，若函數(shù)f(x)是x的n次多項式，則稱方程(5.0.1)為多項式方程或代數(shù)方程： 3x x x 2 0 8 6 3 ；若函數(shù)f(x)是超越函數(shù)（自變量之間的 關(guān)系不能用有限次加、減

2、、乘、除、乘方、開方 運算表示的函數(shù)。如指數(shù)函數(shù)、對數(shù)函數(shù)、三角函數(shù)和反三角函數(shù)等都是超越函數(shù)），則稱方程(5.0.1)為超越方程：例e tan 6x 0 使f(x) 0的x稱為方程f(x) 0的根，又稱為函數(shù)f(x)的 3x * 零點若f(x)可分解為 其中m為正整數(shù)，且g(x f(x) =(x x * )g(x) * m ， 當(dāng)m=1時，稱x為方程f(x) 0 * ) 0 的單根，而當(dāng)m 1時，則稱x為方程f(x) 0的m重根，或 * 稱x為f(x)的m重零點設(shè)x為f(x)的m重零點，且g(x)充 * * 分光滑，則 . 根的求解：對于n次多項式方程，當(dāng)次數(shù)n 4時， * f(x) f (

3、x) f (m 1) (x) 0 * ，f (m) (x) 0 * 多項式方程的根可用求根公式表示：n 1,2時方程的根是我們已經(jīng)熟知的，n 3,4時雖然有求根公式，但已不適合用于數(shù)值計算；而次數(shù)n 5時，就不能用公式表示多項式方程的根了因此，對于次數(shù)n 3的多項式方程和一般連續(xù)函數(shù)方程(5.0.1)，在實際應(yīng)用時，通常并不需要得到方程根的解析表達式，只要得到滿意肯定精度的數(shù)值近似根就可以了 對于非線性方程f(x) 0，求其近似數(shù)值根一般分為四步： (1) 推斷根的存在性：推斷方程f(x) 0是否有根？若有，有幾個？ (2) 確定根的分布范圍：分析并估量方程根的分布狀況，并將每一個根用相應(yīng)區(qū)間

4、分隔開，即確定方程根的有根區(qū)間； (3) 根的初始化：確定根的初始近似值(稱之為初始近似根)； (4) 根的精確化：對根的某個初始近似值設(shè)法逐 步精確化，使其滿意肯定的精度要求 由以上步驟可以看出，求非線性方程數(shù) 值近似根的方法一般為迭代法 第一節(jié) 初始近似根的確定 一、有根區(qū)間的確定 設(shè)f(x)為區(qū)間a,b上的連續(xù)函數(shù)，若f(a)f(b) 0，由閉區(qū)間上連續(xù)函數(shù)的性質(zhì)（根的存在定理）可知，方程 f(x) 0f(x) 0 在(a,b)內(nèi)至少存在一個實根，此時則稱a,b為方程的有根區(qū)間(rooted inter-val) 此外我們也可以借助某些數(shù)學(xué)軟件(如mathcad, mathematics

5、, matlab等)描繪出f(x)的圖像，直觀地了解方程f(x) 0根的分布狀況因此，我們可用摸索的方法或依據(jù)函數(shù)的圖象，確定出根的分布范圍，即將函數(shù)f(x)的定義域分成若干個只含一個實根的區(qū)間 例5.1 試確定方程f(x) x解 由于f (x) 6x 5 6 x 1 0 的有根區(qū)間. 1 ，當(dāng)x 5 16 時f (x) 0，則f(x)為嚴 格單調(diào)增函數(shù)；而當(dāng)x 減函數(shù)又由于 16 時f (x) 0，則f(x)為嚴格單調(diào)， f( ) 0 1 0f 6 ，所以方程 f(x) x x 1 0 6 只有兩個實根 經(jīng)進一步分析可知，f(1)f(2) 0，則方程在1，2內(nèi)有一個實根；f( 1)f(0)

6、0，則方程的另一個實根在-1，0內(nèi). 下面介紹的幾種求方程的根的常用數(shù)值解法，即二分法，牛頓迭代法，都是將方程的初始近似根逐步精確化的方法 其次節(jié) 二分法 二分法也稱為區(qū)間對分法，是解非線性方程最直觀、最簡潔的方法 為爭論便利，不妨設(shè)函數(shù)f(x)在a,b上連續(xù)，嚴格單調(diào)，且f(a)f(b) 0，則方程f(x) 0在區(qū)間a,b內(nèi)有且僅有一個實根x 二分法的基本思想：將方程的有根區(qū)間平分為兩個小區(qū)間，然后推斷根在哪個小區(qū)間，舍去無根小區(qū)間，而后再把有根的小區(qū)間一分為二，推斷根屬于哪個更小的區(qū)間，如此反復(fù)，直到求出滿意精度要求的近似根 二分法的詳細計算過程如下： 1. 取區(qū)間a,b的中點x 12 (

7、a b) ，計算區(qū)間中點函數(shù) 值f(x)，并推斷： 若f(a)f(x若f(x ) 0 ，則根x a,x0 ，令a 1 a,b1 x0 ，則新的有 根區(qū)間為a,b； 1 1 ) 0 ，則x即為所求根x； 若f(a)f(x ) 00 ，則根x 1 x0,b ，令a 1 x0,b1 b ，則新的 有根區(qū)間為a,b 1 圖5.2 二分法示意圖 2. 對有根區(qū)間a,b施行同樣的操作，即取中點 1 1 x1 12 (a1 b1) ，再將a,b分為兩個子區(qū)間a,x和x,b，計 1 1 1 1 1 1 1 算f(a)和f(x)，若 1 f(a1)f(x1) 0 x1,b1 則x a1,x1 ，令a 2 a1,

8、b2 x1 ；否則x 2 ，令a 2 x1,b2 b1 這 1 樣又確定了一個有根區(qū)間a度的一半 ,b2 ，其長度是區(qū)間a,b長 1 如此反復(fù)，便得到一系列有根區(qū)間 a,b a,b a,b a,b 1 1 2 2 n n 明顯，區(qū)間a n ,bn 的長度為 2 b a2 n bn an bn 1 an 1 (5.2.1) 當(dāng)n 時，上式的極限為0，區(qū)間a k ,bk 最終必收斂于一 點, 該點就是所求方程(5.0.1)的根x 我們?nèi)《趾蟮淖罱K的有根區(qū)間a為方程(5.0.1)的根x的近似根 n ,bn 的中點x作 n xn an bn 2 ，x n an,bn ， 其誤差估量式為 |x當(dāng)n 時

9、，取|x * xn| bn an 2bn an 2 b a2 n 1 (5.2.2) n xn| 0 ，即x x * 對預(yù)先給定的精度 0(即指定的肯定誤差限 )，可以用以下方式結(jié)束二分法： 當(dāng)|b取x n 1 an 1| 時，必有|x xn| ，結(jié)束二分法計算， xn ； 二分法的計算步驟如下： (1) 輸入有根區(qū)間的端點a,b及預(yù)先給定的精度 ； (2) x: (a b)/2； (3) 若 f(a)f(x) 0 ，則b: x，轉(zhuǎn)向(4)；否則a: x，轉(zhuǎn) 向(4)； (4) 若b a ，則輸出方程滿意精度的根x，結(jié)束；否則轉(zhuǎn)向(2) 二分法的優(yōu)點： 1、是算法簡潔； 2、對函數(shù)的性質(zhì)要求較

10、低(只要連續(xù)即可)； 3、收斂性可保證 二分法的缺點： 1、收斂速度很慢； 2、不能求偶數(shù)重根，緣由在于當(dāng)方程(5.0.1)有偶數(shù)重根時所分區(qū)間端點處函數(shù)值同號，而將該區(qū)間舍去造成失根現(xiàn)象 因此在實際應(yīng)用時，可用它求方程根的初始近似值 例5.2 用二分法求方程f(x) x(取 10) 3 3 x 1 0 2 在0,1上的根 解(1) 這里a 0,b 1， f(0) 1 0, 0,1 f(1) 1 0 ，得有根區(qū)間 ； (2) 計算x(3) 計算x 0 122 0.5,f(0.5) 0.125 0 ，得有根區(qū)間0.5,1； 得有根區(qū)間0.75,1； 0.5 1 2 0.75,f(0.75) 0.

11、01563 0 xk 1 10 3 如此連續(xù)，直到x 5.1： k 時停止，計算結(jié)果見表 表5.1 由表5.1知 x9 x8 0.00098 10 3 所以原方程在0,1內(nèi)的根x * x9 0.75489 第三節(jié) 牛頓迭代法及其收斂性 迭代法在數(shù)學(xué)的各個分支都有著重要的應(yīng)用本節(jié)主要爭論迭代法在非線性方程求根的應(yīng)用 一、迭代法的基本思想 迭代法的基本思想是：將方程(5.0.1)中f(x) 0化為下列等價形式 x g(x) (5.3.1) 若要求x滿意f(x * * ) 0 ，則只需求出x * g(x) * 即可；反之 也是如此，則稱x為函數(shù)g(x)的一個不動點，求函數(shù)f(x) * 的零點就等價于

12、求函數(shù)g(x)的不動點在有根區(qū)間內(nèi)選一個初始近似值x，然后按(5.3.1)構(gòu)造公式 x k 1 g(xk),k 0,1,2, (5.3.2) 可得到一個數(shù)列 x k ,x1,x2, ,xk, 稱 x 為迭代序列，而稱(5.3.1)式中的g(x)為迭代函數(shù)假如迭代序列 x 是收斂的，且收斂于x，則當(dāng)g(x) * k 連續(xù)時，在(5.3.2)式兩邊取極限即得x f(x) 0 * * g(x) * ，即 從而x便是方程(5.0.1)的根但實際計算當(dāng)然不行能 * 做無窮多步，有用上，當(dāng)k充分大時，若 x x k k 1 就取x作為原方程的近似根這種求根法稱為不動點 k 迭代法，或稱逐次靠近法(pica

13、rd迭代法)(5.3.2)就是一個不動點迭代公式當(dāng)?shù)?5.3.2)產(chǎn)生的迭代序列 x 收斂時，就稱迭代法或迭代公式(5.3.2) k 是收斂的，否則就稱為是發(fā)散的 二、不動點迭代法的構(gòu)造 我們使用迭代法求解非線性方程(5.0.1)時需要解決如下四個問題：(1) 迭代函數(shù)的構(gòu)造；(2) 初始近似根的選??；(3) 迭代序列收斂性分析；(4) 收斂速度和誤差分析 三、牛頓迭代法及其收斂性 設(shè)x是一元非線性方程f(x) 0的根，函數(shù)f(x)在x的 * 某鄰域內(nèi)連續(xù)可微， f (xk) 0 k xk 是某個迭代近似根，且 k 把f(x)在點x處進行一階泰勒綻開，可得 f(xk) f (xk)(x

14、xk) f(x) 則方程f(x) 0可近似表示為 f(x ) f (xk)(x xk) 0 (5.3.3) 這是一個線性方程，求解得 x x k f(xk)f (xk) k 1 將其右端項作為新的迭代值x，則可得迭代公式 xk 1 xk f(xk)f (xk) k 0,1,2, (5.3.4) 這就是牛頓迭代法(newtons method)，(5.3.4)稱為牛頓迭代公式. 如圖5.3所示，曲線y f(x)與x軸的交 點x就是方程f(x) 0的根設(shè)x是方程 圖5.3 切線法示意圖 f(x) 0的一個近似根，過曲線y f(x)上的 k 點p(x k k ,f(xk) 作切線，切線與x軸的交點為

15、x,切線的方 k 1 程為 y f(xk) f (xk)(x xk) k 設(shè)切線點與x軸的交點為(x牛頓迭代公式(5.3.4) xk 1 xk k 1 ,0) ，若f (x ) 0 ，則可得 f(xk)f (xk) ,k 0,1,2, 因此，牛頓迭代法又稱為切線法(tangent method) 牛頓迭代法的幾何意義：用曲線y f(x)在點(x k 1 k ,f(xk) 處 的切線與x軸的交點的橫坐標x來代替曲線y f(x)與x軸交點的橫坐標x 牛頓迭代法的計算步驟為： (1) 給出初始近似根x及精度 ； (2) 計算x (3) 1 : x0 f(x0)f (x0) ； 1 對于給定的允許誤差

16、 ，若x x0 , 轉(zhuǎn)向(4)； 否則x : x1 ,轉(zhuǎn)向(2)； 1 (4) 輸出滿意精度的根x，結(jié)束 例5.3 用牛頓迭代法求方程xe根，精度為 10 8 x 1 0 在x 0.5四周的 解 這里f(x) xe式為 x 1 ,f (x) e x xe x ，相應(yīng)的牛頓迭代公 表5.3k 0,1,2, 取x 0.5，迭代結(jié)果見表5.3，易見 |x x| 0.00000001 10 0 xk 1 xk xkee xk xk 1 xk xke xk xk e xk 1 xk , 8 43 故 x x4 0.567143290 迭代了4次就得到了較滿足的結(jié)果 例5.4 用牛頓法計算3 解 令x 3 2 f(x) x ，則x 3 0 2 3 0 ，即求3等價于求方程 的正實根由于f (x) 2x，由牛頓迭代公式得