Preface ix

1 Mathematical Preliminaries and Error Analysis 1

1.1 Review of Calculus 2

1.2 Round-off Errors and Computer Arithmetic 17

1.3 Algorithms and Convergence 32

1.4 Numerical Software 41

2 Solutions of Equations in One Variable 47

2.1 The Bisection Method 48

2.2 Fixed-Point Iteration 56

2.3 Newton’s Method and Its Extensions 67

2.4 Error Analysis for Iterative Methods 79

2.5 Accelerating Convergence 86

2.6 Zeros of Polynomials and Müller’s Method 91

2.7 Survey of Methods and Software 101

3 Interpolation and Polynomial Approximation 105

3.1 Interpolation and the Lagrange Polynomial 106

3.2 Data Approximation and Neville’s Method 117

3.3 Divided Differences 124

3.4 Hermite Interpolation 136

3.5 Cubic Spline Interpolation 144

3.6 Parametric Curves 164

3.7 Survey of Methods and Software 171

4 Numerical Differentiation and Integration 173

4.1 Numerical Differentiation 174

4.2 Richardson’s Extrapolation 185

4.3 Elements of Numerical Integration 193

v

Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s).

Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.

vi Contents

4.4 Composite Numerical Integration 203

4.5 Romberg Integration 213

4.6 Adaptive Quadrature Methods 220

4.7 Gaussian Quadrature 228

4.8 Multiple Integrals 235

4.9 Improper Integrals 250

4.10 Survey of Methods and Software 256

5 Initial-Value Problems for Ordinary Differential

Equations 259

5.1 The Elementary Theory of Initial-Value Problems 260

5.2 Euler’s Method 266

5.3 Higher-Order Taylor Methods 276

5.4 Runge-Kutta Methods 282

5.5 Error Control and the Runge-Kutta-Fehlberg Method 293

5.6 Multistep Methods 302

5.7 Variable Step-Size Multistep Methods 315

5.8 Extrapolation Methods 321

5.9 Higher-Order Equations and Systems of Differential Equations 328

5.10 Stability 339

5.11 Stiff Differential Equations 348

5.12 Survey of Methods and Software 355

6 Direct Methods for Solving Linear Systems 357

6.1 Linear Systems of Equations 358

6.2 Pivoting Strategies 372

6.3 Linear Algebra and Matrix Inversion 381

6.4 The Determinant of a Matrix 396

6.5 Matrix Factorization 400

6.6 Special Types of Matrices 411

6.7 Survey of Methods and Software 428

7 IterativeTechniques in Matrix Algebra 431

7.1 Norms of Vectors and Matrices 432

7.2 Eigenvalues and Eigenvectors 443

7.3 The Jacobi and Gauss-Siedel Iterative Techniques 450

7.4 Relaxation Techniques for Solving Linear Systems 462

7.5 Error Bounds and Iterative Refinement 469

7.6 The Conjugate Gradient Method 479

7.7 Survey of Methods and Software 495

Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s).

Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.

Contents vii

8 ApproximationTheory 497

8.1 Discrete Least Squares Approximation 498

8.2 Orthogonal Polynomials and Least Squares Approximation 510

8.3 Chebyshev Polynomials and Economization of Power Series 518

8.4 Rational Function Approximation 528

8.5 Trigonometric Polynomial Approximation 538

8.6 Fast Fourier Transforms 547

8.7 Survey of Methods and Software 558

9 Approximating Eigenvalues 561

9.1 Linear Algebra and Eigenvalues 562

9.2 Orthogonal Matrices and Similarity Transformations 570

9.3 The Power Method 576

9.4 Householder’s Method 593

9.5 The QR Algorithm 601

9.6 Singular Value Decomposition 614

9.7 Survey of Methods and Software 626

10 Numerical Solutions of Nonlinear Systems of

Equations 629

10.1 Fixed Points for Functions of Several Variables 630

10.2 Newton’s Method 638

10.3 Quasi-Newton Methods 647

10.4 Steepest Descent Techniques 654

10.5 Homotopy and Continuation Methods 660

10.6 Survey of Methods and Software 668

11 Boundary-Value Problems for Ordinary Differential

Equations 671

11.1 The Linear Shooting Method 672

11.2 The Shooting Method for Nonlinear Problems 678

11.3 Finite-Difference Methods for Linear Problems 684

11.4 Finite-Difference Methods for Nonlinear Problems 691

11.5 The Rayleigh-Ritz Method 696

11.6 Survey of Methods and Software 711

Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s).

Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.

viii Contents

12 Numerical Solutions to Partial Differential

Equations 713

12.1 Elliptic Partial Differential Equations 716

12.2 Parabolic Partial Differential Equations 725

12.3 Hyperbolic Partial Differential Equations 739

12.4 An Introduction to the Finite-Element Method 746

12.5 Survey of Methods and Software 760

Bibliography 763

