ECM-2D K L University - Home



Finite Differences and Interpolation

Suppose we are given the following values of y = f(x) for a set of values of x :

x : x0 x1 x2 …… xn

y : y0 y1 y2 …… yn

The process of finding the values of y corresponding to any value of x=xi between x0 and xn is called interpolation.

← The technique of estimating the value of a function for any intermediate value of the independent variable is called interpolation.

← The technique of estimating the value of a function outside the given range is called extrapolation.

← The study of interpolation is based on the concept of differences of a function.

← Suppose that the function y=f(x) is tabulated for the equally spaced values x = x0, x1=x0+h, x2=x0+2h, …, xn=x0+nh giving y = y0, y1, y2, …, yn. To determine the values of f(x) and f '(x) for some intermediate values of x, we use the following three types of differences

1. Forward differences

2. Backward differences

3. Central differences

Forward differences: The forward differences are defined and denoted by ∆f(x)=f(x+h)-f(x),

∆y0 = y1 – y0

∆y1 = y2 – y1

∆y2 = y3 – y2

…………….

∆yr = yr+1 – yr

…………….

∆yn-1 = yn – yn-1

These are called the first forward differences and ∆ is the forward difference operator.

Similarly the second forward differences are defined by

∆2 yr = ∆ yr+1 – ∆yr.

In general

∆p yr = ∆p-1 yr+1 – ∆p-1yr ,

pth forward differences.

The forward differences systematically set out in a table called forward difference table.

|Value of x |Value of y |1st diff. |2nd diff. |3rd diff. |4th diff. |

| | |∆ |∆2 |∆3 |∆4 |

|y |3 |? |2 |? |-2.4 |

Sol. Let p and q be the missing values in the given table, then the difference table is as follows:

|x |y |∆y |∆2y |∆3y |

|45 |3 | | | |

| | |p – 3 | | |

|50 |p | |5 – 2p | |

| | |2 – p | |3p + q – 9 |

|55 |2 | |p + q – 4 | |

| | |q – 2 | |3.6 – p – 3q |

|60 |q | |–0.4 – 2q | |

| | |–2.4 – q | | |

|65 |-2.4 | | | |

Since three entries are given, the function y can be represented by a second degree polynomial.

Therefore, ∆3y0 = 0 and ∆3y1 = 0. Thus 3p + q – 9 = 0 and 3.6 – p – 3q = 0. Solving these equations, we get p = 2.925 and q = 0.225.

Example#2. Determine the missing values in the following table without using difference table.

|x |45 |50 |55 |60 |65 |

|y |3 |? |2 |? |-2.4 |

Sol. Given that y0 = 3, y2 = 2 and y4 = -2.4 and missing values be taken as y1= p and y3 = q. Since three entries are given, the function y can be represented by a second degree polynomial.

Therefore, ∆3y0 = 0 and ∆3y1 = 0.

(E – 1)3y0 = 0 (E – 1)3y1 = 0

(E3 – 3E2 + 3E – 1)y0 = 0 (E3 – 3E2 + 3E – 1)y1 = 0

y3 – 3y2 + 3y1 – y0 = 0 y4 – 3y3 + 3y2 – y1 = 0

q – 3(2)+ 3p – 3 = 0 -2.4 – 3q + 3(2) – p = 0

3p + q – 9 = 0 3.6 – p – 3q = 0.

Solving these equations, we get p = 2.925 and q = 0.225.

Newton’s Forward Interpolation Formulae:

Let the function y=f(x) take the values y0, y1, y2, … corresponding to the values x0, x1, x2, … of x. Suppose it is required to evaluate f(x) for x=x0+ph, p is any real number.

For any real number p, we have defined E such that

Ep f(x) = f(x0+ph)

yp = f(x0+ph) = Epf(x0)= (1+∆)py0

= [1+p∆+p(p-1)/2! ∆2 + p(p-1)(p-2)/3! ∆3 +…] y0

= y0 + p ∆y0 + p(p-1)/2! ∆2 y0+ p(p-1)(p-2)/3! ∆3 y0+…

