非線性方程的數值求法

1、非線性方程的數值求法第1頁，共74頁，2022年，5月20日，3點40分，星期四記筆記 當f(x)不是x的線性函數時，稱對應的函數方程為非線性方程。如果f(x)是多項式函數，則稱為代數方程，否則稱為超越方程（三角方程，指數、對數方程等）。一般稱n次多項式構成的方程 為n次代數方程,當n1時,方程顯然是非線性的 一般稍微復雜的3次以上的代數方程或超越方程,很難甚至無法求得精確解。本章將介紹常用的求解非線性方程的近似根的幾種數值解法 第2頁，共74頁，2022年，5月20日，3點40分，星期四記筆記 通常方程根的數值解法大致分為三個步驟進行判定根的存在性。即方程有沒有根？如果有 根，有幾個根？ 確

2、定根的分布范圍。即將每一個根用區(qū)間隔 離開來，這個過程實際上是獲得方程各根的 初始近似值。 根的精確化。將根的初始近似值按某種方法 逐步精確化，直到滿足預先要求的精度為止 第3頁，共74頁，2022年，5月20日，3點40分，星期四本章介紹方程的迭代解法，它既可以用來求解代數方程，也可以用來解超越方程，并且僅限于求方程的實根。運用迭代法求解方程的根應解決以下兩個問題：確定根的初值;將進一步精確化到所需要的精度。記筆記第4頁，共74頁，2022年，5月20日，3點40分，星期四7.1 二分法 二分法又稱二分區(qū)間法,是求解方程(5.1)的近似根的一種常用的簡單方法。 設函數f(x)在閉區(qū)間a,b上

3、連續(xù),且f(a)f(b)0,根據連續(xù)函數的性質可知, f(x)= 0在(a,b)內必有實根,稱區(qū)間a,b為有根區(qū)間。為明確起見,假定方程f(x)=0在區(qū)間a,b內有惟一實根x*。 二分法的基本思想是: 首先確定有根區(qū)間,將區(qū)間二等分, 通過判斷f(x)的符號, 逐步將有根區(qū)間縮小, 直至有根區(qū)間足夠地小, 便可求出滿足精度要求的近似根。第5頁，共74頁，2022年，5月20日，3點40分，星期四確定有根區(qū)間的方法 為了確定根的初值，首先必須圈定根所在的范圍， 稱為圈定根或根的隔離。 在上述基礎上，采取適當的數值方法確定具有一定 精度要求的初值。 對于代數方程，其根的個數（實或復的）與其次數 相

4、同。至于超越方程，其根可能是一個、幾個或無 解，并沒有什么固定的圈根方法 求方程根的問題，就幾何上講,是求曲線 y=f (x)與 x軸交點的橫坐標。第6頁，共74頁，2022年，5月20日，3點40分，星期四 由高等數學知識知, 設f (x)為區(qū)間a,b上的單值連續(xù), 如果f (a)f (b)0 , 則a,b中至少有一個實根。如果f (x)在a,b上還是單調地遞增或遞減，則僅有一個實根。記筆記由此可大體確定根所在子區(qū)間，方法有： (1) 畫圖法 (2) 逐步搜索法y=f(x)abyx第7頁，共74頁，2022年，5月20日，3點40分，星期四(1) 畫圖法 畫出y = f (x)的略圖，從而看

5、出曲線與x軸交點的 大致位置。 也可將f (x) = 0分解為1(x)= 2(x)的形式，1(x) 與 2(x)兩曲線交點的橫坐標所在的子區(qū)間即為含根 區(qū)間。例如 xlogx-1= 0可以改寫為logx=1/x畫出對數曲線y=logx,與雙曲線y= 1/x,它們交 點的橫坐標位于區(qū)間2,3內第8頁，共74頁，2022年，5月20日，3點40分，星期四(1) 畫圖法023yx第9頁，共74頁，2022年，5月20日，3點40分，星期四對于某些看不清根的函數，可以擴大一下曲線y0 xy=f(x)y=kf(x)(1) 畫圖法記筆記第10頁，共74頁，2022年，5月20日，3點40分，星期四y0 x

