第六章方程求根

第六章方程求根第1頁，課件共85頁，創(chuàng)作于2023年2月如果f(x)可以分解成

其中m為正整數(shù)且則稱x*是f(x)的m重零點,或方程f(x)=0的m重根.若f(x)存在m階導(dǎo)數(shù),則是方程f(x)的m重根(m>1)當且僅當當m=1時稱x*為單根.零點或根的重數(shù)第2頁，課件共85頁，創(chuàng)作于2023年2月

當f(x)不是x的線性函數(shù)時,稱對應(yīng)的函數(shù)方程為非線性方程.如果f(x)是多項式函數(shù),則稱為代數(shù)方程,若f(x)是三角函數(shù)、指數(shù)函數(shù)、對數(shù)函數(shù)等,稱為超越方程.一般稱n次多項式構(gòu)成的方程為n次代數(shù)方程,當n＞1時,方程顯然是非線性的一般稍微復(fù)雜的3次以上的代數(shù)方程或超越方程,很難甚至無法求得精確解.第3頁，課件共85頁，創(chuàng)作于2023年2月記筆記

本章將介紹常用的求解非線性方程的近似根的幾種數(shù)值解法區(qū)間法迭代法Newton法弦截法拋物線法….逐步搜索法二分法….第4頁，課件共85頁，創(chuàng)作于2023年2月

通常方程求根的數(shù)值解法大致分為三個步驟進行①

判定根的存在性.

即方程有沒有根？如果有根,有幾個根？②確定根的分布范圍.

即將每一個根用區(qū)間隔離開來,這個過程實際上是獲得方程各根的初始近似值.③根的精確化.

將根的初始近似值按某種方法逐步精確化,直到滿足預(yù)先要求的精度為止第5頁，課件共85頁，創(chuàng)作于2023年2月本章介紹方程求根的數(shù)值解法,它既可以用來求解代數(shù)方程,也可以用來解超越方程,并且僅限于求方程的實根.

運用迭代解方程的根應(yīng)解決以下兩個問題：確定根的初值;將進一步精確化到所需要的精度.記筆記第6頁，課件共85頁，創(chuàng)作于2023年2月6.1.1逐步搜索法

為明確起見，不妨假定f(a)<0,f(b)>0.從有根區(qū)間[a,b]的左端的x0=a出發(fā)，按照某個預(yù)定的步長h一步一步地向右跨，每跨一步進行一次根的“搜索”，即檢查節(jié)點xk=a+kh上的函數(shù)值f(xk)的符號，一旦發(fā)現(xiàn)f(xk)與f(a)異號,則可以確定一個縮小了的有根區(qū)間[xk-1,xk],其寬度等于預(yù)定的步長h第7頁，課件共85頁，創(chuàng)作于2023年2月例6.1

方程f(x)=x3-x-1=0,確定其有根區(qū)間.xf(x)00.51.01.5

–––+可以看出,在[1.0,1.5]內(nèi)必有一根.解：不難發(fā)現(xiàn)f(0)<0,f(2)>0,知f(x)在區(qū)間(0,2)內(nèi)至有一個實根設(shè)從x=0出發(fā),取h=0.5為步長向右進行根的搜索,列表如下第8頁，課件共85頁，創(chuàng)作于2023年2月用逐步搜索法的關(guān)鍵是選取步長h只要h取得足夠小,利用此法可以得到具有任意精度的近似根.

相應(yīng)的,所需要的搜索步數(shù)增多，計算量增大

第9頁，課件共85頁，創(chuàng)作于2023年2月6.1.2二分法

