《牛顿-拉夫森法和割线法》由会员分享，可在线阅读，更多相关《牛顿-拉夫森法和割线法（18页珍藏版）》请在金锄头文库上搜索。
1、4 牛顿法 /* Newton - Raphson Method */,原理：将非线性方程线性化 Taylor 展开 /* Taylors expansion */,取 x0 x*，将 f (x)在 x0 做一阶Taylor展开:,， 在 x0 和 x 之间。,将 (x* x0)2 看成高阶小量，则有：,线性 /* linear */,只要 f C1，每一步迭代都有f ( xk ) 0， 而且 ，则 x*就是 f 的根。,4 Newton - Raphson Method,定理,（收敛的充分条件）设 f C2a, b，若(1) f (a) f (b) 0；则Newtons Method产生的序
2、列 xk 收敛到f (x) 在 a, b 的唯一根。,有根,根唯一,产生的序列单调有界，保证收敛。,定理,（局部收敛性）设 f C2a, b，若 x* 为 f (x) 在a, b上的根，且 f (x*) 0，则存在 x* 的邻域 使得任取初值 ，Newtons Method产生的序列 xk 收敛到x*，且满足,4 Newton - Raphson Method,证明：Newtons Method 事实上是一种特殊的不动点迭代 其中 ，则,收敛,由 Taylor 展开：,只要 f (x*) 0，则令 可得结论。,在单根 /*simple root */ 附近收敛快,4 Newton - Raph
3、son Method,注：Newtons Method 收敛性依赖于x0 的选取。,x*,HW: p.27 #3, #4,Excuses for not doing homeworkI have the proof, but there isnt room to write it in this margin.,4 Newton - Raphson Method, 重根 /* multiple root */ 加速收敛法：,Q1: 若 ，Newtons Method 是否仍收敛？,设 x* 是 f 的 n 重根，则： 且 。,因为 Newtons Method 事实上是一种特殊的不动点迭代，其
4、中 ，则,A1: 有局部收敛性，但重数 n 越高，收敛越慢。,Q2: 如何加速重根的收敛？,A2: 将求 f 的重根转化为求另一函数的单根。,令，则 f 的重根 = 的单根。,4 Newton - Raphson Method, 正割法 /* Secant Method */ ：,Newtons Method 一步要计算 f 和 f ，相当于2个函数值，比较费时。现用 f 的值近似 f ，可少算一个函数值。,切线 /* tangent line */,割线 /* secant line */,切线斜率割线斜率,需要2个初值 x0 和 x1。,收敛比Newtons Method 慢，且对初值要求
5、同样高。,4 Newton - Raphson Method, 下山法 /* Descent Method */ Newtons Method 局部微调：,原理：若由 xk 得到的 xk+1 不能使 | f | 减小，则在 xk 和 xk+1 之间找一个更好的点 ，使得 。,注： = 1 时就是Newtons Method 公式。 当 = 1 代入效果不好时，将 减半计算。,4 Newton - Raphson Method,Algorithm: Newtons Descent MethodFind a solution to f (x) = 0 given an initial approx
6、imation x0.Input: initial approximation x0; f (x) and f (x); minimum step size of xmin; tolerance TOL1 for x ; tolerance TOL2 for ; maximum number of iterations Nmax.Output: approximate solution x or message of failure.Step 1 Set k = 1;Step 2 While ( k Nmax) do steps 3-10Step 3 Set = 1; Step 4 Set ;
7、 /* compute xk */Step 5 If | x x0 | TOL2 then GOTO Step 4 ; /* compute a better xi */ Step 9 Set x0 = x0 + xmin ; /* move forward anyway to avoid deadlock */Step 10 Set k +;Step 11 Output (Method failed after Nmax iterations); STOP. /* unsuccessful */,计算量未见得减小,4 Newton - Raphson Method, 求复根 /* Findi
8、ng Complex Roots */ Newton 公式中的自变量可以是复数,记 z = x + i y, z0 为初值，同样有,设,HW: p.28 #10,代入公式，令实、虚部对应相等，可得,4 Newton - Raphson Method,4 Newton - Raphson Method,5 迭代法的收敛阶 /* Order of Convergence */, 一般 Fixed-Point Iteration 有 ，称为线 性收敛 /* linear convergence */，这时 p = 1，0 C 1。 例如 xn = 1/nn 超线性收敛到0，但对任何 p 1 都没有
9、p 阶收敛。, Aitken 加速有 。 称为超线性收敛 /* superlinear convergence */。,5 Order of Convergence, Steffensen 加速有 p = 2，条件是 ，称为平方收敛 /* quadratic convergence */。, Newtons Method 有 ，只要 ， 就有 p 2。重根是线性收敛的。,Q: 如何实际确定收敛阶和渐进误差常数？,证明：,HW: p.29 #1,6 劈因子法 /* Splitting Method */,求多项式的根,目标：r = r ( u*, v* ) = 0，s = s ( u*, v* ) = 0。,6 Splitting Method,将r 和 s 在初值点( u, v )做一阶Taylor展开，并代入( u*, v*)：,6 Splitting Method, 计算 r 和 s ：,可记为 bn1,若令 ，则,6 Splitting Method, 计算 ：,n2 阶多项式,n4 阶多项式,与前一步同理，可导出和 的公式。,6 Splitting Method, 计算 ：,而前一步得到,可见,
