Interpolation part-III (Newton’s Forward/Backward difference and derivation of error)

Welcome to the lecture series of numerical methods and till now we have discussed about this finite difference operator. So now we will continue about this Central difference table and we will start about this Central difference approximation how we can use for different values here So in the tabular form if you will just write this Central difference table here, the Central difference can be written as if I will just write i as the value here that is 0, 1, 2, 3, 4 here and there respected tabular values are like x i then I can just write this tabular point as x 0, x 1, x 2, x 3, x 4, here and associated variables values like y 0, y 1, y 2, y 3, y 4, here then the Central difference approximates that delta of y i as since we are just expressing delta of f of x as f of x plus h by 2, minus f of x minus h by 2 I can just write delta of y of r as y of r plus half minus y of r minus half here. So if I am just expressing this one in this form then I can write this post approximation as Delta of y of half here, then 2nd approximation I can just write since you are just considering the average of this 2 here. So first average if I will just consider 1 plus 0 by 2, since delta of y of r means Delta of y of half here, so delta of y of half means y of half plus half this will just give you y of 1 minus y of half minus half means this will just give you y 0 there So that is why we if you are just taking the difference of this 2 here then we can just write that as delta of y of half here. If you will just take the difference of y 2 minus y of 1, I can just write delta of y 3 by 2 here and for y 3 minus y 2, I can just write delta y of 5 by 2 here. If I will just take the difference of these two I can just write delta of y 7 by 2, since delta of y of 3 by 2 I can just write this one as in the form of y of 3 by 2 plus half minus y of 3 by 2 minus half here. So it can be written as y of 3 plus 1 by 2 here minus y of 3 minus 1 by 2 here, so it can be written as y 2 minus y of 1 here So obviously y 2 minus y of 1 it is just written as delta of y of minus 3 by 2 here. Similarly, y of 1 minus y 0 it can be written as delta y of half here, and if you are just taking difference of y 3 minus y 2 it can be represented as delta y of 5 by 2 here. And if you just take the difference of y 4 minus y 3 it can be expressed as delta y of 7 by 2. Again if you will take the difference of this two here, so it can be expressed as delta square of y i and I can just write this one as delta of y of 1 here. Since if you just take the average of y of sorry this is delta square of y of 1 here, if I am just assuming this one this means that delta of delta of y of 1 here So if I will just take delta of y of 1 so delta of y of 1 I can just write as y of 1 minus half sorry plus half minus y of 1 minus half here and it can obviously have written as y of 1 plus half minus delta of y of 1 minus half here. And I can just write this one as Delta of y of 1 plus half sorry I just write this one as y of 1 plus half plus half minus y of 1 plus half minus half here. Similarly, minus it can be written as y of 1 minus half plus half minus y of 1 minus half minus half here, so obviously it can be written as 1 plus 1 this is y 2 minus y 1 since it cancel it out, so directly I can write this one as

y 2 minus y 1 minus y of 1 minus y 0. So if you will just see this delta square of y 1 is nothing but we can just write y 2 minus y 1 minus y 1 minus y 0 here, so obviously this is just coming as del square of y 1 here Similarly, we can just write this difference of this 2 as del square of y 2 and the difference of this two we can just write delta square of y 3 here. If you will just take the difference of again this 2 here so it can be written in the form of del cube of y I here, so i can just write this one as del cube of y 3 by 2 and this one can be written as delta cube of y 5 by 2 here. If I will take one more difference here that is del to the power 4 y i, so then i can just write del to the power 4 of y 2 here. Since if you are just taking this central difference form here, so the values are associated here as 0, 1, 2, 3, 4 and the central value is taking as 2 here. So that is why the final form the central difference approximates the value at the centre of the table only So next we will discuss about this Newton’s forward difference formula, basically we are just using this set of tabular point that is in the form of the x 0, x 1, x 2 up to x n here, and all of this tabular points that is x 0 to x n are equally spaced this means that x 0, x 1, x 2, x 3 likewise we are just writing up to x n here. This means that if all points are equally spaced we can just write x i equals to x i minus 1 plus h here or we can just write this one as x 1 equal to x 0 plus h, x 2 equal to x 1 plus h likewise x n equals to x n minus 1 plus h here And we can just write all this points that is in the form of like x 0, x 1, x 2, x 3 up to x n if these are the given set of tabular points we can just express all this points should be equally spaced, this means that h is the space size in that locations then we can express this associated variables values as y 0, y of 1 up to y n there Then we can express this Newton’s forward difference formula as y of xp this means that any particular point if you want evaluate at any middle of this intervals then we can just write this formula as in the formula y 0 plus P delta of y 0, p into p minus 1 by factorial 2 del square of y 0, so up to p into p minus 1 into p minus 2 up to p minus n minus 1 divided by n factorial and del to the power n y 0 here So basically if you want to evaluate any point within this particular interval then we can just express this point as xp as x 0 plus ph here. And if we want to express this function in the form of a polynomial we can just replace at any point x means we can just replace this p as in the form of x there and we can evaluate this formula in the form of a polynomial there So in a complete form if you want to derive this formula then we can take this Taylor series expansion which is used for this shift operator So if we want to express this Newton’s forward difference formula in the form of the p here this means that Newton’s forward difference formula

