Conte, de Boor - Elementary Numerical Analysis. An Algorithmic Approach (523140), страница 13
Текст из файла (страница 13)
. , xn, distinct or not, in case f(x) has enough derivatives.Further, if f(x) is sufficiently often differentiable, then g n (x) is differentiable. For by the definition of derivatives,if this limit exists. On the other hand,*2.7CONTINUITY OF DMDED DIFFERENCES AND OSCULATORY INTERPOLATION67by Theorem 2.5. Hence(2.38)Finally, it explains our definition of osculatory interpolation as repeated interpolation. For it shows that the interpolating polynomial atpoints x0, . . .
, xn converges to the interpolating polynomial at pointsall i. Thus, k-fold interpolation at a point is they0, . . . yn aslimiting case as we let k distinct interpolation points coalesce. The studentis familiar with this phenomenon in the case n = 1 of linear interpolation.In this case, the straight line p1(x) = f(x0) + f[x0, x1](x - x0) is a secantto (the graph of) f(x) which goes over into the tangent(x - y)f’(y) as both x0 and x1 approach the pointy, andagrees withf(x) in value and slope at x = y.Example 2.9 With f(x) = 1n x, calculate f(l.5) by cubic interpolation, using f(1) = 0,f(2) = 0.693147, f’(1) = 1, f’(2) = 0.5.In this case, the four interpolation points are y 0 = y 1 = 1, y 2 = y 3 = 2. WecalculateThe complete divided-difference table is written as follows:With thisp 3 (x) = 0.
+ (1.)(x - 1) + (-0.306853)(x - 1)2 + (0.113706)(x - l)2(x - 2)is the cubic polynomial which agrees with 1n x in value and slope at the two points x = 1and x = 2. The osculatory character of the approximation of 1n x by p3(x) is evidentfrom Fig. 2.7. Using Algorithm 2.1 to evaluate p3(x) at 1.5, we getWith e3(x) - f(x) - p3(X) the error, we get from (2.37) and Theorem 2.5(i) the estimate68INTERPOLATION BY POLYNOMIALSFigure 2.7 Osculatory interpolation.Since 1n 1.5 = 0.405465, the error is actually only 0.00361.
This shows once again thatthe uncertainty about the location ofmakes error estimates based on (2.18) ratherconservative-to put it nicely.We conclude this section with a FORTRAN program which calculatesthe coefficients for the Newton form of pn(x) and then evaluates pn(x) at agiven set of equally spaced points.C CONSTRUCTION OF THE NEWTON FORM FOR THE POLYNOMIAL OF DEGREEC .LE.
N , WHICH AGREES WITH F(X) AT Y(I), I=l,...,NPl.C SOME OR ALL OF THE INTERPOLATION POINTS MAY COINCIDE, SUBJECTC ONLY TO THE FOLLOWING RESTRICTIONS.C (1) IF Y(I) = Y(I+K), THEN Y(I) = Y(I+1) = . . . = Y(I+K) .I = 1 , THENC (2) IF ALSO Y(I-1) .NE. Y(I) , OR IFCF(I+J) = VALUE OF J-TH DERIVATIVE OF F(X) AT X = Y(J),J=0 ,..., K.CCINTEGER I,J,K,N,NPOINT,NP1REALDX,DY,F(30),FLAST,PNOFX,REALK,X,Y(30)READ500,NP1,(Y(I),F(I),I=1,NP1)500 FORMAT(I2/(2Fl0.3))CONSTRUCT DIVIDED DIFFERENCESCN = NP1 - 1DO 10 K=l,NREALK = KFLAST = F(1)DO 9 I=l,NP1-KDY = Y(I+K) - Y(I)IF (DY .EQ.
0.) THENF(I) = F(I+1)/REALKELSEF(I) = (F(I+1) - FLAST)/DYFLAST = F(I+1)END IF9CONTINUE*2.7CONTINUITY OF DIVIDED DIFFERENCES AND OSCULATORY INTERPOLATION69F(NP1-K+1) = FLAST10 CONTINUECCALCULATE PN(X) FOR VARIOUS VALUES OF X.READ 501,NPOINT,X,DX501 FORMAT(I3/2Fl0.3)DO 30 J=l,NPOINTPNOFX = F(1)DO 29 I=2,NP1PNOFX = F(I) + (X - Y(I))*PNOFX29CONTINUEPRINT 629,J,X,PNOFX629FORMAT(Il0,2E20.7)X = X + DX30 CONTINUESTOPENDThe calculation of divided differences corresponds to Algorithm 2.3 ifall interpolation points are distinct. If some interpolation points coincide,the input must contain values of derivatives of the interpolant.
Specifically,the input is assumed to consist of the array of interpolation points Y(I),I = 1,. . . , NP1 = n + 1, together with an array of numbers F(I), I =1, . . . , NP1. For simplicity of programming, the sequence of interpolationpoints is assumed to satisfy the restriction thati.e., all repeated interpolation points appear together. With this restriction,it is further assumed that, for each I,Thus, with f(x) = l/x, n = 6, the following input would be correct, in thesense that it would produce the polynomial of degree < 6, which interpolates f(x) = l/x at the given Y(I), I = 1, .
. . , 7.The student is encouraged to take an example like this and tracethrough the calculations in the FORTRAN program. The following flowchart describing the calculations of the divided differences might help inthis endeavor.70INTERPOLATION BY POLYNOMIALSEXERCISES2.7-1 For f(x) = ex calculate f(0.5), using quadratic interpolation, given that f(0) = 1, f’(0) =1, f(1) = 2.7183. Compare with the correctly rounded result f(0.5) = 1.6487.2.7-3 For f(x) = sinh x we are given thatForm a divided-difference table and calculate f(0.5) using cubic interpolation.
Compare theresult with sinh 0.5 = 0.5211.2.7-3 A function f(x) has a double zero at z1 and a triple zero at z2. Determine the form ofthe polynomial of degree < 5 which interpolates f(x) twice at z1, three times at z2, and onceat some point z3.2.7-4 Find the coefficients a0, al, a2, a3 for the cubic polynomial p3(x) = a0 + a1(x - y) +a 2 (x - y) 2 + a 3 (x - y) 3 , so that*2.7CONTINUITY OF DMDED DIFFERENCES AND OSCULATORY INTERPOLATION712.7-5 Get a simple expression for p 3 [(y + z ) / 2 ] in terms of the given numberswhere p3(x) is the polynomial determined in Exercise 2.7-4.2.7-6 Let f(x) and g(x) be smooth functions. Prove that f(x) agrees with g(x) k -fold at thepoint x = c if and only iffor x near c.2.7-7 Let g(x) = f[x0, . .
. , xk, x]. Prove that(use induction).2.7-8 Use Exercise 2.7-7 to prove that if g(x) = f[x0, . . . , xk, x], then2.7-9 Let f(x) - g(x)h(x). Prove that(use induction; else identify the right side as the leading coefficient of a polynomial of degree< k which interpolates g(x)h(x) at x0, . . .
, xk). What well known calculus formula do youobtain from this in case x0 = . . . = xk ?Previous HomeCHAPTERTHREETHE SOLUTION OF NONLINEAR EQUATIONSOne of the most frequently occurring problems in scientific work is to findthe roots of equations of the form(3.1)i.e., zeros of the function f(x). The function f(x) may be given explicitly,as, for example, a polynomial in x or as a transcendental function.Frequently, however, f(x) may be known only implicitly; i.e., a rule forevaluating f(x) for any argument may be known, but its explicit form isunknown. Thus f(x) may represent the value which the solution of adifferential equation assumes at a specified point, while x may represent aninitial condition of the differential equation.
In rare cases it may bepossible to obtain the exact roots of (3.1), an illustration of this being afactorable polynomial. In general, however, we can hope to obtain onlyapproximate solutions, relying on some computational technique to produce the approximation. Depending on the context, “approximate solution” may then mean either a point x*, for which (3.1) is “approximatelysatisfied,” i.e., for which |f(x*)| is “small,” or a point x* which is “closeto” a solution of (3.1).
Unfortunately the concept of an “approximatesolution” is rather fuzzy. An approximate solution obtained on a computerwill almost always be in error due to roundoff or instability or to theparticular arithmetic used. Indeed there may be many “approximate solutions” which are equally valid even though the required solution is unique.72NextTHE SOLUTION OF NONLINEAR EQUATIONS73To illustrate the uncertainties in root finding we exhibit below in Fig.
3.1 agraph of the functionThis function has of course the single zero x = 1. A FORTRAN programwas written to evaluate p6(x) in its expanded form. This program was usedto evaluate p 6 (x) at a large number of points x1 < x2 < · · · < xN nearx = 1 on a CDC 6500 computer. A Calcomp plotter was then used toproduce the piecewise straight-line graph presented in Fig. 3.1. From thegraph we see that p6(x) has many apparent zeros since it has many signchanges. These apparent zeros range from 0.994 to 1.006. Thus use of theexpanded form of p6(x) to estimate the zero at x = 1 leads to apparentlyacceptable estimates which are correct to only 2 decimal digits, eventhough the CDC 6500 works in 14-digit floating-point arithmetic.
Thereason for this behavior can be traced to round-off error and significantdigit cancellation in the FORTRAN calculation of P6 (x). This exampleillustrates some of the dangers in root finding.Figure 3.174THE SOLUTION OF NONLINEAR EQUATIONSIn the remainder of this chapter we shall consider various iterativemethods for finding approximations to simple roots of (3.1). Specialattention will be given to polynomial equations because of their importance in engineering applications.3.1 A SURVEY OF ITERATIVE METHODSIn this section, we introduce some elementary iterative methods for findinga solution of the equation(3-1)and illustrate their use by applying them to the simple polynomial equation(3.2)3for which f(x) = x - x - 1.For this example, one finds that(3.3)Hence, since f(x) is continuous, f(x) must vanish somewhere in the interval[1,2], by the intermediate-value theorem for continuous functions (see Sec.1.7). If f(x) were to vanish at two or more points in [1,2], then, by Rolle’stheorem (see Sec.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
