Как сделать полином лагранжа

Обновлено: 09.10.2024

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

Метод решения задачи

Полином Лагранжа

Представим интерполяционную функцию в виде полинома

где - полиномы степели n вида:

Очевидно, что принимает значение 1 в точке и 0 в остальных узлах интерполяции. Следовательно в точке исходный полином принимает значение
Таким образом, построенный полином является интерполяционным полиномом для функции на сетке .

Полином Ньютона

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

где - полиномы Лагранжа степени i <= n.
Пусть
. Этот полином имеет степень i и обращается в нуль при .
Поэтому он представим в виде:
, где - коэффициент при . Так как не входит в , то совпадает с коэффициентом при в полиноме . Таким образом из определения получаем:

Препишем формулу в виде

Рекуррентно выражая пролучам окончательную формулу для полинома:

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

Погрешность интерполирования

Поставим вопрос о том, насколько хорошо интерполяционный полином приближает функцию на отрезке [a,b].
Рассмотри м остаточный член:
, x ? [a, b].
По определению интерполяционного полинома
поэтому речь идет об оценке при значениях .
Пусть имеет непрерывную (n+1) производную на отрезке [a, b].
Тогда погрешность определяется формулой:
,
где ,
- точка из [a, b].
Так как точка наизвестна, то эта формула позволяет только оценить погрешность:

где
Из вида множетеля следует, что оценка имеет смысл только при . Если это не так, то при интерполяции используются полиномы низких степеней (n = 1,2).

Выбор узлов интерполяции

Так как от выбора узлов завист точность интерполяции, то возникает вопрос о том, как их выбирать. С помощью выбора узлов можно минимизировать значение в оценке погрешности. Эта задача решается с помощью многочлена Чебышева [1]:

В качестве узлов следут взять корни этого многочлена, то есть точки:

Пример

В качастве примера рассмотрим интерполяцию синуса. Возьмем равномерную решетку x = [-3,-1.5,0,1.5,3];
Интерполяция полиномом Лагранжа:

Ошибка(максимальное отклонение от sin(x) на отрезке):0.1423
Интерполяция полиномом Ньютона:
Ошибка:
Возьмем решетку x с узлами в корнях полинома Чебышева= [-2.8531,-1.7632,0,1.7634,2.8532];
Интерполяция полиномом Лагранжа:

Ошибка: 0.0944
Интерполяция полиномом Ньютона:
Ошибка:

Дано пар точек на плоскости . Все различны. Необходимо найти многочлен такой, что , где

Переводя на русский язык имеем: Иван загадал точек на плоскости, а Мария, имея эту информацию, должна придумать функцию, которая (по меньшей мере) будет проходить через все эти точки. В рамках текущей статьи наша задача сводится к помощи Марии окольными путями.

Процесс

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

В рамках статьи предлагаю за такую функцию взять десятичный логарифм и следующие точки:

Представляя их на плоскости, должно получится нечто следующее:

Нетрудно заметить, что сейчас кол-во пар точек равно .

При решении данной задачи приходит на ум некая системы уравнений, где кол-во линейно-независимых строк равно . Что же это за система уравнений такая?

Давайте попробуем функцию записать в виде суммы десятичных логарифмов с коэффициентами про оных (да так, чтобы кол-во коэффициентов было равно ):

Аргументы при различные чтобы избежать линейной зависимости строк в будущем (можно придумать другие). А также, учитывая, что область определения функции как минимум (на основе заданных условием точек), мы таким образом обеспечиваем существование области значений для функции в этой области определения.

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

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

Собственно решая данную систему относительно получим следующее решение:

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

Она, разумеется, будет проходить через заданный набор точек. А график функции будет выглядеть следующим образом:

Также, ради наглядности, можно привести аппроксимированную систему решений:

Тогда аппроксимированный вид функции будет следующий:

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

Различные примеры

На десерт аналогично построим функцию в радикалах:

Составим систему уравнения для нахождения коэффициентов:

Её решение единственно и выглядит следующим образом:

Тогда готовая функция выглядит следующим образом:

Что по совместительтву является полином Лагранжа для данного набора точек (т.к. оный в неявном виде реализует радикальную форму алгоритма из статьи). График на области заданных точек выглядит так:

