[PDF] Numerical Analysis - Faculty - The University of Chicago PDF nalrs.pdf

The publisher would like to acknowledge the author of this volume for type- the importance of the field of numerical analysis that such books and others

in the field and to include references to new books and expository accounts The book is designed for use in a graduate program in Numerical Analysis that The author has taught the basic introductory course and the advanced course on

[PDF] Introduction to Numerical Analysis - IITB Math - IIT Bombay

K E Atkinson, An Introduction to Numerical Analysis (2nd edition), Wiley-India, 1989 Students are requested to refer the text books listed under course syllabus These notes may have errors of all kind and the author request the readers to

[PDF] INDIAN INSTITUTE OF TECHNOLOGY ROORKEE - IIT Roorkee

Suggested Books: S No Name of Authors / Books / Publishers Year of Publication/ Reprint 1 Gerald, C F and Wheatly, P O ," Applied Numerical Analysis", 6

[PDF] Special Priced Indian Edition - Springer

For the third edition, the author has added a new chapter on associative algebras for Mathematical Exposition for his many mathematics books: 'Lang's Algebra semester course, Applied Linear Algebra and Matrix Analysis places special

[PDF] Numerical Analysis, 9th ed - KSU Faculty

please visit www cengage com/highered to search by ISBN#, author, title, or keyword Books that address the application of numerical techniques on parallel

[PDF] Numerical Methods - Department of Mathematics, HKUST

What follows were my lecture notes for Math 3311: Introduction to Numerical Meth- ods, taught at the Hong Kong University of Science and Technology Math 3311

[PDF] AN INTRODUCTION TO NUMERICAL ANALYSIS Second Edition

2 mar 2012 · This introduction to numerical analysis was written for students in mathematics, the physical phy of some of the important books and papers on the material of the chapter The chapters all In that paper, the authors also

[PDF] Numerical Analysis - Faculty - The University of Chicago

The publisher would like to acknowledge the author of this volume for type- the importance of the field of numerical analysis that such books and others

[PDF] Applied Numerical Analysis - CSE, IIT Madras

0 1 Analysis Versus Numerical Analysis 2 A set of books, Nu?nerical Recipes, lists and discusses numerical of one of the authors, taken by Elsie F Gerald

Numerical Analysis

L. Ridgway Scott

PRINCETON UNIVERSITY PRESS

PRINCETON AND OXFORD

Copyrightc?2011 by Princeton University Press

Published by Princeton University Press, 41 William Street,

Princeton, New Jersey 08540

In the United Kingdom: Princeton University Press, 6 OxfordStreet,

Woodstock, Oxfordshire OX20 1TW

press.princeton.edu

All Rights Reserved

Library of Congress Control Number: 2010943322

ISBN: 978-0-691-14686-7

British Library Cataloging-in-Publication Data is available The publisher would like to acknowledge the author of this volume for type- setting this book using L

ATEX and Dr. Janet Englund and Peter Scott for

providing the cover photograph

Printed on acid-free paper∞

Printed in the United States of America

10 9 8 7 6 5 4 3 2 1

Dedication

To the memory of Ed Conway

1who, along with his colleagues at Tulane

University, provided a stable, adaptive, and inspirational starting point for my career.

1Edward Daire Conway, III (1937-1985) was a student of Eberhard Friedrich Ferdinand

Hopf at the University of Indiana. Hopf was a student of Erhard Schmidt and Issai Schur.

Prefacexi

Chapter 1. Numerical Algorithms1

1.1 Finding roots2

1.2 Analyzing Heron"s algorithm5

1.3 Where to start6

1.4 An unstable algorithm8

1.5 General roots: effects of floating-point9

1.6 Exercises11

1.7 Solutions13

Chapter 2. Nonlinear Equations15

2.1 Fixed-point iteration16

2.2 Particular methods20

2.3 Complex roots25

2.4 Error propagation26

2.5 More reading27

2.6 Exercises27

2.7 Solutions30

Chapter 3. Linear Systems35

3.1 Gaussian elimination36

3.2 Factorization38

3.3 Triangular matrices42

3.4 Pivoting44

3.5 More reading47

3.6 Exercises47

3.7 Solutions50

