Quintic Equation

• Step 1. Find the upper and lower bounds of real roots
• Step 2. Find the extrema of $f(x)$
• Step 3. Select ranges containing a root
  • Case 1. $n = 4$
  • Case 2. $n = 2$
  • Case 3. $n = 0$
• Step 4. Ostrowski’s method
• References

Consider a quintic equation $$\begin{aligned} f(x) = x^5 + a_4x^4 + a_3x^3 + a_2x^2 + a_1x + a_0 = 0 \end{aligned}$$

Even though it is a well-known fact that there is no general solution in radicals to degree five or higher polynomial equations as proved by Abel-Ruffini theorem, it is possible to find approximately the roots of $f(x)$.

Step 1. Find the upper and lower bounds of real roots

First of all, determine the search range. With the geometrical properties of polynomial roots, there are some methods to get the bounds of real roots. Among them, an application of Cauchy’s bound can set an upper bound as follows. $$\begin{aligned} 1 + \max_{0 \le i \le 4} (-a_i) \end{aligned}$$

For a lower bound, it suffices to apply this formula to $f(-x)$ and then multiply $-1$ by the result.

Step 2. Find the extrema of $f(x)$

$$\begin{aligned} f'(x) = 5x^4 + 4 a_4 x^3 + 3 a_3 x^2 + 2 a_2 x + a_1 = 0 \end{aligned}$$

Next, the extrema should be obtained from the first derivative $f'(x)$. This requires solving a quartic equation and this note explains how to do this. These extrema are used to set ranges to find each root. Note that any inflection point will not be counted because it cannot be an extremum since $f(x)$ is polynomial.

Step 3. Select ranges containing a root

This step aims to set ranges worthy to run an iterative method to find roots. The found extrema are used to set the initialization of an iterative method since a root is probably located between the adjacent extrema. For this, all the extrema must be sorted first including the upper and lower bounds. Given $n$ the number of extrema, let $p_i$ be the $i$-th element in the sorted list. Note that $p_0$ is the lower bound and $p_{n+1}$ is the upper bound. $p_i$ is an extremum sorted in increasing order only when $1 \le i \le n$. The possible value of $n$ is always $4$, $2$, or $0$.

Case 1. $n = 4$

Case 2. $n = 2$

Case 3. $n = 0$

Then, which range should be selected? It depends that $f(x)$ is increasing or decreasing in that range. But, in both cases, surely any root cannot be found if $f(p_{i-1}) f(p_i) > 0$. As another corner case, $f(p_{i-1}) f(p_i) = 0$ means that $f(p_{i-1})$ or $f(p_i) = 0$ is the root. However, it is safe to assume that $f(p_{i-1}) \ne 0$ since this search is left-to-right and will double skip when $f(p_i) \ge 0$ happens as follows.

If $f(x)$ is increasing in $[p_{i-1}, p_i]$,

• $p_i$ is the root when $f(p_i) = 0$, and skip $[p_i, p_{i+1}]$ range because this range does not need to be searched.
• There is no root if $f(p_{i-1}) f(p_i) > 0$, and skip $[p_i, p_{i+1}]$ range because this range does not need to be searched.
• There exists a root when $f(p_i) > 0$.

If $f(x)$ is decreasing in $[p_{i-1}, p_i]$,

• $p_i$ is the root when $f(p_i) = 0$, and skip $[p_i, p_{i+1}]$ range because this range does not need to be searched.
• There is no root if $f(p_{i-1}) f(p_i) > 0$, and skip $[p_i, p_{i+1}]$ range because this range does not need to be searched.
• There exists a root when $f(p_i) < 0$.

Note that the case that $f(x)$ is increasing above the $x$-axis or $f(x)$ is decreasing below the $x$-axis is naturally skipped.

Step 4. Ostrowski’s method

