MCA645 CU-MCA-SEM-II-Statistical & Numerical Methods-converted

For F4, we need to know: y + F3 =5+0.53523913352 =5.53523913352 So Step 2 Next, we take those 4 values and substitute them into the Runge-Kutta RK4 formula: We need to take this y1 value and use the new x1=0.2 value to find the next value, y2, and so on up to x=2. Following is the table of resulting values. We haven't included any values after y in the bottom row as we won't be using them. 100 CU IDOL SELF LEARNING MATERIAL (SLM)

4.4 PREDICTOR- CORRECTOR METHOD A general k-step implicit method involves, at the kth time step, and if f depends on y in a complicated way then it is not obvious how to dig yn+k out of fn+k = f((n + k)h, yn+k). One solution to this problem would be to only ever use explicit methods in which βk = 0. But this is not a good solution, for implicit methods generally have better properties than the explicit ones (for example, the implicit trapezium is second order while the explicit Euler is only first order). Another solution involves a so-called predictor-corrector method. This involves 1. The predictor step. We use an explicit method to obtain an approximation to yn+k. 2. The corrector step. We use an implicit method, but with the predicted value on the right- hand side in the evaluation of fn+k. We use to denote this approximate (predicted) value of fn+k. 3. We can then go on to correct again and again. At each step we put the latest approximation to yn+k in the right-hand side of the scheme (via f) to generate a new approximation from the left-hand side. (This is not unlike an implementation of Newton-Raphson. In that method we require an initial guess (we “predict”) and then the Newton-Raphson approach tells us how to iterate (or “correct”) our latest approximation. The main difference here is that we have a systematic way of obtaining the initial prediction.) It is sufficient for our purposes to illustrate the idea of a predictor-corrector method using the simplest possible pair of methods. We use Euler’s method to predict and the trapezium method to correct. 101 CU IDOL SELF LEARNING MATERIAL (SLM)

Example 1: Suppose that y = y(t) is the solution to the initial value problem Use Euler’s method and the trapezium method as a predictor-corrector pair (with one correction at each time step). Take the time step to be h = 0.05 so as to obtain approximations to y (0.05) and y (0.1). If correction is repeated until the corrected values settle down to a converged number then the approximation inherits all the (nice) properties of the implicit scheme. So, in the example above we 102 CU IDOL SELF LEARNING MATERIAL (SLM)

would have second order accurate results obtained by a procedure which gets around the implicit nature of the trapezium method. Of course in the hand-calculations done above we only corrected once, rather than repeatedly to convergence. The example above is such that the dependence of f (t, y) on y is very simple and we could use the approach seen in Section 32.1 to implement the trapezium method. It turns out that the true trapezium method approximations to y (0.05) and y (0.1) are y1 = 3.155128 and y2 = 3.320776 respectively, to 6 decimal places. The predictor-corrector method will produce these values if enough corrections are taken. Example 2: y′ = xi 0 0.5 1 1.5 yi 2 2.636 3.595 4.968 Find y (2) by Milne's Simpson predictor corrector method Solution: y′ = Milne's Simpson predictor formula is We have given that 103 x0 =0, x1= 0.5, x2=1, x3 =1.5 and using Runge kutta 4 method, we get y0=2, y1=2.636, y2=3.595, y3=4.968 y′ = CU IDOL SELF LEARNING MATERIAL (SLM)

y′1 = = 1.568 (where x=0.5, y=2.636) y′2 = = 2.2975 (where x=1, y=3.595) y′3 = = 3.234 (where x=1.5, y=4.968) putting the values in (2), we get So, the predicted value is 6.871 Now, we will correct it by corrector method to get the final value y4=6.8732 104 CU IDOL SELF LEARNING MATERIAL (SLM)

∴y (2) =6.8732 (Answer) 4.5 SUMMARY In real-life application, models typically involve objects & recorded rates of change between them (derivatives/differentials) — the goal of DFQ is to define a general relationship between the two. Systems of this kind are extremely common in natural phenomena, which is precisely why DFQ plays a prominent role in topics ranging from physics to economics & biology. The Euler and the Runge–Kutta methods are considered efficient numerical algorithms and are currently used for solving integer order ordinary differential equations (ODE). When sending a satellite to another planet, it is often necessary to make a course correction mid-way. The differential equations governing the motion are well known, so the projected path can be calculated by solving the differential equations concerned. Often this is done using a Runge-Kutta method (or a variant thereof), particularly if the effect of another planet is of consequence. Likewise, if a correction has to be made, the effect of the correction can be calculated before making it to ensure that it is an appropriate correction. Again a Runge-Kutta technique can be used. 4.6 KEYWORDS • Taylor Series: In mathematics, the Taylor series of a function is an infinite sum of terms that are expressed in terms of the function's derivatives at a single point. • Euler Method: In mathematics and computational science, the Euler method (also called forward Euler method) is a first-order numerical procedure for solving ordinary differential equations (ODEs) with a given initial value. • Static re-gridding: means that in the course of the time. evolution, the space grid is adapted at discrete times. • Step size: incremental change in the x-coordinate • Error Control : An error-correcting code is an algorithm for expressing a sequence of numbers such that any errors which are introduced can be detected and corrected (within certain limitations) based on the remaining numbers 4.7 LEARNING ACTIVITY 1. Suppose that y = y(t) is the solution to the initial value problem 105 CU IDOL SELF LEARNING MATERIAL (SLM)

