Root Finding

Newton’s method

Newton’s method uses the linear approximation to approach the root of $f(x)$, the following is the linear approximation near $x = a$.

$$ f(x) = f(a) + f'(a)(x-a) $$

Because we want to approximate the root $r$ by $x_{n}$ as close as we want, take $x = x_{n}$,$a = x_{n-1}$. Then we substitute them to the equation and derive it by separating $x_n$ and $x_{n-1}$.

$$ f(x_n) = 0 = f(x_{n-1})+f'(x_{n-1})(x_n - x_{n-1}) $$$$ x_n = x_{n-1} - \frac{f(x_n)}{f'(x_{n-1)}} $$

Hence, we can iterate the function to approximate the real root.

Tung’s method

By the second order Taylor’s expansion at $x = a$.

$$ f(x) = f(a) + f'(a)(x-a)+\frac{f''(a)}{2!}(x-a)^2 + R_3(x) $$

As the same way we did in the Newton’s method, take $x = x_{n+1}$, $a = x_{n}$. This equation becomes

$$ f(x_{n+1}) = f(x_n) + f'(x_n)(x_{n+1}-x_n)+\frac{1}{2}f''(x_n)(x_{n+1} - x_n)^2 \quad ── \ (1) $$

Let $t = x_{n+1} - x_n$, substitute $t$ into the equation$(1)$.

$$ f(x_{n+1}) = 0 = f(x_n) + f'(x_n) \cdot t + \frac{1}{2} f''(x_n) \cdot t^2 \quad ──\ (2) $$

The equation (2) can be seen as a quadratic equation of $t$. Hence, we solve $t$ by the formula.

$$ t = \frac{-f'(x_n) \pm \sqrt{[f'(x_n)]^2 - 2f(x_n)f''(x_n)}}{f''(x_n)} = x_{n+1} - x_n $$$$ x_{n+1} = x_n + \frac{-f'(x_n) \pm \sqrt{[f'(x_n)]^2 - 2f(x_n)f''(x_n)}}{f''(x_n)} $$

We can find that there are two roots in this equation. Since we hope $x_{n+1}$ can close to the real root, logically we chose the one closer to the real root. But, in reality, we don’t know where is the real root. Thus, we have to chage the strategy by chosing the one closer to $x_n$, because $x_n$is approxing to the real root.

Hsiao’s method

Hsiao’s method is keep the Taylor’s expansion to the forth oreder, and derive it. Then, iteration the formula we derived to approximate the root.

Now, we have the forth order Taylor’s expansion at $x = a$.

$$ f(x) = f(a) + f'(a)(x-a)+\frac{f''(x)}{2!}(x-a)^2 + \frac{f^{(3)}(x)}{3!}(x-a)^3 + \frac{f^{(4)}(x)}{4!}(x-a)^4 + R_5(x) $$

As the same way we did in the Newton’s method, take $x = x_{n+1}$, $a = x_n$

$$ \begin{align*} f(x_{n+1}) = 0 = f(x_n)+f'(x_n)(x_{n+1} - x_n) + \frac{1}{2}f''(x_n)(x_{n+1}-x_n)^2 + \frac{1}{6}f^{(3)}(x_n)(x_{n+1}-x_n)^3 + \frac{1}{24}f^{(4)}(x_n)(x_{n+1} - x_n)^4 \end{align*} $$

We want to find a iterative formula $x_{n+1} = g(x_n)$, therefore move the $f(x_n)$to the other side and extract $(x_{n+1} - x_n)$out.

$$ \begin{align*} -f(x_n) = (x_{n+1} - x_n)[f'(x_n)+\frac{1}{2}f''(x_n)(x_{n+1}-x_n) + \frac{1}{6}f^{(3)}(x_n)(x_{n+1}-x_n)^2 + \frac{1}{24}f^{(4)}(x_n)(x_{n+1} - x_n)^3] \end{align*} $$

By the Newton’s method, $x_{n+1} - x_n = -\frac{f(x_n)}{f'(x_n)}$. Subtitute them into the equation.

$$ \begin{align*} -f(x_n) = (x_{n+1} - x_n)[f'(x_n) - \frac{1}{2}f''(x_n) \frac{f(x_n)}{f'(x_n)} + \frac{1}{6} f^{(3)}(x_n)[\frac{f(x)}{f'(x)}]^2 - \frac{1}{24}f^{(4)}(x_n) [\frac{f(x)}{f'(x)}]^3] \end{align*} $$

Then, we move the $x_{n+1}$to one side, all the other elements to another side.

$$ x_{n+1} = x_n - \frac{24[f'(x_n)]^3 f(x_n)}{24[f'(x_n)]^2 -12f''(x_n)[f'(x_n)]^2f(x_n) + 4 f^{(3)}(x_n)f'(x_n)[f(x_n)]^2 -f^{(4)}(x)[f(x)]^3} $$