A finite divided difference is a recursive difference quotient that approximates the derivative of a function using discrete values. It's a fundamental tool in numerical analysis, especially for polynomial interpolation and approximation of derivatives.
Understanding Divided Differences
At its core, a divided difference provides an estimate of the rate of change of a function, similar to a derivative. However, instead of using the limit definition of a derivative, it relies on function values at discrete points.
Definition and Notation
Let f(x) be a function and x0, x1, ..., xn be distinct points. The divided differences are defined as follows:
-
Zeroth divided difference: f[xi] = f(xi) (the function value itself)
-
First divided difference: f[xi, xi+1] = (f(xi+1) - f(xi)) / (xi+1 - xi) (slope between two points)
-
Second divided difference: f[xi, xi+1, xi+2] = (f[xi+1, xi+2] - f[xi, xi+1]) / (xi+2 - xi)
-
General nth divided difference: f[xi, xi+1, ..., xi+n] = (f[xi+1, ..., xi+n] - f[xi, ..., xi+n-1]) / (xi+n - xi)
The key here is the recursive nature. Higher-order divided differences are built from lower-order ones.
Table Representation
Divided differences are often organized in a table, which makes the calculation more systematic:
| xi | f(xi) | f[xi, xi+1] | f[xi, xi+1, xi+2] | f[xi, xi+1, xi+2, xi+3] |
|---|---|---|---|---|
| x0 | f(x0) | |||
| x1 | f(x1) | f[x0, x1] | ||
| x2 | f(x2) | f[x1, x2] | f[x0, x1, x2] | |
| x3 | f(x3) | f[x2, x3] | f[x1, x2, x3] | f[x0, x1, x2, x3] |
Example
Let's say we have the following data points for a function f(x):
- x0 = 1, f(x0) = 1
- x1 = 2, f(x1) = 4
- x2 = 3, f(x2) = 9
Then, the divided differences would be:
- f[x0, x1] = (4 - 1) / (2 - 1) = 3
- f[x1, x2] = (9 - 4) / (3 - 2) = 5
- f[x0, x1, x2] = (5 - 3) / (3 - 1) = 1
Use in Polynomial Interpolation
Divided differences are the building blocks for Newton's Divided Difference Interpolating Polynomial, which provides a way to approximate a function given a set of data points. The polynomial is of the form:
P(x) = f(x0) + f[x0, x1](x - x0) + f[x0, x1, x2](x - x0)(x - x1) + ...
Properties and Significance
- Symmetry: The value of a divided difference is independent of the order of the arguments. For example, f[x0, x1] = f[x1, x0].
- Approximation of Derivatives: As the points xi get closer together, the divided differences approach the derivatives of the function. f[x0, x1] approximates f'(x) at some point between x0 and x1.
- Ease of Calculation: The recursive definition makes it computationally straightforward to calculate higher-order divided differences.
In summary, finite divided differences are a powerful numerical technique for approximating derivatives and constructing interpolating polynomials, especially when dealing with discrete data. They provide a flexible and computationally efficient way to estimate function behavior.
