第二章 方程求根

1、第二章 方程求根§2.0 引 言§2.1 二分法§2.2 簡單迭代法§2.3 牛頓（Newton）法§2.4 其它求根方法（迭代過程的加速方法）§2.5 作業(yè)講評§2.0引 言 非線性科學是當今科學發(fā)展的一個重要研究方向，非線性方程的求根也成為其中一個重要內容。一般而言，非線性方程的求根非常復雜。 在實際應用中有許多非線性方程的例子，例如（1）在光的衍射理論（the theory of diffraction of light)中,需要求x-tanx=0的根（2）在行星軌道（ planetary orbits）的計算中,對任

2、意的a和b，需要求x-asinx=b的根（3）在數(shù)學中，需要求n次多項式的根。非線性方程的一般形式 這里是單變量 的函數(shù)，它可以是代數(shù)多項式 ()也可以是超越函數(shù)，即不能表示為上述形式的函數(shù)。滿足方程 的x值通常叫做方程的根或解，也叫函數(shù)的零點。§2.1二分法(Bisection Method)1 概念:二分法也稱對分區(qū)間法、對分法等，是最簡單的求根方法，屬于區(qū)間法求根類型。在用近似方法時，需要知道方程的根所在區(qū)間。若區(qū)間a,b含有方程f(x)=0的根，則稱a,b為f(x)=0的有根區(qū)間；若區(qū)間a,b僅含方程f(x)= 0的一個根，則稱a,b為f(x)= 0的一個單根區(qū)間。2基本思想

3、 根的存在定理(零點定理)： f(x)為a,b上的連續(xù)函數(shù)，若 f(a)·f(b)<0，則a,b中至少有一個實根。如果f(x)在a,b上還是單調遞增或遞減的，則f(x)=0僅有一個實根。   3構造原理直接取區(qū)間a,b的中點x=(a +b)/2作為問題的近似解，那么我們可以估計出絕對誤差限僅為區(qū)間長的一半，即e=(b-a)/2。如果這個結果能滿足精度要求，我們就停止進一步的計算；如果不能，就求出f(x),結果只能是下面三種情況之一：（1） f(a)·f(x)<0，此時我們有x*a,x； （2） f(x)·f(b)<0

4、，此時我們有x*x,b；（3） f(x)=0，此時x即為問題的精確解。在前兩種情況下，我們可以用x分別替換原問題中的b或a,從而把求解的區(qū)間減小了一半。這樣我們又可以取新區(qū)間a,b的中點。經過N次迭代后，剩下的區(qū)間長為(b- a)/ 。這也是結果的絕對誤差限。如此繼續(xù)下去就達到是有根區(qū)間逐步縮小的目的，在這一些相互包含的子區(qū)間中構造收斂的數(shù)列來逼近根 。例求方程的有根區(qū)間.解根據(jù)有根區(qū)間定義，對方程的根進行搜索計算，結果如下表：方程的三個有根區(qū)間為1,2,3,4,5,6.非線性方程f(x)=0求根，包括求超越方程和代數(shù)方程的根x*,方程的根也是f(x)的零點，即f(x*)=0,x*可以是實根也

5、可以是復根，本章以求實根為主。求實根首先要確定根x*所在區(qū)間，稱為有根區(qū)間。根據(jù)連續(xù)函數(shù)性質，若f(x)在上連續(xù)，當f()f(b)<0時，為有根區(qū)間,為找到方程f(x)=0的有根區(qū)間,可用逐次搜索法,也就是在x的不同點上計算f(x),觀察f(x)的符號,如例2.1表中所示,只要在相鄰兩點f反號,則得到有根區(qū)間,本例得到三個有根區(qū)間,分別為1,23,45,6.4基本步驟假設f(x)=0，在區(qū)間a,b中只有一個根，且滿足f(a)f(b)<0，則利用二分法構造求根過程為： While(|a-b|>eps) x=(a+b)/2 計算f(x) 若(|f(x)|<eps) 則 x為

