Numerical Analysis - Computer Science

[Pages:341]Numerical Analysis

Numerical Analysis L. Ridgway Scott

PRINCETON UNIVERSITY PRESS PRINCETON AND OXFORD

Copyright c 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 Oxford Street, 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 typesetting this book using LATEX 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 Conway1 who, 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.

Contents

Preface

xi

Chapter 1. Numerical Algorithms

1

1.1 Finding roots

2

1.2 Analyzing Heron's algorithm

5

1.3 Where to start

6

1.4 An unstable algorithm

8

1.5 General roots: effects of floating-point

9

1.6 Exercises

11

1.7 Solutions

13

Chapter 2. Nonlinear Equations

15

2.1 Fixed-point iteration

16

2.2 Particular methods

20

2.3 Complex roots

25

2.4 Error propagation

26

2.5 More reading

27

2.6 Exercises

27

2.7 Solutions

30

Chapter 3. Linear Systems

35

3.1 Gaussian elimination

36

3.2 Factorization

38

3.3 Triangular matrices

42

3.4 Pivoting

44

3.5 More reading

47

3.6 Exercises

47

3.7 Solutions

50

Chapter 4. Direct Solvers

51

4.1 Direct factorization

51

4.2 Caution about factorization

56

4.3 Banded matrices

58

4.4 More reading

60

4.5 Exercises

60

4.6 Solutions

63

viii

Chapter 5. Vector Spaces 5.1 Normed vector spaces 5.2 Proving the triangle inequality 5.3 Relations between norms 5.4 Inner-product spaces 5.5 More reading 5.6 Exercises 5.7 Solutions

Chapter 6. Operators 6.1 Operators 6.2 Schur decomposition 6.3 Convergent matrices 6.4 Powers of matrices 6.5 Exercises 6.6 Solutions

Chapter 7. Nonlinear Systems 7.1 Functional iteration for systems 7.2 Newton's method 7.3 Limiting behavior of Newton's method 7.4 Mixing solvers 7.5 More reading 7.6 Exercises 7.7 Solutions

Chapter 8. Iterative Methods 8.1 Stationary iterative methods 8.2 General splittings 8.3 Necessary conditions for convergence 8.4 More reading 8.5 Exercises 8.6 Solutions

Chapter 9. Conjugate Gradients 9.1 Minimization methods 9.2 Conjugate Gradient iteration 9.3 Optimal approximation of CG 9.4 Comparing iterative solvers 9.5 More reading 9.6 Exercises 9.7 Solutions

CONTENTS

65 66 69 71 72 76 77 79

81 82 84 89 89 92 95

97 98 103 108 110 111 111 114

115 116 117 123 128 128 131

133 133 137 141 147 147 148 149

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download