A Friendly Introduction to Numerical Analysis / Edition 1

by Brian Bradie

Overview

This reader-friendly introduction to the fundamental concepts and techniques of numerical analysis/numerical methods develops concepts and techniques in a clear, concise, easy-to- read manner, followed by fully-worked examples. Application problems drawn from the literature of many different fields prepares readers to use the techniques covered to solve a wide variety of practical problems. KEY TOPICS: Rootfinding. Systems of Equations. Eigenvalues and Eigenvectors. Interpolation and Curve Fitting. Numerical Differentiation and Integration. Numerical Methods for Initial Value Problems of Ordinary Differential Equations. Second-Order One-Dimensional Two-Point Boundary Value Problems. Finite Difference Method for Elliptic Partial Differential Equations. Finite Difference Method for Parabolic Partial Differential Equations. Finite Difference Method for Hyperbolic Partial Differential Equations and the Convection-Diffusion Equation. MARKET: For anyone interested in numerical analysis/methods and their applications in many fields

Product Details

ISBN-13:	9780130130549
Publisher:	Pearson Education
Publication date:	04/26/2005
Series:	Featured Titles for Numerical Analysis Series
Edition description:	New Edition
Pages:	984
Product dimensions:	7.00(w) x 9.20(h) x 1.90(d)

Read an Excerpt

This is an introduction to the fundamental concepts and techniques of numerical analysis and numerical methods for undergraduates, as well as for graduate engineers arid applied scientists receiving their first exposure to numerical analysis. Applications drawn from the literature of many different fields will prepare students to use the techniques covered to solve a wide variety of practical problems. There is also sufficient mathematical detail to prepare students to embark upon an investigation of more advanced topics, especially in PDEs. The presentation style is what I like to call tell and show. This means that the concepts and techniques are first developed in a clear, concise, and easy-to-read manner, and then illustrated with at least one fully worked example. In total, nearly 250 fully worked examples are presented to help the students grasp the sequence of calculations associated with a particular method and gain better insight into algorithm operation.

The text is organized around mathematical problems, with each chapter devoted to a single type of problem (e.g., rootfinding, numerical calculus: differentiation and integration, the matrix eigenvalue problem, and elliptic partial differential equations). Within each chapter the presentation begins with the simplest and most basic methods, progressing gradually to more advanced topics. Early chapters generally contain easier material, while later chapters proceed at increasing levels of difficulty and complexity. Throughout, emphasis is placed on understanding and being able to work with the key concepts of rate/order of convergence and stability, and assessing the accuracy of numerical results. This emphasis helpsstudents develop skill in numerically verifying theoretical convergence speed. More importantly, the text emphasizes that it is not sufficient to obtain the correct answer from a numerical algorithm; one must also check that convergence toward the correct answer is happening at the correct speed. I have always felt very strongly that a textbook must provide students with some means of checking their understanding and honing their skills, some means of making the knowledge their own. This is invariably accomplished through the exercises. This text features more than 1200 numbered exercises (many with multiple parts) organized into exercise sets at the end of each section. Each exercise set contains problems designed to provide students with the opportunity to practice (with paper, pencil, and calculator) the sequence of calculations associated with a particular method. The exercises usually also require the verification of theoretical error bounds and/or theoretical rates of convergence. Additional exercises may require the derivation of a method, an examination of conditions under which methods perform better or worse than predicted by theory, or extension of material presented in the section. Many exercises require students to code a numerical method on the computer and then use that computer code, and many exercises are application problems that require interpretation of results. Distinctive Features

A quick scan of the table of contents will reveal that certain topics typically found in a book of this nature, such as approximation (orthogonal least-squares, FFT, rational function approximation) and optimization, have been omitted. In place of these topics is an extensive coverage of material not usually found, or only briefly discussed, in other texts. This extensive coverage includes treatment of non-Dirichlet boundary conditions, and artificial singularities for one-dimensional boundary value problems; treatment of non-Dirichlet boundary conditions, the multigrid method and irregular domains for elliptic partial differential equations; treatment of source and decay terms, non-Dirichlet boundary conditions, polar coordinates and problems in two space dimensions for parabolic partial differential equations; and treatment of the advection and convection-diffusion equations. Why did I select such nom-standard topics for inclusion? My primary objective in writing this text was to create a book that would allow students to immediately apply the numerical techniques they have learned to real-world problems. After reviewing technical journals and textbooks to determine the most commonly used basic numerical techniques and discussing topics with my colleagues and non-academic scientists/engineers, I felt that students would benefit more from an expanded coverage of boundary value problems and partial differential equations than they would from a superficial coverage of these same topics and inclusion of those topics which have been omitted.

In keeping with the objective of preparing students to apply numerical techniques, an extensive set of application problems has been compiled from the literature of many different fields. Physics, biology, chemistry, chemical engineering, thermodynamics, heat transfer, electrostatics, ecology, manufacturing and sociology are among the fields represented. Each chapter opens with outlines of several real-world problems which serve to motivate the study and to demonstrate the broad applicability of the class of methods which will be treated in that chapter. Application problems then appear throughout the chapter as both worked examples and exercises. An added benefit of the application problems is that they afford the opportunity to discuss practical issues, such as introducing nondimensional variables, treating singularities, and manipulating problems into the form required by a particular method. Perhaps the most distinctive feature of this book is the minimal amount of pseudocode which appears. This feature is in marked contrast to other introductory textbooks on numerical analysis, which tend to have a lot of pseudocode, and usually some Maple and/or MATLAB code fragments, too. Unfortunately, it has been my experience that most students don't use pseudocode properly. What is intended by an author as a teaching tool, more often than not, is used by the students just to expedite the completion of an assignment. Instead of digging through each line of code to develop a deeper understanding of how and why each method works, the student simply translates the code into whatever happens to be the language of choice: When this happens, little or no transfer of knowledge takes place. The end result in such a case is that the presence of pseudocode hinders, rather than promotes, student learning. For this reason, I have chosen to include eudocode only when the natural language description of an algorithm became too mbersome or when the pseudocode was needed to develop some other essential idea. Although pseudocode has largely been removed, students have most certainly not been left without guidance in the production of efficient, working code. Where appropriate, programming hints have been provided, and important implementation details have been discussed. Then, of course, there are the worked examples. These provide dynamic demonstrations for each of the algorithms being developed and contain sufficient detail to suggest an overall structure for the implementation of the algorithm. Furthermore, to recognize that structure, the student will have to become actively involved with the details of the example. Thus, when compared with pseudocode, which is a static representation of an algorithm, worked examples are, in my opinion, the superior alternative. Supplements and Software

This text is accompanied by an Instructors Solutions Manual that can be obtained (by instructors only) by contacting either the local Prentice Hall sales rep or [e-mail]. There are also 70 plus pages of Answers to Selected Exercises for students, found on the website

www.pcs.cnu.edu/~bbradie/textbookanswers.html

To accommodate differing viewpoints on the pseudocode issue, implementations for all of the methods developed in the text can be downloaded via the Internet. Each method is available in MATLAB and C++ formats. Depending upon demand, Maple, Mathematica, MathCad and Fortran implementations may be added. Instructions for using the MATLAB functions are contained in the header of the corresponding m-file and are accessible through the standard MATLAB help (function name) facility. Each C++ function is described in the comments at the beginning of the code. The main page for obtaining the software is located at www.pcs.cnu.edu/~bbradie/textbookcode.html. To the Student

The best advice that I can give for working with this textbook is to be an active reader. This means that each time you come to a worked example, you should verify the results of all calculations on your own and attempt to fill in all of the missing details. A similar procedure should be employed for each proof that you read. Working in this fashion will not only hone your general mechanical and analytical skills, but will also significantly improve your understanding of how and why each numerical method works, and will stimulate the process by which you assimilate new knowledge and make it your own. The most common stumbling block encountered by numerical analysis students is difficulty in translating the natural language description of an algorithm into working computer code. Here is a scheme that you may find helpful in overcoming this problem. Start by identifying the inputs. The inputs should include every item that must be known for the code to perform its intended task. Don't forget values that are needed to control the termination of an iterative process. Next, identify the outputs, which are, of course, the values which the code is supposed to compute. Once the inputs and the outputs have been clearly identified, focus on the construction of a logical and well-defined sequence of steps that will produce the outputs from the inputs. The worked examples should prove extremely useful at this point. Finally, convert each step into the appropriate set of assignment statements, conditional/branching statements, loop structures and function calls. As with any new skill, the more you practice, the better you will become.

