方程求根的迭代法第1頁，共51頁，2023年，2月20日，星期五本章處理二分法和牛頓法在第二節(jié)課已講過。加深算法收斂性方面的理解。介紹幾種新方法。第2頁，共51頁，2023年，2月20日，星期五引言在科學(xué)研究和工程設(shè)計中,經(jīng)常會遇到的一大類問題是非線性方程

f(x)=0的求根問題，其中f(x)為非線性函數(shù)。方程f(x)=0的根,亦稱為函數(shù)f(x)的零點如果f(x)可以分解成,其中m為正整數(shù)且,則稱x*是f(x)的m重零點,或稱方程f(x)=0的m重根。當(dāng)m=1時稱x*為單根。若f(x)存在m階導(dǎo)數(shù),則是方程f(x)的m重根(m>1)當(dāng)且僅當(dāng)?shù)?頁，共51頁，2023年，2月20日，星期五記筆記當(dāng)f(x)不是x的線性函數(shù)時，稱對應(yīng)的函數(shù)方程為非線性方程。如果f(x)是多項式函數(shù)，則稱為代數(shù)方程，否則稱為超越方程（三角方程，指數(shù)、對數(shù)方程等）。一般稱n次多項式構(gòu)成的方程為n次代數(shù)方程,當(dāng)n＞1時,方程顯然是非線性的一般稍微復(fù)雜的3次以上的代數(shù)方程或超越方程,很難甚至無法求得精確解。本章將介紹常用的求解非線性方程的近似根的幾種數(shù)值解法第4頁，共51頁，2023年，2月20日，星期五數(shù)值解法步驟①

判定根的存在性。即方程有沒有根？如果有根，有幾個根？②確定根的分布范圍。即將每一個根用區(qū)間隔離開來，這個過程實際上是獲得方程各根的初始近似值。③根的精確化。將根的初始近似值按某種方法逐步精確化，直到滿足預(yù)先要求的精度為止第5頁，共51頁，2023年，2月20日，星期五二分法（略）復(fù)習(xí)作業(yè)題第6頁，共51頁，2023年，2月20日，星期五不動點迭代對于一般的非線性方程,沒有通常所說的求根公式求其精確解,需要設(shè)計近似求解方法,即迭代法。它是一種逐次逼近的方法,用某個固定公式反復(fù)校正根的近似值,使之逐步精確化，最后得到滿足精度要求的結(jié)果。迭代法的基本思想為求解非線性方程f(x)=0的根，先將其寫成便于迭代的等價方程

其中為x的連續(xù)函數(shù)第7頁，共51頁，2023年，2月20日，星期五即如果數(shù)使f(x)=0,則也有,反之,若,則也有,稱為迭代函數(shù)

任取一個初值,代入式的右端,得到

再將代入式的右端,得到,依此類推,得到一個數(shù)列…，其一般表示稱為求解非線性方程的簡單迭代法。第8頁，共51頁，2023年，2月20日，星期五如果由迭代格式產(chǎn)生的序列收斂,即則稱迭代法收斂。實際計算中當(dāng)然不可能也沒必要無窮多步地做下去,對預(yù)先給定的精度要求ε，只要某個k滿足即可結(jié)束計算并取當(dāng)然，迭代函數(shù)的構(gòu)造方法是多種多樣的。第9頁，共51頁，2023年，2月20日，星期五例1用迭代法求方程在x=1.5附近的一個根解將方程改寫成如下兩種等價形式

相應(yīng)地可得到兩個迭代公式如果取初始值＝1.5，用上述兩個迭代公式分別迭代，計算結(jié)果第10頁，共51頁，2023年，2月20日，星期五kxk012345671.51.357211.330861.325881.324941.324761.324731.32472第11頁，共51頁，2023年，2月20日，星期五幾何意義通常將方程f(x)=0化為與它同解的方程的方法不止一種,有的收斂,有的不收斂,這取決于的性態(tài),方程的求根問題在幾何上就是確定曲線y=與直線y=x的交點P*的橫坐標(biāo)(a)(b)第12頁，共51頁，2023年，2月20日，星期五幾何意義第13頁，共51頁，2023年，2月20日，星期五

對方程f(x)=0可以構(gòu)造不同的迭代公式,但迭代公式并非總是收斂。那么,當(dāng)?shù)瘮?shù)滿足什么條件時，相應(yīng)的迭代公式才收斂呢？即使迭代收斂時，我們也不可能迭代很多次，而是迭代有限次后就停止，這就需要估計迭代值的誤差，以便適時終止迭代。不動點迭代收斂性第14頁，共51頁，2023年，2月20日，星期五定理1，2

