数值分析方法第三章

第二章非线性方程求根/*SolutionsofNonlinearEquations

*/求f(x)=0的根2024/1/161.求根问题包括下面三个问题：根的存在性：即f(x)=0有没有根？假设有，有几个根？哪儿有根？确定有根区间根的精确化：一个根的近似值后，能否将它精确到足够精度？.问题的提出方程：y=f

(x)方程的根：x=?

y=0xy0y=f

(x)x=?y=3x-2(x=2/3)y=x2-2x+1

(x=1)y=6.7410-3-exp(-5000/x)非线性问题(x

1000)2024/1/163.科学技术中常遇到高次代数方程或超越方程的求根问题。大于4次的代数方程无求根公式。因此需要研究函数方程求根问题的数值方法。例如：求解高次方程7x6-x3+x-1.5=0的根。

ex-cos(

x)=0求解含有指数和三角函数的超越方程的根。.Why数值计算？根：数值analyticalmethodnumericalmethod无解析方法2024/1/165.求实根近似值的常用方法1、二分法2、迭代法3、牛顿法4、弦截法2024/1/166.§二分法/*BisectionMethod*/原理：假设fC[a,b]，且f(a)·f(b)<0，那么f在(a,b)上必有一根。问题求连续函数y=f(x)

在区间[a,b]上的唯一实根y=0xyy=f(x)ab分析“实根”两侧f(x)反号“实根”同侧f(x)同号若:f(x1)f(x2)反号，则

“实根”在x1和x2之间方法逐步缩小“有根区间”2024/1/167.

执行步骤1．计算f(x)在有解区间[a,b]端点处的值，f(a)，f(b)。2．计算f(x)在区间中点处的值f(x0)。3．判断假设f(x0)=0，那么x0即是根，否那么检验：〔1〕假设f(x0)与f(a)异号，那么知解位于区间[a,x0]，b1=x0,a1=a;〔2〕假设f(x0)与f(a)同号，那么知解位于区间[x0,b]，a1=x0,b1=b。反复执行步骤2、3，便可得到一系列有根区间：

(a,b),(a1,b1),…,(ak,bk),…2024/1/16.的一个正的近似解〔精确到0.1〕x2-2x-1=0-+23f(2)<0，f(3)>02<x1<3-+22.53f(2)<0，f(2.5)>02<x1<2.5-+22.252.53f(2.25)<0，f(2.5)>02.25<x1<2.5-+22.3752.53f(2.375)<0，f(2.5)>02.375<x1<2.5-+22.3752.43753f(2.375)<0，f(2.4375)>02.375<x1<2.4375求方程每个有根区间的长度都是前一个有根区间长度的一半.abx1x2abWhentostop?或不能保证x

的精度x*

2xx*2024/1/1610.误差分析：有误差第k步产生的xk

有误差对于给定的精度

,可估计二分法所需的步数k：第1步产生的有误差2024/1/1611.①简单;②对f(x)

要求不高(只要连续即可).①无法求复根及偶重根②收敛慢2024/1/1612.例：求以下方程位于区间[1,1.5]内的一个根2024/1/1613.多根的求法运用零点定理可以得到如下逐步搜索法：

先确定方程f(x)=0的所有实根所在的区间为[a,b],从x0=a

出发,以步长

h=(b-a)/n

其中n是正整数，在[a,b]内取定节点：

xi=x0＋ih(i=0,1,2，……，n)

计算f(xi)的值,依据函数值异号及实根的个数确定隔根区间,通过调整步长，总可找到所有隔根区间。.

y

x

a

b

o在计算中步长h要适当取小一些,假设h过长那么容易丢根(假设在区间范围内有两相邻函数值符号相同而判定无根)假设间隔h值太小,那么影响计算速度。

.“数学〞上是正确的， 但作为一种“数学方法〞， 应用于实际的“科学问题〞时， 不是“放之四海而兼准〞的。

f(x)

在[a,b]上连续

f(a)f(b)<0应用二分法求解.有(2n+1)个根时

例：已知f(x)在[0,

)上连续，且f(0)>0，

f(

)<0。 欲求x尽可能小的根。求解过程尝试

：f(1)>0尝试

：f(5)>0尝试

：f(10)<0二分法：f(8)=0x0y105但是，实际曲线

