коэффициенты полинома лагранжа можно найти не решая систему уравнений

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

1. Интерполяционная формула Лагранжа

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

где ˗ степень полинома ;

˗ значение значения интерполирующей функции в точке ;

˗ базисные полиномы (множитель Лагранжа), которые определяются по формуле:

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

Многочлен в форме Лагранжа в явном виде содержит значения функций в узлах интерполяции, поэтому он удобен, когда значения функций меняются, а узлы интерполяции неизменны. Число арифметических операции, необходимых для построения многочлена Лагранжа, пропорционально и является наименьшим для всех форм записи. К недостаткам этой формы записи можно отнести то, что при построении полинома степени n+1 полностью теряется информация о предыдущем полиноме степени n, т.е. с изменением числа узлов приходится все вычисление выполнить заново.

2. Погрешность интерполяционного полинома в форме Лагранжа

Рассмотрим функцию f ( x ), которая непрерывна и дифференцируема на рассматриваемом отрезке [a, b]. Интерполяционный полином L (x) в форме Лагранжа принимает в точках заданные значения функции . В остальных точках интерполяционный полином L (x) отличается от значения функции f ( x ) на величину остаточного члена, который определяет абсолютную погрешность интерполяционной формулы Лагранжа:

А бсолютную погрешность интерполяционной формулы Лагранжа определяют следующим образом:

где n ˗ степень полинома

Переменная представляет собой верхнюю границу значения модуля (n +1)-й производной функции f(x) на заданном интервале [a, b]

Погрешность интерполяции методом Лагранжа зависит от свойств функции f ( x ), а также от расположения узлов интерполяции и точки x. В случае если погрешность не достигает нужной точности, то нужно разбить отрезок на части и интерполировать каждую часть в отдельности – кусочная интерполяция.

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

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

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

3. Методика вычисления полинома в форме Лагранжа

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

2. Выполняется вычисление полинома n-степени в форме Лагранжа по следующей формуле:

Алгоритм вычисления полинома в форме Лагранжа представлен на рисунке 1.

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

В качестве примера рассмотрим следующую практическую задачу. В рамках задачи известен набор шести значений, которые получены методом случайной выборки для различных моментов времени. Следует отметить, что данная выборка значений описывает функция на интервале [0, 10]. Необходимо построить многочлен в форме Лагранжа для представленного набора значений. С помощью интерполяционной формулы вычислить приближенное значение функции в точке , а также определить оценку погрешности результата вычислений.

Многочлен в форме Лагранжа, который строится на основании шести значений, представляет собой полином 5 степени. Результат построения полинома в форме Лагранжа показан в графическом виде.

С помощью найденного полинома можно определить значение функции в любой точке заданного интервала. Определение промежуточных значений величины по имеющемуся дискретному набору известных значений называется «интерполяцией». В соответствии с условиями задачи полином в форме Лагранжа в точке x =9,5 принимает следующее значение: L (9,5)= – 4,121. Из графика видно, что полученное значение не совпадает c о значением функции f ( x ) на величину абсолютной погрешности интерполяционной формулы Лагранжа.

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

Для того, чтобы добавить Ваш комментарий к статье, пожалуйста, зарегистрируйтесь на сайте.

Источник

Путеводитель по полиномам и сплайнам для программиста

Итак, вы программист. Зачем вам вообще могут понадобится полиномы? Например затем, что это хорошая геометрическая глина, из которой можно слепить разные вещи.

Из нашей статьи, объясняющей сущность математического анализа на примере python’а, крови и динамита, видно, что вы можете анализировать и синтезировать произвольные функции в качестве многочленов. Однако вовсе не обязательно работать именно с функциями. Иногда вам может понадобиться смоделировать сплайн из нескольких точек или свойств, вроде тангенсов кривых. Например, вам надо слепить какую-нибудь анимацию, или приятный видео эффект, или провести кривую, проходящую через определенные точки, или создать поверхность плоскую в одном месте и изогнутую в другом.

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

Для его вычисления требуется всего 6 действий умножения и 3 сложения. Это важно, поскольку ваша модель будет постоянно подвергаться вычислениям. Но и здесь мы можем произвести оптимизацию. В этом нам поможет схема Горнера. С ее помощью тот же самый многочлен можно записать в виде

