精選收斂加速的方法講義

（優(yōu)選）收斂加速的方法課件現(xiàn)在是1頁\一共有34頁\編輯于星期四現(xiàn)在是2頁\一共有34頁\編輯于星期四[a,b]稱為有根區(qū)間.

則現(xiàn)在是3頁\一共有34頁\編輯于星期四現(xiàn)在是4頁\一共有34頁\編輯于星期四(2)

(3)

(1)

f(ak)f(bk)<0

現(xiàn)在是5頁\一共有34頁\編輯于星期四由此可見，如果二分過程無限地進(jìn)行下去（），則有限區(qū)間必定縮為一點x*，該點顯然就是所求的根。實際上，我們不可能去完成這種無窮過程，也無必要，只需得到滿足一定精度的近似值就可以了。如果令有根區(qū)間[an,bn]的中點為

x*的近似值，則在二分過程中，得到下列以x*為極限的近似根序列由于現(xiàn)在是6頁\一共有34頁\編輯于星期四現(xiàn)在是7頁\一共有34頁\編輯于星期四現(xiàn)在是8頁\一共有34頁\編輯于星期四二分法優(yōu)點：是方程求根問題的一種直接搜索方法，算法簡單、直觀、實用，收斂性總能得到保證。缺點（局限性）：不能求重根；計算速度慢。思考：為什么不能求重根？例2.1用二分法求方程在區(qū)間[1,1.5］內(nèi)的一個實根，要求誤差不超過0.005。解由公式估計所要二分的次數(shù)即只要二分6次，便能達(dá)到所要求的精度。現(xiàn)在是9頁\一共有34頁\編輯于星期四計算結(jié)果kakbkxkf(xk)01.01.51.25-11.251.51.375+21.251.3751.3125-31.31251.3751.3438+41.31251.34381.3281+51.31251.32811.3203-61.32031.32811.3242-現(xiàn)在是10頁\一共有34頁\編輯于星期四作業(yè)：1、用二分法求方程在區(qū)間[1,2］內(nèi)的一個實根，要求誤差不超過0.005?，F(xiàn)在是11頁\一共有34頁\編輯于星期四將一個計算過程反復(fù)進(jìn)行一種常見常用的計算技術(shù)構(gòu)造有效的迭代格式選取合適的迭代初值對迭代格式進(jìn)行收斂性分析一種圓周率的計算方案:初值:x0=1(n=1,2,3,······)迭代格式:2.2迭代法現(xiàn)在是12頁\一共有34頁\編輯于星期四1選取初值把給定的方程改寫成等價形式

f(x)=0若存在x*,使得,則稱x*為不動點。在根x*的附近取一點x0作為x*的預(yù)測值,也叫迭代初值。(1)現(xiàn)在是13頁\一共有34頁\編輯于星期四把x0代入(1)的右端，得如果，則。如果，把x1作為根的新的預(yù)測值代入(1)，得如果，則。如果，把x2作為根的新的預(yù)測值代入(1)......如此重復(fù)上述步驟，則有迭代公式(k=0,1,2,···)2按迭代格式進(jìn)行計算現(xiàn)在是14頁\一共有34頁\編輯于星期四3判別收斂其中，：迭代函數(shù)，得到迭代序列如果迭代序列的極限存在，則迭代過程收斂，顯然有如果迭代序列的極限不存在，則稱迭代過程發(fā)散。上述迭代過程也稱不動點迭代法。現(xiàn)在是15頁\一共有34頁\編輯于星期四方程求根，在幾何上就是確定曲線與直線的交點p*幾何意義x*x2

x1

x0如果逐漸逼近p*，－－－迭代過程收斂y=xyox現(xiàn)在是16頁\一共有34頁\編輯于星期四如果逐漸遠(yuǎn)離p*，－－－迭代過程發(fā)散（無意義）x2

x1

x0x*

y=xyox現(xiàn)在是17頁\一共有34頁\編輯于星期四

例2.2求方程

f(x)=x3–x–1=0

在x=1.5附近的根x*。

解設(shè)將方程改寫成下列形式由此得迭代公式迭代初值取x0=1.5，計算值用6位數(shù)字表示。迭代結(jié)果如下表現(xiàn)在是18頁\一共有34頁\編輯于星期四kxkkxk01.551.3247611.3572161.3247321.3308671.3247231.3258881.3247241.32494從表中可看到x7與x8完全相同，這時可認(rèn)為x8已滿足方程，x8即為所求根的近似值。上述迭代過程是收斂的?，F(xiàn)在是19頁\一共有34頁\編輯于星期四如果將方程改寫成下列形式據(jù)此有迭代公式迭代初值仍取x0=1.5，則有當(dāng)k增大時，xk隨之增大而不趨于任何極限，此時迭代過程發(fā)散。通過此例說明，迭代過程只有在一定條件下才可能收斂。一個發(fā)散的過程沒有任何意義?，F(xiàn)在是20頁\一共有34頁\編輯于星期四定理2.3如果,滿足條件:;(2)則方程在[a,b]有唯一的不動點x*。證若或,顯然有不動點設(shè),則有,記則有所以,存在x*,使得即,x*即為不動點.現(xiàn)在是21頁\一共有34頁\編輯于星期四唯一性：設(shè)在[a,b]上存在兩個根x1*和x2*，則由微分中值定理，必有現(xiàn)在是22頁\一共有34頁\編輯于星期四定理2.4如果,滿足條件:;(2)則對任意的x0∈[a,b],迭代格式產(chǎn)生的序列{xk}收斂到不動點x*,且有事后誤差估計式證現(xiàn)在是23頁\一共有34頁\編輯于星期四(0<L<1)所以,，故迭代格式收斂現(xiàn)在是24頁\一共有34頁\編輯于星期四現(xiàn)在是25頁\一共有34頁\編輯于星期四現(xiàn)在是26頁\一共有34頁\編輯于星期四由此可見，迭代過程的收斂性通常依賴于迭代初值的選取現(xiàn)在是27頁\一共有34頁\編輯于星期四迭代法的計算步驟：1）準(zhǔn)備：確定方程f(x)=0的等價形式及初值x0，為確保迭代收斂，要求滿足或2）迭代：按迭代公式計算出xk3）判別：直到，則終止迭代，取現(xiàn)在是28頁\一共有34頁\編輯于星期四例2.3求方程

x=e–x在x=0.5附近的一個根，要求精度?，F(xiàn)在是29頁\一共有34頁\編輯于星期四不動點迭代產(chǎn)生序列的收斂速度數(shù)列的p

階收斂概念記迭代誤差： 則稱迭代過程是p

階收斂的.特別:(1)收斂階p=1時,稱為線性收斂;(2)收斂階p>1時,稱為超線性收斂;(3)收斂階p=2時,稱為平方收斂序列的收斂階數(shù)越高,收斂速度越快收斂速度：接近收斂時迭代誤差的下降速度。定義當(dāng)時，有現(xiàn)在是30頁\一共有34頁\編輯于星期四例2.3方程x3+10x-20=0,取x0=1.5,證明迭代法是線性收斂證令f(x)=x3+10x–20,繪出y=f(x)圖形可知方程的根x*≈1.5,令求導(dǎo)數(shù),得現(xiàn)在是31頁\一共有34頁\編輯于星期四利用Lagrange中值定理,有其中,介于xk和x*之間.所以由此可知,這一序列的收斂階數(shù)為1,即迭代法是線性收斂.顯然,在x*附近現(xiàn)在是32頁\一共有34頁\編輯于星期四定理2.6而則p階收斂。證因為，所以迭代過程局部收斂。由Taylor公式其中,介于xk和x*之間.所以故迭代法p階收斂.