Use Euler’s method and the trapezium method as a predictor-corrector pair (with one correction at each time step). Take the time step to be h = 0.2 so as to obtain approximations to y (0.2) and y (0.4). 2. Solve the following using RK4 (Runge-Kutta Method of Order 4) for 0 ≤ x ≤2. Use a step size of h=0.2: 4.8 UNIT END QUESTIONS A. Descriptive Type Questions 1. What is Taylor Series? 2. Discuss Euler’s method 3. Explain Runge Kutta Method 4. Compare advantage of Taylor expansion and Runge Kutta Method 5. Explain Predictor- Corrector Method B. Multiple Choice Questions as a predictor. 1. The second-order Runge-Kutta method uses a) Backward order method b) forward Euler method c) midpoint rule d) multipoint method 2. How many steps does the fourth-order Runge-Kutta method use? a) Two steps b) Five steps c) Four steps d) Three steps 106 CU IDOL SELF LEARNING MATERIAL (SLM)

3. The expansion of f(a+h) is 4. How many predictor and corrector steps does the fourth-order Runge-Kutta method use? a) Three predictor and one corrector steps b) One predictor and three corrector steps c) Two predictor and two corrector steps d) One predictor and two corrector steps 5. To find the value of cosh (23) with good accuracy the Taylor series should be centered at a) 23 b) 22 c) 21 d) Delta (small) interval around 23 Answers: 1 - b; 2 - c; 3 - a; 4 - c; 5 -d; 4.9 REFERENCES • Rajaraman V., Computer Oriented Numerical Method. New Delhi: Prentice Hall. • Gupta S.P. and Kapoor, V.K. (2014). Fundamentals of Mathematical Statistics. Delhi: Sultan Chand and Sons. • Sujatha Sinha, Sushma Pradhan, Numerical Analysis and Statistical Methods, Academic Publishers. • Graybill (1990). Introduction to Statistics. New York: McGraw Publishing House. • J. H. Wilkinson , The Algebraic Eigenvalue Problem (Numerical Mathematics and Scientific Computation), Clarendon Press • Kendall E. Atkinson , An Introduction to Numerical Analysis, Wiley India Private Limited • Gupta Dey , Numerical Methods , McGraw Hill Education; • Numerical Methods & Analysis – Engineering App – Google Play store 107 CU IDOL SELF LEARNING MATERIAL (SLM)

• https://en.wikibooks.org/wiki/Statistics/Numerical_Methods/Numerical_Comparison_of_Stati stical_Software UNIT 5- NUMERICAL DIFFERENTIATION AND INTEGRATION: Structure 5.0 Learning Objective 5.1 Introduction 5.2 Differentiation formulae based on polynomial fit 5.3 Pitfalls in differentiation 5.4 Trapezoidal Rules 5.5 Simpson's rules 5.6 Gaussian Quadrature. 5.7 Summary 5. 8 Keywords 5.9 Learning Activity 5.10 Unit End Questions 5.11 References 5.0 LEARNING OBJECTIVE After studying this unit, you will be able to: • Explain the Differentiation formulae based on polynomial fit • Comprehend the Trapezoidal Rules, Simpson's rules and Gaussian Quadrature. 5.1 INTRODUCTION Differentiation and integration are basic mathematical operations with a wide range of applications in various fields of science and engineering. Simple continuous algebraic or transcendental functions can be easily differentiated or integrated directly. However at times there are complicated continuous functions which are tedious to differentiate or integrate directly or in the case of experimental data, where tabulated values of variables are given in discrete form, direct methods of calculus are not applicable. In this chapter, we develop ways to approximate the derivatives of function, when only data points are given and also to integrate definite integrals by splitting the area under the curve in specified ways. 108 CU IDOL SELF LEARNING MATERIAL (SLM)

5.2 DIFFERENTIATION FORMULAE BASED ON POLYNOMIAL FIT: Numerical Differentiation: Numerical differentiation is the process of computing the value of the derivative of an explicitly unknown function, with given discrete set of points (xi, yi) , i = 0, 1, 2, 3, …, n. To differentiate a function numerically, we first determine an interpolating polynomial and then compute the approximate derivative at the given point. If xi’s are equispaced i. Newton's forward interpolation formula is used to find the derivative near the beginning of the table. ii. Newton's backward interpolation formula is used to compute the derivation near the end of the table. iii. Stirling’s formula is used to estimate the derivative near the centre of the table. If ’s is not equispaced, we may find using Newton’s divided difference method or Lagrange’s interpolation formula and then differentiate it as many times as required Derivatives Using Newton’s Forward Interpolation Formula: Newton’s forward interpolation formula for the function y = f(x) is given by 109 CU IDOL SELF LEARNING MATERIAL (SLM)

Derivatives Using Newton’s Backward Interpolation Formula Newton’s backward interpolation formula for the function y = f(x) is given by 110 CU IDOL SELF LEARNING MATERIAL (SLM)

Derivatives Using Stirling’s Interpolation Formula Stirling’s central difference interpolation formula (taking x0 as the middle value of the table) is given by: Derivatives of Polynomial with Unequispaced xi’s: In case where xi’s are not equispaced in a given data, the polynomial y =f(x) may be found using Newton’s divided difference method or Lagrange’s interpolation formula and then direct differentiation may be applied. Remark: In case derivative has to be found at a point, whose value needs to be interpolated, then first apply applicable interpolation technique and then differentiate the function. In all the cases irrespective of data points being equispaced or not, the y= f(x) polynomial may be found using the applicable interpolation formulae and then direct differentiation can be done using usual calculus techniques. Example 1 Given a cubic polynomial with following data points 111 CU IDOL SELF LEARNING MATERIAL (SLM)

Solution: Derivative has to be evaluated near the starting of the table, thereby constructing forward difference table for the function y = f(x) 112 CU IDOL SELF LEARNING MATERIAL (SLM)

Example 2: Find Solution using Newton's Forward Difference formula x f(x) 01 10 21 3 10 x = -1 Solution: The value of table for x and y x012 3 y101 10 Newton's forward difference interpolation method to find solution Newton's forward difference table is 113 CU IDOL SELF LEARNING MATERIAL (SLM)

xy Δy Δ2y Δ3y 01 -1 6 1 2 10 9 8 21 3 10 The value of x at you want to find the f(x):x=-1 h = x1 - x0 = 1- 0 = 1 p= = = -1 Newton's forward difference interpolation formula is y (-1) = 1 + 1 + 2 - 6 114 y (-1) = -2 Solution of newton's forward interpolation method y (-1) = -2 Example 3: Find Solution using Newton's Backward Difference formula x f(x) CU IDOL SELF LEARNING MATERIAL (SLM)

1891 46 1901 66 1911 81 1921 93 1931 101 x = 1925 Solution: The value of table for x and y x 1891 1901 1911 1921 1931 y 46 66 81 93 101 Newton's backward difference interpolation method to find solution Newton's backward difference table is x y ∇y ∇2y ∇3y ∇4y 1891 46 20 1901 66 -5 15 2 1911 81 -3 -3 12 -1 1921 93 -4 8 1931 101 The value of x at you want to find the f(x):x=1925 115 CU IDOL SELF LEARNING MATERIAL (SLM)

h = x1 - x0 = 1901 - 1891=10 p= = = -0.6 Newton's backward difference interpolation formula is y (1925) = 101 -4.8 + 0.48 + 0.056 + 0.1008 y (1925) =96.8368 Solution of newton's backward interpolation method y (1925) = 96.8368 Example 4: Find Solution using Newton's Backward Difference formula x f(x) 01 10 21 3 10 x=4 Solution: The value of table for x and y x012 3 y101 10 116 CU IDOL SELF LEARNING MATERIAL (SLM)

Newton's backward difference interpolation method to find solution Newton's backward difference table is xy ∇y ∇2y ∇3y 01 -1 6 10 1 2 9 8 21 3 10 The value of x at you want to find the f(x): x = 4 h = x1 - x0 = 1 – 0 = 1 p= = =1 Newton's backward difference interpolation formula is y (4) = 10 + 9 + 8 + 6 y (4) = 33 117 CU IDOL SELF LEARNING MATERIAL (SLM)

Solution of newton's backward interpolation method y (4) = 33 5.3 PITFALLS IN DIFFERENTIATION • Numerical differentiation accumulates error. • For second- and higher-order derivatives, and often, for cross-derivatives, the error can become substantial. Numerical Integration Numerical Integration is the process of computing the value of definite integral , when the integrand function y = f(x) is given as discrete set of points (xi, yi), i = 0, 1, 2, 3, …, n. As in case of numerical differentiation, here also the integrand y = f(x) is first replaced with an interpolating polynomial, and then it is integrated to compute the value of the definite integral. This gives us 'quadrature formula' for numerical integration. Newton Cotes Quadrature Formula For an explicitly known function y = f(x) , let take values y0, y1, y2, …, yn, for taking values x0, x1, x2, …, xn, where xi’s are equispaced. 118 CU IDOL SELF LEARNING MATERIAL (SLM)

