非线性方程组的数值解法——牛顿法、弦切法.ppt

第七章非线性方程(组)的数值解法计算方法 Newton 法 弦截法、抛物线法1本讲内容n Newton 法及其收敛性n 牛顿下山法n 弦截法与抛物线法2Newton 法q 基本思想将非线性方程线性化l 设 xk 是 f (x)=0 的近似根，将 f(x) 在 xk 处 Taylor 展开令：条件： f(x) 03Newton 法xyx*xkxk+14Newton 法算法 ：( Newton 法 )(1) 任取迭代初始值 x0(2) 对 k = 1, 2, . , maxit，计算判断收敛性，若收敛，则停止计算，输出近似解5收敛性 k = 0, 1, 2, . . . l 迭代函数牛顿法至少二阶局部收敛6举例例：用 Newton 法求 f(x) = xex 1=0 的解ex75.m7举例例：用 Newton 法求 f(x) = x2 C=0 的正根解：对任意 x00，总有 |q|1，即牛顿法收敛8牛顿法q 牛顿的优点牛顿法是目前求解非线性方程 (组) 的主要方法至少二阶局部收敛，收敛速度较快，特别是当迭代点充分靠近精确解时q 牛顿的缺点l 对重根收敛速度较慢（线性收敛）l 对初值的选取很敏感，要求初值相当接近真解先用其它算法获取一个近似解，然后使用牛顿法l 需要求导数！9简化的Newton法线性收敛简化的 Newton 法l 基本思想：用 f(x0) 替代所有的 f(xk)10Newton下山法l 下山因子的取法： 从 =1 开始，逐次减半，直到满足下降条件l 基本思想：要求每一步迭代满足下降条件l 具体做法：加下山因子 Newton下山法保证全局收敛11重根情形且l 解法一：直接使用 Newton 法线性收敛l 解法二：改进的 Newton 法二阶收敛缺点：需要知道 m 的值重根情形12重根情形令x* 是 (x)=0 的单重根l 解法三：用 Newton 法解 (x) = 0迭代格式：13举例例：求 x4 - 4x2 4=0 的二重根 (1) 普通 Newton 法ex76.m(2) 改进的 Newton 法(3) 用 Newton 法解 (x) = 014弦截法与抛物线法弦截法与抛物线法l 目的：避免计算 Newton 法中的导数，且具有较高的收敛性（超线性收敛）l 弦截法（割线法）：用差商代替微商l 抛物线法：用二次多项式近似 f(x)15弦截法l 弦截法迭代格式：k = 1, 2, 3, . . .l 注：弦截法需要提供两个迭代初始值16收敛性定理：设 x* 是 f(x) 的零点， f(x) 在 x* 的某邻域 U(x,) 内有二阶连续导数，且 f(x)0，若初值 x0，x1 U(x,)，则当 U(x,) 充分小时，弦截法具有 p 阶收敛性，其中17弦截法几何含义xyx*xk-1xkxk+118抛物线法l 基本思想： 用二次曲线与 x 轴的交点作为 x* 的近似值 抛物线法19抛物线法yxk-2xk-1xkxk+120抛物线法l 计算过程二次曲线方程 (三点 Newton 插值多项式)l 问题：p2(x) 与 x 轴有两个交点，取哪个点？解决方法：取靠近 xk 的那个点!21抛物线法取靠近 xk 的那个点22收敛性在一定条件下可以证明：抛物线法的收敛阶为 23作业l 教材 238 页，习题 7l 教材 239 页，习题 9、1524。