Reliability in Computing - The Role of Interval Methods in Scientific Computing

Front Cover

Reliability in Computing: The Role of Interval Methods in Scientific Computing

Copyright Page

Table of Contents

Contributors

Preface

Acknowledgments

Part 1: Computer Arithmetic and Mathematical Software

Chapter 1. ARITHMETIC FOR VECTOR PROCESSORS

ABSTRACT

1. INTRODUCTION

2. THE STATE OF THE ART

3. FAST COMPUTATION OF SUMS AND SCALAR PRODUCTS

4. SUMMATION WITH ONLY ONE ROW OF ADDERS

5. SYSTEMS WITH LARGE EXPONENT RANGE AND FURTHER REMARKS

6. APPLICATION TO MULTIPLE PRECISION ARITHMETIC

7. CONTEMPORARY FLOATING-POINT ARITHMETIC

8. LITERATURE

Chapter 2. FORTRAN-SC, A FORTRAN Extension for Engineering/Scientific Computation with Access to ACRITH: Language Description with Examples

Abstract

1. Introduction

2. Development of FORTRAN-SC

3. Main Language Concepts

4. Language Description with Examples

5. Implementation of FORTRAN-SC

References

Chapter 3. FORTRAN-SC A FORTRAN Extension for Engineering/Scientific Computation with Access to ACRITH: Demonstration of the Compiler and Sample Programs

Abstract

Introduction

Example 1 : Interval Newton Method

Example 2 : Automatic Differentiation

Example 3 : Runge-Kutta Method

Example 4 : Gaussian Elimination Method

Example 5 : Verified Solution of a Linear System

References

Chapter 4. Reliable Expression Evaluation in PASCAL-SC

Abstract

1. Floating-point arithmetic

2. Interval arithmetic

3. The optimal scalar product

4. Complex floating-point and complex interval arithmetic

5. Matrix and vector arithmetic

6. Accurate Operations and Problem Solving Routines

7. Transformation of arithmetic expressions

8. Solution of nonlinear systems

9. The data type dotprecision

10. Dotproduct expressions

11. Conclusion

References

Chapter 5. Floating-Point Standards — Theory and Practice

1. Introduction

2. The Standards

3. Implementations

4. Software Support

5. Conclusions

References

Chapter 6. Algorithms for Verified Inclusions: Theory and Practice

Summary

0. Introduction

1. Basic theorems

2. Practical verification on the computer

3. Interactive Programming Environment

4. References

Chapter 7. Applications of Differentiation Arithmetic

Abstract

1. Differentiation Arithmetic – Why, What, and How?

2. Why? – Motivation

3 . What? – Component tools

4. Conditions on f

5. How to use it? – Applications

6. Acknowledgements

References

Part 2: Linear and Nonlinear Systems

Chapter 8. INTERVAL ACCELERATION OF CONVERGENCE

Abstract

1. INTRODUCTION

2. EXAMPLES

3. DEFINITIONS AND NOTATION

4. INTERVAL METHODS

5. HOW CAN WE GET BOUNDS ON A GIVEN POINT-SEQUENCE ?

6. ACCELERATION OF CONVERGENCE

REFERENCES

Chapter 9. SOLVING SYSTEMS OF LINEAR INTERVAL EQUATIONS

0. Introduction

1. Bounding the solutions

2. Computing the xy's

3. Explicit formulae for x, x

4. Inverse interval matrix

References

Chapter 10. Interval Least Squares — a Diagnostic Tool

Introduction

Linearity

Interval Notation

Effects of Nonlinearity

Interval Linear Equations

Normal Equations

QR Approach

Nonlinearity Indices

Test Data

Test Results

Diagnosing Collinearity

Concluding Remarks

References

Chapter 11. Existence of Solutions and Iterations for Nonlinear Equations

1. Introduction

2. Bisection

3. Brouwer Fixed–Point Theorem

4. Avoiding the Brouwer Fixed-Point Theorem

5. Iteration methods

References

Chapter 12. INTERVAL METHODS FOR ALGEBRAIC EQUATIONS

1. Introduction

2. Notation

3. Preliminaries

4. Interval Methods for Single Equations

5. Interval Methods for Systems of Equations

References

Chapter 13. Error Questions in the Computation of Solution Manifolds of Parametrized Equations

1.Introduction

2. Discretization Errors

3. Continuation Methods

4. Triangulations and Foldpoint Calculations

5. References

Chapter 14. THE ENCLOSURE OF SOLUTIONS OF PARAMETER-DEPENDENT SYSTEMS OF EQUATIONS

1 . Introduction

2. Covering the solution set

3. Homogeneous linear interval equations

4. Numerical examples

5. Final remarks

References

Part 3: Optimization

Chapter 15. AN OVERVIEW OF GLOBAL OPTIMIZATION USING INTERVAL ANALYSIS

Abstract

1. Introduction

2. The fundamental theorem

3. Newton's method

4. Existence

5. Introductory remarks on optimization

6. Monotonicity

7. Concavity

8. Deletion of boxes where f is large

9. Feasibility

10. Termination

11. A global optimization algorithm

12. An example

13. Other examples

14. Conclusion

References

Chapter 16. Philosophy and Practicalities of Interval Arithmetic

Abstract

1.0 The scope of interval bounds

2.0 Input/Output conventions

3.0 Universal Applicability

4.0 Using Bounds on Observation Errors

5.0 Summary

Chapter 17. SOME RECENT ASPECTS OF INTERVAL ALGORITHMS FOR GLOBAL OPTIMIZATION

Summary

1. Introduction

2. Convergence properties of the algorithm

3. Global optimization over unbounded domains

4. Nonsmooth optimization

5. Numerical results

Acknowledgement

References

Chapter 18. The Use of Interval Arithmetic in Uncovering Structure of Linear Systems

ABSTRACT

I. INTRODUCTION

II. TESTS TO UNCOVER THE STRUCTURE OF ANY LINEAR SYSTEM

III. TESTS TO UNCOVER THE STRUCTURE OF THE CONSTRAINT MATRIX IN LINEAR PROGRAMMING PROBLEMS

IV. CONCLUSION

BIBLIOGRAPHY

Part 4: Operator Equations

Chapter 19. THE ROLE of ORDER in COMPUTING

1. Number systems

2. Interval lattices

3. Lattice-ordered algebras

4. Hypercubes

5. Positive linear operators

6. Random numbers

7. The binary digits of 1/ 2

8. Continued fractions

REFERENCES

Chapter 20. INTERVAL METHODS FOR OPERATOR EQUATIONS

1. Introduction

2. General model

3. Nonlinear initial value problems for ordinary differential equations

4. Comparison for nonlinear two point boundary value problems

5. Nonlinear elliptic boundary value problems. For simplicity, we only consider the

403

References

Chapter 21. Boundary Implications for Stability Properties: Present Status

1. Introduction

3. Interval matrices

4. Applications

Acknowledgement

References

Chapter 22. VALIDATING COMPUTATION IN A FUNCTION SPACE

1. Introduction

2. Ultra-arithmetic and Roundings

References

Epilogue: A Poem about My Life