6、解 若f(x)*f(b)<0 修正區(qū)間為x,b 若f(a)*f(x)<0 修正區(qū)間為a,xEnd while 按上述步驟求根的方法稱為二分法，若記做了k次二分區(qū)間處理得到的有根區(qū)間為，則有二分法對應的求根數(shù)列算式為 , k=0,1,2,。5誤差估計與分析 第1步產生的有誤差 第 k 步產生的有誤差對于給定的精度 e ,可估計二分法所需的步數(shù) k ： 注：用二分法求根，最好先給出 f (x) 草圖以確定根的大概位置?；蛴盟阉鞒绦?，將a, b分為若干小區(qū)間，對每一個滿足 f (ak)·f (bk) < 0 的區(qū)間調用二分法程序，可找出區(qū)間a, b內的多個根，不必要求 f

7、 (a)·f (b) < 0 。6 例題例1 證明方程1xsinx0在區(qū)間0,1內有一個根，使用二分法求誤差不超過0.5×104的根要迭代多少次？證明 令f(x)1xsinx， f(0)=1>0，f(1)=sin1<0 f(x)=1xsinx=0在0，1有根.又 f¢(x)=1cosx>0(xÎ0.1),故f(x)0在區(qū)間0，1內有唯一實根.給定誤差限e0.5×10-4，有只要取n14. 例2： 已知 在有一個零點， ，用二分法計算結果如下：       

8、60;     n有根區(qū)間  11.0,2.01.52.37521.0,1.51.25-1.7968731.25,1.51.3750.1621141.25,1.3751.3125-0.8483951.3125,1.3751.34375-0.3509861.34375,1.3751.359375-0.0964171.359375,1.3751.36718750.0323681.359375,1.36718751.36328125-0.03215二分法的優(yōu)點：就是不管含根區(qū)間a , b多大總能求出滿足要求的根，且對函數(shù)的要求不高，計算簡單

9、；缺點：不能求重根，其收斂速度在數(shù)列xn越靠近根時越慢。二分法一般常用于為方程提供初始近似值當計算出的近似根比較準確時，再用其他方法對近似根做快速進一步精化。§2.2簡單迭代法1 不動點迭代法的思想 將方程 改寫成等價的形式 ，則的根 也滿足方程 ，反之亦然。稱為的不動點。而求 的根的問題就成為求的不動點問題。 2 不動點迭代法的基本過程 選取初值，以公式 進行迭代，稱為迭代函數(shù)，若收斂到，則 就是 的不動點，這種方法就稱為不動點迭代法。 將 轉化為的方法可以是多種多樣的，例： 在 上有以下方法：(1) (2) (3) (4) 取 ，有的收斂，有的發(fā)散，有的快，有的慢。例1： 用迭代

10、法求解方程(1) 將原方程化為等價方程顯然迭代法發(fā)散(2) 如果將原方程化為等價方程仍取初值依此類推,得 已經收斂,故原方程的解為.可以發(fā)現(xiàn),同樣的方程不同的迭代格式有不同的結果. 這與迭代函數(shù)的構造有關。迭代法是非線性方程求根中各類迭代法的基礎，其涉及的處理方法，概念和理論都易于推廣。 3 迭代法的幾何意義記 它們交點的橫坐標p即為方程的根。例2 用迭代法求方程x54x20的最小正根.計算過程保留4位小數(shù).分析 容易判斷1，2是方程的有根區(qū)間.若建立迭代格式,即 ,此時迭代發(fā)散.建立迭代格式 此時迭代收斂.解 建立迭代格式 取初值x0=1得: 取 4 迭代過程的收斂性 從前面的分析可知，收斂

11、的迭代數(shù)列xk的極限是方程f(x)的根，但計算機是不能做無窮次計算，因此迭代法一般只能求出具有任意固定精度的根的近似值，這樣在給定精度后，了解迭代進行的次數(shù)即何時終止迭代才能得到滿足要求的近似根就顯得非常重要。定理假設迭代函數(shù) (x), (x)ÎCa, b滿足下面條件:( I ) 當 xÎa, b 時，(x)Îa, b；( II ) $ 0 £ L < 1 使得 |(x) | £ L < 1 對 " xÎa, b 成立。則任取x0Îa, b，由xk+1 =(xk) 得到的序列收斂于(x) 在a, b上的

12、唯一不動點。并且有誤差估計式：. 2. 證：由迭代格式和條件，有 xk+1-xk|(xk)- xk|               |(xk)- (x*) +(x*)- xk|               | x*-xk-(xk)+(x*)|         &

13、#160;     | x*-xk|-|(xk)- (x*)|               | x*-xk|-L|xk- x*|               (1-L)| x*-xk|因為   0<L<1，所以有 另一方面， xk+1-xk|(xk)-(xk-1)|L

