Bernoulli method

A method for finding the real root of algebraic equations of the type

$$ \tag{* } a _ {0} x ^ {n} + a _ {1} x ^ {n-1} + \dots + a _ {n} = 0 $$

with the largest modulus (absolute value). The method was proposed by D. Bernoulli [1] and is based on the following principle. Let $ y(0) \dots y(n - 1) $ be random numbers and let the values of $ y(n), y(n + 1) \dots $ be calculated by the following difference equation:

$$ a _ {0} y (m+n) + a _ {1} y (m+n-1) + \dots + a _ {n} y (m) = 0 . $$

In general, as $ m \rightarrow \infty $, the expression $ y(m + 1)/y(m) $ tends to the value of the root of equation (*) with the largest modulus.

References

[1]	D. Bernoulli, Comm. Acad. Sci. Imper. Petropolitanae , 3 , Petropolis (1732) pp. 62–69
[2]	Sir Edmund Whittaker, G. Robinson, "The calculus of observations. A treatise on numerical mathematics" (4th ed.) Blackie & Son (1954) p.99. Zbl 0058.33603

Comments

The expression $ y (m +1 )/y (m) $ tends to the root of largest modulus only if this root is simple and if no other roots of the same maximum modulus occur. If not, then one can proceed as follows (cf. [a1]). Let there be one (not necessarily real) root $ x _ {p} $ of largest modulus, with multiplicity $ p $. Then the solution of the linear difference equation for $ y (m) $ is

$$ y (m) \approx \ \sum _ {j = 0 } ^ { {p } - 1 } C _ {j} \left ( \begin{array}{c} p \\ j \end{array} \right ) x _ {p} ^ {m} , $$

as $ m \rightarrow \infty $. This expression is the solution of a linear difference equation with characteristic polynomial $ (x - x _ {p} ) ^ {p} $, so that $ y (m) $ satisfies the linear difference equation

$$ \tag{a1 } y (m) \approx \ \sum _ {j = 0 } ^ { {p } - 1 } x _ {p} ^ {j} \left ( \begin{array}{c} p \\ j \end{array} \right ) y (m - j) $$

as $ m \rightarrow \infty $. If $ p \leq 2 $, then this equation can be solved explicitly in $ x _ {p} $, otherwise (a1) is rewritten with $ m $ replaced by $ m - 1, m - 2 \dots $ and the resulting equations are solved in $ x _ {p} , x _ {p} ^ {2} , . . . $.

If two roots $ x _ {p} $ and $ x _ {q} $( of multiplicity $ p $ and $ q $) of the same maximum modulus occur, then $ y (m) $ satisfies, as $ m \rightarrow \infty $, a linear difference equation with $ (x - x _ {p} ) ^ {p} (x - x _ {q} ) ^ {q} $ as characteristic polynomial, and (a1) must be replaced by the corresponding difference equation of order $ p + q $.

References

[a1]	F.B. Hildebrand, "Introduction to numerical analysis" , McGraw-Hill (1956)
[a2]	A.S. Householder, "The numerical treatment of a single nonlinear equation" , McGraw-Hill (1970)