Bairstow's method

The Bairstow method is an iterative method of numerical analysis and used to determine the zeros of a polynomial. The method was first introduced in 1920 by Leonard Bairstow ( 1880-1963 ) in the appendix of his book "Applied Aerodynamics ".

Every polynomial with real coefficients can be decomposed into a product of linear and quadratic irreducible factors, also with real coefficients ( Fundamental Theorem of Algebra by Gauss, 1799). The linear factors correspond to real roots, the quadratic conjugate pairs of complex real zeros. If there is more than one real zero, so the linear factors can be combined easily into square. In order to avoid calculating with complex numbers, you can look for real quadratic factors. Bairstow the method is, in addition to the variation of the real Jenkins Traub method, one way to approximate square such factors. The real or complex zeros of this quadratic factor can then be determined using the known formula for solving quadratic equations. More zeros can be obtained from the remaining polynomial after removal of the quadratic factor.

As with any iterative method also depends on the success and the rapid convergence of the choice of a good starting point, ie an initial quadratic polynomial, from which should be almost a factor of the polynomial. The quality is thereby determined by the size of the remainder after polynomial division. In the case of a randomly selected starting point results in a behavior as is visualized in the Newton - fractal. If the polynomial to be solved multiple zeros or close to each other lying cluster of zeros, so this method may fail to find them.

Features of the method

Polynomials with real coefficients such as can also have complex zeros. With techniques such as regulators Falsi and Newton's method, which are only one zero, it is not possible to find complex roots, without the calculation is performed in the complex domain with complex arithmetic. The Bairstow method uses the property of polynomials with real coefficients, indicating that complex roots always occur in pairs, conjugated. The method finds the zeros as a couple and provides a quadratic equation with real coefficients, from which a real or complex conjugate zeros pair can be determined.

The features of the method in the summary:

• For a polynomial with real coefficients, the Bairstow method completely works in the real and
• Is also possibly occurring in pairs complex conjugate zeros (and).
• The zero point calculation is also programs available that can not deal with complex arithmetic
• In one iteration of real arithmetic is significantly faster than one iteration in a complex arithmetic.

Bairstow the method is derived from the Newton's method, and is converged as this (local) with second order.

Description of the procedure

Given a polynomial of degree n whose zeros are sought:

The coefficients of the polynomial are all real numbers. If you were to start now in a direct application of Newton's method to the equation with a real starting value, so all members of the iteration sequence were real again. To find complex roots, the bill would have to be done with complex numbers. That was in older programming languages ​​not possible without great effort.

However, have polynomials f ( x) with real coefficients the property that complex roots always occur in complex conjugate pairs, is a root, so also. The quadratic polynomial

And which has the zero points, is also a factor of the polynomial f (x) and also has only real coefficients. So instead of directly determine zeros, quadratic factors are first searched.

Is a square factor of f (x), there is another factor b (x ) of degree n- 2, which can be determined by polynomial division. Is a (x) is not a factor, then the polynomial results in a remainder R ( x), which is a linear or polynomial constant. The rest is determined here from the identity f ( x) = a ( x ) b ( x) r (x). After a comparison of coefficients, a system of quadratic equations results in the coefficients

Of the upper n-1 equations, the coefficients of b ( x ) can be from that of a (x ) and f ( x) be determined. From the last two equations, the coefficients of the polynomial result. The goal of the method is to keep them as small as possible by fitting a (x). From the calculation model can be seen that the coefficients of b ( x), and finally the remainder of the r (x) polynomials in two variables, coefficients of a (x) is. This 2x2 system can now be addressed with the Newton method.

Determining the need and the derivatives of the equations can be simplified by algebraic means.

Mathematical reasoning

It searches a factorization with a square factor a (x) and a remaining factor b (x). However, if a (x ), only one of approximate factor, leaving the division with remainder of f ( x) by a (x) with result b ( x) a remainder r (x ),

As a (x) is square, is r (x ) is linear or constant. Is a linear polynomial is now searched, so that a better approximation of a factor of f ( x). Is the polynomial improved even an exact factor, so there is a polynomial of degree n -3

In Newton's method only first order terms in the coordinates of the change vector are considered, all higher-grade terms are neglected. To first order the results by combining the two equations

This equation can be resolved into a linear equation system for the coefficients of and. However, the equation can be simplified by algebraic means further so that the linear system to be solved ultimately has two variable and as many equations.

As is true, the polynomial is already itself the representative of smallest degree in its residue class modulo a (x). As is the residue class of zero must

. apply Now also the polynomial b ( x ) modulo a (x) can be reduced by a further division with remainder is a quotient q ( x) and a linear residual p ( x) with yield. The result is