二分法又稱二分區(qū)間法,是求解方程(6.1)的近似根的一種常用的簡單方法.二分法的基本思想:首先確定有根區(qū)間,將區(qū)間二等分,通過判斷f(x)的符號,逐步將有根區(qū)間縮小,直至有根區(qū)間足夠地小,便可求出滿足精度要求的近似根.第10頁，課件共85頁，創(chuàng)作于2023年2月①取有根區(qū)間[a,b]的中點將區(qū)間分為兩個小區(qū)間,然后在[a,x0]和[x0,b]中確定新的有根區(qū)間，記其為[a1,b1]求根過程第11頁，課件共85頁，創(chuàng)作于2023年2月②對壓縮了的有根區(qū)間施行同樣的手法,即取中點,將區(qū)間再分為兩半,然后再確定有根區(qū)間,其長度是的二分之一③如此反復(fù)下去,若不出現(xiàn),即可得出一系列有根區(qū)間序列：上述每個區(qū)間都是前一個區(qū)間的一半,因此的長度

當k→∞時趨于零,這些區(qū)間最終收斂于一點x*

即為所求的根

.第12頁，課件共85頁，創(chuàng)作于2023年2月

每次二分后,取有根區(qū)間的中點作為根的近似值,得到一個近似根的序列

該序列以根x*為極限只要二分足夠多次(即k足夠大),便有這里ε為給定精度,由于,則(6.2)第13頁，課件共85頁，創(chuàng)作于2023年2月當給定精度ε＞0后,要想成立,只要取k滿足即可,亦即當:

時,計算得到的就是滿足精度要求的近似根

.在程序中通常用相鄰的與的差的絕對值或與的差的絕對值是否小于ε來決定二分區(qū)間的次數(shù).

第14頁，課件共85頁，創(chuàng)作于2023年2月

二分法算法實現(xiàn)第15頁，課件共85頁，創(chuàng)作于2023年2月例6.2求方程f(x)=x3-x-1=0在區(qū)間[1.0,1.5]內(nèi)的一個實根,使誤差不超過0.5×10-2.第16頁，課件共85頁，創(chuàng)作于2023年2月且f(x)在[2,3]上連續(xù),故方程f(x)=0在[2,3]內(nèi)至少有一個根.證明令由例6.3

證明方程在區(qū)間[2,3]內(nèi)有一個根,使用二分法求誤差不超過0.5×10-3的根要二分多少次？又當時故f(x)在[2,3]上是單調(diào)遞增函數(shù),從而f(x)在[2,3]上有且僅有一根.第17頁，課件共85頁，創(chuàng)作于2023年2月誤差限為只要取k滿足

即可,亦即所以需二分10次便可達到要求.

給定誤差限

＝0.5×10-3,使用二分法時第18頁，課件共85頁，創(chuàng)作于2023年2月二分法的優(yōu)點是不管有根區(qū)間多大,總能求出滿足精度要求的根,且對函數(shù)f(x)的要求不高,只要連續(xù)即可,計算亦簡單;它的局限性是只能用于求函數(shù)的實根,不能用于求復(fù)根及重根,它的收斂速度與比值為的等比級數(shù)相同.第19頁，課件共85頁，創(chuàng)作于2023年2月6.2迭代法6.2.1

迭代法過程的收斂性為求解非線性方程f(x)=0的根,先將其寫成便于迭代的等價方程

(6.3)其中為x的連續(xù)函數(shù).即第20頁，課件共85頁，創(chuàng)作于2023年2月任取一個初值代入式的右端,得到

再將代入式的右端,得到式(6.3)稱為求解非線性方程的簡單迭代法,稱為迭代函數(shù)

.

(6.4)依此類推,得到一個數(shù)列如果由迭代格式產(chǎn)生的序列收斂,即

則稱迭代法收斂.此時x*就是方程f(x)=0的根.

第21頁，課件共85頁，創(chuàng)作于2023年2月迭代法的幾何意義

通常將方程f(x)=0化為與它同解的方程的方法不止一種,有的收斂,有的不收斂,這取決于的性態(tài),方程的求根問題在幾何上就是確定曲線y=

與直線y=x的交點P*的橫坐標(下圖所示)

(a)(b)第22頁，課件共85頁，創(chuàng)作于2023年2月第23頁，課件共85頁，創(chuàng)作于2023年2月例6.4

用迭代法求方程在x=1.5附近的一個根解將方程改寫成如下兩種等價形式

