Inverse Interpolation

Finding the inputs that yield a specific output is a fundamental challenge across science and engineering, commonly known as root-finding. While traditional methods iteratively guess the solution, they can be inefficient or unstable. This article introduces a more elegant and powerful approach: inverse interpolation, which tackles the problem by fundamentally flipping the perspective from $y=f(x)$ to $x=g(y)$. By examining the problem through this inverted lens, we unlock simpler and often more robust solutions. In the following chapters, we will first explore the core principles and mechanisms of this technique, revealing how methods like the secant method and inverse quadratic interpolation work. Subsequently, the article will demonstrate the wide-ranging utility of this approach, drawing connections to diverse applications in engineering, science, and finance.

Suppose you have a machine, a black box described by some function $f(x)$. You put in a number $x$, and it gives you back a number $y$. The game we often play in science and engineering is called ​​root-finding​​: we want to find the special input $x$ that makes the machine's output exactly zero. Maybe $f(x)$ represents the net force on a bridge, and we want to find the load $x$ that results in zero stress in a critical beam. Or perhaps $f(x)$ is a financial model, and we want to find the interest rate $x$ that makes the net present value of an investment zero.

The usual approach is a kind of educated guessing. You try an $x_1$, you see what $f(x_1)$ is. It's not zero. You try an $x_2$, you get $f(x_2)$. Also not zero. But maybe by looking at how the output changed, you can make a better guess for $x_3$. This is the heart of many famous methods. But today, we're going to look at this problem in a completely different way. We are going to flip the entire problem on its head.

Instead of thinking of the output $y$ as a function of the input $x$, that is, $y=f(x)$, what if we imagine the opposite? What if we could think of the input $x$ as a function of the output $y$? Let’s call this inverted function $g$, so that $x=g(y)$.

Why would we do this? Because if we could find this function $g$, our root-finding problem would become laughably simple. Finding the $x$ that gives $f(x)=0$ would be the same as asking, "What is $x$ when $y=0$?" In our new language, this is just a matter of calculating $g(0)$. No more guessing! Just plug zero into our magical inverse function $g$ and we're done.

Of course, there's a catch. We usually don't know the inverse function $g(y)$ in its entirety. But we don't need to. Just as standard methods approximate the original function $f(x)$ locally (say, with a line), we can try to approximate the inverse function $g(y)$ locally. And this subtle shift in perspective has profound and beautiful consequences.

Let's start with the simplest possible approximation. A function can be approximated by a straight line, right? So, let's approximate our mysterious inverse function $x=g(y)$ with a line. To define a line, we need two points. Suppose we have already made two guesses, $x_{k-1}$ and $x_k$, and we’ve calculated their outputs, $y_{k-1} = f(x_{k-1})$ and $y_k = f(x_k)$.

In our inverted world, these correspond to the points $(y_{k-1}, x_{k-1})$ and $(y_k, x_k)$. We can draw a straight line through them. The equation of this line, which we'll call $P(y)$, is our linear approximation of $g(y)$. Our new-and-improved guess for the root, $x_{k+1}$, is simply the value of this line at $y=0$. That is, $x_{k+1} = P(0)$.

If you write down the equation for that line and solve for $P(0)$, you get a wonderful surprise. The formula that pops out is:

This is exactly the formula for the ​​secant method​​! This is a remarkable discovery. The secant method, which we traditionally think of as drawing a line through $(x_{k-1}, f(x_{k-1}))$ and $(x_k, f(x_k))$ and finding where it crosses the x-axis, is algebraically identical to drawing a line through the inverted points and finding where it crosses the y-axis. It’s the same algorithm, just viewed from a different and, as we'll see, more powerful perspective. This insight reveals a hidden unity between different ways of thinking about the problem.

If approximating the inverse function with a line is a good idea, then approximating it with a parabola should be even better, especially if the original function is curvy. This is the core idea behind ​​inverse quadratic interpolation (IQI)​​.

To define a unique parabola, we need three points. So, let's take our last three points: $(a, f(a))$, $(b, f(b))$, and $(c, f(c))$. We flip them to get three points in our inverse space: $(f(a), a)$, $(f(b), b)$, and $(f(c), c)$. We then fit a "sideways" parabola of the form $x = Q(y)$ through these three points.

The formula for this parabola can be written down directly using Lagrange interpolation. Our next estimate for the root is simply $x_{new} = Q(0)$, which gives the explicit, if somewhat intimidating, formula:

Don't let the complexity of the formula fool you; the idea is beautifully simple. We're building a more sophisticated model of the inverse function and then asking it a very simple question: "Where are you when $y=0$?" Because this quadratic model captures the local curvature of the function, it can often produce astonishingly accurate estimates, converging to the true root much faster than the linear secant method.

