Previous |  Up |  Next

Article

Keywords:
epsilon-inflation; P-contraction; contraction; verification algorithms; interval computation; nonlinear equations; eigenvalues; singular values
Summary:
For contractive interval functions $ [g] $ we show that $ [g]([x]^{k_0}_\epsilon ) \subseteq \int ([x]^{k_0}_\epsilon ) $ results from the iterative process $ [x]^{k+1} := [g]([x]^k_\epsilon ) $ after finitely many iterations if one uses the epsilon-inflated vector $ [x]^k_\epsilon $ as input for $ [g] $ instead of the original output vector $ [x]^k $. Applying Brouwer’s fixed point theorem, zeros of various mathematical problems can be verified in this way.
References:
[A87b] G. Alefeld: Rigorous Error Bounds for Singular Values of a Matrix Using the Precise Scalar Product. Computerarithmetic, E. Kaucher, U. Kulisch and Ch. Ullrich (eds.), Teubner, Stuttgart, 1987, pp. 9–30. MR 0904306
[AH83] G. Alefeld and J. Herzberger: Introduction to Interval Computations. Academic Press, New York, 1983. MR 0733988
[AS86] G. Alefeld and H. Spreuer: Iterative improvement of componentwise error bounds for invariant subspaces belonging to a double or nearly double eigenvalue. Computing 36 (1986), 321–334. DOI 10.1007/BF02240207 | MR 0843941
[CM78] O. Caprani and K. Madsen: Iterative methods for interval inclusion of fixed points. BIT 18 (1978), 42–51. DOI 10.1007/BF01947742 | MR 0478583
[G89] K. Grüner: Solving the Complex Algebraic Eigenvalue Problem with Verified High Accuracy. Accurate Numerical Algorithms, A Collection of Research Papers, Research Reports ESPRIT, Project 1072, DIAMOND, Vol. 1, Ch. Ullrich and J. Wolff von Gudenberg (eds.), Springer, Berlin, 1989, pp. 59–78.
[K90] S. König: On the Inflation Parameter Used in Self-Validating Methods. Contributions to Computer Arithmetic and Self-Validating Numerical Methods, Ch. Ullrich (ed.), Baltzer, IMACS, Basel, 1990, pp. 127–132. MR 1131093
[M94b] G. Mayer: Result Verification for Eigenvectors and Eigenvalues. Topics in Validated Computations, J. Herzberger (ed.), Elsevier, Amsterdam, 1994, pp. 209–276. MR 1318956 | Zbl 0813.65077
[M95a] G. Mayer: Über ein Prinzip in der Verifikationsnumerik. Z. angew. Math. Mech. 75 (1995), S II, S 545–S 546.. Zbl 0850.65104
[M95b] G. Mayer: Epsilon-inflation in verification algorithms. J. Comp. Appl. Math. 60 (1995), 147–169. DOI 10.1016/0377-0427(94)00089-J | MR 1354653 | Zbl 0839.65059
[M95c] G. Mayer: On a unified representation of some interval analytic algorithms. Rostock. Math. Kolloq. 49 (1995), 75–88. MR 1392204 | Zbl 0861.65049
[M96] G. Mayer: Success in Epsilon-Inflation. Scientific Computing and Validated Numerics, G. Alefeld, A. Frommer and B. Lang (eds.), Akademie Verlag, Berlin, 1996, pp. 98–104. MR 1394227 | Zbl 0848.65035
[N90] A. Neumaier: Interval Methods for Systems of Equations. Cambridge University Press, Cambridge, 1990. MR 1100928 | Zbl 0715.65030
[R80] S. M. Rump: Kleine Fehlerschranken bei Matrixproblemen. Thesis, Universität Karlsruhe, 1980. Zbl 0437.65036
[R83] S. M. Rump: Solving Algebraic Problems with High Accuracy. A New Approach to Scientific Computation, U. W. Kulisch and W. L. Miranker (eds.), Academic Press, New York, 1983, pp. 53–120. MR 0751813 | Zbl 0597.65018
[R86] S. M. Rump: New Results in Verified Inclusions. Accurate Scientific Computation, Lecture Notes in Computer Science Vol.  235, W. L. Miranker and R. A. Toupin (eds.), Springer, Berlin, 1986, pp. 31–69. MR 0868284
[R92] S. M. Rump: On the solution of interval linear systems. Computing 47 (1992), 337–353. DOI 10.1007/BF02320201 | MR 1155502 | Zbl 0753.65030
Partner of
EuDML logo