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

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

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

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

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

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

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

（2.5）

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

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

證明由連續(xù)函數(shù)的性質(zhì)，存在的某個(gè)鄰域，使對(duì)于任意成立此外，對(duì)于任意，總有，這是因?yàn)橛谑且罁?jù)定理7.2.2可以斷定迭代過程對(duì)于任意初值均收斂.

證畢.

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

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

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

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