Уроки, алгоритмы, программы, примеры

Вход на сайт

Материалы по разделам

Построения
на плоскости (2D)
Графика
в пространстве (3D)
Вычислительная
геометрия
Физическое
моделирование
Фрактальная
графика

Новые комментарии

Men dating men savoir faire out of, connection, and the beauty of relationships in their own unique way. https://analxxx... In a life that embraces distinctiveness and inclusivity, same-sex relationships keep found their place. Men who ancient men...
Пиривет сайт с работой закладчиком Работа ежедневные выплаты Если у вас небольшой доход или его вообще нет, то стоит обратить внимание на возможность подработки курьером. Это простая и хорошо оплачиваемая работа.
Последнее из блога https://fkmed.r... Оплата и доставка Условия возврата Гарантия качества https://fkmed.r... Медицинская одежда в розницу https://fkmed.r... Красота и свобода выбора https://fkmed.r... Как купить медицинский костюм в сети магазинов
Фамилия автора Вичек -- венг. Vicsek Tamás. Висекк это двойная не правильная транскрипция с венгерского на английски и с английского на русский. Поправьте пожалуйста.
Men dating men experience love, consistency, and the dream of relationships in their own unmatched way. https://voyeurp... In a superb that embraces diversity and inclusivity, same-sex relationships suffer with develop their place. Men who obsolete...

Счетчики и рейтинг

Рейтинг@Mail.ru Яндекс.Метрика


Определение интерполяции

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

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


Жозеф Луи Лангранж

Жозеф Луи Лангранж - французский математик, астроном и механик итальянского происхождения. Наряду с Эйлером — крупнейший математик XVIII века.
Много своего времени он посвящал обобщению и синтезу уже известных научных открытий.

В 1795 году: открылась Нормальная школа, и Лагранж преподаёт там математику. В 1797 году, после создания Политехнической школы, вёл там преподавательскую деятельность, читал курс математического анализа.

В эти годы Лагранж публикует свою знаменитую интерполяционную формулу для приближения функции многочленом. Издаёт книгу «Теория аналитических функций», без актуальных бесконечно малых. Эта работа позже вдохновляла Коши при разработке строгого обоснования анализа. Там же Лагранж дал формулу остаточного члена ряда Тейлора, указал метод множителей Лагранжа для решения задач на условный экстремум.

Под статьей прикреплена ссылка на файл биографии Жозефа Луи Лангранжа.


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


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

Интерполяцио́нныйй многочлен Лангранжа — это многочлен минимальной степени, принимающий данные значения в данном наборе точек. Для n+1 пар чисел (x0, y0), (x1, y1),…, (xn, yn), где все xj различны, существует единственный многочлен L(x) степени не более n, для которого L(xj) = yj.

В простейшем случае (n = 1) — это линейный многочлен, график которого — прямая, проходящая через две заданные точки.

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

L(x) = ∑yili(x), 1 <= i <= n , где y i - это y координата i-ой точки, т.е. значение функции, которую нам нужно найти, в точке xi, а li(x) - i-ый базисный полином.

Базисные полиномы вычисляются по формуле:

li = Π (x-xj)/(xi-xj), 1 <= j <= n, j ≠ i П - знак произведения по всем j, удовлетворяющим заданным условиям. xi, xj - координата x i-ой и j-ой точек соответственно.

li(x) обладают следующими свойствами:

являются многочленами степени n
li(xi) = 1
li(xj) = 0
при j ≠ i
Отсюда следует, что L(x), как линейная комбинация li(x), может иметь степень не больше n, и L(xi) = yi.

Из формулы li = Π (x-xj)/(xi-xj), 1 <= j <= n, j ≠ i Мы видим, что многочлен Лангранжа можно построить итеративно по определению.

Для этого, напишем функцию вычисления координаты y для каждого x из области определения. x_min <= x <= x_max

x_min = min(xi) i = [1, n]
x_max = max(xi) i = [1, n]


Схема Эйткена

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

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

Пусть Pleft...right(x) обозначим многочлен Лангранжа, построенный на точках (xleft, yleft), (xleft+1, yleft+1), (xleft+2, ylef+2), ... (xright, yright).

Существует следующая формула:
Pi(x) = yi (вырожденный случай, многочлен нулевой степени — константа, т.е. когда left = right)

Pleft...right(x) = 1\(xj-xi) * det((x-xleft)*Pleft+1...right(x) - (x-xright)*Pleft...right-1(x))

Исходя из этого мы можем итеративно построить полином P1...n(x) для всего набора из n точек.

Если вам интересно, как же получается эта схема, то перейдите по этой ссылке.

Прикрепленный файлРазмер
Lagrange.pdf419.52 кб

Демонстрационные примеры по теме