[PDF] Numerical analysis SCHAUM - University of Halabja

View - Download Numerical analysis SCHAUM - University of Halabja

Previous PDF

Next PDF

THEORY AND PROBLEMS '

NUMERICAL

ANALYSIS

FRANCIS SCHEID, Ph.D.

Professor of Mathematics

Boston University

SCHAUM9S OUTLINE SERIES

McGRAW-HILL BOOK COMPANY

New York, St. Louis, Sun Francisco, Toronto, Sydney Copyright @ 1968 by McGraw-Hill, Inc. A11 Rights Reserved. Printed in the United States of America. No part of this publication may be reproduced, stored in a 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. ISBN

07-055197-9

The popularity and explosive growth of numerical analysis today are further evidence that applications are still the leading source of inspiration for mathematical creativity. Whenever new mathematical ideas are developed it is usually new applications which have pointed the way. The electronic computing machine is itself an illustration of this, a response to an overwhelming need for faster computation. And the appearance of such machines has made it possible to meet the demands of today's applications, in many cases, by developing more sophisticated numerical methods. This is the pedigree of modern numerical analysis. It is the numerical aspect of the broad field of applied analysis. It would be a mistake, however, to draw too fine a boundary between our subject and what is called pure or abstract analysis. The borderline is a fuzzy one, as borderlines usually are, and materials from both sides frequently infiltrate the other. In earlier days it was commonplace for mathematicians to be expert at both the pure and the applied. Both have long since developed to a size which makes full acquaintance with even one impossible, and reasonable competence at both an arduous objective. In spite of this the applied mathematician, including the numerical analyst, must try to keep aware of what is happening across the border. To this end it has been one of my objectives to provide occasional evidence of infiltration, at least in elementary ways. The treatment of Taylor series is one such example. The importance of these series in pure analysis is classical, but they are also valuable for computing functions, estimating error, and so on. Fourier series, orthogonal polynomials and perturbation series (just to mention a few) are other topics which are valuable on both sides of the borderline. The proof of the classical existence theorem of differential equations by "applied" methods is a beautiful illustration of how applications lead eventually to abstract theory. So, although our principal interest here is numerical mathematics, a number of topics usually relegated to other places will be presented briefly, because they are themselves useful in computation and, even more important, because they are a reminder of the fuzzy borderline and of the value of in- filtration in both directions. The numerical analyst is, after all, an analyst. This book has been designed to serve as text for any introductory course in numerical analysis. There is adequate material for a year course at senior or beginning graduate level. By omitting the more demanding theoretical parts it may also be used for a one term course at a more elementary level. The extensive collection of solved problems also permits use as a supplement to any standard textbook in the subject.

It will even be useful as

independent reading for students of science or engineering with an interest in numerical methods. Each chapter begins with a capsule summary of results to be obtained and methods to be illustrated. Ordinarily it is not expected that this summary will be completely self- explanatory. It should be viewed as a table of contents for that chapter. The details are fully presented among the solved problems and an abundant supply of supplementary problems is offered to test one's understanding. Answers to most of the supplementary problems have been provided. An often used procedure for evaluating a numerical method involves applying it to a problem for which the exact solution is known. This problem then serves as a "test case". Many such examples have been included. When they occur as supplementary problems it is the exact answer which is given. Needless to say, the nu- merical method should not be expected to produce this exact answer, which is given so that the computer may check the accuracy of his own result to whatever number of digits he desires. For certain problems no answer has been supplied. These offer a touch of realism, since in practice the computer must not only find an answer but decide for himself whether or not it is correct. I take this opportunity to express my gratitude to Dr. Donald Chand, who expertly programmed all the machine computations, to Dr. Martin Silverstein, who carefully read the manuscript and suggested numerous improvements, and to my publisher and his team. I have no doubt that, in spite of strenuous efforts, there remain errors of one sort or another. Numerical analysts are among the world's most error-conscious people, no doubt because they make so many. I will be pleased and grateful to hear from any reader who discovers errors. There is no reward except the exhilaration of continuing the search for the all-too-elusive "truth".

