方程求根的迭代法

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

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

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

其中為x的連續(xù)函數(shù)第七頁，共五十一頁，2022年，8月28日即如果數(shù)使f(x)=0,則也有,反之,若,則也有,稱為迭代函數(shù)

任取一個(gè)初值,代入式的右端,得到

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

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

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

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

②第十五頁，共五十一頁，2022年，8月28日由連續(xù)函數(shù)介值定理知,必有∈[a,b],使所以有解存在,即假設(shè)有兩個(gè)解和,,∈[a,b]，則，由微分中值定理有

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

∈[a,b]有第十六頁，共五十一頁，2022年，8月28日按迭代過程,有

由于L<1,所以有,可見L越小,收斂越快再證誤差估計(jì)式①②第十七頁，共五十一頁，2022年，8月28日∵

∴即①得證。

即②得證。

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

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

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

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

第二十三頁，共五十一頁，2022年，8月28日定理4設(shè)迭代過程,若在所求根的鄰域連續(xù)且

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

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

當(dāng)范圍不大時(shí),設(shè)變化不大,其估計(jì)值為L,則有可見,若將迭代值與加權(quán)平均,則可得到的是比更好的近似根迭代法的加速（加權(quán)法）第二十六頁，共五十一頁，2022年，8月28日迭代：

改進(jìn)：

或合并寫成：

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

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

這樣得到埃特金加速公式第二十九頁，共五十一頁，2022年，8月28日例7用埃特金方法求方程在初值附近的一個(gè)根,精度要求

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

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

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

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

用牛頓迭代法求x=e-x的根,ε=10-4 取x0=0.5,逐次計(jì)算得x1=0.57102,x2=0.56716，x3=0.56714解：因f(xk)=xex–1,f′(x)=ex(x+1) 建立迭代公式第三十六頁，共五十一頁，2022年，8月28日

牛頓下山法

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

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

第三十七頁，共五十一頁，2022年，8月28日

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

弦截法的基本思想

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