А это уже всего 3 умножения и 3 сложения. Вот видите, мы только начали, а вы уже научились избавляться от одной трети вычислений.

Полиномиальная интерполяция

Задача адаптации многолчена n-ной степени под n+1 точку пространства называется полиномиальной интерполяцией. Существует несколько способов ее реализации. Вы можете воспользоваться интерполяционными формулами Ньютона или Лагранжа, однако самый простой способ получения интерполяционного многочлена — решение системы линейных уравнений.

Если многочлен проходит через точку, значит, мы, очевидно, можем утверждать, что P(xi) = yi. Допустим, мы хотим адаптировать полином под набор из трех точек. Это означает, что:

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

Поскольку xs и ys известны, нам остается только решить систему и узнать коэффициенты a, b, c, и поскольку эта система из трех уравнений и трех переменных, мы как правило можем получить одно единственное решение.

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

Этот график также очень полезен для мысленного анализа линейных систем. В общем случае, уместить прямую линию в трех точках нельзя, равно как и нельзя найти решение для системы из n уравнений при n-1 неизвестных переменных. Но иногда это возможно. Например, в случаях, когда некоторые из точек совпадают или все они намерено расположены на одной прямой.

Обратная ситуация еще интереснее. Мы можем провести бесконечное количество парабол через две заданные точки. Все они одинаково подходят в качестве решения задачи. И в то же время мы не можем получить некое однозначно лучшее решение для систем из n уравнений и n+1 переменных.

Но что если это все-таки возможно? Что если мы можем ввести некоторый дополнительный критерий для выбора наиболее подходящего варианта?

Синтез

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

Производная функции тесно связана с геометрическими свойствами ее графика. Первая производная определяет тангенс угла наклона касательной, а вторая — кривизну.

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

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

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

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

Феномен Рунге

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

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

Узлы Чебышева

Один из способов борьбы с хаосом заключается в выборе специальной сетки для интерполяции — узлов Чебышева. Это специальные значения x, которые получаются путем деления полукруга с радиусом 1 на равные фрагменты и их проецирования на ось x.

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

Конечно, вы можете расширить интервал по оси X настолько, насколько нужно с помощью одномерного аффинного преобразования. Не обязательно придерживаться отрезка (-1; 1).

Но интерполяция при этом сохраняет свою повсеместность. Изменение первой точки по-прежнему влияет на работу функции возле последней, хотя и не настолько существенно.

Сплайны

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

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

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

Заключение

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

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

Источник

Инструменты сайта

Основное

Навигация

Информация

Действия

Содержание

Интерполяция

Интерполяция или интерполирование — приближенное или точное нахождение какой-либо величины по известным отдельным значениям этой же величины, или других величин, с ней связанных.

Происхождение слова «интерполяция» ☞ ЗДЕСЬ.

Задача интерполяции решается в разных классах функций — полиномов алгебраических или тригонометрических, комбинаций экспонент; в классе рациональных функций. Начинаем изложение материала с самого простого случая —

Полиномиальная интерполяция

Все множество интерполяционных полиномов, принимающих значения по таблице, можно представить в виде

Решение ☞ ЗДЕСЬ.

Пусть имеется интерполяционная таблица

Пример. Интерполяционный полином для таблицы

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

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

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

Пример. Построить интерполяционный полином по таблице

Рекурсивное вычисление коэффициентов

В настоящем пункте мы произведем «доводку» метода Лагранжа до коэффициентов интерполяционного полинома

Интерполяционный полином в форме Ньютона

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

Теорема. Интерполяционный полином в форме Ньютона записывается в виде:

Применение полиномиальной интерполяции в задаче о разделении секрета

Обратная интерполяция

В одном из предшествующих ☝ пунктов решалcя следующий

Пример. Найти корни интерполяционного полинома, заданного таблицей

Интерполяционный полином Эрмита

Пример. Построить интерполяционный полином по таблице

Построить уравнение «горки»: найти полином из условий

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

Рациональная интерполяция

Первое решение задачи было предложено Коши в 1821 г. [9].

Теорема [Коши]. Обозначим:

Биографические заметки о Коши ☞ ЗДЕСЬ.

