Please use this identifier to cite or link to this item:
Fulltext available Open Access
Title: New results on verified inclusions
Language: English
Authors: Rump, Siegfried M. 
Issue Date: 1985
Source: Proceedings of the Symposium on Accurate Scientific Computation 1985, p. 31-69
Abstract (english): The computational results of traditional numerical algorithms on computers are usually good approximations to the solution of a given problem. However, no verification is provided for some bound on the maximum relative error of the approximation. As can be demonstrated by ill-conditioned examples, those approximations may be drastically wrong. The algorithms based on the inclusion theory (ef. [38]) do have an automatic verification process. Rather than approximations to the solution an inclusion of the solution is computed and the correctness of the bounds together with the existence and uniqueness of the solution within the bounds is automatically verified by the computer without any effort on the part of the user. The computing time of these algorithms is of the order of a comparable, standard floating-oint algorith (such as Gaussian elimination in case of general linear systems). In the following some new results complementing the inclusion theory are given. One of the main results is that the inclusion sets need not to be convex. Therefore other types of inclusion sets such as torus-sectors can be used. Another main observation is that the new and old theorems can be proved without using fixed point theorems. Moreover improvements of existing theorems of the inclusion theory by means of weaker assumptions are presented. Another fundamental observation is the following. It is well-known that a real iteration in Rn with affine iteration function converges if and only if the spectral radius of the itaration matrix is less than one. It can be shown that a similar result holds for our inclusion algorithm: An inclusion will be achieved if and only if the spectral radius of the iteration matrix is less then one. This result is best possible. It is demonstrated by means of theorems and examples that even for extremely ill-conditioned examples very sharp inclusions of the solution are computed. The inclusions are almost always of least significant bit accuracy, i.e. the left and right bounds of the inclusion are adjacent floating-point numbers.
DOI: 10.15480/882.313
ISBN: 3-540-16798-6
Institute: Zuverlässiges Rechnen E-19 
Type: InProceedings (Aufsatz / Paper einer Konferenz etc.)
Appears in Collections:Publications with fulltext

Files in This Item:
File Description SizeFormat
Ru86.pdf5,02 MBAdobe PDFThumbnail
Show full item record

Page view(s)

Last Week
Last month
checked on Sep 20, 2020


checked on Sep 20, 2020

Google ScholarTM


Note about this record


Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.