6、ABa1b1a2b2(2) 逐步搜索法(2) 搜索法 對于給定的f (x),設有根區(qū)間為A,B,從x0=A出發(fā),以步長h=(B-A)/n(n是正整數),在A,B內取定節(jié)點:xi=x0ih (i=0,1,2,n),從左至右檢查f (xi)的符號,如發(fā)現(xiàn)xi與端點x0的函數值異號,則得到一個縮小的有根子區(qū)間xi-1,xi。第11頁，共74頁，2022年，5月20日，3點40分，星期四例1 方程f(x)=x3-x-1=0 確定其有根區(qū)間解：用試湊的方法，不難發(fā)現(xiàn) f(0)0 在區(qū)間（0，2）內至少有一個實根 設從x=0出發(fā),取h=0.5為步長向右進行根的 搜索,列表如下xf(x)0 0.5 1.0

7、1.5 2 + +可以看出，在1.0,1.5內必有一根第12頁，共74頁，2022年，5月20日，3點40分，星期四 用逐步搜索法進行實根隔離的關鍵是選取步長h 要選擇適當h ，使之既能把根隔離開來，工作量 又不太大。 為獲取指定精度要求的初值,可在以上隔離根的 基礎上采用對分法繼續(xù)縮小該含根子區(qū)間 二分法可以看作是搜索法的一種改進。第13頁，共74頁，2022年，5月20日，3點40分，星期四 取有根區(qū)間a,b之中點, 將它分為兩半,分點 ,這樣就可縮小有根區(qū)間7.1.2 二分法求根過程 設方程f(x)=0在區(qū)間a,b內有根,二分法就是逐步收縮有根區(qū)間，最后得出所求的根。具體過程如下 第14

8、頁，共74頁，2022年，5月20日，3點40分，星期四 對壓縮了的有根區(qū)間 施行同樣的手法, 即取中點 ,將區(qū)間 再分為兩半,然 后再確定有根區(qū)間 ,其長度是 的 二分之一 如此反復下去,若不出現(xiàn) ,即可得出一 系列有根區(qū)間序列： 上述每個區(qū)間都是前一個區(qū)間的一半,因此 的長度 當k時趨于零,這些區(qū)間最終收斂于一點x* 即為 所求的根 。第15頁，共74頁，2022年，5月20日，3點40分，星期四每次二分后,取有根區(qū)間 的中點作為根的近似值，得到一個近似根的序列 該序列以根x*為極限 只要二分足夠多次(即k足夠大),便有這里為給定精度,由于 ,則 第16頁，共74頁，2022年，5月20日

9、，3點40分，星期四當給定精度0后,要想 成立,只要取k滿足 即可，亦即當: 時,做到第k+1次二分,計算得到的 就是滿足精度要求的近似根 。 在程序中通常用相鄰的 與 的差的絕對值或 與 的差的絕對值是否小于來決定二分區(qū)間的次數。 第17頁，共74頁，2022年，5月20日，3點40分，星期四 二分法算法實現(xiàn)第18頁，共74頁，2022年，5月20日，3點40分，星期四例 求方程f(x)=x3-x-1=0 在區(qū)間1.0,1.5內 的一 個實根, 使誤差不超過0.510-2。P215例 證明方程 在區(qū)間2, 3內有一個根 , 使用二分法求誤差不超過0.510-3 的根要二 分多少次？證明 令

10、且f(x)在2, 3上連續(xù),故方程f(x)=0在2,3內至少有一個根。又 當時 時， ,故f(x)在2, 3上是單調遞增函數,從而f(x)在2, 3上有且僅有一根。 給定誤差限 0.510-3 ,使用二分法時第19頁，共74頁，2022年，5月20日，3點40分，星期四 誤差限為 只要取k滿足 即可，亦即 所以需二分10次便可達到要求。 二分法的優(yōu)點是不管有根區(qū)間 多大,總能求出滿足精度要求的根,且對函數f(x)的要求不高,只要連續(xù)即可,計算亦簡單;它的局限性是只能用于求函數的實根,不能用于求復根及重根,它的收斂速度與比值為 的等比級數相同。 第20頁，共74頁，2022年，5月20日，3點4