5.4 NUMERICAL INTEGRATION USING TRAPEZOIDAL RULE: If we put n= 1 in Newton’s Cote’s quadrature formula given by (1) , we get the curve through (x0, y0) and (x1, y1) as a straight line and being linear equation in x, 2nd and higher order differences are zero. 119 CU IDOL SELF LEARNING MATERIAL (SLM)

Example 1: Find Solution using Trapezoidal rule x f(x) 0.0 1.0000 0.1 0.9975 0.2 0.9900 0.3 0.9776 0.4 0.8604 Solution: The value of table for x and y x0 0.1 0.2 0.3 0.4 y1 0.9975 0.99 0.9776 0.8604 Using Trapezoidal Rule ∫y dx = [y0 + y4 + 2(y1 + y2 +y3)] ∫y dx = [1+0.8604+2× (0.9975+0.99+0.9776)] ∫y dx = [1+0.8604+2× (2.9651)] ∫y dx=0.38953 Solution by Trapezoidal Rule is 0.38953 Example 2: Find Solution of an equation 1/x using Trapezoidal rule, where x1 = 1 and x2 = 2, Step value (h) = 0.25 Solution: Equation is f(x)= . 120 CU IDOL SELF LEARNING MATERIAL (SLM)

The value of table for x and y x1 1.25 1.5 1.75 2 y1 0.8 0.6667 0.5714 0.5 Using Trapezoidal Rule ∫y dx = [y0 + y4 + 2(y1 + y2 + y3)] ∫y dx = [1+0.5+2× (0.8+0.6667+0.5714)] ∫y dx = 0.252[1+0.5+2× (2.0381)] ∫y dx = 0.697 Solution by Trapezoidal Rule is 0.697 5.5 Numerical Integration Using Simpson’s One-Third Rule: If we put n= 2 in Newton’s Cote’s quadrature formula given by (1) , we get the curve through the points (x0, y0) (x1, y1) and (x2, y2) , as a parabolic figure and being quadratic equation in x , 3rd and higher order differences are zero 121 CU IDOL SELF LEARNING MATERIAL (SLM)

This is known as Simpson’s one-third rule to evaluate , where the function y = f(x) is given as discrete set of points (xi, yi), i = 0,1, 2, 3, …, n. NUMERICAL INTEGRATION USING SIMPSON’S THREE- EIGHTH RULE If we put n = 3 in Newton’s Cote’s quadrature formula given by (1) , we get the curve through the points (x0, y0) (x1, y1) , (x2, y2) and (x3, y3) as a cubic polynomial and hence 4th and higher order differences are zero. Newton’s Cote’s quadrature formula reduces to: 122 CU IDOL SELF LEARNING MATERIAL (SLM)

This is known as Simpson’s three-eighths rule to evaluate , where the function y = f(x) is given as discrete set of points (xi, yi), i = 0,1, 2, 3, …, n. Remarks: • Simpson’s rules ideally returns more accurate results compared to trapezoidal rule provided h is small, less than one essentially. • Simpson’s 1/3 rule requires odd number of points (even number of subintervals) for application. Simpson’s 3/8 rule requires number of sub-intervals to be multiple of 3. Examples 1. Find Solution using Simpson's 1/3 rule x f(x) 0.0 1.0000 0.1 0.9975 0.2 0.9900 0.3 0.9776 0.4 0.8604 Solution: The value of table for x and y x0 0.1 0.2 0.3 0.4 0.8604 y 1 0.9975 0.99 0.9776 Using Simpsons 1/3 Rule ∫y dx = [(y0 +y4) + 4(y1+y3) + 2(y2)] ∫y dx = [(1+0.8604) + 4× (0.9975+0.9776) + 2× (0.99)] 123 CU IDOL SELF LEARNING MATERIAL (SLM)

∫y dx = [(1+0.8604) + 4× (1.9751) + 2 × (0.99)] ∫y dx = 0.39136 Solution by Simpson's 1/3 Rule is 0.39136 Example 2. Find Solution of an equation 1/x using Simpson's 1/3 rule, where x1 = 1 and x2 = 2 Step value (h) = 0.25 Solution: Equation is f(x)= . The value of table for x and y x1 1.25 1.5 1.75 2 y1 0.8 0.6667 0.5714 0.5 Using Simpsons 1/3 Rule ∫y dx = [(y0 + y4) + 4(y1+y3) + 2(y2)] ∫y dx = [(1+0.5) + 4 × (0.8+0.5714) + 2 × (0.6667)] ∫y dx = [(1+0.5) +4× (1.3714) +2 × (0.6667)] ∫y dx = 0.6933 Solution by Simpson's 1/3 Rule is 0.6933 Example 3: Find Solution using Simpson's 3/8 rule 124 CU IDOL SELF LEARNING MATERIAL (SLM)