CONTENTS

Chapter Page

WHAT IS NUMERICAL ANALYSIS? .................................... 1 THE COLLOCATION POLYNOMIAL ..................................... 10 FINITE DIFFERENCES ................................................. 15 FACTORIAL POLYNOMIALS ............................................ 22 SUMMATION ............................................................ 30 THE NEWTON FORMULA .............................................. 34 OPERATORS AND COLLOCATION POLYNOMIALS ...................... 38 UNEQUALLY-SPACED ARGUMENTS ................................... 53 DIVIDED DIFFERENCES ............................................... 58 OSCULATING POLYNOMIALS ........................................ 65 THE TAYLOR POLYNOMIAL ............................................ 70 INTERPOLATION AND PREDICTION ................................... 79 NUMERICAL DIFFERENTIATION ...................................... 97 NUMERICAL INTEGRATION ........................................ 107 GAUSSIAN INTEGRATION .............................................. 125 SINGULAR INTEGRALS ................................................ 150 SUMS AND SERIES .................................................... 156 ............................................. DIFFERENCE EQUATIONS 177 DIFFERENTIAL EQUATIONS .......................................... 193 DIFFERENTIAL PROBLEMS OF HIGHER ORDER ..................... 223 LEAST-SQUARES POLYNOMIAL APPROXIMATION .................... 235 ............................ MIN-MAX POLYNOMIAL APPROXIMATION 267 ......................... APPROXIMATION BY RATIONAL FUNCTIONS 283 .................................... TRIGONOMETRIC APPROXIMATION 293 NONLINEAR ALGEBRA ................................................ 310 ...................................................... LINEAR SYSTEMS 334 LINEAR PROGRAMMING ............................................... 361 .......................................... OVERDETERMINED SYSTEMS 375 ........................................ BOUNDARY VALUE PROBLEMS 382 .............................................. MONTE CARL0 METHODS 401 .......................... ANSWERS TO SUPPLEMENTARY PROBLEMS 407 ................................................................... INDEX 419

Chapter 1

What Is Numerical Analysis?

THE ALGORITHM

Our subject has been described in many ways, and the elementary examples which make up this first chapter bring out the essential parts of most descriptions. They are intended as a preview of what lies ahead, providing a perspective from which the course of action may be best understood. To summarize these examples in advance, they suggest that numerical analysis involves the development and evaluation of methods for computing required numerical results from given numerical data. This makes it a part of the modern subject of information processing. The given data are the input information, the required results are the output information, and the method of computation is known as the algorithm. These essential ingredients of a numerical analysis problem may be summarized in a flow- chart, Fig. 1-1.

Fig. 1-1

THE PRESENCE OF ERROR

Output

Information Input

Information

The description just chosen is definitely applications oriented. It focuses our efforts on the search for algorithms. Frequently we will find that several algorithms are available for producing the required output information, and we must choose between them. There are various reasons for preferring one algorithm over another, but two obvious criteria are speed and accuracy. Speed is clearly an advantage. Other things being equal the faster method surely gets the nod. The issue of accuracy will consume much of our energy, and it exposes a second major feature of our subject, the presence of error. Rarely will input information be exact, since it ordinarily comes from measurement devices of some sort. And usually the computing algorithm introduces further error. The output informa- tion therefore contains error from both these sources, as suggested in a second flow-chart (Fig.

1-2). An algorithm which minimizes error growth clearly rates serious consideration.

Fig. 1-2

- w

SUPPORTING THEORY

Though our view of numerical analysis will be applications oriented, we will naturally be concerned with supporting theory. Often the theory to which we are led has intrinsic interest; it is attractive mathematics. Primarily however, theory is important to us because it contributes to the search for better algorithms. P The

Algorithm

Output

Errors

w r Input

Errors

Algorithm

Errors