11、0分，星期四7.2 不動點迭代法及其收斂性 對于一般的非線性方程,沒有通常所說的求根公式求其精確解,需要設計近似求解方法,即迭代法。它是一種逐次逼近的方法,用某個固定公式反復校正根的近似值,使之逐步精確化，最后得到滿足精度要求的結果。7.2.1 迭代法的基本思想 為求解非線性方程f(x)=0的根，先將其寫成便于迭代的等價方程 (5.3)其中 為x的連續(xù)函數第21頁，共74頁，2022年，5月20日，3點40分，星期四即如果數 使f(x)=0, 則也有 , 反之, 若 , 則也有 , 稱 為迭代函數 .任取一個初值 , 代入式 的右端, 得到 再將 代入式 的右端, 得到 ,依此類推, 得到一個

12、數列 ， 其一般表示 式(5.4)稱為求解非線性方程的簡單迭代法。 (5.4)第22頁，共74頁，2022年，5月20日，3點40分，星期四如果由迭代格式 產生的序列 收斂,即 則稱迭代法收斂。 實際計算中當然不可能也沒必要無窮多步地做下去, 對預先給定的精度要求，只要某個k滿足即可結束計算并取 當然，迭代函數 的構造方法是多種多樣的。第23頁，共74頁，2022年，5月20日，3點40分，星期四例4 用迭代法求方程 在x=1.5附近的一個根解 將方程改寫成如下兩種等價形式 相應地可得到兩個迭代公式如果取初始值 1.5，用上述兩個迭代公式分別迭代，計算結果第24頁，共74頁，2022年，5月2

13、0日，3點40分，星期四kxk012345671.51.357211.330861.325881.324941.324761.324731.32472第25頁，共74頁，2022年，5月20日，3點40分，星期四7.2.2 迭代法的幾何意義 通常將方程f(x)=0 化為與它同解的方程的方法不止一種,有的收斂,有的不收斂,這取決于 的性態(tài),方程 的求根問題在幾何上就是確定曲線y= 與直線y=x的交點P*的橫坐標(圖7-2所示) (a)(b)第26頁，共74頁，2022年，5月20日，3點40分，星期四圖7-2 迭代法的幾何意義 第27頁，共74頁，2022年，5月20日，3點40分，星期四7.2

14、.3 迭代法收斂的條件 對方程f(x)=0可以構造不同的迭代公式, 但迭代公式并非總是收斂。那么,當迭代函數 滿足什么條件時，相應的迭代公式才收斂呢？即使迭代收斂時，我們也不可能迭代很多次，而是迭代有限次后就停止，這就需要估計迭代值的誤差，以便適時終止迭代 第28頁，共74頁，2022年，5月20日，3點40分，星期四定理1 .2 設函數 在a,b上具有連續(xù)的一階導數, 且滿足（1）對所有的xa,b 有 a,b（2）存在 0 L 1 ,使所有的xa,b有 L則方程 在a,b上的解 存在且唯一，對任意的 a ,b ，迭代過程均收斂于 。并有誤差估計式 第29頁，共74頁，2022年，5月20日，

15、3點40分，星期四由連續(xù)函數介值定理知, 必有 a, b, 使 所以有解存在, 即假設有兩個解 和 , , a, b，則 由微分中值定理有其中是介于 和 之間的點 從而有a,b，進而有 由條件(2)有 1, 所以 - =0，即 = ，解唯一。證: 構造函數 ,由條件對任意的xa, b a, b有第30頁，共74頁，2022年，5月20日，3點40分，星期四按迭代過程 ,有 由于L0），使 則稱序列 是 p 階收斂的,c稱漸近誤差常數。特別地,p=1時稱為線性收斂,p=2時稱為平方收斂。1 p 0 xn+1X*ayx0Bf(x)0a=x0yx0B=x0f(x)0ayx0Bf(x)0a =x0第5

