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

第二章方程求根

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

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

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

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

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

是方程的根,(a)若

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

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

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

,

顯然

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

的中點(diǎn)作為

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

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

近似根x.Step1

令k=1;Step2計(jì)算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;計(jì)算x=f((a+b)/2);轉(zhuǎn)Step3；Step7

輸出方程的近似解

x;停止.算法過程:

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

②

對(duì)f(x)

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

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

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

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

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

時(shí)，

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

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