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

Вход на сайт

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

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

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

Спасибо за реализацию, она действительно быстрая. Но не все линии отрисовывает в нужную сторону... Необходимо добавить проверку для случая X-линии if(y1 "<" y0) grad=-grad; и аналогично для Y-линии if(x1 "<" x0) grad=-grad; P.S. На...
Отличные уроки(учу GL по ним), только в renderScene нужно добавить очистку буфера цвета и буфера глубины. При изменении размеров треугольники размножаются)
как исправить это , сделал все по инструкции
Timer1 - выдает ошибку. Использовал IdleTimer1, работает! unit Unit1; {$mode objfpc}{$H+} interface uses Classes, SysUtils, FileUtil, Forms, Controls, Graphics, Dialogs, StdCtrls, ExtCtrls, OpenGLContext, GL, GLU; type { TForm1 } TForm1 =...
в коде присутствуют ошибки! // Считываем координаты procedure TForm1.getCoords(Sender: TObject); var j1:longint; begin n:= StrToInt(Edit2.Text); //число точек s1:=Edit1.Text; s2:=''; i := 1; j:=1; k:=0...

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

Яндекс.Метрика Рейтинг@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 кб