Chapter 4. Direct Solvers51

4.1 Direct factorization51

4.2 Caution about factorization56

4.3 Banded matrices58

4.4 More reading60

4.5 Exercises60

4.6 Solutions63

viiiCONTENTS

Chapter 5. Vector Spaces65

5.1 Normed vector spaces66

5.2 Proving the triangle inequality69

5.3 Relations between norms71

5.4 Inner-product spaces72

5.5 More reading76

5.6 Exercises77

5.7 Solutions79

Chapter 6. Operators81

6.1 Operators82

6.2 Schur decomposition84

6.3 Convergent matrices89

6.4 Powers of matrices89

6.5 Exercises92

6.6 Solutions95

Chapter 7. Nonlinear Systems97

7.1 Functional iteration for systems98

7.2 Newton"s method103

7.3 Limiting behavior of Newton"s method108

7.4 Mixing solvers110

7.5 More reading111

7.6 Exercises111

7.7 Solutions114

Chapter 8. Iterative Methods115

8.1 Stationary iterative methods116

8.2 General splittings117

8.3 Necessary conditions for convergence123

8.4 More reading128

8.5 Exercises128

8.6 Solutions131

Chapter 9. Conjugate Gradients133

9.1 Minimization methods133

9.2 Conjugate Gradient iteration137

9.3 Optimal approximation of CG141

9.4 Comparing iterative solvers147

9.5 More reading147

9.6 Exercises148

9.7 Solutions149

CONTENTSix

Chapter 10. Polynomial Interpolation151

10.1 Local approximation: Taylor"s theorem151

10.2 Distributed approximation: interpolation152

10.3 Norms in infinite-dimensional spaces157

10.4 More reading160

10.5 Exercises160

10.6 Solutions163

Chapter 11. Chebyshev and Hermite Interpolation 167

11.1 Error termω167

11.2 Chebyshev basis functions170

11.3 Lebesgue function171

11.4 Generalized interpolation173

11.5 More reading177

11.6 Exercises178

11.7 Solutions180

Chapter 12. Approximation Theory183

12.1 Best approximation by polynomials183

12.2 Weierstrass and Bernstein187

12.3 Least squares191

12.4 Piecewise polynomial approximation193

12.5 Adaptive approximation195

12.6 More reading196

12.7 Exercises196

12.8 Solutions199

Chapter 13. Numerical Quadrature203

13.1 Interpolatory quadrature203

13.2 Peano kernel theorem209

13.3 Gregorie-Euler-Maclaurin formulas212

13.4 Other quadrature rules219

13.5 More reading221

13.6 Exercises221

13.7 Solutions224

Chapter 14. Eigenvalue Problems225

14.1 Eigenvalue examples225

14.2 Gershgorin"s theorem227

14.3 Solving separately232

14.4 How not to eigen233

14.5 Reduction to Hessenberg form234

14.6 More reading237

14.7 Exercises238

14.8 Solutions240

xCONTENTS

Chapter 15. Eigenvalue Algorithms241

15.1 Power method241

15.2 Inverse iteration250

15.3 Singular value decomposition252

15.4 Comparing factorizations253

15.5 More reading254

15.6 Exercises254

15.7 Solutions256

Chapter 16. Ordinary Differential Equations 257

16.1 Basic theory of ODEs257

16.2 Existence and uniqueness of solutions258

16.3 Basic discretization methods262

16.4 Convergence of discretization methods266

16.5 More reading269

16.6 Exercises269

16.7 Solutions271

Chapter 17. Higher-order ODE Discretization Methods 275

17.1 Higher-order discretization276

17.2 Convergence conditions281

17.3 Backward differentiation formulas287

17.4 More reading288

17.5 Exercises289

17.6 Solutions291

Chapter 18. Floating Point293

18.1 Floating-point arithmetic293

18.2 Errors in solving systems301

18.3 More reading305

18.4 Exercises305

18.5 Solutions308

Chapter 19. Notation309

Bibliography311

Index323

Preface

