View source for Two-sided estimate

<!--
t0946001.png
$#A+1 = 51 n = 0
$#C+1 = 51 : ~/encyclopedia/old_files/data/T094/T.0904600 Two\AAhsided estimate
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}}

The set of estimates of a given quantity  $  a $
from above and from below. An estimate from above is an inequality of the form  $  a \leq  A _ {1} $; 
an estimate from below is an inequality  $  a \geq  A _ {0} $, 
which has the opposite sense. The quantities  $  A _ {0} $, 
$  A _ {1} $
with the aid of which  $  a $
is estimated usually have a simpler form or can be much more readily calculated than  $  a $.

===Examples.===

1) Let  $  m $, 
$  M $
be, respectively, the minimum and the maximum of a function  $  f $
on an interval  $  [ \alpha , \beta ] $. 
The following two-sided estimate will then be valid for the integral  $  \int _  \alpha   ^  \beta  f ( x)  d x $:

$$ 
m ( \beta - \alpha )  \leq   \int\limits _  \alpha  ^  \beta  
f ( x)  dx  \leq   M ( \beta - \alpha ) ;
$$

here

$$ 
A _ {0}  =  m ( \beta - \alpha ) ,\ \ 
a  =  \int\limits _  \alpha  ^  \beta   f ( x)  dx ,\ \ 
A _ {1}  =  M ( \beta - \alpha ) .
$$

2) A two-sided estimate for the [[Lebesgue constants|Lebesgue constants]]  $  L _ {n} $
for all  $  n = 0 , 1 \dots $
is:

$$ 
0 . 9897 \dots  <  L _ {n} - 
\frac{4}{\pi  ^ {2} }
  \mathop{\rm ln}
( 2n + 1 )  \leq   1 .
$$

3) A two-sided estimate of eigenvalues. Consider the eigenvalue problem for a linear self-adjoint operator  $  T $, 
$  Tu = \lambda u $, 
in a Hilbert space  $  H $. 
One constructs an iterative process  $  Tf _ {n+} 1 = f _ {n} $, 
where  $  f _ {0} \neq 0 $. 
Since the operator  $  T $
is self-adjoint, the scalar products  $  ( f _ {m} , f _ {k} ) $
depend only on the sum  $  m+ k $
of the indices. The numbers  $  a _ {n} = ( f _ {0} , f _ {n} )= ( f _ {m} , f _ {n-} m ) $
are known as Schwartz constants, while the numbers  $  \mu _ {n+} 1 = a _ {n} / a _ {n+} 1 $
are known as Rayleigh–Schwartz ratios. If the operator  $  T $
is positive, the  $  \mu _ {n} $
form a monotone non-decreasing convergent sequence.

If  $  \lambda _ {0} $
is an eigenvalue of  $  T $, 
$  a < \lambda _ {0} < b $, 
$  a < \mu _ {2k} < b $, 
and the interval  $  ( a , b ) $
does not comprise other points of the spectrum of  $  T $, 
then

$$ 
\mu _ {2k} - 
\frac{\rho  ^ {2} }{b - \mu _ {2k} }
  \leq   \lambda _ {0}  \leq   \mu _ {2k} + 
\frac{\rho  ^ {2} }{\mu _ {2k} - a }
 ,\ \ 
\rho  ^ {2}  =  
\frac{\mu _ {2k-} 1 - \mu _ {2k} }{\mu _ {2k} }

$$

