計(jì)算方法第六章迭代法

計(jì)算方法第六章迭代法第一頁(yè)，共五十三頁(yè)，編輯于2023年，星期一第一節(jié)非線性方程求根（）1、二分法利用連續(xù)函數(shù)的性質(zhì)進(jìn)行對(duì)分。計(jì)算框圖為：第二頁(yè)，共五十三頁(yè)，編輯于2023年，星期一壓縮映射：集合A上的映射，A上兩個(gè)點(diǎn)之間的距離記為，如映射滿足下面條件，稱為壓縮映射例：設(shè)函數(shù)滿足：，則該函數(shù)為壓縮映射定理：如果

為閉集合A上的壓縮映射，則方程x=(x)

在集合A

上有唯一解。且解可以用下面迭代得到：第三頁(yè)，共五十三頁(yè)，編輯于2023年，星期一2、簡(jiǎn)單迭代：對(duì)于形如的方程，可以通過迭代求解。定理：滿足下面條件時(shí)，為壓縮映射：（1）當(dāng)時(shí)，（2）存在正數(shù)L<1，使得則方程在區(qū)間上有唯一解，且解可以用下面迭代得到第四頁(yè)，共五十三頁(yè)，編輯于2023年，星期一第五頁(yè)，共五十三頁(yè)，編輯于2023年，星期一第六頁(yè)，共五十三頁(yè)，編輯于2023年，星期一例：在區(qū)間[1，）上求解方程可用迭代法求解，迭代序列第七頁(yè)，共五十三頁(yè)，編輯于2023年，星期一誤差估計(jì)：第k步迭代計(jì)算值與精確值誤差為使用迭代法求解方程值得注意的事項(xiàng)：1、將要求解的方程化成的形式。2、該迭代法第一個(gè)條件不易驗(yàn)證。因此，實(shí)際使用時(shí)，總在根的附近區(qū)間內(nèi)進(jìn)行迭代計(jì)算，以保證每次迭代的值都在迭代區(qū)間內(nèi)。3、L很小時(shí)迭代收斂非?？?，但如果L與1很接近，則收斂相當(dāng)慢。第八頁(yè)，共五十三頁(yè)，編輯于2023年，星期一收斂階：定義：設(shè)，如果存在實(shí)數(shù)p和非零常數(shù)c，使：則稱序列p階收斂，特別，p＝1時(shí)，稱為線性收斂，p>1時(shí)，稱為超線性收斂，p＝2時(shí)稱為平方收斂。p越大，序列收斂越快。如果是線性收斂，則0<c<1第九頁(yè)，共五十三頁(yè)，編輯于2023年，星期一加速收斂技術(shù)：1、松弛法選擇適當(dāng)?shù)某?shù)（松弛因子），令第十頁(yè)，共五十三頁(yè)，編輯于2023年，星期一例子：求方程的根迭代格式：?。?.15，第十一頁(yè)，共五十三頁(yè)，編輯于2023年，星期一計(jì)算結(jié)果要求準(zhǔn)確到小數(shù)后8位數(shù)字2.1544347393126992.1036120826483502.0959274643276272.0947605999163422.0945833046495202.0945563634929972.0945522695502622.0945516474387052.0945515529032052.0945515385376762.0945515363547042.1025999584485222.0947499378817042.0945564465017492.0945516575136532.0945515389722662.094551536038016第十二頁(yè)，共五十三頁(yè)，編輯于2023年，星期一x=2.510y=x

x=(2*y+5)**(1.0/3.0)

if(abs(x-y).lt.0.00000001)then

goto15 endif goto1015x=2.520y=x

x=(2*y+5)**(1.0/3.0) x=1.15*x+(1.0-1.15)*y

if(abs(x-y).lt.0.00000001)then

goto30 endif goto2030end第十三頁(yè)，共五十三頁(yè)，編輯于2023年，星期一Aitken加速法（適用于線性收斂情況）第十四頁(yè)，共五十三頁(yè)，編輯于2023年，星期一3、插值加速法第十五頁(yè)，共五十三頁(yè)，編輯于2023年，星期一由線性插值公式：第十六頁(yè)，共五十三頁(yè)，編輯于2023年，星期一斯特芬森迭代（迭代兩次后用Aitken加速）：迭代一次用插值加速，稱為插值加速迭代：第十七頁(yè)，共五十三頁(yè)，編輯于2023年，星期一3.對(duì)于一般的函數(shù)方程f(x)=0

的求解，解決方案為：構(gòu)造等價(jià)的方程x=(x)

，利用迭代法求解。這稱為牛頓迭代，迭代序列收斂條件為：這在函數(shù)方程f(x)=0根a

