Question

Given the four data points \((-1,1),(0,1),(1,2),(2,0)\), determine the interpolating cubic polynomial \- using the monomial basis; \- using the Lagrange basis; \- using the Newton basis. Show that the three representations give the same polynomial.

Short answer

Based on the solutions from monomial basis, Lagrange basis, and Newton basis, the interpolating cubic polynomial for the given data points is: \(P(x) = \frac{1}{6}x^3 + x^2 - \frac{3}{2}x + 1\)

Step-by-step solution

1: Monomial basis

To find the interpolating cubic polynomial using the monomial basis, we first need to set up a system of linear equations. Let the polynomial be in the form \(P(x) = ax^3 + bx^2 + cx + d\). Substituting the given data points, we get the following system of equations: (1) \(-a + b - c + d = 1\) (2) \(d = 1\) (3) \(a + b + c + d = 2\) (4) \(8a + 4b + 2c + d = 0\) Now solve the system to find the coefficients a, b, c, and d.

2: Solve the linear system

We can simplify the system by substituting the value of d (1) into the other equations: (1) \(-a + b - c = 0\) (2) \(a + b + c = 1\) (3) \(8a + 4b + 2c = -1\) Solving this system, we get: \(a = \frac{1}{6}, \space b = 1, \space c = -\frac{3}{2}, \space d = 1\) Thus, \(P(x) = \frac{1}{6}x^3 + x^2 - \frac{3}{2}x + 1\).

3: Lagrange basis

To find the interpolating polynomial using the Lagrange basis, we use the formula: \(P(x) = \sum_{i=0}^n f(x_i) L_i(x)\) where \(L_i(x) = \prod_{j=0, j\neq i}^n \frac{x-x_j}{x_i-x_j}\) and \(f(x_i)\) is the corresponding value. For our data points, we have: \(L_0(x) = \frac{(x-0)(x-1)(x-2)}{(-1-0)(-1-1)(-1-2)} = \frac{x (x-1)(x-2)}{6}\) \(L_1(x) = \frac{(x+1)(x-1)(x-2)}{(0+1)(0-1)(0-2)} = -\frac{(x+1)(x-1)(x-2)}{2}\) \(L_2(x) = \frac{(x+1)(x)(x-2)}{(1+1)(1)(1-2)} = \frac{(x+1)x(x-2)}{2}\) \(L_3(x) = \frac{(x+1)(x)(x-1)}{(2+1)(2)(2-1)} = \frac{(x+1)x(x-1)}{6}\) Substituting the \(f(x_i)\) values and summing: \(P(x) = 1 \cdot L_0(x) + 1\cdot L_1(x) + 2\cdot L_2(x) + 0\cdot L_3(x)\) \(P(x) = \frac{1}{6}x^3 + x^2 - \frac{3}{2}x + 1\)

4: Newton basis

To find the interpolating polynomial using the Newton basis, we use Newton's divided difference formula: \(P(x) = f[X_0] + (x-x_0)f[X_0, X_1] + (x-x_0)(x-x_1)f[X_0, X_1, X_2] + (x-x_0)(x-x_1)(x-x_2)f[X_0, X_1, X_2, X_3]\) with divided differences \(f[X_i]\). Use the data points to calculate the divided differences: \(f[X_0]=1\) \(f[X_1]=1\) \(f[X_2]=2\) \(f[X_3]=0\) \(f[X_0, X_1] = \frac{1-1}{-1-0} = 0\) \(f[X_1, X_2] = \frac{2-1}{1-0} = 1\) \(f[X_0, X_1, X_2] = \frac{1-0}{1+1} = \frac{1}{2}\) \(f[X_2, X_3] = \frac{0-2}{2-1} = -2\) \(f[X_0, X_1, X_2, X_3] = \frac{-2-\frac{1}{2}}{2+1} = \frac{-5}{6}\) Substituting the divided differences: \(P(x) = 1 + 0(x+1) + \frac{1}{2}(x+1)x + \frac{-5}{6}(x+1)x(x-1)\) \(P(x) = \frac{1}{6}x^3 + x^2 - \frac{3}{2}x + 1\)