設(shè)函數(shù)在[a,b]上具有連續(xù)的一階導(dǎo)數(shù),且滿足（1）對所有的x∈[a,b]有∈[a,b]（2）存在0<L<1,使所有的x∈[a,b]有≤L則方程在[a,b]上的解存在且唯一，對任意的∈[a,b]，迭代過程均收斂于。并有誤差估計式①

②第15頁，共51頁，2023年，2月20日，星期五由連續(xù)函數(shù)介值定理知,必有∈[a,b],使所以有解存在,即假設(shè)有兩個解和,,∈[a,b]，則，由微分中值定理有

其中ξ是介于x*和之間的點從而有ξ∈[a,b]，進(jìn)而有由條件(2)有<1,所以-=0，即=，解唯一。證:構(gòu)造函數(shù),由條件（1）對任意的x∈[a,b]

∈[a,b]有第16頁，共51頁，2023年，2月20日，星期五按迭代過程,有

由于L<1,所以有,可見L越小,收斂越快再證誤差估計式①②第17頁，共51頁，2023年，2月20日，星期五∵

∴即①得證。

即②得證。

第18頁，共51頁，2023年，2月20日，星期五例2對方程,構(gòu)造收斂的迭代格式,求其最小正根,計算過程保留4位小數(shù)。解容易判斷[1,2]是方程的有根區(qū)間,且在此區(qū)間內(nèi),所以此方程在區(qū)間[1,2]有且僅有一根。將原方程改寫成以下兩種等價形式。① ,即不滿足收斂條件。②,即此時迭代公式滿足迭代收斂條件。第19頁，共51頁，2023年，2月20日，星期五局部收斂性當(dāng)?shù)瘮?shù)較復(fù)雜時,通常只能設(shè)法使迭代過程在根的鄰域(局部)收斂。定理3設(shè)在的根的鄰域中有連續(xù)的一階導(dǎo)數(shù),且則迭代過程具有局部收斂性。證:由于,存在充分小鄰域△:,使成立這里L(fēng)為某個定數(shù),根據(jù)微分中值定理當(dāng)故有由定理1知對于任意的都收斂第20頁，共51頁，2023年，2月20日，星期五例3設(shè),要使迭代過程局部收斂到,求的取值范圍。解：

由在根鄰域具有局部收斂性時,收斂條件所以

第21頁，共51頁，2023年，2月20日，星期五例4已知方程在內(nèi)有根,且在上滿足,利用構(gòu)造一個迭代函數(shù),使局部收斂于。解:由可得,

故,迭代公式局部收斂第22頁，共51頁，2023年，2月20日，星期五迭代法的收斂速度一種迭代法具有實用價值，首先要求它是收斂的，其次還要求它收斂得比較快。定義2.2設(shè)迭代過程收斂于的根,記迭代誤差若存在常數(shù)p（p≥1）和c（c>0），使則稱序列是p階收斂的,c稱漸近誤差常數(shù)。特別地,p=1時稱為線性收斂,p=2時稱為平方收斂。1<p<2時稱為超線性收斂。數(shù)p的大小反映了迭代法收斂的速度的快慢，p愈大，則收斂的速度愈快，故迭代法的收斂階是對迭代法收斂速度的一種度量。

第23頁，共51頁，2023年，2月20日，星期五定理4設(shè)迭代過程,若在所求根的鄰域連續(xù)且

則迭代過程在鄰域是p階收斂的。證:由于即在鄰域

,所以有局部收斂性,將在處泰勒展開根據(jù)已知條件得由迭代公式及有第24頁，共51頁，2023年，2月20日，星期五例5已知迭代公式收斂于證明該迭代公式平方收斂。證:迭代公式相應(yīng)的迭代函數(shù)為將代入，根據(jù)定理4可知，迭代公式平方收斂。為了使迭代過程收斂或提高收斂的速度,可設(shè)法①提高初值的精度以減少迭代的次數(shù)②提高收斂的階數(shù)p第25頁，共51頁，2023年，2月20日，星期五設(shè)是根的某個近似值,用迭代公式校正一次得又根據(jù)中值定理有其中

當(dāng)范圍不大時,設(shè)變化不大,其估計值為L,則有可見,若將迭代值與加權(quán)平均,則可得到的是比更好的近似根迭代法的加速（加權(quán)法）第26頁，共51頁，2023年，2月20日，星期五迭代：

改進(jìn)：

或合并寫成：

第27頁，共51頁，2023年，2月20日，星期五例6用加權(quán)法加速技術(shù)求方程在0.5附近的一個根。解：因為在附近取L=-0.6，建立如下迭代公式仍取,逐次計算得=0.56658…=0.56714。迭代4次便可得到精度的結(jié)果,而不用加速技術(shù)需迭代18次,效果顯著。第28頁，共51頁，2023年，2月20日，星期五埃特金（Aitken）方法在加權(quán)法中,估計L的值有時不太方便。假設(shè)在求得以后,先求出由,利用中值定理可得(在求根區(qū)間變化不大,用某個定值L近似地替代之)L