Самым интересным в данной истории является то, что произвольные функции для построения конечной функции можно ~~и нужно~~ комбинировать. Иными словами, функция может быть построена сразу на радикалах и логарифмах, а может и на чем-то другом (показательные функции, факториалы, и т.п. ). Лишь бы полученный набор функций обеспечивал линейную независимость строк при подборе коэффициентов. В общем виде для заданных пар точек это выглядит так:

Где — коэффициенты которые предстоит найти через систему уравнений (СЛАУ), а — некоторые функции, которые обеспечат линейную независимость при нахождении коэффициентов.

А дальше — по алгоритму выше, всё совершенно аналогично. Не забывая о том, что должны быть определены на заданных условием точках.

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

Дабы удовлетворить заданному набору точек, коэффициенты будут в таком случае следующие (найдены строго по алгоритму из статьи):

А сама функция будет такой:

Подставим оные в готовую функцию:

А также полюбуемся очень хорошим графиком:

Зачем это нужно?

Да хотя бы для того, чтобы представить себе пучок веревок, стянутых пластиковыми хомутами :)

(* Тут мы просто наложили все графики друг на друга)

На этом в рамках текущей статьи все, рекомендую поиграться самостоятельно.

На этом изображении для четырех точек ( (-9, 5) , (-4, 2) , (-1, -2) , (7, 9) ) показан (кубический) интерполяционный многочлен L ( x ) (штриховой, черный), который представляет собой сумму масштабированных базисных полиномов y ₀ l ₀ ( x ) , y ₁ l ₁ ( x ) , y ₂ l ₂ ( x ) и y ₃ l ₃ ( x ) . Полином интерполяции проходит через все четыре контрольные точки, и каждый масштабированный базисный полином проходит через свою соответствующую контрольную точку и равен 0, где x соответствует трем другим контрольным точкам.

В численном анализе , полиномы Лагранжа используются для полиномиальной интерполяции . Для данного набора точек, у которых нет двух равных значений, полином Лагранжа является полиномом самой низкой степени, который принимает для каждого значения соответствующее значение , так что функции совпадают в каждой точке. ( Икс j , y j ) , y_ )> Икс j <\ displaystyle x_ > Икс j <\ displaystyle x_ > y j <\ displaystyle y_ >

Хотя метод был назван в честь Жозефа-Луи Лагранжа , опубликовавшего его в 1795 году, он был впервые открыт в 1779 году Эдвардом Уорингом . [1] Это также простое следствие формулы, опубликованной в 1783 году Леонардом Эйлером . [2]

Интерполяция Лагранжа восприимчива к феномену больших колебаний Рунге . Поскольку изменение точек требует пересчета всего интерполянта, часто вместо этого проще использовать полиномы Ньютона . Икс j >

СОДЕРЖАНИЕ

Здесь мы строим базисные функции Лагранжа 1-го, 2-го и 3-го порядков на двуединичной области. Линейные комбинации базисных функций Лагранжа используются для построения интерполяционных полиномов Лагранжа. Базисные функции Лагранжа обычно используются в анализе методом конечных элементов в качестве основы для форм-функций элементов. Кроме того, часто используется двуединичная область в качестве естественного пространства для определения конечных элементов.

Учитывая набор из k + 1 точек данных

где нет двух одинаковых, интерполяционный полином в форме Лагранжа представляет собой линейную комбинацию Икс j >

L ( Икс ) знак равно ? j знак равно 0 k y j l j ( Икс ) ^ y_ \ ell _ (x)>

базисных многочленов Лагранжа

где . Обратите внимание на то, как, учитывая исходное предположение, что нет двух одинаковых, затем (когда ) , поэтому это выражение всегда четко определено. Причина, по которой пары с недопустимыми, заключается в том , что не существует такой интерполяционной функции ; функция может получить только одно значение для каждого аргумента . С другой стороны, если также , то эти две точки фактически будут одной точкой. 0 <= j <= k Икс j > м ? j Икс j - Икс м ? 0 -x_ \ neq 0> Икс я знак равно Икс j =x_> y i ? y j \neq y_> L y i = L ( x i ) =L(x_)> x i > y i = y j =y_>

С другой стороны,

