(Original) Solving Equations by the Tangent-Parabola Method

(原创)切抛物线法解方程 苏剑林 · 2010-03-06 · Mathematics equation function numerical algorithm zero point iteration curve parabola

Newton's method approximates the zeros of a function by using the zero of the equation of the function's tangent line — it uses a "tangent straight line." If we instead use a "tangent parabola" with the same curvature, we can obtain more stable convergence and faster convergence speed.

Suppose 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)$-------(A)

$ax_0^2+bx_0+c=f(x_0)$-------(B)

$a(x_0-\Delta x)^2+b(x_0-\Delta x)+c=f(x_0-\Delta x)$-------(C)

where $lim_{\Delta x->0}$more

This system of equations does have a solution. First, subtracting (B) from (A) gives:

$a(\Delta x^2+2x_0\Delta x)+b\Delta x=f(x_0+\Delta x)-f(x_0)$----(D)

Subtracting (C) from (B) gives

$a(-\Delta x^2+2x_0\Delta x)+b\Delta x=f(x_0)-f(x_0-\Delta x)$----(E)

Subtracting (E) from (D) 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->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->0}\frac{f'(x_0)-f'(x_0-\Delta x)}{2\Delta x} \\ =lim_{\Delta x->0} \frac{f''(x_0-\Delta x)}{2}=\frac{f''(x_0)}{2}\end{aligned}$$

that is, $a=\frac{y_0''}{2}$, and from this we further obtain: $b=y_0'-y_0''x_0$, $c=y_0-y_0'+\frac{y_0''x_0^2}{2}$

At this point, we have found the tangent-parabola equation for an arbitrary function $y=f(x)$, which can be used to effectively approximate the zero of the original function. Let $y=f(x)$, and setting the above parabola equation equal to zero, we solve this equation:

$$x=x_0-\frac{y_0'}{y_0''}+-\sqrt{(\frac{y_0'}{y_0''})^2-\frac{2y_0}{y_0''}}$$

In general, this value is closer to the zero of the equation than $x_0$ (here $+-$ is to be determined; usually the positive sign is taken). We can take this solution and continue finding the tangent parabola, repeating the above steps, thus obtaining the recurrence formula:

$$x_{n+1}=x_n-\frac{y_n'}{y_n''}+-\sqrt{(\frac{y_n'}{y_n''})^2-\frac{2y_n}{y_n''}}$$

Admittedly, this involves much more computation than Newton's method; but it also has certain advantages — faster convergence, and a wider range of valid values for $x_0$.

The above derivation was carried out from a purely geometric point of view, so its geometric meaning is clear. It can also be derived more conveniently from the Taylor series. According to the Taylor series, we have:

$$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 +...$$

Newton's method takes $f(x)=f(x_n)+(x-x_n)f'(x_n)$ as the approximate equation for $f(x)=0$, whereas the "tangent parabola" method takes $f(x)=f(x_n)+(x-x_n)f'(x_n)+(x-x_n)^2 \frac{f''(x_n)}{2!}$, which is a quadratic equation in x. From this we can derive:

$$x_{n+1}=x_n-\frac{y_n'}{y_n''}+-\sqrt{(\frac{y_n'}{y_n''})^2-\frac{2y_n}{y_n''}}$$

Isn't this process much simpler? So why did we start with the more complicated geometric approach? In fact, deriving it this way precisely reflects the key point of analytic geometry — combining algebra with geometry — which helps us understand the geometric meaning of a method, and in turn allows us to derive even more methods. For example, instead of a "tangent parabola," we could use a "tangent hyperbola," a "tangent ellipse," and so on, achieving further results. For instance, the result for the "tangent hyperbola" of a function is

$$\begin{aligned}y=k/x+b \\ k=-y_0'x_0^2 \\ b=y_0+y_0'x_0\end{aligned}$$

with the recurrence formula: $x_{n+1}=\frac{y_n' x_n^2}{y_n+y_n' x_n}$

(This is the "weak tangent hyperbola," which converges more slowly than Newton's method; the full tangent hyperbola should take the form $y=k/{x-l}+b$, which requires the use of the second derivative.)