can be written as y of xp that is at any point within this interval x 0, x 1 up to x n, if we want to find at any point then we can just write this formula as in the form of y 0, p delta of y 0, p into n minus 1 by factorial 2 del square of y 0 plus upto p into p minus 1 upto p minus n minus 1 by n factorial, delta to the power n of y 0 there Especially if you will just see in a tabular point here this is starting at x 0, x 1, x 2, x 3 upto x n here. So if any point we want evaluate at the beginning of the table we can use Newton’s forward difference formula here. Basically if we are just writing this point as x, this means that x has a coefficient there so that is why we are just expressing that is in the form of x p here. So usually x p can be written as x 0 plus ph since all of these points we are just expressing that is in the form of x i equals to x i minus 1 plus h here And wherever we will just start this competition we have to choose the beginning of the point as x 0 there since this p values should be lies between 0 and 1 here. Especially if you will just consider then we can just evaluate this formula there, this means that if you want to find y of xp in a functional form here, we can just write this one as y of x 0 plus ph and it can be expressed as E to the power p of y 0 there. And E can be expressed in the form of 1 plus delta here since whenever we are just expressing delta of f of x usually it is written in the form of f of x plus h minus f of x and hence it can be written as E of f of x minus f of x and it can be written as E minus 1 f of x there So delta can be expressed as E minus 1 so that is why we can just write 1 plus delta equals to E there. So that is why we can just replace here E as 1 plus delta whole power p of y 0 here, and if you just expand this term then we can just write this one as 1 plus p delta plus p into p minus 1 by factorial 2 plus p into p minus 1 into p minus 2 by 3 factorial, delta square here, this is cube here, so likewise it will just continue and operated on this y 0 value. So I can just write this values as y 0 plus p delta of y 0 plus p into p minus 1 by 2 factorial del square of y 0 likewise I can just express And if I want to evaluate this function in a polynomial form that is in the form of x there I can just express this as I can express this p in the form of hear since x is expressed xp is expressed as x 0 plus ph hear. So this xp is nothing but any point which is existing within this interval x 0, x 1, x 2 upto x n, in any of this intervals so this xp is situated So commonly we can just consider this point as x there, so which can be expressed as x 0 plus ph and I can just write p as x minus x 0 by h there. Similarly, if I want to write p minus 1 this can be written as x minus x 0 by h minus 1 here and which can be written as x minus x 0 minus h by h here, where I can just write x minus x 1 by h here, since x 1 can be expressed as x 0 plus h here Similarly, I can just write p minus 2 that is in the form of x minus x 2 by h there In each of this formulation I can just express this one in the form of p if i will just replace p in terms of x there I can just obtain a polynomial that is in the form of x there So if it is asked to evaluate any polynomial