After selecting ranges containing a root, the iterative method can be run in these ranges. Since the increasing or decreasing trend in each range is not changed, the initialization of the iterative method may be set as follows. $$\begin{aligned} \frac{f(p_{i-1}) + f(p_i)}{2} \end{aligned}$$

Newton’s method or Halley’s method might be used for this step, but Ostrowski’s two-point method yields a better efficiency index than both the Newton and the Halley methods since it reaches a fourth-order convergence rate. Ostrowski’s method can be derived from double Newton’s method, and its geometric approach looks like the below figure.

Let $y_n$ be the updated result of $x_n$ from the Newton’s method. Then, $$\begin{aligned} y_n = x_n - \frac{f(x_n)}{f'(x_n)} \end{aligned}$$

Now, let $M$ be the midpoint of $(y_n, 0)$ and $(x_n, f(x_n))$. The intersection between the $x$-axis and the line drawn through $M$ and $(y_n, f(y_n))$ is considered as the updated point, $x_{n+1}$. From the similarity, $$\begin{aligned} \frac{f(y_n)}{y_n - x_{n+1}} = \frac{f(x_n)/2}{(x_n + y_n)/2 - x_{n+1}} = \frac{f(x_n)}{x_n + y_n - 2x_{n+1}} \end{aligned}$$

After arranging this equation and substituting $y_n$ by the form of $x_n$, $$\begin{aligned} &\quad f(y_n)(x_n + y_n - 2x_{n+1}) = (y_n - x_{n+1}) f(x_n) \\\\ \Longrightarrow &\quad x_{n+1} (f(x_n) - 2f(y_n)) = y_n f(x_n) - f(y_n) (x_n + y_n) \\\\ \Longrightarrow &\quad x_{n+1} (f(x_n) - 2f(y_n)) = \left( x_n - \frac{f(x_n)}{f'(x_n)} \right) f(x_n) - f(y_n) (x_n + x_n - \frac{f(x_n)}{f'(x_n)}) \\\\ \Longrightarrow &\quad x_{n+1} (f(x_n) - 2f(y_n)) = x_n (f(x_n) - 2f(y_n)) - \frac{f(x_n)}{f'(x_n)} (f(x_n) - f(y_n)) \\\\ \Longrightarrow &\quad x_{n+1} (f(x_n) - 2f(y_n)) = x_n (f(x_n) - 2f(y_n)) - \frac{f(x_n)}{f'(x_n)} (f(x_n) - 2f(y_n) + f(y_n)) \\\\ \Longrightarrow &\quad x_{n+1} (f(x_n) - 2f(y_n)) = x_n (f(x_n) - 2f(y_n)) - \frac{f(x_n)}{f'(x_n)} (f(x_n) - 2f(y_n)) - \frac{f(x_n) f(y_n)}{f'(x_n)} \\\\ \Longrightarrow &\quad x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} - \frac{f(x_n) f(y_n)}{f'(x_n) (f(x_n) - 2f(y_n))} \end{aligned}$$

In conclusion, this method is divided into two steps. $$\begin{aligned} \begin{cases} \; y_n = x_n - \cfrac{f(x_n)}{f'(x_n)} \\\\ \; x_{n+1} = y_n - \cfrac{f(x_n) f(y_n)}{f'(x_n) (f(x_n) - 2f(y_n))} \end{cases} \end{aligned}$$

It is worth noting that this method’s convergence order is reduced when encountering multiple roots. However, step 3 would already handle if the multiple roots exist because this case could be caught by testing $p_i = 0$. Also, it is guaranteed that each range $[p_{i-1}, p_i]$ has a root since its increasing or decreasing trend is consistent.

References

[1] Fast and Stable Polynomial Root Finders - Part Six

[2] Miodrag Petkovic, Beny Neta, Ljiljana Petkovic, and Jovana Dzunic. 2013. MULTIPOINT METHODS FOR SOLVING NONLINEAR EQUATIONS (1st. ed.). Academic Press, Inc., USA.