Newton’s method uses the root of the tangent line equation of a function to approximate the root of the original function. It uses a “tangent line”; if we change this to a “tangent parabola” with the same curvature, we obtain more stable convergence and a faster convergence rate.
Assume the function y=f(x) has a “tangent parabola” y=ax^2+bx+c at (x_0,y_0), then we should have:
a(x_0+\Delta x)^2+b(x_0+\Delta x)+c=f(x_0+\Delta x) \tag{A} ax_0^2+bx_0+c=f(x_0) \tag{B} a(x_0-\Delta x)^2+b(x_0-\Delta x)+c=f(x_0-\Delta x) \tag{C}
where \lim_{\Delta x \to 0}.
This system of equations has a solution. First, (A) - (B) gives: a(\Delta x^2+2x_0\Delta x)+b\Delta x=f(x_0+\Delta x)-f(x_0) \tag{D} (B) - (C) gives: a(-\Delta x^2+2x_0\Delta x)+b\Delta x=f(x_0)-f(x_0-\Delta x) \tag{E} (D) - (E) gives: \begin{aligned} 2\Delta x^2 a &= [f(x_0+\Delta x)-f(x_0)]-[f(x_0)-f(x_0-\Delta x)] \\ &\Rightarrow \\ a &= \lim_{\Delta x \to 0} \frac{\frac{f(x_0+\Delta x)-f(x_0)}{\Delta x}-\frac{f(x_0)-f(x_0-\Delta x)}{\Delta x}}{2\Delta x} \\ &= \lim_{\Delta x \to 0} \frac{f'(x_0)-f'(x_0-\Delta x)}{2\Delta x} \\ &= \lim_{\Delta x \to 0} \frac{f''(x_0-\Delta x)}{2} = \frac{f''(x_0)}{2} \end{aligned}
That is a=\frac{y_0''}{2}, and consequently we have: b=y_0'-y_0''x_0, c=y_0-y_0'+\frac{y_0''x_0^2}{2}.
Thus, we have derived the tangent parabola equation for any function y=f(x), which can be used to effectively approximate the root of the original function. Let y=f(x), set the above parabola equation to 0, and solve this equation: x=x_0-\frac{y_0'}{y_0''} \pm \sqrt{\left(\frac{y_0'}{y_0''}\right)^2-\frac{2y_0}{y_0''}}
Generally, this is a value closer to the root of the equation than x_0 (\pm is to be determined, usually the positive sign is taken). We can take this solution to continue finding the tangent parabola and repeat the above steps. Thus, the iterative formula is: x_{n+1}=x_n-\frac{y_n'}{y_n''} \pm \sqrt{\left(\frac{y_n'}{y_n''}\right)^2-\frac{2y_n}{y_n''}}
Undeniably, the computational cost is much larger than that of Newton’s method; however, it also has certain advantages: it converges faster, and the range of values for x_0 is wider.
The above was derived from a purely geometric perspective, which has clear geometric meaning. It can be derived more conveniently from the Taylor series. According to the Taylor series: f(x)=f(x_n)+f'(x_n)(x-x_n)+\frac{f''(x_n)}{2!}(x-x_n)^2 +\frac{f'''(x_n)}{3!}(x-x_n)^3 +\dots
Newton’s method takes f(x)=f(x_n)+(x-x_n)f'(x_n) as the approximate equation for f(x)=0, while the “tangent parabola” takes f(x)=f(x_n)+(x-x_n)f'(x_n)+(x-x_n)^2 \frac{f''(x_n)}{2!}. This is a quadratic equation in x, from which we can derive: x_{n+1}=x_n-\frac{y_n'}{y_n''} \pm \sqrt{\left(\frac{y_n'}{y_n''}\right)^2-\frac{2y_n}{y_n''}}
Is the process much simpler? But why did we start with the complex geometric derivation? In fact, such a derivation embodies the key point of analytic geometry—the combination of algebra and geometry. It helps us understand the geometric meaning of a method and subsequently derive more methods. For example, instead of a “tangent parabola”, we could use a “tangent hyperbola”, “tangent ellipse”, etc., to achieve more results. For example, the result for a function’s “tangent hyperbola” is: \begin{aligned} y &= k/x+b \\ k &= -y_0'x_0^2 \\ b &= y_0+y_0'x_0 \end{aligned} The iterative formula is: x_{n+1}=\frac{y_n' x_n^2}{y_n+y_n' x_n}
(This is a “weak tangent hyperbola”, which converges slower than Newton’s method; a complete tangent hyperbola should be in the form y=k/(x-l)+b, which requires the use of second derivatives.)
When reposting, please include the address of this article: https://kexue.fm/archives/504
For more detailed reposting matters, please refer to: “Scientific Space FAQ”