Другими словами, все базисные полиномы равны нулю в точке , за исключением того , для которого это верно , потому что в нем отсутствует член. x = x j > l j ( x ) (x)> l j ( x j ) = 1 (x_)=1> ( x - x j ) <\displaystyle (x-x_)>

Искомая функция L ( x ) является полиномом от x наименьшей степени, который интерполирует данный набор данных; то есть, он принимает значение y _j в соответствующем x _j для всех точек данных j :

В произведении есть k множителей, и каждый множитель содержит один x , поэтому L ( x ) (который является суммой этих полиномов k -степени) должен быть полиномом степени не выше k . l j ( x ) (x)>
l j ( x i ) = ? m = 0 m ? j k x i - x m x j - x m . (x_)=\prod _m=0\\m\neq j\end>^-x_>-x_>>.>

Разверните этот продукт. Поскольку в продукте отсутствует термин, где m = j , если i = j, то все термины, которые появляются, являются . Кроме того, если i ? j, то один член в продукте будет (для m = i ) , обнуляя весь продукт. Так, x j - x m x j - x m = 1 -x_>-x_>>=1> x i - x i x j - x i = 0 -x_>-x_>>=0>

Таким образом, функция L ( x ) является многочленом степени не выше k и где L ( x _i ) = y _i .

Кроме того, интерполирующий полином уникален, как показано теоремой о неразрешенности в статье по полиномиальной интерполяции .

Также верно и то, что:

поскольку он должен быть полиномом степени не выше k и проходить через все эти k + 1 точки данных:

в результате получается горизонтальная линия, поскольку прямая линия - единственный многочлен степени меньше k + 1, который проходит через k + 1 выровненные точки.

Решение задачи интерполяции приводит к проблеме линейной алгебры, сводящейся к обращению матрицы. Используя стандартный одночлен основу для нашего интерполяционного полинома , мы должны инвертировать матрицу Вандермонда , чтобы решить для коэффициентов в . Выбирая более прочную основу, основу Лагранжа, мы просто получим единичную матрицу , , которая является его собственной инверсией: базис Лагранжа автоматически переворачивает аналог матрицы Вандермонда. L ( x ) = ? j = 0 k x j m j ^x^m_> ( x i ) j )^> L ( x i ) = y i )=y_> m j <\displaystyle m_> L ( x ) L ( x ) = ? j = 0 k l j ( x ) y j ^l_(x)y_> d i j >

Эта конструкция аналогична китайской теореме об остатках . Вместо того, чтобы проверять остатки целых чисел по модулю простых чисел, мы проверяем остатки многочленов при делении на линеары.

Кроме того, при большом порядке можно использовать быстрое преобразование Фурье для определения коэффициентов интерполированного полинома.

Мы хотим интерполировать ? ( x ) = x 2 в диапазоне 1 <= x <= 3, учитывая эти три точки:

Мы хотим интерполировать ? ( x ) = x 3 в диапазоне 1 <= x <= 4, учитывая эти четыре точки:

Форма Лагранжа интерполяционного полинома показывает линейный характер полиномиальной интерполяции и уникальность интерполяционного полинома. Поэтому ему отдают предпочтение в доказательствах и теоретических аргументах. Уникальность также можно увидеть из обратимости матрицы Вандермонда из-за того, что определитель Вандермонда не обращается в нуль .

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

Лагранж и другая интерполяция в равноотстоящих точках, как в приведенном выше примере, дают полином, колеблющийся выше и ниже истинной функции. Это поведение имеет тенденцию расти с увеличением количества точек, что приводит к расхождению, известному как феномен Рунге ; проблема может быть устранена выбором точек интерполяции в чебышевских узлах . [3]

Базисные полиномы Лагранжа можно использовать при численном интегрировании для вывода формул Ньютона – Котеса .

мы можем переписать базисные полиномы Лагранжа как

или, определяя барицентрические веса [4]

мы можем просто написать

которую обычно называют первой формой формулы барицентрической интерполяции.

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

Барицентрическая формула интерполяции может также легко быть обновлена , чтобы включить новый узел путем деления каждого из , по и строительства нового , как указаны выше. x k + 1 > w j > j = 0 … k ( x j - x k + 1 ) -x_)> w k + 1 <\displaystyle w_>

