Построение кривой по точкам с помощью интерполяции Лагранжа
Построение кривой по множеству точек P с помощью интерполяционного многочлена Лагранжа.
Введение
В данной статье объясняется построение кривой по точкам с помощью интерполяционного многочлена Лагранжа. Построение кривой по точкам используется в широком спектре технических применений, таких как проектирование машин и поверхностей самолетов. Главная проблема, учитывая множество точек в плане, в том, что надо построить по ним гладкую кривую, проходящую через эти точки. Порядок кривой f(x) зависит от количества заданных точек. Например, если задано две точки, функция будет иметь первый порядок, и кривая будет линией, проходящей через эти две точки, тогда как если задано три точки, функция будет иметь второй порядок f(x) = x2 . Сначала разберем многочлен Лагранжа, затем перейдем к алгоритму и реализации. В этой статье код написан на C#.
Основы
Многочлен Лагранжа
Интерполяция на двух точках, (x0, y0) и (x1, y1), дает линейное уравнение или прямую линию. Стандартная форма линейного уравнения задается y = mx +c, где m – градиент линии, а c - отрезок, отсекаемый на оси Y.
m = y1 ? y0 / x1 ? x0
c = y0 ? mx0
что дает:
y = (y1 ? y0 / x1 ? x0) * x + (x1 y0 ? x0 y1)/ (x1 ? x0)
Линейное уравнение переписано, чтобы две полученные интерполяцией точки, (x0, y0) и (x1, y1), были непосредственно представлены.
Поэтому линейное уравнение переписывается в виде:
P1(x) = a0(x ? x1) + a1(x ? x0)
где a0 и a1 - константы. Точки x0 и x1 в множителях вышеприведенного уравнения называются центрами. Применив уравнение в (x0, y0), получаем:
y0 = a0(x0 ? x1) + a1(x0 ? x0)
или
a0 = y0/ x0?x1
В (x1, y1) получаем:
y1 = a0(x1 ? x1) + a1(x1 ? x0), or a1 = y1/ x1?x0
Следовательно, линейное уравнение становится:
P1(x) = y0 (x? x1) /(x0 ? x1) + y1 (x? x0) / (x1 ? x0)
Квадратичная форма многочлена Лагранжа интерполирует три точки, (x0, y0), (x1, y1), and (x2, y2). Многочлен имеет вид:
P2(x) = a0(x? x1)(x? x2) + a1(x? x0) (x? x2) + a2(x? x0)(x? x1)
с центрами в x0, x1, и x2. В (x0, y0):
y0 = a0(x0 ? x1)(x0 ? x2) + a1(x0 ? x0)(x0 ? x2) + a2(x0 ? x0)(x0 ? x1),
или
a0 = y0/ (x0 ? x1)(x0 ? x2)
a1 = y1 / (x1 ? x0)(x1 ? x2)
a2 = y2/ (x2 ? x0)(x2 ? x1)
P2(x) = y0 (x? x1)(x? x2) / (x0 ? x1)(x0 ? x2) + y1 (x ? x0)(x ? x2)/
(x1 ? x0)(x1 ? x2) + y2 (x? x0)(x? x1)/ (x2 ? x0)(x2 ? x1)
В целом, многочлен Лагранжа степени n является многочленом, полученным путем интерполяции по множеству точек, (xi , yi ) для i = 0, 1, . . ., n, следующим образом:
Pn(x) = y0L0(x) + y1L1(x) + ••• + ynLn(x)
Использование кода
Алгоритм
Заданы интерполяционные точки (xi , yi ) для i =0, 1, . . . ,n;
для i = 0 до n
//суммирующее умножение от k = 1 (и k не равно i) до n
Вычислить Li (x) = ?nk=1,k != i (x?xk ) / (xi?xk ) ;
endfor
Вычислить Pn(x) = y0L0(x) + y1L1(x) + ••• + ynLn(x);
Скачайте исходники из верха этой страницы, чтобы изучить код.
Интересные моменты
Численные методы – очень интересная область разработки программного обеспечения. Данная статья связана с этой областью ... Скоро будут опубликованы новые статьи о вычислительной геометрии,такие как алгоритм выпуклой оболочки и триангуляция.