1、第二章 迭代法的一般原理非線性方程組無論從理論上還是計算方法上，都比線性方程組復(fù)雜得多。一般的非線性方程組很難求出解析解，往往只能求出其數(shù)值解，且往往只能借助于迭代法。本章我們將討論迭代法的一般原理、迭代法的一般構(gòu)造及迭代收斂速度的衡量標準。2-1 迭代法與不動點定理設(shè)，考慮方程(2-1)若存在，使，則稱為方程(2-1) 的解。用迭代法求解(2-1) ，先將(2-1)化為等價的方程(2-2)這里映象。方程(2-2)的解(即)稱為映象g的不動點。因此用迭代法解方程(2-1)，就是求(2-2)中映象g的不動點。這樣以及g是否存在不動點自然就是我們關(guān)心的問題。定理2-1 若為有界閉集上的嚴格非膨脹映

2、象，則g在內(nèi)有唯一不動點。證 唯一性 設(shè)g在內(nèi)至少有兩個不動點，則因，所以由上式推得。唯一性得證。記，由g及泛數(shù)的連續(xù)性可知連續(xù)。因為有界閉集，故j在上有最小值。設(shè)為最小點，即則為g的不動點。因為若不然，則有，再由g嚴格非膨脹，可得這與為j的最小點相矛盾，故為g的不動點。注 定理中的有界閉性、g的壓縮性和g映入自身，此3個條件缺一不可。例如，在上嚴格非膨脹，但它在中卻沒有不動點。下面我們介紹在應(yīng)用上非常廣泛的不動點定理。定理2-2 (Brouwer不動點定理) 設(shè)在有解閉凸集上連續(xù)，且，則g在至少有一個不動點。本定理在一維情形下敘述為： 則f在中至少有一個不動點。幾何解釋見圖2-1。xybaa

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

4、非定常迭代。有時得到新的近似除依賴外，還依賴前幾次的得到信息，這時的迭代為多步迭代。例如，如獲得依賴于則迭代可寫為(2-5)稱這種迭代為m步迭代。類似地有m步非定常迭代。通常稱g或為迭代函數(shù)。用不同的方法構(gòu)造的迭代函數(shù)可得到不同的得到法。設(shè)，如果一個迭代法得到的序列則稱得到序列是適定的，適定性是迭代法的起碼要求。若是方程(2-1)的解，且序列滿足則稱迭代序列收斂于。定義2-1 設(shè)，是方程的一個解。若存在的一個鄰域，使對任何初始值(對于m步迭代法，初值為 )，迭代序列總是適定的且收斂于，則稱是迭代序列的吸引點。不少迭代法都是設(shè)法使迭代函數(shù)g是壓縮的，這時迭代序列的吸引點恰是g的不動點。有時候也可

5、使g具有某種單調(diào)性，構(gòu)成單調(diào)單調(diào)法。2-3 迭代法的收斂性與收斂階前面談到，一個迭代法，當其產(chǎn)生的迭代序列在適定和收斂時才有意義。單步迭代格式(2-3)在實際中被采用得最多，這里，我們不加證明地給出三個與(2-3)格式有關(guān)的收斂性定理。定理2-4 設(shè)是方程的解，。若存在一個開球S = 和常數(shù)，使得對一切，有(2-7)則對任意，是迭代序列(2-3)的一個吸引點。定理2-5 (Ostrowski) 設(shè)映象有一不動點，且在處F-可導，的譜半徑(即特征值的最大模)(2-9)則存在開球，對任意初值，是迭代序列的一個吸引點。定理2-4與2-5都是指出迭代在解的小球中即解的充分小的鄰域中收斂，這種收斂稱為局

6、部收斂，也就是說在已知方程(2-1)的解存在的情況下討論的。如果在不知道方程(2-1)的解是否存在的情況下，只根據(jù)迭代初始近似滿足的條件就能證明迭代序列收斂到方程的解，就稱這種迭代法具有半局部收斂性。局部收斂性與半局部收斂性都要求初始近似充分接近解，這給實際計算帶來很大的不便。如果一個迭代法對求解域D中任一點作為近似，迭代序列都能收斂到所求方程的解，這種收斂稱為大范圍收斂，這種收斂對實際計算很有意義。對于定理2-5中的g若是仿射的，即，則條件(2-9) 變?yōu)椋怯玫ń饩€性方程組的收斂的充分必要條件，而對非線性方程組而言，條件(2-9) 僅為迭代(2-3)局部收斂的充分條件，這是線性和非線性的不同之處。下面我們給出一個非常實用的判斷迭代全局收斂的定理。定理2-6設(shè)這里，()為常數(shù)，映象具有一階連續(xù)偏導數(shù)，。若存在常數(shù)滿足(2-10)這里為的第i個分量函數(shù)，則迭代序列(2-3)對于任意初始近似收斂于g的不動點，并且有估計對于一個迭代法，除了考慮其收斂性，研究其收斂速度對實際計算也是十分重要的。為了衡量收斂速度，我們這里引入收斂階的概念。定義2-2 設(shè)迭代序列收斂到，如果存在及常數(shù)