分章測(cè)試筆試。課件或課后題。上機(jī)。分組。講解。計(jì)入期末成績(jī)。30%—50%課后習(xí)題1、2、5、7、8、9編程二分法、一般的迭代法第2章一元非線性方程的解法2.1初始近似根的確定2.2二分法2.3迭代法的一般知識(shí)2.4牛頓迭代法（切線法）2.5弦截法（割線法）2.6埃特金（Aitken）迭代法引言本章討論：求一元非線性方程f(x)=0的根的近似值。引言例如e-x-x=0,x8-x3+5x-3=0,x-sinx=0,等等求根的大致步驟：(1)判定根的存在性。(2)確定根的初始近似值(初始近似根)。(3)根的精確化。如果f(x*)=f′(x*)=f″(x*)=……=f(m-1)(x*)=0,但f(m)(x*)≠0,其中m是正整數(shù)，則稱x*為方程f(x)=0的m重根-------函數(shù)f(x)的m重零點(diǎn)。如果f(x*)=0,則x*是方程f(x)=0的根,也稱它是函數(shù)f(x)的零點(diǎn)。方程的1重根稱為單根，這時(shí)f(x*)=0而f′(x*)≠0。第2章一元非線性方程的解法2.1初始近似根的確定2.2二分法2.3迭代法的一般知識(shí)2.4牛頓迭代法（切線法）2.5弦截法（割線法）2.6埃特金（Aitken）迭代法引言從有限區(qū)間的左端點(diǎn)出發(fā)，按預(yù)定的步長h一步一步地向右跨，每跨一步進(jìn)行一次根的“搜索”，即檢查所在節(jié)點(diǎn)上的函數(shù)值的符號(hào)，一旦發(fā)現(xiàn)其與左端的函數(shù)值異號(hào)，則可確定一個(gè)縮小了的有限區(qū)間，其寬度等于預(yù)定的步長h。然后，再對(duì)新的有限區(qū)間，取新的更小的預(yù)定步長，繼續(xù)“搜索”，直到有限區(qū)間的寬度足夠小。稱這種方法為逐步搜索法。逐步搜索法(1)x0←a;(2)若f(x0)f(x0+h)≤0則結(jié)束；否則做下步。

(3)x0←x0+h，轉(zhuǎn)(2)（其中h為預(yù)選的步長）求初始近似根的逐步掃描法：（設(shè)(a,b)內(nèi)有根）

定理

如果函數(shù)f(x)在區(qū)間[a,b]上連續(xù)，嚴(yán)格單調(diào)，且f(a)f(b)<0，則在(a,b)內(nèi)方程有且僅有一個(gè)實(shí)根。2.1初始近似根的確定第2章一元非線性方程的解法2.1初始近似根的確定2.2二分法2.3迭代法的一般知識(shí)2.4牛頓迭代法（切線法）2.5弦截法（割線法）2.6埃特金（Aitken）迭代法引言二分法的基本思想和計(jì)算過程近似根的誤差估計(jì)二分法的計(jì)算流程二分法舉例2.2二分法二分法的基本思想將含方程根的區(qū)間平分為兩個(gè)小區(qū)間，然后判斷根在哪個(gè)小區(qū)間，舍去無根的區(qū)間，而把有根的區(qū)間再一分為二，再判斷根屬于哪個(gè)更小的區(qū)間，如此周而復(fù)始，直到求出滿足精度要求的近似根。條件：函數(shù)f(x)在[a,b]上連續(xù)，嚴(yán)格單調(diào)，且f(a)f(b)<0，這時(shí)方程在區(qū)間內(nèi)有且僅有一個(gè)實(shí)根x*。二分法的基本思想和計(jì)算過程具體計(jì)算過程第1次二分，取中點(diǎn)若f(a)f(x0)<0，則x*∈(a,x0)，令a1=a,b1=x0；令a1=x0,b1=b。新的有根區(qū)間為(a1,b1)，長度是原來的一半。否則x*∈(x0,b)，x*x*第2次二分，取中點(diǎn)若f(a1)f(x1)<0，則x*∈(a1,x1)，令a2=a1,b2=x1；否則令a2=x1,b2=b1

。新的有根區(qū)間為(a2,b2)。如此反復(fù)，有∈(ak,bk),k=0,1,2,…..二分法的基本思想和計(jì)算過程近似根的誤差估計(jì)二分法的計(jì)算流程二分法舉例2.2二分法近似根xk的誤差估計(jì)

x*l

m|—————|—————|ak

xk

bk

