Divided Differences in Polynomial Interpolation

Sec:3.3 Divided Differences

Sec:3.3 Divided Differences How many lines passes through these two points ? How many parabola passes through these three points ? How many polynomial of degree one passes through these two points ? How many polynomial of degree two passes through these three points ? there is one and only one polynomial of order n that passes through all the points. Polynomial interpolation consists of determining the unique nth-order polynomial that fits n + 1 data points. How many polynomial of degree n passes through these (n+1) points ?

Sec:3.3 Divided Differences Although this polynomial is unique, there are alternate algebraic representations that are useful in certain situations. Lagrange interpolating polynomial Divided-Difference Notation ? ? ? = ?(??)??,?? first divided difference zeroth divided difference ?=0 ?(?) is nth order polynomial that passes exactly through all n + 1 data points (?0,?(?0)), ,(??,?(??)) ? ?0 = ?(?0) ?[??,??] =?[?1] ?[?0] ?1 ?0 ? ?1 = ?(?1) ?[??,??+?] =?[??+1] ?[??] ??+1 ?? ? ?? = ?(??) Example Compute first divided difference ? ?0,?1 and ? ?1,?2 ? ?0=1 ?1=2 ?2=4 ?[?] ?[?0] =1 ?[?1] =8 ? ?2 = 14 ? ? ? =8 1 2 1 ?0=1 ?1=2 ?2=4 ? ?0=1 ? ?1=8 ? ?2=14 = 7 ? ?0,?1 =14 8 4 2 ? ?1,?2 = 3

Sec:3.3 Divided Differences Divided-Difference Notation second divided difference zeroth divided difference first divided difference ?[??,??,??] =?[??,??] ?[??,??] ?? ?? ?[??,??] =?[?1] ?[?0] ? ?0 = ?(?0) ?1 ?0 ? ?1 = ?(?1) ?[??,??+?,??+?] =?[??+?,??+?] ?[??,??+?] ??+? ?? ?[??,??+?] =?[??+1] ?[??] ? ?? = ?(??) ??+1 ?? Example Compute first divided difference ? ?0,?1,,?2 first divided difference second divided difference ? ?[?] ?0=1 ?[?0] =1 ? ?0,?1 =8 1 2 1= 7 ? ??,??,??=? ??,?? ? ??,?? =? ? ? ?= ? ?1=2 ?[?1] =8 ?? ?? ? ? ?1,?2 =14 8 4 2= 3 ?2=4 ? ?2 = 14

Sec:3.3 Divided Differences Divided-Difference Notation second divided difference zeroth divided difference first divided difference ?[??,??,??] =?[??,??] ?[??,??] ?? ?? ?[??,??] =?[?1] ?[?0] ? ?0 = ?(?0) ?1 ?0 ? ?1 = ?(?1) ?[??,??+?,??+?] =?[??+?,??+?] ?[??,??+?] ??+? ?? ?[??,??+?] =?[??+1] ?[??] ? ?? = ?(??) ??+1 ?? K-th divided difference (K-1)-th divided difference ?[??,??+?, ,??+?] =?[??+?, ,??+?] ?[??, ,??+? ?] ??+? ?? divided differences are defined recursively

Sec:3.3 Divided Differences n-th divided difference ?[??,??, ,??] =?[??, ,??] ?[??, ,?? ?] ?? ?? divided differences are defined recursively

Sec:3.3 Divided Differences n-th divided difference ?[??,??, ,??] =?[??, ,??] ?[??, ,?? ?] ?? ?? Example Compute the third divided difference ? ?0,?1,?2,?3 First Second Third ?? ?[??] 1 3 6 3 2 1 13 3 3 1 = 3 = 5 2 6 19 6 3 2 9 5 5 1= 1 = 13 3 19 40 13 5 2 = 9 99 19 5 3 5 99 = 40 ? ?0,?1,?2,?3 = ? 1,2,3,5 = 1

Sec:3.3 Divided Differences A polynomial of order 2 that passes through the three points (?0,?(?0)), (?1,?(?1)), (?2,?(?2)). ?2? = ?[??] + ?[??,??] ? ?0 + ?[??,??,??] ? ?0 ? ?1

Sec:3.3 Divided Differences Example ? ?[?] Fit a second-order polynomial to the three points ?0=1 ?[?0] =1 ?1=2 ?[?1] =8 ?2=4 ? ?2 = 14 first divided difference second divided difference ? ?[?] ?0=1 ?[?0] =1 ? ?0,?1 =8 1 2 1= 7 ? ??,??,??=? ??,?? ? ??,?? =? ? ? ?= ? ?1=2 ?[?1] =8 ?? ?? ? ? ?1,?2 =14 8 4 2= 3 ?2=4 ? ?2 = 14 ?2? = ?[??] + ?[??,??] ? ?0 + ?[??,??,??] ? ?0 ? ?1 ?2? = ? + ? ? 1 ? ?? 1 ? 2

