Reliability in Computing (eBook)

The Role of Interval Methods in Scientific Computing

Ramon E. Moore (Herausgeber)

eBook Download: PDF

2014 | 1. Auflage
444 Seiten
Elsevier Science (Verlag)
978-1-4832-7784-4 (ISBN)

Infos

Perspectives in Computing, Vol. 19: Reliability in Computing: The Role of Interval Methods in Scientific Computing presents a survey of the role of interval methods in reliable scientific computing, including vector arithmetic, language description, convergence, and algorithms. The selection takes a look at arithmetic for vector processors, FORTRAN-SC, and reliable expression evaluation in PASCAL-SC. Discussions focus on interval arithmetic, optimal scalar product, matrix and vector arithmetic, transformation of arithmetic expressions, development of FORTRAN-SC, and language description with examples. The text then examines floating-point standards, algorithms for verified inclusions, applications of differentiation arithmetic, and interval acceleration of convergence. The book ponders on solving systems of linear interval equations, interval least squares, existence of solutions and iterations for nonlinear equations, and interval methods for algebraic equations. Topics include interval methods for single equations, diagnosing collinearity, interval linear equations, effects of nonlinearity, and bounding the solutions. The publication is a valuable source of data for computer science experts and researchers interested in the role of interval methods in reliable scientific computing.

Inhalt

