Namespaces
Variants
Actions

Difference between revisions of "Bernoulli method"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
 +
<!--
 +
b0156301.png
 +
$#A+1 = 29 n = 0
 +
$#C+1 = 29 : ~/encyclopedia/old_files/data/B015/B.0105630 Bernoulli method
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
A method for finding the real root of algebraic equations of the type
 
A method for finding the real root of algebraic equations of the type
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015630/b0156301.png" /></td> <td valign="top" style="width:5%;text-align:right;">(*)</td></tr></table>
+
$$ \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 [[#References|[1]]] and is based on the following principle. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015630/b0156302.png" /> be random numbers and let the values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015630/b0156303.png" /> be calculated by the following difference equation:
+
with the largest modulus (absolute value). The method was proposed by D. Bernoulli [[#References|[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:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015630/b0156304.png" /></td> </tr></table>
+
$$
 +
a _ {0} y (m+n) + a _ {1} y
 +
(m+n-1) + \dots +
 +
a _ {n} y (m)  = 0 .
 +
$$
  
In general, as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015630/b0156305.png" />, the expression <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015630/b0156306.png" /> tends to the value of the root of equation (*) with the largest modulus.
+
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====
 
====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  D. Bernoulli,  ''Comm. Acad. Sci. Imper. Petropolitanae'' , '''3''' , Petropolis  (1732)  pp. 62–69</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  E.T. Whittaker,   G. Robinson,   "Mathematische Bearbeitung von Resultaten der Observation" , Leningrad-Moscow  (1935) (In Russian; translated from German)</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[1]</TD> <TD valign="top">  D. Bernoulli,  ''Comm. Acad. Sci. Imper. Petropolitanae'' , '''3''' , Petropolis  (1732)  pp. 62–69</TD></TR>
 +
<TR><TD valign="top">[2]</TD> <TD valign="top">  Sir Edmund Whittaker, G. Robinson, "The calculus of observations. A treatise on numerical mathematics" (4th ed.) Blackie & Son (1954) p.99. {{ZBL|0058.33603}}</TD></TR>
 +
</table>
  
 +
====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. [[#References|[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}
  
====Comments====
+
\right )
The expression <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015630/b0156307.png" /> 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. [[#References|[a1]]]). Let there be one (not necessarily real) root <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015630/b0156308.png" /> of largest modulus, with multiplicity <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015630/b0156309.png" />. Then the solution of the linear difference equation for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015630/b01563010.png" /> is
+
x _ {p}  ^ {m} ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015630/b01563011.png" /></td> </tr></table>
+
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
  
as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015630/b01563012.png" />. This expression is the solution of a linear difference equation with characteristic polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015630/b01563013.png" />, so that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015630/b01563014.png" /> 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}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015630/b01563015.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a1)</td></tr></table>
+
\right )
 +
y (m - j)
 +
$$
  
as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015630/b01563016.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015630/b01563017.png" />, then this equation can be solved explicitly in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015630/b01563018.png" />, otherwise (a1) is rewritten with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015630/b01563019.png" /> replaced by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015630/b01563020.png" /> and the resulting equations are solved in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015630/b01563021.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015630/b01563022.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015630/b01563023.png" /> (of multiplicity <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015630/b01563024.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015630/b01563025.png" />) of the same maximum modulus occur, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015630/b01563026.png" /> satisfies, as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015630/b01563027.png" />, a linear difference equation with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015630/b01563028.png" /> as characteristic polynomial, and (a1) must be replaced by the corresponding difference equation of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b015/b015630/b01563029.png" />.
+
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====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  F.B. Hildebrand,  "Introduction to numerical analysis" , McGraw-Hill  (1956)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  A.S. Householder,  "The numerical treatment of a single nonlinear equation" , McGraw-Hill  (1970)</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  F.B. Hildebrand,  "Introduction to numerical analysis" , McGraw-Hill  (1956)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  A.S. Householder,  "The numerical treatment of a single nonlinear equation" , McGraw-Hill  (1970)</TD></TR></table>

Latest revision as of 09:54, 29 May 2020


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)
How to Cite This Entry:
Bernoulli method. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Bernoulli_method&oldid=12883
This article was adapted from an original article by L.N. Dovbysh (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article