Two-sided estimate

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 $ 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, [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 [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). 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 [5]–[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

[1]	P.V. Galkin, "Estimates for the Lebesgue constants" Proc. Steklov Inst. Math. , 1–4 (1971) Trudy Mat. Inst. Steklov. , 109 (1971) pp. 3–5
[2]	L. Collatz, "Eigenwertaufgaben mit technischen Anwendungen" , Akad. Verlagsgesell. Geest u. Portig K.-D. (1949)
[3]	L. Collatz, "Functional analysis and numerical mathematics" , Acad. Press (1966) (Translated from German)
[4]	N.S. Bakhvalov, "Numerical methods: analysis, algebra, ordinary differential equations" , MIR (1977) (Translated from Russian)
[5]	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
[6]	E.Ya. Remez, Zap. Prirodn.-Tekhn. Viddilu Akad. Nauk UkrSSR , 1 (1931) pp. 1–38
[7a]	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
[7b]	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
[8]	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
[9]	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

References

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