非线性方程迭代法市公开课获奖课件

1、非线性方程迭代法邹昌文 第1页第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 根。迭代法几何意义下列第2页第2页xyy = xxyy = xxyy = xxyy = xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0 x1p1x0p0 x1p1x0p0

2、 x1p1x0p0 x1p1第3页第3页定理（充足条件）考虑方程 x = g(x), g(x)Ca, b, 若( I ) 当 xa, b 时， g(x)a, b；( II ) 0 L 1 使得 | g(x) | L 1 对 xa, b 成立。则任取 x0a, b，由 xk+1 = g(xk) 得到序列 收敛于g(x) 在a, b上唯一不动点。并且有误差预计式：( k = 1, 2, )且存在极限第4页第4页证实： g(x) 在a, b上存在不动点？令有根 不动点唯一？反证：若不然，设尚有 ，则在和之间。而 当k 时， xk 收敛到 x* ？第5页第5页可用 来控制收敛精度L 越 收敛越快小注：

3、定理条件非必要条件，可将a, b缩小，定义局部收敛性：若在 x* 某 领域 B = x | | x x* | 有 gC1a, b 且 | g(x*) | 1，则由x0B 开始迭代收敛。即调整初值可得到收敛结果。第6页第6页 设在区间a, b上方程 x= (x) 有根x*,且对一切xa, b 都有|(x)| 1，则对于该区间上任意x0(x*), 迭代公式xk+1= (xk )一定发散。证实:不也许收敛于0。定理第7页第7页改进、加速收敛 / accelerating convergence / 待定参数法：若 | g(x) | 1，则将 x = g(x) 等价地改造为求K，使得例：求 在 (1,

4、 2) 实根。假如用 进行迭代，则在(1, 2)中有现令希望，即在 (1, 2) 上可取任意 ，比如K = 0.5，则相应 即产生收敛序列。第8页第8页 Aitken 加速：xyy = xy = g(x)x*x0P(x0, x1)x1x2P(x1, x2)普通地，有：比 收敛得略快。 Steffensen 加速：详见P273第9页第9页定理 （牛顿法收敛充足条件）设 f C2a, b，若(1) f (a) f (b) 0；则Newtons Method产生序列 xk 收敛到f (x) 在 a, b 唯一根。有根根唯一产生序列单调有界，确保收敛。定理 （局部收敛性）设 f C2a, b，若 x*

5、 为 f (x) 在a, b上根，且 f (x*) 0，则存在 x* 邻域 使得任取初值 ，Newtons Method产生序列 xk 收敛到x*，且满足第10页第10页证实：Newtons Method 事实上是一个特殊不动点迭代 其中 ，则收敛由 Taylor 展开：只要 f (x*) 0，则令 可得结论。在单根 /simple root / 附近收敛快第11页第11页牛顿迭代法改进与推广 重根 / multiple root / 加速收敛法：Q1: 若 ，Newtons Method 是否仍收敛？设 x* 是 f n 重根，则： 且 。由于 Newtons Method 事实上是一个特殊

6、不动点迭代，其中 ，则A1: 有局部收敛性，但重数 n 越高，收敛越慢。Q2: 如何加速重根收敛？A2: 将求 f 重根转化为求另一函数单根。令，则 f 重根 = 单根。第12页第12页 正割法 / Secant Method / ：Newtons Method 一步要计算 f 和 f ，相称于2个函数值，比较费时。现用 f 值近似 f ，可少算一个函数值。x0 x1切线 / tangent line /割线 / secant line /切线斜率割线斜率需要2个初值 x0 和 x1。收敛比Newtons Method 慢，且对初值要求同样高。第13页第13页 下山法 / Descent Me

7、thod / Newtons Method 局部微调：原理：若由 xk 得到 xk+1 不能使 | f | 减小，则在 xk 和 xk+1 之间找一个更加好点 ，使得 。xkxk+1注： = 1 时就是Newtons Method 公式。 当 = 1 代入效果不好时，将 减半计算。第14页第14页 求复根 / Finding Complex Roots / Newton 公式中自变量能够是复数记 z = x + i y, z0 为初值，同样有设代入公式，令实、虚部相应相等，可得第15页第15页迭代法收敛阶 / Order of Convergence /定义设迭代 xk+1 = g(xk) 收

8、敛到g(x) 不动点 x*。设 ek = xk x*，若，则称该迭代为p 阶收敛，其中 C 称为渐进误差常数。/ xk converges to x* of order p, with asymptotic error constant C 0 / 普通 Fixed-Point Iteration 有 ，称为线 性收敛 / linear convergence /，这时 p = 1，0 C 1。 比如 xn = 1/nn 超线性收敛到0，但对任何 p 1 都没有 p 阶收敛。 Aitken 加速有 。 称为超线性收敛 / superlinear convergence /。第16页第16页 S

9、teffensen 加速有 p = 2，条件是 ，称为平方收敛 / quadratic convergence /。 Newtons Method 有 ，只要 ， 就有 p 2。重根是线性收敛。Q: 如何实际拟定收敛阶和渐进误差常数？定理 设 x* 为x = g(x) 不动点，若 ，p 2； ，且 ，则 xk+1 = g(xk) 在 内 p 阶收敛。证实：x*k C详见P271第17页第17页第18页第18页第19页第19页第20页第20页 一个迭代法含有实用价值，首先要求它是收敛，另一方面还要求它收敛得比较快。 设迭代过程 收敛于 根 ,记迭代误差若存在常数p（p1）和c（c0），使 则称序列 是p 阶收敛,c称渐近误差