Table of Contents

(NOTE: Each chapter begins with An Overview.)

1. Getting Started.

Algorithms. Convergence. Floating Point Numbers. Floating Point Arithmetic.

2. Rootfinding.

Bisection Method. Method of False Position. Fixed Point Iteration. Newton's Method. The Secant Method and Muller's Method. Accelerating Convergence. Roots of Polynomials.

3. Systems of Equations.

Gaussian Elimination. Pivoting Strategies. Norms. Error Estimates. LU Decomposition. Direct Factorization. Special Matrices. Iterative Techniques for Linear Systems: Basic Concepts and Methods. Iterative Techniques for Linear Systems: Conjugate-Gradient Method. Nonlinear Systems.

4. Eigenvalues and Eigenvectors.

The Power Method. The Inverse Power Method. Deflation. Reduction to Tridiagonal Form. Eigenvalues of Tridiagonal and Hessenberg Matrices.

5. Interpolation and Curve Fitting.

Lagrange Form of the Interpolating Polynomial. Neville's Algorithm. The Newton Form of the Interpolating Polynomial and Divided Differences. Optimal Interpolating Points. Piecewise Linear Interpolation. Hermite and Hermite Cubic Interpolation. Regression.

6. Numerical Differentiation and Integration.

Continuous Theory and Key Numerical Concepts. Euler's Method. Higher-Order One-Step Methods. Multistep Methods. Convergence Analysis. Error Control and Variable Step Size Algorithms. Systems of Equations and Higher-Order Equations. Absolute Stability and Stiff Equations.

7. Numerical Methods for Initial Value Problems of Ordinary Differential Equations.

Continuous Theory and Key Numerical Concepts. Euler's Method. Higher-Order One-Step Methods. Multistep Methods. Convergence Analysis. Error Control and Variable Step Size Algorithms. Systems of Equations and Higher-Order Equations. Absolute Stability and Stiff Equations.

8. Second-Order One-Dimensional Two-Point Boundary Value Problems.

Finite Difference Method, Part I: The Linear Problem with Dirichlet Boundary Conditions. Finite Difference Method, Part II: The Linear Problem with Non-Dirichlet Boundary Conditions. Finite Difference Method, Part III: Nonlinear Problems. The Shooting Method, Part I: Linear Boundary Value Problems. The Shooting Method, Part II: Nonlinear Boundary Value Problems.

9. Finite Difference Method for Elliptic Partial Differential Equations.

The Poisson Equation on a Rectangular Domain, I: Dirichlet Boundary Conditions. The Poisson Equation on a Rectangular Domain, II: Non-Dirichlet Boundary Conditions. Solving the Discrete Equations: Relaxation Schemes. Local Mode Analysis of Relaxation and the Multigrid Method. Irregular Domains.

10. Finite Difference Method for Parabolic Partial Differential Equations.

The Heat Equation with Dirichlet Boundary Conditions. Stability. More General Parabolic Equations. Non-Dirichlet Boundary Conditions. Polar Coordinates. Problems in Two Space Dimensions.

11. Finite Difference Method for Hyperbolic Partial Differential Equations and the Convection-Diffusion Equation.

Advection Equation, I: Upwind Differencing. Advection Equation, II: MacCormack Method. Convection-Diffusion Equation. The Wave Equation.

Appendices.

Appendix A. Important Theorems from Calculus. Appendix B. Algorithm for Solving a Tridiagonal System of Linear Equations.

References.


Index.

Answers to Selected Problems.

Preface

This is an introduction to the fundamental concepts and techniques of numerical analysis and numerical methods for undergraduates, as well as for graduate engineers arid applied scientists receiving their first exposure to numerical analysis. Applications drawn from the literature of many different fields will prepare students to use the techniques covered to solve a wide variety of practical problems. There is also sufficient mathematical detail to prepare students to embark upon an investigation of more advanced topics, especially in PDEs. The presentation style is what I like to call tell and show. This means that the concepts and techniques are first developed in a clear, concise, and easy-to-read manner, and then illustrated with at least one fully worked example. In total, nearly 250 fully worked examples are presented to help the students grasp the sequence of calculations associated with a particular method and gain better insight into algorithm operation.

