Lecture 46

So far we have discussed polynomial interpolation that connects n plus 1 points xi yi in two ways. The first way is via inversion of Vandermonde matrix and the second is to use Newton's approximating polynomial. When we interpolate using a polynomial essentially what we do is the calculation of this ai which are the coefficients of the polynomial. We have seen that as we go from this Vandermonde type technique to Newton's technique the calculation of this coefficients become easier. Now we want to stretch ourself and we want to go further such that the calculation of these coefficients are not at all necessary. In fact if the calculation of this coefficient comes down to just getting this f of xi then we can say that f of xi are already known because they are same as the yi so the coefficient calculation is not at all necessary. How can we achieve that? Let's see by discussing the Lagrange interpolating polynomial. So let us think about what we have done so far. We have used a polynomial such as y equals a naught plus a 1x plus a 2x square up to an x to the power n and then we have used Newton's polynomial where we have used y equals b naught plus b 1 x minus x naught b 2 x minus x naught into x minus x 1 etc. Now if you look into it you will see that the standard polynomial that is a naught plus a 1x etc. I can write it as a sum of ai xi i of x and here you can think about that we are representing this function y equals fx as a linear combination of a set of basis functions and this basis functions are psi i of x. In this particular case the basis functions are 1 x x square x cube all the way up to x to the power n. Similarly if I go for Newton's polynomial I can write this expression of Newton interpolating polynomial as a sum of bi phi i of x. That means here also we are having a linear combination of the basis functions and the basis functions here are phi naught equals 1 phi 1 equals x minus x naught and all the way up to phi n that is the product of x minus xi where i goes from 0 to n minus 1. So the idea is that as we leave the technique of inverting Vandermonde matrix and we use interpolating polynomial what we are doing is that we are selecting good quality basis functions. They are good because they help us to get the coefficients easily. So the goal is to select basis function to get the coefficient easily and we want to stretch this to an extent where we don't want to calculate the basis coefficients at all. So we want to design the basis function in an intelligent way so the coefficient calculation will render unnecessary. Now let's see how we can do so. We do so using certain type of interpolating polynomial known as Lagrange polynomial. In Lagrange polynomial the basis functions are L naught of x, L1 of x, Ln of x etc and the coefficients are f of x naught, f of x1 etc all the way up to f of xn which means that we already know this f of x naught, f of x1. They are part of the data set given to us which means that we don't have to calculate the coefficients at all but we have to figure out what are these basis functions. Once again here the basis functions are Li of x for i going from 0 to n and the coefficients are f of xi which are known. So now we have to know this basis function L naught x, L1 x up to Ln x where the coefficients are known and the next part we will see that how we exactly get this Lagrange basis functions L naught, L1 etc. Each of these basis function if you look into it they are essentially a polynomial. This is true for even for the Newton's polynomial or even before that if I take 1 x, x square as the basis function they are also polynomials. So each of these basis function is a polynomial and their degree cannot be greater than n either they are up to n or they will be less than n. That is true for all sorts of interpolation not only Lagrange. Now let's say that we select certain arbitrary x that is xk. It could be one of these points xi, yi but it is not necessary it could be anything. So in this one of this x equals xk some arbitrary value of x and if I write that in terms of Lagrange polynomial, if Lagrange polynomial passes through this point then for x equals xk the value of this function will be L naught xk f x naught L1 xk f x1 etc etc Ln xk f of xn. Please note that the f are fixed here they don't depend on xk at all. f of x naught f of x1 etc these coefficients are known previously as soon as we know this data set xi, yi we know this coefficient f x naught is y naught f x1 is y1 etc. So they are known and we can write this as C ik f of xi where this C ik I write as Li of xk. This is just a symbol and it has no other inherent complexity at least up to now. So you can see that at a given point x equal to xk the value of f what we are getting f at x equal to xk is essentially a linear combination of the different f of x naught x1 etc etc which we have received from the given data. So at any point if we want to find the value of fx what we have to do we have to take a linear combination of this initial f of x and this linear combination will be combined based on the value of L at that xk. This f of x naught x1 xn etc they are of course independent coefficient for instance the value of f of x naught does not depend on value of f of x1 they are independently we have received these values they may be coming from certain experiments that we don't know we don't have to know but we know that they are constant and they are independent of each other they are only the input to find the value of fx at certain arbitrary point x equals xk and until now whatever we have discussed this idea is applicable to all interpolation routines not necessarily only Lagrange's interpolation. Now we move forward we have this x equals xk and we know that at x equals xk we have cik f of xi and this xi's are the measured point here which we have received as a data set probably coming from measurement probably coming from other sources we don't have to know. Now let us do some small tricks what we do is that we will pick up this points xi, yi one by one and we'll put it in this expression that f of x equals xk is cik fxi and let's see what happens. So f at xy will be c0i fx0 c1i fx1 all the way up to cni fxn this c's are coming from here and this xi's are the actual points where we already know the values so we want to repeat this for all i's going from 0 to n so what happens exactly if I let's say we take a case i equals 0 and we know that here xi equals x0 which means that in place of xi I put x0 this will be c00 fx0 c10 fx1 etc etc up to cn0 fxn. Now we know that fx0 is known and it is completely independent of fx1 fx2 etc etc up to fxn which means that in this particular expression the value of fx0 does not depend on fx1 at all or fx2 at all that means that c10 c20 etc etc it must be 0 and c00 here that should be 1. Similarly we can test for i equals 1 that means xi equals x1 and once again I write this expression that is f of x1 equals c01 fx0 c11 fx1 etc up to cn1 fxn and if I use the same argument as before that fx1 does not depend on fx0 or fx2 or any other f for that matter then c01 c21 up to cn1 all will be 0 only c11 will be 1. Now we can generalize this and we can write that cij which is li of xj will be 1 for i equals j and cij that is li of xj will be 0 for i not equal to j. This is very important now and we have to work on this for some time. So now let us concentrate on this that li x equal to xj equals 1 for i equal to j li x equal to xj for 0 for i not equal to j. What does that mean? It means that if I take any of this l functions for instance let's say this is l0 x how does this function look like? This is one of this basis function. This basis function will have zeros for x1 x2 x3 etc and at x0 this basis function will be 1 and it has zeros everywhere for all other points. Please note that this x0 x1 x2 all the way up to xn these are the points we have received these are our given data set and our basis function l0 is such that it will have 1 at x0 and it will have 0 in all other x's. Similarly for instance if we have l1 x then it will have 1 at x1 and it will have zeros at other x's such as x0 x2 etc all the way up to xn. If this is the nature of this basis function how can I write that? So this basis functions have their roots for instance l0 x has its root at x1 x2 x3 etc so for any function li x it has the roots of j equals 0 to n and j not equals i so we'll only drop that i for which this li x at that particular i point it will have one value but it has roots other xi's will be the root of this function. That means the general expression of this li x will be something multiplied to the product of x minus xj where j is not equal to i. Just to understand this process here you can write this l0 x equal to some arbitrary alpha naught multiplied by x minus x1 x minus x2 etc etc up to x minus xn. This alpha naught of course we have to figure it out we don't know yet how this is coming because x1 x2 etc root of this l0 x I can write l0 x in this manner and also I want to emphasize here that l0 x does not have any other roots these are the only roots it may have because if I multiply all these first brackets I get x to the power n and I know that all of this basis function cannot be their degree of that polynomial cannot be greater than n so these are the only roots that l0 x will have. So now we have arrived at certain expression of the basis function only thing that we need is to find out the alpha i. Now you see that this expression of this basis function li we have got it using this concept that li at x equal to xj equals 0 for i not equals j and that gives us the roots of li and that gives us the expression of li like this we don't know the alpha yet but we know that li at x equal to xj will be 1 for i equals j so if I use this expression I'll get an expression for alpha i so let us see this is alpha i and in place of x if I write x i then alpha i and a product of x i minus x j will give me 1 of course j cannot be equal to i and this means that alpha i equals 1 by product of x i minus x j and thus li of x is a product of x minus x j divided by x i minus x j this x i minus x j is coming from this alpha i and these are the expression of all our basis function we have reached the basis functions finally and the function polynomial can be written now as y equal to sum of li x f x i and I know what the li's are so we are all set and this form of interpolating polynomial is known as Lagrange interpolating polynomial the coefficients in Lagrange interpolating polynomial are f x i they are known from the input data set so we don't have to calculate them but we can immediately see that the basis functions are not very easy to get so we have to put some effort in finding the basis function but if we do so then the next part is easy because we don't have to calculate the coefficients for your exercise you take up a function y equals to ln of x and then you approximate this function as a polynomial of degree 2 in the interval 1 to 6 first you do it with Lagrange interpolating polynomial and then you can repeat the exercise using Newton's polynomial that's all for this lecture thank you and I'll see you in next class