FOR FREE CONTENT

Baristow Method

Back to Programming

Description

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 $x^{2} + 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 $x^{2} - px - q$ , then a quotient polynomial $Q_{n - 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 $f_{n - 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 $b_{i}$ (i = 0,…., n) can be obtained by the recurrence relation

If $x^{2} - px - q$ is the factor of the function $p_{n} (x)$ then the remainder R(x) = 0 and the root of $x^{2} - 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 $b_{0}$ and $b_{1}$ are functions of p and q we have Taylor series expansion such that

For ∆s, ∆r << 1, $O (∆ r^{2}, ∆ 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 $a_{i}$ is replaced with $b_{i}$ and $b_{i}$ with $c_{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

Algorithm

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]

Code

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

Debashis Roy Faculty of Computer Science Department, JCC College, University of Calcutta

Please Login to Bookmark