Divided differences

What Are Divided Differences?

Divided differences are a fundamental concept in numerical analysis used to construct polynomials that accurately approximate a function through a given set of data points. This method is particularly valuable when the data points are not uniformly spaced, allowing for efficient interpolation and approximation of values between known observations. In quantitative finance, divided differences can be applied within financial modeling to smooth discrete data, such as interest rates or volatilities, and estimate values at intermediate points.

History and Origin

The concept of divided differences is primarily attributed to Sir Isaac Newton, who introduced the method in his work "Methodus Differentialis" published in 1711.¹⁰ Newton's aim was to provide a systematic way to construct interpolating polynomials, which had significant applications in fields like astronomy for predicting planetary positions based on discrete observations. His method provided a powerful tool for numerical approximation before the widespread adoption of modern computing, laying foundational groundwork for later numerical methods and the development of the Newton's form of the interpolating polynomial.

Key Takeaways

Divided differences are a recursive algorithm for computing coefficients of interpolating polynomials.
They are particularly useful for interpolating data points that are not uniformly spaced.
The method allows for the incremental addition of new data points without recomputing the entire polynomial from scratch.
In finance, divided differences aid in creating smooth curves from discrete market data, essential for various pricing models.
While computationally efficient, the method can be susceptible to numerical errors, especially with ill-conditioned data sets.

Formula and Calculation

Divided differences are defined recursively. Given a set of data points ((x_0, y_0), (x_1, y_1), \ldots, (x_n, y_n)), where (y_i = f(x_i)), the divided differences are calculated as follows:

Zeroth-order divided difference:
$f[x_i] = y_i$

First-order divided difference:
$f[x_i, x_{i+1}] = \frac{f[x_{i+1}] - f[x_i]}{x_{i+1} - x_i}$

Second-order divided difference:
$f[x_i, x_{i+1}, x_{i+2}] = \frac{f[x_{i+1}, x_{i+2}] - f[x_i, x_{i+1}]}{x_{i+2} - x_i}$

General n-th order divided difference:
$f[x_0, x_1, \ldots, x_n] = \frac{f[x_1, x_2, \ldots, x_n] - f[x_0, x_1, \ldots, x_{n-1}]}{x_n - x_0}$

These calculated divided differences then serve as the coefficients for Newton's interpolating polynomial:
$P_n(x) = f[x_0] + f[x_0, x_1](x - x_0) + f[x_0, x_1, x_2](x - x_0)(x - x_1) + \ldots + f[x_0, x_1, \ldots, x_n](x - x_0)(x - x_1)\ldots(x - x_{n-1})$

Each successive term in the polynomial represents the impact of an additional data point on the overall approximation.

Interpreting the Divided Differences

Divided differences can be interpreted as discrete derivative approximations. The first-order divided difference represents the average rate of change of the function between two points, analogous to the slope of a secant line. Higher-order divided differences approximate higher-order derivatives of the underlying function.

In practical applications, the values of divided differences indicate how "smoothly" a function changes between given data points. A large change in a high-order divided difference might suggest rapid oscillation or a non-linear relationship in the underlying data. Understanding these values helps in evaluating the behavior of an interpolated function, such as a yield curve or volatility surface, and assessing the reasonableness of the generated approximation.

Hypothetical Example

Consider a scenario where an analyst has the following discrete bond yields for specific maturities:

Maturity (Years) (x)	Yield (%) (y)
1	2.0
3	2.5
5	3.2

The analyst wants to estimate the yield for a bond with a 2-year maturity using divided differences.

Zeroth-order:
- f[1] = 2.0
- f[3] = 2.5
- f[5] = 3.2
First-order:
- f[1, 3] = (f[3] - f[1]) / (3 - 1) = (2.5 - 2.0) / 2 = 0.5 / 2 = 0.25
- f[3, 5] = (f[5] - f[3]) / (5 - 3) = (3.2 - 2.5) / 2 = 0.7 / 2 = 0.35
Second-order:
- f[1, 3, 5] = (f[3, 5] - f[1, 3]) / (5 - 1) = (0.35 - 0.25) / 4 = 0.10 / 4 = 0.025

Now, construct Newton's interpolating polynomial using the leading diagonal elements of the divided difference table: f[1], f[1, 3], f[1, 3, 5].