x f(x) 0.0 1.0000 0.1 0.9975 0.2 0.9900 0.3 0.9776 0.4 0.8604 Solution: The value of table for x and y x0 0.1 0.2 0.3 0.4 y1 0.9975 0.99 0.9776 0.8604 Using Simpson's 3/8 Rule ∫y dx = [(y0 + y4) + 2(y3) + 3(y1+y2)] ∫y dx = [(1+0.8604) +2×(0.9776) + 3×(0.9975+0.99)] ∫y dx = [(1+0.8604) + 2×(0.9776) + 3×(1.9875)] ∫y dx = 0.36668 Solution by Simpson's 38 Rule is 0.36668 Example 4: Find Solution of an equation 1/x using Simpson's 3/8 rule where x1 = 1 and x2 = 2, Step value (h) = 0.25 Solution: Equation is f(x) = 125 CU IDOL SELF LEARNING MATERIAL (SLM)

The value of table for x and y x1 1.25 1.5 1.75 2 y1 0.8 0.6667 0.5714 0.5 Using Simpson's 3/8 Rule ∫y dx = [(y0+y4)+2(y3)+3(y1+y2)] ∫y dx = [(1+0.5)+2×(0.5714)+3×(0.8+0.6667)] ∫y dx = [(1+0.5)+2×(0.5714)+3×(1.4667)] ∫y dx = 0.6603 Solution by Simpson's 38 Rule is 0.6603 126 CU IDOL SELF LEARNING MATERIAL (SLM)

127 CU IDOL SELF LEARNING MATERIAL (SLM)

5.6 GAUSSIAN QUADRATURE: When approximate , nodes ������0, ������1, ⋯, ������������ in [������, ������] do not need to be equally spaced. This can lead to the greatest degree of precision (accuracy) Here ������1, ⋯, ������������ and ������1, ⋯, ������������ are 2������ parameters. We therefore determine a class of polynomials of degree at most 2������ − 1 for which the quadrature formulas have the degree of precision less than or equal to 2������ − 1. Gaussian quadrature on arbitrary intervals 128 CU IDOL SELF LEARNING MATERIAL (SLM)

5.7 SUMMARY Numerical Differentiation concept is used in Velocity and acceleration of a moving object • Current, power, temperature, and velocity gradients • Rates of growth and decay in a population • Marginal cost and marginal profits in economics, etc. Numerical integration has numerous practical applications in the field of calculus. Simpson’s rule due to its ease in application and higher accuracy is a preferred method. We can use numerical integration to estimate the values of definite integrals when a closed form of the integral is difficult to find or when an approximate value only of the definite integral is needed. The most commonly used techniques for numerical integration are the midpoint rule, trapezoidal rule, and Simpson’s rule. The midpoint rule approximates the definite integral using rectangular regions whereas the trapezoidal rule approximates the definite integral using trapezoidal approximations. 129 CU IDOL SELF LEARNING MATERIAL (SLM)

Simpson’s rule approximates the definite integral by first approximating the original function using piecewise quadratic functions. 5.8 KEYWORDS: • Numerical Integration: Numerical Integration is the process of computing the value of definite integral , when the integrand function y = f(x) is given as discrete set of points (xi, yi), i = 0, 1, 2, 3, …, n. • Numerical differentiation is the process of computing the value of the derivative of an explicitly unknown function, with given discrete set of points • Simpson's rule : In numerical analysis, Simpson's rule is a method for numerical integration, the numerical approximation of definite integrals • Trapezoidal rule: In mathematics, and more specifically in numerical analysis, the trapezoidal rule (also known as the trapezoid rule or trapezium rule) is a technique for approximating the definite integral. The trapezoidal rule works by approximating the region under the graph of the function as a trapezoid and calculating its area. • Arbitrary Interval: not representing any specific value. 5.9 LEARNING ACTIVITY 1: Given a polynomial with following data points: 2. 130 CU IDOL SELF LEARNING MATERIAL (SLM)

5.10 UNIT END QUESTIONS A. Descriptive Type Questions 1. Discuss Differentiation formulae based on polynomial fit 2. Explain Pitfalls in differentiation 3. State and explain Newton Cotes Quadrature Formula 4. Explain Simpson’s 3/8 th rule 5. Write a note on Gaussian Quadrature B. Multiple Choice Questions 1. Find the area of the traverse using Simpson’s rule if d= 12 m and the values of ordinates are 2.25m, 1.46m, 3.23m, 4.46m. a) 116.88 sq. m b) 161.88 sq. m c) 611.88 sq. m d) 169.54 sq. m 2. The total number of ordinates present must be_ a) Real numbers b) Complex c) Even d) Odd 3. The results obtained are greater than which among the following? 131 a) Prismoidal rule b) Trapezoidal rule c) Rectangular rule d) Square rule 4. Which of the following indicates the formula for Simpson’s rule? a) Δ = (d/3)*((O0+On) + 4*(O1+O3+……..) + 2*(O2+O4+.............)) b) Δ = (d/3)*((O0+On) + 2*(O1+O3+……..) + 2*(O2+O4+ ............ )) c) Δ = (d/3)*((O0+On) + 4*(O1+O3+……..) + 2*(O2+O4+.............)) d) Δ = (d/3)*((O0+On) + 2*(O1+O3+……..) + 4*(O2+O4+ ............ )) CU IDOL SELF LEARNING MATERIAL (SLM)