二分法的基本思想和計(jì)算過程近似根的誤差估計(jì)二分法的計(jì)算流程二分法舉例2.2二分法例求方程

要求用二分法，取四位小數(shù)計(jì)算，精確到10-2。

解a=1,b=1.5,f(1)=-1<0,f(1.5)>0.在區(qū)間(1,1.5)內(nèi)的根。所以f(x)在(1,1.5)內(nèi)有且僅有一個(gè)實(shí)根。(1)證明根的存在性例求方程

要求用二分法，取四位小數(shù)計(jì)算，精確到10-2。

解得k=6滿足要求，二分7次計(jì)算到x6即可。x0==1.25,f(1.25)<0,f(1)f(1.25)>0,得有根區(qū)間[1.25,1.5];x1=f(1.375)>0,f(1.25)f(1.375)<0,得有根區(qū)間[1.25,1.375];在區(qū)間(1,1.5)內(nèi)的根。(2)求近似根如此繼續(xù)，計(jì)算結(jié)果見列表：kakbkxkf(xk)的符號(hào)011.51.25－11.251.51.375＋21.251.3751.3125－31.31251.3751.3438＋41.31251.34381.3282＋51.31251.32821.3204－61.32041.32821.3243－得x6=1.3243,所以根x*≈1.32例：利用計(jì)算器，求方程在[2,3]上的近似解,（精確到0.1）。解得k=4滿足要求，二分5次計(jì)算到x4即可。(2)kakbkxkf(xk)的符號(hào)0232.5＋122.52.25－22.252.52.375－32.3752.52.4375＋42.3752.43742.40625－得x4=2.40625,所以根x*≈2.4二分法的基本思想和計(jì)算過程近似根的誤差估計(jì)二分法的計(jì)算流程二分法舉例2.2二分法二分法的計(jì)算流程#include<stdio.h>#include<math.h>#definef(x)((x*x+10)*x-20)#defineeps0.005

二分法的C程序main(){floata,b,y,x;intk=0;

clrscr();

printf("\nepsilon=%f\n",eps);

printf("\na=");scanf("%f",&a);

printf("\nb=");scanf("%f",&b);do{y=f(a);x=(a+b)/2;k++;if(y*f(x)<0){b=x;}elsea=x;}

while((b-a)>=eps);printf("\nTherootisx=%f,k=%d\n",x,k);getch();}求方程

取四位小數(shù)計(jì)算，精確到10-2。

在區(qū)間(a,b)內(nèi)的根。要求用二分法，第2章一元非線性方程的解法2.1初始近似根的確定2.2二分法2.3迭代法的一般知識(shí)2.4牛頓迭代法（切線法）2.5弦截法（割線法）2.6埃特金（Aitken）迭代法引言2.3.1迭代法的基本思想及幾何意義2.3.2迭代法的收斂條件及誤差估計(jì)式2.3迭代法的一般知識(shí)2.2.3局部收斂性與迭代法收斂的階1.迭代法的基本思想2.3.1迭代法的基本思想及幾何意義2.迭代法的幾何意義方程f(x)=0化為等價(jià)形式的方程x=g(x)

