Category: Interpolation

Interpolation is a technique in numerical analysis to find a functional formula based on given data of given points.

  • 2d-Solved problems for Newton-divided differences.

    2d-Solved problems for Newton-divided differences.

    Solved problems for Newton-divided differences.

    We have discussed the Newton-divided difference interpolation in a previous post. In this post, we have two solved problems as an application to Newton-divided differences.

    The first solved problem.

    Three points where x and y values are given are required to get the expression for the polynomial based on Newton-divided differences and the value of a new point with x=2.70.

    The next equation will obtain the polynomial, but we need to estimate the values of b0,b1, and b2. We could start the first point and call it (?x1,y1), but in these two solved problems, I consider the first point coordinates as (X0, y0).

    We know that b0=y0, from the given table, the first point y value or y0=3.
    To get the b1, we must estimate the first divided difference between x0,y0, and(x1,y1).

    The Graph curve based on the given points is shown in the next slide image. We have three points, meaning we have three’ coefficients: b0, b1, and b2. the polynomial P(x) =b0+b0*(x-x0)+b2*(x-x0)*(x-x1). Such an expression will give p(x=x0)=b0, while P(x=x1)=b0+b1*(x1-x0)+b2*(x1-x0)*(x1-x1)=b0+b1*(x1-x0)+0.

    The first coefficient, b0, is equal to the y coordinate of the first point, so b0=y0.

    Solved problem-1 Newton divided differences.

    How do we estimate the b0, b1, and b2 values?

    The shown equation gives the second divided difference in the next slide image.

    The first divided difference between points (x1, y1) and ( x0,y0) is estimated as the difference between (y1 and y0)/the difference between x1 and x0.

    After estimating the first two differences, the value of these differences will be divided by the difference between(x2-x0) to get the second divided difference. the coefficient b0=3, while b1=(y1-y0)/(x1-x0)=(5-3)/(2-1), f[x1,x2)=(y2-y1)/(x2-x1)=(8-5)/(3-2)=3, b2=f[x1,x2)-f[x1,x2)/(x3-x0)=1/2.

    Once we have obtained the three values of b0,b1, and b2, we can write the polynomial, as the next slide image shows.

    Detailed procedure on how to get b0, b1, b2.

    The final expression for the polynomial using Newton-divided differences.

    The next slide image shows the final expression for the polynomial using Newton-divided differences.

    Using table to get 0,b1 and b2 values.

    The last requirement is to estimate the y value for a new point of a given x value =2.70. Before we can substitute the value of x=2.7 in the polynomial expression, it is preferred to check the y values of the given three points via the table using the values obtained using the polynomial expression for (x0,x1,x2).

    The final expression for P(2.7).

    From the shown calculations, we can substitute the value of x=2.70 and get the P(2.70), which is equal to 6.995.

    The second solved problem.

    Four points where x and y values are given require getting the expression for the polynomial based on Newton-divided differences. Since we have four points, we have to determine the values of four b’s: b0,b1,b2, and b3.

    The equation will now be expanded to account for the four values of b’s.

    How do we estimate the value of b1?

    The value of b0 is the same value of y0 for the first point, which equals 1. For the value of b1, it will be estimated as the first divided difference between points (x0,y0) and (x1,y1).

    The second solved problem for Newton divided differences.

    How do we estimate the value of b2?

    The b2 values can be estimated in two stages. The first stage is to get the first divided difference between points (x2,y2) and ( x1,y1).

    The value of the coefficient b2.

    The second stage is to get the first divided difference between points (x0,y0) and ( x1,y1). The estimated differences will be divided by (x2-x0).

    This table is used to get the differences for the 4 given points in the case of a cubic polynomial, which is a polynomial of degree 3. The equations of b0,b1,b2, and b3 are shown in the slide image.

    table for the differnt terms of b coefficients.

    How do we estimate the value of b3?

    The given calculation for the value of b3 is given in the next slide image for more details.

    The value of coefficient b3.

    The final value of b3 is shown to be=-1/12.

    A table was used to get the Newton-divided differences.

    It is much easier to estimate the divided differences and get the different values of b0,b1,b2, and b3 by using the table.

    detailed Table for the values of b0 to b3.

    Once we have obtained the three values of b0,b1,b2, and b3.

    The final expression for the polynomial using Newton-divided differences.

    The expression of the cubic function is shown. The given table compares all the y values of the given four points, estimated by plugging the polynomial expression, and finds that they match.

    Check the Y cootes for point by polynomial.

    We can find the polynomial, as we can see from the next slide image. It is preferred to check the y values of the given four points via the table using the values obtained by using the polynomial expression for (x0,x1,x2,x3).

    The final expression for the polynomial.

    This is a link to Holistic Numerical Methods-Newton divided Differences.

    This links to the previous post: What is Newton-divided difference interpolation?

  • 2c- What is Newton-divided difference interpolation?

    2c- What is Newton-divided difference interpolation?

    What is Newton-divided difference interpolation?

    Newton has developed a new form for the interpolation of functions. In this post, we will be discussing Newton-divided difference interpolation.

    A new form of Quadratic expression was adopted. For a Quadratic function where n=2, we need n+1 points, three points. Our n+1=3 points, namely (xo, x1, x2), and their y coordinates are (yo, y1, y2).

    The quadratic function will be written as Q(x) = b0+b1(x-x0) +b2(x-x0) (x-x1). It can be further expanded as Q(x) = bo+b1x- b1*xo +b2(x^2-x*x1-x0*x+x0 *x1). Recalling our polynomial expressed as  P2(x)= ao+a1*x+a2*x^2.

    Since both functions are the same, we will equate both. For the item of x, we have a1*x=+b1*x-b2*x1*x-b2*x0*x. a1= b1 -b2*x1 -b2*x0.

    Introduction to Newton-divided difference interpolation.

    Similarly, For the item of x^2, we have a2*x^2=b2*x^2. Then for the value of the term a2, it will be a2= b2

    For the constant item, we have a0= b0-b1*x0+b2*x0*x1. To get values of b0,b1,b2, in terms of the given three Points. Use the first point(x0,y0) to get the value of b0. We can rewrite the Q(x0) as: x=x0,y=y0.

    Q(x) = b0+b1(x-x0) +b2(x-x0) (x-x1). Q(x0) =y0= b0+b1(x0-x0) +b2(x0-x0) (x0-x1). b0=y0.

    Back to our equation of Q(x), Q(x) = y0+b1(x-x0) +b2(x-x0) (x-x1). For the second point(x1,y1), we can rewrite the Q(x1) as: x=x1,y=y1. From the equation Q(x) = y0+b1(x-x0) +b2(x-x0) (x-x1).

    The expression of the first divided difference.

    Q(x1) =y1= y0+b1(x1-x0) +b2(x1-x0) (x1-x1). y1= y0+b1(x1-x0)+0 then b1=(y1-y0)/(x1-x0). This is the first divided difference written as f, bracket x0,x1, then bracket.

    The expression of b1 in terms of the x1,y1 and x2,y2.

    Back to our equation of Q(x). Q(x) = y0+b1(x-x0) +b2(x-x0) (x-x1). Rewrite as: Q(x) = y0+((y1-y0)/(x1-x0))* (x-x0) +b2(x-x0) (x-x1). For the third point(x2,y2), we can rewrite the Q(x2) as: x=x2,y=y2. From the equation Q(x) = y0+((y1-y0)/(x1-x0))* (x-x0) +b2(x-x0) (x-x1).
    Q(x2) =y2= y0+((y1-y0)/(x1-x0))* (x2-x0) +b2(x2-x0) (x2-x1).

    The following steps in the next slide picture will illustrate the procedure to get the value of b2.

    The steps to get b2 value.

    Newton-divided difference or second-divided difference.

    For the second divided-difference, which is written as f, bracket x0,x1,x2, then bracket.

    The expression for Newton the second divided difference.

    This is the final expression for the quadratic polynomial using Newton-divided difference interpolation.

    The final expression of Newton divided -differnec for a quadratic function.

    The polynomial is shown in the case of the first order.

    The first divided difference is shown in the next slide. A line represents the first divided difference.

    The polynomial is shown in the case of the first order. The first divided difference is shown in the next slide. A line represents the first divided difference.

    Newton first divided difference

    For the Higher-order n value, an expression can be developed and made as a table.

    We can make a table for the second divided difference. The next slide image shows the arrangement. The source is from Amos Gilat’s Numerical Methods for Engineers. The clouded area is for a Quadratic polynomial.

    Newton second divided difference diagram

    The main advantage of Newton’s divided difference interpolation is that we will not substitute it to make a solution for the n equations. In our case, n=2 is for a quadratic function.

    The next post will solve two problems as practice problems for Newton-Divided difference polynomials.

    This is a Wiki link for Numerical analysis.

    This is a link to Holistic Numerical Methods-Newton divided Differences.

  • 2b- Solved problems for quadratic interpolation

    2b- Solved problems for quadratic interpolation

    Solved problems for quadratic interpolation using the vandermonde matrix.

    Two solved problems for quadratic interpolation are introduced by using the given three points and the corresponding y values to get the coefficients a0,a1, and a2. And then, we can write the quadratic polynomial expression as P(x)=a0+a1x+a2x2.

    The last step is multiplying the inverse matrix V-1 by the X-X matrix to find the value of the factor column vector.

    We ultimately obtained these values, as shown in the last slide image.

    Introduction to quadratic interpolation.

    These equations can be written in a matrix form. The Form of V*X=Y is to be used, where V is the Vandermonde matrix, and the column vector for the coefficients of a0,a1, and a2.y is the column vector of y values for the three points.

    Three polynomial equation for quadratic interpolation

    This is the final value for the coefficients. For more details, please refer to the previous post to learn how to derive this expression. The matrix b is formed with 3×3, and the different factors for all the rows and columns are shown in the next slide image.

    The values of a0,a1,and a2 for the quadratic interpolation polynomial.

    Solved problem 1/2 of the solved problems for quadratic interpolation.

    It is required to derive an expression for the quadratic polynomial for a given three-point x and y value and check the P(x) value of x=2.70.

    The values of b11,b12, and b13 of the first row of matrix B.

    The first step is to find the value of coefficients a0,a1, and a2 by substituting the corresponding elements of the B matrix, considering x0=1, y0=3, x1=2, y1=5, and x2=3 and y2=8. All the rows have different x0,x1,x2, and fractions values.

    The next slide image explains the values of the first row of matrix B.

    Solved problem#1 of the two solved problems for quadratic interpolation

    The values of b21,b22, and b23 of the second row of matrix B.

    The next slide image explains the values of the second row of matrix B.

    Solved problem-1. second-row expression.

    The values of b31,b32, and b32 of the third row of matrix B.

    .The next slide image explains the values of the third row of matrix B.

    Solved problem-1. third-row expression.

    The values of a0,a1, and a2 for solved example-1.

    Once we have written the three rows of matrix B, we will multiply matrix B by the vector matrix ( y0,y1,y2). The product will give the corresponding values of the coefficients: a0=2, a1=1/2, and a2=1/2.

    The final expression of P(x)and P(2.707) value.

    The quadratic polynomial can be written as P(x)=a0+a1x+a2*x2. The last step is to find the point p with coordinate x=2.70. P(2.707) will be 6.995. Please check the next slide image for more details.

    Solved problem#1- Final quadratic polynomial expression.

    Solved problem 2/2 of the solved problems for quadratic interpolation.

    It is required to derive an expression for the quadratic polynomial using quadratic interpolation for a given three-point x and y value and check the P(x) value of x=pi/12.

    The function is f(x)=(sin x+cos x). the given x values are x0=10 degrees, x1=20 degrees and x2=30 degrees. The first step is to find the value of coefficients a0,a1, and a2 by substituting the corresponding elements of the B matrix.

    After converting the values in degrees to the corresponding values in radians.consider x0=0.1745, y0=1.1585, x1=0.3491, y1=1.2817, and x2=0.5236 and y2=1.3660.

    Solved problem#2 of the two solved problems for quadratic interpolation.

    The values of b11,b21, and b31 of the first column of matrix B.

    The next slide image explains the values of the first column of matrix B and the values of the different elements.

    The value of the first column of B matrix.

    The values of b12,b22, and b23 of the second column of matrix B.

    The next slide image explains the values of the second column of matrix B and the values of the different elements.

    The value of the second column of B matrix.

    The values of b13,b23, and b33 of the third column of matrix B.

    The next slide image explains the values of the third column of matrix B and the values of the different elements.

    The value of the third column of B matrix.

    The values of a0,a1, and a2.

    Once we have written the three rows or columns as we have done in this example of matrix B, we will multiply matrix B by the vector matrix ( y0,y1,y2). The product will give the corresponding value of the coefficients as follows:

    a0=0.9968, a1=1.0176 and a2=-0.6009.

    The final expression of quadratic interpolation is P(x) and the value of P(PI/12).

    The quadratic polynomial can be written as P(x)=a0+a1x+a2*x2. The last step is to find P(pi/12), which will be=1.222.

    The original function’s corresponding value of Pi/12 is obtained by writing sin (pi/12)+ cos(pi/12)=1.2247, which has little difference from the quadratic polynomial value.

    This links to post 9, titled How to Use a Matrix for the Quadratic Function?

    The previous post 2a– Easy introduction to quadratic interpolation.

    The next post is Introduction to Newton-divided difference interpolation.

Quadratic interpolation.

Quadratic interpolation is using a second-order polynomial to make interpolation for a function.
Unlike linear interpolation, which we discussed in the previous post, quadratic interpolation requires three points.

The first point of the three points has a coordinate of(x0,y0 ), the second point has a coordinate of(x1,y1 ), and the last point has a coordinate of(x2,y2 )

Introduction to quadratic interpolation

What is the Vandermonde matrix?

After substituting in the polynomial matrix by the value of the different x and y of the given three points, we will have a set of quadratic equations with three unknowns a0,a1, a2. These equations can be written in a matrix form. The Form of V*X=Y is to be used, where V is the Vandermonde matrix, Xs is the column vector for the coefficients of a0,a1, and a2.y is the column vector of y values for the three points.

Three polynomial equations for quadratic interpolation

How do we derive the expression for the Vandermonde elements?

The Vandermonde matrix, in the case of quadratic polynomials, is a(3 x 3) matrix, it can be written in the form of Vi,j =xi-1^j-1, where i is the row number and j is the column number, for instance,, V23=x2-1^j(3-1)=x1^2, V23 is the element in the second row and the third column, will be equal to the second power of x1.

I have written using that form of the different elements of the Vandermonde matrix for quadratic interpolation.

How to derive the expression for vandermonde?

How do we find the determinant value of the Vandermonde matrix?

To get the matrix’s determinant value, we will let x0=0 by multiplying the second column by x0, subtracting the new result from the third column, and placing the result in the third column.

How to derive the expression for vandermonde?

This is a continuation of the calculations.

Steps used to get the determinant value of the Vandermonde matrix.

To get the determinant value of the matrix, we will let x0=0 by multiplying the second column by x0, then subtract the new result of that multiplication from the third column and place the result in the third column.

The process will be repeated by the first column by x0, then the new result of that multiplication will be subtracted from the second column and placed in the second column.

steps to get the determinant value.

The first row will have two zeros in the second and third columns, while the second row will have a value in the first column.

Finally, the first column will have a value in the third row.

Steps used to get the determinant value of the Vandermonde matrix.

The final value of the determinant of the Vandermonde matrix can be found as (x2-x0)*(x1-x0)*(x2-x1).

The final expression for the determinant of the Vandermonde matrix.

The process to get the inverse of the Vandermonde matrix.

We want to find out the inverse matrix of Vandermonde, this is done by using co-factors and adjugate.

How to get the inverse matrix of the Vadermonde matrix?

We will start estimating the minors of matrix V. The next images will show the estimation process for the minors of the first, second, and third rows.

The values of the minors for the second row for the V matrix.

These are the values of the minors for the second row of the matrix. The values of the minors are for the third row of the matrix.

The values of the minors for the third row for the V matrix.

The step-by-step procedure is shown in the next slide image.

The cofactor of vandermonde matrix.

We can form the co-actor matrix and factor (x2-x1) for the first column & (x2-x0) for the second column, and (x2-x1) from the last column.

Forming the cofactor matrix by considering the signs.

To get the inverse of the V—matrix, we will divide the co-factor matrix by the determinant value, which we estimated earlier.

That division cancels the common factor, and the final result of the inverse matrix can be found.

Factoring the columns of the co-factor matrix.

The final value of the coefficient matrix.

The last step is to multiply the inverse matrix V-1 by the X-X-matrix to find the value of the factor column vector.

In the end, we obtained these values, as shown in the last slide image.

The values of a0,a1, and a2 for the quadratic interpolation polynomial.

This is an external Useful external siteMathonline.

The next post: Solved problems for quadratic interpolation.

  • 1- Easy introduction to the definition of Interpolation.

    1- Easy introduction to the definition of Interpolation.

    Definition of interpolation and linear interpolation?

    As defined by Prof. Gilat Amos, reference book, Numerical Methods for Engineers and Scientists, 3rd Edition: An Introduction with Applications Using MATLAB, Interpolation is a procedure in which a mathematical formula is used to represent a given set of data points such that the formula gives the exact value at all the data points and an estimated value between the points.

    This section shows how to do this using a single polynomial, regardless of the number of points. As mentioned in the previous section, for any number of points n, there is a polynomial of order n—1 that passes through all points.

    The polynomial is in the first order (a straight line connecting the points) for two points.

    For three points, the polynomial is of second order (a parabola that connects the points), and so on. The next slide image shows the same function but is represented by different polynomials based on the information of the given points.

    For instance, if only two points, A and B, are given, the first graph will be represented by linear interpolation.

    The second graph gives three points: the polynomial is quadratic, etc.

    Various types of interpolation represented  by polynomials.

    This is illustrated in Fig. 6-11, which shows how first, second, third, and fourth-order polynomials connect two, three, four, and five points, respectively.

    What is the definition of  interpolation?

    What are polynomials?

    From math is fun, site, the polynomial is composed of two words: poly (meaning “many”) and nominal (in this case, meaning “term”), so it says “many terms.”
    A polynomial can have constants, variables, and exponents but never be divided by a variable.

    In the next slide image, the first-degree polynomial comprises two terms: one term is a constant, while the other is a variable. Second-degree and third-degree polynomials are expressed.

    How to express first, second, third degree polynomials?

    What is the leading coefficient for a polynomial?

    The leading coefficient of a polynomial is the coefficient with the highest variable degree. Here is the polynomial calculator for the DEGREE AND LEADING COEFFICIENT CALCULATOR.

    Solved problem, what is the leading term?

    A Solved problem for leading coefficient and leading term.

    For a given example of f(x)= 5×4+2×3-x+4, the leading coefficient is the coefficient with the highest power. The highest power is 4, and the coefficient of that highest power is 5. The highest term is(5*x4).

    Solved problem, what is the leading term?

    What is linear interpolation?

    Linear interpolation estimates a missing functional value between two data points by constructing a line between them. The linear function of the line can then be used to find the desired value of the data point of interest.

    Using the initial point A, which has a coordinate of (x0,y0), and another point b, with a coordinate of (x1,y1), the line joining the two points can be estimated by estimating its slope as the difference in y divided by the difference in x distance.

    What is the definition of linear interpolation?tio

    The final form of the polynomial used for the linear interpolation can be written as P(x)=y=y0+((y1-y0)*(x-x0)/(x1-x0).
    Then, we will substitute the given values of points A and b. Thus, we get the final equation of x and y.

    Derivation of the polynomial equation for linear interpolation.

    Solved example#1.

    if we want to get a linear interpolation of the f(x) sqrt(x), we need two points, which are given by point-1, with (1,1), and the second point is point 2, which has a coordinate of(9,3).

    We will substitute in the equation of the P(x)=y=y0+((y1-y0)*(x-x0)/(x1-x0). for x0=1, y0=1 and (x1=9, y1=3), thus we can get the final polynomial equation as a linear interpolation.

    Solved problem for linear interpolation.

    For point c, where x=5, we can p(5) as=2.00. For f(x) as sqrt of (5), it will equal =2.236. We can estimate the error between the original and linear interpolation functions. A graph is drawn to show the difference between the two functions.

    How to estimate the error % due to linear interpolation?

    The next post is post 2a-an Easy introduction to quadratic interpolation to quadratic interpolation.
    This is a great resource for the background of interpolation.
    Linear interpolation calculator tool.