的某鄰域內(nèi)顯然成立。第十八頁(yè)，共五十三頁(yè)，編輯于2023年，星期一牛頓迭代法的幾何意義：第十九頁(yè)，共五十三頁(yè)，編輯于2023年，星期一一個(gè)例子：第二十頁(yè)，共五十三頁(yè)，編輯于2023年，星期一牛頓迭代法是局部收斂。因此，只有初值選得靠近精確解時(shí)，才能保證迭代序列收斂。定理：設(shè)函數(shù)f(x)在區(qū)間[a,b]上二階導(dǎo)數(shù)存在，且：則牛頓迭代序列收斂于f(x)＝0在區(qū)間[a,b]上的唯一根。第二十一頁(yè)，共五十三頁(yè)，編輯于2023年，星期一利用泰勒展開容易證明，牛頓迭代法具有二階收斂性，即平方收斂。收斂速度快這是牛頓迭代法的主要優(yōu)點(diǎn)。計(jì)算步驟（框圖）：例子：建立求某個(gè)正實(shí)數(shù)c

的平方根的迭代格式。第二十二頁(yè)，共五十三頁(yè)，編輯于2023年，星期一設(shè)函數(shù)方程f(x)=0

的根為，將f()泰勒展開第二十三頁(yè)，共五十三頁(yè)，編輯于2023年，星期一改進(jìn)牛頓迭代或柯西迭代第二十四頁(yè)，共五十三頁(yè)，編輯于2023年，星期一設(shè)函數(shù)y=f(x)的反函數(shù)為x=(y)，f(x)=0

的根為第二十五頁(yè)，共五十三頁(yè)，編輯于2023年，星期一牛頓迭代法的收斂性：牛頓迭代法二階收斂，兩種改進(jìn)牛頓迭代法三階收斂第二十六頁(yè)，共五十三頁(yè)，編輯于2023年，星期一簡(jiǎn)化牛頓法：目的：避免計(jì)算迭代格式中的導(dǎo)數(shù)方法：將牛頓迭代中導(dǎo)數(shù)取為某個(gè)定點(diǎn)的值，如，按如下格式迭代幾何意義如圖第二十七頁(yè)，共五十三頁(yè)，編輯于2023年，星期一進(jìn)一步，取任意常數(shù)c

代替迭代公式中的導(dǎo)數(shù)值，迭代公式為迭代函數(shù)為，為使迭代序列收斂，c

應(yīng)滿足這稱為簡(jiǎn)化牛頓法，顯然，當(dāng)c

與導(dǎo)數(shù)同號(hào)且滿足上面式子時(shí)，迭代收斂。第二十八頁(yè)，共五十三頁(yè)，編輯于2023年，星期一本例中，c

與導(dǎo)數(shù)異號(hào)，迭代發(fā)散第二十九頁(yè)，共五十三頁(yè)，編輯于2023年，星期一弦割法：用過兩個(gè)點(diǎn)的直線的斜率代替函數(shù)在點(diǎn)處函數(shù)的導(dǎo)數(shù)，進(jìn)行迭代。迭代公式：同樣，此法具有局部收斂性。其收斂是超線性收斂，收斂階為1.618第三十頁(yè)，共五十三頁(yè)，編輯于2023年，星期一單點(diǎn)弦割法：用固定點(diǎn)代替可以證明，單點(diǎn)法也是局部收斂的，且收斂階為線性收斂，即1階收斂。第三十一頁(yè)，共五十三頁(yè)，編輯于2023年，星期一牛頓下山法：目的是解決初值的選取范圍太小這以困難。構(gòu)造迭代格式為：其中的參數(shù)滿足：這個(gè)方法稱為牛頓下山法。其中的參數(shù)稱為下山因子，通常取，然后逐步減半。牛頓下山法當(dāng)時(shí)，只有線性收斂速度，但對(duì)初值的選取卻放的相當(dāng)寬。第三十二頁(yè)，共五十三頁(yè)，編輯于2023年，星期一第二節(jié)線性代數(shù)方程組迭代解法求解代數(shù)方程組方法：將方程組改造為一個(gè)等價(jià)的方程組構(gòu)造迭代格式：設(shè)為事先給定的誤差精度，則可以得到迭代次數(shù)：定理：對(duì)于上面的迭代格式，如果B的范數(shù)小于1，則對(duì)于任意的初始向量與常向量g，迭代格式收斂，迭代誤差估計(jì)：第三十三頁(yè)，共五十三頁(yè)，編輯于2023年，星期一2.1雅可比迭代與高斯－賽德爾迭代考慮n階方程組，設(shè)系數(shù)陣非奇異，且對(duì)角元非零將方程組變形為：第三十四頁(yè)，共五十三頁(yè)，編輯于2023年，星期一任意取一組初值，可以建立迭代格式：顯然，如上面的迭代收斂，則收斂向量必然為方程組的唯一解。這個(gè)迭代法稱為雅可比迭代。雅可比迭代也稱為同時(shí)（或整體）代換第三十五頁(yè)，共五十三頁(yè)，編輯于2023年，星期一顯然，如果雅可比迭代法收斂，則將迭代格式中每一步迭代得到的迭代向量分量帶入下一步迭代，則迭代效果應(yīng)該更好，這種迭代稱為高斯－賽德爾迭代，（逐個(gè)代換法）雅可比迭代與高斯－賽德爾迭代都稱為簡(jiǎn)單迭代。第三十六頁(yè)，共五十三頁(yè)，編輯于2023年，星期一逐個(gè)超松弛（SOR）迭代：第三十七頁(yè)，共五十三頁(yè)，編輯于2023年，星期一基本迭代的收斂第三十八頁(yè)，共五十三頁(yè)，編輯于2023年，星期一雅可比迭代的矩陣形式：高斯——賽德爾迭代的矩陣形式：超松弛（SOR）迭代矩陣形式：第三十九頁(yè)，共五十三頁(yè)，編輯于2023年，星期一代數(shù)方程組簡(jiǎn)單迭代法收斂的條件定義：矩陣A的特征值中模最大者，稱為矩陣的譜半徑，矩陣A的譜半徑記為(A)定理：簡(jiǎn)單迭代收斂的充分必要條件是或矩陣B

