Рубрики

Интерполяция Лагранжа

Что такое интерполяция?
Интерполяция — это метод поиска новых точек данных в диапазоне дискретного набора известных точек данных (Source Wiki ). Другими словами, интерполяция — это метод оценки значения математической функции для любого промежуточного значения независимой переменной.
Например, в данной таблице нам дан 4 набора дискретных точек данных для неизвестной функции f (x):

Как найти?
Здесь мы можем применить интерполяционную формулу Лагранжа, чтобы получить наше решение.
Интерполяционная формула Лагранжа:
Если y = f (x) принимает значения y0, y1,…, yn, соответствующие x = x0, x1,…, xn, то

Этот метод предпочтителен по сравнению с аналогами, такими как метод Ньютона, потому что он применим даже для неравномерно расположенных значений x.

Мы можем использовать методы интерполяции, чтобы найти промежуточную точку данных, скажем, при х = 3.

C ++

// C ++ программа для реализации интерполяции Лагранжа
#include<bits/stdc++.h>

using namespace std;

  
// Для представления точки данных, соответствующей x и y = f (x)

struct Data

{

    int x, y;

};

  
// функция для интерполяции заданных точек данных по формуле Лагранжа
// xi соответствует новой точке данных, значение которой должно быть получено
// n представляет количество известных точек данных

double interpolate(Data f[], int xi, int n)

{

    double result = 0; // Инициализировать результат

  

    for (int i=0; i<n; i++)

    {

        // Вычисляем отдельные термины вышеприведенной формулы

        double term = f[i].y;

        for (int j=0;j<n;j++)

        {

            if (j!=i)

                term = term*(xi - f[j].x)/double(f[i].x - f[j].x);

        }

  

        // Добавить текущий термин в результат

        result += term;

    }

  

    return result;

}

  
// функция драйвера для проверки программы

int main()

{

    // создаем массив из 4 известных точек данных

    Data f[] = {{0,2}, {1,3}, {2,12}, {5,147}};

  

    // Использование функции интерполяции для получения точки данных

    // соответствует x = 3

    cout << "Value of f(3) is : " << interpolate(f, 3, 5);

  

    return 0;

}

Джава

// Java-программа для реализации
// интерполяции Лагранжа

  

import java.util.*;

  

class GFG

{

  
// Для представления точки данных
// соответствует x и y = f (x)

static class Data

{

    int x, y;

  

    public Data(int x, int y) 

    {

        super();

        this.x = x;

        this.y = y;

    }

      
};

  
// функция для интерполяции заданного
// точки данных по формуле Лагранжа
// xi соответствует новой точке данных
// чье значение должно быть получено n
// представляет количество известных точек данных

static double interpolate(Data f[], int xi, int n)

{

    double result = 0; // Инициализировать результат

  

    for (int i = 0; i < n; i++)

    {

        // Вычисляем отдельные термины вышеприведенной формулы

        double term = f[i].y;

        for (int j = 0; j < n; j++)

        {

            if (j != i)

                term = term*(xi - f[j].x) / (f[i].x - f[j].x);

        }

  

        // Добавить текущий термин в результат

        result += term;

    }

  

    return result;

}

  
// Код драйвера

public static void main(String[] args)

{

    // создаем массив из 4 известных точек данных

    Data f[] = {new Data(0, 2), new Data(1, 3), 

                new Data(2, 12), new Data(5, 147)};

  

    // Использование функции интерполяции для получения

    // точка данных, соответствующая x = 3

    System.out.print("Value of f(3) is : "

                    (int)interpolate(f, 3, 4));

}
}

  
// Этот код предоставлен 29AjayKumar

C #

// C # программа для реализации
// интерполяции Лагранжа

using System;

  

class GFG

{

  
// Для представления точки данных
// соответствует x и y = f (x)

class Data

{

    public int x, y;

    public Data(int x, int y) 

    {

        this.x = x;

        this.y = y;

    }

};

  
// функция для интерполяции заданного
// точки данных по формуле Лагранжа
// xi соответствует новой точке данных
// чье значение должно быть получено n
// представляет количество известных точек данных

static double interpolate(Data []f, 

                          int xi, int n)

{

    double result = 0; // Инициализировать результат

  

    for (int i = 0; i < n; i++)

    {

        // Вычисляем отдельные термины

        // вышеуказанной формулы

        double term = f[i].y;

        for (int j = 0; j < n; j++)

        {

            if (j != i)

                term = term * (xi - f[j].x) / 

                          (f[i].x - f[j].x);

        }

  

        // Добавить текущий термин в результат

        result += term;

    }

    return result;

}

  
// Код драйвера

public static void Main(String[] args)

{

    // создаем массив из 4 известных точек данных

    Data []f = {new Data(0, 2), 

                new Data(1, 3), 

                new Data(2, 12), 

                new Data(5, 147)};

  

    // Использование функции интерполяции для получения

    // точка данных, соответствующая x = 3

    Console.Write("Value of f(3) is : "

                  (int)interpolate(f, 3, 4));

}
}

  
// Этот код предоставлен PrinciRaj1992

Выход:

Value of f(3) is : 35

Сложность:
Временная сложность вышеуказанного решения составляет O (n 2 ), а вспомогательное пространство — O (1).

Ссылки:
https://en.wikipedia.org/wiki/Lagrange_polynomial
Высшая инженерная математика, доктор BS Grewal
https://mat.iitm.ac.in/home/sryedida/public_html/caimna/interpolation/lagrange.html

Эта статья предоставлена Ашутошем Кумаром . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Интерполяция Лагранжа

0.00 (0%) 0 votes