The Lin-Bairstow Method

The Lin-Bairstow Method

Quadratic Synthetic Division

Let the polynomial of degree n have coefficients .Then has the familiar form

(1).

Letbe a fixed quadratic term.Then can be expressed as

(2),

whereis the remainder when is divided by.Hereis a polynomial of degreeand can be represented by

(3).

If we setand,then

(4),
where
(5)

and equation (4) can be written

(6).

The terms in (6) can be expanded so that is represented in powers ofx.

(7)

The numbersare found by comparing the coefficients ofin equations (1) and (7).The coefficientsofandare computed recursively.

(8)Set ,and

,and then

for.

Example.Use quadratic synthetic division to divideby.
Solution.

Heuristics

In the days when "hand computations" were necessary, the quadratic synthetic division tableau (or table) was used.The coefficientsof the polynomial are entered on the first row in descending order, the second and third rows are reserved for the intermediate computation steps(and)and the bottom row contains the coefficients,and.

Using vector coefficients

As mentioned above, it is efficient to store the coefficientsof a polynomial of degree n in the vector.Notice that this is a shift of the index for and the polynomialis written in the form

.

Given the quadratic,the quotientand remainderare


and
.

The recursive formulas for computing the coefficientsofare

,and

,and then

for.

The Lin-Bairstow Method

We now build on the previous idea and develop the Lin-Bairstow's method for finding a quadratic factorof.Suppose that we start with the initial guess

(9)

and thatcan be expressed as

.

Whenuandvare small, the quadratic (9)is close to a factor of.We want to find new valuesso that

(10)

is closer to a factor ofthan the quadratic (9).

Observe thatuandvare functions ofrands, that is

,and
.

The new valuessatisfy the relations

,and
.

The differentials of the functionsuandvare used to produce the approximations


and

The new valuesare to satisfy

,and
.

When the quantitiesare small, we replace the above approximations with equations and obtain the linear system:


(11)

All we need to do is find the values of the partial derivatives , , and and then use Cramer's rule to compute.Let us announce that the values of the partial derivatives are



where the coefficients are built upon the coefficients given in (8) and are calculated recursively using the formulas

(12)Set ,and

,and then

for.

The formulas in (12) use the coefficients in (8).Since

,and
,and

the linear system in (11)can be written as

Cramer's rule can be used to solve this linear system.The required determinants are

,,and.

and the new valuesare computed using the formulas

,
and
.

The iterative process is continued until good approximations torandshave been found.If the initial guessesare chosen small, the iteration does not tend to wander for a long time before converging.When,the larger powers ofxcan be neglected in equation (1) and we have the approximation

.

Hence the initial guesses forcould beand,provided that.

If hand calculations are done, then the quadratic synthetic division tableau can be extended to form an easy way to calculate the coefficients .

Bairstow's method is a special case of Newton's method in two dimensions.

Algorithm (Lin-Bairstow Iteration).To find a quadratic factor ofgiven an initial approximation.

Mathematica Subroutine (Lin-Bairstow Iteration).