計算方法ch2資料課件

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

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

定理

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

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

x*l

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

xk

bk

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

要求用二分法，取四位小數計算，精確到10-2。

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

要求用二分法，取四位小數計算，精確到10-2。

解得k=6滿足要求，二分7次計算到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)內的根。(2)求近似根如此繼續(xù)，計算結果見列表：kakbkxkf(xk)的符號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例：利用計算器，求方程在[2,3]上的近似解,（精確到0.1）。解得k=4滿足要求，二分5次計算到x4即可。(2)kakbkxkf(xk)的符號0232.5＋122.52.25－22.252.52.375－32.3752.52.4375＋42.3752.43742.40625－得x4=2.40625,所以根x*≈2.4二分法的基本思想和計算過程近似根的誤差估計二分法的計算流程二分法舉例2.2二分法二分法的計算流程#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();}求方程

取四位小數計算，精確到10-2。

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

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

，則x*

即為方程的根。實際計算到|xk–xk-1|<ε（ε是預定的精度），取x*≈xk

。

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

得到迭代序列{xk

},構造迭代公式

xk+1=g(xk

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

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

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

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

{xk

}收斂（發(fā)散）。求方程f(x)=x–10x+2=0在（0,1）的一個根，取4位有效數字計算。問題：迭代公式是否一定收斂？因f(0)=1>0,f(1)=-7<0,所以方程在（0，1）中有根。方程改寫為兩種等價形式：看下例：解對應的迭代公式分別為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.迭代法的幾何意義問題：迭代函數g(x)滿足什么條件時，迭代序列才收斂?x1=g(x0)x2=g(x1)2.3.1迭代法的基本思想及幾何意義2.3.2迭代法的收斂條件及誤差估計式2.3迭代法的一般知識2.2.3局部收斂性與迭代法收斂的階2.3.2迭代法的收斂條件及誤差估計式定理2.1

設方程x=g(x)在[a,b]上有一階導數，如果(1)當x∈[a,b]時g(x)∈[a,b];(2)存在正數q<1，使對任意x∈[a,b]

都有

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

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

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

使f(x*)=0.于是x*為方程x=g(x)的根。先證根的存在性。其次，證根的惟一性。設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)當x∈[a,b]時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→∞）所以，對[a,b]上任取的x0,迭代公式xk+1=g(xk

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

設方程x=g(x)在[a,b]上有一階導數，如果(1)當x∈[a,b]時g(x)∈[a,b];(2)存在正數q<1，使對任意x∈[a,b]

都有

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

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

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

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

0.080080.012270.001870.000270.00005

kxk

xk-xk-1

因為|x5-x4|=0.00005<10-4所以x*≈x5=2.09454……結果列表：(2)迭代函數根據定理2.2,迭代函數對應的迭代公式是發(fā)散的。例求方程x=e–x在x=0.5附近的一個根，按5位小數計算，結果的精度要求為ε=10–3.解方程等價于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)內,g(x)的一階導數連續(xù)，且有所以用迭代公式xk+1=e–xk

進行計算是收斂的。根據定理2.1迭代結果:

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]的斂散性。利用迭代形式計算在[1.5,3]的實根。迭代三次，結果保留兩位有效數字，選取初始近似根為3。迭代次數 近似根0 31 1.52 2.06253 1.983398438結果保留兩位有效數字所以近似根為2.02.3.1迭代法的基本思想及幾何意義2.3.2迭代法的收斂條件及誤差估計式2.3迭代法的一般知識2.2.3局部收斂性與迭代法收斂的階定義2-1的某個領域使得迭代公式對于任意初值定理2-2且2.2.3局部收斂性與迭代法收斂的階若存在設定義2-2

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

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

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

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

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

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

證明：

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

)

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

定理2-2且設定理2-3.

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

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

2.4.3牛頓迭代法的計算步驟(1)給出x0,ε；(2)計算(3)若則轉(4)；否則，轉(2);(4)輸出x1,結束。例用牛頓迭代法求方程xex-1=0在x=0.5附近的根（取5位小數計算），精度要求為ε=10–3.解相應的牛頓迭代公式為取x0=0.5，經計算可得計算表格參考P21中表2-3,則x2-3=0,求等價于求方程令例用牛頓迭代法計算解的正實根。因為f′(x)=2x，由牛頓迭代公式得取初值x0=1.5，迭代5次可得≈1.732050808問題如何用牛頓法計算任意正數的算術平方根？是否還能用牛頓法計算一個正數的立方根？是否還能用牛頓法計算一個正數的n次方根？2.4.1牛頓法的基本思想2.4.2牛頓法的收斂性2.4牛頓迭代法（切線法）2.4.3牛頓法的計算步驟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次才達到精度要求2.用Newton下山法,結果如下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迭代法的一般知識2.4牛頓迭代法（切線法）2.5弦截法（割線法）2.6埃特金（Aitken）迭代法引言2.5弦截法（割線法）研究目的：在牛頓法基礎上，構造既有較高的收斂速度，又不須導數的迭代公式。

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

幾何意義

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

kxk

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

用差商牛頓迭代法與割線法都是線性化方法。牛頓法、一般迭代法在計算時只需要前一步的值，稱為單點迭代法。牛頓法需要計算導數，收斂速度快割線法在計算時需要前兩步的值，稱為多點迭代法。計算時迭代公式

xk+1=g(xk

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

012345

2.375001.840921.491401.347101.32518

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