[PDF] Applied Numerical Analysis.pdf

View - Download Applied Numerical Analysis.pdf

Previous PDF

Next PDF

bA,ani. "

Seventh Ed )n

merica

Patrick 0. Wheatley

California Polytechnic State University

Boston San Francisco New York

London Toronto Sydney Tokyo Singapore Madrid

Mexico City Munich

Paris Cape Town Hong Kong Montreal

Publisher: Greg Tobin

Managing Editor: Karen Guardino

Acquisitions Editor: William Hoffman

Associate Editor:

RoseAnne

Johnson

Production Supervisor: Cindy Cody

Marketing Manager: Pamela Laskey

Marketing Coordinator: Heather Peck

Prepress Supervisor: Caroline Fell

Manufacturing Buyer: Evelyn

Beaton

Cover Designer: Dennis Schaefer

Cover Photo Credit:

CREATASPhotography

Compositor: Progressive Information Technologies

Library of Congress Cataloging-in-Publication Data

Gerald, Curtis F., 1915-

Applied numerical

analysis1Curtis

F. Gerald, Patrick 0. Wheat1ey.-7th ed.

p. cm.

Includes bibliographical references and index.

ISBN 0-321-13304-8

1. Numerical analysis.

I. Wheatley, Patrick

0. 11. Title.

Copyright

O 2004 Pearson Education, Inc.

All rights reserved. No part of this publication may be reproduced, stored in retrieval system, or transmitted,

in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise, without the prior

written permission of the publisher. Printed in the United States of America.

Preface ix

0 Preliminaries 1

Contents of This Chapter 1

0.1 Analysis Versus Numerical Analysis 2

0.2 Computers and Numerical Analysis 4

0.3 An Illustrative Example 6

0.4 Kinds of Errors in Numerical Procedures 10

0.5 Interval Arithmetic 19

0.6 Parallel and Distributed Computing 21

0.7 Measuring the Efficiency of Numerical Procedures 26

Exercises 28

'I

Applied Problems and Projects 30

C

1 Solving Nonlinear Equations 32

Contents of This Chapter 33

1.1 Interval Halving (Bisection) 33

1.2 Linear Interpolation Methods 38

1.3 Newton's Method 42

1.4 Muller's Method 50

Contents

1.5 Fixed-Point Iteration: x = g(x) Method 54

1.6 Multiple Roots 60

1.7 Nonlinear Systems 63

Exercises 67

Applied Problems and Projects 71

2 Solving Sets of Equations 76

Contents of This Chapter 76

2.1 Matrices and Vectors 77

2.2 Elimination Methods 88

2.3 The Inverse of a Matrix and Matrix Pathology 106

2.4 Ill-Conditioned Systems 110

2.5 Iterative Methods 121

2.6 Parallel Processing 129 Exercises 135

Applied Problems and Projects 141

3 Interpolation and Curve Fitting 147

Contents of This Chapter 148

Interpolating Polynomials 149

Divided Differences 157

Spline Curves 168

Bezier Curves and B-Splines Curves 179

Interpolating on a Surface

188

Least-Squares Approximations 199

Exercises 209

Applied Problems and Projects 215

Approximation of Functions 220

Contents of This Chapter 220

Contents vii

4.1 Chebyshev Polynomials and Chebyshev Series 221

4.2 Rational Function Approximations 232

4.3 Fourier Series 240

Exercises 252

Applied Problems and Projects 254

5 Numerical Differentiation and ntegration 256

Contents of This Chapter 257

Differentiation with a Computer 258

Numerical Integration-The Trapezoidal Rule 272

Simpson's Rules 280

An Application of Numerical Integration-Fourier

Series

and Fourier

Transforms

285

Adaptive Integration 297

Gaussian Quadrature 301

Multiple Integrals 307

Applications of Cubic Splines 3

17

Exercises 321

Applied Problems and Projects 326

6 Numerical Solution of Ordinary

Differential Equations

329

Contents of This Chapter 330

The Taylor-Series Method 332

The Euler Method and Its Modifications 335

Runge- Kutta Methods 340

Multistep Methods 347

Higher-Order Equations and Systems 359

Stiff Equations 364

Boundary-Value Problems 366

Characteristic-Value Problems 38 1

Exercises 394

Applied Problems and Projects 399

viii Contents

7 Optimization 485

Contents of This Chapter 405

Finding the Minimum of

y = f(x) 406

Minimizing a Function of Several Variables 417

Linear Programming 428

Nonlinear Programming 442

Other Optimizations 449

Exercises 453

Applied Problems

and Projects 458

Partial-Differential Equations 461

Contents of This Chapter 463

8.1 Elliptic Equations 463

.2 Parabolic Equations 48 1 .3 Hyperbolic Equations 499