(Temple's theorem, [[#References|[3]]]). Under certain conditions the Rayleigh–Schwartz ratios converge to an eigenvalue of  $  T $.

Numerical methods for obtaining two-sided estimates (two-sided approximations) are known as two-sided methods [[#References|[4]]]. The method of constructing Rayleigh–Schwartz ratios just described is an example of a two-sided method. Some two-sided methods are based on the use of a pair of approximate formulas, with residual terms of opposite signs. For instance, let a function  $  f $
be interpolated at the points (interpolation nodes)  $  x _ {0} < x _ {1} < \dots < x _ {n} $
by the Lagrange polynomial  $  L _ {0} ( x) $
with nodes  $  x _ {0} , x _ {1} \dots x _ {n-} 1 $, 
and let  $  L _ {1} ( x) $
be the Lagrange interpolation polynomial with nodes  $  x _ {1} , x _ {2} \dots x _ {n} $(
cf. [[Lagrange interpolation formula|Lagrange interpolation formula]]). The following relations will then be valid for the residual terms:

$$ 
R _ {0} ( x)  =  f ( x) - L _ {0} ( x)  =  
\frac{f ^ { ( n) } ( \xi _ {0)} }{n!}
 ( x - x _ {0} ) \dots ( x - x _ {n-} 1 ) ,
$$

$$ 
R _ {1} ( x)  =  f ( x) - L _ {1} ( x)  =  
\frac{f ^ { ( n) } ( \xi _ {1} ) }{n!}
 ( x - x _ {1} ) \dots ( x - x _ {n} ) ,
$$

where  $  \xi _ {0} , \xi _ {1} \in [ x _ {0} , x _ {n} ] $. 
If the derivative  $  f ^ { ( n) } $
does not change sign in  $  [ x _ {0} , x _ {n} ] $, 
then  $  R _ {0} $
and  $  R _ {1} $
have opposite signs. The following two-sided estimate is valid:

$$ 
\min ( L _ {0} ( x) , L _ {1} ( x) )  \leq   f ( x)
 \leq   \max ( L _ {0} ( x) , L _ {1} ( x) ) .
$$

Two-sided methods for solving ordinary differential equations are now in a most advanced stage of development [[#References|[5]]]–[[#References|[9]]].

Two-sided methods make it possible to identify the boundaries of the domain in which the solution of the problem is known to be contained. This necessarily entails a more complicated algorithm, and a further complication of the algorithm must be accepted if the method is used in practical computations, in view of the rounding-off errors involved. Two-sided methods are used mainly in cases where a guaranteed estimate of the error is required.

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  P.V. Galkin,   "Estimates for the Lebesgue constants"  ''Proc. Steklov Inst. Math.'' , '''1–4'''  (1971)  ''Trudy Mat. Inst. Steklov.'' , '''109'''  (1971)  pp. 3–5</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  L. Collatz,   "Eigenwertaufgaben mit technischen Anwendungen" , Akad. Verlagsgesell. Geest u. Portig K.-D.  (1949)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  L. Collatz,   "Functional analysis and numerical mathematics" , Acad. Press  (1966)  (Translated from German)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  N.S. Bakhvalov,   "Numerical methods: analysis, algebra, ordinary differential equations" , MIR  (1977)  (Translated from Russian)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  E.A. Volkov,   "Effective error estimates for difference solutions of boundary value problems in ordinary differential equations"  ''Proc. Steklov Inst. Math.'' , '''112'''  (1971)  pp. 143–155  ''Trudy Mat. Inst. Steklov.'' , '''112'''  (1971)  pp. 141–151</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  E.Ya. Remez,   ''Zap. Prirodn.-Tekhn. Viddilu Akad. Nauk UkrSSR'' , '''1'''  (1931)  pp. 1–38</TD></TR><TR><TD valign="top">[7a]</TD> <TD valign="top">  A.D. Gorbunov,   Yu.A. Shakhov,   "On the approximate solution of Cauchy's problem for ordinary differential equations to a number of correct figures"  ''USSR Comp. Math. Math. Phys.'' , '''3''' :  2  (1963)  pp. 316–335  ''Zh. Vychisl. Mat. i Mat. Fiz.'' , '''3''' :  2  (1963)  pp. 239–253</TD></TR><TR><TD valign="top">[7b]</TD> <TD valign="top">  A.D. Gorbunov,   Yu.A. Shakhov,   "On the approximate solution of Cauchy's problem for ordinary differential equations to a number of correct figures II"  ''USSR Comp. Math. Math. Phys.'' , '''4''' :  3  (1964)  pp. 37–47  ''Zh. Vychisl. Mat. i Mat. Fiz.'' , '''4''' :  3  (1964)  pp. 426–433</TD></TR><TR><TD valign="top">[8]</TD> <TD valign="top">  V.I. Devyatko,   "On a two-sided approximation for the numerical integration of ordinary differential equations"  ''USSR Comp. Math. Math. Phys.'' , '''3''' :  2  (1963)  pp. 336–350  ''Zh. Vychisl. Mat. i. Mat. Fiz.'' , '''3''' :  2  (1963)  pp. 254–265</TD></TR><TR><TD valign="top">[9]</TD> <TD valign="top">  N.P. Salikhov,   "Polar difference methods of solving Cauchy's problem for a system of ordinary differential equations"  ''USSR Comp. Math. Math. Phys.'' , '''2''' :  4  (1962)  pp. 535–553  ''Zh. Vychisl. Mat. i Mat. Fiz.'' , '''2''' :  4  (1962)  pp. 515–528</TD></TR></table>

====Comments====

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  L. Collatz,   "Numerical treatment of differential equations" , Springer  (1966)  (Translated from German)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  K. Rektorys (ed.) , ''Survey of applicable mathematics'' , Iliffe  (1969)  pp. Sect. 32A</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  T.J. Rivlin,   "An introduction to the approximation of functions" , Dover, reprint  (1969)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  R.E. Moore,   "Interval analysis" , Prentice-Hall  (1966)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  D.M. Young,   R.T. Gregory,   "A survey of numerical mathematics" , Dover, reprint  (1988)</TD></TR></table>