At this point, you might be asking: why all this talk of inversion? We could just as well fit a standard parabola $y = P(x)$ through our three points and find where it crosses the x-axis by solving the quadratic equation $P(x)=0$. Why is the inverse approach generally better? Herein lies the true elegance of the method.

First, notice that the IQI formula gives us our new estimate directly. There are no equations to solve. With standard quadratic interpolation, we would have to solve a quadratic equation, which is an extra step.

But there's a much more profound reason. Imagine our three points on the standard graph of $y=f(x)$ are such that the parabola fitting them opens upwards and its minimum is above the x-axis. In this case, the parabola never crosses the x-axis! The method fails completely, unable to provide a real-valued next guess. This is not some rare, pathological case; it can happen easily when the iterates are near a root where the function is relatively flat.

Now consider our sideways parabola, $x = Q(y)$. As long as our three function values $f(a), f(b), f(c)$ are distinct, we can always fit a unique quadratic. This parabola, being a function of $y$, intersects the x-axis (the line $y=0$) at exactly one point. There's no ambiguity, no risk of the parabola "missing" the axis. The estimate $x_{new}=Q(0)$ is always well-defined and unique. This provides a remarkable level of numerical stability that the standard approach lacks.

Inverse Quadratic Interpolation is fast and elegant, but like a high-performance racing engine, it can be sensitive. What if our three points $(a, f(a))$, $(b, f(b))$, and $(c, f(c))$ happen to lie on a straight line? The formula for IQI doesn't break; instead, the quadratic term in our model happens to be zero, and the "parabola" becomes a line. In this situation, the IQI step gracefully degenerates and produces the exact same estimate as the secant method. It's another beautiful piece of mathematical consistency.

However, sometimes the IQI estimate, while well-defined, might not be a good one. For example, if the function behaves strangely, the parabolic approximation might throw our next estimate far away from the region of interest. A sophisticated algorithm can't just blindly accept every suggestion from its interpolation steps.