5. In which of the following cases, Simpson’s rule is adopted? a) When straights are perpendicular b) When straights are parallel c) When straights form curves d) When straights form parabolic arcs Answers: 1 - b; 2 – d ; 3 - b ; 4 -a ; 5 - b; 5.11 REFERENCES ▪ Rajaraman V., Computer Oriented Numerical Method. New Delhi: Prentice Hall. ▪ Salaria R.S.A, Textbook of Statistical and Numerical Methods in Engineering, Delhi: Khanna Book Publishing Company. ▪ Gupta S.P. and Kapoor, V.K. (2014). Fundamentals of Mathematical Statistics. Delhi: Sultan Chand and Sons. ▪ Anderson (1990). Statistical Modelling. New York: McGraw Publishing House. ▪ Graybill (1990). Introduction to Statistics. New York: McGraw Publishing House. ▪ Kendall E. Atkinson , An Introduction to Numerical Analysis, Wiley India Private Limited ▪ Numerical Methods & Analysis – Engineering App – Google Play store ▪ https://en.wikibooks.org/wiki/Statistics/Numerical_Methods/Numerical_Comparison_of_Statistic al_Software 132 CU IDOL SELF LEARNING MATERIAL (SLM)

133 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 6- INTERPOLATION AND APPROXIMATION 1: Structure 6.0 Learning Objective 6.1 Introduction 6.2 Polynomial interpolation 6.3 Difference tables 6.4 Inverse interpolation 6.4.1 Lagrange’s Inverse Interpolation Formula 6.5 Summary 6.6 Keywords 6.7 Learning Activity 6.8 Unit End Questions 6.9 References 6.0 LEARNING OBJECTIVE After studying this unit, you will be able to: • State the concept of Polynomial interpolation • Comprehend the Difference tables • Understand the Inverse interpolation, 6.1 INTRODUCTION A method for approximating or precisely finding some quantity by known individual values of it or of other quantities related to it. On the basis of interpolation a whole series of approximate methods for solving mathematical problems has been developed. Most significant in numerical mathematics is the problem of constructing means for the interpolation of functions. The interpolation of functional and operators is also widely used in constructing numerical methods. An interpolating polynomial passes through all the data points. A polynomial of order n passes through n data points. Example: Lagrange’s interpolation formula Lagrange's Interpolation Formula An approximating polynomial does not necessarily pass through all the data points. Here the order of the fitted polynomial is much less than the number of data points. The coefficients of the polynomial are determined by applying some principle like minimization of sum of squares of errors (Least squares criteria). Regression lines and curves come under this category. 134 CU IDOL SELF LEARNING MATERIAL (SLM)

6.2 POLYNOMIAL INTERPOLATION Since linear interpolation is not adequate unless the given points are closely spaced, we consider higher order interpolating polynomials. Let f(x) be given at the selected sample of (n + 1) points: x0 < x1 < · · · < xn, i.e., we have (n+1) pairs (xi, fi), i = 0, 1, 2, . . ., n. The objective now is to find the lowest degree polynomial that passes through this selected sample of points. Figure 6.1: Interpolating the function f(x) by a polynomial of degree n, Pn(x). Consider the nth degree polynomial We wish to determine the coefficients aj , j = 0, 1, . . . , n, such that These (n + 1) conditions yield the linear system 135 CU IDOL SELF LEARNING MATERIAL (SLM)

The matrix V is known as the Vandermonde matrix. It is non-singular with nonzero determinant For n = 3, for example, Hence a can be uniquely determined as a = V −1 f. Another proof of the uniqueness of the interpolating polynomial can be given as follows. Theorem: Uniqueness of interpolating polynomial. Given a set of points x0 < x1 < · · · < xn, there exists only one polynomial that interpolates a function at those points. Proof: Let P(x) and Q(x) be two interpolating polynomials of degree at most n, for the same set of points x0 < x1 < · · · < xn. Also, let R(x) = P(x) − Q(x). Then R(x) is also a polynomial of degree at most n. Since P(xi) = Q(xi) = fi, we have, R(xi) = 0 for i = 0, 1, . . ., n. In other words R(x) has (n + 1) roots. From the Fundamental Theorem of Algebra however, R(x) cannot have more than n roots. A contradiction! Thus, R(x) ≡ 0, and P(x) ≡ Q(x). Example 1: Given the following table for the function f(x), obtain the lowest degree interpolating polynomial. 136 CU IDOL SELF LEARNING MATERIAL (SLM)

