計算方法第六章迭代法

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

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

在集合A

上有唯一解。且解可以用下面迭代得到：第3頁，共53頁，2023年，2月20日，星期二2、簡單迭代：對于形如的方程，可以通過迭代求解。定理：滿足下面條件時，為壓縮映射：（1）當時，（2）存在正數(shù)L<1，使得則方程在區(qū)間上有唯一解，且解可以用下面迭代得到第4頁，共53頁，2023年，2月20日，星期二第5頁，共53頁，2023年，2月20日，星期二第6頁，共53頁，2023年，2月20日，星期二例：在區(qū)間[1，）上求解方程可用迭代法求解，迭代序列第7頁，共53頁，2023年，2月20日，星期二誤差估計：第k步迭代計算值與精確值誤差為使用迭代法求解方程值得注意的事項：1、將要求解的方程化成的形式。2、該迭代法第一個條件不易驗證。因此，實際使用時，總在根的附近區(qū)間內(nèi)進行迭代計算，以保證每次迭代的值都在迭代區(qū)間內(nèi)。3、L很小時迭代收斂非?？?，但如果L與1很接近，則收斂相當慢。第8頁，共53頁，2023年，2月20日，星期二收斂階：定義：設(shè)，如果存在實數(shù)p和非零常數(shù)c，使：則稱序列p階收斂，特別，p＝1時，稱為線性收斂，p>1時，稱為超線性收斂，p＝2時稱為平方收斂。p越大，序列收斂越快。如果是線性收斂，則0<c<1第9頁，共53頁，2023年，2月20日，星期二加速收斂技術(shù)：1、松弛法選擇適當?shù)某?shù)（松弛因子），令第10頁，共53頁，2023年，2月20日，星期二例子：求方程的根迭代格式：取＝1.15，第11頁，共53頁，2023年，2月20日，星期二計算結(jié)果要求準確到小數(shù)后8位數(shù)字2.1544347393126992.1036120826483502.0959274643276272.0947605999163422.0945833046495202.0945563634929972.0945522695502622.0945516474387052.0945515529032052.0945515385376762.0945515363547042.1025999584485222.0947499378817042.0945564465017492.0945516575136532.0945515389722662.094551536038016第12頁，共53頁，2023年，2月20日，星期二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第13頁，共53頁，2023年，2月20日，星期二Aitken加速法（適用于線性收斂情況）第14頁，共53頁，2023年，2月20日，星期二3、插值加速法第15頁，共53頁，2023年，2月20日，星期二由線性插值公式：第16頁，共53頁，2023年，2月20日，星期二斯特芬森迭代（迭代兩次后用Aitken加速）：迭代一次用插值加速，稱為插值加速迭代：第17頁，共53頁，2023年，2月20日，星期二3.對于一般的函數(shù)方程f(x)=0

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

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

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

的平方根的迭代格式。第22頁，共53頁，2023年，2月20日，星期二設(shè)函數(shù)方程f(x)=0

的根為，將f()泰勒展開第23頁，共53頁，2023年，2月20日，星期二改進牛頓迭代或柯西迭代第24頁，共53頁，2023年，2月20日，星期二設(shè)函數(shù)y=f(x)的反函數(shù)為x=(y)，f(x)=0

的根為第25頁，共53頁，2023年，2月20日，星期二牛頓迭代法的收斂性：牛頓迭代法二階收斂，兩種改進牛頓迭代法三階收斂第26頁，共53頁，2023年，2月20日，星期二簡化牛頓法：目的：避免計算迭代格式中的導(dǎo)數(shù)方法：將牛頓迭代中導(dǎo)數(shù)取為某個定點的值，如，按如下格式迭代幾何意義如圖第27頁，共53頁，2023年，2月20日，星期二進一步，取任意常數(shù)c

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

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

與導(dǎo)數(shù)同號且滿足上面式子時，迭代收斂。第28頁，共53頁，2023年，2月20日，星期二本例中，c

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

的譜半徑(B)<1第40頁，共53頁，2023年，2月20日，星期二推論1：如果迭代矩陣的范數(shù)小于1，則簡單迭代收斂。推論2：逐次超松弛迭代法收斂的一個條件是0<<2推論3：A嚴格對角占優(yōu)時，雅可比迭代、0<1的SOR法都收斂。推論4：A對稱正定時，雅可比迭代法收斂的充要條件是2D－A對稱正定，SOR收斂的充要條件是0<<21、A嚴格對角占優(yōu)，則雅可比、高斯－賽德爾迭代都收斂。2、如A

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

對稱正定，D為A

的對角線上的元組成的矩陣，如2D－A也對稱正定，則雅可比迭代收斂；如A對稱正定而2D－A非正定，則雅可比迭代不收斂。第41頁，共53頁，2023年，2月20日，星期二第三節(jié)非線性方程組的迭代解法3.1一般迭代。設(shè)有非線性方程組

第42頁，共53頁，2023年，2月20日，星期二將方程組改寫為下式，可得Jacobi型迭代格式第43頁，共53頁，2023年，2月20日，星期二記，稱為關(guān)于x的Frechet導(dǎo)數(shù)。定理：若滿足：1、存在凸閉區(qū)域，使得2、存在正常數(shù)，使得，則在在惟一的不動點x*，并且迭代序列收斂于x*，而且有上述關(guān)于方程式迭代一樣的誤差估計。注：上述矩陣的范數(shù)可取1范數(shù)、2范數(shù)、無窮范數(shù)等。存第44頁，共53頁，2023年，2月20日，星期二例子：第45頁，共53頁，2023年，2月20日，星期二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第46頁，共53頁，2023年，2月20日，星期二

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第47頁，共53頁，2023年，2月20日，星期二類似的可以得到高斯－賽德爾型迭代：第48頁，共53頁，2023年，2月20日，星期二2.249999996274710E-0015.466796866210643E-0022.323589238058666E-0015.640252253045976E-0022.325613187635559E-0015.645018072260635E-0022.325668492678739E-