Мы можем еще больше упростить первую форму, сначала рассмотрев барицентрическую интерполяцию постоянной функции : g ( x ) ? 1

Деление на не изменяет интерполяцию, но дает L ( x ) g ( x )

которая называется второй формой или истинной формой формулы барицентрической интерполяции. Эта вторая форма имеет то преимущество, что ее не нужно оценивать для каждой оценки . l ( x ) L ( x )

При интерполяции заданной функции f полиномом степени k в узлах мы получаем остаток, который можно выразить как [5] x 0 , . . . , x k . x_> R ( x ) = f ( x ) - L ( x )

где - обозначение разделенных разностей . В качестве альтернативы остаток может быть выражен как контурный интеграл в комплексной области как f [ x 0 , … , x k , x ] ,\ldots ,x_,x]>

Остаток можно связать как

Уравнение можно переписать как

В производных го полинома Лагранжа можно записать в виде d

Для первой производной коэффициенты имеют вид

а для второй производной

С помощью рекурсии можно вычислить формулы для высших производных.

Многочлен Лагранжа также можно вычислить в конечных полях . Это имеет применение в криптографии , например, в схеме совместного использования секретов Шамира .

нуля при / = у, а в остальных точках он обращается в нуль. Следовательно, все эти точки являются для него корнями:

подставим с в формулу /?,(х), получим: отсюда

Это и есть интерполяционный многочлен Лагранжа. По исходной таблице формула позволяет весьма просто составить внешний вид многочлена.

Пример 2.63. Построить интерполяционный многочлен Лагранжа для функции, заданной таблично

Интерполяцио?нный многочле?н Лагра?нжа — многочлен минимальной степени, принимающий данные значения в данном наборе точек. Для " width="" height="" />
пар чисел ,y_),(x_,y_)\dots (x_,y_)>" width="" height="" />
, где все >" width="" height="" />
различны, существует единственный многочлен " width="" height="" />
степени не более " width="" height="" />
, для которого )=y_>" width="" height="" />
.

$<\displaystyle n=1> В простейшем случае$
это линейный многочлен, Определение

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

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

$<\displaystyle l_<j> (x)=\prod _^>-x_>>=>-x_>>\cdots >-x_>>>-x_>>\cdots <\frac <x-x_>-x_>>\,\!>$

$<\displaystyle l_<j> Легко видеть что (x)>$
обладают такими свойствами:

Отсюда следует, что " width="" height="" />
, как линейная комбинация (x)>" width="" height="" />
, может иметь степень не больше " width="" height="" />
, и )=y_>" width="" height="" />
, Применения

$<\displaystyle y_ Полиномы Лагранжа используются для известны значения =f(x_)>$
в некоторых точках. Тогда мы можем интерполировать эту функцию как

$<\displaystyle f(x)\approx \sum _<j=0> ^f(x_)l_(x)>$

$<\displaystyle \int \limits _^ f(x)dx\approx \sum _^f(x_)\int \limits _^l_(x)dx>$

Значения интегралов от >" width="" height="" />
не зависят от " width="" height="" />
, и их можно вычислить заранее, зная последовательность >" width="" height="" />
.

Для случая равномерного распределения по отрезку узлов интерполяции

$<\displaystyle x_ В указанном случае можно выразить >$
через расстояние между узлами интерполяции h и начальную точку >" width="" height="" />
:

$<\displaystyle x_<j> \equiv +jh>>$
,

$<\displaystyle <x_ -x_>\equiv (i-j)h>$
.

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

$<\displaystyle l_ (x)=<\prod _^<(x-x_) \over (x_-x_)>>=<\prod \limits _^(x-x_-jh) \over h^\prod \limits _^(i-j)>>$

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

$<\displaystyle y=<<x-x_<0> > \over h>\,\!>$

и получить полином от XY, который строится с использованием только целочисленной арифметики. Недостатком данного подхода является факториальная сложность числителя и знаменателя, что требует использования cs:Lagrangeova interpolace nl:Lagrange-polynoom

Читайте также:


Как сделать оплетку на ручку кружки

Как сделать манговый чай

Как сделать маршрутный лист по географии

Как сделать камею

Как сделать клюв попугая