計(jì)算方法非線性方程的數(shù)值解法

計(jì)算方法非線性方程的數(shù)值解法第1頁，共63頁，2023年，2月20日，星期四第2章非線性方程的數(shù)值解法

2.1初始近似值的搜索

2.2迭代法

2.3牛頓迭代法（切線法）

2.4弦截法（割線法）第2頁，共63頁，2023年，2月20日，星期四2.1初始近似值的搜索2.1.1方程的根第3頁，共63頁，2023年，2月20日，星期四單根和重根第4頁，共63頁，2023年，2月20日，星期四第5頁，共63頁，2023年，2月20日，星期四第6頁，共63頁，2023年，2月20日，星期四有根區(qū)間第7頁，共63頁，2023年，2月20日，星期四

假設(shè)f(x)在區(qū)間[a,b]內(nèi)有一個(gè)實(shí)根x*,若b–a較小，則可在(a,b)上任取一點(diǎn)x0作為初始近似根。

一般情形，可用逐步搜索法。2.1.2逐步搜索法第8頁，共63頁，2023年，2月20日，星期四第9頁，共63頁，2023年，2月20日，星期四例對方程搜索有根區(qū)間。解由于f(x)是連續(xù)函數(shù)，f(0)=-1<0，f(2)>0，故方程至少有一正實(shí)根。設(shè)從x=0

出發(fā)，取h=0.5為步長，逐步右跨搜索，得x

00.51.01.5f(x)

―――+所以f(x)在區(qū)間（1,1.5）上單調(diào)連續(xù)，因而在(1,1.5)內(nèi)有且僅有一個(gè)實(shí)根，故可取[1,1.5]上任一點(diǎn)做初始近似根?？梢娫冢?，1.5）內(nèi)有根。又第10頁，共63頁，2023年，2月20日，星期四第11頁，共63頁，2023年，2月20日，星期四

2.1.3區(qū)間二分法

定理函數(shù)f(x)在[a,b]上單調(diào)連續(xù)，且f(a)f(b)<0，則方程f(x)=0在區(qū)間[a,b]上有且僅有一個(gè)實(shí)根x*。

二分法的基本思想將有根的區(qū)間二分為兩個(gè)小區(qū)間，然后判斷根在那個(gè)小區(qū)間，舍去無根的小區(qū)間，而把有根的小區(qū)間再一分為二，再判斷根屬于哪個(gè)更小的區(qū)間，如此反復(fù)，直到求出滿足精度要求的近似根。第12頁，共63頁，2023年，2月20日，星期四令

近似根xk的誤差估計(jì)中點(diǎn)這時(shí)有三種情況：

f(x0)=0,x0為所求的根.f(x0)和a0

同號，取x0=

a1

f(x0)和b0

同號，取x0=

b1

x*x*新的有根區(qū)間為(a1,b1)，長度是原來的一半。第13頁，共63頁，2023年，2月20日，星期四如此反復(fù)，有∈(ak,bk),k=0,1,2,…..

近似根xk的誤差估計(jì)第14頁，共63頁，2023年，2月20日，星期四第2次二分，取中點(diǎn)若f(a1)f(x1)<0，則x*∈(a1,x1)，令a2=a1,b2=x1；否則令a2=x1,b2=b1

。新的有根區(qū)間為(a2,b2)。第15頁，共63頁，2023年，2月20日，星期四由此得二分過程結(jié)束的原則：先給定精度要求ε(絕對誤差限)，

（2）當(dāng)|bk+1–ak+1|<ε時(shí)結(jié)束二分計(jì)算，取

x*≈xk

；

（1）事先由ε估計(jì)出二分的最小次數(shù)k

，取x*≈xk

第16頁，共63頁，2023年，2月20日，星期四第17頁，共63頁，2023年，2月20日，星期四第18頁，共63頁，2023年，2月20日，星期四第19頁，共63頁，2023年，2月20日，星期四第20頁，共63頁，2023年，2月20日，星期四第21頁，共63頁，2023年，2月20日，星期四第22頁，共63頁，2023年，2月20日，星期四第23頁，共63頁，2023年，2月20日，星期四2.2迭代法2.2.1迭代原理2.2.2迭代的收斂性2.2.3迭代的收斂速度2.2.4迭代的加速第24頁，共63頁，2023年，2月20日，星期四預(yù)備定理第25頁，共63頁，2023年，2月20日，星期四2.2.1迭代原理第26頁，共63頁，2023年，2月20日，星期四計(jì)算結(jié)果見下表第27頁，共63頁，2023年，2月20日，星期四

方程f(x)=0化為等價(jià)形式的方程x=φ(x)，構(gòu)造迭代公式xk+1=φ(xk),k=0,1,2,……取初始近似根x0

,進(jìn)行迭代計(jì)算x1=φ(x0),x2=φ(x1),……..則有x1,

x2,,…….,xk,

…….,得到迭代序列{xk}.如果這個(gè)序列有極限，則迭代公式是收斂的。這時(shí)

則，x*

為不動(dòng)點(diǎn)，等價(jià)地有f(x*)=0,x*

即為方程的根。連續(xù)函數(shù)φ(x)稱為迭代函數(shù)。實(shí)際計(jì)算到|xk–xk-1|<ε（ε是預(yù)定的精度），取x*≈xk

。

第28頁，共63頁，2023年，2月20日，星期四迭代公式收斂指迭代序列{xk

}收斂，迭代公式發(fā)散指迭代序列{xk}不收斂，即發(fā)散。迭代公式不一定總是收斂。例如求方程

