第二章非線性方程求根

第二章非線性方程求根第1頁，共90頁，2023年，2月20日，星期三第二章方程求根2.1增值尋根法與二分法2.2迭代法（重點）2.3迭代收斂的加速2.4牛頓法（重點）2.5割線法第2頁，共90頁，2023年，2月20日，星期三歷史背景代數(shù)方程的求根問題是一個古老的數(shù)學(xué)問題。理論上，n次代數(shù)方程在復(fù)數(shù)域內(nèi)一定有

n個根(考慮重數(shù))。早在16世紀(jì)就找到了三次、四次方程的求根公式，但直到19世紀(jì)才證明大于等于5次的一般代數(shù)方程式不能用代數(shù)公式求解，而對于超越方程就復(fù)雜的多，如果有解，其解可能是一個或幾個，也可能是無窮多個。一般也不存在根的解析表達(dá)式。因此需要研究數(shù)值方法求得滿足一定精度要求的根的近似解。第3頁，共90頁，2023年，2月20日，星期三根的概念給定方程f

(x)=0，如果有a使得f(a)=0，則稱a為f(x)=0的根或f(x)的零點.設(shè)有正整數(shù)m使得f(x)=(x-a)mg(x)且g(a)0，則當(dāng)m2時，稱a為f(x)=0的m重根；當(dāng)m=1時，稱為f(x)=0的單根.本章只討論實根的求法.第4頁，共90頁，2023年，2月20日，星期三

本章重點介紹求解非線性方程的幾種常見和有效的數(shù)值方法,簡單介紹一些最基本的解法.無論在理論上,還是在實際應(yīng)用中,這些數(shù)值解法都是對經(jīng)典的解析方法的突破性開拓和補(bǔ)充,許多問題的求解,在解析方法無能為力時,數(shù)值方法則可以借助于計算機(jī)出色完成.第5頁，共90頁，2023年，2月20日，星期三2.1.1增值尋根法求非線性方程確定方程的有根區(qū)間(如增值尋根法)計算根的近似值（如二分法）有根區(qū)間：存在根隔根區(qū)間：唯一根的根的方法常分為兩步：第6頁，共90頁，2023年，2月20日，星期三零點定理：設(shè)，且，則方程在區(qū)間上至少有一個根。如果在上恒正或恒負(fù)，則此根唯一。零點定理第7頁，共90頁，2023年，2月20日，星期三等步長掃描用計算機(jī)求有根區(qū)間：等步長掃描法。設(shè)h>0是給定的步長，取，若則掃描成功；否則令，繼續(xù)上述方法，直到成功。如果則掃描失敗。再將h

縮小，重復(fù)以上步驟。第8頁，共90頁，2023年，2月20日，星期三例題例設(shè)方程解：取h=0.1,掃描得：又即在有唯一根。第9頁，共90頁，2023年，2月20日，星期三設(shè)有非線性方程f(x)=0其中，f(x)為[a,b]上連續(xù)函數(shù)且設(shè) f(a)f(b)<0不妨設(shè)方程于[a,b]內(nèi)僅有一個實根。求方程實根x*的二分法過程，就是將含根區(qū)間[a,b]逐步分半，檢查函數(shù)符號的變化，以便確定含根的充分小區(qū)間。2.2二分法第10頁，共90頁，2023年，2月20日，星期三示意圖ba1b2x*ab1a2第11頁，共90頁，2023年，2月20日，星期三二分法的步驟用二分法(將區(qū)間對平分)求解。令若，則為有根區(qū)間，否則為有根區(qū)間記新的有根區(qū)間為，則且第12頁，共90頁，2023年，2月20日，星期三二分法對重復(fù)上述做法得且

第13頁，共90頁，2023年，2月20日，星期三

設(shè)所求的根為，則即取為的近似解，則

第14頁，共90頁，2023年，2月20日，星期三收斂速度可用二分法求方程實根x*的近似值到任意指定的精度。事實上，設(shè)ε為給定精度要求，試確定分半次數(shù)n使由兩邊取對數(shù)，即得且二分法收斂速度與公比為1/2的等比級數(shù)相同。第15頁，共90頁，2023年，2月20日，星期三

解:為達(dá)到要求的精度，用二分法需進(jìn)行

即最多需要11次二分。第16頁，共90頁，2023年，2月20日，星期三k1[1.0,2.0]1.52.3752[1.0,1.5]1.25-1.7968753[1.25,1.5]1.3750.1621093754[1.25,1.375]1.3125-0.8483886725[1.3125,1.375]1.34375-0.3509826666[1.34375,1.375]1.359375-0.0964088447[1.359375,1.375]1.36718750.0323557858[1.359375,1.367187500]1.36328125-0.0321499719[1.363281250,1.367187500]1.3652433750.00007202510[1.363281250,1.365234375]1.364257813-0.01604669111[1.364257813,1.365234375]1.364746094-0.00798926312[1.364746094,1.365234375]1.364990235-0.003959102計算結(jié)果