Exercises 509

Applied Problems and Projects 513

lement Analysis 517

Contents of This Chapter 5 18

9.1 Mathematical Background 5 18

9.2 Finite Elements for Ordinary-Differential Equations 526

9.3 Finite Elements for Partial-Differential Equations 535

Exercises 562

Applied Problems and Projects 564

Appendixes

A Some Basic Information from Calculus 567

B Software Resources 571

Answers to Selected Exercises 575

References 599

In this seventh edition, we continue on the path established in previous editions. Quoting from the preface of the sixth edition, we "retain the same features that have made the book popular: ease of reading so that the instructor does not have to 'interpret the book' for the student, many illustrative examples that often solve the same problem with different pro- cedures to clarify the comparison of methods, many exercises from which the instructor may choose appropriately for the class, more challenging problems and projects that show practical applications of the material." We have made substantial improvements on the previous edition. These include:

Theoretical matters that previously were in a

separa1:e section near the end of each chap- ter have been merged with the description of the procedures. Example computer programs that admittedly were not of professional quality have been deleted, with the idea that this is not normallly a programming course anyway. Easy-to-read algorithms have been retained so that students can write programs if they desire. There is greater emphasis on computer algebra systems;

MATLAB

is the predominant system, but this is compared with Maple and

Mathcmatica. The use of spreadsheets to

solve problems is covered as well. A new chapter on optimization (Chapter 7) has been added that includes multivariable cases as well as single-variable situations. Linear programming has been included, of course, but the treatment is intended to provide a real understanding of the simplex method rather than to merely give a recipe for solving the problem. Nonlinear program- ming is treated to contrast this with the simpler linear case. Boundary value problems for ordinary diffferential equations have been separated from those for partial differential equations and are inclutded in the chapter on ordinary dif- ferential equations. Partial differential equations that satisfy boundary conditions (ellip- tic equations) are combined with the other types of partial differential equations in a single chapter.

Preface

Many exercises have been modified or rewritten to provide an even greater variety. New exercises and projects have been added and some of these are more challenging than in the previous edition. As in previous editions, this book is unique in its inclusion of a thorough survey of numerical methods for solving partial differential equations and an introduction to the finite element method. Many suggestions from reviewers have allowed us to clarify and extend the treatment of several topics and we have made editorial changes to make the book easier to read and understand. We again quote from the preface to the sixth edition: Applied Numerical Analysis is written as a text for sophomores and juniors in engi- neering, science, mathematics, and computer science. It should be a valuable source book for practicing engineers. Because of its coverage of many numerical methods, the text can serve as a valuable reference. Although we assume that the student has a good knowledge of calculus, appropriate topics are reviewed in the context of their use. An appendix gives a summary of the most important items that are needed to develop and analyze numerical procedures. We purposely keep the mathematical notation simple for clarity. Furthermore, the answers to exercises marked with a b are found in the back of the text.

Acknowledgements

Many instructors have given valuable suggestions and constructive criticism. We mention those whose thorough reviews have helped make this edition better:

Todd Arbogast,

University of Texas at Austin

Neil Berger, University of Zllinois at Chicago

Barbara Bertram, Michigan Technological Sciences

Herman Gollwitzer, Drexel University

Chenyi Hu, University of Houston-Downtown

Tim Sauer, George Mason University

Daoqi Yang, Wayne State University

Kathie Yerion, Gonzaga University

We also want to express our thanks to those at Addison-Wesley who have worked extensively with us to ensure the publication of another quality edition: Greg

Tobin,

Bill Hoffman,

RoseAnne

Johnson, Cindy Cody, Pam Laskey, Heather Peck,

and Barbara Atkinson. relirnina This book teaches how a computer can be used to solve problems that may not be solvable by the techniques that are taught in most calculus courses.

It also shows how those prob-

lems that you may have solved before can be solved in a different way. Our emphasis is on problems that exist in the real world, although these examples will be simplified. Many of these simplified examples can be solved analytically, which allows a comparison with the computer-derived solution. Modern mathematics began when Isaac Newton found mathematical models that matched the empirical laws that Johannes Kepler had reached after about

20 years of

observation of the planets. Today, most of applied m~athematics is a repetition of what Newton did: to develop mathematical relationships that: can be used to simulate some real- world situation and to predict its response to different external factors. The beauty of mathematics is that it builds on simple cases to arrive at more complex and useful ones. This is true for this book-we start with mathematical applications that are easily understood but that become the basis for other, more important applications of numerical analysis.

Contents of fh,is, Chapter '

We begin each chapter of this book with a list of the topics that are discussed in that chapter.

0.1 Analysis Versus Numerical Analysis

