第7章.非线性方程迭代法.ppt

1、非线性方程迭代法,邹昌文,迭代法 / Fixed-Point Iteration /,f (x) = 0,x = g (x),f (x) 的根,g (x) 的不动点,思路,从一个初值 x0 出发，计算 x1 = g(x0), x2 = g(x1), , xk+1 = g(xk), 若 收敛，即存在 x* 使得 ，且 g 连续，则由 可知 x* = g(x* )，即x* 是 g 的不动点，也就是f 的根。,迭代法几何意义如下,定理,（充分条件）考虑方程 x = g(x), g(x)Ca, b, 若,( I ) 当 xa, b 时， g(x)a, b； ( II ) 0 L 1 使得 | g(x)

2、 | L 1 对 xa, b 成立。 则任取 x0a, b，由 xk+1 = g(xk) 得到的序列 收敛于g(x) 在a, b上的唯一不动点。并且有误差估计式：,( k = 1, 2, ),且存在极限,证明： g(x) 在a, b上存在不动点？,令,有根, 不动点唯一？,反证：若不然，设还有 ，则,而, 当k 时， xk 收敛到 x* ？,可用 来控制收敛精度,L 越 收敛越快,小,注：定理条件非必要条件，可将a, b缩小，定义局部收敛性：若在 x* 的某 领域 B = x | | x x* | 有 gC1a, b 且 | g(x*) | 1，则由x0B 开始的迭代收敛。即调整初值可得到收敛

3、的结果。,设在区间a, b上方程 x= (x) 有根x*,且对一切xa, b 都有|(x)| 1，则对于该区间上任意x0(x*), 迭代公式xk+1= (xk )一定发散。,证明:,不可能收敛于0。,定理, 待定参数法：,若 | g(x) | 1，则将 x = g(x) 等价地改造为,求K，使得,例：求 在 (1, 2) 的实根。,如果用 进行迭代，则在(1, 2)中有,现令,在 (1, 2) 上可取任意 ，例如K = 0.5，则对应 即产生收敛序列。, Aitken 加速：,P(x0, x1),P(x1, x2),一般地，有：,比 收敛得略快。, Steffensen 加速：,详见P273,

4、定理,（牛顿法收敛的充分条件）设 f C2a, b，若 (1) f (a) f (b) 0； 则Newtons Method产生的序列 xk 收敛到f (x) 在 a, b 的唯一根。,有根,根唯一,产生的序列单调有界，保证收敛。,定理,（局部收敛性）设 f C2a, b，若 x* 为 f (x) 在a, b上的根，且 f (x*) 0，则存在 x* 的邻域 使得任取初值 ，Newtons Method产生的序列 xk 收敛到x*，且满足,证明：Newtons Method 事实上是一种特殊的不动点迭代 其中 ，则,收敛,由 Taylor 展开：,只要 f (x*) 0，则令 可得结论。,在单

5、根 /simple root / 附近收敛快, 重根 / multiple root / 加速收敛法：,Q1: 若 ，Newtons Method 是否仍收敛？,设 x* 是 f 的 n 重根，则： 且 。,因为 Newtons Method 事实上是一种特殊的不动点迭代， 其中 ，则,A1: 有局部收敛性，但重数 n 越高，收敛越慢。,Q2: 如何加速重根的收敛？,A2: 将求 f 的重根转化为求另一函数的单根。,令，则 f 的重根 = 的单根。, 正割法 / Secant Method / ：,Newtons Method 一步要计算 f 和 f ，相当于2个函数值，比较费时。现用 f 的

6、值近似 f ，可少算一个函数值。,切线 / tangent line /,割线 / secant line /,切线斜率割线斜率,需要2个初值 x0 和 x1。,收敛比Newtons Method 慢，且对初值要求同样高。, 下山法 / Descent Method / Newtons Method 局部微调：,原理：若由 xk 得到的 xk+1 不能使 | f | 减小，则在 xk 和 xk+1 之间找一个更好的点 ，使得 。,注： = 1 时就是Newtons Method 公式。 当 = 1 代入效果不好时，将 减半计算。, 求复根 / Finding Complex Roots / N

7、ewton 公式中的自变量可以是复数,记 z = x + i y, z0 为初值，同样有,设,代入公式，令实、虚部对应相等，可得,迭代法的收敛阶 / Order of Convergence /, 一般 Fixed-Point Iteration 有 ，称为线 性收敛 / linear convergence /，这时 p = 1，0 C 1。,注：超线性收敛不一定有 p 1。 例如 xn = 1/nn 超线性收敛到0，但对任何 p 1 都没有 p 阶收敛。, Aitken 加速有 。 称为超线性收敛 / superlinear convergence /。, Steffensen 加速有 p = 2，条件是 ，称为平方收敛 / quadratic convergence /。, Newtons Method 有 ，只要 ， 就有 p 2。重根是线性收敛的。,Q: 如何实际确定收敛阶和渐进误差常数？,证明：,详见P271,一种迭代法具有实用价值，首先要求它是收敛的，其次还要求它收敛得比较快。 设迭代过程 收敛于 的根 ,记迭代误差 若存在常数p（p1）和c（c0），使,则称序列 是p 阶收敛的,c称渐近误差常数。特别地,p=1时称