Solution: Since the number of nodes = 3 = n + 1, therefore n = 2. Let that satisfies the following conditions at the points x0 = 1; x1 = 2, x2 = 4: Using Gaussian elimination with partial pivoting, we compute the solution Therefore, the interpolating polynomial is given by P2(x) = −4 − 2x + x2. We can use this approximation to estimate the root of f(x) that lies in the interval [2, 4]: Example 2: Suppose that f(x)f(x) is a polynomial of degree 2 with f (1) =2, f (2) =5, and f (4) =2. Find the formula of f(x) SOLUTION: Since f(x)f(x) has degree 2, it must be of the form f(x)=a+bx+cx2, where the coefficient a, b, c is to be determined. Since f (1) =2, 2= a + b×1 +c×12 = a + b + c. Similarly, we get two other equations: 5 = a + 2b + 4c 137 2 = a + 4b +16c CU IDOL SELF LEARNING MATERIAL (SLM)

Solving all the three equations together we get a=−4, b=15/2, c=−3/2. In this example we say that f interpolates the three points (1,2), (2,5) and (4,2). We also call f an interpolating polynomial for this set of 3 points. 6.3 DIFFERENCE TABLE Newton Divided Difference Table: It may also be noted for calculating the higher order divided differences we have used lower order divided differences. In fact, starting from the given zeroth order differences f(xi); i = 0, 1, …, none can systematically arrive at any of higher order divided differences. For clarity the entire calculation may be depicted in the form of a table called Again suppose that we are given the data set (xi, fi) and that we are interested in finding the 5th order Newton Divided Difference inter polynomial. Let us first construct the Newton Divided Difference Table. Wherein one can clearly see how the lower order differences are used in calculating the higher order Divided Differences: 138 CU IDOL SELF LEARNING MATERIAL (SLM)

Example 1: Construct the Newton Divided Difference Table for generating Newton interpolation polynomial with the following data set: Solution: Here n= 5. One can fit a fourth order Newton Divided Difference interpolation polynomial to the given data. Let us generate Newton Divided Difference Table; as requested. Note: One may note that the given data corresponds to the cubic polynomial . To fit such a data order polynomial is adequate. From the Newton Divided Difference table we notice that the fourth order difference is zero. Further the divided differences in the table can be directly used for constructing the Newton Divided Difference interpolation polynomial that would fit the data. Example 2: Find Solution using Newton's Divided Difference Interpolation formula 139 CU IDOL SELF LEARNING MATERIAL (SLM)

x f(x) 300 2.4771 304 2.4829 305 2.4843 307 2.4871 x = 301 Solution: The value of table for x and y x 300 304 305 307 y 2.4771 2.4829 2.4843 2.4871 Numerical divided differences method to find solution Newton's divided difference table is x y 1st order 2nd order 300 2.4771 0.00145 304 2.4829 0 0.0014 305 2.4843 0 0.0014 307 2.4871 The value of x at you want to find the f(x):x = 301 140 Newton's divided difference interpolation formula is CU IDOL SELF LEARNING MATERIAL (SLM)

f(x)= y0 + (x - x0) f[x0, x1] + (x - x0)(x - x1)f[x0, x1, x2] y(301) =2.4771+(301-300)×0.00145+(301-300)(301-304)×0 y(301) =2.4771+(1)×0.00145+(1)(-3)×0 y(301) =2.4771+0.00145+0 y(301) =2.47858 Solution of divided difference interpolation method y(301)=2.47858 Example 3: Find Solution using Newton's Divided Difference Interpolation formula x f(x) 2 0.69315 2.5 0.91629 3 1.09861 x = 2.7 Solution: The value of table for x and y x 2 2.5 3 y 0.69315 0.91629 1.09861 Numerical divided differences method to find solution Newton's divided difference table is 141 CU IDOL SELF LEARNING MATERIAL (SLM)

x y 1st order 2nd order 2 0.69315 0.44628 2.5 0.91629 -0.08164 0.36464 3 1.09861 The value of x at you want to find the f(x):x = 2.7 Newton's divided difference interpolation formula is f(x) = y0 + (x - x0) f [x0, x1] + (x - x0) (x - x1) f[x0, x1, x2] y(2.7) = 0.69315+(2.7-2)×0.44628+(2.7-2)(2.7-2.5)× -0.08164 y(2.7) = 0.69315+(0.7)×0.44628+(0.7)(0.2)×-0.08164 y(2.7) = 0.69315+0.312396-0.01143 y(2.7) = 0.994116 Solution of divided difference interpolation method y(2.7) = 0.994116 6.4 INVERSE INTERPOLATION, Sometimes we have to find the value of x for a given values of y not in the table. This reverse process is known as inverse interpolation. Thus, inverse interpolation is defined as the process of finding the value of the argument corresponding to a given value of the function lying between two tabulated functional values. 6.4.1 Lagrange’s Inverse Interpolation Formula Whether the arguments are equally spaced or not, the entries are always unequally spaced. 142 So, Lagrange’s formula is the natural choice, because Lagrange’s formula is merely a relation between two variables, either of which may be chosen as the independent variable. CU IDOL SELF LEARNING MATERIAL (SLM)

