1、簡(jiǎn)單迭代法 不動(dòng)點(diǎn)迭代的收斂性 迭代序列的收斂速度 收斂加速的方法,第二章 非線性方程的求根方法,a,b稱為有根區(qū)間.,則,(2),(3),(1),f(ak) f(bk)0,由此可見，如果二分過程無限地進(jìn)行下去（ ），則有限區(qū)間必定縮為一點(diǎn)x*，該點(diǎn)顯然就是所求的根。 實(shí)際上，我們不可能去完成這種無窮過程，也無必要，只需得到滿足一定精度的近似值就可以了。 如果令有根區(qū)間an,bn的中點(diǎn) 為 x*的近似值，則在二分過程中，得到下列以x*為極限的近似根序列,由于,二分法優(yōu)點(diǎn)：是方程求根問題的一種直接搜索方法，算法簡(jiǎn)單、直觀、實(shí)用，收斂性總能得到保證。 缺點(diǎn)（局限性）：不能求重根；計(jì)算速度慢。,思考

2、：為什么不能求重根？,例2.1 用二分法求方程 在區(qū)間 1, 1.5內(nèi)的一個(gè)實(shí)根，要求誤差不超過0.005。,解 由公式估計(jì)所要 二分的次數(shù) 即只要二分6次，便能達(dá)到所要求的精度。,計(jì)算結(jié)果,作業(yè)：1、用二分法求方程 在區(qū)間1,2內(nèi)的一個(gè)實(shí)根，要求誤差不超過0.005。,將一個(gè)計(jì)算過程反復(fù)進(jìn)行 一種常見常用的計(jì)算技術(shù) 構(gòu)造有效的迭代格式 選取合適的迭代初值 對(duì)迭代格式進(jìn)行收斂性分析,一種圓周率的計(jì)算方案:,初值: x0=1,2.2 迭代法,1 選取初值 把給定的方程 改寫成等價(jià)形式,f (x)= 0,若存在 x*,使得 ,則稱x*為不動(dòng)點(diǎn)。 在根x*的附近取一點(diǎn)x0作為x*的預(yù)測(cè)值,也叫迭代初

3、值。,(1),把x0代入(1)的右端，得,如果 ，則 。,如果 ，把 x1作為根的新的預(yù)測(cè)值代入(1)，得,如果 ，則 。,如果 ，把 x2作為根的新的預(yù)測(cè)值代入(1). 如此重復(fù)上述步驟，則有迭代公式,( k = 0, 1, 2, ),2 按迭代格式進(jìn)行計(jì)算,3 判別收斂,其中， ：迭代函數(shù)，得到迭代序列,如果迭代序列的極限存在，則迭代過程收斂，顯然有,如果迭代序列的極限不存在，則稱迭代過程發(fā)散。,上述迭代過程也稱不動(dòng)點(diǎn)迭代法。,方程 求根，在幾何上就是確定曲線 與直線 的交點(diǎn) p*,幾何意義,x* x2 x1 x0,如果 逐漸逼近p*，迭代過程收斂,如果 逐漸遠(yuǎn)離p*，迭代過程發(fā)散 （無意

4、義）,例2.2 求方程 f (x)=x3 x 1 = 0 在x =1.5附近的根 x*。,解 設(shè)將方程改寫成下列形式,由此得迭代公式,迭代初值取x0 =1.5，計(jì)算值用6位數(shù)字表示。 迭代結(jié)果如下表,從表中可看到 x7與 x8完全相同，這時(shí)可認(rèn)為x8已滿足方程， x8 即為所求根的近似值。,上述迭代過程是收斂的。,如果將方程改寫成下列形式,據(jù)此有迭代公式,迭代初值仍取 x0 =1.5，則有,當(dāng) k增大時(shí)，xk隨之增大而不趨于任何極限，此時(shí)迭代過程發(fā)散。,通過此例說明，迭代過程只有在一定條件下才可能收斂。一個(gè)發(fā)散的過程沒有任何意義。,證 若 或 ,顯然 有不動(dòng)點(diǎn),設(shè) , 則有 ,記 則有,所以,

5、存在x*,使得 即 , x*即為不動(dòng)點(diǎn).,唯一性： 設(shè)在a, b 上存在兩個(gè)根x1*和x2*，則 由微分中值定理,，必有,定理2.4 如果 ,滿足條件: ; (2),則對(duì)任意的 x0 a, b , 迭代格式 產(chǎn)生的序列 xk 收斂到不動(dòng)點(diǎn)x*,且有事后誤差估計(jì)式,證,( 0L1 ),所以, ，故迭代格式收斂,由此可見，迭代過程的收斂性通常依賴于迭代初值的選取,迭代法的計(jì)算步驟： 1）準(zhǔn)備：確定方程 f(x)=0 的等價(jià)形式 及初值x0，為確保迭代收斂，要求 滿足 或,2）迭代：按迭代公式 計(jì)算出xk,3）判別：直到 ，則終止迭代，取,例2.3 求方程 x=ex 在 x=0.5 附近的一個(gè)根，要

6、求精度 。,不動(dòng)點(diǎn)迭代產(chǎn)生序列的收斂速度,數(shù)列的 p 階收斂概念,記迭代誤差：,則稱迭代過程是 p 階收斂的.,特別: (1) 收斂階p=1時(shí),稱為線性收斂; (2) 收斂階p1時(shí),稱為超線性收斂; (3) 收斂階p=2 時(shí),稱為平方收斂,序列的收斂階數(shù)越高,收斂速度越快,收斂速度：接近收斂時(shí)迭代誤差的下降速度。,定義 當(dāng) 時(shí)，有,例2.3 方程 x3+10 x-20=0,取 x0 = 1.5, 證明迭代法,是線性收斂,證 令 f (x) = x3 + 10 x 20, 繪出 y = f(x) 圖形可知 方程的根 x*1.5, 令,求導(dǎo)數(shù), 得,利用Lagrange中值定理, 有,其中, 介于xk和x*之間. 所以,由此可知,這一序列的收斂階數(shù)為1,即迭代法是線性收斂.,顯然,在x*附近,定理2.6,而 則 p 階收斂。,證 因?yàn)?，所以迭代過程局部收斂。由Taylor公式,其中, 介于xk和x*之間.所以,故迭代法p階收斂.,迭代公式的加速,迭代公式 產(chǎn)生的數(shù)列xk有時(shí)收斂得很慢。令新的迭代函數(shù)為,要得到收斂速度更快的迭代函