，若當(dāng)g(x)(稱為迭代函數(shù)）連續(xù)，

，則x*

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

。

1、迭代法的基本思想：取初始近似根x0,迭代計(jì)算x1=g(x0),x2=g(x1),……..

得到迭代序列{xk

},構(gòu)造迭代公式

xk+1=g(xk

),k=0,1,2,……例

f(x)=xex-1=0,可化為等價(jià)形式x=e–x迭代公式xk+1=e–xk迭代法也稱逐次逼近法。例

f(x)=x-2x=0,可化為等價(jià)形式x=2x迭代公式x

k+1=2xk迭代公式收斂（發(fā)散）指迭代序列

{xk

}收斂（發(fā)散）。求方程f(x)=x–10x+2=0在（0,1）的一個(gè)根，取4位有效數(shù)字計(jì)算。問題：迭代公式是否一定收斂？因f(0)=1>0,f(1)=-7<0,所以方程在（0，1）中有根。方程改寫為兩種等價(jià)形式：看下例：解對(duì)應(yīng)的迭代公式分別為10x=x+2x=lg(x+2)用迭代公式（1）x1=lg3=0.4771,x2=lg(x1+2)=0.3939,….,x6=0.3758,x7=lg(x6+2)=0.3758,…用迭代公式（2）x1=10-2=8,x2=108-2≈108,x3=10108-2≈10108，……x6、x7重合，所以迭代公式（1）是收斂的，x*≈0.3758。迭代公式（2）發(fā)散。取x0=1,算得,x0=1,算得2.迭代法的幾何意義問題：迭代函數(shù)g(x)滿足什么條件時(shí)，迭代序列才收斂?x1=g(x0)x2=g(x1)2.3.1迭代法的基本思想及幾何意義2.3.2迭代法的收斂條件及誤差估計(jì)式2.3迭代法的一般知識(shí)2.2.3局部收斂性與迭代法收斂的階2.3.2迭代法的收斂條件及誤差估計(jì)式定理2.1

設(shè)方程x=g(x)在[a,b]上有一階導(dǎo)數(shù)，如果(1)當(dāng)x∈[a,b]時(shí)g(x)∈[a,b];(2)存在正數(shù)q<1，使對(duì)任意x∈[a,b]

都有

|g′(x)|≤q<1則方程x=g(x)在[a,b]上有惟一的根x*

；且對(duì)于[a,b]上任意初始近似根x0,迭代公式xk+1=g(xk)均收斂于方程的根x*;還有誤差估計(jì)式證明記f(x)=x-g(x),

由條件（1）有a≤g(a)、g(b)≤b,于是f(a)≤0,f(b)≥0，由于f(x)是連續(xù)函數(shù)，故必存在x*∈[a,b]

使f(x*)=0.于是x*為方程x=g(x)的根。先證根的存在性。其次，證根的惟一性。設(shè)y*也是方程的根，則x*=g(x*),y*=g(y*),|x*-y*|=|g(x*)–g(y*)|=|g′(ξ)(x*-y*)|≤q|x*-y*|由已知條件|g′(x)|≤q<1故必有x*=y*,所以方程在[a,b]的根是惟一的。微分中值定理,ξ在x*,y*之間(1)當(dāng)x∈[a,b]時(shí)g(x)∈[a,b];再證迭代公式收斂。由x0∈[a,b]

知xk∈[a,b]，k=0,1,2,……|xk+1-x*|=|g(xk)–g(x*)|=|g′(ξ)(xk-x*)|≤q|xk-x*|≤q2|xk-1-x*||xk-x*|≤q|xk-1-x*|≤q3|xk-2-x*|≤……≤qk+1|x0-x*|→0（k→∞）所以，對(duì)[a,b]上任取的x0,迭代公式xk+1=g(xk

)都收斂于x*。0<q<1,qk+1→0誤差公式的證明從略?？梢詤⒖凑n本P16頁。|xk-1-x*|≤q|xk-2-x*|(1)當(dāng)x∈[a,b]時(shí)g(x)∈[a,b];2.3.2迭代法的收斂條件及誤差估計(jì)式定理2.1

設(shè)方程x=g(x)在[a,b]上有一階導(dǎo)數(shù)，如果(1)當(dāng)x∈[a,b]時(shí)g(x)∈[a,b];(2)存在正數(shù)q<1，使對(duì)任意x∈[a,b]

都有

|g′(x)|≤q<1則方程x=g(x)在[a,b]上有惟一的根x*

；且對(duì)于[a,b]上任意初始近似根x0,迭代公式xk+1=g(xk)均收斂于方程的根x*;還有誤差估計(jì)式aby=x附加定理設(shè)在區(qū)間[a,b]上方程x=g(x)有根x*,且對(duì)一切x∈[a,b]都有|g′(x)|≥1，則對(duì)于該區(qū)間上任意x0(≠x*),迭代公式xk+1=g(xk

)一定發(fā)散。證明不可能收斂于0。迭代法的計(jì)算步驟（1）確定方程f(x)=0的一個(gè)等價(jià)形式x=g(x),要求在某個(gè)含根區(qū)間[a,b]內(nèi)滿足|g′(x)|≤q<1。(2)構(gòu)造迭代公式xk+1=g(xk)，選取初始近似根x0,進(jìn)行迭代計(jì)算。(3)當(dāng)|xk+1–xk

|<ε（ε是預(yù)定的精度）時(shí)停止計(jì)算，取x*≈xk+1。例方程f(x)=x3-2x-5=0在(1.5,2.5)內(nèi)有一實(shí)根，分別取作為迭代函數(shù)，試判斷對(duì)應(yīng)的迭代公式是否收斂，并用一個(gè)收斂的迭代公式求方程的根，精度要求為ε=10-4。解(1)單調(diào)，且所以迭代公式收斂。取x0=2計(jì)算,01234522.080082.092352.09422.094492.09454

0.080080.012270.001870.000270.00005

kxk

xk-xk-1

因?yàn)閨x5-x4|=0.00005<10-4所以x*≈x5=2.09454……結(jié)果列表：(2)迭代函數(shù)根據(jù)定理2.2,迭代函數(shù)對(duì)應(yīng)的迭代公式是發(fā)散的。例求方程x=e–x在x=0.5附近的一個(gè)根，按5位小數(shù)計(jì)算，結(jié)果的精度要求為ε=10–3.解方程等價(jià)于f(x)=x–e–x=0.由于f(0.5)<0,f(0.6)>0,故x*∈(0.5,0.6),令g(x)=e–x,在(0.5,0.6)內(nèi),g(x)的一階導(dǎo)數(shù)連續(xù)，且有所以用迭代公式xk+1=e–xk

