Please use this identifier to cite or link to this item: https://doi.org/10.15480/882.313
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.
URI: http://tubdok.tub.tuhh.de/handle/11420/315
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 (tub.dok)

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

Page view(s)

217
Last Week
3
Last month
4
checked on May 23, 2019

Download(s)

114
checked on May 23, 2019

Google ScholarTM

Check

Export

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