Bernoulli's method

This article is about the root-finding algorithm. For an unrelated topic in ordinary differential equation, see Bernoulli differential equation. For an unrelated topic in fluid dynamics, see Bernoulli's principle.

In numerical analysis, Bernoulli's method, named after Daniel Bernoulli, is a root-finding algorithm which calculates the largest root (or zero) in magnitude of a polynomial. The method uses a quotient ratio of successive terms in a sequence calculated using only the coefficients of the given polynomial and does not require an initial starting root approximation. Since it converges slowly with a linear order, it can be used for finding an initial guess for another root-finding algorithm, such as Newton's method.

The method

Given a polynomial p written as

$$p(z)=a_{0}z^{d}+a_{1}z^{d-1}+...+a_{d}$$

where d is the degree of p. Pick d arbitrary starting values for a series x written as ${\textstyle \{x_{n}\}=x_{-d+1},x_{-d},...,x_{-1},x_{0}}$, where usually ${\textstyle x=\{0,0,0,...,0,1\}}$ is used for initial starting values. Then the terms in the sequence are computed with:

$$x_{n}=-{\frac {a_{1}x_{n-1}+a_{2}x_{n-2}+...+a_{d}x_{n-d}}{a_{0}}}$$

The sucessive ratios of two successive numbers in the sequence x, written as ${\textstyle q_{n}={\frac {x_{n+1}}{x_{n}}}}$ in the limit tends to the largest root in magnitude of p.

Derivation of the method

Consider the n-th order difference equation:

$$a_{n}x_{m}+a_{n-1}x_{m-1}+...+a_{0}x_{m-n}=0(a_{n}\neq 0;m=n,n+1,...)$$

which has a solution

$$x_{m}=c_{1}r_{1}^{m}+c_{2}r_{2}^{m}+...+c_{n}r_{n}^{m}$$

where ${\textstyle r_{i}}$ is a root of p and ${\textstyle c_{i}}$ are suitable constants. By division of successive terms in this sequence we get

$${\frac {x_{m+1}}{x_{m}}}={\frac {c_{1}r_{1}^{m+1}+c_{2}r_{2}^{m+1}+...+c_{n}r_{n}^{m+1}}{c_{1}r_{1}^{m}+c_{2}r_{2}^{m}+...+c_{n}r_{n}^{m}}}$$

Assuming that ${\textstyle r_{1}}$ is the dominant root such that ${\textstyle |r_{1}|>|r_{k}|,k=2,3,...,n}$ then by factoring out ${\textstyle r_{1}}$ results in

$${\frac {x_{m+1}}{x_{m}}}=r_{1}{\frac {c_{1}+c_{2}({\frac {r_{2}}{r_{1}}})^{m+1}+...+c_{n}({\frac {r_{n}}{r_{1}}})^{m+1}}{c_{1}+c_{2}({\frac {r_{2}}{r_{1}}})^{m}+...+c_{n}({\frac {r_{n}}{r_{1}}})^{m}}}$$

and because each root division has a larger denominator than numerator they will tend to zero, then ${\textstyle \lim _{m\to \infty }{\frac {x_{m+1}}{x_{m}}}=r_{1}}$. This does assume that ${\textstyle c_{1}\neq 0}$, yet Blum shows that initial starting values of the sequence x using all 0's followed by a final 1, avoids such an issue.

Convergence

Bernoulli's method will converge on the largest root in magnitude of a given polynomial with a linear order of convergence. This can lead to problems when there is multiplicity of the dominant root, a dominant conjugate pair, or otherwise multiple equidistant dominant roots, although variations on Bernoulli's method exist to combat these issues. To speed convergence, Alexander Aitken developed his Aitken delta-squared process as part of an improvement on his extension to Bernoulli's method, which also found all of the roots simultaneously.

In the case of converging on the smallest root of a polynomial (instead of the largest), the coefficients of the original polynomial are reversed, the method applied on the new polynomial, and the result inverted, which would give the smallest root of the original. When using root deflation with something like Horner's method, deflating from the smallest root is more stable. Another extension of Bernoulli's method is the Quotient-Difference method, which also finds all roots simultaneously, even though it can be unstable. Given the slow convergence of Bernoulli's method, and the instability of QD method, they can instead be used as reliable ways to find initial starting values for other root-finding algorithms, rather than iterated until tolerance.

Example

Let ${\textstyle p(z)=z^{2}-z-1=0}$. This means that ${\textstyle a_{0}=1,a_{1}=-1,a_{2}=-1}$ so updating the recurrence equation gives

$$x_{n}=-{\frac {(-1)x_{n-1}+(-1)x_{n-2}}{(1)}}=x_{n-1}+x_{n-2}$$

Using the recommended initial series of all 0's and a final 1 gives ${\textstyle x_{-1}=0,x_{0}=1}$ and from this generates the following table.

xn	qn
0	−
1	1
1	2
2	1.5
3	1.666
5	1.6
8	1.625
13	1.61538461538
21	1.61904761905
34	1.61764705882
55	1.61818181818

This eventually converges on 1.618034, also known as the Golden ratio, which is the largest root of the example polynomial. This sequence x, also happens to be the famous Fibonacci sequence. The method would work even if the sequence used different starting values instead of 0 and 1; the quotient ratio will eventually be the same.

See also

• Graeffe's method
• List of things named after members of the Bernoulli family