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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Определение

[править | править код]
Интерполяционный многочлен Лагранжа для четырёх точек (-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.