数值计算方法 第4版 课件 第2章 非线性方程的数值解法

第2章非线性方程的数值解法

2.1初始近似值的搜索

2.2迭代法

2.3牛顿迭代法（切线法）

2.4弦截法（割线法）2.1初始近似值的搜索2.1.1方程的根单根和重根有根区间

假设f(x)在区间[a,b]内有一个实根x*,若b–a较小，则可在(a,b)上任取一点x0作为初始近似根。

一般情形，可用逐步搜索法。2.1.2逐步搜索法例对方程搜索有根区间。解由于f(x)是连续函数，

f(0)=-1<0，f(2)>0，故方程至少有一正实根。设从x=0

出发，取h=0.5为步长，逐步右跨搜索，得x00.51.01.5f(x)―――+所以f(x)在区间（1,1.5）上单调连续，因而在(1,1.5)内有且仅有一个实根，故可取[1,1.5]上任一点做初始近似根。可见在（1，1.5）内有根。又

2.1.3区间二分法

定理函数f(x)在[a,b]上单调连续，且f(a)f(b)<0，则方程f(x)=0在区间[a,b]上有且仅有一个实根x*。

二分法的基本思想将有根的区间二分为两个小区间，然后判断根在那个小区间，舍去无根的小区间，而把有根的小区间再一分为二，再判断根属于哪个更小的区间，如此反复，直到求出满足精度要求的近似根。令

近似根xk的误差估计中点这时有三种情况：

f(x0)=0,x0为所求的根.f(x0)和a0

同号，取x0=

a1

f(x0)和b0

同号，取x0=

b1

x*x*新的有根区间为(a1,b1)，长度是原来的一半。如此反复，有∈(ak,bk),k=0,1,2,…..

近似根xk的误差估计第2次二分，取中点若f(a1)f(x1)<0，则x*∈(a1,x1)，令a2=a1,b2=x1；否则令a2=x1,b2=b1

。新的有根区间为(a2,b2)。由此得二分过程结束的原则：先给定精度要求ε(绝对误差限)，

（2）当|bk+1–ak+1|<ε时结束二分计算，取

x*≈xk

；

（1）事先由ε估计出二分的最小次数k

，取x*≈xk

2.2迭代法2.2.1迭代原理2.2.2迭代的收敛性2.2.3迭代的收敛速度2.2.4迭代的加速预备定理2.2.1迭代原理计算结果见下表

方程f(x)=0化为等价形式的方程x=φ(x)，构造迭代公式xk+1=φ(xk

),k=0,1,2,……取初始近似根x0

,进行迭代计算x1=φ(x0),x2=φ(x1),……..则有x1,

x2,,…….,xk

,

…….,得到迭代序列{xk

}.如果这个序列有极限，则迭代公式是收敛的。这时

则，x*

为不动点，等价地有f(x*)=0,x*

即为方程的根。连续函数φ(x)称为迭代函数。实际计算到|xk–xk-1|<ε（ε是预定的精度），取x*≈xk

。

迭代公式收敛指迭代序列{xk

}收敛，迭代公式发散指迭代序列{xk

}不收敛，即发散。迭代公式不一定总是收敛。例如求方程

f(x)=x3-x-1=0的一个根。对应的迭代公式为取初值迭代序列{xk

}发散.x1=φ(x0)x2=φ(x1)迭代法收敛与发散的图示迭代法的收敛与发散

收敛的情形发散的情形2.2.2迭代的收敛性迭代法的收敛条件及误差估计式定理（充分性条件）

设函数

φ(x)

在[a,b]上连续，且

(1)对x∈[a,b],有φ

(x)∈[a,b](2)存在0<L<1，使对任意x∈[a,b]有

|φ

′(x)|≤L<1则方程x=φ(x)在[a,b]上的根x*存在且唯一；对初值

x0∈[a,b]

,迭代过程xk+1=

φ

(xk)均收敛于方程的根x*。定理中的(1)对x∈[a,b],有φ(x)∈[a,b]，称为适定性（映内性）。证明先证根的存在性。作连续函数ψ(x)=x-φ(x),由条件（1）x∈[a,b],φ

(x)∈[a,b]，即a≤φ(x)、x≤b,于是

ψ(a)=a-φ

(a)≤0

ψ(b)=b-φ(b)≥0

由于ψ(x)是连续函数，故必存在

x*∈[a,b]

使ψ(x*)=0.即ψ(x*)=x*-φ(x*)=0.于是

x*=φ

(x*)即x*为方程

x=φ

(x)的根。其次，证根的唯一性。

