На этом изображении показаны четыре точки ((−9, 5), (−4, 2), (−1, - 2), (7, 9)), (кубический) интерполяционный многочлен L (x) (штриховой, черный), который представляет собой сумму масштабированных базисных многочленов y 0ℓ0(x), y 1ℓ1(x), y 2ℓ2(x) и y 3ℓ3(x). Полином интерполяции проходит через все четыре контрольные точки, и каждый масштабированный базисный полином проходит через свою соответствующую контрольную точку и равен 0, где x соответствует трем другим контрольным точкам.
В численном анализе, Полиномы Лагранжа используются для полиномиальной интерполяции. Для заданного набора точек без двух значения равны, полином Лагранжа - это полином самой низкой степени, который принимает для каждого значения соответствующее значение , чтобы функции совпадали в каждой точке.
Хотя метод был назван в честь Жозефа-Луи Лагранжа, опубликовавшего его в 1795 году, метод был впервые обнаружен в 1779 году Эдвардом Уорингом. формула, опубликованная в 1783 году Леонардом Эйлером.
Использование полиномов Лагранжа включает в себя метод Ньютона-Котеса числового интегрирования и схему совместного использования секретов Шамира в криптография.
Интерполяция Лагранжа чувствительна к феномену Рунге больших колебаний. Поскольку изменение точек требует пересчета всего интерполянта, часто вместо этого проще использовать полиномы Ньютона.
Содержание
- 1 Определение
- 2 Доказательство
- 3 Перспектива из линейной алгебры
- 4 Примеры
- 4.1 Пример 1
- 4.2 Пример 2
- 4.3 Примечания
- 5 Барицентрический форма
- 6 Остаток в формуле интерполяции Лагранжа
- 7 Производные
- 8 Конечные поля
- 9 См. также
- 10 Ссылки
- 11 Внешние ссылки
Определение
Здесь мы строим базисные функции Лагранжа 1-го, 2-го и 3-го порядков в двуединичной области. Линейные комбинации базисных функций Лагранжа используются для построения интерполяционных полиномов Лагранжа. Базисные функции Лагранжа обычно используются в
анализе конечных элементов в качестве базисных функций формы элементов. Кроме того, часто используется двуединичная область в качестве естественного пространства для определения конечных элементов.
Учитывая набор из k + 1 точек данных
где нет двух одинаковых , интерполяционный многочлен в форме Лагранжа является линейная комбинация
базисных многочленов Лагранжа
где . Обратите внимание, как, учитывая исходное предположение, что нет двух одинаковых , тогда (когда ) , поэтому это выражение всегда четко определено. Пары причин с недопустимы, если нет функция интерполяции такая, что будет существовать; функция может получить только одно значение для каждого аргумента . С другой стороны, если также , тогда эти две точки будут фактически одной точкой.
Для всех , включает термин в числителе, поэтому весь продукт будет равен нулю при :
На с другой стороны,
Другими словами, все базисные полиномы равны нулю при , за исключением , для которого он считает, что , потому что в нем отсутствует срок.
Отсюда следует, что , поэтому в каждой точке , , показывая, что точно интерполирует функцию.
Доказательство
Искомая функция L (x) является полиномом от x наименьшей степени, который интерполирует данный набор данных; то есть принимает значение y j при соответствующем x j для всех точек данных j:
Обратите внимание на следующее:
- In в произведении есть k множителей, и каждый множитель содержит один x, поэтому L (x) (который является суммой этих многочленов степени k) должен быть полиномом от степень не выше k.
Разверните этот продукт. Поскольку в продукте отсутствует член, где m = j, если i = j, то все термины, которые появляются, имеют вид . Кроме того, если i ≠ j, то один член в продукте будет (для m = i), , обнуление всего продукта. Итак,
где - это дельта Кронекера. Итак:
Таким образом, функция L (x) является многочленом со степенью не выше k и где L (x i) = y i.
Кроме того, интерполяционный полином уникален, как показано теоремой о неразрывности в статье интерполяция полиномов.
Также верно, что:
, поскольку он должен быть полиномом степени не выше k и проходить через все эти k + 1 точки данных:
в результате получается горизонтальная линия, поскольку прямая линия - единственный многочлен степени меньше k + 1, который проходит через k + 1 выровненные точки.
Перспектива из линейной алгебры
Решение задачи интерполяции приводит к проблеме в линейной алгебре, которая сводится к обращению матрицы. Используя стандартный мономиальный базис для нашего интерполяционного полинома , мы должны инвертировать матрицу Вандермонда найти для коэффициентов из . Выбирая лучший базис, базис Лагранжа, , мы просто получаем единичную матрицу, , которая является собственной инверсией: базис Лагранжа автоматически инвертирует аналог матрицы Вандермонда.
Эта конструкция аналогична китайской теореме об остатках. Вместо того, чтобы проверять остатки целых чисел по модулю простых чисел, мы проверяем остатки многочленов при делении на линеары.
Кроме того, при большом порядке быстрое преобразование Фурье может использоваться для определения коэффициентов интерполированного полинома.
Примеры
Пример 1
Мы хотим интерполировать ƒ (x) = x в диапазоне 1 ≤ x ≤ 3, учитывая эти три точки:
Интерполирующий полином равен:
Пример 2
Мы хотим интерполировать ƒ (x) = x в диапазоне 1 ≤ x ≤ 4, учитывая эти четыре точки:
| |
| |
| |
| |
Интерполирующий многочлен:
Примечания
Пример расхождения интерполяции для набора Полиномы Лагранжа.
Форма Лагранжа интерполяционного полинома показывает линейный характер полиномиальной интерполяции и уникальность интерполяционного полинома. Поэтому ему отдают предпочтение в доказательствах и теоретических аргументах. Уникальность также можно увидеть из обратимости матрицы Вандермонда из-за того, что детерминант Вандермонда.
не обращается в нуль. Но, как видно из построения, каждый раз узел x k изменения, все базисные полиномы Лагранжа должны быть пересчитаны. Лучшая форма интерполяционного полинома для практических (или вычислительных) целей - это барицентрическая форма интерполяции Лагранжа (см. Ниже) или полиномов Ньютона.
Лагранжа и другой интерполяции в равноотстоящих точках, как в примере выше, дают полином, колеблющийся выше и ниже истинной функции. Это поведение имеет тенденцию расти с увеличением количества точек, что приводит к расхождению, известному как феномен Рунге ; проблема может быть устранена путем выбора точек интерполяции в узлах Чебышева.
. Полиномы базиса Лагранжа могут использоваться в численном интегрировании для получения формул Ньютона – Котеса.
Барицентрической формы
Использование
мы можем переписать базисные полиномы Лагранжа как
или, определяя барицентрические веса
мы можем просто написать
, который обычно называют первой формой барицентрической интерполяции формула.
Преимущество этого представления состоит в том, что теперь интерполяционный полином можно оценить как
который, если веса были предварительно вычислены, требуется только операций (оценка и веса ) в отличие от для оценки лагранжа базисные многочлены по отдельности.
Формула барицентрической интерполяции также может быть легко обновлена, чтобы включить новый узел , разделив каждый из , by и построение нового , как указано выше.
Мы можем еще больше упростить первую форму, сначала рассмотрев барицентрическую интерполяцию постоянной функции :
Деление by не изменяет интерполяцию, но дает
, которая упоминается как вторая форма или истинная форма формулы барицентрической интерполяции. Эта вторая форма имеет то преимущество, что не нужно оценивать для каждой оценки .
Остаток в формуле интерполяции Лагранжа
При интерполяции заданной функции f полиномом степени k в узлах получаем остаток который может быть выражен как
где - это обозначение для разделенных разностей. В качестве альтернативы, остаток может быть выражен как контурный интеграл в комплексной области как
Остаток может быть связан как
Вывод
Очевидно, равен нулю в узлах. Найти в точке . Определите новую функцию и выберите (Это обеспечивает в узлах), где - константа, которую мы должны определить для заданного . Теперь имеет нулей (во всех узлах и ) между и (включая конечные точки). Если предположить, что равно раз дифференцируемым, и являются многочленами и, следовательно, бесконечно дифференцируемы. По теореме Ролля имеет нули, имеет нули... имеет 1 ноль, скажем,
- F (k + 1) (ξ) = f (k + 1) (ξ) - L (к + 1) (ξ) - R (k + 1) (ξ) {\ displaystyle F ^ {(k + 1)} (\ xi) = f ^ {(k + 1)} ( \ xi) -L ^ {(k + 1)} (\ xi) -R ^ {(k + 1)} (\ xi)}
- L (k + 1) = 0, R (k + 1) = C ⋅ (к + 1)! {\ displaystyle L ^ {(k + 1)} = 0, R ^ {(k + 1)} = C \ cdot (k + 1)!}(Поскольку наибольшая степень x {\ displaystyle x}in R (x) {\ displaystyle R (x)}is k + 1 {\ displaystyle k + 1})
- 0 знак равно е (к + 1) (ξ) - С ⋅ (к + 1)! {\ Displaystyle 0 = f ^ {(k + 1)} (\ xi) -C \ cdot (k + 1)!}
Уравнение можно переформулировать так:
- C = f (k + 1) (ξ) (k + 1)! {\ Displaystyle C = {\ frac {f ^ {(k + 1)} (\ xi)} {(k + 1)!}}}
Производные
d {\ displaystyle d}-ые производные полинома Лагранжа могут быть записаны как
- L (d) (x): знак равно ∑ j знак равно 0 kyj ℓ j (d) (x) {\ displaystyle L ^ {(d)} (x): = \ sum _ {j = 0} ^ {k} y_ {j} \ ell _ {j} ^ {(d)} (x)}.
Для первой производной коэффициенты определяются как
- ℓ j (1) (x): = ∑ i = 0 я ≠ jk [1 xj - xi ∏ м знак равно 0 м ≠ (i, j) kx - xmxj - xm] {\ displaystyle \ ell _ {j} ^ {(1)} (x): = \ сумма _ {\ begin {smallmatrix} i = 0 \\ i \ not = j \ end {smallmatrix}} ^ {k} \ left [{\ frac {1} {x_ {j} -x_ {i}}} \ prod _ {\ begin {smallmatrix} m = 0 \\ m \ not = (i, j) \ end {smallmatrix}} ^ {k} {\ frac {x-x_ {m}} {x_ {j} -x_ {m}}} \ right]}
и для второй производной
- ℓ j (2) (x): = ∑ i = 0 i ≠ jk 1 xj - xi [∑ m = 0 m ≠ (i, j) k (1 xj - xm ∏ l = 0 l ≠ (i, j, m) kx - xlxj - xl)] {\ displaystyle \ ell _ {j} ^ {(2)} (x): = \ sum _ {\ begin {smallmatrix} i = 0 \\ i \ neq j \ end {smallmatrix}} ^ {k} {\ frac {1} {x_ {j} -x_ {i}}} \ left [\ sum _ {\ begin {smallmatrix} m = 0 \\ m \ neq (i, j) \ end {smallmatrix}} ^ {k} \ left ({\ frac {1} {x_ {j} -x_ {m}}} \ prod _ {\ begin {smallmatrix} l = 0 \\ l \ neq (i, j, m) \ end {smallmatrix}} ^ {k} {\ frac {x-x_ {l}} {x_ {j} -x_ {l}}} \ right) \ right]}.
С помощью рекурсии можно вычислять формулы для высших производных.
Конечные поля
Многочлен Лагранжа также может быть вычислен в конечных полях. Это имеет приложения в криптографии, например в схеме секретного обмена Шамиром.
См. Также
Ссылки
Внешние ссылки
- , Энциклопедия математики, EMS Press, 2001 [1994]
- ALGLIB имеет реализации на C ++ / C # / VBA / Pascal.
- GSL имеет код полиномиальной интерполяции на C
- SO имеет пример MATLAB, который демонстрирует алгоритм и воссоздает первое изображение в этой статье
- Метод интерполяции Лагранжа - Примечания, PPT, Mathcad, Mathematica, MATLAB, Maple в Институте холистических численных методов
- Интерполяционный полином Лагранжа на сайте www.math-linux.com
- Weisstein, Eric W. " Отставание диапазон Интерполирующий многочлен ". MathWorld.
- Многочлен Лагранжа в ProofWiki
- Динамическая интерполяция Лагранжа с JSXGraph
- Численные вычисления с функциями: Проект Chebfun
- Функция рабочего листа Excel для бикубической интерполяции Лагранжа
- Лагранжа полиномы в Python