第二章 非线性方程的数值解法 非线性方程 n次代数方程 : 超越方程: n=1,2 n=3,4 n≥5 求根公式 查数学手册 ? 如

Presentation on theme: "第二章 非线性方程的数值解法 非线性方程 n次代数方程 : 超越方程: n=1,2 n=3,4 n≥5 求根公式 查数学手册 ? 如"— Presentation transcript:

1 第二章 非线性方程的数值解法 非线性方程 n次代数方程 : 超越方程: n=1,2 n=3,4 n≥5 求根公式 查数学手册 ? 如
第二章 非线性方程的数值解法 n次代数方程 : n=1,2 n=3,4 n≥5 求根公式 查数学手册 ? 超越方程: 非线性方程 如 无穷多个解

2 非线性方程 方程的根 函数f(x)的零点 根的存在性 根的隔离：找出有根区间 非线性方程求根 根的精确化：算法，满足一定精度的 近似根

3 则至少有一个数 使得 ，若同时 的一阶导数 在 内存在且保持定号，即 (或 )则这样的 在 内唯一。 定 理:
求方程 的几何意义 a b x* 如果函数 在 上连续，且 则至少有一个数 使得 ，若同时 的一阶导数 在 内存在且保持定号，即 (或 )则这样的 在 内唯一。 定 理:

4 例 求方程的根 解： （1）根的存在性 （2）有根区间 (2,3), (3,4), (5,6) f(a) f(b)<0 （3）确定算法

5 非线性方程求根的算法： 二分法 简单迭代法 牛顿迭代法 弦割法 抛物线法 ……

6 §1 二分法 原理：若 f C[a, b]，且 f (a) · f (b) < 0，则 f 在 (a, b) 上至少有一实根。
§1 二分法 原理：若 f C[a, b]，且 f (a) · f (b) < 0，则 f 在 (a, b) 上至少有一实根。 基本思想：逐步将区间分半，通过判别区间端点函数值的符号，进一步搜索有根区间，将有根区间缩小到充分小，从而求 出满足给定精度的根 的近似值。 以此类推

7 终止法则？ When to stop? x* b a a x1 x2 b 近似根序列： … …

8 停止！ 二分次数的计算：

9 二分法的计算步骤： 1、准备 计算f(a)，f(b) 2、二分 计算 3、判断 反复执行步骤2、3，直到满足精度要求！

10 例 用二分法求方程 在区间 上的根，误差限为 ，问至少需对分多少次？
例 用二分法求方程 在区间 上的根，误差限为 ，问至少需对分多少次？ 解：

11 例 用二分法求方程 在区间 上的根，要求误差不超过 。
例 用二分法求方程 在区间 上的根，要求误差不超过 。 解： k ak bk f(ak) f(bk) xk f(xk) |xk-xk-1| 1 1.5 -1 0.875 1.25 -0.297 1.375 0.225 0.125 2 1.313 -0.052 0.062 3 1.344 0.083 0.031 4 1.328 0.015 0.016 5 1.320 -0.019 0.008

12 ①计算过程简单； 优点 ② 对f (x)要求不高(只要连续即可)。 ①无法求复根及偶重根； 缺点 ②收敛速度慢。
注：用二分法求根，最好先给出 f (x) 草图以确定根的大概位置。或用搜索程序，将[a, b]分为若干小区间，对每一个满足 f (ak)·f (bk) < 0 的区间调用二分法程序，可找出区间[a, b]内的多个根，且不必要求 f (a)·f (b) < 0 。

13 §2 迭代法 2.1 简单迭代法 f (x) = 0 x = g (x) 迭代函数 迭代公式 初始值 收敛 迭代法收敛 迭代序列 … 发散
§2 迭代法 2.1 简单迭代法 等价变换 f (x) = 0 x = g (x) 迭代函数 迭代公式 初始值 收敛 迭代法收敛 迭代序列 … 发散 迭代法发散 不动点迭代法

14 例： 用迭代法求方程 在 的根。 下面选取4种迭代格式： 1、 即 2、 即 3、 即 4、 即

15 取 计算结果如下： 法4 法1 法2 法3 发散 发散 收敛 收敛

16     2.2 迭代法的几何意义 x y y = x x y y = x x0 p0 p1 y=g(x) y=g(x) x* x1

17 2.3 迭代法收敛的充分条件 定理1 若迭代函数 g(x)满足如下条件： ( I )当 x[a, b] 时， g(x)[a, b]；
( II )  0  L < 1 使得 对  x[a, b] 成立。

18 例： 用迭代法求方程 在 的根。 1、 不满足条件( I ) 发散 4、 满足条件(I) 满足条件(II) 收敛 3、 2、
用迭代法求方程 在 的根。 1、 不满足条件( I ) 发散 4、 满足条件(I) 满足条件(II) 收敛 3、 2、 迭代函数g(x)比较复杂,或有根区间太大时，按定理1判断收敛比较困难

19 定理2 局部收敛：若方程 x=g(x) 有实根x* ，如果存在x* 的邻域R： ，对任意x0，迭代法产生的序列均收敛到x* ，则
称该迭代法局部收敛。 定理2 若存在区间 ，使 ( I ) 方程 在 内有实根x*； ( II ) 在 内连续，且 。 则迭代法 在x*附近具有局部收敛性。

20 ①计算过程简单； 优点 ② 易在计算机上实现。 ①迭代函数形式不一，且不一定收敛； 缺点 ②收敛速度慢。
注：用迭代法求根，最好先给出 f (x) 草图以确定根的大概位置，再选定初始值，并选择在初始值附近具有局部收敛的迭代函数。

