Algebraic Solution of Polynomials

There are many treatments of the solution of polynomial equations up to degree four in the literature (i.e. the quartic, cubic, quadratic and trivial linear cases). Many of them are difficult to follow. Some contain steps that are difficult to implement on a computer (such as: “select the real value”, i.e. the value “with zero imaginary part”). However, amongst all the methods there are some real gems. Here is an explanation of those methods that I feel are the simplest to follow, and to implement.

Firstly, some general transformations.

Reduction of General Polynomial to Monic

Given a general degree-n polynomial (where a_n \ne 0)

a(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_2 x^2 + a_1 x + a_0

we can form the monic polynomial (with leading coefficient b_n = 1)

b(x) = x^n + b_{n-1} x^{n-1} + \cdots + b_2 x^2 + b_1 x + b_0

by defining b_i = \dfrac{a_i}{a_n}.

The polynomial b(x) has the same roots (zeros) as a(x). If a(x) is depressed (see below), then so is b(x), so b(x) is monic depressed.

Depression of General and Monic Polynomials

Given a general degree-n polynomial

a(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_2 x^2 + a_1 x + a_0

we can form the depressed polynomial (with no x^{n-1} term)

c(y) = c_n y^n + c_{n-2} y^{n-2} + c_{n-3} y^{n-3} + \cdots + c_2 y^2 + c_1 y + c_0

by defining x = y - \dfrac{a_{n-i}}{n a_n}.

Then, c_n = a_n and c_{n-1} = 0, but the other c_i are more complicated. For example, if n=4, then c_2 = \dfrac{8 a_4 a_2 - 3 a_3^2}{8 a_4}.

The polynomial c(y) does not generally have the same roots as a(x); they are related by the above substitution: y is a root of c(y) iff (if and only if) x is a root of a(x).

If a(x) is monic (see above), then so is c(y), so c(y) is monic depressed.

The order of transforming a general polynomial to monic and depressed forms does not matter.

Now we can move on to root-finding…

Solution of Quadratic (Degree 2)

Given a general quadratic polynomial equation

c x^2 + b x + a = 0

(noting that I have reversed the usual naming of the coefficients for consistency with what follows), we have the familiar formula

x = \dfrac{-b \pm \sqrt{b^2 - 4ac}}{2c}
(the denominator would be 2a with the conventional naming).

Less familiar is the formula

x = \dfrac{2a}{-b \mp \sqrt{b^2 - 4ac}}
(the numerator would be 2c with the conventional naming).

For completeness, and following the methods used below, we can alternatively form the monic depressed form of this equation:

let x = y - \dfrac{b}{2c}

Then y^2 + \dfrac{4 a c - b^2}{4 c^2} = 0 is immediately soluble.

A note on terminology here: p(x) is a polynomial which has roots, whereas p(x)=0 and p_1(x)=p_2(x) are polynomial equations, which have solutions.

Solution of Cubic (Degree 3)

Given a general cubic polynomial equation, we form the monic depressed form

x^3 + b x + a = 0.

We assume that a \ne 0, otherwise 0 is a root, and we can factor an (x-0) (i.e. just x) out of this equation to obtain a quadratic. Similarly, we assume b \ne 0.

I’m afraid, somewhat “out of the air”, we pull the substitution

x = y - \dfrac{b}{3y}, to obtain

y^3 + a - \dfrac{b^3}{27 y^3} = 0

which we multiply through by y^3 thus

y^6 + a y^3 - \dfrac{b^3}{27} = 0.

We can further substitute y = t^{\frac{1}{3}} \approx \sqrt[3]{t} (i.e. y^3 = t), to see that what we have is essentially just a quadratic:

t^2 + a t - \dfrac{b^3}{27} = 0.

Therefore, we solve this for t

t = \dfrac{-a \pm \sqrt{a^{2} + \dfrac{4}{27} b^{3}}}{2}

and back-subsitute to get our roots x. Incidentally, although we get two values t_0 and t_1 for t, we only get three (rather than six) values for y, as each is duplicated. Therefore, there is no problem with false roots.

These are the roots of the monic depressed case; thus, finally, we must back-substitute through the transformation back to the original (possibly non-monic non-depressed) polynomial.

Solution of Quartic (Degree 4)

Given a general quartic polynomial equation, we form the monic depressed form

x^4 + c x^2 + b x + a = 0.

We assume that a \ne 0, otherwise 0 is a root, and we can factor an (x-0) (i.e. just x) out of this equation to obtain a cubic. Similarly, we assume b \ne 0, otherwise we have a quadratic in x^2.

If we can factor the left-hand side of this equation as the biquadratic

(x^2+px+s)(x^2+qx+t),

then we have two quadratic to solve, and we are through. Therefore we expand this:

x^4 + (p+q) x^3 + (s+t+pq)x^2 + (pt+qs)x + st = 0

Matching the coefficients, we have:

p+q = 0 (from the missing x^3 term in the depressed form);
s+t+pq = c;
pt+qs = b; and
st = a.

Thus we immediately have:

q=-p;

c = s+t-p^2;
b = p(t-s);

c+p^2 = t+s;
b/p = t-s.

Note also that, generally

(t+s)^2 = t^2 + s^2 + 2st;
(t-s)^2 = t^2 + s^2 - 2st.

So, 4a = 4st = (t+s)^2 + (t-s)^2 = (c+p)^2-(b/p)^2

So rearranging, and multiplying by p^2:

p^6 + 2c p^4 + (c^2-4a) p^2 - b^2 = 0.

This is cubic in p^2. Thus we can solve for p. Then, we have

q = -p;
t = \frac{1}{2} (c + p^2 + b/p);
s = \frac{1}{2} (c + p^2 - b/p).

Thus we can back-substitute into our biquadratic.

Again, these are the roots of the monic depressed case; thus, finally, we must back-substitute through the transformation back to the original polynomial.

For an example, see my later post with an example of solving a quartic.

Higher Powers

Galois

According to Galois Theory, the general polynomial of degree greater than four is not algebraically soluble (so called by radicals).

Patterns and Other Attacks

However, sometimes the particular coefficients of a particular higher-degree polynomial, make it soluble.

For example, if the polynomial is palindromic, then it can be transformed to a lower-degree polynomial. If its coefficients are all rational or integral, then repeated roots (if any) may be factored out by an exact method, possibly reducing the degree. All rational and complex rational roots may be found in a finite number of steps, using the rational root theorem; these may then be factored out, reducing the degree.

For more information, please see my polynomials.pdf from the Q site (now superceded by Pure). This document is actually a guide to using my polynomial library, implemented in Q, but it does contain some further details of polynomials.

Advertisements

One Response to “Algebraic Solution of Polynomials”

  1. Rob Says:

    [2014-11-21: corrected a sign error in the section on the cubic, and added the explicit formula for the roots of the resulting quadratic.]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: