Atkinson K. An Introduction to Numerical Analysis

AN

INTRODUCTION

TO

NUMERICAL ANALYSIS

Second Edition

Kendall E. Atkinson

University

of

Iowa

•

WILEY

John

Wiley & Sons

'

'·

__

j

1978, 1989, by

John

Wiley & Sons, Inc.

Published simultaneously

in

Canada.

Reproduction

or

translation

of

any

part

of

this work beyond that permitted by Sections

107

and

108

of

the 1976 United States Copyright

Act without the permission

of

the

copyright

owner is unlawful. Requests for permission

or

further information should

be

addressed to

the

Permissions Department,

John

Wiley & Sons.

Library•

of

Congre.fs Cataloging in Publication Data:

Atkinson,

Kendall

E.

An

introduction

to numerical

analysis/Kendall

E.

Atkinson.-

2nd

ed.

p. em.

Bibliography: p.

Includes index.

ISBN 0-471-62489-6

1.

Numerical

analysis.

QA297.A84 1988

519.4-dcl9

20

19

18 17

16 15

14

I. Title.

PREFACE

to the first edition

This introduction to numerical analysis was written for students in mathematics,

the physical sciences, and engineering,

at

the upper undergraduate to beginning

graduate level. Prerequisites for using the text are elementary calculus, linear

algebra,

and

an

introduction

to

differential equations. The student's level

of

mathematical maturity

or

experience with mathematics should

be

somewhat

higher; I have found that most students do not attain the necessary level until

their senior year. Finally, the student should have a knowledge of computer

programming. The preferred language for most scientific programming is For-

tran.

A truly effective use

of

numerical analysis in applications requires

both

a

theoretical knowledge

of

the subject

and

computational experience with it. The

theoretical knowledge should include an understanding

of

both the original

problem being solved and of the numerical me.thods for its solution, including

their derivation, error analysis, and

an

idea

of

when they

will

perform well

or

poorly. This kind

of

knowledge is necessary even if you are only considering

using a package program from your computer center.

You must still understand

the program's purpose and limitations to know whether it applies to your

particular situation

or

not. More importantly, a majority

of

problems cannot

be

solved by the simple application

of

a standard program.

For

such problems you

must devise new numerical methods, and this is usually done by adapting

standard numerical methods

to

the new situation. This requires a good theoreti-

cal foundation in numerical analysis, both to devise the new methods and

to

avoid certain numerical pitfalls that occur easily

in

a number

of

problem areas.

Computational experience is also very important.

It

·gives a sense of reality

to

most theoretical discussions; and

it

brings out the important difference between

the exact arithmetic implicit in most theoretical discussions and the finite-length

arithmetic computation, whether

on

a computer

or

a

hand

calculator. The use

of

a computer also imposes constraints

on

the structure

of

numerical methods,

constraints that are

not

evident

and

that seem unnecessary from· a strictly

mathematical viewpoint.

For

example, iterative procedures are often preferred

over direct procedures because of simpler programming requirements

or

com-

puter memory size limitations, even though the direct procedure may seem

simpler to explain

and

to

use. Many numerical examples are

~ven

in

this text

to

illustrate these points,

and

there are a number

of

exercises that will give the

student a variety

of

<...)mputational experience.

ix

i

__

___j

X PREFACE TO THE FIRST EDITION

The

book

is

organized in a fairly standard manner. Topics that are simpler,

both

theoretically and computationally, come first; for example, rootfinding for a

single nonlinear equation

is

covered in Chapter

2.

The more sophisticated topics

within numerical linear algebra are left until the last three chapters.

If

an

instructor prefers, however, Chapters 7 through 9 on numerical linear ·algebra can

be

inserted

at

any point following Chapter

1.

Chapter 1 contains a number

of

introductory topics, some of which the instructor may wish to postpone until

later

in

the course.

It

is

important, however, to cover the mathematical and

notational preliminaries of Section 1.1 and the introduction to computer

floating-point arithmetic given in

Section 1.2 and

in

part

of

Section 1.3.

The

text contains more than enough material for a one-year course. In

addition, introductions are given to some topics that instructors may wish to

expand

on

from their own notes. For example, a brief introduction

is

given to

stiff differential equations in the last

part

of Section 6.8 in Chapter 6; and some

theoretical foundation for the least squares data-fitting problem

is

given in

Theorem

7.5 and Problem 15

of