第17頁，共90頁，2023年，2月20日，星期三2.2.1迭代法基本思想對于有時可以寫成形式如：第18頁，共90頁，2023年，2月20日，星期三迭代法及收斂性考察方程。一般不能直接求出它的根。但如果給出根的某個猜測值，代入中的右端得到，再以為一個猜測值，代入的右端得反復(fù)迭代得第19頁，共90頁，2023年，2月20日，星期三簡單迭代法（單點迭代法）將變?yōu)榱硪环N等價形式。選取的某一近似值，則按遞推關(guān)系產(chǎn)生的迭代序列。這種方法算為單點迭代法。形如的迭代公式稱為多點迭代法。第20頁，共90頁，2023年，2月20日，星期三迭代法及收斂性若收斂，即則得的一個根稱此迭代過程收斂。第21頁，共90頁，2023年，2月20日，星期三迭代法的幾何意義交點的橫坐標(biāo)xyy=xx*y=(x)x0p0x1p1第22頁，共90頁，2023年，2月20日，星期三例題例試用迭代法求方程在區(qū)間(1，2)內(nèi)的實根，初始近似值?。?５。解：由建立迭代關(guān)系

k=0,1,2,3,…計算結(jié)果如下:第23頁，共90頁，2023年，2月20日，星期三例題精確到小數(shù)點后五位kxkKxk01.551.3247611.3572161.3247321.3308671.3247231.3258881.3247241.32494第24頁，共90頁，2023年，2月20日，星期三例題但如果由建立迭代公式仍取，則有，顯然結(jié)果越來越大，是發(fā)散序列第25頁，共90頁，2023年，2月20日，星期三２.２.３迭代法收斂的條件壓縮映像原理

設(shè)迭代函數(shù)在閉區(qū)間上滿足（1）（2）滿足Lipschitz條件即:有且，稱為李普希茲常數(shù)。第26頁，共90頁，2023年，2月20日，星期三壓縮映像原理則在上存在唯一解，點也稱為函數(shù)的不動點。且對，由產(chǎn)生的序列收斂于。第27頁，共90頁，2023年，2月20日，星期三壓縮映像原理證明證明：不失一般性,不妨設(shè)

否則a或b為方程的根。根的存在性令

第28頁，共90頁，2023年，2月20日，星期三壓縮映像原理證明則，即由是上的連續(xù)函數(shù)是上的連續(xù)函數(shù)。故由零點定理在上至少有一根第29頁，共90頁，2023年，2月20日，星期三壓縮映像原理證明根的唯一性假設(shè)有均為方程的根，則因為0<L<1，故：，即根是唯一的。第30頁，共90頁，2023年，2月20日，星期三壓縮映像原理證明序列的收斂性

與n無關(guān)，而0<L<1即第31頁，共90頁，2023年，2月20日，星期三誤差估計★★第32頁，共90頁，2023年，2月20日，星期三誤差估計若滿足壓縮映像原理條件，則

這是事后估計，也就是停機(jī)標(biāo)準(zhǔn)，L越小，收斂速度越快。這是事前估計。選取n，預(yù)先估計迭代次數(shù)?！铩锏?3頁，共90頁，2023年，2月20日，星期三例若取迭代函數(shù)，不滿足壓縮映像原理，故不能肯定收斂到方程的根。第34頁，共90頁，2023年，2月20日，星期三例證明函數(shù)在區(qū)間[1，2]上滿足迭代收斂條件。證明：第35頁，共90頁，2023年，2月20日，星期三

第36頁，共90頁，2023年，2月20日，星期三２.２.３迭代法收斂的條件第37頁，共90頁，2023年，2月20日，星期三2.2.3迭代法收斂的條件★★第38頁，共90頁，2023年，2月20日，星期三

滿足Lipschitz條件滿足條件１第39頁，共90頁，2023年，2月20日，星期三2.2.3迭代法收斂的條件

滿足Lipschitz條件滿足條件１第40頁，共90頁，2023年，2月20日，星期三注1：設(shè)方程

在區(qū)間內(nèi)有根

，且存在有

，則對任意初值

，且

,迭代過程

發(fā)散.第41頁，共90頁，2023年，2月20日，星期三注2：定理中的假設(shè)條件：

在一般情況下，可能對于大范圍的含根區(qū)間不滿足，而在

根的鄰近是進(jìn)成立的，為此有迭代過程局部收斂性結(jié)果：

第42頁，共90頁，2023年，2月20日，星期三２.２.２幾何示意圖

第43頁，共90頁，2023年，2月20日，星期三1>|L|≈1

第44頁，共90頁，2023年，2月20日，星期三|L|較小

★L(fēng)越小收斂速度越快。第45頁，共90頁，2023年，2月20日，星期三迭代公式：第46頁，共90頁，2023年，2月20日，星期三迭代公式比較第47頁，共90頁，2023年，2月20日，星期三迭代公式比較第48頁，共90頁，2023年，2月20日，星期三n（1）（2）（3）（4）01.51.51.51.51-0.8750.81651.286953771.3483997326.7322.99691.402540801.367376373-469.7

1.345458381.364957014

1.375170251.365264755

1.360094191.365225596

