$$\require{cancel}$$

# 1.5: The Solution of Polynomial Equations

The Newton-Raphson method is very suitable for the solution of polynomial equations, for example for the solution of a quintic equation:

$a_0 + a_1 x + a_2 x^2 + a_3 x^3 + a_4 x^4 + a_5 x^5 = 0 . \label{1.5.1}$

Before illustrating the method, it should be pointed out that, even though it may look inelegant in print, in order to evaluate a polynomial expression numerically it is far easier and quicker to nest the parentheses and write the polynomial in the form

$a_0 + x(a_1 + x(a_2 + x(a_3 + x(a_4 + xa_5)))). \label{1.5.2}$

Working from the inside out, we see that the process is a multiplication followed by an addition, repeated over and over. This is very easy whether the calculation is done by computer, by calculator, or in one's head.

For example, evaluate the following expression in your head, for $$x = 4$$:

$2 - 7x + 2x^2 - 8x^3 - 2x^4 + 3x^5 . \nonumber$

You couldn't? But now evaluate the following expression in your head for $$x = 4$$ and see how (relatively) easy it is:

$2 + x(-7 + x(2 + x(-8 + x (-2 + 3x)))). \nonumber$

Fortran

As an example of how efficient the nested parentheses are in a computer program, here is a FORTRAN program for evaluating a fifth degree polynomial. It is assumed that the value of x has been defined in a FORTRAN variable called X, and that the six coefficients $$a_0, a_1, ... a_5$$ have been stored in a vector as $$\text{A}(1), \ \text{A}(2),... \ \text{A}(6)$$.

$$\text{Y} = 0 .$$
$$\text{DO1I} = 1,5$$
$$1 \quad \text{Y} = (\text{Y + A}(7-\text{I}))^* \text{X}$$
$$\text{Y} = \text{Y} + \text{A}(1)$$

The calculation is finished!

We return now to the solution of

$f(x) = a_0 + a_1x + a_2 x^2 + a_3 x^3 + a_4 x^4 + a_5 x^5 = 0. \label{1.5.3}$

We have $f^\prime (x) = a_1 + 2a_2 x + 3a_3 x^2 + 4 a_4 x^3 + 5a_5 x^4 . \label{1.5.4}$

Now $x = x - f / f^\prime , \label{1.5.5}$

and after simplification,

$x = \frac{-a_0 + x^2 ( a_2 + x(2a_3 + x(3a_4 + 4a_5 x )))}{a_1 + x(2a_2 + x(3a_3 + x(4a_4 + 5a_5 x)))}, \label{1.5.6}$

which is now ready for numerical iteration.

For example, let us solve

$205 + 111x + 4x^2 -31x^3 - 10x^4 + 3x^5 = 0 \label{1.5.7}$

A reasonable first guess could be obtained by drawing a graph of this function to see where it crosses the $$x$$-axis, but, truth to tell, the Newton-Raphson process usually works so well that one need spend little time on a first guess; just use the first number that comes into your head, for example, $$x = 0$$. Subsequent iterations then go

\begin{array}
-1.846 \ 847 \\
-1.983 \ 713 \\
-1.967 \ 392 \\
-1.967 \ 111 \\
-1.967 \ 110 \\
\nonumber
\end{array}

A question that remains is: How many solutions are there? The general answer is that an nth degree polynomial equation has n solutions. This statement needs to be qualified a little. For example, the solutions need not be real. The solutions may be imaginary, as they are, for example, in the equation

$1 + x^2 = 0 \label{1.5.8}$

or complex, as they are, for example, in the equation

$1 + x + x^2 = 0 . \label{1.5.9}$

If the solutions are real they may not be distinct. For example, the equation

$1 - 2x + x^2 = 0 \label{1.5.10}$

has two solutions at $$x = 1$$, and the reader may be forgiven for thinking that this somewhat stretches the meaning of "two solutions". However, if one includes complex roots and repeated real roots, it is then always true that an $$n$$th degree polynomial has $$n$$ solutions. The five solutions of the quintic equation we solved above, for example, are

\begin{array}{c c c}
4.947 \ 845 \\
2.340 \ 216 \\
-1.967 \ 110 \\
-0.993 \ 808 & + & 1.418 \ 597i \\
-0.993 \ 808 & - & 1.418 \ 597i \\
\nonumber
\end{array}

Can one tell in advance how many real roots a polynomial equation has? The most certain way to tell is to plot a graph of the polynomial function and see how many times it crosses the $$x$$-axis. However, it is possible to a limited extent to determine in advance how many real roots there are. The following "rules" may help. Some will be fairly obvious; others require proof.

The number of real roots of a polynomial of odd degree is odd. Thus a quintic equation can have one, three or five real roots. Not all of these roots need be distinct, however, so this is of limited help. Nevertheless a polynomial of odd degree always has at least one real root. The number of real roots of an equation of even degree is even - but the roots need not all be distinct, and the number of real roots could be zero.

An upper limit to the number of real roots can be determined by examining the signs of the coefficients. For example, consider again the equation

$205 + 111x + 4x^2 -31x^3 -10x^4 + 3x^5 = 0 . \label{1.5.11}$

The signs of the coefficients, written in order starting with $$a_0$$, are

$+++--+\nonumber$

Run your eye along this list, and count the number of times there is a change of sign. The sign changes twice. This tells us that there are not more than two positive real roots. (If one of the coefficients in a polynomial equation is zero, i.e. if one of the terms is "missing", this does not count as a change of sign.)

Now change the signs of all coefficients of odd powers of $$x$$:

$+-++--\nonumber$

This time there are three changes of sign. This tells us that there are not more than three negative real roots.

In other words, the number of changes of sign in $$f(x)$$ gives us an upper limit to the number of positive real roots, and the number of changes of sign in $$f(−x)$$ gives us an upper limit to the number of negative real roots.

One last "rule" is that complex roots occur in conjugate pairs. In our particular example, these rules tell us that there are not more than two positive real roots, and not more than three negative real roots. Since the degree of the polynomial is odd, there is at least one real root, though we cannot tell whether it is positive or negative.

In fact the particular equation, as we have seen, has two positive real roots, one negative real root, and two conjugate complex roots.