7非线性方程求根.ppt

Numerical Analysis 第七章 非线性方程(组)的数值解法 本章内容 本讲内容 非线性方程数值解法 非线性方程数值解法 二分法（对分法） 二分法 误差分析 不动点迭代 不动点迭代 连续性分析 解的存在唯一性 收敛性分析 收敛性分析 举例 局部收敛 收敛速度 收敛速度 Aitken 加速 Aitken 加速 Steffenson 加速 Steffenson 加速 举例 本讲内容 Newton 法 Newton 法 Newton 法 收敛性 举例 举例 牛顿法 简化的Newton法 Newton下山法 重根情形 重根情形 举例 弦截法与抛物线法 弦截法 收敛性 弦截法几何含义 抛物线法(略) 抛物线法 抛物线法 抛物线法 收敛性 例：用 Newton 法求 f(x) = xex – 1=0 的解 % Newton 迭代 clear; clc f = inline(x*exp(x)-1,x); df = inline(exp(x)*(1+x),x); n = 10; tol = 1e-6; x0 = 0.5; % 迭代初始值 for k = 1 : n x = x0 - f(x0)/df(x0); fprintf(k=%2d, x=%.7f\n,k,x); if abs(x-x0)tol, break, end x0 = x; end 例(P224)：用 Newton 法求 f(x) = x2 – C=0 的正根 解： 对任意 x00， 总有 |q|1， 即牛顿法收敛 牛顿的优点 牛顿法是目前求解非线性方程 (组) 的主要方法 至少二阶局部收敛，收敛速度较快，特别是当迭代点充分靠近精确解时。 牛顿的缺点 对重根收敛速度较慢（线性收敛） 对初值的选取很敏感，要求初值相当接近真解 先用其它算法获取一个近似解，然后使用牛顿法 需要求导数！ 线性收敛 简化的 Newton 法 基本思想：用 f’(x0) 替代所有的 f’(xk) 下山因子的取法： 从 ?=1 开始，逐次减半，直到满足下降条件 基本思想：要求每一步迭代满足下降条件 具体做法：加下山因子 ? Newton下山法 保证全局收敛 且 解法一：直接使用 Newton 法 线性收敛 解法二：改进的 Newton 法 二阶收敛 缺点：需要知道 m 的值 重根情形 令 x* 是 ? (x)=0 的单重根 解法三：用 Newton 法解 ? (x) = 0 迭代格式： 例：求 x4 - 4x2 ＋ 4=0 的二重根 (1) 普通 Newton 法 (2) 改进的 Newton 法 (3) 用 Newton 法解 ? (x) = 0 % 重根 clear; clc f = inline(x^4 -4*x^2 + 4,x); g1 = inline(x-(x^2-2)/(4*x),x); g2 = inline(x-(x^2-2)/(2*x),x); g3 = inline(x-x*(x^2-2)/(x^2+2),x); fprintf(True solution: x=%.7f\n,sqrt(2)); n = 10; x0 = 1.5; % 迭代初始值 x1 = x0; x2 = x0; x3 = x0; for k = 1 : n x1 = g1(x1); x2 = g2(x2); x3 = g3(x3); fprintf(k=%2d, x1=%.7f, x2=%.7f, x3=%.7f\n,k,x1,x2,x3); end 弦截法与抛物线法 目的：避免计算 Newton 法中的导数，且具有较高的收敛性（超线性收敛） 弦截法（割线法）：用差商代替微商 抛物线法：用二次多项式近似 f(x) 弦截法迭代格式： k = 1, 2, 3, . . . 注：弦截法需要提供两个迭代初始值 定理：设 x* 是 f(x) 的零点， f(x) 在 x* 的某邻域 U(x,?) 内有二阶连续导数，且 f’(x)?0，若初值 x0，x1 ?U(x,?)，则当 U(x,?) 充分小时，弦截法具有 p 阶收敛性，其中 x y x* xk-1 xk xk+1 基本思想： 用二次曲线与 x 轴的交点作为 x* 的近似值 抛物线法 y xk-2 xk-1 xk xk+1 * * 数值分析 非线性方程求解 二分法 不动点迭代法及其加速 牛顿法、弦截法、抛物线法 求根问题的敏感性与多项式的零点 非线性方程组的数值求解 迭代格式 加速算法 收敛性 非线性方程求解介绍 二分法及其收敛性 不动点迭代及其加速 考虑方程 若 f(x) 是一次多项式，则称为线性方程；