CREATE OWN LIBRARY

To find the complex roots, the Bairstow method is very useful. As the complex roots occur in pair which always produces a quadratic factor, this method extracts the quadratic factor of the form ${\mathbf{x}}^{\mathbf{2}}\mathbf{+}\mathbf{px}\mathbf{+}\mathbf{q}$ from that polynomial. The quadratic factor may give a pair of complex roots or a pair of real roots.

DERIVATION

Let the polynomial of degree n be:

If it is divided by quadratic factor ${\mathbf{x}}^{\mathbf{2}}\mathbf{-}\mathbf{px}\mathbf{-}\mathbf{q}$, then a quotient polynomial ${\mathrm{Q}}_{\mathrm{n}-2}\left(\mathrm{x}\right)$ of degree (n - 2) and a remainder term which is a polynomial of degree 1 like Rx + S can be found.

Now the quotient will be also a polynomial ${\mathrm{f}}_{\mathrm{n}-2}\left(\mathrm{x}\right)$ i.e. 

And the remainder will be the linear function 

Since this quotient and the remainder are obtained by the standard synthetic division then the co-efficient ${\mathrm{b}}_{\mathrm{i}}$ (i = 0,…., n) can be obtained by the recurrence relation

If ${\mathbf{x}}^{\mathbf{2}}\mathbf{-}\mathbf{px}\mathbf{-}\mathbf{q}$ is the factor of the function ${\mathrm{p}}_{\mathrm{n}}\left(\mathrm{x}\right)$ then the remainder R(x) = 0 and the root of ${\mathbf{x}}^{\mathbf{2}}\mathbf{-}\mathbf{px}\mathbf{-}\mathbf{q}$ are the roots of the function also. 

The values of p and q are based on some guess. 

So this method reduces the determination of the values of p and q such that R(x) = 0. For finding these values it uses a strategy that is similar to Newton Raphson’s method.

Since both ${\mathrm{b}}_0$ and ${\mathrm{b}}_1$ are functions of p and q we have Taylor series expansion such that 

For ∆s, ∆r << 1, $\mathrm{O}(∆{\mathrm{r}}^2, ∆{\mathrm{s}}^2)$) tends to 0, which means the second and the higher-order may be neglected, so ∆r, ∆s are the improvements of r and s respectively which may be obtained  by equating

In the recurrence relation, the ${\mathrm{a}}_{\mathrm{i}}$ is replaced with ${\mathrm{b}}_{\mathrm{i}}$ and ${\mathrm{b}}_{\mathrm{i}}$ with ${\mathrm{c}}_{\mathrm{i}}$ we get

Where

These systems of equations may be written as:

Now these equations can be solved for (∆s,  ∆r) and turn can be used to improve the values of r, s to (r + ∆r, s + ∆s)

GRAPHICAL REPRESENTATION

INPUT: 

A polynomial and the initial guesses

OUTPUT: 

The complex root

PROCESS:

Step 1: [Bairstow’s method]
	Step 1.1. Set dp ← 0
	Step 1.2. Set dq ← 0
	Step 1.3. Read d [the degree of polynomial]
	Step 1.4. for i in range(0, d) repeat
			Read a[i]
		[End of ‘for’ loop]
	Step 1.5. Read p [the initial guess of p]
	Step 1.6. Read q [the initial guess of q]
	Step 1.7. Set c[0] ← b[0] ← a[0]
		   Set b[1] ← a[1] – p × b[0]
		   Set c[1] ← b[1] – p × c[0]
		for i = 2 to d repeat
			Set b[i] ← a[i] – p × b[i - 1] – q × b[i - 2]
			Set c[i] ← b[i] – p × c[i - 1] – q × c[i - 2]
		[End of ‘for’ loop]
		Set dn ← c[d - 2] × c[d - 2] - c[d - 3] × (c[d - 1] - b[d - 1])
		Set dp ← (b[d - 1] × c[d - 2] - b[d] × c[d - 3])/dn
		Set dq ← (b[d] × c[d - 2] - b[d - 1] × (c[d - 1] - b[d - 1]))/dn
		Set p ← p + dp 
		Set q ← q + dq
		while dp > 0.01 or dq > 0.01 repeat Step 1.7.
	Step 1.8. print p, q
[End of Bairstow Method]