Chapter 7. These can easily be expanded by

using the references given in the respective chapters.

Each chapter contains a discussion of the research literature and a bibliogra-

phy

of

some

of

the important books and papers on the material of the chapter.

The

chapters all conclude with a set

of

exercises. Some

of

these exercises are

illustrations

or

applications of the text material, and others involve the develop-

ment

of

new material. As an aid to the student, answers and hints to selected

exercises are given at the end

of

the book.

It

is important, however, for students

to solve some problems in which there is no given answer against which they can

check their results. This forces them to develop a variety

of

other means for

checking their own work; and it

will

force them to develop some common sense

or

judgment

as an aid in knowing whether

or

not

their results are reasonable.

I teach a one-year course covering much

of

the material of this book. Chapters

1 through

5 form the first semester, and Chapters 6 through 9 form the second

semester.

In

most chapters, a number of topics can be deleted without any

difficulty

arising· in later chapters. Exceptions to this are Section 2.5

on

linear

iteration methods,

Sections 3.1 to 3.3, 3.6 on interpolation theory, Section 4.4

on

orthogonal polynomials, and Section 5.1 on the trapezoidal and Simpson integra-

tion rules.

I thank

Professor Herb Hethcote of the University of Iowa for his helpful

advice and for having taught from an earlier rough draft

of

the book. I am also

grateful for the advice of

Professors Robert Barnhill, University of Utah, Herman

Burchard, Oklahoma

State University, and Robert J. Flynn, Polytechnic Institute

of

New York. I am very grateful to Ada

Bums

and Lois Friday, who did an

excellent

job

of

typing this and earlier versions of the book. I thank the many

stude~ts

who, over the past twelve years, enrolled in my course and used my

notes and rough drafts rather than a regular text. They pointed but numerous

errors, and their difficulties with certain topics helped me in preparing better

presentations

of

them. The staff of John Wiley have been very helpful, and the

text is much better as a result of their efforts. Finally,

I thank

my

wife Alice for

her patient and encouraging support, without which the book would probably

have not been completed.

Iowa City, August, 1978

Kendall E. Atkinson

CONTENTS

ONE

ERROR: ITS SOURCES, PROPAGATION,

AND

ANALYSIS

1.1

Mathematical Preliminaries

1.2 Computer Representation of Numbers

1.3 Definitions and Sources

of

Error

1.4 Propagation of Errors

1.5 Errors in Summation

1.6 Stability in Numerical Analysis

Discussion of the Literature

Problems

1WO

ROOTFINDING FOR NONLINEAR EQUATIONS

2.1 The Bisection Method

2.2 Newton's Method

2.3 The Secant Method

2.4 Muller's Method

2.5 A General Theory for One-Point Iteration Methods

2.6 Aitken Extrapolation for Linearly Convergent Sequences

2.7 The Numerical Evaluation of Multiple Roots

2.8 Brent's Rootfinding Algorithm

2.9 Roots of Polynomials

2.10

Systems of Nonlinear Equations

2.11 Newton's Method for Nonlinear

Systems

2.12 Unconstrained Optimization

Discussion of the Literature

Problems

THREE

INTERPOLATION THEORY

3.1 PolynOinial Interpolation Theory

3.2 Newton Divided Differences

3

11

17

23

29

34

39

43

53

56

58

65

73

76

83

87

91

94

103

108

111

114

117

131

138

xiii

;

i'

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

!

'

xiv

CONTENTS

3.3 Finite Differences and Table-Oriented Interpolation Formulas

147

3.4 Errors in Data and Forward Differences

151

3.5 Further Results on Interpolation Error

154

3.6 Hermite Interpolation

159

3.7 Piecewise Polynomial Interpolation

163

3.8 Trigonometric Interpolation

176

Discussion of the Literature

183

Problems

185

FOUR

APPROXIMATION OF FUNCTIONS

4.1 The Weierstrass Theorem and Taylor's Theorem

4.2 The Minimax Approximation Problem

4.3 The Least Squares Approximation Problem

4.4 Orthogonal Polynomials

4.5 The Least Squares Approximation

Problem (continued)

4.6 Minimax Approximations

4.7 Near-Minimax Approximations

Discussion of the Literature

Problems

FIVE

NUMERICAL

INTEGRATION

5.1 The Trapezoidal Rule and Simpson's Rule

5.2 Newton-Cotes Integration Formulas