將迭代值再迭代一次,得新的迭代值則將上述兩個方程聯(lián)立消去常數(shù)L化簡可得

這樣得到埃特金加速公式第29頁，共51頁，2023年，2月20日，星期五例7用埃特金方法求方程在初值附近的一個根,精度要求

取迭代格式解埃特金方法迭代格式為只迭代二次就得到滿足精度要求的解。第30頁，共51頁，2023年，2月20日，星期五牛頓迭代法（略講）基本思想是將非線性函數(shù)f(x)逐步線性化,從而將非線性方程f(x)=0近似地轉(zhuǎn)化為線性方程求解。迭代格式構(gòu)建方法：泰勒公式一階展開式。忽略高次項,用其線性部分作為函數(shù)f(x)的近似，第31頁，共51頁，2023年，2月20日，星期五牛頓迭代法的收斂性定理4設(shè)是方程的單根,且f(x)在的某鄰域內(nèi)有連續(xù)的二階導(dǎo)數(shù),則牛頓法在附近局部收斂,且至少二階收斂,有

證:牛頓迭代公式對應(yīng)的迭代函數(shù)為若是方程的單根,則有,從而由定理2

知,牛頓迭代法在附近局部收斂。又由定理3

知,迭代公式至少具有二階收斂速度。第32頁，共51頁，2023年，2月20日，星期五利用泰勒公式所以證畢第33頁，共51頁，2023年，2月20日，星期五yx0B=x0f′′(x)>0xn+1X*ayx0Bf′′(x)>0a=x0yx0B=x0f′′(x)<0ayx0Bf′′(x)<0a=x0第34頁，共51頁，2023年，2月20日，星期五yx10x0X*0x0X*x2不滿足迭代條件時，可能導(dǎo)致迭代值遠(yuǎn)離根的情況而找不到根或死循環(huán)的情況第35頁，共51頁，2023年，2月20日，星期五例8

用牛頓迭代法求x=e-x的根,ε=10-4 取x0=0.5,逐次計算得x1=0.57102,x2=0.56716，x3=0.56714解：因f(xk)=xex–1,f′(x)=ex(x+1) 建立迭代公式第36頁，共51頁，2023年，2月20日，星期五

牛頓下山法

通常,牛頓迭代法的收斂性依賴于初始值的選取,如果偏離所求的根比較遠(yuǎn),則牛頓法可能發(fā)散。為了防止迭代發(fā)散,我們對牛頓迭代法的迭代過程再附加一項要求,即具有單調(diào)性

將牛頓迭代法與下山法結(jié)合起來使用,即在下山法保證函數(shù)值下降的前提下,用牛頓迭代法加快收斂速度。把這一算法稱為牛頓下山法。即滿足這項要求的算法稱下山法。其中λ(0<λ<1)為下山因子

第37頁，共51頁，2023年，2月20日，星期五

下山因子的選擇是個逐步探索的過程，設(shè)從λ=1開始反復(fù)將λ減半進(jìn)行試算,即逐次取λ為從中挑選下山因子，直至找到其中某個λ使單調(diào)性條件成立，則稱“下山成功”，否則“下山失敗”，這時需另選初值重算。第38頁，共51頁，2023年，2月20日，星期五重根情形第39頁，共51頁，2023年，2月20日，星期五第40頁，共51頁，2023年，2月20日，星期五kxk(1)(2)(3)0123x0x1x2x31.51.4583333331.4366071431.4254976191.51.4166666671.4142156861.4142135621.51.4117647061.4142114381.414213562第41頁，共51頁，2023年，2月20日，星期五牛頓迭代法雖然具有收斂速度快的優(yōu)點，但每迭代一次都要計算導(dǎo)數(shù),當(dāng)比較復(fù)雜時,不僅每次計算帶來很多不便，而且還可能十分麻煩，如果用不計算導(dǎo)數(shù)的迭代方法，往往只有線性收斂的速度。本節(jié)介紹的弦截法便是一種不必進(jìn)行導(dǎo)數(shù)運算的求根方法。弦截法在迭代過程中不僅用到前一步處的函數(shù)值，而且還使用處的函數(shù)值來構(gòu)造迭代函數(shù)，這樣做能提高迭代的收斂速度。弦截法第42頁，共51頁，2023年，2月20日，星期五

弦截法的基本思想

為避免計算函數(shù)的導(dǎo)數(shù)，使用差商替代牛頓公式中的導(dǎo)數(shù)