|
Bairstow method Algorithm
|
|
|
Bairstow method is an iterative method used to find all the roots of a polynomial both the real and complex.
It is based on the idea of synthetic division of the given polynomial by a quadratic function.
|
|
|
The method divides a polynomial, `f_n(x)=a_0 + a_1x + a_2x^2 + ... + + a_nx^n`
by a quadratic function `x^2-rx-s`, where `r` and `s` are guessed values.
|
|
|
This division gives us a new polynomial `f_(n-2)(x)=b_2 + b_3x + b_4x^2 + ... + + b_nx^(n-2)`
and the remainder polynomial `R(x)=b_1(x-r)+b_0`
|
|
|
Since the quotient `f_(n-2)(x)` and the remainder `R(x)` are obtained by synthetic division the coefficients `b_i` (where i=0,1,...n)
can be obtained by the following recurrence relationship
|
|
|
`b_n=a_n`
`b_(n-1)=a_(n-1)+rb_n`
`b_(i)=a_(i)+rb_(i+1)+sb_(i+2)` for (i=n-2,...,0)
|
|
|
If `x^2-rx-s` is an exact factor of `f_n(x)` then the remainder `R(x)` is 0 and the real/complex roots of `x^2-rx-s` are the roots of `f_n(x)`.
It may be noted that `x^2-rx-s` is considered based on some guess values for `r,s`.
So Bairstow's method reduces to determining the values of `r` and `s` such that `R(x)=0`.
Since both `b_0` and `b_1` are functions of `r` and `s`, they can be expanded using Taylor series of `b_0`, `b_1` as
`b_0(r+Delta r,s+Delta s) = b_0+(del b_0)/(del r)Delta r+(del b_0)/(del s)Delta s`
`b_1(r+Delta r,s+Delta s) = b_1+(del b_1)/(del r)Delta r+(del b_1)/(del s)Delta s`
|
|
|
By setting both equations equal to 0
`(del b_0)/(del r)Delta r+(del b_0)/(del s)Delta s = -b_0`
`(del b_1)/(del r)Delta r+(del b_1)/(del s)Delta s = -b_1`
|
|
|
To solve the system of equations above, we need partial derivatives of `b_0` and `b_1` with respect to `r` and `s`.
Bairstow has shown that these partial derivatives can be obtained by a synthetic division of the `b's`, means by replacing `a_i's` with `b_i's`, and `b_i's` with `c_i's`, such that
`c_n=b_n`
`c_(n-1)=b_(n-1)+rc_n`
`c_(i)=b_(i)+rc_(i+1)+sc_(i+2)` for (i=n-2,...,1)
where `(del b_0)/(del r)=c_1, (del b_0)/(del s)=(del b_1)/(del r)=c_2, (del b_1)/(del s)=c_3`
|
|
|
This system of equations may be written as.
`c_1 Delta r+c_2 Delta s = -b_0`
`c_2 Delta r+c_3 Delta s = -b_1`
|
|
|
These equations can be solved for `Delta r` and `Delta s`, which can be used to improved the initial guess of `r` and `s`.
|
|
|
At each step, an approximate error in r and s estimated as
`|epsilon_(a,r)|=|(Delta r)/(r)|xx100%`
`|epsilon_(a,s)|=|(Delta s)/(s)|xx100%`
|
|
|
If `|epsilon_(a,r)|>epsilon_(s)` or `|epsilon_(a,s)|>epsilon_(s)`, where `epsilon_(s)` is the iteration stopping error,
then we repeat the process with the new guess `(r+Delta r,s+Delta s)`, Otherwise the roots of `f_(n)(x)` can be determined by
`x_(1,2)=(r+-sqrt(r^2+4s))/2`
|
|
|
If we want to find all the roots of `f_(n)(x)` then we have the following 3 possibilities
|
|
1.
|
If quotient polynomial `f_(n-2)(x)` is a third order or higher order polynomial then apply the Bairstow's method again to the quotient polynomial.
The previous values of `(r,s)` can be used as the starting guesses for this iteration.
|
|
2.
|
If quotient polynomial `f_(n-2)(x)` is a quadratic function then use quadratic formula to obtain the remaining two roots of `f_(n)(x)`.
|
|
3.
|
If quotient polynomial `f_(n-2)(x)` is a linear function say `ax+b=0` then the remaining single root is `x=(-b)/a`
|
