计算方法-2

null计算计算方法Computational Method第二章 一元非线性方程的解法第二章 一元非线性方程的解法主要内容 ——**3. 迭代法 4. 牛顿迭代法 5. 弦截法 6. 埃特金迭代法1. 根的概念 2. 二分法 §2.1 根的概念§2.1 根的概念我们已经熟悉求解一元一次方程、一元二次方程以及某些特殊类型的高次代数方程或非线性方程的方法。这些方法都是代数解法，求出的根是方程的准确根。 但是，在许多实际问中遇到的方程，例如代数方程 或超越方程 等等，虽然形式简单，但却不易求得其准确根或者根的解析表达式。 为此，需要用数值方法求得满足一定精度要求的根的近似解。**§2.1 根的概念§2.1 根的概念这里，我们主要讨论一元非线性方程，即 其中，f (x)为变量 x 的非线性函数，x 可以是实数也可以是复数。本章主要讨论它的实根的数值计算问题。 若存在 x* 使得 f (x*) = 0，则称 x*为方程 f (x) = 0的根，或为函数 f (x)的零点。 若函数 f (x)可以分解为 f (x) = (x - x*)kg(x)，其中 k 为正整数且 g(x*)  0，则 当k  2时，称 x*为方程 f (x) = 0 的 k 重根 或函数 f (x)的 k 重零点； 当k = 1时，称 x*为方程 f (x) = 0 的单根。**§2.1 根的概念§2.1 根的概念若函数 f (x)存在 k 阶连续导数，则 x*为方程 f (x) = 0 的 k重根当且仅当 f (x*) = f '(x*) = f ''(x*) = … = f (k-1)(x*) = 0，f (k)(x*)≠0 特别地，当k = 1时，有f (x*) = 0 且 f '(x*) ≠ 0。 求解方程根的大致步骤 —— 判定根的存在性。 确定根的初始近似值，即找出每个有根区间，有根区间内的任一点都可看成是该根的一个近似值。 近似根的精确化，即根据根的初始近似值按某种方法逐步精确化，直至满足预先要求的精度为止。**§2.1 根的概念§2.1 根的概念判定根存在的方法 零点定理 —— 设函数 f (x)在闭区间[a, b]上连续，且 f (a) · f (b) < 0，则方程 f (x) = 0 在开区间(a, b)内至少有一实根。即至少有一点 (a <  < b)，使得 f ( ) = 0。 设函数 f (x)在闭区间[a, b]上单调连续(指 f (x) 的一阶导数 f '(x)在[a, b]上恒正或恒负)，且 f (a) · f (b) < 0，则方程 f (x) = 0 在开区间(a, b)内有且仅有一个实根。此时，称[a, b]为有根区间。**§2.1 根的概念§2.1 根的概念确定根的初始近似值 假设 f (x)在区间(a, b)内有且仅有一个实根 x*，若 b - a 较小，则可在(a, b)上任取一点 x0 作为方程的初始近似根。 如何找出有根区间[a, b]？ 方法 —— 试值法 计算 f (x)在若干个点上的函数值，通过函数值符号的变化情况来确定有根区间。 作图法 画出函数 y = f (x)的图形，观察曲线 y = f (x)与 x 轴交点的大致位置，从而确定有根区间。**§2.1 根的概念§2.1 根的概念等步长扫描法 基本原理 —— 当函数 f (x)连续时，可从某点 x0 出发，以 h 为步长依次取点 xi = x0 + i · h ( i = 1, 2, … , N ) 如果有 f ( xi-1 ) · f ( xi ) < 0，则可断定方程 f (x) = 0在区间( xi-1 , xi )内至少有一实根。**§2.1 根的概念§2.1 根的概念例如：讨论方程 f (x) = x3 – x – 1 = 0的根的位置。 由于 f (0) = -1 < 0，f (∞) > 0，故该方程在区间(0 , +∞)内至少有一实根。 现从 x = 0出发，取h = 0.5为步长向右扫描，则函数 f (x)在下列各点上的函数值如下表所示： 由表可见，方程在(1 , 1.5)内至少有一实根。又因 即 f (x)在区间[1 , 1.5]上单调连续，故方程在(1 , 1.5)内有且仅有一个实根，因而可在[1 , 1.5]上任取一点作为方程的初始近似根。**-1-1.375-10.875§2.1 根的概念§2.1 根的概念算法实现 —— 输入 a, b, h (预选步长)；同时，x0 ← a , f0 ← f (x0)； x1 ← x0 + h , f1 ← f (x1)； 若 x1 > b , 则输出失败信息，程序结束； 若 f1 = 0, 则 x1 即为方程的一个根 , 输出 x1 , 程序结束； 若 f0 · f1 < 0 , 则[x0 , x1]即为有根区间，输出 x0 和 x1，程序结束；否则，进入下一步； x0 ← x1 , f0 ← f1 ；转； 注： 当 x1 > b 时，可将 h 适当缩小，继续以上步骤； 如果对足够小的步长 h 扫描仍失败，则说明在[a, b]内无根或有偶重根。**§2.1 根的概念§2.1 根的概念近似根的精确化 根据根的初始近似值，通过某种数值方法，逐步改善近似根的精确度，直至求得满足一定精度要求的近似根。 计算机上常用的求方程近似根的数值方法有 —— 二分法 简单迭代法 牛顿(Newton)迭代法 弦截法 埃特金(Aitken)迭代法**§2.2 二分法§2.2 二分法前提 —— 不妨假定方程 f (x) = 0 在区间[a, b]内有唯一的实根 x* 。此时，[a, b]即为有根区间。 基本思想 —— 首先确定有根区间，然后平分有根区间，通过判断区间端点处的函数值符号，逐步将有根区间缩小，直至有根区间足够地小，便可求出满足给定精度要求的根 x*的近似值。**§2.2 二分法具体计算过程 §2.2 二分法**依次类推，便可得到一系列有根区间：x*abb1a2a3●●a1●b2●b3§2.2 二分法§2.2 二分法其中每个小区间的长度都是前一区间长度的一半，即 显然，当k→∞，必有 bk - ak→0。 因此，如果二分过程无限进行下去，则有根区间 ( ak , bk )最终必收敛于一点 x*，该点就是所求方程的根。 实际计算中，二分过程不可能无限进行下去，只要获得满足预定精度的近似值即可。 如何根据预定精度来结束二分过程？**§2.2 二分法§2.2 二分法二分过程结束原则 —— 设 ε 为预先给定的精度，如果把每次二分后的有根区间 ( ak , bk )的中点 xk 作为所求根 x* 的近似值，则近似根 xk 的误差估计式为 当 |bk+1 – ak+1| <ε时，结束二分过程；此时，取 x*≈xk ； 当 即二分k+1次结束。此时，取 x* ≈ xk 。** x* l m |———|———| ak xk bk §2.2 二分法§2.2 二分法例如：用二分法求方程 f (x) = x3 – x – 1 = 0在区间(1 , 1.5)内的根。要求取四位小数计算，并精确到10-2。 【解】由题意知：a = 1 , b = 1.5 ,  = 0.510-2 ； 并且 f (1) = -1 < 0 , f (1.5) > 0，故有根区间为(1 , 1.5) ； 取 由于 f (1.25) · f (1.5) < 0，故新的有根区间为(1.25 , 1.5)； 取 由于 f (1.25) · f (1.375) < 0，故新的有根区间为(1.25 , 1.375)； 以此类推，计算结果见下表：**§2.2 二分法§2.2 二分法计算结果 由于 |b6 – a6| ≈ 0.0078，于是 故取 x* ≈ x6 ≈ 1.32。**§2.2 二分法§2.2 二分法此外，也可事先估计所要的最小二分次数，再进行计算，这样可以减少计算量。 根据精度要求，即 = 0.510-2 ，近似根应满足 即只要二分 7 次， x6 便可达到精度要求。 **§2.2 二分法§2.2 二分法程序框图**§2.2 二分法§2.2 二分法二分算法实现**§2.2 二分法§2.2 二分法优点 —— 算法简单、可靠，易编程; 对f (x)要求不高(只要连续即可)。 缺点 —— 只能求实根(单实根或奇重实根)，无法求复根及偶重根； 收敛速度较慢，特别是对精度要求较高的近似根，求解时间较长。**§2.3 迭代法§2.3 迭代法迭代法是数值计算中一种重要的逐次逼近法。 基本思想 —— 给定方程的一个初始近似根，然后反复使用某一公式来校正这个初始近似根，使之逐步精确化，直到满足预先给定的精度要求为止。 具体做法： 取一个根的初始近似值 x0 , 计算 x1 = g(x0) , x2 = g(x1) , … , xk+1 = g(xk) , … , 得到一个迭代序列{ xk }, k = 0, 1, 2, … 。**f (x) = 0x = g(x)迭代公式：xk+1 = g(xk) , k = 0, 1, 2, …§2.3 迭代法§2.3 迭代法若迭代序列收敛，则称迭代公式或迭代法是收敛的，否则称迭代公式是发散的。 假设迭代序列收敛于 x* ，即 则当g(x)连续时，对迭代公式 xk+1 = g(xk) 两边取极限，可得 由此表明，序列{ xk }的极限就是方程 f (x) = 0的根。 同样，对于预先给定的精度 > 0，只要 k 适当大且满足 |xk – xk-1 | < ε 就可结束计算并取 x* ≈ xk 。**§2.3 迭代法§2.3 迭代法例如：用迭代法求解方程 f (x) = x3 – x – 1 = 0在[1, 2]内的根。（用6位有效数字计算） 【解】 首先判断有根区间 由于 f (1) = -1 < 0，f (2) = 5 > 0，且 f '(x) = 3x2 – 1 > 0，故方程在[1,2]内有且仅有一个实根，即[1, 2]为有根区间。 构造迭代公式 将原方程改写成以下等价形式 —— 取初始近似根 x0 = 1.5，迭代结果如下表所示：**§2.3 迭代法§2.3 迭代法迭代结果 因为 x7 和 x8 重合，故取 x8 = 1.32472 作为原方程根的一个较好的近似值。 此时，迭代公式 **收敛。§2.3 迭代法§2.3 迭代法虽然迭代法的基本思想很简单，但效果并不总是令人满意的。对于上例，若将方程 f (x) = x3 – x – 1 = 0 写成另一种等价形式，即 仍取初始近似根 x0 = 1.5进行迭代，结果如下： 显然，迭代结果越来越大，迭代公式 **发散。§2.3 迭代法§2.3 迭代法结论 —— 对于一个方程，虽然可以构造不同的迭代公式，但迭代公式并非总是收敛的，即迭代序列的收敛性依赖于迭代函数的构造！ **？ §2.3 迭代法§2.3 迭代法几何意义**|g'(x)|<1|g'(x)|≥1§2.3 迭代法§2.3 迭代法判断迭代公式发散的充分条件 —— **定理2-1 如果对任意 x[a, b]都有 |g'(x)| ≥ 1，则迭代公式 xk+1 = g(xk)发散。证明：当 xk [a, b]时，有 其中，  介于 xk 和 x* 之间。由此可见，迭代序列不会逐步逼近根 x* ，即迭代公式发散。§2.3 迭代法§2.3 迭代法判断迭代公式收敛的充分条件 ——**213§2.3 迭代法§2.3 迭代法证明： 惟一实根 x* ？ 先证根的存在性 —— 令 f (x) = x – g(x)，由条件 a≤g(x)≤b，可得 因此，方程 x = g(x)在区间[a, b]上有根 x* 。 再证根的惟一性 —— [反证]假设 x* 和 y* 都是方程 x = g(x)在[a, b]上的根，则 由条件 q < 1可知，要使上式成立，只有 x* = y*。 综上所述，方程 x = g(x)在[a, b]上有惟一实根 x* 。**f (a) = a – g(a)≤0，f (b) = b – g(b)≥0| x*– y*| = | g(x*) – g(y*)| = | g'(ξ) · (x*– y*)| ≤ q · | x*– y*|§2.3 迭代法§2.3 迭代法 迭代公式收敛于 x* ？ 因此，对 x0[a, b]，迭代公式 xk+1 = g(xk)均收敛于 x*。**| x* – xk | = | g(x*) – g(xk-1)| = | g'(ξ) | · | x* – xk-1 | ≤ q | x* – xk-1 | ≤ q2 | x* – xk-2 | ≤ … … ≤ qk | x* – x0 |∵ 0  q < 1 ∴ qk → 0(k→∞) 0§2.3 迭代法§2.3 迭代法 误差估计式 对任意正整数 p ，有 **令 p →+∞ (k 固定)，即得前半个误差估计式。利用微分中值定理，即可得到结果。§2.3 迭代法§2.3 迭代法例如：已知方程 f (x) = x3 – x – 1 = 0在[1, 2]内有一实根，将方程分别化为 两种等价形式，试判断对应的迭代公式是否收敛？ 【解】 迭代函数 对应的迭代公式 由于 根据定理2-1，迭代公式 xk+1 = g1(xk)发散。**§2.3 迭代法§2.3 迭代法 迭代函数 对应的迭代公式 因为 所以g2(x)在[1, 2]内单调增加。 当 x[1, 2] 时， 即g2(x) [1, 2]，满足定理2-2中的条件 1。 另一方面，由于 即满足定理2-2中的条件 2。 因此，对 x0[1, 2]，迭代公式 xk+1 = g2(xk)收敛。**§2.3 迭代法§2.3 迭代法例如：求方程 x = e-x 在 x = 0.5 附近的一个根。按 5 位小数计算，计算结果的精度要求为ε = 10-3。 【解】 确定有根区间 —— 令 f (x) = x – e-x 由于 f (0.4) < 0，f (0.7) > 0，故所求的根在区间(0.4 , 0.7)内，且在 x = 0.5 附近。  构造收敛的迭代公式 —— 令 g(x) = e-x 为迭代函数，则 1. 当x[0.4 , 0.7]时，g(x)[0.4 , 0.7]； 2. **§2.3 迭代法§2.3 迭代法迭代结果如下： 由表可见，方程 x = e-x 满足精度要求的根为 x* ≈ x10 ≈ 0.567**§2.3 迭代法§2.3 迭代法例如：能否用迭代法求解方程 x = 4 – 2x ? 若不能，试将方程改写成能用迭代法求解的形式。 【解】令 f (x) = x – 4 + 2x ，由于 f (1) < 0，f (2) > 0，故方程 f (x) = 0 在区间(1, 2)内有根。 根据题意，g(x) = 4 – 2x，则 g'(x) = -2xln2 > 2ln2 > 1， x(1, 2) 由定理2-1知，迭代公式发散，即不能用来迭代求根。 将原方程改为 x = ln(4 – x)/ln2，则 g(x) = ln(4 – x)/ln2，若 当 x[1, 2]时，g(x)[1, ln3/ln2][1, 2]； 对x(1, 2)，有 由定理2-2知，可用迭代公式 xk+1 = ln(4 – xk)/ln2来求解。**§2.3 迭代法§2.3 迭代法判断迭代公式局部收敛的充分条件 ——**定义2-1 若存在 x* 的某个邻域 D : | x - x* | <δ，使迭代公式 xk+1 = g(xk) 对于任意初值 x0  D 均收敛，则称迭代公式 xk+1 = g(xk) 在根 x* 附近具有局部收敛性。定理2-3 设方程 x = g(x)在区间[a, b]内有根 x*，且 g(x)在根 x* 附近有连续的一阶导数。如果 | g'(x*) | < 1 则迭代公式 xk+1 = g(xk)在 x* 附近具有局部收敛性。§2.3 迭代法§2.3 迭代法定理2-3证明 —— 由于g(x)在根 x* 附近有连续的一阶导数，故存在 x* 的一个邻域 (x*-δ, x*+δ)  [a, b], 使得 | g'(x) |≤q < 1 另一方面， | g(x) - x* | = | g(x) - g(x*) | = | g'(ξ)(x - x*) |≤q| x - x* | <δ 即对 x  (x*-δ, x*+δ)，有 g(x)(x*-δ, x*+δ) 成立。 因此，由定理2-2可知，对 x0  (x*-δ, x*+δ)，迭代公式局部收敛。**§2.3 迭代法§2.3 迭代法例如：已知方程 x = (x) 在[a, b]内有根 x*，且在[a, b]上满足|'(x) - 3| < 1。试利用(x) 构造一个迭代函数 g(x)，使 xk+1 = g(xk) (k = 0, 1, 2, …) 局部收敛于 x* 。 【解】**§2.3 迭代法§2.3 迭代法例如：已知方程 x3 – x2 – 1 = 0 在 x = 1.5 附近有根，把方程写成以下三种不同的等价形式 ——    试判断每种迭代公式在 x0 = 1.5 附近的敛散性，并选一种收敛计算，精确到小数点后第二位。**§2.3 迭代法§2.3 迭代法【解】    选择进行迭代计算 —— 由于| x4 - x3 | = 0.002 <  = 0.510-2 ，故取 x4 =1.47。**§2.3 迭代法§2.3 迭代法例如：设 F(x) = x + c(x2 - 3)，应如何选取 c 才能使迭代公式 xk+1 = F(xk)具有局部收敛性？ 【解】方程 x = F(x)的根为 由 F(x) = x + c(x2 - 3) 知，F'(x) = 1+2cx 要使迭代公式具有局部收敛性，只要满足   综上所述，使迭代公式 xk+1 = F(xk)具有局部收敛性的 c 的范围为**§2.3 迭代法§2.3 迭代法例如：用适当的迭代公式证明 —— 【证明】考虑迭代公式 则 记 ，则 当 x[0, 2]时，g(x)[g(0), g(2)][0, 2]； 对x(0, 2)，有**§2.3 迭代法§2.3 迭代法迭代法的收敛阶 特别地， 当 p = 1 且 0 < C < 1时，称为线性收敛； 当1 < p < 2时，称为超线性收敛； 当 p = 2 时，称为平方收敛。**§2.3 迭代法§2.3 迭代法迭代法的收敛阶 证明：根据定理2-3及已知条件 g'(x*) = 0 < 1，迭代公式xk+1 = g(xk) 在 x* 附近具有局部收敛性。 把函数 g(x) 在 x* 处Taylor展开，得到**§2.3 迭代法§2.3 迭代法 根据已知条件，整理得到 即 于是 因此，迭代公式 xk+1 = g(xk)在 x* 的邻域是 p 阶收敛的。**§2.3 迭代法§2.3 迭代法 证法1：迭代函数为 根据定理2-4可知，迭代公式平方收敛。 证法2：迭代误差 ek = xk - x* = xk - 1，于是 根据定义2-2可知，迭代公式平方收敛。**例如：已知迭代公式 局部收敛于方程 的根 x* = 1，证明该迭代公式平方收敛。§2.3 迭代法§2.3 迭代法迭代法计算步骤 —— 确定方程 f (x) = 0 的等价形式 x = g(x) 为使迭代过程收敛，要求 g(x) 在有根区间[a , b]内满足 | g'(x)|≤q < 1 选取初始近似根 x0 ，按迭代公式进行计算 xk+1 = g(xk) , k = 0, 1, 2, … 当| xk – xk-1 | < ε（ε 是预定精度）时停止计算，取 x* ≈ xk**§2.3 迭代法§2.3 迭代法程序框图**§2.3 迭代法§2.3 迭代法迭代算法实现**§2.4 牛顿(Newton)迭代法§2.4 牛顿(Newton)迭代法基本思想 —— 把非线性方程线性化，用线性方程的解逐步逼近非线性方程的解。 牛顿迭代公式 —— 设 xk 是方程 f (x) = 0 的近似根，将函数 f (x) 在点 xk 作一阶Taylor展开(忽略高阶项)： 设其根为 xk+1 ，即 当f '(xk) ≠ 0时，可得**= 0§2.4 牛顿(Newton)迭代法§2.4 牛顿(Newton)迭代法几何意义 **xk+1xk+2Pk (xk , f(xk))Pk+1方程 f (x) = 0的根 x*表示曲线 y = f (x) 与 x 轴交点的横坐标。 牛顿迭代法是在根x*的附近，以 xk 作为第 k 次迭代值，然后以 y = f (x) 在点 Pk 处的切线与 x 轴交点的横坐标 xk+1 来代替曲线 y = f (x) 与 x 轴交点的横坐标 x*。 因此，牛顿迭代法也称为切线法。xk(xk+1 ,0)§2.4 牛顿(Newton)迭代法§2.4 牛顿(Newton)迭代法例如：用牛顿迭代法求方程 x = e-x 在[0, 1]中的近似根，取 5 位小数计算，精度要求为 ε = 10–3。 【解】首先把方程改写为 xex – 1 = 0 令 f (x) = xex – 1，则 f '(x) = ex + xex 相应的Newton迭代公式为 取初值 x0 = 0.5进行迭代计算，结果如下： 由于| x3 - x2| = 0.00002 < 10–3，故 x ≈ x3 ≈ 0.567。**§2.4 牛顿(Newton)迭代法§2.4 牛顿(Newton)迭代法例如： 【解】 注：此例的意义在于通过加法和乘除法实现开方运算，是计算机上作开方运算的一个方法。**§2.4 牛顿(Newton)迭代法§2.4 牛顿(Newton)迭代法法1： 法2：**§2.4 牛顿(Newton)迭代法§2.4 牛顿(Newton)迭代法牛顿迭代法的收敛性 —— 局部收敛 证明：x* 是 f (x) = 0单根 由牛顿法迭代函数 故**f (x*) = 0， f (x*) ≠ 0局部收敛§2.4 牛顿(Newton)迭代法§2.4 牛顿(Newton)迭代法 由Taylor展开： **牛顿迭代公式至少具有二阶收敛速度§2.4 牛顿(Newton)迭代法§2.4 牛顿(Newton)迭代法牛顿迭代法收敛的充分条件 —— 由   方程 f (x) = 0在[a, b]上有唯一根 x*。 由  产生的序列单调有界，保证收敛。 由    分 4 种情况讨论牛顿迭代法的收敛性。**定理2-6 设函数 f (x)C2[a, b]，且有  f (a) · f (b) < 0； 在[a, b]上，f '(x) ≠ 0且 f ''(x)不变号； 初始近似根 x0[a, b]满足 f (x0) · f ''(x0) > 0 ； 则牛顿迭代法产生的迭代序列单调收敛于方程 f (x) = 0在[a, b]上的唯一根 x*。§2.4 牛顿(Newton)迭代法§2.4 牛顿(Newton)迭代法**x1x2x1x2x1x2x1x2§2.4 牛顿(Newton)迭代法§2.4 牛顿(Newton)迭代法优点 —— 适用面广，可用于求重根和代数方程的复根； 在 x* 是方程 f (x) = 0单根且 迭代过程收敛的情况下，具有平方收敛速度。 缺点 —— 对初始近似根 x0的选取要求较高，x0必须充分靠近 x*才能保证局部收敛；若 x0离 x*太远，迭代可能发散； 每一步都需求出函数 f (x)的导数 f '(x)。 改进 —— 牛顿下山法 弦截法(割线法)**x*§2.5 牛顿下山法§2.5 牛顿下山法牛顿下山法定义 —— 当xk 求得后，通过  的选取使得 xk+1满足 其中,  为下山因子；-f(x)/f’(x)为 f(x)在点 x 的下山方向. 【说明】 当 =1时，牛顿下山法为标准的牛顿迭代法； 当 =0时， ，此时 不收敛于x*，因此为保证收敛性，  不能太小。**§2.5 牛顿下山法§2.5 牛顿下山法下山因子 的取法 ——   =1 若满足 ，则把 xk+1作为第k+1次近似值； 若不满足 ，则取 =1/2；   =1/2 若满足 ，则把 xk+1作为第k+1次近似值； 若不满足 ，则取 =1/4；  ......**§2.6 弦截法§2.6 弦截法基本思想 —— 为避免导数计算，用差商来代替导数 f '(x) ，即 Newton迭代公式 整理得到 **§2.6 弦截法§2.6 弦截法几何意义 ——**xk+1Pk (xk , f(xk))用过曲线上两点 Pk -1、Pk的割线来代替曲线，用割线与 x 轴交点的横坐标作为方程 f (x) = 0 的近似根xk +1 。Pk+1 (xk+1 , f(xk+1))Pk-1 (xk-1 , f(xk-1))割线方程 令 y = 0，则 x = xk+1 即 xk+1 的表达式就是弦截迭代公式。xk+2§2.6 弦截法§2.6 弦截法例如：用弦截法求方程 x = e-x 在 x = 0.5 附近的根。 取 ε < 10-3。 【解】首先把方程改写为 x – e-x = 0，并令 f (x) = x – e-x ，则弦截迭代公式如下： 取 x0 = 0.5，x1 = 0.6 作为初始近似根，进行迭代计算，结果如下： 由于| x3 - x2| = 0.00039 < 10–3，故 x ≈ x3 ≈ 0.567。 与牛顿迭代法相比，弦截法的收敛速度也是比较快的。**§2.7 迭代收敛的加速方法§2.7 迭代收敛的加速方法对于收敛的迭代过程，只要迭代足够多次，总可以得到满足指定精度要求的结果。但是，有时迭代过程收敛缓慢，计算效率很低。 如何改进迭代法使之加快收敛速度？ 方法 —— 斯蒂芬森(Steffensen)加速迭代法 埃特金(Aitken)加速迭代法**§2.7 迭代收敛的加速方法§2.7 迭代收敛的加速方法斯蒂芬森(Steffensen)加速迭代法**P1●或§2.7 迭代收敛的加速方法§2.7 迭代收敛的加速方法 **或§2.7 迭代收敛的加速方法§2.7 迭代收敛的加速方法埃特金(Aitken)加速迭代法 设 x*为方程 x = g(x)的一个实根，xk 为一个近似根，且 利用微分中值定理，有 整理得到**构造前提 —— 假定 g'(x) 在求根区间内改变不大，即 g'(x)≈L。§2.7 迭代收敛的加速方法§2.7 迭代收敛的加速方法因此，埃特金迭代公式归结如下： 注：当迭代过程收敛缓慢时，一般可用埃特金方法进行加速。但是，当 g'(x) 变化幅度较大或者 x0 与 x* 的距离较远时，埃特金方法也可能失效。 另外，埃特金方法有时可以把一个原本发散的迭代公式改造成一个收敛的迭代公式。**§2.7 迭代收敛的加速方法§2.7 迭代收敛的加速方法例如：用埃特金迭代法求 x3 – x – 1 = 0在 (1, 1.5)内的根。 【解】将方程改写成 x = x3 – 1，则 g(x) = x3 – 1。 简单迭代公式 埃特金迭代公式 取 x0 = 1.5**小结小结二分法 简单、容易编程；对函数要求不高；收敛速度慢；适用于求解精度不高的近似根；一般用来作为其他迭代法的初值。 迭代法 逐次逼近，原理简单，但需要证明收敛性，存在收敛速度问题，可以用Aitken迭代法改善。 牛顿法 特殊的迭代法，具有一般迭代法特点，还具有在单根附近的平方收敛速度，但对初值选取要求高，可以用牛顿下山法改善。 弦截法 不求导数，收敛慢。**