11. Построение кривых. Интерполяционный полином Лагранжа. Достоинства и недостатки. (Листинг функции для реализации полинома Лагранжа по лабораторной работе).

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

,

где

(14.1)

и в соответствии с определением интерполирующей функции

(14.2)

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

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

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

(14.6)

Неизвестные коэффициенты определим из условия

.

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

Подставляя найденные значения коэффициентов в выражение (14.6) для многочлена , получим

(14.7)

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

Достоинства полинома Лагранжа:

• график интерполяционного многочлена Лагранжа проходит через каждую точку массива;

• конструируемая функция легко описывается (число подлежащих определению коэффициентов интерполяционного многочлена Лагранжа на сетке равно );

• построенная функция имеет непрерывные производные любого порядка;

• заданным массивом интерполяционный многочлен определен од­нозначно.

Недостатки полинома Лагранжа:

• степень интерполяционного многочлена Лагранжа зависит от числа узлов сетки, и чем больше это число, тем выше степень интерполяционного многочлена и, значит, тем больше требуется вычислений;

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

12. Построение кривых. Интерполяционный кубический сплайн. (Листинг функции для реализации кубического сплайна по лабораторной работе).

Достоинства кубической сплайн-интерполяции

• график построенной функции проходит через каждую точку мас­сива;

• конструируемая функция сравнительно легко описывается (число подлежащих определению коэффициентов равно );

• заданным массивом построенная функция определена однозначно;

• степень многочленов не зависит от числа узлов сетки и, следова­тельно, не изменяется при его увеличении;

• построенная функция имеет непрерывные первые и вторые производные;

• построенная функция обладает хорошими аппроксимационными свойствами.

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

13. Построение кривых. Геометрические сплайны. Кривая Безье. Геометрический алгоритм построения кривой Безье. (Листинг функции для реализации геометрического алгоритма построения кривой Безье по лабораторной работе)

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

Формулировка задачи: по заданному множеству вершин

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

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

Во многих случаях она довольно точно показывает, как будет проходить искомая кривая, что особенно полезно при решении задачи сглаживания. Каж­дая вершина заданного массива является либо внутренней либо гранич­ной (концевой). В массиве Р вершины Р₁ …, P_m-1 внутренние, а вершины Р₀ и Р_m - граничные (концевые).

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

(1)

где - некоторые функциональные коэффициенты, подлежащие определению.

Кривая Безье

Кривая Безье задается несколькими точками в N-мерном пространстве (классический вариант, описываемый в литературе – 4 точки, но мы, для удобства, помимо этого случая будем использовать вырожденные случаи из 3-х точек, а так же пользоваться введением дополнительных вершин), но нам так много не нужно, поэтому ограничимся тремя измерениями (хотя все приведенные алгоритмы будут справедливы и для векторов другой мерности).

Для начала рассмотрим самый простой случай (его иллюстрация этого случая приведена на рис. 1) – когда у нас 4 вершины.

Здесь p0 и p3 – начальная и конечная точки соответственно, а p1 и p2 – промежуточные точки. Разности же вершин p1-p0 и p2-p3 определяют крутизну кривой в этих точках. Сама же кривая задается следующим уравнением:

C(s) = p0 * ( 1 – s )³ + 3 * p1 * s * ( 1 – s )² + 3 * p2 * s² * ( 1 – s ) + p3 * s³

Несложно показать, что

C( 0 ) = p0

C( 1 ) = p3

C’( 0 ) = 3 * ( p1 - p0 )

C’( 1 ) = 3 * ( p3 – p2 )

Собственно как я и говорил – кривая проходит через конечные точки + имеется информация о крутизне кривой.