which is existing at any point which is existing at the beginning of the table then we can express that as a polynomial of x in Newton’s forward difference formula So this is a Newton’s forward difference formula whatever I have just discussed then we will just go for this Newton’s backward difference formula. In the Newton’s backward difference formula especially we are just using this tabular values at the end of the table only So if you will discuss about Newton’s backward difference formula, especially if the set of tabular points are expressed in the form of x 0, x 1, x 2 up to x n and the corresponding associated values are y 0, y 1, y 2 upto y n and each of these points are equi-spaced, this means that x 0 minus x 1 difference will be h and x 2 minus x 1 difference will be h, then we can just write Newton’s backward difference formula as y of xp as y 0 plus P nabla of y 0, p into p plus 1 by factorial 2, nabla square y 0, p into p plus 1 upto p plus n minus 1 by n factorial, nabla to the power n of y 0 We have to choose y 0 in such a fashion that y 0 should be existing at the end of the table So, previous values can be considered as y of minus 1, y of minus 2 up to y of minus n. Since this value y 0 will exist at the end of the table only and we can express here xp or x as x 0 plus ph the, where p can be written as x minus x 0 by h in that position also. And if we want to express this function in a form of shift operator here this means that y of xp can be written as E power p y 0 here, since xp can be expressed as x 0 plus ph and where we can just write E of xp means E of x 0 plus ph, which can be expressed as E to the power p of x 0 here So since we are just expressing this function that is E of f of xp here or E of xp means it is E of x 0 plus ph, so if you want to express this one that is y as a function of x here that means y of x 0 plus ph here and E is operated on y of p here, so that is why it is written as E to the power p of y 0 this one So that is why if we want to express this one as in the form of E to the power p of y 0 here, so it can be expressed as in the form of nabla here that is usually nabla of f of x is written in the form of f of x minus f of x minus h and it can be expressed as f of x minus E power minus 1 f of x this one, so we I can just write 1 minus E inverse of f of x So this can be written in the form of like nabla equal to 1 minus E inverse or I can just write this one as E inverse equals to 1 minus nabla here, and E can be written as 1 minus nabla whole inverse. So if I will just write here this can be written in the form of 1 minus nabla whole to the power minus p of y 0 and it can be expanded in the form of like 1 plus p nabla plus the into the plus 1 by factorial 2 nabla square, so likewise operated on y 0. So in a combine form I can just write y 0 plus p nabla of y 0 p into p plus 1 by factorial two, nabla square y 0, plus this will just continue So this is the representation for Newton’s backward difference formula and if you just write this is in the form of polynomial here

so then we can just estimate this series as in the form of like p equals to x minus x 0 by h here. So similarly I can just express p plus 1 as p equals to x minus x 0 by h here, so p plus 1 can be written as x minus x 0 by h plus 1 this can be written as x minus x 0 plus h by h here. So I can just write x minus x 0 minus h by h, I can just write x minus x of minus 1 by h this one Similarly, I can just write p plus 2 also there, so p plus 2 can be written as x minus x of minus 2 by h there. And in this form we can just express this as in the form of polynomial that is taking all of this a backward point. So whenever we are just discussing this Newton’s forward difference formula or Newton’s backward difference formula there is always existing a error term there Since whenever we are just writing this series expansion so finally we are ended up this this turns upto n-th term there, so after the n-th term so there will be some extra terms there which we are just neglecting there So if that terms we will just include, so in a complete form we can just write this series expansion as y of x equals to your series expansion that as y of xp plus R n term there that is the remainder term. So in each like Newton’s forward difference formula, backward difference formula always there will be associated error there. So if you want to calculate this error first we will discuss about a generalised approximated formula here So if you just write this error of approximations, so let us consider suppose a function y equals to f of x is existing at k plus 1 point suppose, there is x 0, x 1 up to x k and x k plus 1 points and each of these points this functional values will be associated also like y 0, y 1, y 2, upto y k plus 1 then if y of x is satisfied at exactly this points with a polynomial since we are just discussing this one in a polynomial sincere So y of x is approximated with the p of x at x 0, x 1, x 2 upto x k here, since k plus 1 points are existing then if we will just approximate this function here that is y equals to f of x is a function which is approximated or interpolated with a polynomial p of x here that exactly at this points like x 0, x 1, x 2, upto x k point at each of this points the difference between this y equal to f of x and p of x is exactly 0, but at all other points we can just find a difference is existing So if this difference is existing then there will be a error term is associated with each of this function and the polynomial whenever we are just approximating them in a polynomial sense here. So if we will just write this in complete form, so y of x can be written as p of x plus r of x term here. So usually this y of x and p of x exactly equals at each of the nodal points or tabular points, but at all other points we have exist a difference between this y of x and p of x where R of x is existing So if we will just write here R of x as in the form of like Kx into W of x, since at all this tabular points we are just approximating that f of x equals to P of x there, y equal to f of x. So if exactly it will be equal at this point so this functions should be 0 at exactly this points also, so that is why we can just express this Rx as in the form of Kx into W of x, where W of x will be associated with these term like x minus x 0, x minus x 1, x minus x 2 upto x minus x k, where we can just satisfy y of x i equals to P of x i plus R of x i But if we will just approximate this function exactly at this point we can just consider a point which is existing within this interval suppose x bar at that point this function is also satisfying that x bar value. So if you will just consider that function as x