1.361946971.365223067

1.363887001.365229948

1.365916731.365230029

1.364878221.3652300110

1.36541006

15

1.36522368

20

1.36523024

23

1.36522998

25

1.36523001

第49頁，共90頁，2023年，2月20日，星期三2.2.4迭代法收斂的速度定義2設(shè)序列收斂于，令 若有實數(shù)和正常數(shù)C，使得 則稱該序列是p階收斂的；

其中C稱為漸進(jìn)誤差常數(shù)。

★第50頁，共90頁，2023年，2月20日，星期三迭代法收斂的階當(dāng)p=1時，稱為線性收斂；當(dāng)2>p>1時，稱為超線性收斂；當(dāng)p=2時，稱為平方收斂或二次收斂。第51頁，共90頁，2023年，2月20日，星期三定理3（迭代法收斂的階）

★第52頁，共90頁，2023年，2月20日，星期三證明：第53頁，共90頁，2023年，2月20日，星期三

第54頁，共90頁，2023年，2月20日，星期三

第55頁，共90頁，2023年，2月20日，星期三

解：從而知(1)是平方收斂的。第56頁，共90頁，2023年，2月20日，星期三將看作由下述方程確定的隱函數(shù)從而，上式兩邊對求導(dǎo)，得從而，再兩邊對求導(dǎo)，得上式兩邊對求導(dǎo)，得令，可得第57頁，共90頁，2023年，2月20日，星期三例迭代過程是否收斂？如發(fā)散，試構(gòu)造一收斂的迭代公式。

方程為x-4+2x=0.設(shè)f(x)=x-4+2x，則f(1)<0，f(2)>0，故方程f(x)=0在區(qū)間(1,2)內(nèi)有根.題中(x)=4-2x，當(dāng)x(1,2)時,'

(x)=-2xln2>2ln2>1

，由定理2不能用來迭代求根.把方程改寫為x=ln(4-x)/ln2，此時(x)=ln(4-x)/ln2,則1°當(dāng)x[1,2]時，(x)[1,ln3/ln2]

[1,2]2°x(1,2)，有

'(x)=

故可用迭代公式xn+1=ln(4-xn)/ln2來求解(1,2)區(qū)間內(nèi)的唯一根.第58頁，共90頁，2023年，2月20日，星期三２.３迭代收斂的加速

２.３.１松弛法

第59頁，共90頁，2023年，2月20日，星期三

２.３.１松弛法

第60頁，共90頁，2023年，2月20日，星期三２.３.２埃特金（Aitken)方法

第61頁，共90頁，2023年，2月20日，星期三２.３.２埃特金（Aitken)方法

第62頁，共90頁，2023年，2月20日，星期三

埃特金（Aitken)方法第63頁，共90頁，2023年，2月20日，星期三例：

第64頁，共90頁，2023年，2月20日，星期三k（a）(b)(c)(d)(e)01．51．51．51．51．51-0.8750.81651.286953771.348399731.373333326.7322.99691.402540801.367376371.365262013-469.71.345458381.36495701.3652300141.03×1081.375170251.3652647581.365916731.3652300291.364878221.36523001231.36522998251.36523001對選取的gi(x)，取初始近似值x0=1.5，迭代計算結(jié)果列在表。第65頁，共90頁，2023年，2月20日，星期三比較可得，與x8的誤差差不多。

簡單觀察迭代過程，(a)(b)不定，(c)(d)(e)都收斂，但收斂速度相差很大。例：對g4(x)產(chǎn)生的迭代序列進(jìn)行Aitken加速。解:利用計算公式得第66頁，共90頁，2023年，2月20日，星期三第67頁，共90頁，2023年，2月20日，星期三

第68頁，共90頁，2023年，2月20日，星期三2.4牛頓迭代法

2.4.1基本思想將在點展開為Taylor展式有近似方程

★第69頁，共90頁，2023年，2月20日，星期三2.4.2牛頓迭代法的幾何意義xyx*x0x2x1y=f(x)第70頁，共90頁，2023年，2月20日，星期三牛頓迭代法設(shè)方程在根附近取初始近似根由迭代公式求解方法這種求根算法稱為Newton法（切線法）此公式稱為Newton迭代公式.第71頁，共90頁，2023年，2月20日，星期三牛頓迭代法Newton法的迭代函數(shù)是從而

由此知若

是

的一個單根，則在附近Newton法是局部收斂的，并且收斂速度至少是平方收斂的.但如果

是

的m>1重根，則此時Newton法僅有線性收斂速度.第72頁，共90頁，2023年，2月20日，星期三2.4.3Newton法收斂的充分條件第73頁，共90頁，2023年，2月20日，星期三Newton迭代法收斂性證明：根的存在性根的唯一性第74頁，共90頁，2023年，2月20日，星期三第75頁，共90頁，2023年，2月20日，星期三２.４.４牛頓２階導(dǎo)數(shù)法第76頁，共90頁，2023年，2月20日，星期三牛頓２階導(dǎo)數(shù)法迭代公式第77頁，共90頁，2023年，2月20日，星期三由前例