WHAT IS NUMERICAL ANALYSIS ? [CHAP. 1

Solved Problems

1.1. Identify the input information, the algorithm and the output information in t,he prob-

lem of computing the product

45 x 17.

Needless to say this is an elementary problem, but it will serve as a painless first illustration.

3 input information

the 315 algorithm 45

765+output information

The input information consists of the numbers

45 and 17. The algorithm is the familiar process of

multiplication.

The output information is the number

765. If we assume the input exact, then

since no error is introduced by the algorithm the output is also exact. No error occurs anywhere in the problem.

1.2. Compute the product of Problem 1.1 by the "Russian peasant algorithm".

This method involves continually doubling one factor while halving the other, noting where the halving leaves a remainder.

45 R 17 input information

22 34
11 R 68 5 R 136 algorithm 2 272 1 R 544 765

4- output information

The final step is the addition of those multiples of

17 on lines where remainders do occur. The

output information is the same

765 in Problem 1.1. Why this method "works" can be discovered

by patient but elementary investigations. The point of this problem is that more than one algorithm is available for computing a product. Two lengths X and Y are measured to be approximately X - 3.32 and Y - 5.39, the symbol -- representing approximate equality. Compute approximations to X + Y, X + (.l)Y and X + (.01)Y by "three digit addition". This is again an elementary problem but it illustrates the presence of error in computational mathematics.

3.32 3.32 3.32

5.39 0.54 0.05

X + Y - 8.71 X + (.l)Y - 3.86 X + (.Ol)Y - 3.37

Here all numbers have been kept at a uniform length of three digits, by rounding off whenever necessary and by supplying leading zeros whenever necessary. This is in the spirit of modern auto- matic machine computation. Machines store and operate with numbers of a uniform length as we have done here. Usually machine length is six or more digits, not merely three, but for simple illustrations we shall often limit our numbers to three digits. The action in this problem is sum- marized in Fig. 1-3. Input Information The Algorithm Output Information

Three digit

X + (.l)Y - 3.86

x + (.Ol)Y - 3.37

Fig. 1-3

CHAP. 11 WHAT IS NUMERICAL ANALYSIS ?

1.4. Point out the sources of error in Problem 1.3 and note their size.

Assume the input information, 3.32 and 5.39, correct to the three digits offered. With X and Y still representing the (unknown) exact values, the errors in input information are and neither error exceeds .005.

There are also algorithm errors. In approximating

(.l)Y the algo- rithm makes a "roundoff" from .539 to .54, while in approximating (.01)Y it makes a roundoff from .0539 to .05, both errors being on the order of .001.

1.5. Estimate the errors in output information due to the error sources indicated in

Problem

1.4. Take X + Y first. From the equations in Problem 1.4 we easily find (X + Y) - 8.71 = (X - 3.32) + (Y - 6.39) = El + Ex so that the difference between the (unknown) exact X + Y and its computed approximation 8.71 is

IX + Y - 8.71/ 5 ,005 + .005

or .Ol. The second decimal place in our 8.71 is therefore open to slight suspicion. Notice that algo- rithm errors play no part in this "straight addition" problem.

But now consider X 4- (.l)Y. Since

(.l)Y = (.1)(E2+ 6.39) = (.1)E2 + .539 we easily find X + (.l)Y - 3.86 = El + 3.32 + (.1)E2 + .539 - 3.86 = El + (.1)E2 - .001 so that the difference between the (unknown) exact

X + (.l)Y and its computed approximation

3.86 is

IX + (.l)Y - 3.861 5 ]Ell + ((.1)E21 + 1-.0011 5 .005 + .0005 + .001 and does not exceed .0065.

Here the

.005 is an input error, the .0005 is an input error which has been multiplied by .l as the algorithm proceeds, and the .001 is an algorithm error (roundoff). In the same way we find X + (.01)Y - 3.37 = El + 3.32 + (.01)E2 + .0539 - 3.37 = El + (.01)E2 + .0039 so that the error in our computed 3.37 is IX + (.01)Y - 3.371 5 .005 + .00005 + .0039 and does not exceed .009. In all our output information the second decimal place appears to be open to suspicion. This problem shows how even in a simple computation the question of error size is not easy to answer. Here we have estimates of the maximum error possible. In Problem 1.6 we dis- cover that these estimates are too pessimistic.

1.6. Suppose a new theoretical discovery shows the X and Y of Problem 1.3 to be square

roots of

11 and 29. Instead of having to measure these two lengths, they can now

be computed. (See a later chapter for methods of computing square roots.) Correct to six digits, X -- 3.31662 and Y - 5.38616. Recompute the required results of

Problem

1.3 and compare the actual errors in output information of that problem with

the maximum possible errors computed in Problem 1.5.

Using "six digit arithmetic" one easily finds

X + Y - 8.70278, X + (.l)Y - 3.85524, X + (.Ol)Y - 3.37048 A maximum error analysis as made in Problem 1.5 would now show these results to be correct to at least four decimal places. The actual errors in our Problem 1.3 computations can now be more accurately estimated.

Actual error

Maximum error

WHAT IS NUMERICAL ANALYSIS ?

[CHAP. 1 The error in X + (.Ol)Y is far less than the maximum. Realistic error estimation is one of the most difficult tasks of numerical analysis. Frequently, as in this case, a problem for which the exact solution is known is used to test the behavior of error in an algorithm. Find the smaller root of the quadratic equation x2 - 20x + 1 = 0 using three digit arithmetic. The two roots are, according to a well-known theorem of algebra, 10 * 69. The smaller in- volves the minus sign. Limited to three digit arithmetic, our computation runs 10 - fi - 10.0 - 09.9 = 00.1 and serves as an excellent illustration of what happens when nearly equal numbers are subtracted. Though the numbers themselves may have three digit accuracy, some (perhaps all) of these digits will be lost in the subtraction. The main ingredients of this problem are summarized in Fig. 1-4.

See Problem 1.8 for

a better algorithm. Fig. 1-4

Compute 10 - fi

x2 - 20x + 1 = 0 by three digit arithmetic

Input Information

1.8. Noting the theoretical result 10 - fl = 1/(10 + m), use the expression on the

right to compute the root required in Problem 1.7. Again limiting ourselves to three digit arithemetic, 10 + 69 = 10.0 + 09.9 = 19.9 after which 1.00/19.9 = .0503 Output Information Most modern computing machines position leading zeros in the results of multiplications and divisions, retaining at the same time the number of digits (in this case three) which represents machine capacity. In other words, for our division above we may consider the output a three digit number, ignoring the leading zero. Note, however, that in the addition of 10.0 to 09.9 the leading zero is one of the three digits in action. The same was true in Problem 1.3 and this is typical of addition operations in modern machines. Fig.

1-5 now summarizes the ingredients of this

computation. The Algorithm

Compute

1/(10 x2 - 20s + 1 = 0 by three digit arithmetic Fig. 1-5 Notice that supporting theory has offered us an alternative algorithm for the computation of this root. Error analysis will be omitted but our new result is correct to three decimal places, making it far superior to that of Problem 1.7. The new algorithm introduces much smaller algorithm errors.

1.9. Compute the sum fi + V/Z + - . + m.

Suppose we first obtain all square roots to two decimal places. Later an algorithm for com- puting roots will be presented, but for the present we may suppose them extracted from square root tables. The first few will be 1.00, 1.41, 1.73, 2.00, etc. The sum of these hundred numbers comes to 671.27. Clearly such a sum requires at least "five digit arithmetic" for its computation. Since one hundred roundoffs have been made during the course of the algorithm the accuracy of our result is uncertain, but see the next few problems. The computation is summarized in Fig. 1-6 below.

CHAP. 11 WHAT IS NUMERICAL ANALYSIS ?

5

Obtain all square roots

1, 2, . . . , 100 to two decimal places. Compute their sum by Sum - 671.27

five digit arithmetic. Fig. 1-6

1.10. Suppose the numbers XI, x2, . . ., XN are approximations to XI,X~, . . .,XN and that

in each case the maximum possible error is

E. Prove that the maximum possible

error in the sum

XI + xz + . . + XN is NE.

This problem presents another example of supporting theory. Since xi-E S Xi 5 xi+E it follows by addition that

Exi-NE S EXi 5 Exi+ NE

so that -NE 5 EXi - Exi S NE, which is what was to be proved.

1.11. In Problem 1.9 one hundred numbers, each correct to two decimal places, were sum-

med. What is the maximum possible error in their sum? The error in each number is at most .005. Applying Problem 1.10 with E = .005 and N = 100, we find NE = .5. This suggests that the sum may not be correct to even one decimal place. (See also, however, Problem 1.12.)

1.12. As further supporting theory a statistical argument, not reproduced here, suggests

that when N numbers are summed the "probable error" is fl~, where E is again the maximum possible error of the

N numbers involved. Apply this formula to find

the "probable error" of the sum computed in Problem 1.9. With N = 100 and E = .005, probable error = fi~ = 10(.005) = .05. This is more opti- mistic than the maximum error estimate of .5 obtained in Problem 1.11. But which estimate is nearer to the truth?

1.13. For the sum in Problem 1.9, a new computation, in which all square roots are first

found to five decimal places rather than only two, produces the sum 671.36385. Clearly this requires "eight digit arithmetic". Show by using Problem 1.10 that the error in this sum is at most .0005, making it correct to at least three decimal places. Then compare the actual error in our result of Problem 1.9 with the maximum and probable error estimates of Problems

1.11 and 1.12.

With N = 100 and E = .000005 we have NE = .0005, as suggested. The various errors are, therefore, actual error - 671.36 - 671.27 = .09 maximum possible error = .50 probable error = .05 One of our estimates was too pessimistic, the other too optimistic. In this problem the availability of a machine capable of "eight digit arithmetic" has allowed us to check the accuracy of our simpler computation of Problem 1.9 and to study error development. Not always, however, can a bigger machine be called upon, and the question of error size in output information is often im- possible to answer with satisfaction.

1.14. Given

compute lim

A, correct to three digits.

WHAT IS NUMERICAL ANALYSIS ? [CHAP. 1

The following theorem of elementary analysis is an often used piece of supporting theory. "An infinite sequence

A1,A,,A3,

. . . in which the A, alternately increase and decrease, and for which the differences /A, - An+l/ decrease monotonically to zero, is a convergent sequence. More- over, \(limA,) - A,I 5 \A, - For the present sequence this implies convergence, the existence of lirn A, and the fact that the difference between A, and lirn A, cannot exceed lln. Three digit accuracy allows an error of at most .0005 and we can achieve this accuracy by making lln 5 .0005 and n 2 2000. This means that Azooo will be an approximation of sufficient accuracy. But how does one compute this number? Suppose an eight digit computing machine is available. The various reciprocals may then be expressed as eight digit decimals, most of them requiring roundoffs. Summing 2000 such numbers could produce a further error of which seems negligible. So we allow our eight digit machine to compute this lengthy sum. The result, after rounding off to three digits, is: computed sumquotesdbs_dbs12.pdfusesText_18

[PDF] schedule 1 2018

[PDF] schedule 1 instructions 2019

[PDF] schedule 2

[PDF] schedule a

[PDF] schedule c instructions

[PDF] schedule c worksheet

[PDF] schedule c 1

[PDF] schedule c ez

[PDF] schedule se

[PDF] scheduling algorithms

[PDF] scheduling methods in os

[PDF] scheduling pdf

[PDF] schein's model of organizational culture pdf

[PDF] schéma appareil génital masculin de face

[PDF] schéma appareil reproducteur féminin