計(jì)算方法-第2章-一元線性方程的解法資料課件

第2章一元非線性方程的解法§1二分法§2迭代法§3切線法(牛頓法)§4弦截法§5加速迭代法

例在相距100m的兩座建筑物(高度相等的點(diǎn))之間懸掛一根電纜，僅允許電纜在中間最多下垂1m，試計(jì)算所需電纜的長(zhǎng)度(如圖所示)。由于空中電纜的曲線是懸鏈線,建立如圖所示的坐標(biāo)系后,懸鏈線方程為記筆記由題設(shè)知曲線的最底點(diǎn)(0,y(0))與最高點(diǎn)(50,y(50))之間的高度差為1m,所以應(yīng)有y(50)=y(0)+1,即要計(jì)算電纜的長(zhǎng)度,必須先求出上述方程中的a,由于它是關(guān)于a的非線性方程,沒(méi)有現(xiàn)成的公式可用,,因此只能尋求其他解法.在實(shí)際應(yīng)用中有許多非線性方程的例子，例如求f(x)=0的根（1）在光的衍射理論（thetheoryofdiffractionoflight)中,我們需要求x-tanx=0的根（2）在行星軌道（planetaryorbits）的計(jì)算中,對(duì)任意的a和b，我們需要求x-asinx=b的根（3）在數(shù)學(xué)中，需要求n次多項(xiàng)式xn

+a1

xn-1+...+an-1x+an

＝0

的根滿足方程的x值通常叫做方程的根或解，也叫函數(shù)f(x)=0的零點(diǎn)。非線性方程的一般形式：f(x)=0這里f(x)是單變量x的函數(shù)。代數(shù)多項(xiàng)式：

f(x)=a0+a1x+……+anxn

(an≠0)非線性方程可分為兩種：超越函數(shù)，即不能表示為上述形式的函數(shù)。遠(yuǎn)在公元前1700年的古巴比倫人就已有關(guān)于一、二次方程的解法。1535年意大利數(shù)學(xué)家坦特格里亞(TorTaglia)發(fā)現(xiàn)了三次方程的解法，卡當(dāng)(H·Cardano)從他那里得到了這種解法，于1545年在其名著《大法》中公布了三次方程的公式解，稱為卡當(dāng)算法。后來(lái)卡當(dāng)?shù)膶W(xué)生弗瑞里(Ferrari)又提出了四次方程的解法。第二章非線性方程的數(shù)值解法1799年，高斯證明了代數(shù)方程必有一個(gè)實(shí)根或復(fù)根的定理，稱此為代數(shù)基本定理，并由此可以立刻推理n次代數(shù)方程必有n個(gè)實(shí)根或復(fù)根。但求解五次方程時(shí)未能如愿,開(kāi)始意識(shí)到有潛藏其中的奧妙,用現(xiàn)代術(shù)語(yǔ)表示就是置換群理論問(wèn)題。在繼續(xù)探索5次以上方程解的艱難歷程中，第一個(gè)重大突破的是挪威數(shù)學(xué)家阿貝爾(N·Abel1802-1829)1824年阿貝爾發(fā)表了“五次方程代數(shù)解法不可能存在”的論文，但并未受到重視，連數(shù)學(xué)大師高斯也未理解這項(xiàng)成果的重要意義。十四年后，法國(guó)數(shù)學(xué)家劉維爾(J·Liouville)整理并發(fā)表了伽羅華的遺作，人們才意識(shí)到這項(xiàng)近代數(shù)學(xué)發(fā)展史上的重要成果的寶貴。38年后，即1870年，法國(guó)數(shù)學(xué)家若當(dāng)(C·Jordan)在專著《論置換與代數(shù)方程》中闡發(fā)了伽羅華的思想，一門現(xiàn)代數(shù)學(xué)的分支—群論誕生了。在前幾個(gè)世紀(jì)中，曾開(kāi)發(fā)出一些求解代數(shù)方程的有效算法，它們構(gòu)成了數(shù)值分析中的古典算法。至于超越方程則不存在一般的求根方式。方程根的數(shù)值計(jì)算步驟判斷根的存在確定根的分布范圍根的精確化

根的存在定理(零點(diǎn)定理)：

f(x)為[a,b]上的連續(xù)函數(shù)，若f(a)·f(b)<0，則[a,b]中至少有一個(gè)實(shí)根。如果f(x)在[a,b]上還是單調(diào)遞增或遞減的，則f(x)=0僅有一個(gè)實(shí)根。根的分布范圍:

在用近似方法時(shí)，需要知道方程的根所在區(qū)間。若區(qū)間a,b含有方程f(x)=0的根，則稱a,b為f(x)=0的有根區(qū)間；若區(qū)間a,b僅含方程f(x)=0的一個(gè)根，則稱a,b為f(x)=0的一個(gè)隔根區(qū)間。求隔根區(qū)間有兩種方法：例如，求方程3x-1-cosx=0的隔根區(qū)間。將方程等價(jià)變形為3x-1=cosx

，易見(jiàn)y=3x-1與y=cosx的圖像只有一個(gè)交點(diǎn)位于[0.5，1]內(nèi)。畫(huà)出y=f(x)的略圖，從而看出曲線與x軸交點(diǎn)的大致位置。也可將f(x)=0等價(jià)變形為g1(x)=g2(x)的形式，y=g1(x)與y=g2(x)兩曲線交點(diǎn)的橫坐標(biāo)所在的子區(qū)間即為含根區(qū)間。(1)描圖法(2)逐步搜索法運(yùn)用零點(diǎn)定理可以得到如下逐步搜索法：先確定方程f(x)=0的所有實(shí)根所在的區(qū)間為[a,b],從x0=a出發(fā),以步長(zhǎng)

h=(b-a)/n

其中n是正整數(shù)，在[a,b]內(nèi)取定節(jié)點(diǎn)：

xi=x0＋ih

(i=0,1,2，……，n)

計(jì)算f(xi)的值,依據(jù)函數(shù)值異號(hào)及實(shí)根的個(gè)數(shù)確定隔根區(qū)間,通過(guò)調(diào)整步長(zhǎng)，總可找到所有隔根區(qū)間。例1方程f(x)=x3-x-1=0確定其有根區(qū)間解：用試湊的方法，不難發(fā)現(xiàn)

f(0)<0f(2)>0

在區(qū)間（0，2）內(nèi)至少有一個(gè)實(shí)根設(shè)從x=0出發(fā),取h=0.5為步長(zhǎng)向右進(jìn)行根的搜索,列表如下xf(x)00.51.01.52

–––++可以看出，在[1.0,1.5]內(nèi)必有一根§1二分法設(shè)函數(shù)f(x)在區(qū)間［a,b］上單調(diào)連續(xù),且

f(a)·f(b)＜0則方程在區(qū)間(a,b)內(nèi)有且僅有一個(gè)實(shí)根x。下面在有根區(qū)間(a,b)內(nèi)介紹二分法的基本思想。x0=(a+b)2若:f(a)·f(x0)＜0

則，令a1=a，b1=x0

否則，令a1=x0，b1=b如此逐次往復(fù)下去,便得到一系列有根區(qū)間

(a,b),(a1,b1),(a2,b2),…,(ak,bk),…

其中這里a0=a,b0=b顯然有當(dāng)k→∞時(shí),區(qū)間(ak,bk)最終必收斂于一點(diǎn),該點(diǎn)就是所求方程的根x。abx0x1ab什么時(shí)候停止？x*誤差分析：第1步產(chǎn)生的有誤差第k步產(chǎn)生的xk

有誤差對(duì)于給定的精度

,可估計(jì)二分法所需的步數(shù)k：計(jì)算步驟：①輸入有根區(qū)間的端點(diǎn)a、b及預(yù)先給定的精度ε;②(a+b)/2x;③若f(a)f(x)＜0，則xb，轉(zhuǎn)向④;否則xa，轉(zhuǎn)向④。④若b-a＜ε,則輸出方程滿足精度的根x，結(jié)束；否則轉(zhuǎn)向②。二分法具有簡(jiǎn)單和易操作的優(yōu)點(diǎn)。例1求方程

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

在區(qū)間(1,1.5)內(nèi)的根。要求用四位小數(shù)計(jì)算,精確到10-2。

解：這里

a=1，b=1.5

取區(qū)間(1，1.5)的中點(diǎn)由于f（1）＜0，f（1.5）>0f(1.25)＜0,則令

a1=1.25,b1=1.5

得到新的有根區(qū)間(1.25,1.5)§2迭代法迭代法的基本思想是:

首先將方程f(x)改寫(xiě)成某種等價(jià)形式，由等價(jià)形式構(gòu)造相應(yīng)的迭代公式，然后選取方程的某個(gè)初始近似根x0，代入迭代公式反復(fù)校正根的近似值，直到滿足精度要求為止。迭代法是一種數(shù)值計(jì)算中重要的逐次逼近方法。f(x)=x-g(x)=0x=g(x)等價(jià)變換f(x)的根g(x)的不動(dòng)點(diǎn)例：求方程

x3-x-1=0在x=1.5附近的一個(gè)根(用六位有效數(shù)字計(jì)算)。首先將原方程改寫(xiě)成等價(jià)形式用初始近似根

x0=1.5代入上式的右端可得雖然迭代法的基本思想很簡(jiǎn)單，但效果并不總是令人滿意的。對(duì)于上例，若按方程寫(xiě)成另一種等價(jià)形式

x=x3-1

建立迭代公式

xk+1=x3k-1,k=0,1,2,…

仍取初始值x0=1.5,則迭代結(jié)果為

x1=2.375x2=12.3976幾何意義:x=g(x)xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=g(x)y=g(x)y=g(x)y=φ(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1同樣的方程不同的迭代格式有不同的結(jié)果什么形式的迭代法能夠收斂呢?如何構(gòu)造迭代函數(shù)呢?若從任何可取的初值出發(fā)都能保證收斂，則稱它為大范圍收斂。如若為了保證收斂性必須選取初值充分接近于所要求的根，則稱它為局部收斂。通常局部收斂方法比大范圍收斂方法收斂得快。因此，一個(gè)合理的算法是先用一種大范圍收斂方法求得接近于根的近似值（如對(duì)分法），再以其作為新的初值使用局部收斂法（如迭代法）。這里討論迭代法的收斂性時(shí)，均指的是局部收斂性。則方程在(a,b)內(nèi)有唯一的根；

定理/收斂定理/壓縮映像原理設(shè)方程x=g(x)在(a,b)內(nèi)有根x*

g(x)滿足李普希茨(Lipschitz)條件:即對(duì)(a,b)內(nèi)任意的x1

和x2都有：

q為某個(gè)確定的正數(shù)，q＜1條件結(jié)果3.還有誤差估計(jì)式2.且迭代公式xk+1=g(xk)對(duì)任意初始近似值x0均收斂于方程的根x；由已知條件知，x*為方程x=g(x)的根，即x*=g(x*)設(shè)也是方程的根，即于是，由李普希茨條件得因?yàn)閝＜1，所以上式矛盾，故必有證1.有唯一根考慮迭代公式

x

k+1=g(xk),k=0,1,2,…

由李普希茨條件證2.迭代公式收斂因?yàn)閝＜1，當(dāng)k→∞時(shí)，qk→0，即有所以證3.誤差|xk-x*|=|xk-xk-1|=|g(xk-1)-g(xk-2)||xk-x*|≤q/(1-q)|xk-xk-1||xk-x*|≤qk/(1-q)|x1-x0|可用來(lái)控制收斂精度李普希茨(Lipschitz)條件|g(xk-1)-g(x*)|≤q

|xk-1-x*|≤

q

(|xk-xk-1|+|xk-x*|)≤

q

|xk-1-xk-2|≤…≤qk-1|x1-x0|②要驗(yàn)證g(x)是否滿足李氏條件一般比較困難，若g(x)可微，可用條件來(lái)判斷迭代公式是否收斂。必須說(shuō)明兩點(diǎn):①對(duì)于收斂的迭代過(guò)程，誤差估計(jì)式說(shuō)明迭代值的偏差｜xk-xk-1｜相當(dāng)小，就能保證迭代誤差｜x-xk｜足夠小。因此在具體計(jì)算時(shí)常常用條件｜xk-xk-1｜＜ε

來(lái)控制迭代過(guò)程結(jié)束。

例

求方程

x=e-x

在x=0.5附近的一個(gè)根。按五位小數(shù)計(jì)算,計(jì)算結(jié)果的精度要求為ε=10-3。解過(guò)x=0.5以步長(zhǎng)h=0.1計(jì)算

f(x)=x-e-x

由于

f(0.5)＜0，f(0.6)＞0

故所求的根在區(qū)間(0.5,0.6)內(nèi),且在x=0.5附近開(kāi)始結(jié)束輸入輸出FTg(x)=e-x因此用迭代公式

由表可見(jiàn)為方程的根最一般的形式可以寫(xiě)成