"...by faith and faith alone, embrace, believing where we cannot prove," fromIn Memoriamby Alfred Lord Ten- nyson, a memorial to Arthur Hallum. Numerical analysis provides the foundations for a major paradigm shift in what we understand as an acceptable "answer" to a scientific or techni- cal question. In classical calculus we look for answers like⎷ sinx, that is, answers composed of combinations of names of functions thatare familiar. This presumes we can evaluate such an expression as needed, and indeed numerical analysis has enabled the development of pocket calculators and computer software to make this routine. But numerical analysis has done much more than this. We will see that far more complex functions, defined, e.g., only implicitly, can be evaluated just as easily and with the same tech- nology. This makes the search for answers in classical calculus obsolete in many cases. This new paradigm comes at a cost: developing stable, con- vergent algorithms to evaluate functions is often more difficult than more classical analysis of these functions. For this reason, thesubject is still be- ing actively developed. However, it is possible to present many important ideas at an elementary level, as is done here. Today there are many good books on numerical analysis at the graduate level, including general texts [47, 134] as well as more specialized texts. We reference many of the latter at the ends of chapters where we suggest fur- ther reading in particular areas. At a more introductory level, the recent trend has been to provide texts accessible to a wide audience. The book by Burden and Faires [28] has been extremely successful. It is a tribute to the importance of the field of numerical analysis that such books and others [131] are so popular. However, such books intentionally diminish the role of advanced mathematics in the subject of numerical analysis. As a result, numerical analysis is frequently presented as an elementary subject. As a corollary, most students miss exposure to numerical analysis as a mathemat- ical subject. We hope to provide an alternative. Several books written some decades ago addressed specifically a mathe-quotesdbs_dbs20.pdfusesText_26

[PDF] [PDF] Numerical Analysis - Faculty - The University of Chicago

Numerical Analysis

Numerical Analysis

L. Ridgway Scott

PRINCETON UNIVERSITY PRESS

PRINCETON AND OXFORD

Copyrightc?2011 by Princeton University Press

Princeton, New Jersey 08540

Woodstock, Oxfordshire OX20 1TW

All Rights Reserved

Library of Congress Control Number: 2010943322

ISBN: 978-0-691-14686-7

ATEX and Dr. Janet Englund and Peter Scott for

Printed on acid-free paper∞

Printed in the United States of America

10 9 8 7 6 5 4 3 2 1

Dedication

To the memory of Ed Conway

1who, along with his colleagues at Tulane

1Edward Daire Conway, III (1937-1985) was a student of Eberhard Friedrich Ferdinand

Contents

Prefacexi

Chapter 1. Numerical Algorithms1

1.1 Finding roots2

1.2 Analyzing Heron"s algorithm5

1.3 Where to start6

1.4 An unstable algorithm8

1.5 General roots: effects of floating-point9

1.6 Exercises11

1.7 Solutions13

Chapter 2. Nonlinear Equations15

2.1 Fixed-point iteration16

2.2 Particular methods20

2.3 Complex roots25

2.4 Error propagation26

2.5 More reading27

2.6 Exercises27

2.7 Solutions30

Chapter 3. Linear Systems35

3.1 Gaussian elimination36

3.2 Factorization38

3.3 Triangular matrices42

3.4 Pivoting44

3.5 More reading47

3.6 Exercises47

3.7 Solutions50

Chapter 4. Direct Solvers51

4.1 Direct factorization51

4.2 Caution about factorization56

4.3 Banded matrices58

4.4 More reading60

4.5 Exercises60

4.6 Solutions63

Chapter 5. Vector Spaces65

5.1 Normed vector spaces66

5.2 Proving the triangle inequality69

5.3 Relations between norms71

5.4 Inner-product spaces72

5.5 More reading76

5.6 Exercises77

5.7 Solutions79

Chapter 6. Operators81

6.1 Operators82

6.2 Schur decomposition84

6.3 Convergent matrices89

6.4 Powers of matrices89

6.5 Exercises92

6.6 Solutions95

Chapter 7. Nonlinear Systems97

7.1 Functional iteration for systems98

7.2 Newton"s method103

7.3 Limiting behavior of Newton"s method108

7.4 Mixing solvers110

7.5 More reading111

7.6 Exercises111

7.7 Solutions114

Chapter 8. Iterative Methods115

8.1 Stationary iterative methods116

8.2 General splittings117

8.3 Necessary conditions for convergence123