Numerical Analysis 9th Burden Faires

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.

9780538733519.jpg

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.

Advertisements

One response

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

    Like