Numerical analysis Nonlinear equations Theorem

Laguerre's method

Builds on Root of a polynomial Multiplicity of a root Rate of convergence Complex numbers

Statement

Let $p$ be a polynomial of degree $n \ge 2$ with complex coefficients. For a point $x$ with $p(x) \ne 0$ , put $G = \frac{p'(x)}{p(x)}, \qquad H = G^2 - \frac{p''(x)}{p(x)}, \qquad a = \frac{n}{G \pm \sqrt{(n - 1)(nH - G^2)}},$ where the sign is chosen so that the denominator has the larger absolute value. Laguerre's method is the iteration $x_{k+1} = x_k - a$ , with $G, H, a$ computed at $x = x_k$ . Then:

If $r$ is a root of $p$ of multiplicity $1$ , then for $x_0$ close enough to $r$ the iterates converge to $r$ with order $3$ .
If all roots of $p$ are real, then for every real $x_0$ the iterates stay real and converge to a root of $p$ .

Remarks

The formula comes from a model of $p$ near $x$ . Assume that one root $r$ is at distance $a = x - r$ , and that the other $n - 1$ roots all sit at a common distance $b$ . The identities $G = \sum_i \frac{1}{x - r_i}$ and $H = \sum_i \frac{1}{(x - r_i)^2}$ over the roots $r_i$ then give two equations for $a$ and $b$ , whose solution is the formula above. For polynomials with only real roots, a real starting point between two consecutive roots leads to one of these two roots. A real starting point outside all roots leads to the nearest root on that side. At a multiple root the convergence is only linear. The square root can be non-real, so the method also finds the complex roots of real polynomials.

Going deeper

For a student

The method uses $p$ , $p'$ and $p''$ , which Horner's scheme evaluates cheaply. Its convergence from almost any start makes it a robust choice for finding all roots one at a time, with deflation after each root. Its behaviour on polynomials with only real roots is a rare case of guaranteed global convergence.

Reading path

To understand this page from the ground up, read these 5 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Tag	`Y277TCXZ9Z`
URI	`m2://Y277TCXZ9Z`
Kind	statement, theorem
Writing	W0 stub
MSC	65H04
Status	This copy of the site has no build data. Run `m2 status Y277TCXZ9Z`.
About	Root of a polynomial
Uses	Root of a polynomial, Multiplicity of a root, Rate of convergence, Complex numbers
Same as	Wikidata Q1171964 Wikipedia Laguerre's method

Markdown · JSON · Edit on GitHub

What this page needs for W1

a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.