Describes how numerical analysis differs from analytical analysis and shows where each has special advantages. It briefly lists the topics that will be covered in later chapters.

Chapter Zero: Preliminaries

Computers and Numerical Analysis

Explains why computers and numerical analysis are intimately related. It describes several ways by which a computer can be employed in carrying out the procedures.

An Illustrative Example

Tells how a typical problem is solved and uses a special program called a computer algebra system to obtain the solution.

Kinds of Errors in Numerical Procedures

Examines the important topic of the accuracy of computations and the different sources of errors. Errors that are due to the way that computers store numbers are examined in some detail.

Interval Arithmetic

Discusses one way to determine the effect of imprecise values in the equations that are used to model a real-world situation.

Parallel and Distributed Computing

Explains how numerical procedures can sometimes be speeded up by employing a number of computers working together on a problem. Some special difficulties encountered are mentioned.

Measuring the Efficiency of Numerical Procedures

Tells how one can compare the accuracy of different methods, all of which can accomplish a given task, and how they differ in their use of computing resources.

0.1 Analvsis Versus urnerical Analvsis

The word analysis in mathematics usually means to solve a problem through equations. Of course, the equations must then be reduced to an answer through the procedures of algebra, calculus, differential equations, partial differential equations, or the like. Numerical analy- sis is similar in that problems are solved, but now the only procedures that are used are arithmetic: add, subtract, multiply, divide, and compare. Since these operations are exactly those that computers can do, numerical analysis and computers are intimately related. An analytical answer is not always meaningful by itself. Consider this simple cubic equation: n3 - x2 - 3x + 3 = 0. It is not hard to find the factors that show that one of the roots is 6. That is fine, unless you want to cut a board to that length. But rulers are not graduated in square-root values. So what can you do? Maybe you have a calculator that lets you find the value, or you might

0.1: Analysis Versus Numerical Analysis 3

use logarithms, or look it up in a table. Numerical analysis has a rich store of methods to find the answer by purely arithmetical operations. Here's a challenge. You are on a desert island with nothing to work with but a sharp stick that you can use to draw in the sand. You've forgotten everything about mathematics except the four arithmetic operations and you can also compare values (much like a com- puter). For some reason, maybe because you have nothing more interesting to do, you want to get a good value for the cube root of 2. How would you go about this? One way would be trial and error: You try a set of values to see which one gives a result of

2 when it is mul-

tiplied three times, something like this:

1.2~ = 1.728 too small

1 .43 = 2.744 too la.rge

1

Z3 = 1.9531 pretty close

1.26~ = 2.0004 really close! This could go on for some time, but you begin to see that you could interpolate between the last two trials and get an even better answer. Now you say to yourself, "How good an answer do I really need? Maybe 1.26 is as close as I need. After all, when multiplied, 1 .263 gives a result that differs from 2.0000 by a very small number, 0.0004." In this book, we will describe methods that can solve this little problem efficiently and also methods for much more difficult ones. For example, this integral, which gives the length of one arch of the curve y = sin(x), has no closed form solution: Tr

J dl + cos2(x) dx.

0 Numerical analysis can compute the length of this curve by standardized methods that apply to essentially any integrand; there is never a need to make a special substitution or to do integration by parts. Further, the only mathematical operations required are addition, subtraction, multiplication, and division, plus doing comparisons. Another difference between a numerical result and the analytical answer is that the for- mer is always an approximation. Analytical methods usually give the result in terms of mathematical functions that can be evaluated for a specific instance. This also has the advantage that the behavior and properties of the functl~on are often apparent; this is not the case for a numerical answer. However, numerical results can be plotted to show some of the behavior of the solution. While the numerical result is an approximation, this can usually be as accurate as needed. The necessary accuracy is, of course, determined by the application. The -?JZ example suggests that the accuracy desired depends totally on the context of the problem. (There are limitations to the achievable level of accuracy, because of the way that com- puters do arithmetic; we will explain these limitations later.) To achieve high accuracy, very many separate operations must be carried out, but computers do them so rapidly without ever making mistakes that this is no significant problem. Actually, evaluating an analytical result to get the numerical answer for a specific application is subject to the same errors.

Chapter Zero: Preliminaries

The analysis of computer errors and the other sources of error in numerical methods is a critically important part of the study of numerical analysis. This subject will occur often throughout this book. Here are those operations that numerical analysis can do and that are covered in this book: Find wherefix) = 0 for a nonlinear equation or system of equations. Solve systems of linear equations, even large systems. Interpolate to find intermediate values from a table of values and fit curves to experi- mental data. Approximate functions with polynomials or with a ratio of polynomials. Approximate values for the derivatives of a function, even if this is known only by a table of function values. Evaluate the definite integral for any integrand, even if its values are known only from experimental observations. Solve differential equations when initial values are given; these can be of any order and complexity. Numerical analysis can even solve them if conditions are specified at the boundaries of a region. Find the minima or maxima of functions, even when subject to constraints. Solve all types of partial differential equations by several techniques.