f(x)=x3-x-1=0的一個(gè)根。對應(yīng)的迭代公式為取初值迭代序列{xk}發(fā)散.第29頁，共63頁，2023年，2月20日，星期四第30頁，共63頁，2023年，2月20日，星期四x1=φ(x0)x2=φ(x1)迭代法收斂與發(fā)散的圖示第31頁，共63頁，2023年，2月20日，星期四迭代法的收斂與發(fā)散收斂的情形發(fā)散的情形第32頁，共63頁，2023年，2月20日，星期四2.2.2迭代的收斂性迭代法的收斂條件及誤差估計(jì)式定理（充分性條件）

設(shè)函數(shù)φ(x)

在[a,b]上連續(xù)，且

(1)對x∈[a,b],有φ

(x)∈[a,b](2)存在0<L<1，使對任意x∈[a,b]有

|φ

′(x)|≤L<1則方程x=φ(x)在[a,b]上的根x*存在且唯一；對初值

x0∈[a,b]

,迭代過程xk+1=

φ

(xk)均收斂于方程的根x*。定理中的(1)對x∈[a,b],有φ(x)∈[a,b]，稱為適定性（映內(nèi)性）。第33頁，共63頁，2023年，2月20日，星期四證明先證根的存在性。作連續(xù)函數(shù)ψ(x)=x-φ(x),由條件（1）x∈[a,b],φ

(x)∈[a,b]，即a≤φ(x)、x≤b,于是

ψ(a)=a-φ

(a)≤0

ψ(b)=b-φ(b)≥0

由于ψ(x)是連續(xù)函數(shù)，故必存在

x*∈[a,b]

使ψ(x*)=0.即ψ(x*)=x*-φ(x*)=0.于是

x*=φ

(x*)即x*為方程

x=φ

(x)的根。其次，證根的唯一性。

設(shè)y*也是方程的根，則x*=φ(x*),y*=φ(y*),x*-y*=φ(x*)–φ(y*)=φ′(ξ)(x*-y*)x*-y*–φ′(ξ)(x*-y*)=0，（x*-y*）[1-

φ′(ξ)]=0由條件（2）|φ′(x)|≤L<1，故有x*-y*=0，即x*=y*所以方程在[a,b]的根唯一。

第34頁，共63頁，2023年，2月20日，星期四再證迭代的收斂性。由xk=φ(xk-1),x*=φ(x*),有|xk-x*|=|φ′(ξ)(xk-1-x*)|≤L|xk-1-x*|≤L2|xk-2-x*|≤L3|xk-3-x*|≤……≤Lk|x0-x*|→0（k→∞）

所以，對[a,b]上任取的x0,迭代公式xk+1=φ(xk)都收斂于x*。

L越小收斂得越快。定理是充分性條件xk-x*=φ(xk-1)–φ(x*)=φ′(ξ)(xk-1-x*)第35頁，共63頁，2023年，2月20日，星期四推論：在定理的條件下，有誤差估計(jì)式驗(yàn)后誤差估計(jì)式驗(yàn)前誤差估計(jì)式證明：|xk-x*|≤L|xk-1-x*|=L|xk-1-xk+xk-x*|≤L（|xk-x*|+|xk-1-xk|）（1-L)|xk-x*|≤L|xk-1-xk|迭代法的終點(diǎn)判斷：只要相鄰兩次迭代值的偏差充分小，就能保證迭代值足夠準(zhǔn)確，因而用|xk-xk-1|控制迭代過程的結(jié)束。第36頁，共63頁，2023年，2月20日，星期四定理設(shè)在區(qū)間[a,b]上方程x=φ(x)有根x*,且對一切x∈[a,b]都有|

φ′(x)|≥1，則對于該區(qū)間上任意x0(≠x*),迭代公式xk+1=φ(xk)一定發(fā)散。證明不可能收斂于0。第37頁，共63頁，2023年，2月20日，星期四第38頁，共63頁，2023年，2月20日，星期四第39頁，共63頁，2023年，2月20日，星期四計(jì)算結(jié)果見下表取方程的根2.0946。第40頁，共63頁，2023年，2月20日，星期四第41頁，共63頁，2023年，2月20日，星期四由于，故取

第42頁，共63頁，2023年，2月20日，星期四迭代法的局部收斂性第43頁，共63頁，2023年，2月20日，星期四由于在實(shí)際應(yīng)用中根

x*

事先不知道，故條件

|φ′(x*)|<1無法驗(yàn)證。但已知根的初值x0在根

x*鄰域，又根據(jù)φ′(x)的連續(xù)性，則可采用

|φ′(x0)|<1來代替|φ′(x*)|<1，判斷迭代的收斂性。

第44頁，共63頁，2023年，2月20日，星期四例求方程

x=e

–x在x=0.5附近的一個(gè)根，按5位小數(shù)計(jì)算，結(jié)果的精度要求為ε=10–3.解迭代公式xk+1=e

–xk，取φ

(x)=e–x,迭代公式xk+1=e

–xk收斂。第45頁，共63頁，2023年，2月20日，星期四迭代結(jié)果:

012345

0.50.606530.545240.579700.560070.57117

0.10653

－0.061290.03446

－0.019630.01110

678910

0.564860.568440.566410.567560.56691－0.006310.00358

－0.002030.00115

－0.00065kxkxk–xk-1xk–xk-1k

xk|x10-x9|=0.00065<ε，