Program to implement Inverse Interpolation using Lagrange Formula

0 0 6 minutes read

Given task is to find the value of x for a given y of an unknown function y = f(x) where values of some points (x, y) pairs are given.
Let, y = f(x) be an unknown function where x in an independent variable.
For different values of x, say $x_0, x_1, x_2, ..., x_m ( i.e$ [Tex]x_k, k=0, 1, 2, 3…m) [/Tex]values of respective $y_0, y_1, y_2, ..., y_m ( i.e$ [Tex]y_k = f(x_k), k=0, 1, 2, 3…m) [/Tex]given.
The process of finding the value of the independent variable x for a given value of y lying between two tabulated values with the help of the given set of observation for an unknown function is known as Inverse Interpolation.
This is often used to check whether the correctness of output y for an unknown function f i.e how much argument x for this output y differs from the original input.
The problem of inverse interpolation can be solved using Lagrange’s Formula.
Lagrange’s Formula:
The formula for inverse interpolation is similar to interpolation formula but few changes.
Here to solve the problem of inverse interpolation the places of x and y are interchanged. The formula for inverse interpolation is:
$x = \frac{(y-y_1)(y-y_2)(y-y_3)....(y-y_m)}{(y_0-y_1)(y_0-y_2)(y_0-y_3)....(y_0-y_m)}x_0 + \frac{(y-y_0)(y-y_2)(y-y_3)....(y-y_m)}{(y_1-y_0)(y_1-y_2)(y_1-y_3)....(y_1-y_m)}x_1 + \frac{(y-y_0)(y-y_1)(y-y_3)....(y-y_m)}{(y_2-y_0)(y_2-y_1)(y_2-y_3)....(y_2-y_m)}x_2 + ...... + \frac{(y-y_0)(y-y_1)(y-y_2)(y-y_3)....(y-y_m)}{(y_m-y_0)(y_m-y_1)(y_m-y_2)((y_m-y_3)....(y_m-y_{m-1})}x_m$
This method can even be used when the points are unequally spaced. Here x is expressed as a function of y.
Examples:

Input: Find the value of x where y = 4.5 and the given points are:

$\begin{tabular}{|l|l|l|} \hline k & x_k & y_k \\ \hline 0 & 1.27 & 2.3 \\ \hline 1 & 2.25 & 2.95 \\ \hline 2 & 2.5 & 3.5 \\ \hline 3 & 3.6 & 5.1 \\ \hline \end{tabular}$

Output: 2.79501
Explanation: Here num of data points given = 4 and y = 4.5
So, putting the values of all x and y in the inverse interpolation formula given above we get,
$x = \frac{(4.5-2.95)(4.5-3.5)(4.5-5.1)}{2.3-2.95)(2.3-3.5)(2.3-5.1)}\cdot1.27+\frac{(4.5-2.3)(4.5-3.5)(4.5-5.1)}{(2.95-2.3)(2.95-3.5)(2.95-5.1)}\cdot2.25+\frac{(4.5-2.3)(4.5-2.95)(4.5-5.1)}{(3.5-2.3)(3.5-2.95)(3.5-5.1)}\cdot2.5+\frac{(4.5-2.3)(4.5-2.95)(4.5-3.5)}{(5.1-2.3)(5.1-2.95)(5.1-3.5)}\cdot3.6$
From here we get,
The value of x = 2.79501 where the value of y = 4.5

Graph:

Algorithm:
Here, data is a list of points consisting of x and y and n is the num of data points.

STEP – 1 : Initialize the final value x = 0
STEP – 2 : FOR i = 1 to n do
    STEP – 3 : Initialize xi = data[i].x
    STEP – 4 : FOR j = 1 to n do
        STEP – 5 : IF i != j do
            STEP – 6 : Multiply xi by ( y – data[j].y ) and divide by ( data[i].y – data[j].y )
        ENDIF
    ENDFOR
    STEP – 7 : Add xi to x
ENDFOR
STEP – 8 : Return final value of x
STEP – 9 : END

Implementation:

C++

// C++ code for solving inverse interpolation
 
#include <bits/stdc++.h>
using namespace std;
 
// Consider a structure
// to keep each pair of
// x and y together
struct Data {
    double x, y;
};
 
// Function to calculate
// the inverse interpolation
 
double inv_interpolate(Data d[], int n, double y)
{
    // Initialize final x
    double x = 0;
 
    int i, j;
 
    for (i = 0; i < n; i++) {
 
        // Calculate each term
        // of the given formula
        double xi = d[i].x;
        for (j = 0; j < n; j++) {
 
            if (j != i) {
                xi = xi
                     * (y - d[j].y)
                     / (d[i].y - d[j].y);
            }
        }
 
        // Add term to final result
        x += xi;
    }
 
    return x;
}
 
// Driver Code
int main()
{
 
    // Sample dataset of 4 points
    // Here we find the value
    // of x when y = 4.5
    Data d[] = { { 1.27, 2.3 },
                 { 2.25, 2.95 },
                 { 2.5, 3.5 },
                 { 3.6, 5.1 } };
 
    // Size of dataset
    int n = 4;
 
    // Sample y value
    double y = 4.5;
 
    // Using the Inverse Interpolation
    // function to find the
    // value of x when y = 4.5
    cout << "Value of x at y = 4.5 : "
         << inv_interpolate(d, n, y);
 
    return 0;
}

Java

// Java code for solving inverse interpolation
class GFG
{
 
// Consider a structure
// to keep each pair of
// x and y together
static class Data
{
    double x, y;
 
