第二節(jié) 迭代法及其收斂性1

數(shù)值計算方法對于一般的非線性方程,沒有通常所說的求根公式求其精確解,需要設(shè)計近似求解方法,即迭代法。它是一種逐次逼近的方法,用某個固定公式反復(fù)校正根的近似值,使之逐步精確化，最后得到滿足精度要求的結(jié)果。10.2迭代法及其收斂性

10.2.1不動點迭代法的基本概念和迭代格式的構(gòu)造將方程（1.1）改寫成等價的形式（2.1）若要求滿足，則；反之亦然，稱為函數(shù)的一個不動點.求的零點就等價于求的不動點，選擇一個初始近似值，將它代入(2.1)右端，即可求得如此反復(fù)迭代計算（2.2）稱為迭代函數(shù).如果對任何，由（2.2）得到的迭代序列有極限則稱迭代方程(2.2)收斂，且為的不動點，故稱（2.2）為不動點迭代法.

上述迭代法是一種逐次逼近法，其基本思想是將隱式方程（2.1）歸結(jié)為一組顯式的計算公式（2.2），就是說，迭代過程實質(zhì)上是一個逐步顯示化的過程.方程的求根問題在平面上就是要確定曲線與直線的交點對于的某個近似值，在曲線上可確定一點，它以為橫坐標(biāo)，而縱坐標(biāo)則等于過引平行軸的直線，設(shè)此直線交直線于點，然后過再作平行于軸的直線，它與曲線的交點記作，則點的橫坐標(biāo)為，縱坐標(biāo)則等于圖1-2

例1求方程（2.3）在附近的根

解設(shè)將方程（2.3）改寫成下列形式按圖1-2中箭頭所示的路徑繼續(xù)做下去，在曲線上得到點列，其橫坐標(biāo)分別為依公式求得的迭代值據(jù)此建立迭代公式如果點列趨向于點，則相應(yīng)的迭代值收斂得到所求的根各步迭代的結(jié)果見表.如果僅取6位數(shù)字，那么結(jié)果與完全相同，這時可以認(rèn)為實際上已滿足方程(2.3)，即為所求的根.但若采用方程（2.3）的另一種等價形式建立迭代公式仍取迭代初值，則有結(jié)果會越來越大，不可能趨于某個極限.這種不收斂的迭代過程稱作是發(fā)散的.一個發(fā)散的迭代過程，縱使進(jìn)行了千百次迭代，其結(jié)果也是毫無價值的.xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=(x)y=(x)y=(x)y=(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1x210.2.2不動點的存在性與迭代法的收斂性首先考察在上不動點的存在唯一性.定理1設(shè)滿足以下兩個條件：1°映內(nèi)性對任意有2°壓縮性存在正常數(shù),使對都有（2.4）

證明先證不動點存在性.若或，顯然在上存在不動點.因，以下設(shè)及，定義函數(shù)顯然，且滿足，由連續(xù)函數(shù)性質(zhì)可知存在使，即即為的不動點.再證唯一性.設(shè)都是的不動點，則由(2.4)得引出矛盾.故的不動點只能是唯一的.證畢.定理.2設(shè)滿足定理1中的兩個條件，則對任意，由（2.2）得到的迭代序列收斂到的不動點，并有誤差估計

（2.5）

證明設(shè)是在上的唯一不動點，由條件1°，可知，再由（2.4）得因，故當(dāng)時序列收斂到.再證明估計式（2.5），由李普希茲條件有（2.6）反復(fù)遞推得于是對任意正整數(shù)有在上式令，注意到即得式（2.5）證畢.迭代過程是個極限過程.在用迭代法實際計算時，必須按精度要求控制迭代次數(shù).誤差估計式（2.5）原則上可用于確定迭代次數(shù)，但它由于含有信息而不便于實際應(yīng)用.根據(jù)式（2.6），對任意正整數(shù)有在上式中令知由此可見，只要相鄰兩次計算結(jié)果的偏差足夠小即可保證近似值具有足夠精度.對上述定理中的壓縮性，在使用時如果且對任意有（2.7）則由中值定理可知對有表明定理中的壓縮性條件可用（2.7）代替.例7.2.3中，當(dāng)時，,在區(qū)間中，，故（2.7）成立.又因，故定理1中條件1°也成立.所以迭代法是收斂的.而當(dāng)時，在區(qū)間中不滿足定理條件.10.3局部收斂性與收斂階上面給出了迭代序列在區(qū)間上的收斂性，通常稱為全局收斂性.定理的條件有時不易檢驗，實際應(yīng)用時通常只在不動點的鄰近考察其收斂性，即局部收斂性.

定義7.2.1設(shè)有不動點，如果存在的某個鄰域，對任意，迭代（2.2）產(chǎn)生的序列，且收斂到，則稱迭代法（2.2）局部收斂.定理7.2.3設(shè)為的不動點，在的某個鄰域連續(xù)，且，則迭代法（2.2）局部收斂.

證明由連續(xù)函數(shù)的性質(zhì)，存在的某個鄰域，使對于任意成立此外，對于任意，總有，這是因為于是依據(jù)定理7.2.2可以斷定迭代過程對于任意初值均收斂.

證畢.

解這里，可改寫為各種不同的等價形式，其不動點為由此構(gòu)造不同的迭代法：

例7.2.2用不同方法求方程的根討論迭代序列的收斂速度.取，對上述4種迭代法，計算三步所得的結(jié)果如下表.注意，從計算結(jié)果看到迭代法（1）及（2）均不收斂，且它們均不滿足定理3中的局部收斂條件，迭代法（3）和（4）均滿足局部收斂條件，且迭代法（4）比（3）收斂快，因在迭代法（4）中.

定義7.2.2設(shè)迭代過程收斂于方程的根，如果迭代誤差當(dāng)時成立下列漸近關(guān)系式則稱該迭代過程是階收斂的,C為漸進(jìn)誤差常數(shù).特別地,時稱線性收斂，時稱超線性收斂，時稱平方收斂.

證明先證充分性由于，據(jù)定理7.2.3立即可以斷定迭代過程具有局部收斂性.再將在根處做泰勒展開，利用條件（2.8），則有注意到，由上式得因此對迭代誤差，當(dāng)時有（2.9）這表明迭代過程確實為階收斂.證畢.上述定理說明，迭代過程的收斂速度依賴于迭代函數(shù)的選取.如果當(dāng)時，則該迭代過程只可能是線性收斂.在例7.2.2中，迭代法（3）的，故它只是線性收斂，而迭代法（4）的