It is called Newton’s forward interpolation formulae.

Newton’s Backward Interpolation Formulae:

Suppose it is required to evaluate f(x) for x=xn+ph, where p is any real number.

Ep f(x) = f(xn+ph)

yp = f(xn+ph) = Epf(xn)= (1- [pic])-p yn

= [1+p[pic]+p(p+1)/2! [pic]2 + p(p+1)(p+2)/3![pic]3 +…] yn

= yn + p[pic]yn + p(p+1)/2![pic]2 yn+ p(p+1)(p+2)/3![pic]3 yn+…

It is called Newton’s backward interpolation formulae.

Choice of Newton’s Interpolation formulae:

← Newton’s forward interpolation formulae is used for interpolating the values of y near the beginning of a set of tabulated values and extrapolating values of y a little backward of y0.

← Newton’s backward interpolation formulae is used for interpolating the values of y near the end of a set of tabulated values and also extrapolating values of y a little ahead of yn.

Example#1. The table gives the distances in nautical miles of the visible horizon for the given heights in feet above the earth’s surface :

|x=height |100 |150 |200 |250 |300 |

| | |121 | | | |

|7 |392 | |24 | | |

| | |265 | |1 | |

|11 |1452 | |32 | |0 |

| | |457 | |1 | |

|13 |2366 | |42 | | |

| | |709 | | | |

|17 |5202 | | | | |

By Newton divided difference formula

f(x) = y0+(x-x0)[x0, x1] + (x-x0)(x-x1)[x0, x1, x2] +(x-x0)(x-x1)(x-x2)[x0, x1, x2,x3]

+ (x-x0)(x-x1)(x-x2)(x-x3)[x0, x1, x2,x3,x4].

f(9) = 150 + (9 – 5)×121 + (9 – 5) (9 – 7)×24 + (9 – 5)(9 – 7)(9 – 11)×1

+ (9 – 5)(9 – 7)(9 – 11)(9 – 13)×0

= 150 + 484 + 192 – 16 + 0

= 810.

Numerical Differentiation:

Mathematically, the derivative represents the rate of change of a dependent variable with respect to an independent variable. For example, if we are given a function y(t) that specifies an object’s position as a function of time, differentiation provides a means to determine its velocity, as in:

[pic]

As in following Figure, the derivative can be visualized as the slope of a function.

[pic]

Numerical differentiation is used when the function y = f(x) is given in tabular form or it is highly complex. The basic idea in numerical differentiation is to replace the given function y = f(x) on the interval by an interpolating polynomial P(x) and set f '(x) = P'(x), f '' (x) = P'' (x) etc. Numerical differentiation is less exact than interpolation.

Numerical differentiation using Newton’s forward formula: Suppose y = f(x) is specified in an interval [a, b] at equally spaced points xi = x0 + ih (i = 0, 1, …, n) (x0=a, xn=b) by means of values yi = f(xi). By Newton forward interpolation formula

[pic],

where [pic]and h = xi+1 – xi, for i = 1, 2, …, n. Here p is a function of x and [pic]. Rewriting the above equation, we have

[pic]

Differentiating the above equation with respect to x, we have

[pic]Again differentiating with respect to x, we get

[pic]Special case: If the derivative is required to find at a basic tabulated point x = xi, then choose x0= xi and the formulas become

[pic]

And

[pic]

Numerical differentiation using Newton’s backward formula:

In this case we replace y(x) by Newton’s backward interpolation formula

[pic]

where [pic]and h = xi+1 – xi, for i = 1, 2, …, n. Here p is a function of x and [pic]. Rewriting the above equation, we have

[pic]

Differentiating the above equation with respect to x, we have

[pic]Again differentiating with respect to x, we get

[pic] Special case: If the derivative is required to find at a basic tabulated point x = xi, then choose xn= xi and the formulas become

[pic]

and

[pic]

Example#1. Compute f'(x) and f''(x) at (i) x = 16 (ii) x = 15 (iii) x = 24 (iv) x = 25 from the following table