14、|xk-xk-1|                    證得結論1。反復應用上式結果，有xk+1-xkL|xk-xk-1| Lk |x1-x0|可以得到結論。證畢定理給出了收斂迭代數(shù)列xk的誤差估計式，利用它，在給定精度后，要使| x*-xk|，只要計算到或 第一式可以得到迭代次數(shù)的值應取多大，但這樣得到的值往往偏大，第二式是用剛算出的數(shù)列來估計誤差的，它可用較小的迭代運算但到滿足精度的近似解。特別當 L

15、時，有不等式            | x* -xk|xk-xk-1 |此時可用更簡單的不等式  |xk-xk-1 | 成立與否終止迭代，由于這個判別具有簡單易處理特點。實用中，一般不管是否有 L成立，都用|xk-xk-1 |是否小于某個充分小的數(shù)來作為終止條件，它通常也能求出滿足精度的根。 注：定理條件很難保證，可將a, b縮小，定義局部收斂性：若在 x* 的某d 領域 Bd = x | | x - x* | £ d 有ÎC1a, b 且 |(x*) | <

16、 1，則由"x0ÎBd 開始的迭代收斂。即調整初值可得到收斂的結果。簡單迭代法的優(yōu)點是理論豐富算法簡單，易于推廣；缺點是不易找到收斂最快迭代函數(shù)和局部收斂。簡單迭代法主要用于迭代的理論分析上。§2.3 牛頓(Newton)法1 基本思想:將非線性方程逐步線性化而形成迭代公式 Taylor 展開.取的近似根，將f (x)在點做一階Taylor展開: 將看成高階小量，則 于是可得著名的牛頓迭代公式： 相應的迭代函數(shù)為 2 牛頓法幾何意義是：(牛頓法亦稱切線法) 只要 f ÎC1，每一步迭代都有f '( xk ) ¹ 0，而且 ，則 x*就是

17、 f 的根。牛頓迭代公式算法1: 初始化. x0, M,置i:=02: 如果|f(xi)|，則停止. 3: 計算xi+1:=xi-f(xi)/f'(xi)4: 如果|xi+1-xi|< OR |f(xi)|，則停止.5: i:=i+1, 轉至3.例1： 求解f(x)=ex-1.5-tan-1x 的零點。（初始點x0=-7.0）解： f'(x)=-0.702×10-1，f '(x)=ex-(1+x2)-1 計算結果如下表：(取|f(x)<=10-10|)k x f(x) 0 -7.0000 -0.07018881 -10.6771 -0.022566

18、62 -13.2792 -0.004366023 -14.0537 -0.000239024 -14.1011 -7.99585e-0075 -14.1013 -9.00833e-012注：Newton's Method 收斂性依賴于x0 的選取。 例2： 求解的近似值，精度為。（初始點x0=10）解: 該問題可轉化為求解二次方程： x2-115=0的正根，相應的牛頓迭代公式為: 取初值x0=10,經3次迭代得近似值: k x f(x)0 10 -151 10.75 0.56252 10.7238 0.0006844923 10.7238 1.01852e-0093牛頓下山法 其中，稱

19、為下山因子，為保證迭代過程中下山成功，即使|f(xk)|>|f(xk+1)|成立，必須選取適當?shù)南律揭蜃? 取中依次挑取下山因子.Newton法是一種局部收斂方法，通常要求初始近似在解附近才保證迭代序列收斂.為擴大收斂范圍，使對任意迭代序列收斂，通常可引入?yún)?shù)，并將Newton迭代改為 其中，稱為下山因子，式(2.4.4)稱為Newton下山法.通?？蛇x擇使，計算時可取,直到滿足要求為止.由此得到的序列由于滿足下山條件，故它是收斂的，但它只是線性收斂.例 用Newton下山法求的解，取=0.6，計算精確到解 由于,由式(2.4.4)得Newton下山法為,若=1.5用Newton法(=1)迭代3步則求得解的近似=1.324 72.現(xiàn)用=0.6，用=1,則得=17.9,且f(0.6)=-1.384,而不滿足下山條件.通過試算，當時，滿足以下計算時參數(shù),且當Newton法不收斂時，使用Newton下山法.具體做法是取，每次縮減成一半，并檢驗是否成立，若成立則做下一步.