計算方法2方程求根

12學習要點方程求根的三個問題：根的存在性、根的分布、根的精確化；二分法：將有根區(qū)間二分，根據函數的符號變化逐步縮短有根區(qū)間；迭代法：將方程等價轉化為另一種形式，并構造迭代公式；牛頓迭代法與割線法；32.1問題的提出

函數方程f（x）=0若f(x)不是x的線性函數,則稱為非線性方程

,特別地若f(x)是n次多項式，則稱為n次多項式方程或代數方程；若f(x)是超越函數，則稱為超越方程。如果函數f（x）=（x-x*）m

g(x)且g(x*)

0,則稱x*是

(x)的m重零點或

(x)=0的m重根。當m=1時，稱x*是

(x)的單根或單零點。4理論上已證明:對于次數n<=4的多項式方程，它的根可以用公式表示;而次數大于5的多項式方程，它的根一般不能用解析表達式表示;因此對于f(x)=0的函數方程，只要得到滿足精度要求的根的近似值就可以了。常用的求根方法分為區(qū)間法和迭代法兩大類。5數值求根問題包括：根的存在性根的范圍根的精確化6根的存在定理：

假設函數y=f(x)，

xa,b

，且f(a)·f(b)<0，函數圖象如圖則至少存在一點xa,b

使得

f(x)=0，這就是根的存在定理。yxba7第一步：求根的隔離區(qū)間。確定根所在的區(qū)間，使方程在這個小區(qū)間內有且僅有一個根，這就是根的隔離過程。所得小區(qū)間稱為方程的根的隔離區(qū)間或有根區(qū)間。第二步：將根精確化。已知一個根的近似值后，再用一種方法將此近似值精確化，使其滿足給定的精度要求。通常分兩步來求根8三種方法來求根的隔離區(qū)間

作圖法

方程等價變換法

搜索法

9例1的有根區(qū)間10例2求

的有根區(qū)間112.2二分法二分法是求方程近似根的方法中，最直觀、最簡單的一種方法給定方程f(x)=0，設f(x)在區(qū)間[a,b]連續(xù)，嚴格單調，且

f(a)·

f(b)<0，則[a,b]為f(x)=0的一個有根區(qū)間?；舅枷耄河脤Ψ謪^(qū)間的方法根據分點處函數f(x)值的符號逐步將有根區(qū)間縮小，使在足夠小的區(qū)間內，方程有且僅有一個根12記a0=a,b0=b。用中點x0=(a0+b0)/2將區(qū)間[a0,b0]分成2個小區(qū)間：[a0,x0]和[x0,b0]；計算f(x0)，若f(x0)=0，則x0為f(x0)=0的根，計算結束。否則f(a0)f(x0)<0與f(x0)f(b0)<0兩式中有且僅有一式成立。若f(a0)f(x0)<0，令a1=a0，b1=x0，若f(x0)f(b0)<0，令a1=x0，b1=b0；于是[a1,b1]為新的有根區(qū)間，[a0,b0]

[a1,b1]，且后者長度為前者的一半。具體方法：13對新的有根區(qū)間[a1,b1]施行同樣的手續(xù)，于是得到一系列有根區(qū)間[a0,b0]

[a1,b1]

[a2,b2]

……

[ak,bk]其中每一個區(qū)間的長度都是前一個區(qū)間長度的一半，最后一個區(qū)間的長度為bk-ak=（b-a）/2k如果取最后一個區(qū)間[ak,bk]的中點xk=(ak+bk)/2作為f(x)=0根的近似值，則有誤差估計式 |xk-x*|≤(bk-ak)/2=（b-a）/2k+114abb1a1x015例3

用二分法求方程

在區(qū)間[0,1]內的1個實根，要求有3位有效數字。16計算結果kak(f(ak)的符號)xk(f(xk)的符號)bk(f(bk)的符號)00(+)0.5(-)1(-)10(+)0.25(+)0.5(-)20.25(+)0.375(+)0.5(-)30.375(+)0.4375(+)0.5(-)40.4375(+)0.46875(+)0.5(-)50.4375(+)0.453125(-)0.46875(+)60.4375(+)0.4453125(-)0.453125(-)70.4375(+)0.44140625(+)0.4453125(-)80.44140625(+)0.443359375(+)0.4453125(-)90.443359375(+)0.444335937(+)0.4453125(-)100.444335937(+)0.444824218(+)0.444335937(+)17二分法的優(yōu)點與缺點優(yōu)點：計算簡單，方法可靠缺點：不能求偶數重根；不能求復根；收斂速度慢182.3簡單迭代法一迭代格式的構造及其斂散性條件：已知方程

