Newton Forward Interpolation

Gregory Newton's is a forward difference formula which is applied to calculate finite difference identity.

1. PRACTICAL Name- Saloni Singhal M.Sc. (Statistics) II-Sem. Roll No: 2046398 Course- MATH-409 L Numerical Analysis Lab Submitted To: Dr. S.C. Pandey 6.2

2. O BJECTIVE Create an M-file to implement Newton Gregory Forward Interpolation . Curve Fitting- Least Square n th order polynomial to data.

3. Theory Then the process of knowing the value of f(x ) for some unknown value of x not explicitly given in the interval [a, b] is called interpolation. The value thus, determined is known as Interpolated value. This Newton Gregory Forward Interpolation formula is particularly useful for interpolating the values of f(x) near the beginning of the set of values given. h is called the interval of difference and u = ( x – a ) / h, Here a is the first term. Error term of the formula:

4. Program clear; %input number of data points n= input('\ enter number of data points=' ); %input abscissa and ordinate value for a=1:n X(a)= input('enter X'+string (a)); end for b=1:n Y(b)= input('enter Y'+string (b)); end %enter the value to be interpolated using forward interpolation x=input( 'enter value of x to be interpolated' ); %step size h and d gives the forward difference table h=X(2)-X(1); for i =1:n-1 d(i,1)=Y(i+1)-Y( i ); end for j=2:n-1 for i =1:n-j d( i,j )=d(i+1,j-1)-d(i,j-1); end end

5. Program Contd. P1= linspace (min(X),max(X),51); P2=zeros(51,1); for i =1:51 P2( i )= nf (P1( i ), X,Y,n,d ); end %plot for the given points plot(X,Y) hold on %plot for the interpoated curve plot(P1,P2) hold off d nf ( x,X,Y,n,d ) % function to calculate the forward inoterpolation function y= nf ( u,X,Y,n,d ) h=X(2)-X(1); p=(u-X(1))/h; prod=1; y=Y(1); for t=1:n-1 prod=prod*(p-t+1)/t; y= y+prod *d(1,t); end end  

6. Time Complexity 6 For the given program it is calculated as: For line 14= 2(n-1) since loop For line 16= (n-1)+1 since loop from 1:n-1 For line 18= 2(n-1)(n-2) for nested loop For line 24= 51(6n-3) since linspace generates 51 values(given) and min/max has time complexity n For line 36= (6n-3) since loop is from i to n-1 on adding the above dominant value is =O(n 2 ) Big O notation is the most common metric for calculating time complexity. It describes the execution time of a task in relation to the number of steps required to complete it.   We calculate the no of operations in respective loops and function. Big ‘O’ notation takes its dominant value

7. Output

8. Plot of the given data points and interpolated curve Reference: — Data Points plot —Interpolated curve

9. Curve Fitting Syntax: p = polyfit ( x,y,n ) returns the coefficients for a polynomial p(x) of degree n that is a best fit (in a least-squares sense) for the data in y. The coefficients in p are in descending powers, and the length of p is n+1

10. Conclusion • The interpolated value of the point is as shown in figure. • Polyfit (order 3) verifies the actual cubic formula for the given set of data points i.e. y= x³+2x-3.

11. Caveats It can be observed that this formula is appropriate when the value to be interpolated ( x s ) lie almost in the beginning of the data table. More explicitly, when x s lies almost in the end of the data table then only first two or three terms of (1) can be taken into consideration to keep | s | < 1. and hence the result will not be sufficiently accurate. To overcome this problem, we go for next formula named Newton’s Backward difference formula.