Conte, de Boor - Elementary Numerical Analysis. An Algorithmic Approach (523140), страница 6
Текст из файла (страница 6)
Rather, they should be questioned freely ifsubsequent investigations throw any doubt upon their correctness.The student should appreciate this as another example of the basicdifference between numerical analysis and analysis. Analysis became aprecise discipline when it left the restrictions of practical calculations todeal entirely with problems posed in terms of an abstract model of thenumber system, called the real numbers. This abstract model is designed tomake a precise and useful definition of limit possible, which opens the wayto the abstract or symbolic solution of an impressive array of practicalproblems, once these problems are translated into the terms of the model.This still leaves the task of translating the abstract or symbolic solutionsback into practical solutions.
Numerical analysis assumes this task, andwith it the limitations of practical calculations from which analysismanaged to escape so elegantly. Numerical answers are therefore usuallytentative and, at best, known to be accurate only to within certain bounds.Numerical analysis is therefore not merely concerned with the construction of numerical methods. Rather, a large portion of numericalanalysis consists in the derivation of useful error bounds, or error estimates,for the numerical answers produced by a numerical algorithm. Throughoutthis book, the student will meet this preoccupation with error bounds sotypical of numerical analysis.1.7 SOME MATHEMATICAL PRELIMINARIES 25EXERCISES1.6-1 The number ln 2 may be calculated from the seriesIt is known from analysis that this series converges and that the magnitude of the error in anypartial sum is less than the magnitude of the first neglected term.
Estimate the number ofterms that would be required to calculate ln 2 to 10 decimal places.1.6-2 For h near zero it is possible to writeandFind the values ofandfor which these equalities hold.1.6-3 Try to calculate, on a computer, the limit of the sequenceTheoretically, what isand what is the order of convergence of the sequence?1.7 SOME MATHEMATICAL PRELIMINARIESIt is assumed that the student is familiar with the topics normally coveredin the undergraduate analytic geometry and calculus sequence. Theseinclude elementary notions of real and complex number systems; continuity; the concept of limits, sequences, and series; differentiation and integration.
For Chap. 4, some knowledge of determinants is assumed. ForChaps. 8 and 9, some familiarity with the solution of ordinary differentialequations is also assumed, although these chapters may be omitted.In particular, we shall make frequent use of the following theorems.Theorem 1.1: Intermediate-value theorem for continuous functions Letf(x) be a continuous function on the intervalfor some number a and somethenThis theorem is often used in the following form:Theorem 1.2 Let f(x) be a continuous function on [a,b], let x1, . . .
, xnbe points in [a,b], and let g1, . . . , gn, be real numbers all of one sign.Then26NUMBER SYSTEMS AND ERRORSTO indicate the proof, assume without loss of generality that gi > 0,thenis a number between the two valuesandof the continuous functionand the conclusion followsfrom Theorem 1.1.One proves analogously the corresponding statement for infinite sumsor integrals:HenceTheorem 1.3: Mean-value theorem for integrals Let g(x) be a nonnegative or nonpositive integrable function on [a,b]. If f(x) is continuouson [a,b], then(1.28)Warning The assumption that g(x) is of one sign is essential in Theorem1.3, as the simple exampleshows.Theorem 1.4 Let f(x) be a continuous function on the closed andbounded interval [a,b]. Then f(x) “assumes its maximum and minimum values on [a,b]”; i.e., there exist pointssuchthatTheorem 1.5: Rolle’s theorem Let f(x) be continuous on the (closedand finite) interval [a,b] and differentiable on (a,b).
If f(a) = f(b) =0, thenThe proof makes essential use of Theorem 1.4. For by Theorem 1.4,there are pointssuch that, for allIf now neither _ nor is in (a,b), thenand everywill do. Otherwise, eitheroris in (a,b), say,But thensincebeing the biggest value achieved by f(x) on [a,b].An immediate consequence of Rolle’s theorem is the following theorem.Theorem 1.6: Mean-value theorem for derivatives If f(x) is continuouson the (closed and finite) interval [a,b] and differentiable on (a, b),1.7 SOME MATHEMATICAL PRELIMINARIES 27then(1.29)One gets Theorem 1.6 from Theorem 1.5 by considering in Theorem1.5 the functioninstead of f(x).
Clearly, F(x) vanishes both at a and at b.It follows directly from Theorem 1.6 that if f(x) is continuous on [a,b]and differentiable on (a,b), and c is some point in [a,b], then for all(1.30)The fundamental theorem of calculus provides the more precise statement:If f(x) is continuously differentiable, then for all(1.31)from which (1.30) follows by the mean-value theorem for integrals (1.28),since f '(x) is continuous. More generally, one has the following theorem.Theorem 1.7: Taylor’s formula with (integral) remainder If f(x) hasn + 1 continuous derivatives on [a,b] and c is some point in [a,b],then for all(1 .
32)where(1.33)One gets (1.32) from (1.31) by considering the functioninstead of f(x). For,But since F(c) = f(c), this giveshence by (1.31),28NUMBER SYSTEMS AND ERRORSwhich is (1.32), after the substitution of x for c and of c for x.Actually, f (n+1)(x) need not be continuous for (1.32) to hold. However,if in (1.32), f(n+1)(x) is continuous, one gets, using Theorem 1.3, the morefamiliar but less useful form for the remainder:(1.34)By setting h = x - c, (1.32) and (1.34) take the form(1.35)Example The function f(x) = eX has the Taylor expansionfor some between 0 and x(1.36)about c - 0.
The expansion of f(x) = ln x = log, x about c = 1 iswhere 0 < x < 2, andis between 1 and x.A similar formula holds for functions of several variables. One obtainsthis formula from Theorem 1.7 with the aid ofTheorem 1.8: Chain rule If the function f(x,y, . . . , z) has continuousfirst partial derivatives with respect to each of its variables, andx = x(t), y = y(t), . . . , z = z(t) are continuously differentiable functions of t, then g(t) = f(x(t), y(t), . . . , z(t)) is also continuously differentiable, andFrom this theorem, one obtains an expression for f(x, y, .
. . , z) interms of the value and the partial derivatives at (a, b, . . . , c) by introducing the functionand then evaluating its Taylor series expansion around t = 0 at t = 1. Forexample, this gives1.7SOME MATHEMATICAL PRELIMINARIES 29Theorem 1.9 If f(x,y) has continuous first and second partial derivatives in a neighborhood D of the point (a,b) in the (x,y) plane, then(1.37)for all (x,y) in D, wherefor somedepending on (x,y), and the subscripts on fdenote partial differentiation.For example, the expansion of exsin yabout (a,b) = (0, 0) is(1.38)Finally, in the discussion of eigenvalues of matrices and elsewhere, weneed the following theorem.Theorem 1.10: Fundamental theorem of algebra If p(x) is a polynomialof degree n > 1, that is,with a,, .
. . , a,, real or complex numbers andleast one zero; i.e., there exists a complex numberthen p(x) has atsuch thatThis rather deep theorem should not be confused with the straightforward statement, “A polynomial of degree n has at most n zeros,counting multiplicity,” which we prove in Chap. 2 and use, for example, inthe discussion of polynomial interpolation.EXERCISES1.7-1 In the mean-value theorem for integrals, Theorem 1.3, let[0,1]. Find the pointspecified by the theorem and verify that this point lies in the interval(0,1).1.7-2 In the mean-value theorem for derivatives, Theorem 1.6, letFind the pointspecified by the theorem and verify that this point lies in the interval (a,b).1.7-3 In the expansion (1.36) for eX, find n so that the resulting power sum will yield anapproximation correct to five significant digits for all x on [0,1].30NUMBER SYSTEMS AND ERRORS1.7-4 Use Taylor’s formula (1.32) to find a power series expansion aboutFind an expression for the remainder, and from this estimate the number of terms that wouldbe needed to guarantee six-significant-digit accuracy forfor all x on the interval[-1,1].1.7-5 Find the remainder R2(x,y) in the example (1.38) and determine its maximum value inthe region D defined by1.7-6 Prove that the remainder term in (1.35) can also be written1.7-7 Illustrate the statement in Exercise 1.7-6 by calculating, forfor various values of h, for example, forwithand comparing R,(h)1.7-8 Prove Theorem 1.9 from Theorems 1.7 and 1.8.1.7-9 Prove Euler’s formulanby comparing the power series for e , evaluated atthe power series forand i times the one forwith the sum ofPreviousCHAPTERTWOINTERPOLATION BY POLYNOMIALSPolynomials are used as the basic means of approximation in nearly allareas of numerical analysis.
They are used in the solution of equations andin the approximation of functions, of integrals and derivatives, of solutionsof integral and differential equations, etc. Polynomials owe this popularityto their simple structure, which makes it easy to construct effectiveapproximations and then make use of them.For this reason, the representation and evaluation of polynomials is abasic topic in numerical analysis. We discuss this topic in the presentchapter in the context of polynomial interpolation, the simplest andcertainly the most widely used technique for obtaining polynomial approximations.
More advanced methods for getting good approximations bypolynomials and other approximating functions are given in Chap. 6. Butit will be shown there that even best polynomial approximation does notgive appreciably better results than an appropriate scheme of polynomialinterpolation.Divided differences serve as the basis of our treatment of the interpolating polynomial. This makes it possible to deal with osculatory (orHermite) interpolation as a special limiting case of polynomial interpolation at distinct points.2.1 POLYNOMIAL FORMSIn this section, we point out that the customary way to describe apolynomial may not always be the best way in calculations, and we31HomeNext32INTERPOLATION BY POLYNOMIALSpropose alternatives, in particular the Newton form.
We also show how toevaluate a polynomial given in Newton form. Finally, in preparation forpolynomial interpolation, we discuss how to count the zeros of a polynomial.A polynomial p(x) of degree < n is, by definition, a function of theform(2.1)with certain coefficients a0, a1, . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
