Bairstow's method

In numerical analysis, Bairstow's method is an efficient algorithm for finding the roots of a real polynomial of arbitrary degree. The algorithm first appeared in the appendix of the 1920 book Applied Aerodynamics by Leonard Bairstow. The algorithm finds the roots in complex conjugate pairs using only real arithmetic.

See root-finding algorithm for other algorithms.

Description of the method

Bairstow's approach is to use Newton's method to adjust the coefficients u and v in the quadratic

x

2

+

u

x

+

v

{\displaystyle x^{2}+ux+v}

until its roots are also roots of the polynomial being solved. The roots of the quadratic may then be determined, and the polynomial may be divided by the quadratic to eliminate those roots. This process is then iterated until the polynomial becomes quadratic or linear, and all the roots have been determined.

Long division of the polynomial to be solved

P

(

x

)

=

∑

i

=

0

n

a

i

x

i

{\displaystyle P(x)=\sum _{i=0}^{n}a_{i}x^{i}}

by

x

2

+

u

x

+

v

{\displaystyle x^{2}+ux+v}

yields a quotient

Q

(

x

)

=

∑

i

=

0

n

−

2

b

i

x

i

{\displaystyle Q(x)=\sum _{i=0}^{n-2}b_{i}x^{i}}

and a remainder

c

x

+

d

{\displaystyle cx+d}

such that

P

(

x

)

=

(

x

2

+

u

x

+

v

)

(

∑

i

=

0

n

−

2

b

i

x

i

)

+

(

c

x

+

d

)

.

{\displaystyle P(x)=(x^{2}+ux+v)\left(\sum _{i=0}^{n-2}b_{i}x^{i}\right)+(cx+d).}

A second division of

Q

(

x

)

{\displaystyle Q(x)}

by

x

2

+

u

x

+

v

{\displaystyle x^{2}+ux+v}

is performed to yield a quotient

R

(

x

)

=

∑

i

=

0

n

−

4

f

i

x

i

{\displaystyle R(x)=\sum _{i=0}^{n-4}f_{i}x^{i}}

and remainder

g

x

+

h

{\displaystyle gx+h}

with

Q

(

x

)

=

(

x

2

+

u

x

+

v

)

(

∑

i

=

0

n

−

4

f

i

x

i

)

+

(

g

x

+

h

)

.

{\displaystyle Q(x)=(x^{2}+ux+v)\left(\sum _{i=0}^{n-4}f_{i}x^{i}\right)+(gx+h).}

The variables

c

,

d

,

g

,

h

{\displaystyle c,\,d,\,g,\,h}

, and the

{

b

i

}

,

{

f

i

}

{\displaystyle \{b_{i}\},\;\{f_{i}\}}

are functions of

u

{\displaystyle u}

and

v

{\displaystyle v}

.