0.2 Computers and Numerical Analysis

Numerical methods require such tedious and repetitive arithmetic operations that only when we have a computer to carry out these many separate operations is it practical to solve problems in this way. A human would make so many mistakes that there would be little confidence in the result. Besides, the manpower cost would be more than could nor- mally be afforded. (Once upon a time, military firing tables were computed by hand using desk calculators, but that was a special case of national emergency before computers were available.) Of course, a computer is essentially dumb and must be given detailed and complete instructions for every single step it is to perform.

In other words, a computer program must

be written so the computer can do numerical analysis. As you study this book, you will learn enough about the many numerical methods available that you will be able to write programs to implement them. The specific computer language used is not very important; programs can be written in BASIC (many dialects), FORTRAN, Pascal, C, C+ +, Java, and even assembly language. Most of the methods will be described fully through pseudocode in such a form that translating this code into a program is relatively straightforward. Actually, writing programs is not always necessary. Numerical analysis is so important that extensive commercial software packages are available. The IMSL (International

Mathematical and Statistical Library)

MATHILIBRARY

has hundreds of routines, of efficient and of proven performance, written in FORTRAN and

C that carry out the

0.2: Computers and Numerical Analysis 5

methods. Recently, LAPACK (Linear Algebra Package) has been made available at nominal cost. This package of FORTRAN programs incorporates the subroutines that were con- tained in the earlier packages of LINPACK and EISPACK. Appendix

B of this book gives

information on these and other programs. The bimonthly newsletter of the Society for

Industrial and Applied Mathematics

(SIAM News) contains discussions and advertisements on some of the latest packages. A set of books,

Nu?nerical

Recipes, lists and discusses

numerical analysis programs in a variety of languages: FORTRAN, Pascal, and C. One important trend in computer operations is the use of several processors working in parallel to carry out procedures with greater speed than can be obtained with a single processor. Some numerical analysis procedures can be carried out this way. Special programming techniques are needed to utilize these fast computer systems. A recent devel- opment is to utilize computers that are idle, even personal computers, to carry out compu- tations. If these idle computers are connected in a network, a control computer can send a portion of a large computation to them. After completmg its part of the task, the individual computers transmit the results back to the control computer. Such an arrangement is termed distributed computing. As you can imagine, cfoordinating and controlling this dis- tributed system is a difficult task.

An alternative to using a program written in one

of'the higher-level languages is to use a kind of software sometimes called a computer algebra system (CAS). (This name is not very standardized and not too descriptive.") This kind of program mimics the way humans solve mathematical problems. Such a program is designed to recognize the type of func- tion (polynomial, transcendental, etc.) presented and then to carry out requested mathe- matical operations on the function or expression. It does so by looking up in tables the new expressions that result from doing the operation or by using a set of built-in-rules. For example, a program can use the ordinary rules for finding derivatives, employ tables of integrals to do integrations, and factor a polynomial or expand a set of factors. These are only a few of the capabilities. If an analytical answer cannot be given, most of these pro- grams allow the user to get an answer by numerical methods. In connection with numerical analysis, an important feature of many such programs is the ability to write utility files that are essentially macros:

A sequence of the built-in oper-

ations is defined to perform a desired larger task or one not inherent in the program. A suc- cession of operations, each of which uses the results of the previous one-a procedure called iteration-is also possible. Many numerical analysis procedures are iterative.

Many computer algebra systems are available.

R7e will discuss only three of these: Mathematics, MATLAB, and Maple. MATLAB will be used extensively; it will be sup- plemented and compared to the other two. In this chapter, we will show how

MATLAB

can plot a function and find where it is a minimum. We anticipate that you will use one of the computer algebra systems as a tool to explore numerical procedures.quotesdbs_dbs20.pdfusesText_26

[PDF] numerical analysis bsc 3rd year

[PDF] numerical analysis handwritten notes pdf

[PDF] numerical analysis pdf download

[PDF] numerical analysis pdf for computer science

[PDF] numerical analysis pdf s.s sastry

[PDF] numerical analysis pdf sauer

[PDF] numerical analysis pdf solutions

[PDF] numerical analysis questions and answers pdf

[PDF] numerical mathematical analysis pdf

[PDF] numerical methods for computer science pdf

[PDF] numerical methods for engineering and science by saumyen guha pdf

[PDF] numerical methods for scientific and engineering computation 4th edition pdf

[PDF] numerical methods for solving system of nonlinear equations

[PDF] numerical methods in civil engineering book pdf

[PDF] numerical methods journal pdf