非线性方程的数值解法

1、第二章 非线性方程的数值解法 /* Numerical Solutions of Nonlinear Equations*/本章主要内容：1、二分法2、不动点迭代的构造及其收敛性判定3、Newton和Steffensen迭代4、弦割法（割线法）与抛物线法历史背景 代数方程的求根问题是一个古老的数学问题。理论上， 次代数方程在复数域内一定有 个根(考虑重数)。早在16世纪就找到了三次、四次方程的求根公式，但直到19世纪才证明大于等于5次的一般代数方程式不能用代数公式求解，而对于超越方程就复杂的多，如果有解，其解可能是一个或几个，也可能是无穷多个。一般也不存在根的解析表达式。因此需要研究数值方法求

2、得满足一定精度要求的根的近似解。 求方程 几何意义基本定理 如果函数 在 上连续，且则至少有一个数 使得 ，若同时 的一阶导数 在 内存在且保持定号，即 (或 )则这样的 在 内唯一。 abx*1 二分法 /* Bisection Method */原理：若 f Ca, b，且 f (a) f (b) 0，则 f 在 (a, b) 上至少有一实根。基本思想：逐步将区间分半，通过判别区间端点函数值的符号，进一步搜索有根区间，将有根区间缩小到充分小，从而求 出满足给定精度的根 的近似值。以此类推终止法则？abx1x2When to stop?或不能保证 x 的精度x*2xx* 二分法算法给定区间a

3、,b ，求f(x)=0 在该区间上的根x.输入: a和b; 容许误差 TOL; 最大对分次数 Nmax.输出: 近似根 x.Step 1 Set k = 1;Step 2 Compute x1=(a+b)/2;Step 3 If f(x1)*f(a)0 , Set b= x1; Else Set a= x1;Step 4 Compute x2=(a+b)/2;Step 5 While ( k Nmax) do steps 6-8 Step 6 If |x1- x2 | TOL , STOP; Output the solution x= (x1+ x2 )/2. Step 7 If f(x2)

4、*f(a)0 , Set b= x2; Else Set a= x2; Step 8 x1=x2 ; Compute x2=(a+b)/2; Set k=k+1; Step 9 Output “Maximum iterations exceeded”; STOP.3、由二分法的过程可知：4、对分次数的计算公式：1、2、令解：例1：用二分法求方程 在区间 上的根，误差限为 ，问至少需对分多少次？简单; 对f (x) 要求不高(只要连续即可) .无法求复根及偶重根收敛慢 注：用二分法求根，最好先给出 f (x) 草图以确定根的大概位置。或用搜索程序，将a, b分为若干小区间，对每一个满足 f (a

5、k)f (bk) 0 的区间调用二分法程序，可找出区间a, b内的多个根，且不必要求 f (a)f (b) 0 。优点缺点2 迭代法的理论 /* Theory of Iteration Method*/f (x) = 0 x = g (x)（迭代函数）等价变换思路从一个初值 x0 出发，计算 x1 = g(x0), x2 = g(x1), , xk+1 = g(xk), 若 收敛，即存在 x* 使得 ，且 g 连续，则由 可知 x* = g(x* )，即x* 是 g 的不动点，也就是f 的根。看起来很简单，令人有点不相信，那么问题是什么呢？如何判定这种方法是收敛的呢？f (x) 的根g (x)

6、 的不动点一、不动点迭代 /*Fixed-Point Iteration*/xyy = xxyy = xxyy = xxyy = xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0 x1p1x0p0 x1p1x0p0 x1p1x0p0 x1p1几何意义例2：已知方程 在 上有一个根（正根）下面选取5种迭代格式：1、即2、即3、即4、即5、即取计算结果如下：法1法4法3法2法5Lipschitz条件成立的充分条件考虑方程 x = g(x), 若( I ) 当 xa, b 时， g(x)a, b；( II ) 0 L 1 使得 对 xa, b 成立。则任取 x0a, b，由

