迭代法的般原理

1、第二章迭代法的一般原理非線性方程組無論從理論上還是計(jì)算方法上，都比線性方程組復(fù)雜得多。一般的非線性 方程組很難求出解析解，往往只能求出其數(shù)值解，且往往只能借助于迭代法。本章我們將討 論迭代法的一般原理、迭代法的一般構(gòu)造及迭代收斂速度的衡量標(biāo)準(zhǔn)。2-1迭代法與不動(dòng)點(diǎn)定理設(shè)f : D Rn > Rn，考慮方程f x =0(2-1)若存在x D，使f x = 0，則稱x為方程(2-1)的解。用迭代法求解(2-1)，先將(2-1)化為等價(jià)的方程x = g x(2-2)這里映象g : DRn > Rn。方程(2-2)的解x* (即 x*二gx* )稱為映象g的不動(dòng)點(diǎn)。因此用迭代法解方程(2-

2、1)，就是求(2-2)中映象g的不動(dòng)點(diǎn)。這樣以及g是否存在不動(dòng)點(diǎn)自然就是我們關(guān)心的問題。定理2-1若g: D Rn > Rn為有界閉集Do D上的嚴(yán)格非膨脹映象，g D。 D。，則g 在Do內(nèi)有唯一不動(dòng)點(diǎn)。證 唯一性 設(shè)g在Do內(nèi)至少有兩個(gè)不動(dòng)點(diǎn)x1，x2，則贋一 x 2| 二 gx1 gx2 - x1 一 x 2|因：,所以由上式推得X1二x2。唯一性得證。記'x =|x-gx|；，由g及泛數(shù)的連續(xù)性可知:DRn > R1連續(xù)。因Do為有界閉集，故在Do上有最小值。設(shè)x: Do為最小點(diǎn)，即x* -rpDn x gx則x*為g的不動(dòng)點(diǎn)。因?yàn)槿舨蝗?，則有 xgx*，再由g嚴(yán)格

3、非膨脹，可得*H* H III *-gxg g x - g g x 牛；x - g x 二 x這與x*為、的最小點(diǎn)相矛盾，故x*為g的不動(dòng)點(diǎn)。注 定理中Do的有界閉性、g的壓縮性和g映Do入自身，此3個(gè)條件缺一不可。例如，g x =x 1在Do =上嚴(yán)格非膨脹，但它在Do中卻沒有不動(dòng)點(diǎn)。x下面我們介紹在應(yīng)用上非常廣泛的不動(dòng)點(diǎn)定理。定理2-2 （Brouwer不動(dòng)點(diǎn)定理）設(shè)g: D Rn Rn在有解閉凸集Do D上連續(xù)，且G DoDo，則g在Do至少有一個(gè)不動(dòng)點(diǎn)。本定理在一維情形下敘述為：f：a,b a,b】則f在a,b】中至少有一個(gè)不動(dòng)點(diǎn)。幾何解釋見圖2-10圖2-1 一維Brouwer定理2

4、-2迭代格式的構(gòu)造前一節(jié)我們談到，用迭代法求解方程(2-1)，是先將這個(gè)方程化為等價(jià)的方程(2-2),然后 求映象g的不動(dòng)點(diǎn)，通常(也是最簡單的情形)構(gòu)造如下迭代序列：xk1 = gxk , k= 0,1,2;(2-3)我們希望這個(gè)迭代序列 xk 1收斂到g的不動(dòng)點(diǎn)x*，亦即方程f x =0的解。如果g是壓縮的， 可望迭代序列收斂。圖2-2展示了一維迭代收斂的一種情形。圖2-2迭代序列收斂對于(2-3)形式的迭代形式，g可以有各種表示方式。g可能只依賴于f和。如果g不依賴于迭代步k只依賴于xk，則稱迭代(2-3)為單步定常迭代。如果迭代還依賴于迭代步k，則迭代形式可表示為xk 1 = gk x

5、k ,k =0,1,2；(2-4)并稱之為單步非定常迭代。有時(shí)得到新的近似xk 1除依賴xk外，還依賴前幾次的得到信息,這時(shí)的迭代為多步迭代。例如，如獲得 x k 1依賴于k kM x ,x ,k -m 1 ,x則迭代可寫為(2-5)k*1kk m 1x = g x , x -稱這種迭代為m步迭代。類似地有m步非定常迭代。通常稱g或gk為迭代函數(shù)。用不同的方法構(gòu)造的迭代函數(shù)可得到不同的得到法。設(shè)g : D Rn > Rn，如果一個(gè)迭代法得到的序列xZ D則稱得到序列是適定的，適定性是迭代法的起碼要求。若X： D是方程(2-1)的解，且序列k 滿足k*lim x =xk_.則稱迭代序列收斂

