Lecture3NewtonLecture3Newton迭代法迭代法和弦截法和弦截法Newtons MethodExtend tangent line from current approximation xi, f(xi) to where it crosses the x axisxi, f(xi)Newtons MethodTheorem 1.5 Assume that and there exists a number , where f(p)=0. If , then there exists a such that the sequence define by the iteration will converge to p for any initial approximation . Newtons Method证明 由于g(x)连续，且 then for any given number k in (0, 1), there exists a such that for all .Newtons Method此时，g(x)是 上的压缩映射。根据压缩映射定理对于任意选定的初值，迭代序列收敛于g(x)的不动点p.Newtons MethodCorollary 1.2 Assume that A0 is a real number and let be an initial approximation to .Define the sequence using the recursive ruleThen the sequence converges to .that is Newtons Iteration for Finding Square Roots证明 可以看出，序列 是Newton 迭代序列。 以下证明序列收敛于 。 Newtons Iteration for Finding Square RootsSpeed of ConvergenceDefinition Assume that converges to p and set for . If two positive constants and exist, and then the sequence is said to converge to p with order of convergence R. The number A is called the asymptotic error constant.If R=1, the convergence is called linear. If R=2, the convergence is called quadratic. Speed of Convergence说明等价于在直角坐标系下，点 逐渐接近直线用最小二乘法可以求出用最小二乘法可以求出-R和和-lnA，继而求出，继而求出R、A。 Speed of ConvergenceK=1时，则额外要求|g(p)|25、在程序设计中如何控制迭代的循环？n选择一个最大的迭代次数n函数值充分小（小于epsilon）n相邻迭代差充分小（看着绝对误差, 小于delta）n相对误差充分小(小于delta)。在计算相对误差时，为了避免分母过小，分母用abs(p1)+delta来替换。Newton Iteration作业（6题）n编写一个C语言函数，利用Newton迭代求多项式的根。