相應(yīng)地可得到兩個迭代公式如果取初始值＝1.5,用上述兩個迭代公式分別迭代,計算結(jié)果第24頁，課件共85頁，創(chuàng)作于2023年2月kxk012345671.51.357211.330861.325881.324941.324761.324731.32472收斂！發(fā)散！第25頁，課件共85頁，創(chuàng)作于2023年2月迭代法收斂的條件對方程f(x)=0可以構(gòu)造不同的迭代公式,但迭代公式并非總是收斂.那么,當?shù)瘮?shù)滿足什么條件時,相應(yīng)的迭代公式才收斂呢？即使迭代收斂時,我們也不可能迭代很多次,而是迭代有限次后就停止,這就需要估計迭代值的誤差,以便適時終止迭代.

第26頁，課件共85頁，創(chuàng)作于2023年2月定理6.1

假定函數(shù)在[a,b]上具有連續(xù)的一階導(dǎo)數(shù),且滿足下列兩項條件：

對任意的x∈[a,b]

有

∈[a,b]，

存在

0<L<1

,使所有的x∈[a,b],有

≤L<1則方程在[a,b]上的解存在且唯一,且對任意的∈[a,b],迭代過程均收斂于.并有誤差估計式

(6.5)(6.6)第27頁，課件共85頁，創(chuàng)作于2023年2月定理6.1’

假定函數(shù)在[a,b]上連續(xù)，且滿足下列兩項條件：

對任意的x∈[a,b]

有

∈[a,b]，

存在

0<L<1

,使所有的

∈[a,b],有則方程在[a,b]上的解存在且唯一,且對任意的∈[a,b],迭代過程均收斂于.并有誤差估計式

(6.5)(6.6)第28頁，課件共85頁，創(chuàng)作于2023年2月

實際計算中當然不可能無窮多步地做下去,

由(6.5)時結(jié)束迭代并取預(yù)先給定精度要求ε,當?shù)?9頁，課件共85頁，創(chuàng)作于2023年2月迭代法的算法框圖第30頁，課件共85頁，創(chuàng)作于2023年2月例6.5

對方程,構(gòu)造收斂的迭代格式,求其一個正根,計算過程保留4位小數(shù).解容易判斷[1,2]是方程的有根區(qū)間,且在此區(qū)間內(nèi),所以此方程在區(qū)間[1,2]有且僅有一根.將原方程改寫成以下兩種等價形式.

①

,即

不滿足收斂條件.②,即此時迭代公式滿足迭代收斂條件.第31頁，課件共85頁，創(chuàng)作于2023年2月局部收斂性在實際應(yīng)用迭代法時，通常在所求的根x*的鄰近進行考察，即研究其局部收斂性.定義6.1

若存在x*的某個領(lǐng)域使迭代過程對于任意初值均收斂，則稱迭代過程在根x*鄰近具有局部收斂性.定理6.2

設(shè)x*為方程

的根,在x*的鄰近有連續(xù)的一階導(dǎo)數(shù),且則迭代過程在x*鄰近具有局部收斂性.第32頁，課件共85頁，創(chuàng)作于2023年2月例6.6求方程x=e-x在x=0.5附近的一個根,要求精度ε=10-5.解：

對x=0.5以h=0.1為步長搜索一次,得(0.5,0.6)為有根區(qū)間.對可知從而在根的附近有，因此迭代公式對于初值x0=0.5是收斂的.第33頁，課件共85頁，創(chuàng)作于2023年2月例6.7

設(shè),要使迭代過程局部收斂到,求的取值范圍.解：

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

第34頁，課件共85頁，創(chuàng)作于2023年2月假定改變不大,近似地取某個近似值L,則由設(shè)是根的某個近似值,用迭代公式校正一次得6.2.2

迭代公式的加工

又根據(jù)中值定理有得令比更好的近似值（1）加權(quán)法第35頁，課件共85頁，創(chuàng)作于2023年2月校正：

改進：或合并寫成：第36頁，課件共85頁，創(chuàng)作于2023年2月仍取,逐次計算得=0.56658，…

=0.56714.

迭代4次便可得到精度的結(jié)果,而不用加速技術(shù)需迭代18次,效果顯著.例6.8