6、于x。定義2-1設(shè)f : D Rn ； Rn， x - D是方程f x = 0的一個(gè)解。若存在x的一個(gè)鄰域 S D，使對任何初始值xS(對于m步迭代法，初值為x,xmJ S)，迭代序列 J總 是適定的且收斂于x*，則稱x*是迭代序列的吸引點(diǎn)。不少迭代法都是設(shè)法使迭代函數(shù) g是壓縮的，這時(shí)迭代序列的吸引點(diǎn)恰是 g的不動(dòng)點(diǎn)。 有時(shí)候也可使g具有某種單調(diào)性，構(gòu)成單調(diào)單調(diào)法。2-3迭代法的收斂性與收斂階前面談到，一個(gè)迭代法，當(dāng)其產(chǎn)生的迭代序列在適定和收斂時(shí)才有意義。單步迭代格式(2-3)在實(shí)際中被采用得最多，這里，我們不加證明地給出三個(gè)與(2-3)格式有關(guān)的收斂性定理。定理2-4設(shè)x *是方程x=gx

7、的解，g: D Rn-； Rn。若存在一個(gè)開球S = S x*廠D和常數(shù)很5 |0,1，使得對一切x S，有|g x - g x* - ax- x*(2-7)則對任意x0 S，x*是迭代序列(2-3)的一個(gè)吸引點(diǎn)。定理2-5 (Ostrowski)設(shè)映象g: DRn > Rn有一不動(dòng)點(diǎn)x： int D，且在x*處F-可導(dǎo)，g x*的譜半徑(即特征值的最大模)? g x- -1(2-9)則存在開球S=S x*,.D，對任意初值x S，x*是迭代序列的一個(gè)吸引點(diǎn)。定理2-4與2-5都是指出迭代在解的小球中即解的充分小的鄰域中收斂，這種收斂稱為局部收斂，也就是說在已知方程(2-1)的解存在的情

8、況下討論的。如果在不知道方程(2-1)的解是否存在的情況下，只根據(jù)迭代初始近似x0滿足的條件就能證明迭代序列 x kk=0,1匚收斂到方程的解x*，就稱這種迭代法具有半局部收斂性。局部收斂性與半局部收斂性都要求初始 近似x0充分接近解x*，這給實(shí)際計(jì)算帶來很大的不便。如果一個(gè)迭代法對求解域D中任一點(diǎn)x0作為近似，迭代序列&5=0,1廣都能收斂到所求方程的解，這種收斂稱為大范圍收斂， 這種收斂對實(shí)際計(jì)算很有意義。對于定理2-5中的g若是仿射的，即g x = Ax b , A L Rn，則條件(2-9)變?yōu)锳 : 1， 它是用迭代法解線性方程組Ax b的收斂的充分必要條件，而對非線性方程組

9、而言，條件(2-9)僅為迭代(2-3)局部收斂的充分條件，這是線性和非線性的不同之處。下面我們給出一個(gè)非常實(shí)用的判斷迭代全局收斂的定理。定理2-6設(shè)D敘公2,，Xn q乞Xj乞by這里ai，bi，(i=1/, n)為常數(shù)，映象g:DRn>Rn具有一階連續(xù)偏導(dǎo)數(shù)，g D D。若存在常數(shù)L ：1滿足|：gi xl L, r D(2-10)| X n這里gi x為g x的第i個(gè)分量函數(shù)，則迭代序列(2-3)對于任意初始近似x' D收斂于g的不 動(dòng)點(diǎn)x* D，并且有估計(jì)x1 - xLk<:1 -L對于一個(gè)迭代法，除了考慮其收斂性，研究其收斂速度對實(shí)際計(jì)算也是十分重要的。為 了衡量收斂速度，我們這里引入收斂階的概念。定義2-2設(shè)迭代序列Jk k =0,1廠收斂至U x*，如果存在p 31及常數(shù)a > 0，使得當(dāng)k王ko時(shí) 有卜心 一x蘭a