Numerical analysis Nonlinear equations Theorem

Graeffe's method

Builds on Root of a polynomial Complex numbers

Statement

Let $p(x) = a \prod_{i=1}^n (x - x_i)$ be a polynomial of degree $n \ge 1$ with complex coefficients and roots $x_1, \dots, x_n$ .

There is a unique polynomial $q$ with $q(x^2) = (-1)^n p(x) p(-x)$ , and $q(y) = a^2 \prod_{i=1}^n (y - x_i^2)$ . So the roots of $q$ are the squares of the roots of $p$ .
Let $p_0 = p$ , let $p_{k+1}$ be obtained from $p_k$ as in clause 1, and write $p_k(y) = \sum_{j=0}^n b_j^{(k)} y^j$ . Suppose that $\abs{x_1} > \abs{x_2} > \cdots > \abs{x_n} > 0$ . Then for each $m = 1, \dots, n$ , $\abs{x_m} = \lim_{k \to \infty} \abs{\frac{b_{n-m}^{(k)}}{b_{n-m+1}^{(k)}}}^{1/2^k}.$

Remarks

Clause 1: $p(-x) = a \prod_i (-x - x_i) = (-1)^n a \prod_i (x + x_i)$ , so $(-1)^n p(x) p(-x) = a^2 \prod_i (x^2 - x_i^2)$ . Clause 2: the roots of $p_k$ are $y_i = x_i^{2^k}$ , and their moduli separate very fast. By the relations between roots and coefficients, $b_{n-m}^{(k)} / b_{n-m+1}^{(k)}$ is a ratio of elementary symmetric functions of the $y_i$ , and the ratio is dominated by $-y_m$ as $k \to \infty$ . For example, $p(x) = x^2 - 3x + 2$ has roots $2$ and $1$ , and one step gives $q(y) = y^2 - 5y + 4$ , with roots $4$ and $1$ . The hypothesis of distinct moduli is needed for clause 2. For $p(x) = x^3 - 1$ the three roots have modulus $1$ , but every $p_k$ equals $y^3 - 1$ , so $b_2^{(k)} / b_3^{(k)} = 0$ and the formula gives $0$ instead of $1$ for $m = 1$ . The method gives only the moduli of the roots; the signs or arguments need extra work.

Going deeper

For a student

Each squaring step costs about $n^2$ operations and needs no starting guess. The coefficients grow or shrink very fast, so a practical version must work with scaled numbers or logarithms. The squaring step, also called the Dandelin–Graeffe step, reappears in modern root finders, for example to estimate root moduli in the splitting circle method.

Reading path

To understand this page from the ground up, read these 3 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	`RHPQG175AH`
URI	`m2://RHPQG175AH`
Kind	statement, theorem
Writing	W0 stub
MSC	65H04
Status	This copy of the site has no build data. Run `m2 status RHPQG175AH`.
About	Root of a polynomial
Uses	Root of a polynomial, Complex numbers
Same as	Wikidata Q5592179 Wikipedia Graeffe's method