Интерполяционный многочлен Лагранжа — Википедия
Интерполяцио́нный многочле́н Лагра́нжа — многочлен минимальной степени, принимающий заданные значения в заданном наборе точек, то есть решающий задачу интерполяции.
Определение
[править | править код]Пусть задана пара чисел где все различны. Требуется построить многочлен степени не более , для которого .
Общий случай
[править | править код]Ж. Л. Лагранж предложил следующий способ вычисления таких многочленов:
где базисные полиномы определяются по формуле
Для любого многочлен имеет степень и
Отсюда следует, что , являющийся линейной комбинацией многочленов , имеет степень не больше и .
Случай равноотстоящих узлов интерполяции
[править | править код]Пусть узлы интерполяции являются равноотстоящими, то есть выражаются через начальную точку и некоторую фиксированную положительную величину следующим образом:
Отсюда следует, что
Подставляя эти выражения в формулу для базисного полинома и вынося за знаки произведения в числителе и знаменателе, получим
Теперь можно ввести замену переменной
и получить выражение для базисных полиномов через , которое строится с использованием только целочисленной арифметики:
Данные величины называются коэффициентами Лагранжа. Они не зависят ни от , ни от и потому могут быть вычислены заранее и записаны в виде таблиц. Недостатком данного подхода является факториальная сложность числителя и знаменателя, что требует использования длинной арифметики.
Остаточный член
[править | править код]Если считать числа значениями некоторой функции в узлах , то ошибка интерполирования функции многочленом равна
где — некоторая средняя точка между наименьшим и наибольшим из чисел . Полагая , можно записать
Единственность
[править | править код]Существует единственный многочлен степени не превосходящей , принимающий заданные значения в заданной точке.
Предположим, что существуют два различных многочлена и степени не более , для которых верно, что для пар чисел где все различны, Рассмотрим многочлен . Подставляя в него (), получаем, что . Таким образом, многочлен имеет корней и все они различны. Следовательно , так как ненулевой многочлен степени не превосходящей имеет не более корней. Следовательно, . ■
Это утверждение является обобщением того факта, что через любые две точки проходит единственная прямая.
С точки зрения линейной алгебры
[править | править код]На единственность интерполяционного многочлена можно также взглянуть с точки зрения СЛАУ. Рассмотрим систему уравнений . В явном виде она записывается как
Её можно переписать в виде системы уравнений с неизвестным вектором :
Матрица в такой системе является матрицей Вандермонда и её определитель равен . Соответственно, если все точки различны, то матрица невырождена и система обладает единственным решением.
С точки зрения китайской теоремы об остатках
[править | править код]По теореме Безу остаток от деления на равен . Таким образом, всю систему можно воспринимать в виде системы сравнений:
По китайской теореме об остатках у такой системы есть единственное решение по модулю , то есть, заданная система однозначно определяет многочлен степени не выше . Такое представление многочлена в виде наборов остатков по модулям мономов аналогично представлению числа в виде остатков от деления на простые модули в системе остаточных классов. При этом явная формула для многочлена Лагранжа также может быть получена в соответствии с формулами китайской теоремы: , где и .
Пример
[править | править код]Найдем формулу интерполяции для имеющей следующие значения:
Получим
Реализация общего случая на языке программирования 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
Применения
[править | править код]Численное интегрирование
[править | править код]Пусть для функции известны значения в некоторых точках. Тогда можно интерполировать эту функцию методом Лагранжа:
Полученное выражение можно использовать для приближённого вычисления определённого интеграла от функции :
Значения интегралов от не зависят от и их можно вычислить заранее с использованием последовательности .
Литература
[править | править код]- Березин, И. С., Жидков Н. П. Методы вычислений. Том I. — 2-е изд., стереотипное — М.: Физматлит. 1962.
Ссылки
[править | править код]- М. А. Тынкевич. Глава 7.6.1. Интерполяционный многочлен Лагранжа // Численные методы анализа. — Кемерово, 2002. — ISBN 5-89070-042-1. (недоступная ссылка)
- А. Г. Хованский. Полиномы Лагранжа и их применения. Видео-лекция. VI Летняя школа «Современная математика», Дубна, 2006.