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 x2+px+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 x2-px-q, then a quotient polynomial Qn-2(x) 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 fn-2(x) 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 bi (i = 0,…., n) can be obtained by the recurrence relation

If x2-px-q is the factor of the function pn(x) then the remainder R(x) = 0 and the root of x2-px-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 b0 and b1 are functions of p and q we have Taylor series expansion such that 

For ∆s, ∆r << 1, O(∆r2, ∆s2)) 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 ai is replaced with bi and bi with ci 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]