|x |15 |17 |19 |21 |23 |25 |

|f(x) |3.873 |4.123 |4.359 |4.583 |4.796 |5.8 |

Sol. Let y = f(x), then from the given table x0 = 15, x1 = 17, x2 = 19, x3 = 21, x4 = 23, x5 = 25 and y0 = 3.873, y1 = 4.123, y2 = 4.359, y3 = 4.583, y4 = 4.796, y5 = 5.8. The finite difference table is

|x |y |∆y |∆2y |∆3y |∆4y |∆5y |

|15 |3.873 | | | | | |

| | |0.25 | | | | |

|17 |4.123 | |-0.014 | | | |

| | |0.236 | |0.002 | | |

|19 |4.359 | |-0.012 | |-0.001 | |

| | |0.224 | |0.001 | |0.002 |

|21 |4.583 | |-0.011 | |0.001 | |

| | |0.213 | |0.002 | | |

|23 |4.796 | |-0.009 | | | |

| | |0.204 | | | | |

|25 |5 | | | | | |

(i) Since x = 16 is nearer to the beginning of the table we use Newton forward formula. Here the step size h = 2. Taking x0 = 15, then [pic]

Newton forward formula to compute first derivative of y=f(x) is

[pic]

Substituting x = 16, p = 0.5, ∆y0 = 0.25, ∆2y0= – 0.014, ∆3y0 = 0.002, ∆4y0= – 0.001, ∆5y0=0.002, we have

[pic]

fʹ(16) = 0.1249375.

Newton forward formula to compute second derivative of y=f(x) is

[pic]

Substituting the values from the table, we have

[pic]

fʹʹ(16) = -0.0038229.

(ii) Since x = 15 is in the beginning of the table, we use Newton forward formula. Here the step size h = 2, x = x0 = 15 and p = 0.

Newton forward formula to compute first derivative of y=f(x) at x = x0 is

[pic]

Substituting the values from the table, we have

[pic]

f'(15) = 0.128958.

Newton forward formula to compute second derivative of y=f(x) at x = x0 is

[pic]

Substituting the values from the table, we have

[pic]

f''(15) = -0.004229.

(iii) Since x = 24 is nearer to the ending of the table, we use Newton backward formula. Here the step size h = 2. Taking xn = 25, then [pic]

Newton backward formula to compute first derivative of y=f(x) is

[pic]

Substituting x = 25, p = – 0.5, [pic]yn = 0.204, [pic]2yn= – 0.009, [pic]3yn = 0.002, [pic]4yn= 0.001, [pic]5yn=0.002, we have

[pic]

f'(24) = 0.09727.

Newton backward formula to compute second derivative of y=f(x) is

[pic]

Substituting the values from the table, we have

[pic]

f''(24) = -0.00242708.

(iv) Since x = 25 is in the ending of the table, we use Newton forward formula. Here the step size h = 2, x = x0 = 15 and p = 0.

Newton backward formula to compute first derivative of y=f(x) at x = xn is

[pic].

Substituting the values from the table, we have

[pic]

f '(25) = 0.10048

Newton backward formula to compute second derivative of y=f(x) at x = xn is

[pic]

Substituting the values from the table, we have

[pic]

f ''(25) = -0.001833.

Numerical Integration

Integration is the inverse of differentiation. Just as differentiation uses differences to quantify an instantaneous process, integration involves summing instantaneous information to give a total result over an interval. Thus, if we are provided with velocity as a function of time, integration can be used to determine the distance traveled:

[pic]

According to the dictionary definition, to integrate means “to bring together, as parts, into

a whole; to unite; to indicate the total amount” Mathematically, definite integration is

represented by

[pic] (1)

which stands for the integral of the function f (x) with respect to the independent variable x, evaluated between the limits x = a to x = b. As suggested by the dictionary definition, the “meaning” of Eq. (1) is the total value, or summation, of f (x)dx over the range x = a to b. In fact, the symbol ∫ is actually a stylized capital S that is intended to signify the close connection between integration and summation.