Front Cover 1
Reliability in Computing: The Role of Interval Methods in Scientific Computing 4
Copyright Page 5
Table of Contents 6
Contributors 10
Preface 14
Acknowledgments 16
Part 1: Computer Arithmetic and Mathematical Software 18
Chapter 1. ARITHMETIC FOR VECTOR PROCESSORS 20
ABSTRACT 20
1. INTRODUCTION 20
2. THE STATE OF THE ART 25
3. FAST COMPUTATION OF SUMS AND SCALAR PRODUCTS 29
4. SUMMATION WITH ONLY ONE ROW OF ADDERS 39
5. SYSTEMS WITH LARGE EXPONENT RANGE AND FURTHER REMARKS 45
6. APPLICATION TO MULTIPLE PRECISION ARITHMETIC 50
7. CONTEMPORARY FLOATING-POINT ARITHMETIC 53
8. LITERATURE 57
Chapter 2. FORTRAN-SC, A FORTRAN Extension for Engineering/Scientific Computation with Access to ACRITH: Language Description with Examples 60
Abstract 60
1. Introduction 61
2. Development of FORTRAN-SC 62
3. Main Language Concepts 63
4. Language Description with Examples 65
5. Implementation of FORTRAN-SC 77
References 78
Chapter 3. FORTRAN-SC A FORTRAN Extension for Engineering/Scientific Computation with Access to ACRITH: Demonstration of the Compiler and Sample Programs 80
Abstract 80
Introduction 81
Example 1 : Interval Newton Method 81
Example 2 : Automatic Differentiation 84
Example 3 : Runge-Kutta Method 88
Example 4 : Gaussian Elimination Method 90
Example 5 : Verified Solution of a Linear System 93
References 96
Chapter 4. Reliable Expression Evaluation in PASCAL-SC 98
Abstract 98
1. Floating-point arithmetic 99
2. Interval arithmetic 101
3. The optimal scalar product 101
4. Complex floating-point and complex interval arithmetic 102
5. Matrix and vector arithmetic 103
6. Accurate Operations and Problem Solving Routines 103
7. Transformation of arithmetic expressions 104
8. Solution of nonlinear systems 105
9. The data type dotprecision 107
10. Dotproduct expressions 109
11. Conclusion 112
References 113
Chapter 5. Floating-Point Standards — Theory and Practice 116
1. Introduction 116
2. The Standards 116
3. Implementations 119
4. Software Support 121
5. Conclusions 123
References 123
Chapter 6. Algorithms for Verified Inclusions: Theory and Practice 126
Summary 126
0. Introduction 127
1. Basic theorems 128
2. Practical verification on the computer 131
3. Interactive Programming Environment 135
4. References 142
Chapter 7. Applications of Differentiation Arithmetic 144
Abstract 144
1. Differentiation Arithmetic – Why, What, and How? 144
2. Why? – Motivation 145
3 . What? – Component tools 147
4. Conditions on f 158
5. How to use it? – Applications 158
6. Acknowledgements 163
References 163
Part 2: Linear and Nonlinear Systems 166
Chapter 8. INTERVAL ACCELERATION OF CONVERGENCE 168
Abstract 168
1. INTRODUCTION 169
2. EXAMPLES 172
3. DEFINITIONS AND NOTATION 175
4. INTERVAL METHODS 177
5. HOW CAN WE GET BOUNDS ON A GIVEN POINT-SEQUENCE ? 180
6. ACCELERATION OF CONVERGENCE 181
REFERENCES 186
Chapter 9. SOLVING SYSTEMS OF LINEAR INTERVAL EQUATIONS 188
0. Introduction 188
1. Bounding the solutions 188
2. Computing the xy's 191
3. Explicit formulae for x, x 194
4. Inverse interval matrix 196
References 197
Chapter 10. Interval Least Squares — a Diagnostic Tool 200
Introduction 200
Linearity 203
Interval Notation 205
Effects of Nonlinearity 206
Interval Linear Equations 206
Normal Equations 207
QR Approach 207
Nonlinearity Indices 209
Test Data 210
Test Results 212
Diagnosing Collinearity 218
Concluding Remarks 220
References 221
Chapter 11. Existence of Solutions and Iterations for Nonlinear Equations 224
1. Introduction 224
2. Bisection 224
3. Brouwer Fixed–Point Theorem 226
4. Avoiding the Brouwer Fixed-Point Theorem 231
5. Iteration methods 240
References 242
Chapter 12. INTERVAL METHODS FOR ALGEBRAIC EQUATIONS 246
1. Introduction 246
2. Notation 246
3. Preliminaries 247
4. Interval Methods for Single Equations 249
5. Interval Methods for Systems of Equations 258
References 264
Chapter 13. Error Questions in the Computation of Solution Manifolds of Parametrized Equations 266
1.Introduction 266
2. Discretization Errors 268
3. Continuation Methods 273
4. Triangulations and Foldpoint Calculations 276
5. References 282
Chapter 14. THE ENCLOSURE OF SOLUTIONS OF PARAMETER-DEPENDENT SYSTEMS OF EQUATIONS 286
1 . Introduction 286
2. Covering the solution set 290
3. Homogeneous linear interval equations 295
4. Numerical examples 298
5. Final remarks 301
References 302
Part 3: Optimization 304
Chapter 15. AN OVERVIEW OF GLOBAL OPTIMIZATION USING INTERVAL ANALYSIS 306
Abstract 306
1. Introduction 306
2. The fundamental theorem 306
3. Newton's method 308
4. Existence 311
5. Introductory remarks on optimization 311
6. Monotonicity 313
7. Concavity 313
8. Deletion of boxes where f is large 314
9. Feasibility 315
10. Termination 315
11. A global optimization algorithm 315
12. An example 318
13. Other examples 319
14. Conclusion 320
References 321
Chapter 16. Philosophy and Practicalities of Interval Arithmetic 326
Abstract 326
1.0 The scope of interval bounds 326
2.0 Input/Output conventions 328
3.0 Universal Applicability 331
4.0 Using Bounds on Observation Errors 332
5.0 Summary 339
Chapter 17. SOME RECENT ASPECTS OF INTERVAL ALGORITHMS FOR GLOBAL OPTIMIZATION 342
Summary 342
1. Introduction 342
2. Convergence properties of the algorithm 346
3. Global optimization over unbounded domains 347
4. Nonsmooth optimization 350
5. Numerical results 353
Acknowledgement 355
References 355
Chapter 18. The Use of Interval Arithmetic in Uncovering Structure of Linear Systems 358
ABSTRACT 358
I. INTRODUCTION 358
II. TESTS TO UNCOVER THE STRUCTURE OF ANY LINEAR SYSTEM 360
III. TESTS TO UNCOVER THE STRUCTURE OF THE CONSTRAINT MATRIX IN LINEAR PROGRAMMING PROBLEMS 365
IV. CONCLUSION 369
BIBLIOGRAPHY 369
Part 4: Operator Equations 372
Chapter 19. THE ROLE of ORDER in COMPUTING 374
1. Number systems 374
2. Interval lattices 377
3. Lattice-ordered algebras 378
4. Hypercubes 382
5. Positive linear operators 384
6. Random numbers 386
7. The binary digits of 1/ 2 388
8. Continued fractions 391
REFERENCES 394
Chapter 20. INTERVAL METHODS FOR OPERATOR EQUATIONS 396
1. Introduction 396
2. General model 396
3. Nonlinear initial value problems for ordinary differential equations 398
4. Comparison for nonlinear two point boundary value problems 400
5. Nonlinear elliptic boundary value problems. For simplicity, we only consider the 
403 
References 406
Chapter 21. Boundary Implications for Stability Properties: Present Status 408
1. Introduction 408
3. Interval matrices 412
4. Applications 414
Acknowledgement 415
References 416
Chapter 22. VALIDATING COMPUTATION IN A FUNCTION SPACE 420
1. Introduction 421
2. Ultra-arithmetic and Roundings 422
References 442
Epilogue: A Poem about My Life 444

Produkt-Details

• Erscheint lt. Verlag: 10.5.2014
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik ► Theorie / Studium
• Themenwelt: Mathematik / Informatik ► Mathematik ► Algebra
• Themenwelt: Mathematik / Informatik ► Mathematik ► Angewandte Mathematik
• ISBN-10: 1-4832-7784-4 / 1483277844
• ISBN-13: 978-1-4832-7784-4 / 9781483277844