This is where the genius of algorithms like ​​Brent's method​​ comes in. Think of it as an expert craftsman with a diverse toolbox. The preferred tool is the powerful and fast IQI. If that's not available (e.g., we don't have three distinct points yet) or if the points are collinear, it uses the trusty secant method. And it always keeps the slow but absolutely reliable ​​bisection method​​ in its back pocket. Before accepting a fast step from IQI or the secant method, it performs crucial safety checks. For instance, is the new guess within the known bracket that's guaranteed to contain the root? If the IQI step proposes a point outside this "safe zone," the algorithm rejects the proposal and takes a conservative bisection step instead, ensuring it never loses track of the root. This combination of speed and safety is what makes Brent's method so powerful and widely used.

No method is perfect, and understanding its limitations is as important as understanding its strengths. The magic of interpolation methods like secant and IQI is predicated on an important assumption: that the function is locally "nice" and can be well-approximated by a low-degree polynomial.

What happens if this isn't true? Consider a function that has a vertical tangent at its root, like $f(x) = \text{sign}(x-2) \sqrt{|x-2|}$. Its derivative blows up to infinity at the root. From the inverse perspective, this means the derivative of the inverse function $g'(y)$ is zero at the root! Our inverse function $x=g(y)$ is perfectly flat at the point we care about. Trying to approximate this with a standard parabola (which has a non-zero slope, unless the vertex is at the root) is a poor fit. The interpolation steps will perform badly, and a robust algorithm like Brent's will be forced to discard their suggestions repeatedly, falling back on slow and steady bisection.

Another potential pitfall is numerical. Look again at the IQI formula. It's filled with denominators like $(f(a)-f(b))$. If our points are close to the root, their function values $f(a)$, $f(b)$, and $f(c)$ might all be very small and very close to each other. When you subtract two nearly identical numbers in a computer, you can lose a tremendous amount of precision in an effect called ​​catastrophic cancellation​​. The small errors in your input values become hugely magnified in the output, and the formula can produce a wildly inaccurate estimate. This is another reason why practical implementations like Brent's method have careful safeguards to check if the denominators are becoming too small, and to switch to a safer method if they are.

By flipping our perspective, we uncovered a deep connection between common root-finding methods and discovered a more stable and elegant way to approach the problem. This journey from a simple line to a safeguarded parabola in a toolbox of algorithms shows how a simple change in viewpoint can unlock powerful new methods, revealing the inherent beauty and unity of numerical science.

In the previous chapter, we explored the "how" of inverse interpolation. We learned the clever trick of swapping the roles of our variables—treating the effect as the cause and the cause as the effect—and then using the familiar machinery of polynomial interpolation to build an approximation of the inverse function. It's a neat piece of numerical machinery. But a tool is only as interesting as the problems it can solve. And it turns out this particular tool is a veritable master key, unlocking doors in a surprising variety of fields.

The real beauty of a scientific principle is not in its abstract formulation, but in its power to connect seemingly disparate ideas. And in that respect, inverse interpolation is a thing of true beauty. It formalizes a way of thinking that is natural to us all: working backward. If I want this result, what did I need to do to get it? This chapter is a journey through that question, and we'll see how this one simple mathematical idea appears again and again, whether we're designing an airplane, locating an earthquake, analyzing data, or even trying to understand the psychology of the stock market.

Let's start with the tangible world of engineering. An engineer's job is often to create something that produces a specific, desired outcome. You don't just build a bridge and see how much load it can take; you design a bridge to take a specific load. You are given the desired effect, and you must determine the necessary cause.

Imagine you are designing the wing of an airplane. You know that for the plane to maintain level flight, it needs to generate a specific amount of lift, which we quantify with a "lift coefficient," $C_L$. You also know that the lift depends on the wing's angle of attack, $\alpha$—the angle between the wing and the oncoming air. Your team has run wind tunnel tests (or complex simulations) and produced a table of data linking various angles of attack to their resulting lift coefficients. The data might look something like this: at $\alpha = -2^\circ$, $C_L = 0$; at $\alpha = 0^\circ$, $C_L \approx 0.22$; at $\alpha = 2^\circ$, $C_L \approx 0.44$, and so on.

Now, the crucial question: for the plane to achieve its target lift coefficient of, say, $C_L^* = 0.5$, what should the angle of attack be? You could try to plot the data, $C_L$ versus $\alpha$, and find a complicated function that fits it, then solve the equation $f(\alpha) = 0.5$. But inverse interpolation says, "Why work so hard?" The question is already phrased in an inverse way. We know the output we want; we're looking for the input. So let's just look at our data table backward! We'll treat $C_L$ as our independent variable and $\alpha$ as our dependent variable. We now have points $(\dots,(0.22, 0), (0.44, 2),\dots)$ and we want to find the value of our new function $\alpha(C_L)$ at the point $C_L = 0.5$. We can feed these "flipped" data points into our interpolation machine, and it directly gives us the required angle of attack. It's elegant, direct, and perfectly suited to the way an engineer thinks.

This same logic applies when we're choosing materials. Consider the stress-strain curve of a metal, a fundamental plot in materials science that shows how much the material deforms (strain, $\epsilon$) under a given load (stress, $\sigma$). For many metals, this curve starts as a steep, straight line (the elastic region) and then, at a point called the yield strength, it abruptly becomes less steep (the plastic region). This "kink" is where the material begins to deform permanently. For safety, it is absolutely critical to know the exact strain at which this yielding begins. The problem is, we are given the material's yield strength, $\sigma_y$, which is a stress value. We need to find the corresponding strain, $\epsilon_y$. Again, this is an inverse problem. We have a function $\sigma(\epsilon)$, and we want to find the input $\epsilon$ that gives the output $\sigma_y$. By taking a few data points $(\epsilon_i, \sigma_i)$ from the curve around the yield point, flipping them to $(\sigma_i, \epsilon_i)$, and performing an inverse interpolation, we can get an excellent estimate for the yield strain. This example is particularly instructive because the real function has a discontinuity in its derivative; it's not a smooth polynomial. Our interpolation is therefore an approximation—a simple, smooth curve we fit through a few points of a more complicated reality—but it's a remarkably effective one for zooming in on the value we need.

The power of "working backward" is not limited to things we build. It's one of the primary tools we use to understand the natural world. A scientist often observes an effect and must deduce the cause.

Think about the terrifying reality of an earthquake. Somewhere, deep in the Earth's crust, rocks have slipped. This event sends out waves through the ground: fast-moving P-waves (Primary) and slower S-waves (Secondary). A seismograph station hundreds of kilometers away records these arrivals. The first thing a seismologist knows is the time difference between the S-wave arrival and the P-wave arrival, the "S-P time." Now, the fundamental question is: how far away was the earthquake?.

Through decades of study, we have built up a reliable model, often presented as a table, that connects epicentral distance, $d$, to the S-P time, $T$. A greater distance means a greater time lag. So, when a seismograph measures a certain S-P time, say 11 seconds, the scientist's task is to invert this relationship to find the distance. They are asking: what distance $d$ corresponds to $T = 11$? This is a perfect setup for inverse interpolation. By treating the table of $(d, T)$ pairs as $(T, d)$ pairs, we can interpolate to find the distance corresponding to any measured time lag. It’s like being a detective: we have the clue (the time lag), and inverse interpolation helps us reconstruct a key part of the event (the distance).

The clues Nature provides are not always so direct. Often, they are buried in noise and randomness. This is the domain of statistics, and here too, our method finds a surprisingly profound application. A central idea in modern statistics is Maximum Likelihood Estimation (MLE). The setup is as follows: we have collected some data—say, a list of measurements $x_1, x_2, \dots, x_n$. We have a hypothesis that this data came from a certain type of probability distribution, like a Gamma distribution, which is described by a parameter, let's call it $k$. The shape of the distribution, and thus the probability of seeing our specific data, depends on the value of $k$. The MLE principle asks: what value of $k$ makes the data we actually observed most likely?

Finding this optimal $k$ involves calculus. We write down the "log-likelihood function," which measures how probable our data is for a given $k$, and we want to find the peak of this function. The peak occurs where the derivative of the log-likelihood function (called the "score function") is equal to zero. So, the deep statistical problem of finding the best parameter for our model has been transformed into a familiar mathematical one: finding the root of a function! And how do we find that root? Often, we use a powerful numerical solver, and as we shall see next, inverse interpolation is the secret engine inside many of these solvers.

So far, we have used inverse interpolation as a direct method for solving a problem. But perhaps its most important role is as a component inside more sophisticated, general-purpose algorithms.

The most fundamental of these is root-finding itself. The problem of finding $x$ such that $f(x)=0$ can be rephrased as an inverse problem: what input $x$ gives the output $0$? If we have a few points $(x_i, y_i)$ where $y_i=f(x_i)$, we can flip them to $(y_i, x_i)$ and ask our interpolator to evaluate the inverse function at $y=0$. This gives us an estimate for the root.

This is a fast and elegant approach, but it can sometimes be reckless. If the function is not well-behaved, a high-degree polynomial interpolation might wiggle wildly and give a terrible estimate. This is where the true genius of modern numerical methods comes in. They don't rely on a single strategy; they combine several in a "hybrid" algorithm. The most famous of these is Brent's method.

You can think of Brent's method as a well-run committee. For its main proposal, it uses the fast, clever, but sometimes overly optimistic inverse quadratic interpolation. This method uses three previous points to create a more accurate parabola for the inverse function. However, before accepting this proposal, the committee chairman runs some checks. Is the proposed new point sensible? Does it stay within the known bounds where the root must lie? Is it making reasonable progress? If inverse quadratic interpolation's proposal fails any of these sanity checks, the chairman dismisses it and turns to a slower but absolutely reliable member: the bisection method, which simply cuts the search interval in half. This combination gives us the best of both worlds: the lightning speed of interpolation when things are going well, and the rock-solid guarantee of convergence from bisection when things get tricky.

This robust root-finding engine, powered by inverse interpolation, is itself a building block for an even grander task: optimization. Whether it's finding the most efficient flight path, the strongest bridge design, or the best parameters for a machine learning model, we are often searching for the minimum (or maximum) of some complex function. Many of the best optimization algorithms work by starting at a point $\mathbf{x}_k$ and then searching along a direction $\mathbf{p}_k$ for the best next point. The question is, how far should we step along this direction? We want to find the step size $\alpha$ that minimizes the function along that line. This is a one-dimensional optimization problem. And how do we find a minimum? We find where the derivative is zero! Once again, a complex, high-dimensional problem has been reduced to a simple, one-dimensional root-finding problem, ready to be solved by our hybrid engine with inverse interpolation at its core.

We end our journey in a place that might seem far removed from the physical laws of engineering and science: the world of finance. Here, the quantities are not distances or strains, but dollars and cents, driven by the complex and often irrational behavior of human beings. Yet, even here, our tool finds a home.

A standard way to estimate the "true" value of a company is a Discounted Cash Flow (DCF) model. This model projects a company's future cash flows and "discounts" them back to the present to arrive at a current value, $P$. A key, and notoriously difficult, input to this model is the assumption about the company's long-term growth rate, $g$. The model is a function $P(g)$. Different assumptions for $g$ lead to different valuations.

Now, let's turn the tables. We don’t need to calculate the price; the stock market does that for us every second. We can observe a company's current stock price, $\widehat{P}$. A fascinating question we can ask is: given the current price $\widehat{P}$, what long-term growth rate $g^*$ is the market implicitly assuming to justify this price? We want to find the $g^*$ such that $P(g^*) = \widehat{P}$.

This is an inverse problem of a very high order. We aren't inverting a simple physical law; we are inverting a complex financial model to probe the collective belief of the market. And the method is exactly the same. We pick a few plausible growth rates, calculate the corresponding prices the model would predict, and then use inverse interpolation on these (price, growth rate) pairs to find the growth rate that corresponds to the actual, observed market price.

From the wing of an airplane to the belief of the market, the intellectual thread is the same. We begin with a question, but instead of attacking it head-on, we take a moment to look at it backward. This simple change in perspective, armed with the tool of inverse interpolation, transforms difficult or impossible problems into straightforward calculations. It is a beautiful testament to the unifying power of mathematical thinking.