Geometrically, integration is just finding the area under a curve from one point to another. It is represented by[pic], where the numbers a and b are the lower and upper limits of integration, respectively, the function f is the integrand of the integral, and x is the variable of integration. Figure 1 represents a graphical demonstration of the concept.

Why are we interested in integration: because most equations in physics are differential equations that must be integrated to find the solution(s). Furthermore, some physical quantities can be obtained by integration (example: displacement from velocity).

The problem is that sometimes integrating analytically some functions can easily become laborious. For this reason, a wide variety of numerical methods have been developed to find the integral.

The process of evaluating a definite integral from a set of tabulated values of the integrand f(x) is called numerical integration. This process when applied to a function of single variable, is known as quadrature.

Let [pic], where y(x) takes the values y0, y1, y2, …, yn for x = x0, x1, x2, …, xn. Let us divide the interval (a, b) into n sub-intervals of width h so that x0 = a, x1 = x0 + h, x2 = x0 + 2h, …, xn = x0 + nh = b.

Trapezoidal rule : [pic].

Simpson’s 1/3rd rule :

[pic]

Simpson’s 3/8th rule :

[pic]

Problem#1. Compute the integral [pic], using (i) Trapezoidal rule (ii) Simpson’s 1/3rd rule (iii) Simpson’s 3/8th rule and also determine the relative true error.

Sol. Let [pic]and divide the interval (0, 6) into n = 6 subintervals each of length h = 1. Then, we have the following tabular values.

|x |0 |1 |2 |3 |4 |5 |6 |

|y(x) |1 |0.5 |0.2 |0.1 |0.0588 |0.0385 |0.027 |

(i) Trapezoidal rule

[pic].

[pic]

(ii) Simpson’s 1/3rd rule

[pic]

[pic]

(iii) Simpson’s 3/8th rule

[pic]

[pic]

[pic].

True value :

[pic]

Relative true error for (i) Trapezoidal rule = [pic]

(ii) Simpson’s 1/3rd rule = [pic]

(iii) Simpson’s 3/8th rule = [pic]

Problems

1. Estimate the missing values in the following table

|x |45 |50 |55 |60 |65 |

|y |3.0 |? |2.0 |? |-2.4 |

2. Express y=2x3-3x2+3x-10 in factorial notation and hence show that Δ3y=12.

3. Given Sin450= 0.7071, Sin500= 0.7660, Sin550= 0.8192, Sin 600= 0.8660, find Sin520, using Newton’s forward formula.

4. From the following table, estimate the number of students who obtained marks between 40 and45

|Marks |30-40 |40-50 |50-60 |60-70 |70-80 |

|No. of students |31 |42 |51 |35 |31 |

5. Construct a cubic polynomial which takes the following values:

|x |0 |1 |2 |3 |

|f(x) |1 |2 |1 |10 |

6. The area of a circle of diameter d is given for the following values:

|d |80 |85 |90 |95 |100 |

|A |5026 |5674 |6362 |7088 |7854 |

Calculate the area of a circle of diameter 105.

7. Use Gauss forward formula to evaluate y30, given that y21 = 18.4708, y25 = 17.8144, y29 = 17.1070, y35 = 16.3432 and y37 = 15.5154.

8. Interpolate by means of Gauss’s backward formula, the population of a town for the year 1974, given that

|Year |1939 |1949 |1959 |1969 |1979 |1989 |

|Population |12 |15 |20 |27 |39 |52 |

|(in thousands) | | | | | | |

9. Employ Sterling’s formula to compute y12.2 from the following table:

|x0 |10 |11 |12 |13 |14 |

|105ux |23,967 |28,060 |31,788 |35,209 |38,368 |

10. Apply Bessel’s formula to obtain y25, given y20 = 2854, y24 = 3162, y28 = 3544, y32 = 3992.

11. Given the values

|x: |5 |7 |11 |13 |17 |

|f(x): |150 |392 |1452 |2366 |5202 |

