計算方法中對分法和一般迭代法

1、數(shù)值分析數(shù)值分析第二章第二章 非線性方程的數(shù)值解法非線性方程的數(shù)值解法 簡介（Introduction） 我們知道在實際應(yīng)用中有許多非線性方程的例子，例如 （1）在光的衍射理論（the theory of diffraction of light)中,我們需要求x-tanx=0的根 （2）在行星軌道（ planetary orbits）的計算中,對任意的a和b，我們需要求x-asinx=b的根 （3） 在數(shù)學(xué)中，需要求n次多項式xn + a1 xn-1+.+an-1 x + an 0的根求求f(x)=0f(x)=0的根的根2.1 對分區(qū)間法對分區(qū)間法 (Bisection Method )原理

2、：原理：若若 f(x) Ca, b，且且 f (a) f (b) 0，則則f(x) 在在 (a, b) 上必有一根。上必有一根。abx1x2a1b2x*b1a2停機(jī)條件（termination condition ）：11xxkk 2)(xf 或或誤差誤差 分析：分析：第第1步產(chǎn)生的步產(chǎn)生的21bax 有誤差有誤差21abx*|x 第第 k 步產(chǎn)生的步產(chǎn)生的 xk 有誤差有誤差kkabx*|x2 對于給定的精度對于給定的精度 ,可估計二分法所需的步可估計二分法所需的步數(shù)數(shù) k ： 2lnlnln2abkabk 用二分法求用二分法求 在在(1,2)(1,2)內(nèi)的根，要求絕對誤差不超過內(nèi)的根，要求

3、絕對誤差不超過 ： f(1)=-50 -(1,2)+ f(1.25)0 (1.25,1.375) f(1.313)0 (1.313,1.375) f(1.344)0 (1.344,1.375) f(1.360)0 (1.360,1.368) 010423 xx21021 f(1.5)0 (1,1.5) nx 1.51 x364. 1368. 1360. 1344. 1313. 1375. 125. 18765432 xxxxxxx12 例2，求方程f(x)= x 3 e-x =0的一個實根。 因為 f(0)0。 故f(x)在(0,1)內(nèi)有根用二分法解之，(a, b)=(0, 1), 計算結(jié)果如

4、表：k ak bk xk f(xk)符號00 1 0.5000 10.5000 0.7500 20.7500 0.8750 3 0.87500.8125 4 0.81250.7812 5 0.7812 0.7656 60.7656 0.7734 7 0.7734 0.7695 8 0.7695 0.7714 90.7714 0.7724 100.7724 0.7729 取x10=0.7729，誤差為| x* -x10|=1/211 。 Remark1：求奇數(shù)個根 Find solutions to the equationon the intervals 0, 4，Use the bisect

5、ion method to compute a solution with an accuracy of 107. Determine the number of iterations to use. 0,1, 1.5, 2.5 and 3,4，利用前面的公式可計算迭代次數(shù)為k=23. Remark2:要區(qū)別根與奇異點Consider f(x) = tan(x) on the interval (0,3).Use the 20 iterations of the bisection method and see what happens. Explain the results that yo

6、u obtained.（如下圖）Remark3:二分法不能用來求重根f (x) = 0 x = g (x)等價變換等價變換f (x) 的根的根g (x) 的不動點的不動點2 2.2 .2 單個方程的迭代法 f(x)=0 f(x)=0化為等價方程化為等價方程x=g(x)x=g(x)的方式是不唯一的方式是不唯一的的, ,有的收斂有的收斂, ,有的發(fā)散有的發(fā)散 For example For example：2x2x3 3-x-1=0-x-1=0321xx 如果將原方程化為等價方程如果將原方程化為等價方程由此可見，這種迭代格式是發(fā)散的由此可見，這種迭代格式是發(fā)散的 取初值取初值00 x310211x

7、x 321213xx 3322155xx 3121kkxx則迭代格式為：321xx 如果將原方程化為等價方程如果將原方程化為等價方程00 x21031 xx3217937.031221xx327937.19644.0仍取初值仍取初值依此類推依此類推, ,得得 x x3 3 = 0.9940 = 0.9940 x x4 4 = 0.9990 = 0.9990 x x5 5 = 0.9998 = 0.9998 x x6 6 = 1.0000 = 1.0000 x x7 7 = 1.0000 = 1.0000已經(jīng)收斂已經(jīng)收斂, ,故原方程的解為故原方程的解為 x = 1.0000 x = 1.000

8、0 同樣的方程同樣的方程不同的迭代格式不同的迭代格式 有不同的結(jié)果有不同的結(jié)果什么形式的迭代什么形式的迭代法能夠收斂呢法能夠收斂呢? ?收斂性分析定義定義2 若存在常數(shù)若存在常數(shù) (0 1),使得對一使得對一切切x x1 1,x,x2 2a,ba,b, , 成立不等式成立不等式|g(x|g(x1 1)-g(x)-g(x2 2)| )| |x |x1 1-x-x2 2| |， 則稱則稱g(x)g(x)是是a,ba,b上的一個壓縮映射上的一個壓縮映射， 稱為壓縮系數(shù)稱為壓縮系數(shù) 考慮方程考慮方程 x = g(x), g(x) Ca, b, 若若( I ) 當(dāng)當(dāng) x a, b 時，時， g(x) a

9、, b；( II )在在a,ba,b上成立不等式：上成立不等式：|g(x|g(x1 1)-g(x)-g(x2 2)| )| |x |x1 1-x-x2 2| | 。則（則（1）g g在在a,ba,b上存在惟一不動點上存在惟一不動點x x* *（2）任?。┤稳?x0 a, b，由由 xk+1 = g(xk) 得到的序列得到的序列 x xk k （ a,ba,b】）】） 收斂于收斂于x x* * 。（3）k k次迭代所得到的近似不動點次迭代所得到的近似不動點x xk k與精確不動點與精確不動點x x* *有有有誤差估有誤差估計式：計式：定理定理2.2.1*11kkkxxxx*101kkxxxx3

10、Fixed-Point Iteration證明：證明： g(x) 在在a, b上存在不動點？上存在不動點？ 不動點唯一？不動點唯一？ 當(dāng)當(dāng)k 時，時， xk 收斂到收斂到 x* ？ | |x x* *-x|=|g(x-x|=|g(x* *)-g(x)| )-g(x)| |x |x* *-x|. -x|. 因因0 0 1 1，故必有，故必有 x=xx=x* *若有若有xxa,ba,b, ,滿足滿足g(x)=xg(x)=x，則則| |x xk k-x-x* *|=|g(x|=|g(xk-1k-1)-g(x)-g(x* *)| )| | |x k-1k-1-x-x* *| | 2 2|x|xk-2k

11、-2-x-x* *| | k k|x|x0 0-x-x* *| |0 0令令G(x)=g(x)-x, xG(x)=g(x)-x, xa a，b b，由條件知由條件知G(a)=g(a)-a0, G(b)=g(b)-b0.G(a)=g(a)-a0, G(b)=g(b)-b0.由條件知由條件知G(x)G(x)在在a,ba,b上連續(xù)，又由介值定理知上連續(xù)，又由介值定理知存在存在x x* *a,ba,b，使使G(xG(x* *)=0)=0，即即x x* *=g(x=g(x* *).).3 Fixed-Point Iteration 可用可用 來來控制收斂精度控制收斂精度|1kkxx 越小，收斂越快越小，

12、收斂越快(4) |(4) |x xk k-x-x* *|=|g(x|=|g(xk-1k-1)-g(x)-g(x* *)| )| | |x k-1k-1-x-x* *| | （|x|xk k-x-xk-1k-1|+|x|+|xk k-x-x* *| |）, ,故有故有 | |x xk k-x-x* *| | /(1-/(1- ) )|x|xk k-x-xk-1k-1|.|.這就證明了估計式這就證明了估計式. . (5) (5) |x|xk k-x-xk-1k-1| | = |g(x= |g(xk-1k-1)-g(x)-g(xk-2k-2)|)| | |x k-1k-1-x-xk-2k-2| k-

13、1k-1|x|x1 1-x-x0 0| |聯(lián)系估計式可得聯(lián)系估計式可得 | |x xk k-x-x* *| | k-1k-1/(1-/(1- ) )|x|x1 1-x-x0 0|.|.即估計式成立即估計式成立定理條件非必要條件，而且定理定理條件非必要條件，而且定理2 .1中中的壓縮條件不好驗證，一般來講的壓縮條件不好驗證，一般來講， 若知道迭代函數(shù)若知道迭代函數(shù)g(x)Ca,b,g(x)Ca,b,并且滿并且滿足足|g(x)| |g(x)| 1,1,對任意的對任意的xxa,ba,b, ,則則g(x)g(x)是是a,ba,b上的壓縮映射上的壓縮映射例題 已知方程2x-7-lgx0，求

14、方程的含根區(qū)間，考查用迭代法解此方程的收斂性。在這里我們考查在區(qū)間3.5,4的迭代法的收斂性 很容易驗證：f(3.5)0 將方程變形成等價形式：x(lgx+7)/2(lg( )7)11( )2ln10 xg xx1g(x)=23.54max |( )| 0.0631xg x 由定理由定理3.2.1知，迭代格式知，迭代格式x xk+1k+1(lgx(lgxk k+7)/2+7)/2在在3.5,43.5,4內(nèi)收斂內(nèi)收斂局部收斂性定理局部收斂性定理定理定理2 .2設(shè)設(shè)x x* *為為g g的不動點，的不動點，g(x)g(x)與與g(x)g(x)在在包含包含x x* *的某鄰域的某鄰域U

15、(xU(x* *) () (即開區(qū)間即開區(qū)間) )內(nèi)連續(xù)，內(nèi)連續(xù)，且且| |g(xg(x* *)|1)| 0 0，當(dāng)，當(dāng)x x0 0 x x* * - - ，x x* *+ + 時，迭代法時，迭代法(3)(3)產(chǎn)生的序列產(chǎn)生的序列 x xk k x x* * - - ，x x* *+ + 且收斂于且收斂于x x* *. .證明略（作為練習(xí)）證明略（作為練習(xí)）We donWe dont know t know x x* *,how do we ,how do we estimate the estimate the inequalityinequality？ 舉例用一般迭代法求x3-x-1=0的

16、正實根x*3x= x+1將方程改寫成：3x)= x+1則迭代函數(shù)為：g(231x)=3x+1 g (（）容易得到：容易得到：g(x)g(x)在包含在包含x x* *的某鄰域的某鄰域U(xU(x* *) ) 內(nèi)內(nèi)連續(xù)，且連續(xù)，且| |g(xg(x* *)|1)|1*3kx= x +1xk+1因此迭代格式在 附近收斂例題用一般迭代法求方程x-lnx2在區(qū)間（2，）內(nèi)的根，要求|xk-xk-1|/|xk|=10-8解：令f(x)=x-lnx-2f(2)0,故方程在（2,4）內(nèi)至少有一個根1f (x)=10,2xx又 （ ， ）f (x)=02,2*因此方程 在（ ， ）內(nèi)僅有一個根x且x（ ， ）將

17、方程化為等價方程：x2lnx1g(x)2lnx (x)|=| 0.51,2 4xx ， |g（ ， ）因此， x0（2，），xk+12lnxk產(chǎn)生的序列 xk 收斂于X*取初值x03.0,計算結(jié)果如下：7 3.1461436118 3.146177452 9 333333.146193204k xk0 3.000000000 1 3.098612289 2 3.130954362 3 3.141337866 4 3.144648781 5 3.145702209 6

18、 3.146037143另一種迭代格式： 1(1 ln)1kkkkxxxx 0 3.000000000 1 3.147918433 2 3.146193441 3 3.146193221 由此可見，對同一個非線性方程的迭代格式，在收斂的情形下，有的收斂快，有的收斂慢。 定義定義1. :設(shè)設(shè)序列序列xk收斂于收斂于x*，若存在若存在p1和正數(shù)和正數(shù)c，使得成立使得成立則稱則稱xk為為 p 階收斂的階收斂的特別特別, p = 1，要求要求c1, 稱線性收斂稱線性收斂; 1p 0，當(dāng)，當(dāng)x x0 0 x x* * - - ，x x* *+ + (x(x0 0 xx* *) )時，由迭代法時，由迭代法

19、xk+1 = g(xk)產(chǎn)生的序列產(chǎn)生的序列x xk k以以p p階收斂速度收斂于階收斂速度收斂于x x* *. .Prove: (1)(1)由由g(g(x x* *)=0)=0必存在必存在 0，當(dāng)，當(dāng)x x0 0 x x* * - - ，x x* *+ + U(x)U(x)時，由迭代格式時，由迭代格式(3)(3)產(chǎn)生的序列產(chǎn)生的序列 x xk k 收收斂于斂于x x* *, ,并有并有x xk k x x* * - - ，x x* *+ + (2)(2)由泰勒公式有由泰勒公式有x xk+1k+1=g(x=g(xk k)=)=g(xg(x* * ）g(xg(x* *)(x)(xk k- - x x* *)+)+g +g (p-1)(p-1) (x (x* *)(x)(xk k-x-x* *)