Appendix A.
The Cause of Divergence and Hunting.
A.1 Divergence.
In the development of the Bairstow Method, the iterated values of the
remainder coefficients are given by a Taylor series expansion, thus
|
|
|
b1 ( r + Dr,s + Ds ) = b1 ( r,s ) + Dr |
¶b1 ( r,s )
¶r
|
+ Ds |
¶b1 ( r,s )
¶s
|
+ ¼ |
|
|
|
b0 ( r + Dr,s + Ds ) = b0 ( r,s ) + Dr |
¶b0 ( r,s )
¶r
|
+ Ds |
¶b0 ( r,s )
¶s
|
+ ¼ |
|
|
|
| (A.1) |
where b1( ) and b0( ) are the coefficient of x and the constant term
in the division remainder.
This leads to
|
|
|
b1 ( r + Dr,s + Ds ) = b1 ( r,s ) + c2 Dr + c3 Ds + e1 |
|
|
|
b0 ( r + Dr,s + Ds ) = b0 ( r,s ) + c1 Dr + c2 Ds + e2 |
|
|
|
| (A.2) |
where c1, c2 and c3 are functions of r and s and the coefficients
of the original equation, and e1 and e2 are second and higher order terms in the Taylor series
expansion. If the method is to converge, the term on the LHS must tend to
zero. The values of Dr and Ds are obtained by ignoring the
e terms and assuming the LHS of (A.2) is indeed zero. This then
leads to,
|
|
|
Ds = |
c1 b1 ( r,s ) - c2 b0 ( r,s )
c22 - c1 c3
|
|
|
|
|
Dr = |
c2 b0 ( r,s ) - c3 b1 ( r,s )
c22 - c1 c3
|
|
|
|
|
| (A.3) |
Substituting these terms back into (A.2) then gives
|
|
|
b1 ( r + Dr,s + Ds ) = e1 |
|
|
|
b0 ( r + Dr,s + Ds ) = e2 |
|
|
|
| (A.4) |
So that, possible divergence is apparently due to the second and higher
order terms in the Taylor series expansion becoming dominant. These terms
are higher order functions of r and s, and the coefficients of the original
equation, which are fixed.
Let the e terms here be given by just the second order terms in
the Taylor series expansion, then
|
|
|
e1 = |
( Dr )2
2!
|
|
¶2b1 ( r,s )
¶r2
|
+ |
( Ds )2
2!
|
|
¶2b1 ( r,s )
¶s2
|
|
|
|
|
e2 = |
( Dr )2
2!
|
|
¶2b0 ( r,s )
¶r2
|
+ |
( Ds )2
2!
|
|
¶2b0 ( r,s )
¶s2
|
|
|
|
|
| (A.5) |
For a quartic polynomial, in which the coefficient of the highest exponent
has been normalised to unity
|
|
|
|
¶b1 ( r,s )
¶s
|
= a3 + 2r = c3 |
|
|
|
|
¶b1 ( r,s )
¶r
|
= |
¶b0 ( r,s )
¶s
|
= a2 + 2s + 2ra3 + 3r2 = c2 |
|
|
|
|
¶b0 ( r,s )
¶r
|
= a1 + 2sa3 + 6rs + 2ra2 + 3r2a3 + 4r3 = c1 |
|
|
|
| (A.6) |
So that
|
|
|
|
¶2b1 ( r,s )
¶s2
|
= |
¶c3
¶s
|
= 0 |
|
|
|
|
¶2b1 ( r,s )
¶r2
|
= |
¶c2
¶r
|
= 2a3 + 6r |
|
|
|
|
¶2b0 ( r,s )
¶s2
|
= |
¶c2
¶s
|
= 2 |
|
|
|
|
¶2b0 ( r,s )
¶r2
|
= |
¶c1
¶r
|
= 6s + 2a2 + 6ra3 + 12r2 |
|
|
|
| (A.7) |
where in (A.6) and (A.7) the "a" parameters are the coefficients of the
original equation.
Substitution of (A.7) into (A.5) then gives
|
|
|
e1 = |
( Dr )2
2!
|
( 2a3 + 6r ) |
|
|
|
e2 = |
( Dr )2
2!
|
( 6s + 2a2 + 6ra3 + 12r2 ) + ( Ds )2 |
|
|
|
| (A.8) |
In (A.8), the coefficients of (Dr)2 and (Ds)2 are
finite and from their form cannot be the source of divergence. Thus if
divergence occurs it must be because Dr and Ds themselves
diverge.
From (A.3) these terms will only diverge if
Substitution of (A.6) into (A.9) yields
|
|
|
c22 - c1 c3 = r4 + 8a3 r3 + ( 6s + 5a2 + 5a32 ) r2 + ( 43 as + 2a2 a3 - 2a32 s - 6a2 s - a1 a3 ) r + 4a2 s + a22 - 2a32 s - a1 a3 |
|
|
|
| (A.10) |
and thus divergence can occur via the iteration process when r approaches any
of the roots of (A.10). These roots clearly depend upon the value of s, and
in the divergence avoider in this application therefore, it is sufficient,
when necessary, to vary only s by a small amount to move r away from these
roots, and ensure that the method converges.
Also note that with Dr and Ds as the ultimate source of
divergence, the primary terms in (A.2) are also subject to this phenomenon
and consequently, under these conditions, (A.4) is not a valid relationship.
For other higher order polynomials, the equivalent equation to (A.10) will
be of the same order as the polynomial, giving more possibilities for
divergence, but the same criteria applies with regard to avoidance.
M3 Version 1.0.0
Ó
P.G.Bass, January 2010
|