$P_2(x) = f[^9^](https://www.mn.uio.no/math/english/people/aca/michaelf/papers/div.pdf) + f[^7^](https://www.mn.uio.no/math/english/people/aca/michaelf/papers/div.pdf), [^8^](https://www.jcbsc.org/admin/get_filephy.php?id=423)(x - 1) + f[^4^](https://www.mn.uio.no/math/english/people/aca/michaelf/papers/div.pdf), [^5^](https://www.jcbsc.org/admin/get_filephy.php?id=423), [^6^](https://math.berkeley.edu/~mgu/MA128ASpring2017/MA128ALectureWeek5.pdf)(x - 1)(x - 3)$
$P_2(x) = 2.0 + 0.25(x - 1) + 0.025(x - 1)(x - 3)$

To estimate the yield for a 2-year maturity (x = 2):
$P_2(2) = 2.0 + 0.25(2 - 1) + 0.025(2 - 1)(2 - 3)$
$P_2(2) = 2.0 + 0.25(1) + 0.025(1)(-1)$
$P_2(2) = 2.0 + 0.25 - 0.025$
$P_2(2) = 2.225$

Based on this interpolation, the estimated yield for a 2-year bond would be 2.225%. This hypothetical example demonstrates how divided differences are used to estimate values between known data points.

Practical Applications

Divided differences, and the interpolation techniques they underpin, have several practical applications in quantitative finance and risk management:

Yield Curve Construction: Financial institutions use divided differences and related interpolation methods to construct smooth yield curves from a limited number of observed bond prices. This allows them to price bonds and derivatives with off-market maturities and to analyze the term structure of interest rates.³
Option Pricing and Volatility Surface Modeling: When valuing options, analysts often need implied volatility for strike prices or maturities not directly quoted in the market. Divided differences can be part of the numerical methods used to interpolate these values, creating a continuous volatility surface.
Time Series Analysis and Forecasting: While more complex models are typically used for forecasting, divided differences can aid in filling gaps in historical financial time series data, providing a more complete dataset for analysis.
Fair Value Calculations: For illiquid or infrequently traded assets, interpolation using divided differences can help in estimating a fair market value based on comparable assets with observed prices.²

Limitations and Criticisms

While divided differences offer a robust method for interpolation, they are not without limitations. A primary concern is their susceptibility to numerical errors, particularly when dealing with a large number of data points or ill-conditioned data sets. These errors can arise from the finite precision of computer arithmetic, leading to issues like round-off error and cancellation error, especially when subtracting nearly equal numbers in the recursive calculation.¹ This can compromise the accuracy of the resulting polynomials, particularly for high-degree interpolations.

Another criticism is that while the interpolating polynomial passes exactly through the given data points, its behavior between those points, especially near the boundaries of the interpolation interval, can sometimes exhibit undesirable oscillations if the underlying function is not smooth or if the data points are poorly distributed. This phenomenon, known as Runge's phenomenon, is a general problem in polynomial interpolation and is not unique to methods based on divided differences. For very noisy or highly oscillatory data, alternative numerical methods like splines or Monte Carlo simulation may provide a more stable or realistic approximation.

Divided Differences vs. Finite Differences

Divided differences and finite differences are related but distinct concepts in numerical analysis. The key distinction lies in the spacing of the independent variables (data points):

Divided Differences: These are designed for unequally spaced data points. The denominator in their calculation explicitly accounts for the difference in the x-values. This makes them highly versatile for real-world data, where observations rarely occur at perfectly uniform intervals.
Finite Differences: These are a special case of divided differences, applicable only when the data points are equally spaced. They involve subtracting consecutive function values without explicit division by the x-interval, as the common interval (h) can be factored out. Finite differences lead to simpler formulas, such as Newton-Gregory forward or backward interpolation formulas, but their applicability is limited to uniformly spaced data.

While both are used for interpolation and approximating derivatives, divided differences offer greater flexibility due to their ability to handle any spacing of data, making them more broadly applicable in diverse financial modeling scenarios.

FAQs

What is the main purpose of divided differences?

The main purpose of divided differences is to provide a systematic way to construct an interpolating polynomials that passes through a given set of data points, especially when these points are not equally spaced. This polynomial can then be used to estimate function values at intermediate points.

How do divided differences simplify interpolation?

Divided differences simplify interpolation by transforming the problem of finding an interpolating polynomial into a recursive calculation of coefficients. This avoids solving a large system of linear equations, which can be computationally intensive and numerically unstable for high-degree polynomials.

Can divided differences be used for extrapolation?

While mathematically possible to use the interpolating polynomial for extrapolation (estimating values outside the range of given data points), it is generally not recommended. Extrapolation with polynomials, including those derived from divided differences, can lead to highly inaccurate and unreliable results, as the polynomial's behavior outside the known data range is not constrained by actual observations and can diverge rapidly.

What is the relationship between divided differences and derivatives?

Divided differences are closely related to derivatives. The first-order divided difference is equivalent to the slope of a secant line and approximates the first derivative. Higher-order divided differences are related to higher-order derivatives of the underlying function, providing a discrete approximation of how the rate of change itself is changing.