x=x+α(x)f(x)

這里α(x)為任意一個(gè)正(或負(fù))的函數(shù)。于是

g(x)=x+α(x)f(x)

這樣只要合理選取α(x),使得迭代公式滿足收斂條件如何構(gòu)造迭代函數(shù)g(x)呢?切線迭代公式：弦截迭代公式：設(shè)x*是方程f(x)=0的根，又x0

為x*附近的一個(gè)值，將f(x)在x0附近做泰勒展式§3切線法(牛頓法)令，則去掉的二次項(xiàng)，有：即以x1代替x0重復(fù)以上的過(guò)程，繼續(xù)下去得：以此產(chǎn)生的序列{xn}得到f(x)=0的近似解，稱為Newton法，又叫切線法。牛頓法的幾何意義xyx*x0x

1x

2牛頓法也稱為切線法Newton迭代的方程為：所以若f(x)在x*處為單根，則所以，迭代格式收斂。Newton迭代法的收斂性注：Newton’sMethod收斂性依賴于x0

的選取。x*x0x0x0(1)選定初值x0、(3)按迭代公式得新的近似值xk+1

(4)判定誤差，決定是否終止迭代。(2)計(jì)算f(x)Newton迭代法的步驟Newton迭代法的步驟結(jié)束輸出F輸入輸出求FTT允許精度最大迭代次數(shù)

例

用Newton迭代法求方程xex-1=0在0.5附近的根,

精度要求=10-5.

解：Newton迭代格式為kxk?(xk)|xk-xk-1|012340.50.571020440.567155570.567143290.56714329-0.175639360.010747510.000033930.00000000030.00000000030.071020440.003864870.000012280.00000000牛頓迭代法的優(yōu)缺點(diǎn)1、優(yōu)點(diǎn)：牛頓迭代法具有平方收斂的速度，所以在迭代過(guò)程中只要迭代幾次就會(huì)得到很精確的解。這是牛頓迭代法比簡(jiǎn)單迭代法優(yōu)越的地方。2、缺點(diǎn)：選定的初值要接近方程的解，否則有可能得不到收斂的結(jié)果。再者，牛頓迭代法計(jì)算量比較大。因每次迭代除計(jì)算函數(shù)值外還要計(jì)算微商值。將Newton迭代中的導(dǎo)數(shù)，用差商代替，有格式是2步格式。收斂速度比Newton迭代慢x0x1切線

割線

§4弦截法x2x2點(diǎn)xk+1是滿足該弦的方程的點(diǎn)，即有從而可求得弦截迭代公式(2―23)例4用弦截法解方程

xex-1=0

解取x0=0.5,x1=0.6作為初始近似根,令

f(x)=x-e-x=0

利用上面公式得到弦截迭代公式為計(jì)算結(jié)果見(jiàn)下頁(yè)表?？梢钥闯鱿医胤ǖ氖諗克俣纫彩潜容^快的。

§5加速迭代法

已知方程的近似根xk，按迭代公式可求得xk+1?，F(xiàn)考慮把xk+1作為過(guò)渡值,記為仍然設(shè)x*為方程的根，即由迭代公式有：

a也即整理得到于是,只要取這樣可得到加速迭代公式

例5

用加速迭代公式求方程

x=e-x

在x=0.5附近的一個(gè)根。解因?yàn)樵趚=0.5附近

g′(x)=-e-xg′(0.5)=-e-0.5≈-0.6故加速迭代公式的具體形式為：與例2（P35）比較：例2：迭代十次滿足精度ε=10-3

例5：迭代三次滿足精度ε=10-5上述迭代法需要計(jì)算導(dǎo)數(shù)a≈g′(x)，下面介紹埃特金(Aitken)迭代方法。它也是一種加速迭代法。埃特金迭代法將上兩式聯(lián)立消去a得到可解出這樣得到埃特金迭代公式

例6

用埃特金迭代法求

x3-x-1=0

在(1,1.5)內(nèi)的根。解前面已經(jīng)提到,迭代公式

xk+1=x3k-1,k=0,1,2,…

是發(fā)散的?，F(xiàn)用埃特金算法來(lái)求根,其迭代公式為仍取x0=1.5,計(jì)算結(jié)果見(jiàn)下表。定義2.2.1

設(shè)序列收斂到，若有實(shí)數(shù)和非零常數(shù)C，使得其中