Другие примеры на применение теоремы Коши ☞ ЗДЕСЬ

Теорема Коши дает решение задачи в смысле «как правило». Дело в том, что задача рациональной интерполяции (в указанной постановке) не всегда разрешима.

Пример. Для таблицы

Альтернативный подход к решению задачи основывается на следующей теореме, развивающей результат К.Якоби [10,11]; он основан на идее из пункта ☝ о рекурсивном вычислении коэффициентов интерполяционного полинома.

Подробнее о методе Якоби (в том числе и об эффективном способе вычисления ганкелевых полиномов) ☞ ЗДЕСЬ.

Тригонометрическая интерполяция

Доказательство тривиально, если обратить внимание на аналогию с интерполяционным полиномом в форме Лагранжа. ♦

Теорема. Функция

Задача. Найти явные выражения для коэффициентов тригонометрического полинома из последней теоремы.

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

Пример. Построить интерполяционный полином второго порядка по следующей таблице

Решение ☞ ЗДЕСЬ.

Для случая системы равноотстоящих узлов решение задачи значительно упрощается.

Подробное изложение теории тригонометрической интерполяции (и дискретного преобразования Фурье) ☞ ЗДЕСЬ

Интерполяция суммами экспонент

Материал настоящего пункта — сильная «выжимка» из [2]. Числовой пример — мой.

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

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

Аппроксимация

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

Аппроксимация в случае недостоверности данных

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

Координаты точки, для которой величина

Теорема 2 [3],[4]. Обозначим

$$ \begin x & 0.0 & 0.9 & 1.8 & 2.6 & 3.3 & 4.4 & 5.2 & 6.1 & 6.5 & 7.4 \\ \hline y & 5.9 & 5.4 & 4.4 & 4.6 & 3.5 & 3.7 & 2.8 & 2.8 & 2.4 & 1.5 \end $$

Метод наименьших квадратов

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

$$ \begin x & 0.5 & 1 & 1.5 & 2 & 2.5 & 3 \\ \hline y & 0.35 & 0.80 & 1.70 & 1.85 & 3.51 & 1.02 \end $$

Дальнейшее развитие идеологии МНК ☞ ЗДЕСЬ.

Многомерная интерполяция

Сложности: парадокс Крамера

Прямоугольная сетка

Задачи

Источники

[1]. Mycielski J. Polynomials with Preassigned Values at their Branching Points. The American Mathematical Monthly, 77 (8).1970, pp. 853-855

[2]. Henrici P. Applied and Computational Complex Analysis. V. 1. 1974. NY. Wiley

[4]. Hilbert D. Ein Beitrag zur Theorie des Legendreschen Polynoms. Acta Math. Bd.18, 1894, S.155-160

[5]. Форсайт Дж., Молер К. Численное решение систем линейных алгебраических уравнений. М. Мир. 1969

[6]. Линник Ю.В. Метод наименьших квадратов и основы математико-статистической теории обработки наблюдений. М.ГИФМЛ. 1958

[7]. Калинина Е.А., Утешев А.Ю. Теория исключения. Учеб. пособие. СПб.: НИИ Химии СПбГУ, 2002. 72 с.

[8]. Утешев А.Ю., Тамасян Г.Ш. К задаче полиномиального интерполирования с кратными узлами. Вестник СПбГУ. Серия 10. 2010. Вып. 3, С. 76-85. Текст (pdf) ☞ ЗДЕСЬ

[9]. Cauchy A.-L. Cours d’Analyse de l’École Royale Polytechnique: Part I: Analyse Algébrique. Paris, France: L’Imprimerie Royale, 1821, pt. 1.

[10]. Jacobi C.G.J. Űber die Darstellung einer Reihe gegebner Werthe durch eine gebrochne rationale Function. J.reine angew. Math. 1846. Bd. 30, S. 127-156

[11]. Утешев А.Ю., Боровой И.И. Решение задачи рациональной интерполяции с использованием ганкелевых полиномов. Вестник СПбГУ. Серия 10. 2016. Вып. 4, С. 31-43. Текст ☞ ЗДЕСЬ (pdf).

[12]. Pearson K. On lines and planes of closest fit to systems of points in space. Phil. Mag. 1901. V.2, pp. 559-572

Источник