The additional material in this edition should permit instructors to prepare an under graduate course in Numerical Linear Algebra for students who have not previously studied numerical Analysis. This could be done by covering Chapters 1, 6, 7, and 9, and then, as time permits, including other material of the instructor's choice Acknowledgments We have been fortunate to have had many of our students and colleagues give us their that essions of earlier editions of this book. We have tried to include all the suggestions that complement the philosophy of the book, and we are extremely grateful to all those who have taken the time to contact us about ways to improve subsequent versions We would particularly like to thank the following, whose suggestions we have used in this and previous editions John Carroll, Dublin City University (Ireland) Gustav Delius, University of York (UK) Pedro Jose Paul Escolano, University of Sevilla(Spain) Warren Hickman, Westminster College Jozsi Jalics, Youngstown State University Dan Kalman, American University Robert Lantos, University of Ottawa( Canada) Eric Rawdon, Duquesne University illip Schmidt, University of Northern Kentucky Kathleen Shannon, Salisbury Ur Roy Simpson, State University of New York, Stony Brook Dennis C Smolarski, Santa Clara University James Verner, Simon Fraser University( Canada) Andre Weideman, University of Stellenbosch(South Africa) Joan Weiss, Fairfield University of massachusetts at Amherst Dick Wood, Seattle Pacific University George Yates, Youngstown State University As has been our practice in past editions of the book, we used undergraduate student elp at Youngstown State University in preparing the ninth edition. Our assistant for this edition was Mario Sracic, who checked the new Maple code in the book and worked as our in-house copy editor. In addition, Edward Burden has been checking all the programs that accompany the text. We would like to express gratitude to our colleagues on the faculty and Copyright 2010 Cengage Learning. All Rights t materially affect the overall leaming eaperience Cengage Learning reserves the right to remo rty commen may be suppressed from the eBook andor eChaptert'sh. May no be copied, scanned, or duplicated, in whole or in part Due to
Preface xiii The additional material in this edition should permit instructors to prepare an undergraduate course in Numerical Linear Algebra for students who have not previously studied Numerical Analysis. This could be done by covering Chapters 1, 6, 7, and 9, and then, as time permits, including other material of the instructor’s choice. Acknowledgments We have been fortunate to have had many of our students and colleagues give us their impressions of earlier editions of this book. We have tried to include all the suggestions that complement the philosophy of the book, and we are extremely grateful to all those who have taken the time to contact us about ways to improve subsequent versions. We would particularly like to thank the following, whose suggestions we have used in this and previous editions. John Carroll, Dublin City University (Ireland) Gustav Delius, University of York (UK) Pedro José Paúl Escolano, University of Sevilla (Spain) Warren Hickman, Westminster College Jozsi Jalics, Youngstown State University Dan Kalman, American University Robert Lantos, University of Ottawa (Canada) Eric Rawdon, Duquesne University Phillip Schmidt, University of Northern Kentucky Kathleen Shannon, Salisbury University Roy Simpson, State University of New York, Stony Brook Dennis C. Smolarski, Santa Clara University Richard Varga, Kent State University James Verner, Simon Fraser University (Canada) André Weideman, University of Stellenbosch (South Africa) Joan Weiss, Fairfield University Nathaniel Whitaker, University of Massachusetts at Amherst Dick Wood, Seattle Pacific University George Yates, Youngstown State University As has been our practice in past editions of the book, we used undergraduate student help at Youngstown State University in preparing the ninth edition. Our assistant for this edition was Mario Sracic, who checked the new Maple code in the book and worked as our in-house copy editor. In addition, Edward Burden has been checking all the programs that accompany the text. We would like to express gratitude to our colleagues on the faculty and 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 administration of Youngstown State University for providing us the opportunity, facilities and encouragement to complete this project. We would also like to thank some people who have made significant contributions to the history of numerical methods. Herman H. Goldstine has written an excellent book entitled A History of Numerical Analysis from the 16th Through the 19th Century [Golds] In addition, The words of mathematics [Schw], by Steven Schwartzman has been a help in compiling our historical material. Another source of excellent historical mathematical knowledge is the MacTutor History of Mathematics archive at the University of St Andrews in Scotland. It has been created by John J O'Connor and Edmund F. Robertson and has the http://www-gap.dcs.st-and.ac.uk/-history/ An incredible amount of work has gone into creating the material on this site, and we have found the information to be unfailingly accurate. Finally, thanks to all the contributors to wikipedia who have added their expertise to that site so that others can benefit from their In closing, thanks again to those who have spent the time and effort to contact us over the years. It has been wonderful to hear from so many students and faculty who used our book for their first exposure to the study of numerical methods. We hope this edition continues this exchange, and adds to the enjoyment of students studying numerical analysis If you have any suggestions for improving future editions of the book, we would, as always be grateful for your comments. We can be contacted most easily by electronic mail at the addresses listed below RichardBurden burden @math. ysu. edu J. Douglas faires faires @math. ysu. edu Copyright 2010 Cengage Learning. All Rights t materially affect the overall leaming eaperience Cengage Learning reserves the right to remo rty commen may be suppressed from the eBook andor eChaptert'sh. May no be copied, scanned, or duplicated, in whole or in part Due to
xiv Preface administration of Youngstown State University for providing us the opportunity, facilities, and encouragement to complete this project. We would also like to thank some people who have made significant contributions to the history of numerical methods. Herman H. Goldstine has written an excellent book entitled A History of Numerical Analysis from the 16th Through the 19th Century [Golds]. In addition, The words of mathematics [Schw], by Steven Schwartzman has been a help in compiling our historical material. Another source of excellent historical mathematical knowledge is the MacTutor History of Mathematics archive at the University of St. Andrews in Scotland. It has been created by John J. O’Connor and Edmund F. Robertson and has the internet address http://www-gap.dcs.st-and.ac.uk/∼history/ . An incredible amount of work has gone into creating the material on this site, and we have found the information to be unfailingly accurate. Finally, thanks to all the contributors to Wikipedia who have added their expertise to that site so that others can benefit from their knowledge. In closing, thanks again to those who have spent the time and effort to contact us over the years. It has been wonderful to hear from so many students and faculty who used our book for their first exposure to the study of numerical methods. We hope this edition continues this exchange, and adds to the enjoyment of students studying numerical analysis. If you have any suggestions for improving future editions of the book, we would, as always, be grateful for your comments. We can be contacted most easily by electronic mail at the addresses listed below. Richard L. Burden burden@math.ysu.edu J. Douglas Faires faires@math.ysu.edu 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
CHAPTER Mathematical preliminaries and Error analysis Introduction In beginning chemistry courses, we see the ideal gas law, PV= NRT which relates the pressure P, volume V, temperature T, and number of moles N of an "ideal"gas. In this equation, R is a constant that depends on the measurement system. Suppose two experiments are conducted to test this law, using the same gas in each case. In the first experiment, P=1.00atm, V=0.100m N=0.00420mol,R=0.08206 The ideal gas law predicts the temperature of the gas to be PV(1.00)(0.100) NR(0.00420)(0.08206) =290.15K=17°C When we measure the temperature of the gas however, we find that the true temperature is 15°C. We then repeat the experiment using the same values of R and N, but increase the pressure by a factor of two and reduce the volume by the same factor. The product PV remains the same, so the predicted temperature is still 17C. But now we find that the actual temperature of the gas is 19C t materially affect the overal leaming eperience. Cengage Learning reserves the right b remove arty oomen may be suppressed from the eBook andor eChapterts). Copynight 2010 Cengage Learning. All Rights Reserved, May no be copied, scanned
CHAPTER 1 Mathematical Preliminaries and Error Analysis Introduction In beginning chemistry courses, we see the ideal gas law, PV = NRT, which relates the pressure P, volume V, temperature T, and number of moles N of an “ideal” gas. In this equation, R is a constant that depends on the measurement system. Suppose two experiments are conducted to test this law, using the same gas in each case. In the first experiment, P = 1.00 atm, V = 0.100 m3 , N = 0.00420 mol, R = 0.08206. The ideal gas law predicts the temperature of the gas to be T = PV NR = (1.00)(0.100) (0.00420)(0.08206) = 290.15 K = 17◦ C. When we measure the temperature of the gas however, we find that the true temperature is 15◦C. V1 V2 We then repeat the experiment using the same values of R and N, but increase the pressure by a factor of two and reduce the volume by the same factor. The product PV remains the same, so the predicted temperature is still 17◦C. But now we find that the actual temperature of the gas is 19◦C. 1 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
CHAPTER 1 Mathematical Preliminaries and Error Analysis Clearly, the ideal gas law is suspect, but before concluding that the law is invalid in this situation we should examine the data to see whether the error could be attributed to the experimental results. If so, we might be able to determine how much more accurate our experimental results would need to be to ensure that an error of this magnitude did not Analysis of the error involved in calculations is an important topic in numerical analysi and is introduced in Section 1. 2. This particular application is considered in Exercise 28 of that section This chapter contains a short review of those topics from single-variable calculus that will be needed in later chapters. A solid knowledge of calculus is essential for an understand ing of the analysis of numerical techniques, and more thorough review might be needed if you have been away from this subject for a while. In addition there is an introduction to onvergence, error analysis, the machine representation of numbers, and some techniques for categorizing and minimizing computational error. 1.1 Review of calculus Limits and Continuity The concepts of limit and continuity of a function are fundamental to the study of calculus, and form the basis for the analysis of numerical technique Definition 1.1 A function f defined on a set X of real numbers has the limit L at xo, written lim f(x)=L, x→ if, given any real number e>0, there exists a real number 8>0 such that lf(x)-L|<E, whenever x∈Xand0<x-xol<δ. (See Figure 1. 1.) 1.1 y=f(r) Copyright 2010 Cengage Learning. All Rights t materially affect the overall leaming eaperience Cengage Learning reserves the right to remo rty commen may be suppressed from the eBook andor eChaptert'sh. May no be copied, scanned, or duplicated, in whole or in part Due to
2 CHAPTER 1 Mathematical Preliminaries and Error Analysis Clearly, the ideal gas law is suspect, but before concluding that the law is invalid in this situation, we should examine the data to see whether the error could be attributed to the experimental results. If so, we might be able to determine how much more accurate our experimental results would need to be to ensure that an error of this magnitude did not occur. Analysis of the error involved in calculations is an important topic in numerical analysis and is introduced in Section 1.2. This particular application is considered in Exercise 28 of that section. This chapter contains a short review of those topics from single-variable calculus that will be needed in later chapters. A solid knowledge of calculus is essential for an understanding of the analysis of numerical techniques, and more thorough review might be needed if you have been away from this subject for a while. In addition there is an introduction to convergence, error analysis, the machine representation of numbers, and some techniques for categorizing and minimizing computational error. 1.1 Review of Calculus Limits and Continuity The concepts of limit and continuity of a function are fundamental to the study of calculus, and form the basis for the analysis of numerical techniques. Definition 1.1 A function f defined on a set X of real numbers has the limit L at x0, written lim x→x0 f (x) = L, if, given any real number ε > 0, there exists a real number δ > 0 such that |f (x) − L| < ε, whenever x ∈ X and 0 < |x − x0| < δ. (See Figure 1.1.) Figure 1.1 x L ε L ε L x0 δ x0 x0 δ y y f(x) 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.
1.1 Review of calculus Definition 1.2 Let f be a function defined on a set X of real numbers and xo E X. Then f is continuous The basic concepts of calculus at xo if and its applications were developed in the late 17th and lim f(r)=f(xo) arly 18th centuries. but the mathematically precise concepts The function f is continuous on the set X if it is continuous at each number in X of limits and continuity were not described until the time of The set of all functions that are continuous on the set X is denoted C(X). When X is an interval of the real line, the parentheses in this notation are omitted. For example, the (789-1857) Heinrich Eduard set of all functions continuous on the closed interval [a, b] is denoted CI Heine(1821-1881), and Karl R denotes the set of all real numbers, which also has the interval notation(-oo, oo). So Weierstrass(1815-1897) in the the set of all functions that are continuous at every real number is denoted by C(R)or by atter portion of the 19th century.C(-∞,∞) The limit of a sequence of real or complex numbers is defined in a similar manner Definition 1.3 Let (rnIng_, be an infinite sequence of real numbers. This sequence has the limit x(converges to x)if, for any e>0 there exists a positive integer N(E)such that lrn -xl E, whenever () lim x=x,orxn→xasn→∞, means that the sequence InnIng converges tox. Theorem 1.4 If f is a function defined on a set X of real numbers and xo E X, then the following a.f is continuous at b. If (n ne, is any sequence in X converging to xo, then limn-oo f(rn)=f(ro).B The functions we will consider when discussing numerical methods will be assumed to be continuous because this is a minimal requirement for predictable behavior. Functions that are not continuous can skip over points of interest, which can cause difficulties when attempting to approximate a solution to a problem. Differentiability More sophisticated assumptions about a function generally lead to better approximation results. For example, a function with a smooth graph will normally behave more predictably than one with numerous jagged features. The smoothness condition relies on the conce of the derivative Definition 1.5 Let f be a function defined in an open interval containing xo. The function f is differentiable if f(xo)= lim f(x)-f(x0) exists. The number f(xo)is called the derivative of f at xo. A function that has a derivative at each number in a set x is differentiable on x The derivative of f at xo is the slope of the tangent line to the graph of f at (xo, f(ro)) as shown in Figure 1.2 Copyright 2010 Cengage Learning. All Rights May no be copied, scanned, or duplicated, in whole or in part Due to maternally aftec the overall leaning expenence. Cengage Learning
1.1 Review of Calculus 3 Definition 1.2 Let f be a function defined on a set X of real numbers and x0 ∈ X. Then f is continuous at x0 if lim x→x0 f (x) = f (x0). The function f is continuous on the set X if it is continuous at each number in X. The set of all functions that are continuous on the set X is denoted C(X). When X is an interval of the real line, the parentheses in this notation are omitted. For example, the set of all functions continuous on the closed interval [a, b] is denoted C[a, b]. The symbol R denotes the set of all real numbers, which also has the interval notation (−∞,∞). So the set of all functions that are continuous at every real number is denoted by C(R) or by C(−∞,∞). The basic concepts of calculus and its applications were developed in the late 17th and early 18th centuries, but the mathematically precise concepts of limits and continuity were not described until the time of Augustin Louis Cauchy (1789–1857), Heinrich Eduard Heine (1821–1881), and Karl Weierstrass (1815 –1897) in the latter portion of the 19th century. The limit of a sequence of real or complex numbers is defined in a similar manner. Definition 1.3 Let{xn}∞ n=1 be an infinite sequence of real numbers. This sequence has the limit x (converges to x) if, for any ε > 0 there exists a positive integer N(ε) such that |xn − x| < ε, whenever n > N(ε). The notation lim n→∞ xn = x, or xn → x as n → ∞, means that the sequence {xn}∞ n=1 converges to x. Theorem 1.4 If f is a function defined on a set X of real numbers and x0 ∈ X, then the following statements are equivalent: a. f is continuous at x0; b. If {xn}∞ n=1 is any sequence in X converging to x0, then limn→∞ f (xn) = f (x0). The functions we will consider when discussing numerical methods will be assumed to be continuous because this is a minimal requirement for predictable behavior. Functions that are not continuous can skip over points of interest, which can cause difficulties when attempting to approximate a solution to a problem. Differentiability More sophisticated assumptions about a function generally lead to better approximation results. For example, a function with a smooth graph will normally behave more predictably than one with numerous jagged features. The smoothness condition relies on the concept of the derivative. Definition 1.5 Let f be a function defined in an open interval containing x0. The function f is differentiable at x0 if f (x0) = lim x→x0 f (x) − f (x0) x − x0 exists. The number f (x0) is called the derivative of f at x0. A function that has a derivative at each number in a set X is differentiable on X. The derivative of f at x0 is the slope of the tangent line to the graph of f at (x0, f (x0)), as shown in Figure 1.2. 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