2非线性方程(组)的数值解法课案.pptx

1 第二章非线性方程(组)的数值解法 数值分析 —— 方程求根与二分法 2 本章内容 非线性方程求解 二分法 不动点迭代法及其加速 牛顿法、弦截法、抛物线法 求根问题的敏感性与多项式的零点 非线性方程组的数值求解 3 本讲内容 迭代格式 加速算法 收敛性 非线性方程求解介绍 二分法及其收敛性 不动点迭代及其加速 4 非线性方程数值解法 考虑方程 若 f(x) 是一次多项式，则称为线性方程； 否则称为非线性方程 f (x) = 0 若 f(x) = a0 + a1x + . . . + anxn ，则称为代数方程 n=1, 2, 3, 4 时有相应的求根公式，n  5 时不存在求根公式 非线性方程可能有(无穷)多个解，求解时必须强调求解区间 非线性方程一般没有直接解法，通常都使用迭代算法求解 5 非线性方程数值解法 几个基本概念 实根与复根 根的重数 f(x)=(x–x*)m · g(x) 且 g(x*)  0, 则 x*为 f(x)=0 的 m 重根 有根区间：[a, b] 上存在 f (x) = 0 的一个实根 研究内容：在有根的前提下求出方程的近似根 6 二分法（对分法） 基本思想 将有根区间进行对分，找出根所在的小区间，然后再对该小区间对分，依次类推，直到有根区间的长度满足给定的精度为止 二分法 算法 ：(二分法 ) (1) 计算 f(a)，f(b)，若 f(a) f(b) 0 ，则停止计算 (2) 对 k = 1, 2, ... , maxit 计算 f(x)，其中 若 |f(x)| 或 b-a，停止计算，输出近似解 x 若 f(a) · f(x) 0，则令 b = x; 否则令 a = x x1 x2 a b x* 2 8 优点：简单易用，总是收敛 缺点：收敛速度慢，不能求复根和偶数重根 总结：一般用来计算解的一个粗糙估计 9 误差分析 记 a1 = a, b1 = b, 第 k 步的有根区间为 [ak, bk] 迭代法是数值计算中的一类重要方法，应用广泛。 迭代法是一种重要的逐次逼近方法。这种方法 用某个固定公式反复校正根的近似值，使之逐步精 确化，最后得到满足精度要求的结果。 §2 迭代法 , …, , ….     ( I ) 当 x[a, b] 时， (x)[a, b]； ( II )  0  L 1 使得 则任取 x0[a, b]，由 xk+1 = (xk) 得到的序列 收敛于 (x) 在[a, b]上的唯一不动点。并且有误差估计式： ( k = 1, 2, … ) k 定理1 ② 不动点唯一 ③ 当k   时， xk 收敛到 x* ？ 两个迭代值组合的方法： 三个迭代值组合的方法： P(x0, y0) P(y0, z0) §3 牛顿法 引入：将非线性方程线性化 —— Taylor 展开 取 x0  x*，将 f (x)在 x0 做一阶Taylor展开: 将 (x*  x0)2 看成高阶小量，则有： （ f C1，f ’(x*)  0） 单根情形 定理1 （收敛的充分条件）设 f C2[a, b]，若 f (a) f (b) 0； 在整个[a, b]上 f ”不变号且 f ’(x)  0； (3) 选取 x0  [a, b] 使得 f (x0) f ”(x0) 0； 则Newton’s Method产生的序列{ xk } 收敛到f (x) 在 [a, b] 的唯一根。 定理2 重根情形 求复根 —— Newton 公式中的自变量可以是复数