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

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

在集合A

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

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

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

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

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

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

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

代替迭代公式中的導數值，迭代公式為迭代函數為，為使迭代序列收斂，c

應滿足這稱為簡化牛頓法，顯然，當c

與導數同號且滿足上面式子時，迭代收斂。第二十八頁，共五十三頁，編輯于2023年，星期一本例中，c

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

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

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

對稱正定，D為A

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

第四十二頁，共五十三頁，編輯于2023年，星期一將方程組改寫為下式，可得Jacobi型迭代格式第四十三頁，共五十三頁，編輯于2023年，星期一記，稱為關于x的Frechet導數。定理：若滿足：1、存在凸閉區域，使得2、存在正常數，使得，則在在惟一的不動點x*，并且迭代序列收斂于x*，而且有上述關于方程式迭代一樣的誤差估計。注：上述矩陣的范數可取1范數、2范數、無窮范數等。存第四十四頁，共五十三頁，編輯于2023年，星期一例子：第四十五頁，共五十三頁，編輯于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第四十六頁，共五十三頁，編輯于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第四十七頁，共五十三頁，編輯于2023年，星期一類似的可以得到高斯－賽德爾型迭代：第四十八頁，共五十三頁，編輯于2023年，星期一2.249999996274710E-0015.466796866210643E-0022.323589238058666E-0015.640252253045976E-0022.325613187635559E-0015.645018072260635E-0022.325668492678739E-0