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

(1)        .

Let    be a fixed quadratic term.  Then can be expressed as
    
(2)        ,  

where    is the remainder when   is divided by  .  Here    is a polynomial of degree    and can be represented by  

(3)        .  

If we set    and    ,  then

(4)        ,   
    where    
(5)          

and equation (4) can be written

(6)        .  

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

(7)          

The numbers    are found by comparing the coefficients of     in equations (1) and (7).  The coefficients     of    and  are computed recursively.

(8)        Set     ,    and  

            ,    and then  

               for    .  

Proof  Lin-Bairstow Method  Lin-Bairstow Method

Example 1.  Use quadratic synthetic division to divide       by   .  
Solution 1.

Heuristics
    
    In the days when "hand computations" were necessary, the quadratic synthetic division tableau (or table) was used.  The coefficients    of 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  .

Example 2.  Use the "quadratic synthetic division tableau" to divide    by  .  
Solution 2.

Using vector coefficients

    As mentioned above, it is efficient to store the coefficients    of a polynomial   of degree n in the vector  .  Notice that this is a shift of the index for and the polynomial    is written in the form  
    
        .  
        
Given the quadratic  ,  the quotient    and remainder    are

        
    and
        .   

The recursive formulas for computing the coefficients    of    are  

        ,   and      
        
        ,   and then  
        
            for    .  

Example 3.  Use the vector form of quadratic synthetic division to divide       by   .  
Solution 3.

The Lin-Bairstow Method

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

(9)        
          
and that    can be expressed as  

        .    

When  u  and  v  are small, the quadratic (9)  is close to a factor of  .  We want to find new values    so that  

(10)        

is closer to a factor of    than the quadratic (9).  

    Observe that  u  and  v  are functions of  r  and  s, that is   

        ,   and   
        .  

The new values    satisfy the relations  

        ,   and   
        .  

The differentials of the functions  u  and  v  are used to produce the approximations

        
    and
          

The new values    are to satisfy

        ,  and   
        .

When the quantities    are 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 values    are computed using the formulas  

        ,   
    and   
        .  

Proof  Lin-Bairstow Method  Lin-Bairstow Method

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

        .

Hence the initial guesses for    could be    and  ,  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 of     given an initial approximation  .  

Computer Programs  Lin-Bairstow Method  Lin-Bairstow Method

Mathematica Subroutine (Lin-Bairstow Iteration).

Example 4.  Given   .  Start with    and    and use the Lin-Bairstow method to find a quadratic factor of  .  
Solution 4.

Research Experience for Undergraduates

Lin-Bairstow Method  Lin-Bairstow Method  Internet hyperlinks to web sites and a bibliography of articles.  

Download this Mathematica Notebook Lin-Bairstow Method

(c) John H. Mathews 2004