5: Verification

Now that we have found the interpolating polynomial using the monomial basis, Lagrange basis, and Newton basis, we can verify that they all yield the same polynomial. Monomial basis: \(P(x) = \frac{1}{6}x^3 + x^2 - \frac{3}{2}x + 1\) Lagrange basis: \(P(x) = \frac{1}{6}x^3 + x^2 - \frac{3}{2}x + 1\) Newton basis: \(P(x) = \frac{1}{6}x^3 + x^2 - \frac{3}{2}x + 1\) All three representations give the same polynomial, as required.

Key concepts

Monomial Basis

When constructing an interpolating cubic polynomial using a monomial basis, we utilise the most straightforward approach. Here, the polynomial is expressed as a linear combination of standard monomials, which are of the form \( x^n \) for non-negative integers 'n'.

The general form for a cubic polynomial is \( P(x) = ax^3 + bx^2 + cx + d \), where \( a, b, c \), and \( d \) are coefficients that need to be determined. These coefficients are found by creating a system of linear equations using the given data points and solving that system.

Example: Monomial Basis Linear System

In the example provided, substituting the given data points into the polynomial's general form yields a linear system. Once we solve these equations, we get the specific coefficients that define our unique cubic polynomial. The process may involve techniques like substitution and elimination to simplify and eventually solve for the unknowns. The appeal of using a monomial basis lies in its simplicity and the straightforward application of linear algebra techniques.

Lagrange Basis

The Lagrange basis offers an alternative approach to polynomial interpolation that involves the construction of basis polynomials. The key advantage of this method is that it provides a direct formula for the interpolating polynomial without needing to solve a system of linear equations.

Lagrange interpolation is based on \( L_i(x) \) functions, which are defined as the product of fractions that account for the relative positions of the data points, excluding the current point \( x_i \). Therefore, each \( L_i(x) \) is 0 at every \( x_j \) except for at \( x_i \) where it equals 1.

Building the Polynomial with Lagrange Basis

Each basis polynomial is then multiplied by the corresponding function value, and the sum of these products gives us the interpolating polynomial. This method is especially powerful for theoretical work and proofs, as it explicitly shows the contribution of each data point to the final interpolating polynomial.

Newton Basis

Polynomial interpolation using the Newton basis involves a slightly different set of basis polynomials compared to Lagrange. The Newton interpolating polynomial is also a linear combination of basis polynomials, but these basis polynomials are sequentially built on one another.

The process employs divided differences, which are akin to discrete derivatives and measure the rate of change in y-values with respect to x-values. The polynomial is expressed in terms of these divided differences, leading to a formulation that is particularly easy to update if additional points are added.

Key Feature: Divided Differences

One of the significant benefits of the Newton basis approach is that if more data points become available, we do not need to recalibrate all coefficients; only the new terms corresponding to the extra data need to be calculated. This makes the Newton method efficient for sequential computation and adaptable for dynamic datasets.

Numerical Methods

Polynomial interpolation falls under the broader category of numerical methods, procedures used to obtain approximate solutions to mathematical problems. They are particularly important when an analytical solution is challenging or impossible to find.

Why Use Numerical Methods?

Numerical techniques, such as those for interpolating polynomials, are essential when dealing with discrete data points where we seek a function that accurately fits these points. These methods are widely used in scientific computing, engineering, and finance, among other fields, for problems like curve fitting, data approximation, and numerical integration.

Each method of polynomial interpolation—monomial, Lagrange, and Newton—illustrates a different numerical strategy for achieving essentially the same end; the choice of which to use often depends on the specific requirements and constraints of the problem at hand, such as computational efficiency, ease of use, or the need to update with new data dynamically.