第一節(jié)-引言-二分法與迭代法課件

第二章方程求根

本章主要內(nèi)容：1、二分法2、簡單迭代法（重點）3、牛頓迭代法（重點）4、割線法本章難點：分析迭代法的收斂性第二章方程求根本章主要內(nèi)容：1、二分法2、簡單迭代法（1歷史背景

代數(shù)方程的求根問題是一個古老的數(shù)學(xué)問題。理論上，次代數(shù)方程在復(fù)數(shù)域內(nèi)一定有個根(考慮重數(shù))。早在16世紀就找到了三次、四次方程的求根公式，但直到19世紀才證明大于等于5次的一般代數(shù)方程式不能用代數(shù)公式求解，而對于超越方程就復(fù)雜的多，如果有解，其解可能是一個或幾個，也可能是無窮多個。一般也不存在根的解析表達式。因此需要研究數(shù)值方法求得滿足一定精度要求的根的近似解。

歷史背景代數(shù)方程的求根問題是一個古老的數(shù)學(xué)問題。理論2本章解決一元函數(shù)方程的求根問題。否則稱其為超越方程，如當(dāng)為多項式函數(shù)時，稱此方程為代數(shù)方程，如若函數(shù)可表示成(2.1)則稱是方程(2.1)的重根。本章解決一元函數(shù)方程的求根問題。否則稱其為超越方程，如當(dāng)3根的存在性連續(xù)函數(shù)介值定理則這樣的在內(nèi)唯一。abx*若函數(shù)在上連續(xù)，且則至少有一個數(shù)，使得，若還單調(diào)，定理：根的存在性連續(xù)函數(shù)介值定理則這樣的在內(nèi)唯一。4方程f(x)=0的有根區(qū)間的確定有根區(qū)間：方程在這樣的區(qū)間內(nèi)有且只有一個實根。1.描圖法將方程f(x)=0化為g(x)

=h(x)的形式，畫出g(x)和h(x)的簡圖，從兩條曲線的交點的橫坐標(biāo)的位置例2.1求方程3x–1–cosx=0的有根區(qū)間。解：用描圖法，將方程變形為令g(x)=3x-1,h(x)=cosx,做出兩個函數(shù)的簡圖確定有根區(qū)間。注：g(x)和h(x)的圖形比較容易作出。方程f(x)=0的有根區(qū)間的確定有根區(qū)間：方程在這5由圖可知，方程僅有一個實根，有根區(qū)間為由圖可知，方程僅有一個實根，有根區(qū)間為62.通過研究函數(shù)性態(tài)判斷有根區(qū)間例2.2求函數(shù)的有根區(qū)間。解：令,并對其求導(dǎo)數(shù)得單調(diào)減少的。所以函數(shù)在上是又根據(jù)連續(xù)函數(shù)介值定理，方程在內(nèi)有且僅有一個實根。所以是方程的有根區(qū)間。2.通過研究函數(shù)性態(tài)判斷有根區(qū)間例2.2求函數(shù)7第一節(jié)二分法若f

(x)在[a,b]上連續(xù)，且f(a)·f(b)<0，以此類推上至少有一實根。則f(x)在(a,b)原理：基本思想：逐步將區(qū)間分半，通過判別區(qū)間端點函數(shù)值的符號，進一步搜索有根區(qū)間，將有根區(qū)間縮小到充分小，從而求出滿足精度的根的近似。第一節(jié)二分法若f(x)在[a,b]上連續(xù)，且8二分法的實施步驟：（1）找出方程的有根區(qū)間。若每次二分時所取區(qū)間中點都不是根，則上述過程將無限進（3）判斷：若則

是方程的根,(a)若

,則根屬于，置：行下去。計算結(jié)束；否則：(b)若

,則根屬于，置：注：上述過程中常取做機器零，當(dāng)小于此數(shù)時認為是零?。?）計算f(x)在區(qū)間中點的值；如。二分法的實施步驟：（1）找出方程9誤差分析：什么時候停止計算？按上述過程反復(fù)進行,可得一系列有根區(qū)間套當(dāng)n→∞

時,區(qū)間長度趨近于零，因此區(qū)間必將最終收縮為由于每一區(qū)間都是前一區(qū)間的一半，因此區(qū)間的長度一點

,

顯然

就是所求的根。若取區(qū)間

的中點作為

的近似值，則，從而有下述誤差估計式誤差分析：什么時候停止計算？按上述過程反復(fù)進行,可得一系列10只要根據(jù)誤差估計式，對于預(yù)先給定的精度，即可由此確定最大對分次數(shù)便有：因此，就是滿足精度要求的近似解。只要根據(jù)誤差估計式，對于預(yù)先給定的精度，即可由此確定11二分法算法實現(xiàn)問題：給定區(qū)間[a,b]，求f(x)=0在該區(qū)間上的根x.輸入:

