對分法及一般迭代法

1、第四章第四章 非線性方程的數(shù)值解法非線性方程的數(shù)值解法 1根的存在性。方程有沒有根？如果有根，有幾個根？根的存在性。方程有沒有根？如果有根，有幾個根？定理定理1：設(shè)函數(shù)設(shè)函數(shù) f (x) 在區(qū)間在區(qū)間a, b上連續(xù)上連續(xù)，如果如果f (a) f (b) 0打打 印印結(jié)結(jié) 束束否否是是繼續(xù)掃描繼續(xù)掃描 例例1 1：考察方程：考察方程 的含根區(qū)間的含根區(qū)間01)(3xxxfx00.51.01.5f (x)符號符號可見，含根區(qū)間為可見，含根區(qū)間為 1, 1.54.1 對分區(qū)間法對分區(qū)間法 (Bisection Method )原理：原理：若若 f(x) Ca, b，且且 f (a) f (b) 0f

2、 (a) f (b)=0f (a) =0打印打印b, k打印打印a, k結(jié)束結(jié)束是是是是是是否否否否否否m=(a+b)/2|a-b|0打印打印m, ka=mb=m結(jié)束結(jié)束k=k+1是是是是否否否否輸入輸入 ,bak = 0 用二分法求用二分法求 在在(1,2)(1,2)內(nèi)的根，要求絕對誤差不超過內(nèi)的根，要求絕對誤差不超過 ： 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

3、,1.5) nx 1.51 x364. 1368. 1360. 1344. 1313. 1375. 125. 18765432 xxxxxxx12 例3，求方程f(x)= x 3 e-x =0的一個實根。 因為 f(0)0。 故f(x)在(0,1)內(nèi)有根用二分法解之，(a,b）=（0,1)計算結(jié)果如表：ka 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.77

4、14 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 bisection 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:

5、要區(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 you obtained.（如下圖）Remark3:二分法不能用來求重根f (x) = 0 x = g (x)等價變換等價變換f (x) 的根的根g (x) 的不動點的不動點4 4.2 .2 單個方程的迭代法 f(x)=0 f(x)=0化為等價方程化為等價方程x=g(x)x=g(x)的方式是不唯一的方式是不

6、唯一的的, ,有的收斂有的收斂, ,有的發(fā)散有的發(fā)散 For example For example：2x2x3 3-x-1=0-x-1=0 xk+1 = g(xk) (3)321xx 如果將原方程化為等價方程如果將原方程化為等價方程由此可見，這種迭代格式是發(fā)散的由此可見，這種迭代格式是發(fā)散的 取初值取初值00 x310211xx 321213xx 3322155xx 3121kkxx則迭代格式為：321xx 如果將原方程化為等價方程如果將原方程化為等價方程00 x21031 xx3217937.031221xx327937.19644.0仍取初值仍取初值依此類推依此類推, ,得得 x x3

7、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.0000 同樣的方程同樣的方程不同的迭代格式不同的迭代格式 有不同的結(jié)果有不同的結(jié)果什么形式的迭代什么形式的迭代法能夠收斂呢法能夠收斂呢? ?收斂性分析定義定義2 若存在常數(shù)若存在常數(shù) (0 1),使得對一使得對一切切x x1 1,x,x2 2a,ba,b, , 成立不等式成

8、立不等式|g(x|g(x1 1)-g(x)-g(x2 2)| )| |x |x1 1-x-x2 2| |， (5) (5)則稱則稱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, 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）任?。┤?/p>

9、取 x0 a, b，由由 xk+1 = g(xk) 得到的序列得到的序列 x xk k （ a,ba,b】）】） 收斂于收斂于x x* * 。（3）k k次迭代所得到的近似不動點次迭代所得到的近似不動點x xk k與精確不動點與精確不動點x x* *有誤差估計有誤差估計式：式：定理定理4.2.1*1(6)1kkkxxxx*10( 7 )1kkxxxx3 Fixed-Point Iteration證明：證明： g(x) 在在a, b上存在不動點？上存在不動點？ 不動點唯一？不動點唯一？ 當(dāng)當(dāng)k 時，時， xk 收斂到收斂到 x* ？ | |x x* *-x|=|g(x-x|=|g(x* *)-g

10、(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-2-x-x* *| | k k|x|x0 0-x-x* *| |0 0, ,令令G(x)=g(x)-x, xG(x)=g(x)-x, xa,ba,b，由條件知由條件知G(a)=g(a)-a0, G(b)=g(b)-b0.G(a)=g(a)-a

11、0, 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 越小，收斂越快越小，收斂越快(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*

12、 *| |）, ,故有故有 | |x xk k-x-x* *| | /(1-/(1- ) )|x|xk k-x-xk-1k-1|.|.這就證明了估計式這就證明了估計式(6). (6). (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-1k-1|x|x1 1-x-x0 0| |聯(lián)系估計式聯(lián)系估計式(6)(6)可得可得| |x xk k-x-x* *| | k-1k-1/(1-/(1- ) )|x|x1 1-x-x0 0|.|.即估計式即估計式(7)(7)成立成

13、立定理條件非必要條件，而且定理定理條件非必要條件，而且定理4 .1中中的壓縮條件不好驗證，一般來講的壓縮條件不好驗證，一般來講， 若知道迭代函數(shù)若知道迭代函數(shù)g(x)Cg(x)C1 1a,ba,b, ,并并且滿足且滿足|g(x)| |g(x)| 1,1,對任意的對任意的xxa,ba,b, ,則則g g（x)x)是是a,ba,b上的壓縮映射上的壓縮映射xyy = xxyy = xxyy = xxyy = xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p1改進、加速收斂改進、加速收斂 /* a

14、ccelerating convergence */ 待定參數(shù)法：待定參數(shù)法：若若 | g(x) | 1，則將則將 x = g(x) 等價地改造為等價地改造為)()()1()(xxKgxKxKgKxxx 1|)(1|)(| xgKKx 求求K，使得，使得例：例：求求 在在 (1, 2) 的實根。的實根。013)(3 xxxf)()1(313xgxx 如果用如果用 進行迭代，則在進行迭代，則在(1, 2)中有中有1| )(|2 xxg現(xiàn)令現(xiàn)令)1(3)1()()1()(3 xKxKxKgxKx 希望希望1|1| )(|2 KxKx 0122 Kx，即，即在在 (1, 2) 上可取任意上可取任意

15、，例如，例如K = 0.5，則對則對應(yīng)應(yīng) 即產(chǎn)生收斂序列。即產(chǎn)生收斂序列。032 K)1(61233 xxx例題 已知方程2x-7-lgx0，求方程的含根區(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 由定理由定理4.2.1知，迭代格式知，迭代格式x xk+1k+1(lgx(lgxk k+7)/2+7)/2在在3.5,43.5,4內(nèi)收斂內(nèi)收斂局部收斂性定理局部收斂性定理定理定理4

16、 .2 設(shè)設(shè)x x* *為為g g的不動點，的不動點，g(x)g(x)與與g(x)g(x)在在包含包含x x* *的某鄰域的某鄰域U(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

17、 do we estimate the estimate the inequalityinequality？ 舉例用一般迭代法求x3-x-1=0的正實根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,

18、故方程在（2,4）內(nèi)至少有一個根1f (x)=10,2xx又 （ ， ）f (x)=02,2*因此方程 在（ ， ）內(nèi)僅有一個根x且x（ ， ）將方程化為等價方程：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 xi0 3.00000000

19、0 1 3.098612289 2 3.130954362 3 3.141337866 4 3.144648781 5 3.145702209 6 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, 稱

20、線性收斂稱線性收斂; 1p 0，當(dāng)，當(dāng)x x0 0 x x* * - - ，x x* *+ + (x(x0 0 xx* *) )時，由迭代法時，由迭代法(3)(3)產(chǎn)生的序列產(chǎn)生的序列x xk k以以p p階收斂速度收斂于階收斂速度收斂于x x* *. .Proof: (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