Интерполяционный многочлен Лагранжа

Интерполяцио́нный многочле́н Лагра́нжа — многочлен минимальной степени, принимающий заданные значения в заданном наборе точек, то есть решающий задачу интерполяции.

Определение править

 
Интерполяционный многочлен Лагранжа для четырёх точек (-9,5), (-4,2), (-1,-2) и (7,9), а также полиномы  , каждый из которых проходит через одну из выделенных точек, и принимает нулевое значение в остальных.

Пусть задана   пара чисел   где все   различны. Требуется построить многочлен   степени не более  , для которого  .

Общий случай править

Ж. Л. Лагранж предложил следующий способ вычисления таких многочленов:

 

где базисные полиномы   определяются по формуле

 

Для любого   многочлен   имеет степень   и

 

Отсюда следует, что  , являющийся линейной комбинацией многочленов  , имеет степень не больше   и  .

Случай равноотстоящих узлов интерполяции править

Пусть узлы интерполяции   являются равноотстоящими, то есть выражаются через начальную точку   и некоторую фиксированную положительную величину   следующим образом:

 

Отсюда следует, что

 

Подставляя эти выражения в формулу для базисного полинома и вынося   за знаки произведения в числителе и знаменателе, получим

 

Теперь можно ввести замену переменной

 

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

 

Данные величины называются коэффициентами Лагранжа. Они не зависят ни от  , ни от   и потому могут быть вычислены заранее и записаны в виде таблиц. Недостатком данного подхода является факториальная сложность числителя и знаменателя, что требует использования длинной арифметики.

Остаточный член править

Если считать числа   значениями некоторой функции   в узлах  , то ошибка интерполирования функции   многочленом   равна

 

где   — некоторая средняя точка между наименьшим и наибольшим из чисел  . Полагая  , можно записать

 

Единственность править

Существует единственный многочлен степени не превосходящей  , принимающий заданные значения в   заданной точке.

Это утверждение является обобщением того факта, что через любые две точки проходит единственная прямая.

С точки зрения линейной алгебры править

На единственность интерполяционного многочлена можно также взглянуть с точки зрения СЛАУ. Рассмотрим систему уравнений  . В явном виде она записывается как

 

Её можно переписать в виде системы уравнений   с неизвестным вектором  :

 

Матрица   в такой системе является матрицей Вандермонда и её определитель равен  . Соответственно, если все точки   различны, то матрица невырождена и система обладает единственным решением.

С точки зрения китайской теоремы об остатках править

По теореме Безу остаток от деления   на   равен  . Таким образом, всю систему можно воспринимать в виде системы сравнений:

 

По китайской теореме об остатках у такой системы есть единственное решение по модулю  , то есть, заданная система однозначно определяет многочлен степени не выше  . Такое представление многочлена в виде наборов остатков по модулям мономов аналогично представлению числа в виде остатков от деления на простые модули в системе остаточных классов. При этом явная формула для многочлена Лагранжа также может быть получена в соответствии с формулами китайской теоремы:  , где   и  .

Пример править

 
Приближение функции   (синяя линия) многочленом   (зелёная линия).

Найдем формулу интерполяции для   имеющей следующие значения:

 
 
 
 
 
 

Получим

 

Реализация общего случая на языке программирования Python править

import numpy as np

# данные для примера
xi = np.array([-1.5, -0.75, 0, 0.75, 1.5])
yi = np.array([-14.1014, -0.931596, 0, 0.931596, 14.1014])


def get_coefficients(_pl: int, _xi: np.ndarray):
    '''
    Определение коэффициентов для множителей базисных полиномов l_i
    :param _pl: индекс базисного полинома
    :param _xi: массив значений x
    :return:
    '''
    n = int(_xi.shape[0])
    coefficients = np.empty((n, 2), dtype=float)
    for i in range(n):
        if i == _pl:
            coefficients[i][0] = float('inf')
            coefficients[i][1] = float('inf')
        else:
            coefficients[i][0] = 1 / (_xi[_pl] - _xi[i])
            coefficients[i][1] = -_xi[i] / (_xi[_pl] - _xi[i])
    filtered_coefficients = np.empty((n - 1, 2), dtype=float)
    j = 0
    for i in range(n):
        if coefficients[i][0] != float('inf'):
            # изменение последовательности, степень увеличивается
            filtered_coefficients[j][0] = coefficients[i][1]
            filtered_coefficients[j][1] = coefficients[i][0]
            j += 1
    return filtered_coefficients


def get_polynomial_l(_xi: np.ndarray):
    '''
    Определение базисных полиномов
    :param _xi: массив значений x
    :return:
    '''
    n = int(_xi.shape[0])
    pli = np.zeros((n, n), dtype=float)
    for pl in range(n):
        coefficients = get_coefficients(pl, _xi)
        for i in range(1, n - 1):  # проходим по массиву coefficients
            if i == 1:  # на второй итерации занимаются 0-2 степени
                pli[pl][0] = coefficients[i - 1][0] * coefficients[i][0]
                pli[pl][1] = coefficients[i - 1][1] * coefficients[i][0] + coefficients[i][1] * coefficients[i - 1][0]
                pli[pl][2] = coefficients[i - 1][1] * coefficients[i][1]
            else:
                clone_pli = np.zeros(n, dtype=float)
                for val in range(n):
                    clone_pli[val] = pli[pl][val]
                zeros_pli = np.zeros(n, dtype=float)
                for j in range(n-1):  # проходим по строке pl массива pli
                    product_1 = clone_pli[j] * coefficients[i][0]
                    product_2 = clone_pli[j] * coefficients[i][1]
                    zeros_pli[j] += product_1
                    zeros_pli[j+1] += product_2
                for val in range(n):
                    pli[pl][val] = zeros_pli[val]
    return pli

def get_polynomial(_xi: np.ndarray, _yi: np.ndarray):
    '''
    Определение интерполяционного многочлена Лагранжа
    :param _xi: массив значений x
    :param _yi: массив значений y
    :return:
    '''
    n = int(_xi.shape[0])
    polynomial_l = get_polynomial_l(_xi)
    for i in range(n):
        for j in range(n):
            polynomial_l[i][j] *= _yi[i]
    L = np.zeros(n, dtype=float)
    for i in range(n):
        for j in range(n):
            L[i] += polynomial_l[j][i]
    return L

# результат в виде массива коэффициентов многочлена при x в порядке увеличения степени
# [ 0.         -1.47747378  0.          4.8348476   0.        ]
# т.е. результирующий многочлен имеет вид: y(x) = -1.47747378*x + 4.8348476*x^3

Применения править

 
Многочлены Лагранжа степеней от нулевой до пятой для функции  

Численное интегрирование править

Пусть для функции   известны значения   в некоторых точках. Тогда можно интерполировать эту функцию методом Лагранжа:

 

Полученное выражение можно использовать для приближённого вычисления определённого интеграла от функции  :

 

Значения интегралов от   не зависят от   и их можно вычислить заранее с использованием последовательности  .

Литература править

Ссылки править

  • М. А. Тынкевич. Глава 7.6.1. Интерполяционный многочлен Лагранжа // Численные методы анализа. — Кемерово, 2002. — ISBN 5-89070-042-1. (недоступная ссылка)
  • А. Г. Хованский. Полиномы Лагранжа и их применения. Видео-лекция. VI Летняя школа «Современная математика», Дубна, 2006.

См. также править