Answers to Selected Exercises 773

Index 863About

## Overview

This well-respected text gives an introduction to the theory and application of modern numerical approximation techniques for students taking a one- or two-semester course in numerical analysis. With an accessible treatment that only requires a calculus prerequisite, Burden and Faires explain how, why, and when approximation techniques can be expected to work, and why, in some situations, they fail. A wealth of examples and exercises develop students’ intuition, and demonstrate the subject’s practical applications to important everyday problems in math, computing, engineering, and physical science disciplines. The first book of its kind built from the ground up to serve a diverse undergraduate audience, three decades later Burden and Faires remains the definitive introduction to a vital and practical subject.

## Features and Benefits

- Virtually every concept in the text is illustrated by examples, and reinforced by more than 2500 class-tested exercises ranging from elementary applications of methods and algorithms to generalizations and extensions of the theory.
- The exercise sets include many applied problems from diverse areas of engineering, as well as from the physical, computer, biological, and social sciences.
- The algorithms in the text are designed to work with a wide variety of software packages and programming languages, allowing maximum flexibility for users to harness computing power to perform approximations. The book’s companion website offers Maple, Mathematica, and MATLAB worksheets, as well as C, FORTRAN, Java, and Pascal programs.
- The design of the text gives instructors flexibility in choosing topics they wish to cover, selecting the level of theoretical rigor desired, and deciding which applications are most appropriate or interesting for their classes.

**click Here to download**

About the Text

This book was written for a sequence of courses on the theory and application of numerical

approximation techniques. It is designed primarily for junior-level mathematics, science,

and engineering majors who have completed at least the standard college calculus sequence.

Familiarity with the fundamentals of linear algebra and differential equations is useful, but

there is sufficient introductory material on these topics so that courses in these subjects are

not needed as prerequisites.

Previous editions of Numerical Analysis have been used in a wide variety of situations.

In some cases, the mathematical analysis underlying the development of approximation

techniques was given more emphasis than the methods; in others, the emphasis was reversed. The book has been used as a core reference for beginning graduate level courses

in engineering and computer science programs and in first-year courses in introductory

analysis offered at international universities. We have adapted the book to fit these diverse

users without compromising our original purpose:

To introduce modern approximation techniques; to explain how, why, and when they

can be expected to work; and to provide a foundation for further study of numerical

analysis and scientific computing.

The book contains sufficient material for at least a full year of study, but we expect many

people to use it for only a single-term course. In such a single-term course, students learn

to identify the types of problems that require numerical techniques for their solution and

see examples of the error propagation that can occur when numerical methods are applied.

They accurately approximate the solution of problems that cannot be solved exactly and

learn typical techniques for estimating error bounds for the approximations. The remainder

of the text then serves as a reference for methods not considered in the course. Either the

full-year or single-course treatment is consistent with the philosophy of the text.

Virtually every concept in the text is illustrated by example, and this edition contains

more than 2600 class-tested exercises ranging from elementary applications of methods

and algorithms to generalizations and extensions of the theory. In addition, the exercise

sets include numerous applied problems from diverse areas of engineering as well as from

the physical, computer, biological, economic, and social sciences. The chosen applications

clearly and concisely demonstrate how numerical techniques can be, and often must be,

applied in real-life situations.

A number of software packages, known as Computer Algebra Systems (CAS), have

been developed to produce symbolic mathematical computations. Maple®, Mathematica®,

and MATLAB® are predominant among these in the academic environment, and versions

of these software packages are available for most common computer systems. In addition,

Sage, a free open source system, is now available. This system was developed primarily

ix

Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s).

Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.

x Preface

by William Stein at the University of Washington, and was first released in February 2005.

Information about Sage can be found at the site

http://www.sagemath.org .

Although there are differences among the packages, both in performance and price, all can

perform standard algebra and calculus operations.

The results in most of our examples and exercises have been generated using problems

for which exact solutions are known, because this permits the performance of the approximation method to be more easily monitored. For many numerical techniques the error

analysis requires bounding a higher ordinary or partial derivative, which can be a tedious

task and one that is not particularly instructive once the techniques of calculus have been

mastered. Having a symbolic computation package available can be very useful in the study

of approximation techniques, because exact values for derivatives can easily be obtained. A

little insight often permits a symbolic computation to aid in the bounding process as well.

We have chosen Maple as our standard package because of its wide academic distribution and because it now has a NumericalAnalysis package that contains programs that

parallel the methods and algorithms in our text. However, other CAS can be substituted with

only minor modifications. Examples and exercises have been added whenever we felt that

a CAS would be of significant benefit, and we have discussed the approximation methods

that CAS employ when they are unable to solve a problem exactly.

Algorithms and Programs

In our first edition we introduced a feature that at the time was innovative and somewhat

controversial. Instead of presenting our approximation techniques in a specific programming

language (FORTRAN was dominant at the time), we gave algorithms in a pseudo code that

