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]
ADVANTAGES
1. It uses real arithmetic only to find out the complex roots of the given polynomial.
2. It is an efficient algorithm for finding the roots of a polynomial of arbitrary degree.
APPLICATIONS
1. It is used to find the complex root of a polynomial.
Contributed by