a和b;容許誤差TOL;最大對分次數(shù)Nmax.輸出:

近似根x.Step1

令k=1;Step2計算x=(a+b)/2和y=f(x)Step3若kNmax，做Steps4-6Step4若

|y|

<TOL

,停止;輸出

x.Step5

若y*f(a)<0

,置b=x;否則，置a=x;Step6置k=k+1;計算x=f((a+b)/2);轉(zhuǎn)Step3；Step7

輸出方程的近似解

x;停止.算法過程:

二分法算法實現(xiàn)問題：給定區(qū)間[a,b]，求f(x)=12解：例2.3用二分法求方程在區(qū)間上的根，誤差限為0.0005，問至少需對分多少次？由題意知，最大對分次數(shù)所以至少需對分次。對分9次后取有根區(qū)間的中點即為滿足精度要求的根。解：例2.3用二分法求方程在區(qū)間13①算法簡單直觀，收斂性有保證;

②

對f(x)

要求不高(只要連續(xù)即可).①無法求復(fù)根及重根；②收斂速度慢。注：用二分法求根，最好先給出f(x)

草圖以確定根的大概位置?；蛴盟阉鞒绦?，將[a,b]分為若干小區(qū)間，對每一個滿足f(ak)·f(bk)<0的區(qū)間調(diào)用二分法程序，可找出區(qū)間[a,b]內(nèi)的多個根，且不必要求f(a)·f(b)<0。優(yōu)點缺點①算法簡單直觀，收斂性有保證;①無法求復(fù)根14第二節(jié)

迭代法f(x)=0等價變換基本思想從一個初值x0

出發(fā)，計算一、簡單迭代法f(x)的根若數(shù)列收斂，即存在，使得稱為迭代函數(shù)稱為的不動點

若函數(shù)還是連續(xù)的，則即即方程f(x)=0的一個根。這樣就找到了函數(shù)的一個不動點，第二節(jié)迭代法f(x)=0等價變換基本思想從一個初值15xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=φ(x)y=φ(x)y=φ(x)y=φ(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1幾何意義xyy=xxyy=xxyy=xxyy=xx*16例2.4已知方程在上有一個根.解：下面選取5種迭代格式：1、即2、即3、即4、即5、即例2.4已知方程17取計算結(jié)果如下：法1法4法3法2法5取計算結(jié)果如下：法1法4法3法2法518如何判定迭代法的收斂性呢？如何構(gòu)造迭代函數(shù)才能使迭代法收斂？有如下充分條件：定理2.1（壓縮映射原理）若迭代函數(shù)滿足下列兩個條件：(2)0L<1使得對x[a,b]有：(1)當(dāng)x[a,b]時，則迭代過程對于任意初值均收斂于方程的根，且有如下誤差估計式：如何判定迭代法的收斂性呢？如何構(gòu)造迭代函數(shù)才19證明：先證當(dāng)k

時，

xk收斂到x*，這是因為再證定理中的誤差估計式，利用三角不等式所以注：該定理結(jié)論表明只要相鄰兩次迭代值的距離足夠小，即可保證近似值具有足夠的精度，所以可用來判斷是否滿足迭代精度！證明：先證當(dāng)k時，xk收斂到x*，這是因為20問題：給定初始近似值x0，求的解.輸入:初始近似值

x0;容許誤差TOL;最大迭代次數(shù)Nmax.輸出:近似解x或失敗信息.簡單迭代法的算法實現(xiàn)：Step1置i=1;Step2當(dāng)iNmax時，作Step3-5：Step3置;否則，置i=i+1;Step4若|xx0|<TOL，則輸出x，停止；Step6輸出迭代失敗信息，停止計算。Step5置x0=x，轉(zhuǎn)Step2;問題：給定初始近似值x0，求21二、局部收斂性定義：（局部收斂性）若存在的一個閉鄰域，對任意于，則稱該迭代法局部收斂。初值，由迭代過程產(chǎn)生的序列均收斂定理2.2關(guān)于局部收斂，有如下判定定理：設(shè)為的解，在的某鄰域連續(xù)，且則迭代過程局部收斂。二、局部收斂性定義：（局部收斂性）若存在的一個閉鄰域22三、迭代法的收斂階及常數(shù)，使的一種度量;定義：設(shè)序列收斂到，，若存在實數(shù)則稱序列是階收斂的，常數(shù)稱為漸近誤差常數(shù)。特別地，當(dāng)且