21 §3 Newton迭代法 3.1 Newton迭代公式其几何意义 基本思想： 非线性函数 线性化 非线性方程 线性方程
取 x0  x*，将 f (x)在 x0 作Taylor展开: ， 在 x0 和 x 之间

22 将 (x*  x0)2 看成高阶小量，则有： y x x* 与x轴交点的横坐标 只要 f C1，每一步迭代都有

23 无开方运算。 例： 写出求 的Newton迭代格式； 写出求 的Newton迭代格式。要求公式中 解： 等价于求方程 的正根

24 解法一： 等价于求方程 的正根  等价于求方程 的正根 解法二： 

25 Newton迭代法的步骤： ① 选初始值 ，计算 ，k=1； ② 计算 ； 是：终止， ③ 判断 否 ④ ④ k=k+1，计算 ，回②。

26 例：求 的近似值，要求精确到 。 解： 分别选取初始迭代值 ，计算结果如下表所示：

27 则Newton迭代法产生的序列{ xk } 收敛于方程的根 。 定理3
（收敛的充分条件）对方程f (x) =0 且，若 在整个[a, b]上存在方程的单根x* ； (3) f C2[a, b] 。 则Newton迭代法产生的序列{ xk } 收敛于方程的根 。 定理3

28 定理4 （收敛的另一充分条件）对方程 f (x) =0 且，若 在[a, b]上连续； (2) f (a) f (b) < 0；
(3) ； (4) 在[a, b]上不变号（保号）； (5) 则对 Newton’s Method产生的序列{ xk } 收敛于方程 f (x) =0 在[a, b]内的唯一实根 。 选取 x0  [a, b] 使得 。 曲线光滑、连续 有根 单调性 曲线凹凸性不变

29 注：Newton迭代法的收敛性依赖于x0 的选取。
   x0 x0 x0 x*

30 例： 用Newton迭代法求方程 的根，要求精确到 。
解： 根据定理4判断迭代法是否收敛 （2） （1） cos x 连续 （3） （4） （5）选取初始迭代值x0=1 故迭代过程必收敛

31 Newton迭代公式 故x4= 为满足精度要求的近似根。

32 3.3 弦割法 切线斜率　　割线斜率 需要2个初值 x0 和 x1。

33 例： 用弦割法求方程 的根，要求精确到 。 解： 取初始迭代值 x≈

34 简化牛顿法

35 §4 迭代法的收敛阶与加速收敛方法 4.1 收敛阶 设序列 收敛到 ， ，若存在实数 及常 数 ，使 ,则称序列 是 阶收敛的，
§4 迭代法的收敛阶与加速收敛方法 4.1 收敛阶 设序列 收敛到 ， ，若存在实数 及常 数 ，使 ,则称序列 是 阶收敛的， 称为渐近误差常数。 且 时为线性收敛 为超线性收敛 时为平方或二次收敛 注: p 的大小反映了迭代法收敛的快慢，是收敛速度的一 种度量，也是衡量迭代法优劣的一个指标 。

36 迭代法p阶收敛的充分条件： 设迭代法的迭代函数 的高阶导数 在不动点 的邻域里连续，则迭代法是 阶收敛的条件是 定理5

37 证明： 由Taylor公式： 取极限得 即迭代法 是 p阶收敛的。

38 例：比较简单迭代法与Newton迭代法的收敛速度。
简单迭代法线性收敛

39 Newton迭代法 ①单根情形 定理5 二阶收敛

40 ②重根情形 线性收敛

41 若取 迭代格式 二阶收敛 (须已知重数m)

42 如果 是 的m重根 令 Newton迭代法 是 的单根 二阶收敛 迭代格式

43 4.2 迭代收敛的加速方法 变化不大

44 解得 Steffensen加速算法 Steffensen算法

45 设 是根 的某个近似值，用迭代公式校正一次得
Aitken(埃特金)加速收敛方法 设 是根 的某个近似值，用迭代公式校正一次得 x * x 由微分中值定理，有 *), )( ( *) ) * 1 x - = j 其中 介于 与 之间. x * x x 假定 改变不大，近似地取某个近似值 ，则有 ) ( x j L 若将校正值 再校正一次，又得 ) ( 1 x j = 由于 *), ( * 1 2 x L -

46 将它与（3.1）式联立，消去未知的 ，有 * 1 2 x - 解得 Aitken加速算法 Aitken算法

47 例：求方程 在[3,4]中的解，要求精确到10-4。 ① 二分法 所以，要二分13次才能 达到精度要求

48 ② 简单迭代法 取初值x0=3.5 定理2 收敛

49 ③Newton迭代法 取初值x0=3.5

50 ④弦割法 取初值x0=3， x1=4

51 ⑤简化Newton法 取初值x0=3.5

52 ⑥Aitken加速法

53 ①二分法 次 ②简单迭代法 次 ③Newton迭代法 次 ④弦割法 次 ⑤简化Newton法 次 ⑥Aitken加速法 次

54 求根方法 优点 缺点 二分法 原理简单、编程方便 收敛速度慢，不能求重根 简单迭代法 不一定收敛、收敛速度慢 Newton迭代法 收敛速度快、能求重根和复根 要求函数导数，对初值有要求 弦割法 不需求函数导数 要两个初始值，且收敛较慢 简化Newton法 不需次次求函数导数 收敛较慢 Aitken加速法 收敛速度快 有可能失效