進(jìn)行計(jì)算是收斂的。根據(jù)定理2.1迭代結(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<ε，故x*≈x10≈0.567xk+1=e–xkx0=0.5,x2=e–x1=0.54524,…….x1=e–x0=0.60653,已知方程：解：所以該迭代格式發(fā)散。判定在[1.5,3]的斂散性。利用迭代形式計(jì)算在[1.5,3]的實(shí)根。迭代三次，結(jié)果保留兩位有效數(shù)字，選取初始近似根為3。迭代次數(shù) 近似根0 31 1.52 2.06253 1.983398438結(jié)果保留兩位有效數(shù)字所以近似根為2.02.3.1迭代法的基本思想及幾何意義2.3.2迭代法的收斂條件及誤差估計(jì)式2.3迭代法的一般知識(shí)2.2.3局部收斂性與迭代法收斂的階定義2-1的某個(gè)領(lǐng)域使得迭代公式對(duì)于任意初值定理2-2且2.2.3局部收斂性與迭代法收斂的階若存在設(shè)定義2-2

定義2-2：什么是p階收斂？線性收斂p=1(0<c<1)超線性收斂2>p>1平方收斂p＝2設(shè)迭代序列{xk}收斂于方程f(x)=0的根x*，記作

ek=xk-x*(k=0,1,2,…)為迭代誤差。若存在常數(shù)p≥1,c>0,使得則稱迭代序列{xn}是p階收斂的。尤其：P的大小反映了迭代法的收斂速度。P越大，收斂速度也就越快。定義2-2線性收斂p=1(0<c<1)平方收斂定理2-3.

例2-7例2-7證明：經(jīng)計(jì)算知：根據(jù)定理2-3可知，迭代公式平方收斂，得證。第2章一元非線性方程的解法2.1初始近似根的確定2.2二分法2.3迭代法的一般知識(shí)2.4牛頓迭代法（切線法）2.5弦截法（割線法）2.6埃特金（Aitken）迭代法引言2.4.1牛頓法的基本思想2.4.2牛頓法的收斂性2.4牛頓迭代法（切線法）2.4.3牛頓法的計(jì)算步驟2.4.4牛頓下山法把非線性方程線性化，用線性方程的解逐步逼近非線性方程的解。2.4.1牛頓迭代法的基本思想過曲線上的點(diǎn)pk(xk,f(xk))作切線，取切線與軸的交點(diǎn)為xk+1

。用這個(gè)迭代公式求根的方法也稱牛頓迭代法、切線法。Newton迭代公式若f(xk

)≠0，則得2.4.2牛頓迭代法的收斂性:定理2-4

設(shè)x*是方程f(x)=0的單根，且f(x)在x*的某鄰域有二階連續(xù)導(dǎo)數(shù)，則牛頓法在x*附近局部收斂，且至少二階收斂，有

證明：

牛頓迭代法的迭代函數(shù)由迭代公式xk+1=g(xk

)

x*是方程f(x)=0的單根則所以局部二階或一階收斂由定理2-2可知，牛頓迭代法在根x*附近局部收斂。又由定理2-3可知，迭代公式至少具有二階收斂速度。且有證畢。

定理2-2且設(shè)定理2-3.

定理2-5如果在有根區(qū)間[a,b]上f(a)f(b)<0,f′(x)≠0，f″(x)連續(xù)且不變號(hào)，在[a,b]上取初始近似根

x0,使得則牛頓迭代法產(chǎn)生的迭代序列單調(diào)收斂于方程f(x)=0在該區(qū)間上的唯一解。

2.4.3牛頓迭代法的計(jì)算步驟(1)給出x0,ε；(2)計(jì)算(3)若則轉(zhuǎn)(4)；否則，轉(zhuǎn)(2);(4)輸出x1,結(jié)束。例用牛頓迭代法求方程xex-1=0在x=0.5附近的根（取5位小數(shù)計(jì)算），精度要求為ε=10–3.解相應(yīng)的牛頓迭代公式為取x0=0.5，經(jīng)計(jì)算可得計(jì)算表格參考P21中表2-3,則x2-3=0,求等價(jià)于求方程令例用牛頓迭代法計(jì)算解的正實(shí)根。因?yàn)閒′(x)=2x，由牛頓迭代公式得取初值x0=1.5，迭代5次可得≈1.732050808問題如何用牛頓法計(jì)算任意正數(shù)的算術(shù)平方根？是否還能用牛頓法計(jì)算一個(gè)正數(shù)的立方根？是否還能用牛頓法計(jì)算一個(gè)正數(shù)的n次方根？2.4.1牛頓法的基本思想2.4.2牛頓法的收斂性2.4牛頓迭代法（切線法）2.4.3牛頓法的計(jì)算步驟2.4.4牛頓下山法2.4.4牛頓下山法這種方法稱為Newton下山法，例7.解:1.先用Newton迭代法x4=9.70724x5=6.54091x6=4.46497x7=3.13384x8=2.32607x9=1.90230x10=1.75248x11=1.73240x12=1.73205x13=1.73205迭代13次才達(dá)到精度要求2.用Newton下山法,結(jié)果如下k=0x0=-0.99fx0=0.666567k=1x1=32.505829f(x)=11416.4w=0.5x1=15.757915f(x)=1288.5w=0.25x1=7.383958f(x)=126.8w=0.125x1=3.196979f(x)=7.69w=0.0625x1=1.103489f(x)=-0.655k=2x2=4.115071f(x)=19.1w=0.5x2=2.60928f(x)=3.31w=0.25x2=1.85638f(x)=0.27k=3x3=1.74352f(x)=0.023k=4x4=1.73216f(x)=0.00024k=5x5=1.73205f(x)=0.00000k=6x6=1.73205f(x)=0.000000第2章一元非線性方程的解法2.1初始近似根的確定2.2二分法2.3迭代法的一般知識(shí)2.4牛頓迭代法（切線法）2.5弦截法（割線法）2.6埃特金（Aitken）迭代法引言2.5弦截法（割線法）研究目的：在牛頓法基礎(chǔ)上，構(gòu)造既有較高的收斂速度，又不須導(dǎo)數(shù)的迭代公式。