Sec:3.3 Divided Differences General Form of Newton s Interpolating Polynomials A polynomial of order n that passes through the (n+1) points (?0,?(?0)), (?1,?(?1)), ,(??,?(??)). ??? = ?[??] + ?[??,??] ? ?0 + ?[??,??,??] ? ?0 ? ?1 + + ?[??,??, ,??] ? ?0 ? ?1 ? ?? 1 ??does not appear in the product

Sec:3.3 Divided Differences Example ?? ?(??) 1 3 2 6 3 19 5 99 Calculate f (4) using Newton s interpolating polynomials of order 3. Given the data First Second Third ?? ?[??] 1 3 ? 2 6 ? ?? 3 19 ? ? 5 99 ?? ??? = ? + ? ? ? + ? ? ? ? ? + ?(? ?)(? ?)(? ?) The coefficients of the Newton forward divided- difference form of the interpolating polynomial are along the diagonal in the table. ??? = ??

Sec:3.3 Divided Differences Example x 1.0 0.7651977 1.3 0.6200860 1.6 0.4554022 1.9 0.2818186 2.2 0.1103623 f (x) Complete the divided difference table for the data given in the adjacent Table and construct the interpolating polynomial that uses all this data. First Second Third Fourth 0 1.0 0.4837057 0.7651977 0.1087339 1 1.3 0.6200860 0.0658784 0.5489460 0.0018251 2 1.6 0.4554022 0.0494433 0.5786120 3 1.9 0.2818186 0.0680685 0.5715210 0.0118183 4 2.2 0.1103623 ??(?) = ?.??????? ?.??????? ? ?.? ?.??????? ? ?.? ? ?.? + ?.??????? ? ?.? ? ?.? ? ?.? + ?.???????(? ?.?)(? ?.?)(? ?.?)(? ?.?) The coefficients of the Newton forward divided-difference form of the interpolating polynomial are along the diagonal in the table.

Sec:3.3 Divided Differences 4th First Second Third ?? ?[??] 1 3 ? 2 6 ? ?? 3 19 ? ? 5 99 ?? 7 291 ??? = ? + ? ? ? + ? ? ? ? ? + ?(? ?)(? ?)(? ?) 1st 3 2ed 3ed 4th ?? 1 2 ?[??] 3 6 Remark 5 13 If poly of degree 4 is needed, then just complete the diagonal . 1 0 3 5 7 19 99 291 9 40 1 14 96

Sec:3.3 Divided Differences First Second Third ?? ?[??] 1 3 ? 2 6 ? ?? 3 19 ? ? 5 99 ?? ??? = ? + ? ? ? + ? ? ? ? ? + ?(? ?)(? ?)(? ?) Remark Remark The poly of degree 2 which passes through the first three points (1, 3), (2, 6), (3, 19) The poly of degree 1 which passes through the first two points (1, 3), (2, 6) ??? = ? + ? ? ? + ?(? ?)(? ?) ??? = ? + ?(? ?)

Sec:3.3 Divided Differences Example ?? ?(??) 1 3 2 6 3 19 5 99 Calculate f (4) using Newton s interpolating polynomials of order 1 ,2, 3. Given the data First Second Third ?? ?[??] 1 3 ? 2 6 ? ?? 3 19 ? ? 5 99 ?? ??? = ? + ?(? ?) ??? = ?? ??? = ? + ? ? ? + ?(? ?)(? ?) ??? = ?? ??? = ? + ? ? ? + ? ? ? ? ? + (? ?)(? ?)(? ?) ??? = ??

Sec:3.3 Divided Differences data=[1.0 0.7651977; 1.3 0.6200860; 1.6 0.4554022; 1.9 0.2818186; 2.2 0.1103623]; function [d]=Divided_diff(x,y) d=y; n=length(x); for j=2:n for k=n:-1:j d(k)=(d(k)-d(k-1))/(x(k)-x(k-j+1)); end end x =data(:,1); y=data(:,2); [d]=Divided_diff(x,y); d First Second Third Fourth 0 1.0 0.4837057 0.7651977 0.1087339 1 1.3 0.6200860 0.0658784 0.5489460 0.0018251 2 1.6 0.4554022 0.0494433 0.5786120 3 1.9 0.2818186 0.0680685 0.5715210 0.0118183 4 2.2 0.1103623