would lead to a well-structured program in a variety of languages. The programs are coded

and available online in most common programming languages and CAS worksheet formats.

All of these are on the web site for the book:

http://www.math.ysu.edu/∼faires/Numerical-Analysis/ .

For each algorithm there is a program written in FORTRAN, Pascal, C, and Java. In addition,

we have coded the programs using Maple, Mathematica, and MATLAB. This should ensure

that a set of programs is available for most common computing systems.

Every program is illustrated with a sample problem that is closely correlated to the text.

This permits the program to be run initially in the language of your choice to see the form

of the input and output. The programs can then be modified for other problems by making

minor changes. The form of the input and output are, as nearly as possible, the same in

each of the programming systems. This permits an instructor using the programs to discuss

them generically, without regard to the particular programming system an individual student

chooses to use.

The programs are designed to run on a minimally configured computer and given in

ASCII format for flexibility of use. This permits them to be altered using any editor or word

processor that creates standard ASCII files (commonly called “Text Only” files). Extensive

README files are included with the program files so that the peculiarities of the various

programming systems can be individually addressed. The README files are presented

both in ASCII format and as PDF files. As new software is developed, the programs will

be updated and placed on the web site for the book.

For most of the programming systems the appropriate software is needed, such as a

compiler for Pascal, FORTRAN, and C, or one of the computer algebra systems (Maple,

Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s).

Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.

Preface xi

Mathematica, and MATLAB). The Java implementations are an exception. You need the

system to run the programs, but Java can be freely downloaded from various sites. The best

way to obtain Java is to use a search engine to search on the name, choose a download site,

and follow the instructions for that site.

New for This Edition

The first edition of this book was published more than 30 years ago, in the decade after major

advances in numerical techniques were made to reflect the new widespread availability of

computer equipment. In our revisions of the book we have added new techniques in order

to keep our treatment current. To continue this trend, we have made a number of significant

changes to the ninth edition.

• Our treatment of Numerical Linear Algebra has been extensively expanded, and constitutes one of major changes in this edition. In particular, a section on Singular Value

Decomposition has been added at the end of Chapter 9. This required a complete rewrite

of the early part of Chapter 9 and considerable expansion of Chapter 6 to include necessary material concerning symmetric and orthogonal matrices. Chapter 9 is approximately

40% longer than in the eighth edition, and contains a significant number of new examples

and exercises. Although students would certainly benefit from a course in Linear Algebra

before studying this material, sufficient background material is included in the book, and

every result whose proof is not given is referenced to at least one commonly available

source.

• All the Examples in the book have been rewritten to better emphasize the problem to

be solved before the specific solution is presented. Additional steps have been added to

many of the examples to explicitly show the computations required for the first steps of

iteration processes. This gives the reader a way to test and debug programs they have

written for problems similar to the examples.

• A new item designated as an Illustration has been added. This is used when discussing a

specific application of a method not suitable for the problem statement-solution format

of the Examples.

• The Maple code we include now follows, whenever possible, the material included in

their NumericalAnalysis package. The statements given in the text are precisely what is

needed for the Maple worksheet applications, and the output is given in the same font

and color format that Maple produces.

• A number of sections have been expanded, and some divided, to make it easier for instructors to assign problems immediately after the material is presented. This is particularly

true in Chapters 3, 6, 7, and 9.

• Numerous new historical notes have been added, primarily in the margins where they

can be considered independent of the text material. Much of the current material used in

Numerical Analysis was developed in middle of the 20th century, and students should be

aware that mathematical discoveries are ongoing.

• The bibliographic material has been updated to reflect new editions of books that we

reference. New sources have been added that were not previously available.

As always with our revisions, every sentence was examined to determine if it was phrased

in a manner that best relates what is described.

Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s).

Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.

xii Preface

Supplements

A Student Solutions Manual and Study Guide (ISBN-10: 0-538-73351-9; ISBN-13: 978-0-

538-73351-9) is available for purchase with this edition, and contains worked-out solutions

to many of the problems. The solved exercises cover all of the techniques discussed in the

text, and include step-by-step instructions for working through the algorithms. The first two

chapters of this Guide are available for preview on the web site for the book.

Complete solutions to all exercises in the text are available to instructors in secure,

customizable online format through the Cengage Solution Builder service. Adopting instructors can sign up for access at http://www.cengage.com/solutionbuilder. Computation results

in these solutions were regenerated for this edition using the programs on the web site to

ensure compatibility among the various programming systems.

A set of classroom lecture slides, prepared by Professor John Carroll of Dublin City

University, are available on the book’s instructor companion web site at http://www.cengage.

com/math/burden. These slides, created using the Beamer package of LaTeX, are in PDF

format. They present examples, hints, and step-by-step animations of important techniques

in Numerical Analysis.

[…] Numerical Analysis 9th Burden Faires […]

LikeLike