§1方程求根與二分法第7章解非線性方程的迭代法一、引言非線性方程的分兩類：

則可用搜索法求有根區(qū)間.x

?1012f(x)的符號(hào)??++方程根的數(shù)值計(jì)算大致可分三個(gè)步驟進(jìn)行:

(1)判定根的存在性。

(2)確定根的分布范圍,即將每一個(gè)根用區(qū)間隔離開來。

(3)根的精確化,即根據(jù)根的初始近似值按某種方法逐步精確化,直至滿足預(yù)先要求的精度為止。設(shè)f(x)為定義在某區(qū)間上的連續(xù)函數(shù),方程(1.1)存在實(shí)根。雖然方程(1.1)的根的分布范圍一般比較復(fù)雜,但我們不難將函數(shù)f(x)的定義域分成若干個(gè)只含一個(gè)實(shí)根的區(qū)間。例如考慮方程

x2-2x-1=0

由圖7.1所示,該方程的一個(gè)負(fù)實(shí)根在-1和0之間,另一個(gè)正實(shí)根在2和3之間。圖7.1這樣,我們總可以假設(shè)方程(1.1)在(a,b)內(nèi)有且僅有一個(gè)單實(shí)根x*。由連續(xù)函數(shù)的介值定理知

f(a)·f(b)＜0

若數(shù)值b-a較小,那么我們可在(a,b)上任取一點(diǎn)x0作為方程的初始近似根。例如,方程

f(x)=x3-x-1=0

由于f(1)＜0,f(1.5)＞0,又f(x)在區(qū)間(1,1.5)上單調(diào)連續(xù),故可知在(1,1.5)內(nèi)有且僅有一個(gè)實(shí)根。于是可取某個(gè)端點(diǎn)或區(qū)間內(nèi)某一個(gè)點(diǎn)的值作為根的初始近似值。設(shè)函數(shù)f(x)在區(qū)間［a,b］上單調(diào)連續(xù),且

f(a)·f(b)＜0

則方程(1.1)在區(qū)間(a,b)內(nèi)有且僅有一個(gè)實(shí)根x。二、二分法二分法簡(jiǎn)述.且有

(1.3)對(duì)于確定的精度ε,從式(1.3)易求得需要二等分的次數(shù)k。二分法具有簡(jiǎn)單和易操作的優(yōu)點(diǎn)。其計(jì)算步驟如下,框圖如圖7.2所示。1.計(jì)算步驟①輸入有根區(qū)間的端點(diǎn)a,b及預(yù)先給定的精度ε;②(a+b)/2x;③若f(a)f(x)＜0,則x=b,轉(zhuǎn)向④;否則x=a,轉(zhuǎn)向④。④若b-a＜ε,則輸出方程滿足精度的根x,結(jié)束;否則轉(zhuǎn)向②。圖7.22.計(jì)算框圖(見下頁）例1求方程f(x)=x3-x-1=0在區(qū)間(1,1.5)內(nèi)的根。要求用四位小數(shù)計(jì)算,精確到小數(shù)點(diǎn)后兩位。解這里a=1,b=1.5，取區(qū)間(1,1.5)的中點(diǎn)由于f(1)＜0,f(1.25)＜0,則令

a1=1.25,b1=1.5得到新的有根區(qū)間(1.25,1.5)如此重復(fù)二分下去，二分法的計(jì)算結(jié)果如下表取x6=1.3242，誤差限|x6-x*|<0.5/(2^7)<0.005,故x6即為所求近似根，實(shí)際上根x*=1.324717…二分法優(yōu)點(diǎn)：計(jì)算簡(jiǎn)單，收斂性有保證；二分法缺點(diǎn)：收斂不夠快，特別是精度要求高時(shí)，工作量大，而且不能夠求復(fù)根及雙重根?！?迭代法一、不動(dòng)點(diǎn)迭代如果點(diǎn)列﹛Pk﹜趨向于點(diǎn)P*，則相應(yīng)的迭代值xk收斂到所求根x*.kxk012345671.51.357211.330861.325881.324941.324761.324731.32472雖然迭代法的基本思想很簡(jiǎn)單,但效果并不總是令人滿意的。對(duì)于上例,若按方程寫成另一種等價(jià)形式

x=x3-1建立迭代公式

xk+1=x3k-1,k=0,1,2,…仍取初始值x0=1.5,則迭代結(jié)果為

x1=2.375x2=12.3976這種不收斂的迭代過程稱作是發(fā)散的。如下圖：二、不動(dòng)點(diǎn)的存在性與迭代法的收斂性證明先證不動(dòng)點(diǎn)存在性。若三、局部收斂性與收斂階證明由連續(xù)函數(shù)的性質(zhì)，存在x*的某個(gè)鄰域R：|x-x*|≤δ，使對(duì)于任意x∈R成立|ψ＇(x)|≤L<1.此外，對(duì)于任意x∈R，總有ψ(x)∈R，這是因?yàn)?/p>

