数值计算方法2

第二章非线性方程的数值解法2.1二分法2.2一般迭代法2.3牛顿迭代法2.4弦截法（1）确定初始含根区间数值计算方法主要分为两大类。第一类是区间收缩法。

（2）收缩含根区间第二类是迭代法。

（1）选定根的初始近似值（2）按某种原则生成收敛于根的近似点列2.1二分法

基本假设:

2.1.1二分法的计算步骤

常用终止原则为:2.1.2二分法的收敛性与事前误差估计

所以，二分法总是收敛的例2.1试用二分法求

的一个正根，使误差小于10-3故可取初始区间解2.1.3

二分法评述优点：简单可靠，易于编程实现，它对函数要求低，适用于的奇数重根情形。缺点：不能直接用于求偶重根，不能用于求复根，也难以向方程组推广使用，收敛速度慢。2.2一般迭代法迭代法的算法思想为：(1)把（2-2）等价变换为如下形式(2)建立迭代格式或更一般地建立迭代格式(3)适当选取初始值，递推计算出所需的解。2.2.1迭代法的算法思想

2.2.2迭代法的收敛性则称在内李普希兹连续。定义2.1

设在某个区间内，函数满足下述李普希兹条件：则在内李普希兹连续。命题2.1

若在闭区间内连续且命题得证。证定理2.1

设x*=g(x*),g(x)在闭区间：内李普希兹连续，则对任何初值由迭代格式xk+1=g(xk)计算得到的解序列收敛于x*(这时我们称迭代格式xk+1=g(xk)在x*

的邻域上局部收敛）。（1）首先用数学归纳法证明：由假设知又设，则综上，由归纳法原理知，结论成立。

证因此，，定理得证。反设存在矛盾。所以结论成立。2)迭代函数在x*

附近李普希兹连续从而收敛的迭代格式统称为皮卡（Picard）迭代

(2)由（1）的结论和g(x)在内李普希兹连续的假设，可递推得到

注

1)g(x)在内李普希兹连续的条件保证了x*

为f(x)=0在内的唯一根。

证推论

设x*=g(x*)，若g(x)在x*

附近连续可微且，则迭代格式xk+1=g(xk)在x*

附近局部收敛。

注由于x*

事先未知，故实际应用时，代之以近似判则。但需注意，这实际上是假设了x0充分接近x*，若x0

离x*

较远，迭代格式可能不收敛。

定理2.2

（非局部收敛定理）如果在上连续可微且以下条件满足：注

虽然定理2.1的条件是充分条件，但其条件并不很强，实际上，我们易证如下命题。命题2.2

若在区间内，则对任何，迭代格式不收敛。

2.2.3迭代法的误差估计

故对正整数p，有

（2）事后误差估计

由此，对给定的精度可进行(1)事前误差估计简单地代之以或

例2.2试建立收敛的迭代格式求解在区间(2,3)内满足精度要求的根。

首先可简单的把等价化为由此建立迭代格式所以该迭代格式在内不收敛，不可取。为建立收敛的迭代格式，我们把等价化为从而建立迭代格式解易知在x>0时g(x)单调增，故有2<g(2)<g(x)<g(3)<3故由定理2.2得：任取x0

[2,3]，该迭代格式收敛。取x0=2计算，结果见表2-2（书17页）。

2.2.4迭代法的收敛速度与加速收敛技巧

则称该迭代格式是p阶收敛的。特别地，p=1时称为线性收敛，1<p<2时称为超线性收敛，p=2

时称为平方收敛。

定义2.2

设迭代格式的解序列收敛于的根，如果迭代误差当时满足渐近关系式对于线性收敛的计算格式，可采用以下介绍的埃特肯（Aitken）加速技巧来提高收敛速度。设序列线性收敛于，即有，则近似地有两式相除得解得把埃特肯加速技巧应用于单步迭代法便构成了Steffensen算法。据此，我们可取修正值作为的新近似值以提高精度。这一技巧便称为埃特肯加速技巧。

例2.3试用Steffensen算法求解在区间（2，3）内满足精度要求的根。

对例2.2的迭代格式取用算法计算，结果见表2-3。解

2.3牛顿迭代法

2.3.1牛顿迭代公式的构造

设f(x)在其零点附近连续可微，已知为的第k次近似值，则取的根作为的第k+1次近似值其迭代函数为牛顿迭代法几何意义：过点作函数y=f(x)的切线l：以切线l与x轴的交点作为的新近似值

2.3.2牛顿迭代法的收敛性与收敛速度

定理2.3给定f(x)=0，如果在根附近f(x)二阶连续，且为f(x)=0的单根，则牛顿迭代法在附近至少是平方收敛的。首先证明牛顿迭代法的收敛性：

而单根条件保证了因此由定理2.1知，牛顿迭代法局部收敛。证其次证明牛顿迭代法的收敛速度：整理得可见，当时，牛顿迭代法为平方收敛；当时，牛顿迭代法超平方收敛。例2.4试用牛顿迭代法求解在区间(2,3)内满足精度要求的根。相应于该方程的牛顿迭代公式为取x0=2，计算结果见表2-4。解牛顿迭代法评述

优点：是收敛速度比较快

缺点：(1)局部收敛，对初始值的要求比较高。为解决这一问题，可采用二分法来提供足够“好”的近似值作为迭代初值，或通过增加“下山”限制来放宽对初值的要求，即把牛顿迭代法修改为其中的选取使得（这称为“下山”限制）。该方法称为牛顿下山法。（2）当为重根时，牛顿迭代法仅仅线性收敛。（3）由于涉及的计算，导致了对函数的要求高，并增加了每一迭代步的计算量，这在一定程度上减弱了该迭代法收敛快的优越性，而且在向非线性方程组推广时，使计算量和对函数的要求大大增加。因此，人们致力于研究建立牛顿迭代法的修改格式以回避对函数导数值的计算。本章仅对非线性方程介绍一种较为有效的修改算法——弦截法。

2.4弦截法

计算思想是：若已知x*

的两个近似值xk

和xk-1，则以f(x)在xk

与xk-1

之间的平均变化率(差商)近似代替，据此把牛顿迭代法修改为几何意义是以过和两点做曲线的弦线l：以l与x轴的交点作为的新近似值（如图2-3所示）弦截法

定理2.4设f(x)在其零点x*

的邻域内二阶连续，且对，则对，相应的弦截法是阶收敛的。该定理说明弦截法是超线性收敛的算法，也是局部收敛的方法，其迭代初始值亦可用二分法提供。

例2.5试用弦截法求解在区间内满足精度要求的根。

相应于该方程的弦截法公式为取计算，结果见表2-5。解

例2.6试讨论函数方程的根的分布情况，