f(x)=0在區(qū)間[a,b]內有1個根x*。在區(qū)間[a,b]將其改寫成同解方程 x=φ(x)

迭代函數迭代法是數值計算中的一種典型方法，不僅用于方程求根，而且用于方程組求解、矩陣求特征值等方面19取x0∈[a,b]，用遞推公式xk+1=φ(xk)k=0,1,2,…… 可得到序列x0,x1,x2……。如果k→∞,序列{xk}有極限x*,且φ(x）在x*附近連續(xù)，則對上式兩邊取極限，得x*=φ(x*)因而x*是方程x=φ(x)的解，x*也是方程的根迭代格式迭代序列20例

f（x）=x2–2x-3=0它在區(qū)間[2,4]內有唯一根x*。方程可以改寫為多種等價形式，如：1）此時取x0=4，得迭代公式當k越來越大，xk趨近精確根x*=3212）此時仍然取x0=4，得迭代公式當k越來越大，xk離精確根越來越遠22如何判斷所構造的迭代函數x=φ(x)使得迭代序列{xk}收斂或發(fā)散？怎樣估計誤差？問題P0(x0,x1)y2=φ(x)y1=x

x

yoP1(x1,x2)P2P*Q1P0(x0,x1)y2=φ(x)y1=x

x

yoP1(x1,x2)P2P*Q123若迭代法中的迭代函數g(x)在區(qū)間[a,b]上具有一階連續(xù)的導數，且滿足如下2個條件；對任意x∈[a,b]，a≤g(x)≥b;在區(qū)間[a,b]上g’(x)存在，且|g’(x)|≤L<1.則有如下結論：（1）對于任意初始近似值x0∈[a,b]，迭代法xk+1=g(xk)產生的迭代序列{xk}都收斂于方程x=g(x)在區(qū)間[a,b]上的唯一實根x*;

（2）定理24拉格朗日中值定理設函數y=f(x)在閉區(qū)間

a,b

上連續(xù)，在開區(qū)間(a,b)內可導，則在(a,b)內至少有一點ξ，使得25二迭代法的收斂速度定義：

設序列{xk}收斂于x*，并記ek=xk-x*(k=0,1,2,…)。如果存在非零常數p，使得

則稱序列{xk}是p階收斂的。當p=1，且0<|c|<1，稱為線性收斂；當P>1，稱為超線性收斂。特別，當p=2，稱為平方收斂262.4牛頓法與割線法一牛頓迭代公式x*xkxk+1xyoy=f(x)(xk,f(xk))27設xk是f(x)=0的一個近似根，把f(x)在xk處作一階Taylor展開于是：設f’(xk)≠0，則近似解為：取xk+1為原方程新的近似根，得到牛頓迭代公式28定義:

對于方程x=

φ(x)，若在x*的某個鄰域S={x|x∈[x*-δ,x*+δ]}內，對任意初始值x0∈S，迭代格式xk+1=φ(xk)k=0,1,2,……（3.14）都收斂，則稱該迭代格式在x*的附近是局部收斂的。定理:

設方程x=

φ(x)有根x*，且在x*的某個鄰域內φ(x)存在一階連續(xù)的導數，則（1）當|φ’(x)|<1時，迭代格式（3.14）局部收斂（2）當|φ’(x)|>1時，迭代格式（3.14）發(fā)散二牛頓法的局部收斂性29二牛頓法的局部收斂性對φ(x)求導牛頓法的迭代函數為由于f’(x*)≠0，因此φ(x*)=0，由局部收斂定理得知，牛頓迭代法是局部收斂的。30而且，無論當x*是f(x)的單根還是重根，牛頓法均為局部收斂。需要注意的是：初值x0需要足夠靠近x*31牛頓法的收斂階數又由牛頓迭代公式得將f’(x*)在xk處泰勒展開，得代入上式，有32牛頓法的收斂階數即，令k∞，由局部收斂性得知：xkx*時，從而xkx*，所以牛頓迭代法至少為平方收斂33例

用牛頓法求方程f(x)=x(x+1)2-1=0,在0.4附近的根，精確至4位有效數字解: 對f(x)求導得

f’(x)=(x+1)(3x+1)

牛頓迭代格式為取x0=0.4,計算結果為k 0 1 2 3xk 0.4 0.47013 0.46559 0.46557因此 x*≈0.4656341割線法幾何意義四割線法x*xk-1xk+1xyoy=f(x)AB35切線斜率

割線斜率割線法用差商代替求導，減少了牛頓法的計算量，但是需要2個初值x