Sec:3.3 Divided Differences Example ?? ?(??) 1 3 2 6 3 19 5 99 7 291 Write the Newton s interpolating polynomials of order 4. Given the data 1st 3 2ed 3ed 4th ?? 1 2 ?[??] 3 6 5 13 1 0 3 5 7 19 99 291 9 40 1 14 96

Sec:3.3 Divided Differences Example x=[8 9 11 12]; y=log10(x); 0.9031 0.0512 -0.0025 0.0001 Fit a third-order Newton s interpolating polynomial to estimate log(10) using the data at x = 8, 9, 11 and 12. Compute the true percent relative error. [d]=Divided_diff(x,y); d [yi] = eval_poly(x,d,10) Rel_err = (yi-1)/1*100 function [yi] = eval_poly(x,d,xi) yi = d(1); prod = 1; n = length(d); for k=1:n-1 prod=prod*(xi-x(k)) yi=yi+d(k+1)*prod; end ?? ?(??) 8 9 11 12 0.9031 0.9542 1.0414 1.0792 ??(?) = 0.9031+0.0512 ? ? 0.0025 ? ? ? ? + 0.0001 ? ? ? ? (? ??) ??(??) = 1.000044924225105 True percent relative error = 0.0045%

Sec:3.3 Divided Differences Example x=[0 pi/2 pi 3*pi/2 2*pi]; y=sin(x); [d]=Divided_diff(x,y); xx=[0:0.1:2*pi]; [yy] = eval_poly(x,d,xx); ezplot('sin(x)',[0,2*pi]); grid on; hold on plot(xx,yy); plot(x,y,'k*'); hold off Fit a 4th-order Newton s interpolating polynomial to approximate sin(x) using the data at x = 0, pi/2, pi, 3*pi/2 and 2*pi. Plot sin(x) and ?4(?). ? = ???(?) ??(?)

Sec:3.3 Divided Differences Errors of Newton s Interpolating Polynomials ??? = ? ??+ ? ??,?? ? ?0 + + ?[??, ,??] ? ?0 ? ?? 1 ? ? ??? = ??(?) ??(?) =??+1?(?) ? ?0 ? ?? (? + 1)! Theorem 3.6 ?[??,??] =?[??] ?[??] Suppose that f Cn[a, b] and x0, x1, . . . , xnare distinct numbers in [a, b]. Then a number exists in (a, b) with ?? ?? ?[??,??] = ?(?) for some number between x0 and x1 ?(?)(? ) ?! ? [?0,...,??] = Theorem3.6 generalizes this result.

Sec:3.3 Divided Differences Errors of Newton s Interpolating Polynomials ??? = ? ??+ ? ??,?? ? ?0 + + ?[??, ,??] ? ?0 ? ?? 1 ? ? = ??? + ??(?) ??(?) =??+1?(?) ? ?0 ? ?? (? + 1)! For an nth-order interpolating polynomial, an alternative relationship for the error is ?[??, ,??,?] ? ?0 ? ?? ??(?) = ? = ?[??, ,??,?] ? ?? ?=?

Sec:3.3 Divided Differences Remark ? ??, ,?? = ? ???, ,???? ??, ,?? is any rearrangement of the integers 0, 1, . . . , n

Sec:3.3 Divided Differences ??(?) = ?[?,??, ,??] ? ?0 ? ?? nth-order error is Example Problem 18.2 pp522 ??(?) = 0.9031+0.0512 ? ? 0.0025 ? ? ? ? ??(??) = 1.000343408828085 True error = - 3.434e-04 Fit a second-order Newton s interpolating polynomial to estimate log(10) using the data at x = 8, 9, and 11. Compute the true error. ?? ??(?) = ?[?,??,??,??] ? ??(? ??) ? ?? ??(??) = ?[??,??,?,?] ?? ? (?? ?) ?? ?? ?(??) (*) 8 9 11 12 0.9031 0.9542 1.0414 1.0792 ???? = ?.??????? ?? ? (?? ?) ?? ?? ??(10) = -3.434e-04 Because (*) contains the unknown f (10), it cannot be solved for the error. However, if an additional data point f (?3) is available, (*) can be used to estimate the error, as in x=[8 9 11]; y=log10(x); [d]=Divided_diff(x,y); [yi] = eval_poly(x,d,10) err = yi-1 0.9031 0.0512 -0.0025 ??(??) ?[??,??,?,?] ?? ? (?? ?) ?? ?? ???? ?.??? ? ?? ? (?? ?) ?? ?? ???? -2.985e-04