杜绝教条主义.迭代法迭代法是数值计算中一种典型的重要方法，尤其是计算机的普遍使用，使迭代法的应用更为广泛。所谓迭代法就是用某种收敛于所给问题的精确解的极限过程来逐步逼近的一种计算方法，从而可以用有限个步骤算出精确解的具有指定精度的近似解。简单说迭代法是一种逐步逼近的方法。循环迭代，用上一轮结果计算下一轮数据。2024/1/1618.§迭代法/*Fixed-PointIteration

*/思路2024/1/1619.2024/1/1620.迭代序列收敛2024/1/1621.迭代序列发散2024/1/1622.说明：①迭代函数不唯一②迭代序列可能收敛，也可能发散③迭代收敛与否不仅与迭代函数有关，还与初始点有关。.xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0x1p1

x0p0x1p1

x0p0x1p1

x0p0x1p1

2024/1/1624.问题：(1)

|g´(x)|<1，迭代法是否一定收敛？(2)

|g´(x)|

1，迭代法是否一定发散？.迭代序列收敛性的判断原始方程：f(x)=0等价方程：x=g(x)设f(x)=0的根在[a,b]区间内0y=xyxababy=g(x)发散迭代方程组:

y=x,

y=g(x)要求：(1)

y=g(x)也在[a,b]内0y=xyxababy=g(x)DxDg(x)Dg(x)<Dx(2)

|g´(x)|

L<1迭代法收敛的充分条件.那么有：1、存在唯一的实根2、迭代收敛，且有误差估计3、.证明：①g(x)在[a,b]上存在实根？令有根②实根唯一？反证：若不然，设还有，则在和之间。而③当k

时，

xk收敛到x*？

.④

⑤

⑥

可用来控制收敛精度L越收敛越快小.例题能不能用迭代法求解以下方程？如果不能，试将方程改写成能用迭代法求解的形式〔1〕x=(sinx+cosx)/4〔2〕x=4-2x([1,2])

.迭代法的结束条件例

：求方程在[0,0.5]内的根，精确到10-5。2024/1/1631.牛顿法取在x0

做一阶Taylor展开将看成高阶小量，那么有：每一步迭代都有

，而且，那么的根。（牛顿公式），

在x0

和x

之间线性

/*linear*/2024/1/1632.牛顿法几何表示x*x0x1x2xyf(x)切线

/*tangentline*/2024/1/1633.牛顿公式实际上就是用曲线在点处的切线与轴的交点作为曲线与轴交点的近似2024/1/1634.牛顿法例题例用牛顿法求解方程在附近的根解：将方程转化为等价方程令，那么牛顿迭代公式为2024/1/1635.，迭代结果如下表取初值012340.50.57102040.56715550.56714330.5671432

可见，牛顿公式的收敛速度是相当快的。2024/1/1636.牛顿法的收敛性对方程f(x)=0，假设存在区间[a,b]，使f(x)在[a,b]上连续；(2)f(a)f(b)<0；在整个[a,b]上，f(x)0；在整个[a,b]上f不变号选取x0[a,b]使得f(x0)f(x0)>0；那么Newton’sMethod产生的序列{xk}收敛到f(x)=0在[a,b]上的唯一实根。2024/1/1637.牛顿法收敛性示意图2024/1/1638.注：Newton法的收敛性依赖于x0

的选取。x*x0

x0

x02024/1/1639.§Newton-RaphsonMethod下山法/*DescentMethod*/

——Newton’sMethod

局部微调：初值选择不当,牛顿迭代法发散,怎么办?迭代目的:f(x)=0。因此希望迭代过程中|

f(x)

|越来越小。牛顿迭代公式但|

f(xk+1)

|>|

f(xk)

|.原理：若由xk

得到的xk+1不能使|f|减小，则在xk和xk+1之间找一个更好的点，使得。xkxk+1注：0<l1，l称为“下山因子〞=1时就是Newton’sMethod公式。当=1代入效果不好时，将减半计算。.牛顿下山法应用举例计算f(x)

=x3-x-1=0在[0,2]之间的实根迭代公式取初值x0=0.6，得：绝对值较小新的迭代值 f(0.6)

=-1.384 f(17.9)

=5716.4l=0.5 x1=9.25 f(x1)

=781.20l=0.25 x1=4.925 f(x1)

=113.53l=0.125 x1=2.7625 f(x1)

