10.4. Сплайны на треугольных сетках

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

Многочлены степени называются фундаментальными многочленами интерполяции для сетки узлов если

Многочлен Лагранжа, интерполирующий значения в точках определяется формулой

Как линейная комбинация многочленов степени является многочленом степени Многочлен удовлетворяет условию интерполяции

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

Начнем со случая сплайнов от двух переменных. Пусть область представлена в виде объединения конечного числа треугольников так, что пересечением двух разных треугольников могут быть либо пустое множество, либо общая вершина, либо общая сторона (рис. 9а). Такое представление называется триангуляцией. На каждом из треугольников сплайн задается как многочлен степени вида

Многочлен (10.10) имеет коэффициентов, поэтому для его однозначного определения надо задать его значения на сетке, состоящей из такого же количества точек треугольника. Из дальнейшего изложения будет ясно, что сетку узлов на целесообразно образовать как пересечение двух пучков параллельных сторонам треугольника прямых (рис. 9б), разбивающих соответствующие противоположные стороны на равных частей. Число

Рис. 9

вершины треугольника Точки указанной регулярной сетки удобно записать следующим образом

где Произвольную же точку из можно представить в виде:

Координаты точек называются барицентрическими координатами.

Рассмотрим подробнее случай малых Пусть многочлен степени 1

однозначно определяется условиями интерполяции в вершинах треугольника

и по формуле Лагранжа (10.9)

Фундаментальные полиномы интерполяции могут быть заданы в форме (рис. 10а)

Построив на каждом треугольнике многочлен (10.10), на области будем иметь кусочно-линейную функцию (сплайн)

Рис. 10

интерполирующую значения в вершинах треугольников (рис. 106). Нетрудно видеть, что сплайн является непрерывной функцией на

2. Пусть многочлен степени 2

однозначно определяется условиями интерполяции в вершинах треугольника и серединах его сторон

Используя обозначение (10.11), можно записать По формуле Лагранжа

Фундаментальные многочлены интерполяции (верхний индекс 2 в обозначениях означает, что многочлены 2-й степени) могут быть выражены через многочлены (10.13) первой степени. Продемонстрируем это на примере номеров (рис. 11)

Рис. 11

Построив на каждом треугольнике многочлен (10.14), на всей области получим кусочно-параболическую функцию (параболический сплайн)

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

Другими словами, есть сужение многочлена на отрезок Ясно, что многочлены второй степени. Поскольку они интерполируют в трех точках одни и те же значения

то они тождественны. Равенство многочленов на стороне означает непрерывность сплайна на Непрерывность сплайна на установлена.

3) При многочлен на имеет 10 коэффициентов, регулярная сетка построена посредством разбиения сторон треугольника на три равные части, содержит 10 узлов: из них 9 на сторонах треугольника (точки со свойством и одну в центре треугольника — Фундаментальные многочлены интерполяции строятся из многочленов (10.13). Так, для узлов выглядят следующим образом

Построенная на кусочно-кубическая функция непрерывна.

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

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

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

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

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

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

Задавая значения многочлена в узлах сетки, мы однозначно определяем многочлен Это проще сделать с помощью интерполяционной формулы Лагранжа (10.9). При фундаментальными многочленами интерполяции являются многочлены

Рис. 12

где

Используя нетрудно построить фундаментальные многочлены интерполяции при для указанной регулярной сетки.