16、1頁，共74頁，2022年，5月20日，3點40分，星期四yx10 x0X*0 x0X*x2 不滿足迭代條件時，可能導致迭代值遠離根的情況而找不到根或死循環(huán)的情況第52頁，共74頁，2022年，5月20日，3點40分，星期四7.4.4 牛頓迭代法的算法實現(xiàn)第53頁，共74頁，2022年，5月20日，3點40分，星期四例 1 1 用牛頓迭代法求 x=e-x的根,=10-4解：因 f (xk)= x ex 1 , f (x)=ex ( x+1)建立迭代公式取x0=0.5,逐次計算得 x1=0.57102, x2=0.56716， x3=0.56714第54頁，共74頁，2022年，5月20日，3點

17、40分，星期四7.4.5 牛頓下山法 通常,牛頓迭代法的收斂性依賴于初始值 的選取,如果 偏離所求的根 比較遠,則牛頓法可能發(fā)散。為了防止迭代發(fā)散,我們對牛頓迭代法的迭代過程再附加一項要求,即具有單調性 將牛頓迭代法與下山法結合起來使用,即在下山法保證函數值下降的前提下,用牛頓迭代法加快收斂速度。把這一算法稱為牛頓下山法。即滿足這項要求的算法稱下山法。其中(01)為下山因子 第55頁，共74頁，2022年，5月20日，3點40分，星期四 下山因子的選擇是個逐步探索的過程，設從=1開始反復將減半進行試算, 即逐次取為從中挑選下山因子，直至找到其中某個使單調性條件成立，則稱“下山成功”，否則“下山

18、失敗”，這時需另選初值重算。第56頁，共74頁，2022年，5月20日，3點40分，星期四重根情形第57頁，共74頁，2022年，5月20日，3點40分，星期四第58頁，共74頁，2022年，5月20日，3點40分，星期四kxk(1)(2)(3)0123x0 x1x2x31.51.4583333331.4366071431.4254976191.51.4166666671.4142156861.4142135621.51.4117647061.4142114381.414213562第59頁，共74頁，2022年，5月20日，3點40分，星期四7.5 弦截法 牛頓迭代法雖然具有收斂速度快的優(yōu)點

19、，但每迭代一次都要計算導數 , 當 比較復雜時, 不僅每次計算 帶來很多不便，而且還可能十分麻煩，如果用不計算導數的迭代方法，往往只有線性收斂的速度。本節(jié)介紹的弦截法便是一種不必進行導數運算的求根方法。弦截法在迭代過程中不僅用到前一步 處的函數值，而且還使用 處的函數值來構造迭代函數，這樣做能提高迭代的收斂速度。第60頁，共74頁，2022年，5月20日，3點40分，星期四 7.5.1 弦截法的基本思想 為避免計算函數的導數 ，使用差商 替代牛頓公式中的導數 ,便得到迭代公式 稱為弦截迭代公式， 相應的迭代法稱為弦截法。第61頁，共74頁，2022年，5月20日，3點40分，星期四7.5.2

20、弦截法幾何意義弦截法也稱割線法,其幾何意義是用過曲線上兩點 、 的割線來代替曲線,用割線與x軸交點的橫座標作為方程的近似根 再過P1點和點 作割線求出 ,再過P2點和點 作割線求出 ,余此類推，當收斂時可求出滿足精度要求的第62頁，共74頁，2022年，5月20日，3點40分，星期四 可以證明，弦截法具有超線性收斂，收斂的階約為1.618，它與前面介紹的一般迭代法一樣都是線性化方法，但也有區(qū)別。即一般迭代法在計算 時只用到前一步的值 ,故稱之為單點迭代法；而弦截法在求 時要用到前兩步的結果 和 ，使用這種方法必須給出兩個初始近似根 ，這種方法稱為多點迭代法。 第63頁，共74頁，2022年，5月20日，3點40分，星期四例 12 用弦截法求方程 在 初始 值鄰近的一個根。要求解：取 , , 令 利用弦截迭代公式 計算結果， 易見取近似根 則可滿足精度要求。第64頁，共74頁，2022年，5月20日，3點40分，星期四7.5.3 弦截