Bairstow's method

Bairstow's method

In numerical analysis, Bairstow's method is an efficient algorithm for finding the roots of a real polynomial of arbitrary degree. The algorithm first appeared in the appendix of the 1920 book "Applied Aerodynamics" by Leonard Bairstow. The algorithm finds the roots in complex conjugate pairs using only real arithmetic.

See root-finding algorithm for other algorithms.

Description of the method

Bairstow's approach is to use Newton's method to adjust the coefficients "u" and "v" in the quadratic x^2 + ux + v until its roots are also roots of the polynomial being solved. The roots of the quadratic may then be determined, and the polynomial may be divided by the quadratic to eliminate those roots. This process is then iterated until the polynomial becomes quadratic or linear, and all the roots have been determined.

Long division of a polynomial :P(x)=sum_{i=0}^n a_i x^i by x^2 + ux + v yields a quotient:Q(x)=sum_{i=0}^n b_i x^i and a remainder cx+d such that: P(x)=(x^2+ux+v)left(sum_{i=0}^n b_i x^i ight) + (cx+d). The variables c, d, and the {b_i} are functions of u and v. They can be found recursively as follows.:,b_n = b_{n-1} = 0, :,b_i=a_{i+2}-ub_{i+1}-vb_{i+2} qquad (i=n-2,ldots,0), :,c=a_1-ub_0-vb_1,:,d=a_0-vb_0.The quadratic evenly divides the polynomial when:c(u,v)=d(u,v)=0. ,Values of u and v for which this occurs can be discovered by picking starting values and iterating Newton's method in two dimensions:egin{bmatrix}u\ vend{bmatrix} :=egin{bmatrix}u\ vend{bmatrix} - egin{bmatrix}frac{partial c}{partial u}&frac{partial c}{partial v}\ [3pt] frac{partial d}{partial u} &frac{partial d}{partial v}end{bmatrix}^{-1} egin{bmatrix}c\ dend{bmatrix}until convergence occurs.

Performance

Bairstow's algorithm inherits the quadratic convergence of Newton's method, except in the case of quadratic factors of multiplicity higher than 1, when convergence can be rather slow.

External links

* [http://mathworld.wolfram.com/BairstowsMethod.html Bairstow's Algorithm on Mathworld]
* [http://library.lanl.gov/numerical/bookfpdf.html Numerical Recipes in Fortran 77 Online]
* [http://www.savetman.com/roots.html Compute roots of polynomials interactively using Bairstow's Method on savetman.com]
* [http://www.polarhome.com:793/~amate2/php/polysolver_en.php Determine the roots of polynomials (gr(P)<= 10) using Bairstow's Method]
* [http://www.vtk.org/doc/nightly/html/classvtkMath.html LinBairstowSolve, an open-source C++ implementation of the Lin-Bairstow method is available as a method of the VTK library]


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Bairstow — could refer to:* Andrew Bairstow (1975 ), English cricketer. * David Bairstow (1951 ), English cricketer. * Mark Bairstow, Australian rules footballer. * Scott Bairstow, actor. * Leonard Bairstow, English academics, originator of Bairstow s… …   Wikipedia

  • Leonard Bairstow — Sir Leonard Bairstow, CBE Royal Society FRS, FRAeS (1880 1963) was a son of Uriah Bairstow, a wealthy Halifax, West Yorkshire man and keen mathematician. Leonard was born in 1880 in Halifax he is best remembered for is work in aviation and for… …   Wikipedia

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

  • Root-finding algorithm — A root finding algorithm is a numerical method, or algorithm, for finding a value x such that f(x) = 0, for a given function f. Such an x is called a root of the function f. This article is concerned with finding scalar, real or complex roots,… …   Wikipedia

  • List of mathematics articles (B) — NOTOC B B spline B* algebra B* search algorithm B,C,K,W system BA model Ba space Babuška Lax Milgram theorem Baby Monster group Baby step giant step Babylonian mathematics Babylonian numerals Bach tensor Bach s algorithm Bachmann–Howard ordinal… …   Wikipedia

  • The Crossley Heath School — Motto Omne Bonum Ab Alto (All good things come from above) Established 1985 (in current form) Heath Grammar School (1585) Crossley and Porter School (1887) …   Wikipedia

  • John Birkinshaw — was a 19th Century railway engineer from Bedlington, Northumberland noted for his invention of wrought iron rails in 1820. Up till this point, rail systems had used either wooden rails, which were totally incapable of supporting steam engines, or …   Wikipedia

  • United Kingdom company law — Beside the River Thames, the City of London is a global financial centre. Within the Square Mile, the London Stock Exchange lies at the heart of the United Kingdom s corporations. United Kingdom company law is the body of rules that concern… …   Wikipedia

  • Theory of Portuguese discovery of Australia — Although most historians hold that the European discovery of Australia began in 1606 with the voyage of the Dutch navigator Willem Janszoon on board the Duyfken , a number of alternative theories have been put forward. Precedence of discovery has …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”