Question

Let \(\left(\hat{x}_{0}, \hat{x}_{1}, \ldots, \hat{x}_{k}\right)\) be a permutation of the abscissae \(\left(x_{0}, x_{1}, \ldots, x_{k}\right)\). Show that $$ f\left[\hat{x}_{0}, \hat{x}_{1}, \ldots, \hat{x}_{k}\right]=f\left[x_{0}, x_{1}, \ldots, x_{k}\right] $$ [Hint: Consider the \(k\) th derivative of the unique polynomial of degree \(k\) interpolating \(f\) at these \(k+1\) points, regardless of how they are ordered.]

Short answer

**Question:** Show that the divided difference of a given function remains the same under permutations of the abscissae. **Answer:** The divided difference of a function remains the same under permutations of the abscissae because the unique polynomial that interpolates the given points is the same, regardless of the order of the abscissae. Therefore, evaluating the divided differences for both the original and permuted abscissae yields the same constant term, proving that the divided difference stays the same.

Step-by-step solution

Understand the Notation

First, let's understand the notation in the exercise. Here, $$f\left[\hat{x}_{0}, \hat{x}_{1}, \ldots, \hat{x}_{k}\right]$$ and $$f\left[x_{0}, x_{1}, \ldots, x_{k}\right]$$ represent the divided differences for a function \(f\) using a permutation of the abscissae \((x_0, x_1, \ldots x_k)\) and the original abscissae, respectively.

Consider Polynomial Interpolation

Now we know that there exists a unique polynomial of degree \(k\) that interpolates \(f\) in the points \((x_0, x_1, \ldots, x_k)\). Let that polynomial be \(P(x)\). Since this is a polynomial of degree \(k\), we have, after taking the \(k\)th derivative: $$P^{(k)}(x) = C \cdot k!$$ where \(C\) is a constant.

Evaluate the \(k\)th Derivative at One Point

Now, let's consider any one of the abscissae, say \(x_0\), and evaluate the \(k\)th derivative of \(P(x)\) at \(x_0\): $$P^{(k)}(x_0) = C \cdot k!$$ We know that \((P(x) - f(x))^{(k)}=0\) at the points \((x_0, x_1, \ldots, x_k)\) as the polynomial \(P(x)\) interpolates the points.

Evaluate the Divided Difference

Now let's evaluate the divided differences for the given function using the points \((x_0, x_1, \ldots, x_k)\). We have: $$f\left[x_0, x_1, \ldots, x_k\right] = \frac{P^{(k)}(x_0)}{k!} = C$$

Consider the Permuted Abscissae

Let \((\hat{x}_0, \hat{x}_1, \ldots \hat{x}_k)\) be a permutation of the abscissae \((x_0, x_1, \ldots x_k)\). Since the polynomial \(P(x)\) is unique and it interpolates the points, it does not depend on the order of abscissae used. Therefore, if we were to construct a polynomial interpolant \(\hat{P}(x)\) using the permuted abscissae, it must be the same as the original polynomial \(P(x)\): \(\hat{P}(x) = P(x)\).

Evaluate the Divided Difference for the Permuted Points

Now let's evaluate the divided differences for the given function using the permuted points \((\hat{x}_0, \hat{x}_1, \ldots, \hat{x}_k)\). We have: $$f\left[\hat{x}_0, \hat{x}_1, \ldots, \hat{x}_k\right] = \frac{\hat{P}^{(k)}(x_0)}{k!} = \frac{{P}^{(k)}(x_0)}{k!} = C$$ The reason we evaluated the constant term at \(x_0\) and not at any other of the permuted points is that we ensured that \(x_0\) is a point where the polynomial interpolates the function, regardless of the permutation used.

Conclude the Result

Now we have: $$f\left[\hat{x}_0, \hat{x}_1, \ldots, \hat{x}_k\right] = C = f\left[x_0, x_1, \ldots, x_k\right]$$ This shows that the divided difference of \(f\) remains the same under permutations of the abscissae, as required.

Key concepts

Divided Differences

Divided differences are a fundamental tool in interpolation. They provide a way to calculate derivatives and interpolating polynomials for a given set of data points. A divided difference is essentially a recursive division of differences between consecutive points. The notation \(f[x_0, x_1, \ldots, x_k]\) represents the divided difference for function \(f\) with respect to the points \(x_0, x_1, \ldots, x_k\).

• The first divided difference gives the slope between two points: \(f[x_0, x_1] = \frac{f(x_1) - f(x_0)}{x_1 - x_0}\).
• Higher-order differences build on this concept, calculating slopes between divided differences themselves.

Using divided differences, you can systematically construct an interpolating polynomial of minimum degree that fits all provided data points.

Permutation of Abscissae

In polynomial interpolation, the term 'abscissae' refers to the x-coordinates of the data points used. A permutation of abscissae means rearranging these x-coordinates without altering the actual numerical value of any of them. This rearrangement does not affect the resulting interpolating polynomial. It's a crucial point because polynomial's value is determined by the locations, not the order of x-values.

This property ensures the consistency of the interpolation polynomial, meaning:

• The polynomial remains unchanged regardless of the permutation of the data points.
• Divided differences computed on these points are unaffected by their ordering.

This concept is particularly useful as it leads to the conclusion that the polynomial interpolation process itself is invariant under such permutations.

Uniqueness of Polynomial Interpolant

The uniqueness of polynomial interpolant is a significant property in polynomial interpolation that guarantees a single, specific polynomial can pass through a set of given points. For a set of \(k+1\) distinct abscissae, there exists one and only one polynomial of degree \(k\) that fits these points exactly.

• This property arises because the problem defines a linear system where each equation corresponds to fitting the polynomial through each data point.
• Solving this system gives a unique solution due to the linear independence of the basis functions associated with each data point.

This assurance of a unique solution is fundamental in many numerical methods and ensures stability and reliability of polynomial interpolations.

Kth Derivative

The \(k\)th derivative plays an integral role in understanding the behavior and properties of interpolation polynomials. When computing the \(k\)th derivative of a polynomial interpolant, it provides insight into the variation of the polynomial at a specific point. In the context of interpolation:

• Taking the \(k\)th derivative of a polynomial of degree \(k\) results in a constant, indicating the leading term's behavior.
• The \(k\)th derivative at one of the interpolation points often represents a key component in calculating divided differences and constructing interpolation formulas.

This understanding is essential for proof of uniformity in polynomial interpolants, showing that properties like divided differences remain invariant under permutations of the abscissae.