=17.319l=0.0625 x1=1.68125 f(x1)

=2.0710l=0.03125 x1=1.140625 f(x1)

=-0.65664.§Newton-RaphsonMethod

求复根/*FindingComplexRoots*/

——

Newton公式中的自变量可以是复数记z=x+iy,z0

为初值，同样有设代入公式，令实、虚部对应相等，可得.牛顿法优缺点

Newton法具有收敛快，稳定性好，精度高等优点，是求解非线性方程的有效方法之一。但它每次迭代均需计算函数值与导数值，故计算量较大。而且当导数值提供有困难时，Newton法无法进行。2024/1/1644.弦割法弦割法迭代格式

在牛顿迭代格式中，将曲线

上点的切线斜率

，改为其上两点连线(弦)的斜率2024/1/1645.弦

割

法

几

何

表

示x0Xx1

x2

x3YP0P2P1割线

/*secantline*/2024/1/1646.x0x1切线

/*tangentline*/割线

/*secantline*/收敛比Newton’sMethod慢，且对初值要求同样高。.例题分析用弦割法求方程在附近的根〔〕解：取由迭代公式求得00.510.620.567540.0324630.56715–0.0003640.56714–0.00001故，满足精度要求．2024/1/1648.迭代过程的收敛速度

设由某方法确定的序列收敛于方程的根，如果存在正实数p，使得 〔C为非零常数〕定义：那么称序列收敛于x*的收敛速度是p阶的，或称该方法具有p阶敛速。2024/1/1649.当p=1且0<C<1时，称该方法为线性〔一次〕收敛；当p>1时，称方法为超线性收敛。当p=2时，称方法为平方〔二次〕收敛；2024/1/1650.定理设x*为x=g(x)的根，假设，且，那么xk+1=g(xk)在附近p阶收敛。证明：.简单迭代的收敛速度当简单迭代法是线性收敛.牛顿法的收敛速度2024/1/1653..

设由某方法确定的序列收敛于方程的根，〔0<C<1〕那么当k充分大时

解出x*，得2024/1/1655.Aitken〔艾特肯〕加速方法xyy=xy=g(x)x*x0P(x0,x1)x1x2P(x1,x2)比收敛得略快。.MATLAB中，提供了求解单变量方程的函数fzero(f,x0,tol)该函数采用迭代法计算函数f(x)的一个零点，迭代初值为x0当两次迭代结果小于tol时停止迭代过程。tol的缺省值是eps〔1e-4〕注意：在调用函数fzero之前，要使用m文件建立自己要计算的函数f(x)，只有定义了函数f(x)的m文件后，才能在fzero函数的参数中使用自定义函数名fzero函数.求f(x)=x-1/x+5在x0=-5和x0=1作为迭代初值时的零点。先编制一个函数文件fz.m：functionf=fz(x)f=x-1/x+5;在MATLAB命令窗口，输入命令：fzero('fz',-5)%以-5作为迭代初值fzero('fz',1)%以1作为迭代初值.>>fzero('fz',-5)ans=-5.1926>>fzero('fz',1)ans=0.1926.functiony=func11_1(x)y=4*cos(x)-x;>>fzero('func11_1',3)ans=1.2524>>fzero('func11_1',-4)ans=-3.5953>>fzero('func11_1',[-4,-3])ans=-3.5953在该区间内求解.>>fzero('sin(x)-0.1*x',6)ans=7.0682>>fzero('sin(x)-0.1*x',[2,6])ans=2.8523.Humps函数

在区间[-0.5,1.5]的解.Humps函数

>>fplot('humps',[-0.5,1.5]);holdon.>>x1=fzero('humps',-0.5)x1=-0.1316>>x2=fzero('humps',1.5)x2=1.2995>>plot([x1x2],[00],'o');holdoff.roots(p)多项式p的所有复根。例

x3+2x2-5的根>>roots([120-5])ans=-1.6209+1.1826i-1.6209-1.1826i1.2419.求解的方法很多，现成的软件更多，而且会越来越多。为什么还要学习求解的方法？“软件〞不能解决所有实际问题，常常需要“自力更生〞。.关于方程求根问题的小结二分法：f(x)连续、f(a)

f(b)<0、一个实根

简单，速度慢迭代法：|g´(x)|<1、g(x)(a,b)

原理简单、编程容易，