7、 xk+1 = g(xk) 得到的序列 收敛于g(x) 在a, b上的唯一不动点。并且有误差估计式：( k = 1, 2, )且存在极限连续时证明： g(x) 在a, b上存在不动点？令有根 不动点唯一？设还有 ，则在和之间。而 当k 时， xk 收敛到 x* ？L 越 收敛越快可用 来控制收敛精度小注：条件 ( II ) 可改为 在a, b 满足Lipschitz条件,定理结论仍然成立(定理2.2.1)。 算法: 不动点迭代给定初始近似值 x0 ，求x = g(x) 的解.输入: 初始近似值 x0; 容许误差 TOL; 最大迭代次数 Nmax.输出: 近似解 x 或失败信息.Step 1 S

8、et i = 1; x0 = 初始给定值；Step 2 While ( i Nmax) do steps 3-6Step 3 Set x = g(x0); /* 计算 xi */Step 4 If | x x0 | TOL then Output (x); /*成功*/STOP;Step 5 Set i = i +1;Step 6 Set x0 = x ; /* 更新 x0 */Step 7 Output (The method failed after Nmax iterations); /*不成功 */STOP.当 x 很大时，此处可改为二、局部收敛性 /*Local Convergenc

9、e*/（局部收敛性 ） 若存在 的不动点 的一个闭邻域 对任意的 ，由迭代法 产生的序列 均收敛于 ，则称该迭代法局部收敛。 注解:局部收敛性特点：假定解存在，且肯定存在解的一个邻域，使得对其中所有初始值，由迭代生成的序列收敛于解。半局部收敛特点：不知道解存在，但指出要从满足一定（通常很强）条件的初始值出发，保证收敛于某一（临近）解。全局（整体）收敛：肯定在全空间或至少其中一个很大的部分中，无论从何处出发，都能保证收敛于一个解。 设 为 的不动点， 在 的某邻域连续， 且 ，则迭代法(*)局部收敛。 证明：因为 在 的某邻域连续， 存在邻域即对则由定理2.2.1，迭代法(*)对 收敛，即局部收

10、敛.注 解：例3：已知方程 在 内存在唯一根 :（1）建立一种收敛于方程根的迭代方法，并说明收敛的理由； （2）以 为初值迭代两步计算 的近似值 。 迭代函数迭代格式当 时，故收敛。（收敛阶/*the order of Convergence*/)设序列 收敛到 ， ，若存在实数 及常数 ，使 ,则称序列 是 阶收敛的， 称为渐近误差常数。当 且 时， 称为线性收敛， 为超线性收敛， 时为平方或二次收敛.注: （1） 的大小反映了迭代法收敛的快慢，是收敛速度 的一 种度量; （2）设迭代函数 满足收敛定理的条件，则产生的序列满足 ，如果在 或 的邻域有 若取 ，必有 ，此时有 设迭代法的迭代函

11、数 的高阶导数 在不 动点 的邻域里连续，则式（*）是 阶收敛的充要条件是 且 证明：由Taylor公式：充分性取极限得必要性设迭代式（*）是 阶收敛的，则有 即且（反证法）设结论不成立则存在最小正整数 满足情形一情形二由充分性证明知，迭代式（*）是 阶收敛的即而的极限不存在与 阶收敛矛盾证明方法与情形一类似（自己练习）一、使用两个迭代值的组合方法：3 迭代收敛的加速方法 /* Accelerating Method*/本节讨论迭代法加速收敛问题，常用于线性收敛迭代法 将 x = g(x) 等价地改造为当 和 时，有相应的迭代公式为 或者 选取特殊的 ，有可能使迭代加速。 二、Steffensen(斯蒂芬森)加速迭代法：（三个迭代值组合）xyy = xy = g(x)x*x0从初值 出发，计算出在曲线 上得到两个点 用直线连接 、 两点它与 的交点设为 点的坐标为 将 视为新的初值，重复上述步骤 一般地，由 组合得到迭代式或者这个方法称为斯蒂芬森(Stef