5.3 Gaussian Quadrature

5.4 Asymptotic Error Formulas and Their Applications

5.5 Automatic Numerical Integration

5.6 Singular Integrals

5.7 Numerical Differentiation

Discussion of the Literature

Problems

SIX

NUMERICAL

METHODS FOR ORDINARY

DIFFERENTIAL EQUATIONS

6.1 Existence, Uniqueness, and Stability Theory

6.2 Euler's Method

6.3 Multistep Methods

6.4 The Midpoint Method

6.5 The Trapezoidal Method

6.6 A Low-Order Predictor-Corrector Algorithm

197

201

204

207

216

222

225

236

239

249

251

263

270

284

299

305

315

320

323

333

335

341

357

361

366

373

6.7 Derivation of Higher Order Multistep Methods

6.8 Convergence and Stability Theory for Multistep Methods

6.9 Stiff Differential Equations and the Method of Lines

6.10 Single-Step and Runge-Kutta Methods

6.11 Boundary Value Problems

Discussion of the Literature

Problems

SEVEN

LINEAR ALGEBRA

7.1

Vector Spaces, Matrices, and Linear Systems

7.2 Eigenvalues and Canonical Forms for Matrices

7.3 Vector and Matrix Norms

7.4 Convergence and Perturbation Theorems

Discussion of the Literature

Problems

EIGHT

NUMERICAL

SOLUTION

OF

SYSTEMS

OF

LINEAR EQUATIONS

8.1 Gaussian Elimination

8.2 Pivoting and Scaling

in Gaussian Elimination

8.3 Variants of Gaussian Elimination

8.4 Error Analysis

8.5 The Residual Correction Method

8.6 Iteration Methods

8.7 Error Prediction and Acceleration

8.8 The Numerical Solution of Poisson's Equation

8.9 The Conjugate Gradient Method

Discussion of the Literature

Problems

NINE

THE

MATRIX EIGENVALUE PROBLEM

9.1 · Eigenvalue Location, Error, and Stability Results

9.2 The Power Method

9.3 Orthogonal Transformations

Using Householder Matrices

9.4 The Eigenvalues of a Symmetric Tridiagonal Matrix

9.5 The

QR

Method

9.6 The Calculation of Eigenvectors and Inverse Iteration

9.7 Least Squares Solution of Linear Systems

Discussion of the Literature

Problems

CONTENTS

XV

381

394

409

418

433

444

450

463

471

480

490

495

496

507

508

515

522

529

540

544

552

557

562

569

574

587

588

602

609

619

623

628

633

645

648

xvi

CONTENTS

APPENDIX:

MATHEMATICAL SOFTWARE

ANSWERS TO SELECTED EXERCISES

INDEX

661

667

683

ONE

ERROR:

ITS SOURCES,

PROPAGATION,

AND

ANALYSIS

The subject of numerical analysis provides computational methods for the study

and solution of mathematical problems. In this text

we

study numerical methods

for the solution of the most common mathematical problems and

we

analyze the

errors present in these methods. Because almost

all

computation is now done

on

digital computers,

we

also discuss the implications of this in the implementation

of numerical methods.

The study of error

is

a central concern of numerical analysis. Most numerical

methods give answers that are only approximations to the desired true solution,

-and-itcisimportant to understand-and to be able, if possible, to estimate or bound

the resulting error. This chapter examines the various kinds of errors that may

occur in a problem. The representation of numbers in computers

is

examined,

along with the error

in

computer arithmetic. General results on the propagation

of errors in calculations are given, with a detailed look at error in summation

procedures. Finally, the concepts of stability and conditioning of problems and

numerical methods are introduced and illustrated. The first section contains

mathematical preliminaries needed for the work of later chapters.

1.1

Mathematical Preliminaries

This section contains a review of results from calculus, which will be used in this

text. We first give some mean value theorems, and then

we

present and discuss

Taylor's theorem, for functions of one and two variables. The section concludes

with some notation that

will

be used in later chapters.

Theorem 1.1 (Intermediate Value) Let

f(x)

be continuous on the finite interval

a

~

x

~

b,

and define

m =

Infimumf(x),

asxsh

M =

Supremumj(x)

asxsh

Then for any number K in the interval [

m,

MJ,

there is at least one

point

~

in [a, b) for which

!(0

= r

3

Atkinson K. An Introduction to Numerical Analysis

Подождите немного. Документ загружается.