思想：用差商弦截迭代公式

幾何意義

例用弦截迭代法求上一節(jié)的方程x=e-x在x=0.5附近的根。解:弦截迭代公式為方程化為x-e–x=0,令

kxk

01230.50.60.567540.56715弦截法的計(jì)算框圖出一般迭代法、牛頓迭代法與割線法比較：

用差商牛頓迭代法與割線法都是線性化方法。牛頓法、一般迭代法在計(jì)算時(shí)只需要前一步的值，稱為單點(diǎn)迭代法。牛頓法需要計(jì)算導(dǎo)數(shù)，收斂速度快割線法在計(jì)算時(shí)需要前兩步的值，稱為多點(diǎn)迭代法。計(jì)算時(shí)迭代公式

xk+1=g(xk

),k=0,1,2,……每步只需計(jì)算一次函數(shù)值。可以證明，割線法具有超線性收斂速度，收斂的階為1.618.2.6埃特金(Aitken)迭代法研究目的：有時(shí)迭代過程收斂緩慢，如何加速？還有時(shí)普通迭代法不收斂，如何改變斂散性？埃特金迭代法的構(gòu)造條件：埃特金迭代公式用埃特金迭代法求x3-x-1=0在(1,1.5)內(nèi)的根。例解將方程改寫成x=x3-1，建立迭代公式埃特金迭代公式為

012345

2.375001.840921.491401.347101.32518

12.39655.238882.317281.444351.327141.51.416291.355651.328951.324801.32472判定斂散性幾何意義:設(shè)初值由迭代法:由三角形相似,得:過兩點(diǎn)作直線,說明:該表達(dá)式正是埃特金加速收斂的公式,比更接近于從圖中可以看出(1)這里的并不是簡(jiǎn)單收斂列中的(2)對(duì)某些不收斂的情況,用埃特金方法“加速”也有可能收斂.的交點(diǎn)為與第2章一元非線性方程的解法2.1初始近似根的確定2.2二分法2.3迭代法的一般知識(shí)2.4牛頓迭代法（切線法）2.5弦截法（割線法）2.6埃特金（Aitken）迭代法引言二分法一般迭代法牛頓迭代法牛