Advertised as a system of equations, this means

The determinant of the system matrix. This is different from zero, then the solution of the system and the change of the square factor g (x) as follows

For the next step is a (x) replaced by and started from scratch. One can break if the coefficients of the remainder r (x ) are all below a previously set limit.

Broad

The method is based on the following steps:

Iteration

• By polynomial division with the quadratic polynomial

• Re- division of b ( x) by a (x ) yields a new polynomial and its remainder, with an analogous recursion is used, apply it again and;

• Division with the residues is improved, the coefficients of the quadratic polynomial a (x):

• The improved starting values ​​are off

Notes to the expiration

• Determining can be considered as a solution of the following system of equations:

• The method can be numerically relatively simple, fast and low memory implementation, if one does not only calculates and stores, but in step j the used immediately to calculate the coefficients.

• As starting values ​​for the iteration one can form the quadratic polynomial for example, from the three leading coefficients, ie choose. If approximations for two zeros are present, you can also select an alternative according to the Vietaschen formulas.

• The iteration can be stopped, if present, or in the desired result accuracy, then matching zeros have been found and is a divisor of. In this case, all the coefficients are determined by, and then reduced with the new polynomial to locate the next zeroing. Because if you abdividiert of the linear factors of the zeros are obtained.

Algorithm

The program example in pseudo code describes a single iteration, in which the coefficients a0 and a1 of the quadratic polynomial by two corrections da0 and da1 be improved. Field (array ) F ( ) includes polynomial wherein in f (n ) of the coefficient of. The names of variables were chosen otherwise as in the formulas.

In the loop of the double polynomial the program variables b0, b1, b2 are in step j for the coefficients and corresponding q0, q1, q2. In the transition from step j to step j - 1, the program variables must be shifted one index coefficient, b2 b1 ← ← ← q1 and q2 b0 ← q0.

J = n      b0 = f (n)      b1 = 0      q0 = 0      q1 = 0        FOR j = n - 1 TO 0 STEP -1          b2 = b1          b1 = b0          b0 = f ( j) - a1 * b1 - b2 a0 *            q2 = q1          q1 = q0          q0 = b2 - a1 * q1 - q2 a0 *      NEXT j        M = - a0 * q1 - q0 a1 *      D = q0 * q0 - q1 M *      da1 = (b0 * q1 - q0 * b1 ) / D      da0 = ( b1 * M - b0 * q0 ) / D        a1 = a1 - da1      a0 = a0 - da0 As a result of the iteration the program variables contain a0 and a1 improved values ​​for the coefficients of

Example

It should be determined the zeros of the following polynomial:

The starting values ​​of the iteration is determined, for example, the recommendation

The iteration yields the following values ​​:

After the 8th iteration, a1 and a0 of Näherungspolynoms within the calculation accuracy were determined exactly. The solution is then given by the polynomial

The solutions of this quadratic equation are also solutions of the polynomial:

If now those two zeros abdividiert the polynomial, the quadratic polynomial can be used the same as the starting value for the next iteration.

Visualization of the convergence of the method

Similar to the Newton fractal, which visualizes the convergence of Newton's method against several zeros, one can images be created for this procedure to enable an overview of the convergence to the different square factors. In the adjacent frames, a parameterization is selected, the quadratic polynomial which maps a starting point of the method Bairstow each point ( u, v). Itself provides such a polynomial out as a factor of the given polynomial, so give points (u, v) in the upper half plane v> 0 is the complex conjugate pair as a solution set of the quadratic factor in the lower half-plane v < 0, the real couple., The polynomial f (x) k, and s = complex solution of n- 2k real solutions, it is k squared factors on the x axis and S ( s-1) / 2 such as, as combined with each other, each a real solution possible factor results.

In the white-colored points a good factor is achieved in the first iteration, the colored dots provide starting values ​​, the iteration leads to the same colored pool to one of the factors. The gradient corresponds to the number of iterations up to a good approximation, the darker, the more steps were needed. For black start values ​​, the iteration takes place in the first 100 steps is not a factor sufficient accuracy, or diverges iteration. Shown are points.

In general, you can see the convergence of this method does not guarantee, and it is sometimes very slow, how can the black and dark areas of the first image to read polynomial.

You can remedy this situation in part by the odd degree is doing by adding a zero at x = 0, that is considered the expanded polynomial, which is shown in the second image. In the third image Beispielpolynom used above was visualized.

Practically useful, however, by Newton, secant method or regulators falsi first to determine a real zero for odd degree polynomials, and then applied to the reduced polynomial degree, the straight Bairstow method.