设y*也是方程的根，则x*=φ(x*),y*=φ(y*),x*-y*=φ(x*)–φ(y*)=φ′(ξ)(x*-y*)x*-y*–φ′(ξ)(x*-y*)=0，（x*-y*）[1-

φ′(ξ)]=0由条件（2）|φ′(x)|≤L<1，故有x*-y*=0，即x*=y*所以方程在[a,b]的根唯一。

再证迭代的收敛性。由xk=φ(xk-1),x*=φ(x*),有|xk-x*|=|φ′(ξ)(xk-1-x*)|≤L|xk-1-x*|≤L2|xk-2-x*|≤L3|xk-3-x*|≤……≤Lk|x0-x*|→0（k→∞）

所以，对[a,b]上任取的x0,迭代公式xk+1=φ(xk

)都收敛于x*。

L越小收敛得越快。定理是充分性条件xk-x*=φ(xk-1)–φ(x*)=φ′(ξ)(xk-1-x*)推论：在定理的条件下，有误差估计式验后误差估计式验前误差估计式证明：|xk-x*|≤L|xk-1-x*|=L|xk-1-xk+xk-x*|≤L（|xk-x*|+|xk-1-xk|）（1-L)|xk-x*|≤L|xk-1-xk|迭代法的终点判断：只要相邻两次迭代值的偏差充分小，就能保证迭代值足够准确，因而用|xk-xk-1|控制迭代过程的结束。

定理设在区间[a,b]上方程x=φ(x)有根x*,且对一切x∈[a,b]都有|

φ′(x)|≥1，则对于该区间上任意x0(≠x*),迭代公式xk+1=φ(xk

)一定发散。证明不可能收敛于0。计算结果见下表取方程的根2.0946。由于，故取

迭代法的局部收敛性由于在实际应用中根

x*

事先不知道，故条件

|φ′(x*)|<1无法验证。但已知根的初值x0在根

x*邻域，又根据φ′(x)的连续性，则可采用

|φ′(x0)|<1来代替|φ′(x*)|<1，判断迭代的收敛性。

例求方程

x=e

–x在x=0.5附近的一个根，按5位小数计算，结果的精度要求为ε=10–3.解迭代公式xk+1=e

–xk，取φ

(x)=e–x,迭代公式xk+1=e

–xk收敛。迭代结果:

0123450.50.606530.545240.579700.560070.57117

0.10653

－0.061290.03446

－0.019630.011106789100.564860.568440.566410.567560.56691

－0.006310.00358

－0.002030.00115

－0.00065kxkxk–xk-1xk–xk-1k

xk|x10-x9|=0.00065<ε，故x*≈x10≈0.567x0=0.5,

x2=e

–x1=0.54524,…….x1=e–x0=0.60653,xk+1=e

–xk迭代的计算步骤

迭代法计算框图的说明2.2.3迭代过程的收敛速度2.2.4迭代的加速

2埃特金加速与斯蒂芬森迭代法

埃特金迭代将不动点迭代法与埃特金加速结合即得斯蒂芬森迭代法2.3牛顿迭代法2.3.1迭代公式的建立2.3.2牛顿迭代法的收敛情况2.3.3牛顿迭代法的修正法2.3.1迭代公式的建立

3.几何意义

过曲线上的点pk(xk,f(xk))作切线，切线方程

y=f(xk)+f

(xk)(x–xk)

切线方程和横轴的交点(xk+1,0)

，即

0=

f(xk)+f

(xk)(xk+1–xk)若

f

(xk

)≠0，解出xk+1，则得Newton迭代公式例用牛顿迭代法求方程xex-1=0在x=0.5附近的根。解牛顿迭代法

取x0=0.5，经计算可得普通迭代法18次才能得到的计算结果。,则x2-a=0,求等价于求方程

令例造平方根表。用牛顿迭代法计算(其中a>0)解的正实根。因为

f′(x)=2x，由牛顿迭代公式得当a=115时，取初值x0=10，迭代4次可得10，10.7500，10.723837，10.723805，10.723805≈10.723805是否还能用牛顿法计算一个正数的立方根？,则x3-3=0,

求等价于求方程

令例用牛顿迭代法求解的正实根。由牛顿迭代公式得当a=4111.7910时，取初值

x0=8，迭代4次可得7.48，7.439977,7.439760,7.439760,令例用牛顿迭代法造倒数表，计算解3、牛顿迭代法的计算步骤(1)给出x0,ε，N(2)计算(3)若则转(4)；否则，转(2);(4)输出x1,结束。牛顿迭代法局部收敛