d1=2a2+d2x=0.4+(-006)(4)=0 d=a1+d1x=-0.4+(0.16)(4)=0.24 The numerical derivatives is P(4)=0.24(see Figure 1.7(b)) 0.005 i3=2+i4x=0.0666+(-0.0054)=0.046667 2=2+a=-02+060606010333 i1=a0+i2x=1.28+(-0.0133334=1.2266667 io=0+i1x=0+(1.22666(4)=4.9066667 Hence I(4)=4.90666667. Similarly, I(1)=1.14166667. Therefore, i P(r)d. I(4)-I(1)=3765( see figure1.8) (d)Use Algorithm 1.1(i)with .= 5.5 -0.02 b2=a2+b3x=0.2+(-0.02)(5.5)=0.09 b1=a1+b2x=-0.4+(0.09)(5.5)=0.095 bo=ao+b1x=1.28+(0.095)(5.5)=1.8025 The extrapolated value is P(5.5)=1.8025(see Figure 1.7(a)) Figure 1. 8 The approximating polynomial P(a) is integrated and its antiderivative is used to find the area under the curve for -1<a <4 (e) The methods of Chapter 3 can be used to find the coefficients. Assume that P(r)
d1 = 2a2 + d2x = 0.4 + (−0.06)(4) = 0.16 d0 = a1 + d1x = −0.4 + (0.16)(4) = 0.24 The numerical derivatives is P 0 (4) = 0.24(see Figure 1.7(b)). (c) i4 = a3 4 = −0.005 i3 = a2 3 + i4x = 0.06666667 + (−0.005)(4) = 0.04666667 i2 = a1 2 + i3x = −0.2 + (0.04666667)(4) = −0.01333333 i1 = a0 + i2x = 1.28 + (−0.01333333)(4) = 1.22666667 i0 = 0 + i1x = 0 + (1.22666667)(4) = 4.90666667. Hence I(4) = 4.90666667. Similarly, I(1) = 1.14166667. Therefore, R 4 1 P(x)dx = I(4) − I(1) = 3.765 (see Figure 1.8). (d) Use Algorithm 1.1(i) with x = 5.5. b3 = a3 = −0.02 b2 = a2 + b3x = 0.2 + (−0.02)(5.5) = 0.09 b1 = a1 + b2x = −0.4 + (0.09)(5.5) = 0.095 b0 = a0 + b1x = 1.28 + (0.095)(5.5) = 1.8025. The extrapolated value is P(5.5) = 1.8025 (see Figure 1.7(a)). 0 1 2 3 4 5 6 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2 Figure 1.8 y=P(x) Figure 1.8 The approximating polynomial P(x) is integrated and its antiderivative is used to find the area under the curve for −1 ≤ x ≤ 4. (e) The methods of Chapter 3 can be used to find the coefficients. Assume that P(x) = 18
A+Bx+Ca2+Dx then at each value c=1, 2, 3, and 5 we get a linear equation involving A.b. C. and D Atx=1:4+1B+1C+1D=1.06 Atx=2:A+2B+4C+8D=1.12 Atx=3:A+3B+9C+27D=1.34 (3.18 Atx=5:A+5B+25C+125D=1.78 The solution to(1.18)is A= 1.28, B=-04,C=0.2, and D=-02 This method for finding the coefficients is mathematically sound, but sometimes the matrix is difficult to solve accurately. In this chapter we design algorithms specifically for polynomials Let us return to the topic of using a polynomial to calculate approximations to a known function. In Section 1. 1 we saw that the fifth-degree Taylor polynomial for f(r)=In(1+.)is 3 5 If T(a) is used to approximate In(1 +.)on the interval [0, 1, then the error is 0 at .c=0 and is largest when a= 1(see Table 1. 4). In deed, the error between T(1) and the correct value In(1)is 13%. We seek a polynomial of degree 5 that will approximate In(1+a)better over the interval 0, 1. The polynomial P(a)in Example 1.5 is an interpolating polynomial and will approximate In(1+a)with an error no bigger than 0.00002385 over the interval [ 0, 1] Table 1. 4 Values of the Taylor Polynomial T()of Degree 5, and the Function In(1+a)and the Error In(1+a)-T(a)on 0, 1] Taylor polynomial Function Error n(1+x)-T(x) 0.00000000 0.00000000 0.00000000 0.2 0.18233067 0.182321560.000001 0.4 0.33698133 0.33647224 0.00050906 0.6 0.47515200 0.47000363 00514837 0.61380267 0.58778666 0.02601601 0.7833333 0.69314718 0.090186 Example 1.5. Consider the function f(a)=In(1+a) and the polynomial P(x)=0.02957026x5-0.12895295x4+0.28249626 0.48907554x2+0.99910735x based on the six nodes Tk=k/5 for k=0, 1, 2, 3, 4, and 5. The following are empirical descriptions of the approximation P(a)aIn(1 +r) Table 1. 5 Values of the Approximating Polynomial P()of Example 5 and the Function f(a)=In(1+r)and the Error E(r)on[-0.1,1.1 19
A + Bx + Cx2 + Dx3 ; then at each value x = 1, 2, 3, and 5 we get a linear equation involving A, b, C, and D. Atx = 1 : A + 1B + 1C + 1D = 1.06 Atx = 2 : A + 2B + 4C + 8D = 1.12 Atx = 3 : A + 3B + 9C + 27D = 1.34 Atx = 5 : A + 5B + 25C + 125D = 1.78 (3.18) The solution to (1.18) is A = 1.28, B = −0.4, C = 0.2, and D = −0.2. This method for finding the coefficients is mathematically sound, but sometimes the matrix is difficult to solve accurately. In this chapter we design algorithms specifically for polynomials. Let us return to the topic of using a polynomial to calculate approximations to a known function. In Section 1.1 we saw that the fifth-degree Taylor polynomial for f(x) = ln(1 + x) is T(x) = x − x 2 2 + x 3 3 − x 4 4 + x 5 5 . (3.19) If T(x) is used to approximate ln(1 + x) on the interval [0, 1], then the error is 0 at x = 0 and is largest when x = 1 (see Table 1.4). In deed, the error between T(1) and the correct value ln(1) is 13%. We seek a polynomial of degree 5 that will approximate ln(1 + x) better over the interval [0, 1]. The polynomial P(x) in Example 1.5 is an interpolating polynomial and will approximate ln(1 + x) with an error no bigger than 0.00002385 over the interval [0, 1]. Table 1.4 Values of the Taylor Polynomial T(x) of Degree 5, and the Function ln(1 + x) and the Error ln(1 + x) − T(x) on [0, 1] x Taylor polynomial T(x) Function ln(1 + x) Error ln(1 + x) − T(x) 0.0 0.00000000 0.00000000 0.00000000 0.2 0.18233067 0.18232156 0.00000911 0.4 0.33698133 0.33647224 0.00050906 0.6 0.47515200 0.47000363 0.00514837 0.8 0.61380267 0.58778666 0.02601601 1.0 0.78333333 0.69314718 0.09018615 Example 1.5. Consider the function f(x) = ln(1 + x) and the polynomial P(x) = 0.02957026x 5 − 0.12895295x 4 + 0.28249626x 3 −0.48907554x 2 + 0.99910735x based on the six nodes xk = k/5 for k = 0, 1, 2, 3, 4, and 5. The following are empirical descriptions of the approximation P(x) ≈ ln(1 + x). Table 1.5 Values of the Approximating Polynomial P(x) of Example 1.5 and the Function f(x) = ln(1 + x) and the Error E(x) on [−0.1, 1.1]. 19
Approximating Function, Error, E(r) 0. IX posynomial, P(a) f()=In(1+a) In(1+r)-P(r) 0.10509718 0.10536052 0.00026334 0.0 0.00000000 0.00000000 0.00000000 0.1 0.09528988 0.09531018 0.00002030 0.2 0.18232156 0.18232156 0.00000000 0.3 0.26327015 0.26236426 0.00000589 0.4 0.33647224 0.33647224 0.00000000 0.40546139 0.40546511 0.00000372 0.47000363 0.47000363 0.00000000 0.53063292 0.53062825 0.00000467 0.58778666 0.58778666 0.00000000 0.9 0.64184118 0.64185389 0.00001271 1.0 0.69314718 0.69314718 0.00000000 1.10.74206529 0.74193734 0.00012795 1. P(ak)=f(ak) at each node(see Table 1.5) 2. The maximum error on the interval [-0.1, 1.1 occurs at 2=-0.1 and eror≤0.00026334for-0.1≤x≤1.1( see figure1.10) Hence the graph of y= P(r)would appear identical to that of y= In(1+a)(see igure 1.9) The maximum error on the interval [0, 1] occurs at 3=0.06472456 and eror≤0.000035for0≤x≤1( see figure1.10) Remark. At a node Tk we have f(ck=P(ck). Hence e(ak=0 at a node. The graph of e()=f(a)-p(az) looks like a vibrating string, with the nodes being the abscissa where there is no displacement
x Approximating polynomial, P(x) Function, f(x) = ln(1 + x) Error, E(x) = ln(1 + x) − P(x) -0.1 0.10509718 0.10536052 0.00026334 0.0 0.00000000 0.00000000 0.00000000 0.1 0.09528988 0.09531018 0.00002030 0.2 0.18232156 0.18232156 0.00000000 0.3 0.26327015 0.26236426 0.00000589 0.4 0.33647224 0.33647224 0.00000000 0.5 0.40546139 0.40546511 0.00000372 0.6 0.47000363 0.47000363 0.00000000 0.7 0.53063292 0.53062825 0.00000467 0.8 0.58778666 0.58778666 0.00000000 0.9 0.64184118 0.64185389 0.00001271 1.0 0.69314718 0.69314718 0.00000000 1.1 0.74206529 0.74193734 0.00012795 0 0.2 0.4 0.6 0.8 1 1.2 1.4 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 Figure 1.8 y=ln(1+x) 1. P(xk) = f(xk) at each node (see Table 1.5). 2. The maximum error on the interval [−0.1, 1.1] occurs at x = −0.1 and |error| ≤ 0.00026334 for −0.1 ≤ x ≤ 1.1 (see Figure 1.10) Hence the graph of y = P(x) would appear identical to that of y = ln(1 + x) (see Figure 1.9). 3. The maximum error on the interval [0, 1] occurs at x = 0.06472456 and |error| ≤ 0.00002385 for 0 ≤ x ≤ 1 (see Figure 1.10). Remark. At a node xk we have f(xk) = P(xk). Hence E(xk) = 0 at a node. The graph of E(x) = f(x) − P(x) looks like a vibrating string, with the nodes being the abscissa where there is no displacement. 20
Algorithm 1.1(Polynomial Calculus). To evaluate the polynomial() its derivative P(ar), and its integral P()dx by performing synthetic division INPUT N Degree of P(a)h INPUT A(O), A(1),., A(N) Coefficients of P(a)) INPUT C I Constant of integration) INPUT X I Independent variable) (i)Algorithm to Evaluate P(r) pace-saving version B(N):=A(N) Poly: A(N) For K=N-1 DOWNTOO DO FOR K=N-1 DOWNTO O DO B(K);=A(K)+B(K+1)*X Poly: A(K)+poly X PRINT" The value P(a)is", B(O) PRINT” The value p(x)is”,Poly (ii) Algorithm to Evaluate P(a pace-saving version D(N-1):=N*A(N Deriv: =N*A(M FOR K=N-1 DOWNTO 1 DO FOR K=N-1 DOWNTO 1 DO D(K-1);=K*A(K)+D(K)*X Deriv: K* A(K)+Deriv*X PRINT"The value P()is", D(O) PRINT "The value P(a)is",Deriv (iii) Algorithm to Evaluate P Space-saving version I(N+1):=A(N)/(N+1) Integ: =A(N)/(N+1) FOR K=N DOWNTO 1 DO FOR K=N DOWNTO 1 DO I(K);=A(K-1)/K+I(K+1)*X Integ: = A(K-1)/K+Integ*X I(0):=C+I(1)*X Integ:=C+integ* X PRINT” The value I(x)is”,I(0) PRINT” The value l(x)is”, Integ 3.2.1 Exercises for Introduction to Interpolation 1. Consider P(a)=-002 x3+0.1.z2-02r+ 1.66, which passes through the four points(1,1.54),(2,1.5),(3,1.42),and(5,0.6) a) Find P(4) b) Find P(4) (c)Find the definite integral of P(a) taken over [ 1,4
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 −1 −0.5 0 0.5 1 1.5 2 2.5 x 10−5 Figure 12 The graph of the error y=E(x)=ln(1+x)−P(x). x y y=E(x) Algorithm 1.1 (Polynomial Calculus). To evaluate the polynomialP(x), its derivativeP 0 (x), and its integral R P(x)dx by performing synthetic division. INPUT N {Degree of P(x)} INPUT A(0), A(1), . . . , A(N) {Coefficients of P(x)} INPUT C {Constant of integration} INPUT X {Independent variable} (i) Algorithm to Evaluate P(x) B(N) := A(N) For K = N − 1 DOWNTO 0 DO B(K); = A(K) + B(K + 1) ∗ X PRINT ”The value P(x) is”, B(0) Space-saving version : Poly := A(N) FOR K = N − 1 DOWNTO 0 DO Poly := A(K) + poly ∗ X PRINT ”The value P(x) is”,Poly (ii) Algorithm to Evaluate P 0 (x) D(N − 1) := N ∗ A(N) FOR K = N − 1 DOWNTO 1 DO D(K − 1); = K ∗ A(K) + D(K) ∗ X PRINT ”The value P 0 (x) is”, D(0) Space-saving version : Deriv := N ∗ A(N) FOR K = N − 1 DOWNTO 1 DO Deriv := K ∗ A(K) + Deriv ∗ X PRINT ”The value P 0 (x) is”, Deriv (iii) Algorithm to Evaluate P(x) I(N + 1) := A(N)/(N + 1) FOR K = N DOWNTO 1 DO I(K); = A(K − 1)/K + I(K + 1) ∗ X I(0) := C + I(1) ∗ X PRINT ”The value I(x) is”, I(0) Space-saving version : Integ := A(N)/(N + 1) FOR K = N DOWNTO 1 DO Integ := A(K − 1)/K + Integ ∗ X Integ := C + integ ∗ X PRINT ”The value I(x) is”,Integ 3.2.1 Exercises for Introduction to Interpolation 1. Consider P(x) = −0.02x 3 + 0.1x 2 − 0.2x + 1.66, which passes through the four points (1, 1.54),(2, 1.5),(3, 1.42), and (5, 0.66). (a) Find P(4). (b) Find P 0 (4). (c) Find the definite integral of P(x) taken over [1, 4]. 21
(d) Find the extrapolated value P(5.5) (e) Show how to find the coefficients of P(a) 2. Consider P(a)=-004 3+0.14.r2-0 16c+2.08, which passes througl the four points(0,208),(1,202),(2,2.00),and(4,1.12) (a) Find P(3 (b)Find P(3) (c) Find the definite integral of P(a)taken over 0, 3 (d) Find the extrapolated value P(4.5 (e) Show how to find the coefficients of P(a) 3. Consider F(x)=-0.029216667x3+0.275x2-0.5708333-1.375, which passes through the four points(1, 1.05), (2, 1.10),(3, 1.35), and (5, 1.75) (a) Show that the ordinate 1.05, 1.10, 1.35, and 1. 75 differ from those of example 1.4 by less than 1.8%, yet the coefficients of a and a differ by more than 42% (b)Find P(4) and compare with Example 1.4 (c) Find P(4)and compare with Example 1.4 (d)Find the definite integral of P(a)taken over [1, 4 and compare with Example 1.4 (e) Find the extrapolated value P(5.5 )and compare with Example 1.4 Remark. Part(a) shows that the computation of the coefficients of an interpolating polynomial is an ill-conditioned problem 3.2.2 Algorithms and programs 1. Write a program in MATLAB that will implement Algorithm 1. 1. The pro- gram should accept the coefficients of the polynomial P()=aN.+aN-1 xN-1+…+a2x2+a1x+ ao as an1× N matrix:P=aNaN-1…a2a1ao] 2. For each of the given functions, the fifth-degree polynomial P(ar)passes through the six points(0,f(0),(0.2,f(0.2),(0.4,f(0.4),(0.6,f(0.6),、(0.8, f(0. 8)), (1, f(1). The six coefficients of P(r) are ao, a1, .. as, where a2-+a1x+a0. (i)Find the coefficients of P(a) by solving the 6 x 6 system of linear quations ao+a1.+a2-2+3-+a424as c=f(,) ing T;=G-1)/5 and j=1, 2, 3, 4, 5, 6 for the six unknowns ak]k-o (ii)Use your MATLAB program from Problem 1 to compute the interpo- lated values P(0.3), P(0.4), and P(0.5)and compare with f(0, 3), f(0. 4) and f(0.5), respectively (iii) Use your MATLAB program to compute the extrapolated values P(-0.1) and P(1.1)and compare with f(0. 1)and(f(1. 1), respectively
(d) Find the extrapolated value P(5.5). (e) Show how to find the coefficients of P(x). 2. Consider P(x) = −0.04x 3 + 0.14x 2 − 0.16x + 2.08, which passes through the four points (0, 2.08),(1, 2.02),(2, 2.00), and (4, 1.12). (a) Find P(3). (b) Find P 0 (3). (c) Find the definite integral of P(x) taken over [0, 3]. (d) Find the extrapolated value P(4.5). (e) Show how to find the coefficients of P(x). 3. Consider P(x) = −0.0292166667x 3 + 0.275x 2 − 0.570833333x − 1.375, which passes through the four points (1, 1.05),(2, 1.10),(3, 1.35), and (5, 1.75). (a) Show that the ordinate 1.05, 1.10, 1.35, and 1.75 differ from those of example 1.4 by less than 1.8%, yet the coefficients of x 3 and x differ by more than 42%. (b) Find P(4) and compare with Example 1.4. (c) Find P 0 (4) and compare with Example 1.4. (d) Find the definite integral of P(x) taken over [1, 4] and compare with Example 1.4. (e) Find the extrapolated value P(5.5) and compare with Example 1.4. Remark. Part (a) shows that the computation of the coefficients of an interpolating polynomial is an ill-conditioned problem. 3.2.2 Algorithms and Programs 1. Write a program in MATLAB that will implement Algorithm 1.1. The program should accept the coefficients of the polynomial P(x) = aN x N + aN−1 x N−1 + · · · + a2x 2 + a1x + a0 as an 1 × N matrix: P = [aN aN−1 · · · a2 a1 a0]. 2. For each of the given functions, the fifth-degree polynomial P(x) passes through the six points (0, f(0)),(0.2, f(0.2)),(0.4, f(0.4)),(0.6, f(0.6)),(0.8, f(0.8)),(1, f(1)). The six coefficients of P(x) are a0, a1, · · · , a5, where P(x) = a5x 5 + a4x 4 + a3x 3 + a2x 2 + a1x + a0. (i) Find the coefficients of P(x) by solving the 6 × 6 system of linear equations a0 + a1x + a2x 2 + a3x 3 + a4x 4 + a5x 5 = f(xj ) using xj = (j − 1)/5 and j = 1, 2, 3, 4, 5, 6 for the six unknowns {ak} 5 k=0. (ii) Use your MATLAB program from Problem 1 to compute the interpolated values P(0.3), P(0.4), and P(0.5) and compare with f(0, 3), f(0.4), and f(0.5), respectively. (iii) Use your MATLAB program to compute the extrapolated values P(−0.1) and P(1.1) and compare with f(−0.1) and (f(1.1), respectively. 22