The text is organized around mathematical problems, with each chapter devoted to a single type of problem (e.g., rootfinding, numerical calculus: differentiation and integration, the matrix eigenvalue problem, and elliptic partial differential equations). Within each chapter the presentation begins with the simplest and most basic methods, progressing gradually to more advanced topics. Early chapters generally contain easier material, while later chapters proceed at increasing levels of difficulty and complexity. Throughout, emphasis is placed on understanding and being able to work with the key concepts of rate/order of convergence and stability, and assessing the accuracy of numerical results. This emphasis helps students develop skill in numerically verifying theoretical convergence speed. More importantly, the text emphasizes that it is not sufficient to obtain the correct answer from a numerical algorithm; one must also check that convergence toward the correct answer is happening at the correct speed. I have always felt very strongly that a textbook must provide students with some means of checking their understanding and honing their skills, some means of making the knowledge their own. This is invariably accomplished through the exercises. This text features more than 1200 numbered exercises (many with multiple parts) organized into exercise sets at the end of each section. Each exercise set contains problems designed to provide students with the opportunity to practice (with paper, pencil, and calculator) the sequence of calculations associated with a particular method. The exercises usually also require the verification of theoretical error bounds and/or theoretical rates of convergence. Additional exercises may require the derivation of a method, an examination of conditions under which methods perform better or worse than predicted by theory, or extension of material presented in the section. Many exercises require students to code a numerical method on the computer and then use that computer code, and many exercises are application problems that require interpretation of results.

Distinctive Features

A quick scan of the table of contents will reveal that certain topics typically found in a book of this nature, such as approximation (orthogonal least-squares, FFT, rational function approximation) and optimization, have been omitted. In place of these topics is an extensive coverage of material not usually found, or only briefly discussed, in other texts. This extensive coverage includes treatment of non-Dirichlet boundary conditions, and artificial singularities for one-dimensional boundary value problems; treatment of non-Dirichlet boundary conditions, the multigrid method and irregular domains for elliptic partial differential equations; treatment of source and decay terms, non-Dirichlet boundary conditions, polar coordinates and problems in two space dimensions for parabolic partial differential equations; and treatment of the advection and convection-diffusion equations. Why did I select such nom-standard topics for inclusion? My primary objective in writing this text was to create a book that would allow students to immediately apply the numerical techniques they have learned to real-world problems. After reviewing technical journals and textbooks to determine the most commonly used basic numerical techniques and discussing topics with my colleagues and non-academic scientists/engineers, I felt that students would benefit more from an expanded coverage of boundary value problems and partial differential equations than they would from a superficial coverage of these same topics and inclusion of those topics which have been omitted.

In keeping with the objective of preparing students to apply numerical techniques, an extensive set of application problems has been compiled from the literature of many different fields. Physics, biology, chemistry, chemical engineering, thermodynamics, heat transfer, electrostatics, ecology, manufacturing and sociology are among the fields represented. Each chapter opens with outlines of several real-world problems which serve to motivate the study and to demonstrate the broad applicability of the class of methods which will be treated in that chapter. Application problems then appear throughout the chapter as both worked examples and exercises. An added benefit of the application problems is that they afford the opportunity to discuss practical issues, such as introducing nondimensional variables, treating singularities, and manipulating problems into the form required by a particular method. Perhaps the most distinctive feature of this book is the minimal amount of pseudocode which appears. This feature is in marked contrast to other introductory textbooks on numerical analysis, which tend to have a lot of pseudocode, and usually some Maple and/or MATLAB code fragments, too. Unfortunately, it has been my experience that most students don't use pseudocode properly. What is intended by an author as a teaching tool, more often than not, is used by the students just to expedite the completion of an assignment. Instead of digging through each line of code to develop a deeper understanding of how and why each method works, the student simply translates the code into whatever happens to be the language of choice: When this happens, little or no transfer of knowledge takes place. The end result in such a case is that the presence of pseudocode hinders, rather than promotes, student learning. For this reason, I have chosen to include eudocode only when the natural language description of an algorithm became too mbersome or when the pseudocode was needed to develop some other essential idea. Although pseudocode has largely been removed, students have most certainly not been left without guidance in the production of efficient, working code. Where appropriate, programming hints have been provided, and important implementation details have been discussed. Then, of course, there are the worked examples. These provide dynamic demonstrations for each of the algorithms being developed and contain sufficient detail to suggest an overall structure for the implementation of the algorithm. Furthermore, to recognize that structure, the student will have to become actively involved with the details of the example. Thus, when compared with pseudocode, which is a static representation of an algorithm, worked examples are, in my opinion, the superior alternative.