用加權(quán)法加速技術(shù)求解方程在0.5附近的一個根.解：由前面知在x0=0.5附近收斂.

又在x0=0.5附近，

加速公式的具體形式為第37頁，課件共85頁，創(chuàng)作于2023年2月但上述加速方案需要計算L，實際使用不便.對于用迭代公式再校正一次得同理可得又已知聯(lián)立消去L得推得（2）Aitken加速方法第38頁，課件共85頁，創(chuàng)作于2023年2月校正：

再校正：改進：Aitken加速方法第39頁，課件共85頁，創(chuàng)作于2023年2月校正：

再校正：改進：Aitken加速方法第40頁，課件共85頁，創(chuàng)作于2023年2月例6.9

用Aitken方法求方程解取x0=1.5，迭代格式是發(fā)散的.用Aitken方法進行加速，有第41頁，課件共85頁，創(chuàng)作于2023年2月

用迭代法可逐步精確方程根的近似值,但必須要找到的等價方程,如果選得不合適,不僅影響收斂速度,而且有可能造成迭代格式發(fā)散.能否找到一種迭代方法,既結(jié)構(gòu)簡單,收斂速度快,又不存在發(fā)散的問題？這就是本節(jié)要介紹的Newton法.6.3.1

Newton公式牛頓迭代法一種重要和常用的迭代法,它的基本思想是將非線性函數(shù)f(x)逐步線性化,從而將非線性方程f(x)=0近似地轉(zhuǎn)化為線性方程求解.6.3Newton法

第42頁，課件共85頁，創(chuàng)作于2023年2月將右端取為,即是比更接近于的近似值對于方程,設(shè)其近似根為,

函數(shù)f(x)可在附近作泰勒展開

忽略高次項,用其線性部分作為函數(shù)f(x)的近似,設(shè)的根,則有,即這就是著名的Newton公式(6.7)第43頁，課件共85頁，創(chuàng)作于2023年2月6.3.2

Newton法的幾何解釋

方程f(x)=0的根x*是曲線y=f(x)與x軸交點的橫坐標,設(shè)xk是根x*的某個近似值,過曲線y=f(x)的橫坐標為xk的點Pk=(xk,f(xk))引切線交x軸于xk+1

,并將其作為x*新的近似值,重復(fù)上述過程,可見一次次用切線方程來求解方程f(x)=0的根,所以亦稱為Newton切線法.第44頁，課件共85頁，創(chuàng)作于2023年2月定義6.2

設(shè)迭代過程收斂于的根如果迭代誤差當時成立下列漸進關(guān)系式:則稱該迭代過程是p階收斂的.6.3.3

Newton法的局部收斂性

一種迭代法具有實用價值，首先要求它是收斂的，其次還要求它收斂得比較快.注：p=1時稱為線性收斂；

p=2時稱為平方收斂；1<p<2時稱為超線性收斂.

數(shù)p的大小反映了迭代法收斂的速度的快慢，p愈大，則收斂的速度愈快，故迭代法的收斂階是對迭代法收斂速度的一種度量.

(為常數(shù))第45頁，課件共85頁，創(chuàng)作于2023年2月定理6.3對于迭代過程如果在所求根的鄰近連續(xù),并且則稱該迭代過程在點鄰近是p階收斂的.注：設(shè)是方程的單根,且f(x)在的某鄰域內(nèi)有連續(xù)的二階導(dǎo)數(shù),則牛頓法在附近局部收斂,且至少二階收斂.注：由定理可知，迭代速度依賴于迭代函數(shù)的選取，如果當時，則該迭代過程只可能是線性收斂.

第46頁，課件共85頁，創(chuàng)作于2023年2月重根情形(6.8)第47頁，課件共85頁，創(chuàng)作于2023年2月(6.9)第48頁，課件共85頁，創(chuàng)作于2023年2月kxk(1)(2)(3)0123x0x1x2x31.51.4583333331.4366071431.4254976191.51.4166666671.4142156861.4142135621.51.4117647061.4142114381.414213562第49頁，課件共85頁，創(chuàng)作于2023年2月Newton法的算法實現(xiàn)第50頁，課件共85頁，創(chuàng)作于2023年2月例6.10