的譜半徑(B)<1第四十頁(yè)，共五十三頁(yè)，編輯于2023年，星期一推論1：如果迭代矩陣的范數(shù)小于1，則簡(jiǎn)單迭代收斂。推論2：逐次超松弛迭代法收斂的一個(gè)條件是0<<2推論3：A嚴(yán)格對(duì)角占優(yōu)時(shí)，雅可比迭代、0<1的SOR法都收斂。推論4：A對(duì)稱正定時(shí)，雅可比迭代法收斂的充要條件是2D－A對(duì)稱正定，SOR收斂的充要條件是0<<21、A嚴(yán)格對(duì)角占優(yōu)，則雅可比、高斯－賽德爾迭代都收斂。2、如A

對(duì)稱正定，則高斯－賽德爾迭代收斂。3、如果A

對(duì)稱正定，D為A

的對(duì)角線上的元組成的矩陣，如2D－A也對(duì)稱正定，則雅可比迭代收斂；如A對(duì)稱正定而2D－A非正定，則雅可比迭代不收斂。第四十一頁(yè)，共五十三頁(yè)，編輯于2023年，星期一第三節(jié)非線性方程組的迭代解法3.1一般迭代。設(shè)有非線性方程組

第四十二頁(yè)，共五十三頁(yè)，編輯于2023年，星期一將方程組改寫為下式，可得Jacobi型迭代格式第四十三頁(yè)，共五十三頁(yè)，編輯于2023年，星期一記，稱為關(guān)于x的Frechet導(dǎo)數(shù)。定理：若滿足：1、存在凸閉區(qū)域，使得2、存在正常數(shù)，使得，則在在惟一的不動(dòng)點(diǎn)x*，并且迭代序列收斂于x*，而且有上述關(guān)于方程式迭代一樣的誤差估計(jì)。注：上述矩陣的范數(shù)可取1范數(shù)、2范數(shù)、無(wú)窮范數(shù)等。存第四十四頁(yè)，共五十三頁(yè)，編輯于2023年，星期一例子：第四十五頁(yè)，共五十三頁(yè)，編輯于2023年，星期一2.249999996274710E-0010.000000000000000E+0002.186919316403400E-0015.466796866210643E-0022.325557956363573E-0015.317841537994177E-0022.317490821626177E-0015.644888021896249E-0022.325921363078080E-0015.625890688180394E-0022.325180586318136E-0015.645743714344483E-0022.325700280145271E-0015.643999442076879E-0022.325640279518354E-0015.645223144329810E-0022.325672764847015E-0015.645081864117191E-0022.325668208064959E-0015.645158355581563E-0022.325670264099253E-0015.645147625974770E-0022.325669930999687E-0015.645152467207023E-0022.325670062538411E-0015.645151682875589E-0022.325670038780621E-0015.645151992602669E-002第四十六頁(yè)，共五十三頁(yè)，編輯于2023年，星期一

x=0.0 y=0.010x1=xy1=y

x=0.25*(1+y1-0.1*exp(x1)) y=0.25*(x1-0.125*x1*x1)write(10,*)x,y

if((abs(x-x1)+abs(y-y1)).lt.0.00000001)then

goto15 endif

goto1015end第四十七頁(yè)，共五十三頁(yè)，編輯于2023年，星期一類似的可以得到高斯－賽德爾型迭代：第四十八頁(yè)，共五十三頁(yè)，編輯于2023年，星期一2.249999996274710E-0015.466796866210643E-0022.323589238058666E-0015.640252253045976E-0022.325613187635559E-0015.645018072260635E-0022.325668492678739E-0