Supplements and Software

This text is accompanied by an Instructors Solutions Manual that can be obtained (by instructors only) by contacting either the local Prentice Hall sales rep or [e-mail]. There are also 70 plus pages of Answers to Selected Exercises for students, found on the website

www.pcs.cnu.edu/~bbradie/textbookanswers.html

To accommodate differing viewpoints on the pseudocode issue, implementations for all of the methods developed in the text can be downloaded via the Internet. Each method is available in MATLAB and C++ formats. Depending upon demand, Maple, Mathematica, MathCad and Fortran implementations may be added. Instructions for using the MATLAB functions are contained in the header of the corresponding m-file and are accessible through the standard MATLAB help (function name) facility. Each C++ function is described in the comments at the beginning of the code. The main page for obtaining the software is located at www.pcs.cnu.edu/~bbradie/textbookcode.html .

To the Student

The best advice that I can give for working with this textbook is to be an active reader. This means that each time you come to a worked example, you should verify the results of all calculations on your own and attempt to fill in all of the missing details. A similar procedure should be employed for each proof that you read. Working in this fashion will not only hone your general mechanical and analytical skills, but will also significantly improve your understanding of how and why each numerical method works, and will stimulate the process by which you assimilate new knowledge and make it your own. The most common stumbling block encountered by numerical analysis students is difficulty in translating the natural language description of an algorithm into working computer code. Here is a scheme that you may find helpful in overcoming this problem. Start by identifying the inputs. The inputs should include every item that must be known for the code to perform its intended task. Don't forget values that are needed to control the termination of an iterative process. Next, identify the outputs, which are, of course, the values which the code is supposed to compute. Once the inputs and the outputs have been clearly identified, focus on the construction of a logical and well-defined sequence of steps that will produce the outputs from the inputs. The worked examples should prove extremely useful at this point. Finally, convert each step into the appropriate set of assignment statements, conditional/branching statements, loop structures and function calls. As with any new skill, the more you practice, the better you will become.

Editorial Reviews

"I am extremely impressed with Bradie's book. His passion for explaining things as clearly and understandably as possible, his thorough research of the literature for bringing relevant and pedagogically sound examples from outside mathematics, and his crisp and clear style will certainly make this text an instant success. This is one of the better texts in Numerical Analysis that I have ever seen, and I congratulate the author for producing such a gem." — Alejandro Engel, Rochester Institute of Technology

"The chapters in this book are of uniformly high standards. Chapter 1 in particular is a gem. The treatments of floating point number systems and of floating point arithmetic are especially good. These are topics that are often glossed over in other books, and which are often difficult for students to grasp. The book is extremely well written: the style is clear, the prose flows smoothly, the pace is unhurried, the tone is friendly and conversational, the examples and exercises are interesting and-relevant, and the amount of detail is far greater than in any textbook of its kind that I have ever seen. For these reasons, it will certainly appeal to my students." — Richard Zalik, Auburn University

"I think the tone will appeal to my students: It is relaxed and friendly without being wordy and effusive. The style is a very readable compromise between proof and technical detail on the one hand, and concepts with applications on the other. I think he addresses this fundamental challenge in a way that my students would like. Bradie has decided to include lots of worked examples accompanied by plots. The plots facilitate the inclusion of such a large number of examples, by succinctly communicating the point of each. This reduces the effort needed to understand the ideas behind the example, (I think students simply will not read the book if it takes too much effort. Bradie can include more exercises than is typical because the illustrations ease the communication.)" — Mark Arnold, University of Arkansas

"I like the way Bradie presents the materials in each chapter. He gives a mathematics review on what is needed at the beginning of each chapter. After refreshing students' memories, he begins with the simplest, most basic methods and then progresses gradually to more advanced topics. The book is well written and student-friendly. It provides a lot of examples and exercise problems. The book is written in the way that is easy for students to read. For instance, for each method, there is at least one fully worked example that helps students to understand the concept and the method." — Kuiyuan Li, University of West Florida

From the Publisher