bar value, so we can just choose Kx as Kx bar at that point exactly that K of x bar equal to f of x bar minus P of x bar by W of x bar. Since at that point these values will not satisfy, maybe that point lies here or here, or here, somewhere else it may lies, since exactly at this point we are just observing that y of x, P of x and W of x takes 0 value We are just considering x bar as a point within this interval somewhere that should satisfy the value that is in the form of K of x bar equals to f of x bar minus P of x bar by W of x bar the. So we can just approximate this function that at that point exactly f of x equals to P of x plus W of x into K of x bar, so where we can just write this remainder term R of x as W of x into K of x bar So if we want to determine the value of Kx bar let us consider this function that s Phi of x equal to f of x minus P of x minus f of x bar minus P of x bar by W of x bar into W of x, since W of x takes the value that exactly f of x and P of x are satisfied at x 0, x 1 up to x n there. So if these are the K plus 1 points where Phi of x satisfies these value then we can just assume that Phi of x will be satisfied 0 value at K plus 2 points, since x bar is the extra point there So if x bar is the extra point and x 0, x 1 up to x k plus 1 points then phi function will satisfy zero value at K plus 2 points So if you will just consider in a polynomial sense that satisfying rules theorem, Phi of x will vanish at K plus 2 points then phi dash x must vanish at K plus 1 points. Similarly, if we just go ahead we can just find that Phi of K plus 1 will vanish at one point only suppose that point is zeta suppose Since P of x is a polynomial of highest degree k, so it will take K plus 1-th degree of derivative P of x will also be 0, similarly f of x will also be 0 at that point. But Phi of k plus 1 since at least at one point the K plus 1-th derivative phi function that will give also 0 function there so that is we can just write Phi of k plus 1 zeta equals to 0. So then we can just express f of x bar minus P of x bar by W of x bar this equals to f to the power K plus 1 zeta by K plus 1 factorial So if you just compare both easy questions that is expressed as a question 4 and a question seven we can just get that K of x bar can be expressed as f to the power K plus 1 zeta by K plus 1 factorial. In a complete sense if you want to write this function or this remainder term, so R of x can be expressed in the form of W of x into f to the power K plus 1 zeta by K plus 1 factorial hear So if I am just write here R of x this can be written as W of x into f to the power k plus 1 zeta by K plus 1 factorial here, where zeta should be lies between x 0 to x k here And W of x term is written in the form of x minus x 0 x minus x 1 up to x minus x k here into f to the power k plus 1 zeta by k plus 1 factorial here So if we are just expressing this generalised function that is expressed in the form of like x minus x 0, x minus x 1, to x minus x k, into f to the power k plus 1 zeta by k plus 1 factorial here, where zeta should lie between x 0 and x k. So next class will just continue this function that can be expressed at Central difference tabular points and we can just approximate this values in a Central difference approximated form, that Central difference approximation term includes like a Gauss forward difference, difference formula and Vessels formula and Sterling’s formula, that we will just continue in the next lecture