Evaluate f(9) by using (a) Lagrange’s formula (b) Newton’s divided difference formula.

12. Use Lagrange’s formula to find the form of f(x) when,

|x: |0 |2 |3 |6 |

|f(x): |648 |704 |729 |792 |

13. Determine f(x) as a polynomial in x for the following data using Newton’s divided difference formula

|x: |-4 |-1 |0 |2 |5 |

|f(x): |1245 |33 |5 |9 |1335 |

14. Apply Lagrange’s formula inversely to obtain a root of the equation f(x) = 0 f(30)= -30, f(34) = -13,f(38) = 3 and f(42)= 18.

15. Given that

|x |1.0 |1.1 |1.2 |1.3 |1.4 |1.5 |1.6 |

|y |7.989 |8.403 |8.781 |9.129 |9.451 |9.750 |10.031 |

find the values of dy/dx and d2y/dx2 at x = 1.1and at x 1.6.

16. Find the first and second derivatives of the function tabulated below, at the point x = 1.1

|x: |1.0 |1.2 |1.4 |1.6 |1.8 |2.0 |

|f(x): |0 |0.128 |0.544 |1.296 |2.432 |4.00 |

17. From the following table, find the values of dy/dx and d2y/dx2 at x = 2.03

|x: |1.96 |1.98 |2.00 |2.02 |2.04 |

|y: |0.7825 |0.7739 |0.7651 |0.7563 |0.7473 |

18. The following data gives the corresponding values of pressure and specific volume of a superheated steam.

|v |2 |4 |6 |8 |10 |

|p |105 |42.7 |25.3 |16.7 |13 |

19. From the table below, for each value of x, y is minimum? Also find the value of y

|x |3 |4 |5 |6 |7 |8 |

|y |0.205 |0.240 |0.259 |0.262 |0.250 |0.224 |

20. Given that ,

|x: |4.0 |4.2 |4.4 |4.6 |4.8 |5.0 |5.2 |

|logx: |1.3863 |1.4351 |1.4816 |1.5261 |1.5686 |1.6094 |1.6484 |

Evaluate [pic] by (a) Trapezoidal rule(b) Simpson’s 1/3 rule (c) Simpson’s

3/8th rule.

21. Use Simpson’s 1/3rd rule to find [pic]dx by taking seven ordinates.

22. The velocity (km/min) of a moped which starts from rest, is given at fixed intervals of time t (min) as follows:

|T |2 |4 |6 |8 |10 |

|y |1.0000 |0.9896 |0.9589 |0.9089 |0.8415 |

Short Answer Questions

1. Evaluate Δ2 (abx), interval of differences being unity.

2. Show that Δ log f(x)= log{1+Δf(x)/f(x)}

3. Evaluate Δ10 [(1-x) (1-2x2) (1-3x3) (1-4x4)], if the interval of differencing is 2.

4. Obtain the function whose first difference is 2x3+3x2-5x+4.

5. Prove that y3 = y2 + Δy1 + Δ2y0 + Δ3y0.

6. Prove with usual notations that (E1/2 + E-1/2) (1 + Δ) ½ = 2 + Δ.

7. Prove with usual notations that Δ3y2 = [pic] 3y5.

8. Prove with usual notations that µ2 = 1 + δ2/4.

9. State Newton’s forward interpolative formula.

10. State Bessel’s formula.

11. Write the relation between Δ and E.

12. If f(x) = 3x3 – 2x2 + 1, then find Δ3f(x)

13. State Stirling’s formula.

14. Write the relation between Δ , E and [pic]

15. Prove with usual notations that (1+Δ)(1- [pic]) = 1

16. State Lagrange’s Interpolation formula

17. State Newton’s divided difference formula

18. By Trapezoidal rule, write the value of [pic]dx

19. State Simpson’s 3/8 th rule.

20. If f(x) is given by x = 0 0.5 1 1.5 2

f(x) = 0 0.25 1 2.25 4.

Then the value of [pic]dx by Simpson’s 1/3 rule.

-----------------------

Chapter-2

[pic]

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download