|ψ(x)-x*|=|ψ(x)-ψ(x*)|≤L|x-x*|≤|x-x*|≤δ.于是依據(jù)定理2可以斷定迭代過程xk+1=ψ(xk)對(duì)于任意初值x0∈R均收斂.證畢.kxk迭代法(1)迭代法(2)迭代法(3)迭代法(4)0123

?

x0

x1

x2

x3

?23987?21.521.5?21.751.734751.732631?21.751.7321431.732051?§3迭代收斂的加速方法一、埃特金加速收斂方法二、斯蒂芬森迭代法kxkykzk0123451.51.416291.355651.329851.324801.324722.375001.840921.491401.347101.3251812.39655.238882.317281.444351.32714說明:(2.2)不收斂,(3.3)可能收斂;(2.2)線性收斂,(3.3)平方收斂!kxkykzk0123.53.734443.733073.604143.733813.662023.73347§4牛頓法一、牛頓法及其收斂性牛頓法是非線性方程線性化的方法。其計(jì)算步驟為:①給出初始近似根x0及精度ε。②計(jì)算③若｜x1-x0｜＜ε,則轉(zhuǎn)向④;否則,轉(zhuǎn)向②。④輸出滿足精度的根x1,結(jié)束。牛頓法的計(jì)算框圖見圖7.4。

圖7.4牛頓法有明顯的幾何解釋，方程f(x)=0的根x*可解釋為曲線y=f(x)與x軸的交點(diǎn)的橫坐標(biāo).設(shè)xk是跟x*的某個(gè)近似值,過曲線y=f(x)上橫坐標(biāo)為xk的點(diǎn)Pk引切線,并將該切線與x軸的交點(diǎn)的橫坐標(biāo)xk+1作為x*的新的近似值.注意到切線方程為

y=f(xk)+f＇(xk)(x-xk).這樣求得的值xk+1必滿足（4.1）式，從而就是牛頓公式（4.2）的計(jì)算結(jié)果.由于這種幾何背景,牛頓法亦稱為切線法.oxyx*Xk+1Pky=f(x)Xk二、牛頓法應(yīng)用舉例kxk01230.50.571020.567160.56714kxk012341010.75000010.72383710.72380510.723805三、簡(jiǎn)化牛頓法與牛頓下山法kxkxkxk

f(xk)012341.51.347831.325201.324720.617.9發(fā)散0.6-1.3841.140625-0.6566431.361810.18661.326280.006671.324720.0000086四、重根情形kxk(1)(2)(3)0123x0x1x2x31.51.4583333331.4366071431.4254976191.51.4166666671.4142156861.4142135621.51.4117647061.4142114381.414213562§5弦截法kxk012340.50.60.565320.567090.56714解設(shè)取x0=0.5,x1=0.6作為開始值，用弦截法求得的結(jié)果見表7-10，