Given a set of values (x1,y1), (x2, y2), …, (xn, yn) treating y as the independent variable and x as the dependent variable we have the inverse form of Lagrange’s formula Example 1: If Find correct to two decimals the value of x for which Ux = 1001. Solution Let y = Ux Given x0 = 2, x1 = 3, x2 = 5 andy0 = 113, y1 = 286, y2 = 613 Required the value of x when y = 1001 143 CU IDOL SELF LEARNING MATERIAL (SLM)

Lagrange’s inverse interpolation formula is When y = 1001, we get ∴ the value of x correct to 2 places of decimals is 7.56 Example 3: Use Lagrange’s formula inversely to obtain the value of t when A = 85 from the following table. Solution 144 Let us take t = x and A = y and Lagrange’s inverse interpolation formula is CU IDOL SELF LEARNING MATERIAL (SLM)

When y = 85, we get 145 CU IDOL SELF LEARNING MATERIAL (SLM)

∴ when A = 85, Example 4: Apply Lagrange’s formula inversely to obtain the root of the equation given that and f(42) =18. Solution Let The given values of x are x0 = 30, x1 = 34, x2 = 38, x3 = 42 and the corresponding values of y are y0 = −30, y1 = −13, y2 = 3, y3 = 18 Required the value of x when y = 0 Lagrange’s inverse interpolation formula is When y = 0, we get 146 CU IDOL SELF LEARNING MATERIAL (SLM)

∴ the root of the equation is x = 37.23 6.5 SUMMARY Interpolation is an estimation of a value within two known values in a sequence of values. Divided differences are a recursive division process. The method can be used to calculate the coefficients in the interpolation polynomial in the Newton form. Newton’s divided difference interpolation formula is an interpolation technique used when the interval difference is not same for all sequence of values. Making use of forward difference operator and forward difference table (will be defined a little later) this scheme simplifies the calculations involved in the polynomial approximation of functions which are known at equally spaced data points Inverse Interpolation is often used to check whether the correctness of output y for an unknown function f i.e., how much argument x for this output y differs from the original input. We understood the concept of interpolating polynomial and difference table. 6.6 KEYWORDS • Interpolation: is a statistical method by which related known values are used to estimate an unknown price or potential yield of a security • An approximation: is anything that is similar, but not exactly equal, to something else. A number can be approximated by rounding • Polynomial interpolation: In numerical analysis, polynomial interpolation is the interpolation of a given data set by the polynomial of lowest possible degree that passes through the points of the dataset. • Inverse interpolation: is defined as the process of finding the value of the argument corresponding to a given value of the function lying between two tabulated functional values. • Difference Table: an auxiliary table to facilitate interpolation between the numbers of the principal table giving approximate differences in values of the tabulated function 147 CU IDOL SELF LEARNING MATERIAL (SLM)

corresponding to certain submultiples (such as tenths) of the constant smallest increment of the independent variable in the table. 6.7 LEARNING ACTIVITY 1. Using Newton divided difference interpolation polynomial, construct polynomials of degree two and three for the following data: (1) f (8.1) = 16.94410, f (8.3) =17.56492, f (8.6) = 18.50515, f (8.7) = 18.82091. Also, approximate f (8.4). 2. Use Lagrange’s formula inversely to obtain the value of t when A = 85 from the following table. 6.8 UNIT END QUESTIONS A. Descriptive type Questions 1. What is Polynomial Interpolation 2. State and prove Uniqueness of interpolating polynomial. 3. What is Newton Divided Difference Table? 4. What do you understand by inverse interpolation? 5. Apply Lagrange’s formula inversely to obtain the root of the equation f(x) = 0 given that f(30) = -30, f(34) = -13 , f(38) = 3 and f(42) = 18 B. Multiple Choice Questions 1. Given n+1 data pairs, a unique polynomial of degree passes through the n + 1 data points. 148 CU IDOL SELF LEARNING MATERIAL (SLM)

2. 3. The Lagr ange polynomial that passes through the 3 data points is given by 4. The following data of the velocity of a body is given as a function of time. If you were going to use quadratic interpolation to find the value of the velocity at seconds, what three data points of time would you choose for interpolation? 9.14=t (A) 0, 15, 18 (B) 15, 18, 22 (C) 0, 15, 22 149 CU IDOL SELF LEARNING MATERIAL (SLM)