用Newton法解方程

xex

-1=0.解：因f(xk)=xex

–1,f`(x)=ex

(

x+1) 建立迭代公式

取x0=0.5,逐次計算得

x1=0.57102,

x2=0.56716,

x3=0.56714第51頁，課件共85頁，創(chuàng)作于2023年2月例6.11已知迭代公式收斂于

證明該迭代公式平方收斂.將代入,根據(jù)定理6.3可知,迭代公式平方收斂.證:迭代公式相應(yīng)的迭代函數(shù)為第52頁，課件共85頁，創(chuàng)作于2023年2月6.3.4Newton法應(yīng)用舉例(1)計算迭代對于任意初值x0>0都是收斂的.迭代公式為

迭代公式為

(2)計算1/a迭代對于初值0<x0<2/a都是收斂的.第53頁，課件共85頁，創(chuàng)作于2023年2月6.3.5

Newton下山法

通常,Newton法的收斂性依賴于初始值的選取,如果偏離所求的根比較遠,則Newton法可能發(fā)散.第54頁，課件共85頁，創(chuàng)作于2023年2月為了防止迭代發(fā)散,我們對Newton法的迭代過程再附加一項要求,即具有單調(diào)性

將Newton法與下山法結(jié)合起來使用,即在下山法保證函數(shù)值下降的前提下,用Newton法加快收斂速度.把這一算法稱為Newton下山法.滿足這項要求的算法稱為下山法.第55頁，課件共85頁，創(chuàng)作于2023年2月

為此，將Newton法的計算結(jié)果與前一步的近似值xk適當平均作為新的改進值，即其中稱為下山因子.挑選下山因子時，希望使單調(diào)性條件成立.第56頁，課件共85頁，創(chuàng)作于2023年2月

下山因子的選擇是個逐步探索的過程,設(shè)從

=1開始反復(fù)將

減半進行試算,即逐次取

為從中挑選下山因子,直至找到其中某個

使單調(diào)性條件成立,則稱“下山成功”,否則“下山失敗”,這時需另選初值重算.第57頁，課件共85頁，創(chuàng)作于2023年2月現(xiàn)在設(shè)法利用迭代過程中的“老”信息來回避導(dǎo)數(shù)值的計算.6.4弦截法與拋物線法Newton法雖然具有收斂速度快的優(yōu)點,但每迭代一次都要計算導(dǎo)數(shù)

當比較復(fù)雜時,提供它的導(dǎo)數(shù)值往往是有困難的導(dǎo)出這類求根方法的基礎(chǔ)是插值原理.第58頁，課件共85頁，創(chuàng)作于2023年2月設(shè)是f(x)=0的一組近似根,利用函數(shù)值構(gòu)造插值多項式Pr(x),

并適當選取Pr(x)=0的一個根作為f(x)=0的新的近似根xk+1,這就確定了一個新的迭代過程，記迭代函數(shù)為則有第59頁，課件共85頁，創(chuàng)作于2023年2月6.4.1

弦截法(1)迭代公式

相應(yīng)的迭代法稱為弦截法.(2)幾何意義(3)收斂速度第60頁，課件共85頁，創(chuàng)作于2023年2月定理6.4假設(shè)f(x)在根的鄰域內(nèi)具有二階連續(xù)導(dǎo)數(shù)，且對于任意有又初值,那么當鄰域充分小時，弦截法將按收斂到根弦截法具有超線性收斂！第61頁，課件共85頁，創(chuàng)作于2023年2月弦截法算法實現(xiàn)

第62頁，課件共85頁，創(chuàng)作于2023年2月例6.13

用弦截法方程解：取

令利用弦截迭代公式計算第63頁，課件共85頁，創(chuàng)作于2023年2月6.4.2

拋物線法(1)迭代公式第64頁，課件共85頁，創(chuàng)作于2023年2月(2)幾何意義(3)收斂速度例6.14

用拋物線法方