Skip to main content
main-content

Über dieses Buch

This book is written as an introduction to the theory of error-free computation. In addition, we include several chapters that illustrate how error-free com­ putation can be applied in practice. The book is intended for seniors and first­ year graduate students in fields of study involving scientific computation using digital computers, and for researchers (in those same fields) who wish to obtain an introduction to the subject. We are motivated by the fact that there are large classes of ill-conditioned problems, and there are numerically unstable algorithms, and in either or both of these situations we cannot tolerate rounding errors during the numerical computations involved in obtaining solutions to the problems. Thus, it is important to study finite number systems for digital computers which have the property that computation can be performed free of rounding errors. In Chapter I we discuss single-modulus and multiple-modulus residue number systems and arithmetic in these systems, where the operands may be either integers or rational numbers. In Chapter II we discuss finite-segment p-adic number systems and their relationship to the p-adic numbers of Hensel [1908]. Each rational number in a certain finite set is assigned a unique Hensel code and arithmetic operations using Hensel codes as operands is mathe­ matically equivalent to those same arithmetic operations using the cor­ responding rational numbers as operands. Finite-segment p-adic arithmetic shares with residue arithmetic the property that it is free of rounding errors.

Inhaltsverzeichnis

Frontmatter

Chapter I. Residue or Modular Arithmetic

Abstract
Since an automatic digital computer is a finite machine, it is capable of representing, internally, only a finite set of numbers. Thus, any attempt to use an automatic digital computer to do arithmetic in the field of real numbers (ℝ, +, ·) is doomed to failure because ℝ is an infinite set and most of the elements in this set cannot be represented in a computer.
R. T. Gregory, E. V. Krishnamurthy

Chapter II. Finite-Segment p-adic Arithmetic

Abstract
In this chapter we are motivated to present an alternative number system, the finite-segment p-adic number system introduced by Krishnamurthy, Rao, and Subramanian [1975a], [1975b], and by Alparslan [1975]. This number system is finite and its relation to the (infinite) p-adic number system of Hensel [1908] is explained in subsequent sections.
R. T. Gregory, E. V. Krishnamurthy

Chapter III. Exact Computation of Generalized Inverses

Abstract
It is well known that every nonsingular real or complex (square) matrix A has a unique inverse which has the property that
(1.1) AA -1 = A-1 A = I.
R. T. Gregory, E. V. Krishnamurthy

Chapter IV. Integer Solutions to Linear Equations

Abstract
Consider the system of linear algebraic equations Ax = b, where A is an m x n integer matrix and b is an m-vector with integer components. In general, the solution vector will not necessarily have integer components. However, there are many situations in which we seek an integer solution to such a system.
R. T. Gregory, E. V. Krishnamurthy

Chapter V. Iterative Matrix Inversion and the Iterative Solution of Linear Equations

Abstract
In Section 5 Chapter II, we describe how to compute the Hensel code H(p, r, 1/α if we are given H(p, r, α), by using the fast iterative method based on Newton’s method. It is well known that Newton’s method for finding the reciprocal of a real number can be generalized to
(i)
the computation of the inverse of a nonsingular matrix (see, for example, Stoer and Bulirsch [1980], p. 310, where this is called Schultz’s method), and
 
(ii)
the computation of the Moore-Penrose g-inverse of an arbitrary matrix (see, for example, Ben-Israel and Greville [1974], p. 300).
 
R. T. Gregory, E. V. Krishnamurthy

Chapter VI. The Exact Computation of the Characteristic Polynomial of a Matrix

Abstract
It is not recommended, in general, that we compute the coefficients of the characteristic polynomial of a matrix as a first step in finding the eigenvalues of the matrix by polynomial root-finding techniques. This is due to the fact that if ordinary floating-point arithmetic is used, the accumulation of rounding errors will produce only approximations to the coefficients and, if the polynomial is ill-conditioned, the roots of the “approximate characteristic equation” may not be good approximations to the roots of the characteristic equation. See Wilkinson [1963], Chapter 2, for a discussion of the condition of a polynomial equation with respect to the computation of its roots.
R. T. Gregory, E. V. Krishnamurthy

Backmatter

Weitere Informationen