    public Data(double x, double y)
    {
        super();
        this.x = x;
        this.y = y;
    }
     
};
 
// Function to calculate
// the inverse interpolation
static double inv_interpolate(Data []d, int n, double y)
{
    // Initialize final x
    double x = 0;
 
    int i, j;
 
    for (i = 0; i < n; i++)
    {
 
        // Calculate each term
        // of the given formula
        double xi = d[i].x;
        for (j = 0; j < n; j++) 
        {
 
            if (j != i) 
            {
                xi = xi
                    * (y - d[j].y)
                    / (d[i].y - d[j].y);
            }
        }
 
        // Add term to final result
        x += xi;
    }
    return x;
}
 
// Driver Code
public static void main(String[] args)
{
 
    // Sample dataset of 4 points
    // Here we find the value
    // of x when y = 4.5
    Data []d = { new Data( 1.27, 2.3 ),
            new Data( 2.25, 2.95 ),
            new Data( 2.5, 3.5 ),
            new Data( 3.6, 5.1 ) };
 
    // Size of dataset
    int n = 4;
 
    // Sample y value
    double y = 4.5;
 
    // Using the Inverse Interpolation
    // function to find the
    // value of x when y = 4.5
    System.out.printf("Value of x at y = 4.5 : %.5f"
        , inv_interpolate(d, n, y));
}
}
 
// This code is contributed by Rajput-Ji

Python3

# Python3 code for solving 
# inverse interpolation
 
# Consider a structure
# to keep each pair of
# x and y together
class Data:
    def __init__(self, x, y):
        self.x = x
        self.y = y
 
# Function to calculate
# the inverse interpolation
def inv_interpolate(d: list, n: int, 
                    y: float) -> float:
 
    # Initialize final x
    x = 0
 
    for i in range(n):
 
        # Calculate each term
        # of the given formula
        xi = d[i].x
        for j in range(n):
            if j != i:
                xi = (xi * (y - d[j].y) /
                      (d[i].y - d[j].y))
 
        # Add term to final result
        x += xi
    return x
 
# Driver Code
if __name__ == "__main__":
 
    # Sample dataset of 4 points
    # Here we find the value
    # of x when y = 4.5
    d = [Data(1.27, 2.3), 
         Data(2.25, 2.95), 
         Data(2.5, 3.5), 
         Data(3.6, 5.1)]
 
    # Size of dataset
    n = 4
 
    # Sample y value
    y = 4.5
 
    # Using the Inverse Interpolation
    # function to find the
    # value of x when y = 4.5
    print("Value of x at y = 4.5 :", 
           round(inv_interpolate(d, n, y), 5))
 
# This code is contributed by
# sanjeev2552

C#

// C# code for solving inverse interpolation
using System;
 
class GFG
{
 
// Consider a structure to keep 
// each pair of x and y together
class Data
{
    public double x, y;
 
    public Data(double x, double y)
    {
        this.x = x;
        this.y = y;
    }
};
 
// Function to calculate the 
// inverse interpolation
static double inv_interpolate(Data []d, 
                       int n, double y)
{
    // Initialize readonly x
    double x = 0;
 
    int i, j;
 
    for (i = 0; i < n; i++)
    {
 
        // Calculate each term
        // of the given formula
        double xi = d[i].x;
        for (j = 0; j < n; j++) 
        {
            if (j != i) 
            {
                xi = xi * (y - d[j].y) / 
                              (d[i].y - d[j].y);
            }
        }
 
        // Add term to readonly result
        x += xi;
    }
    return x;
}
 
// Driver Code
public static void Main(String[] args)
{
 
    // Sample dataset of 4 points
    // Here we find the value
    // of x when y = 4.5
    Data []d = {new Data(1.27, 2.3),
                new Data(2.25, 2.95),
                new Data(2.5, 3.5),
                new Data(3.6, 5.1)};
 
    // Size of dataset
    int n = 4;
 
    // Sample y value
    double y = 4.5;
 
    // Using the Inverse Interpolation
    // function to find the
    // value of x when y = 4.5
    Console.Write("Value of x at y = 4.5 : {0:f5}", 
                         inv_interpolate(d, n, y));
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
// javascript code for solving inverse interpolation    
// Consider a structure
    // to keep each pair of
    // x and y together
     class Data {
         
        constructor(x , y) {
            this.x = x;
            this.y = y;
        }
 
    };
 
    // Function to calculate
    // the inverse interpolation
    function inv_interpolate( d , n , y) 
    {
     
        // Initialize final x
        var x = 0;
 
        var i, j;
 
        for (i = 0; i < n; i++) {
 
            // Calculate each term
            // of the given formula
            var xi = d[i].x;
            for (j = 0; j < n; j++) {
 
                if (j != i) {
                    xi = xi * (y - d[j].y) / (d[i].y - d[j].y);
                }
            }
 
            // Add term to final result
            x += xi;
        }
        return x;
    }
 
    // Driver Code
     
        // Sample dataset of 4 points
        // Here we find the value
        // of x when y = 4.5
        var d = [ new Data(1.27, 2.3), new Data(2.25, 2.95), new Data(2.5, 3.5), new Data(3.6, 5.1) ];
 
        // Size of dataset
        var n = 4;
 
        // Sample y value
        var y = 4.5;
 
        // Using the Inverse Interpolation
        // function to find the
        // value of x when y = 4.5
        document.write("Value of x at y = 4.5 : ", inv_interpolate(d, n, y).toFixed(5));
 
// This code is contributed by gauravrajput1 
</script>

Output:

Value of x at y = 4.5 : 2.79501

Complexity: The time complexity of the given solution is O(n^2) and space complexity is O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!