第7章非线性方程求根

数值分析第7章非线性方程求根第7章非线性方程求根方程求根与二分法不动点迭代法及其收敛性迭代收敛的加速方法牛顿法弦截法与抛物线法第七章非线性方程求根/*SolutionsofNonlinearEquations

*/§1多项式基础/*Polynomials*/（自习）§2二分法/*BisectionMethod*/求

f(x)=0的根原理：若f

C[a,b]，且f(a)·f(b)<0，则f

在(a,b)上必有一根。§2BisectionMethodabx1x2abWhentostop?或不能保证

x

的精度x*2xx*§2BisectionMethod误差分析：第1步产生的有误差第k步产生的xk

有误差对于给定的精度

,可估计二分法所需的步数k：①简单;②对f(x)

要求不高(只要连续即可).①无法求复根及偶重根②收敛慢注：用二分法求根，最好先给出f(x)

草图以确定根的大概位置。或用搜索程序，将[a,b]分为若干小区间，对每一个满足f(ak)·f(bk)<0的区间调用二分法程序，可找出区间[a,b]内的多个根，且不必要求f(a)·f(b)<0。§3迭代法/*Fixed-PointIteration

*/f(x)=0x=g(x)等价变换f(x)的根g(x)的不动点思路从一个初值x0

出发，计算x1=g(x0),x2=g(x1),…,xk+1=g(xk),…若收敛，即存在x*使得

，且g连续，则由可知x*=g(x*)，即x*是g的不动点，也就是f

的根。Sobasicallywearedone!Ican’tbelieveit’ssosimple!What’stheproblem?Ohyeah?Whotellsyouthatthemethodisconvergent?§3Fixed-PointIterationxyy=xxyy=xxyy=xxyy=xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1§3Fixed-PointIteration定理考虑方程x=g(x),g(x)C[a,b],若(I)当x[a,b]时，g(x)[a,b]；(II)0L<1使得

|g’(x)|L<1对x[a,b]成立。则任取x0[a,b]，由xk+1=g(xk)得到的序列收敛于g(x)在[a,b]上的唯一不动点。并且有误差估计式：(k=1,2,…)且存在极限k§3Fixed-PointIteration证明：①g(x)在[a,b]上存在不动点？令有根②不动点唯一？反证：若不然，设还有，则在和之间。而③当k

时，

xk收敛到x*？§3Fixed-PointIteration④⑤⑥可用来控制收敛精度L越收敛越快小注：定理条件非必要条件，可将[a,b]缩小，定义局部收敛性：若在x*的某领域B={x||xx*|}有gC1[a,b]且|g’(x*)|<1，则由x0B开始的迭代收敛。即调整初值可得到收敛的结果。§3Fixed-PointIteration改进、加速收敛/*acceleratingconvergence*/

待定参数法：若

|g’(x)|1，则将x=g(x)等价地改造为求K，使得例：求在(1,2)的实根。如果用进行迭代，则在(1,2)中有现令希望，即在(1,2)上可取任意，例如K=0.5，则对应即产生收敛序列。迭代收敛的加速方法

对于收敛的迭代过程，只要迭代足够多次，就可以使结果达到任意的精度。但是收敛缓慢计算量变大Aitken加速方法Steffensen加速方法

Aitken加速：§3Fixed-PointIterationxyy=xy=g(x)x*x0P(x0,x1)x1x2P(x1,x2)§4牛顿法/*Newton-RaphsonMethod*/原理：将非线性方程线性化

——Taylor展开/*Taylor’sexpansion*/取x0

x*，将f(x)在x0

做一阶Taylor展开:，在x0

和x

之间。将(x*

x0)2

看成高阶小量，则有：线性

/*linear*/xyx*x0只要f

C1，每一步迭代都有f’(xk)0，而且，则

x*就是f

的根。§4Newton-RaphsonMethod定理

（收敛的充分条件）设f

C2[a,b]，若(1)f(a)f(b)<0；(2)在整个[a,b]上f”不变号且f’(x)0；(3)选取x0

[a,b]使得f(x0)f”(x0)>0；则Newton’sMethod产生的序列{xk}收敛到f(x)在[a,b]的唯一根。有根根唯一产生的序列单调有界，保证收敛。定理

（局部收敛性）设f

C2[a,b]，若x*

为f(x)在[a,b]上的根，且f’(x*)0，则存在x*的邻域使得任取初值，Newton’sMethod产生的序列{xk}收敛到x*，且满足§4Newton-RaphsonMethod证明：Newton’sMethod事实上是一种特殊的不动点迭代其中，则收敛由Taylor展开：只要f’(x*)0，则令可得结论。在单根

/*simpleroot*/

附近收敛快§4Newton-RaphsonMethod注：Newton’sMethod收敛性依赖于x0

的选取。x*x0x0x0§4Newton-RaphsonMethod改进与推广/*improvementandgeneralization*/重根/*multipleroot*/

加速收敛法：Q1:

若，Newton’sMethod是否仍收敛？设x*是f

的n

重根，则：且。因为Newton’sMethod事实上是一种特殊的不动点迭代，其中，则A1:

有局部收敛性，但重数n

越高，收敛越慢。Q2:

如何加速重根的收敛？A2:

将求

f

的重根转化为求另一函数的单根。令，则f

的重根=

的单根。§4Newton-RaphsonMethod正割法/*SecantMethod*/

：Newton’sMethod

一步要计算f

和f’，相当于2个函数值，比较费时。现用f

的值近似f’，可少算一个函数值。x0x1切线

/*tangentline*/割线

/*secantline*/切线斜率

割线斜率需要2个初值x0

和x1。收敛比Newton’sMethod慢，且对初值要求同样高。§4Newton-RaphsonMethod下山法/*DescentMethod*/

——Newton’sMethod

局部微调：原理：若由xk

得到的xk+1不能使|f|减小，则在xk和xk+1之间找一个更好的点，使得。xkxk+1注：=1时就是Newton’sMethod公式。当=1代入效果不好时，将减半计算。§5迭代法的收敛阶

/*OrderofConvergence*/定义

设迭代xk+1=g(xk)收敛到g(x)的不动点x*。设ek=xk

x*，若，则称该迭代为p

阶收敛，其中C

称为渐进误差常数。/*{xk}convergesto

x*oforder

p,withasymptoticerrorconstant

C>0*/一般Fixed-PointIteration有，称为线性收敛

/*linearconvergence*/，这时p=1，0<C<1。注：超线性收敛不一定有p>1。例如xn

=1/nn超线性收敛到0，但对任何p>1都没有

p

阶收敛。Aitken加速有。称为超线性收敛

/*superlinearconvergence*/。§5OrderofConvergenceSteffensen加速有p=2，条件是，称为平方收敛

/*quadraticconvergence*/。Newton’sMethod有，只要，就有p

2。重根是线性收敛的。Q:

如何实际确定收敛阶和渐进误差常数？定理

设x*

为x=g(x)的不动点，若，p2；，且，则xk+1=g(xk)在内p

阶收敛。证明：x*k

CThisisaonelineproof...ifwestartsufficientlyfartotheleft.§6劈因子法

/*SplittingMetho