Polynomial Solver Programs

The TI-84 programs described (and down-loadable) below will find all roots to the pertinent polynomial equation, be they real- or complex-valued. Additionally, roots of multiplicity greater than one are printed out by the programs as individual roots, e.g., a root of multiplicity 2 will be printed out twice.

Order 2

As has been known since antiquity, the two roots of

(1)

are given by the Quadratic Formula, i.e., by

(2)

The TI-84 program P2.8xp implements equation (2).

Order 3

The three solutions to the the third order, i.e., cubic, polynomial

(3)

are given by the so-called Cubic Formula. The form of the formula used is given on the Alternate Form of the Cubic Formula page. The TI-84 program P3.8xp implements the said formula.

Order 4

The four solutions to the the fourth order, i.e., quartic, polynomial

(4)

are given by the so-called Quartic Formula. The form of the formula used is given on the Alternate Form of the Quartic Formula page. The TI-84 program P4.8xp implements the said formula.

Numerical Accuracy

The solver programs for polynomial equations of orders 5 through 8 described below depend upon a numerical method, viz., Newton-Raphson iteration. Such iteration is ill-conditioned (i.e., possibly inaccurate) when the polynomial in question has roots of multiplicity greater than one, and the ill-conditionedness increases with the order of root multiplicity (be the multiple roots real- or complex-valued). Notwithstanding, my experience with the programs is that 3 to 4 digits of accuracy in the roots is still achieved in the most ill-conditioned cases.

Order 5

For polynomial equations of order higher than order 4, it can be shown that no closed-form solution exists for the roots of such polynomials. Therefore, some sort of numerical methed must be used in their solution. Although many techniques may be used to solve such polynomial equations, the technique used herein depends upon factoring the polynomial equation of interest into polynomials which may then be solved in closed form.

For the fifth order equation, the factorization is into quadratic and cubic parts, i.e.,

(5)

which, upon expanding the second line, gives

(6)

Equations (6) are a non-linear 5 by 5 system, which may be solved via Newton-Raphson iteration. Thus, according to equation (6), define the residual vector as

(7)

where the goal is to solve [r] = [0]. The vector of unknowns is

(8)

Now, according to the schematic below, where i and j range from 1 to 5, and where superscript I stands for the currently best guess for the solution [a], and superscript I+1 stands for an improved guess for the solution [a]

one may write the slope as

(9)

which, when multiplying both sides by a_j^I+1-a_j^I, gives

(10)

Equation (10) in matrix form is

(11)

where

(12)

Taking the partial derivatives in equation (12) then gives

(13)

Finally, the factorization of the polynomial of order 5 is obtained by solving equation (11) for [a] until convergence is reached. Knowing the conveged value of [a], i.e., knowing the factorization, the five solutions to equation (5) are then obtained by applying the Quadratic and Cubic formulas. The TI-84 program P5.8xp implements the above procedure.

Order 6

To solve the polynomial equation of order 6, factor it into quadratic and quartic parts, i.e.,

(14)

which upon expansion yields the 6 by 6 non-linear system

(15)

to solve. Equations (15) are then solved via Newton-Raphson iteration in the manner as is described above for the case of the order 5 equation. Having the factorization so-obtained, the six roots of equation (14) are then obtained by application of the Quadratic and Quartic formulas. The TI-84 program P6.8xp implements the above procedure.

Order 7

To solve the polynomial equation of order 7, factor it into cubic and quartic parts, i.e.,

(16)

which upon expansion yields the 7 by 7 non-linear system

(17)

to solve. Equations (17) are then solved via Newton-Raphson iteration in the manner as is described above for the case of the order 5 equation. Having the factorization so-obtained, the seven roots of equation (16) are then obtained by application of the Cubic and Quartic formulas. The TI-84 program P7.8xp implements the above procedure.

Order 8

To solve the polynomial equation of order 8, factor it into two quartic parts, i.e.,

(18)

which upon expansion yields the 8 by 8 non-linear system

(19)

to solve. Equations (19) are then solved via Newton-Raphson iteration in the manner as is described above for the case of the order 5 equation. Having the factorization so-obtained, the eight roots of equation (18) are then obtained by application of the Quartic formula (twice). The TI-84 program P8.8xp implements the above procedure.

Ad Infinitum

Obviously, the procedure used above to solve polynomial equations of orders 5 through 8 can be carried out for all higher orders. If the polynomial is odd-ordered, then it should be factored into a single cubic and other even-ordered polynomials. Similarly, an even-ordered polynomial should be factored into all even-ordered polynomials. In this way, the nature of any complex-conjugate roots will be preserved.