А. Случай одной переменной

Обратимся для определенности к задаче интерполяции и начнем рассмотрение с обсуждения правил выбора класса кривых.

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

Пусть на плоскости задан набор точек (x_i, y_i), i=0,1,…,m, таких, что х₀<x₁<...<x_m-1<x_m (рис. 3.48).

Рис. 3.48 Набор точек на плоскости

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

Как известно из курса математического анализа, существует интерполяционный многочлен Лагранжа

где

график которого проходит через все заданные точки (x_i, y_i), i=0,1,...,m.

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

Однако полезно остановится и на некоторых недостатках предложенного подхода.

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

2. Изменение одной точки (ситуация, довольно часто встречаемая на практике) требует полного пересчета коэффициентов интерполяционного многочлена и к тому же может существенно повлиять на вид задаваемой им кривой.

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

 

Рис. 3.49 Приближение ломаной

 

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

Рассмотрев эти две крайние ситуации, попробуем найти класс функций, которые сохранили бы перечисленные выше достоинства обоих подходов и были бы в известной степени свободны от их недостатков.

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

То, что получится в результате описанных условий, называют сплайн-функциями или просто сплайнами.

Для того, чтобы понять, какое отношение имеют сплайн-функции к чертежным сплайнам, возьмем гибкую стальную линейку, поставим ее на ребро и, закрепив один из концов в заданной точке, поместим ее между опорами, которые располагаются в плоскости Оху в точках (x_i, y_i), i=0,1,...,m, где х₀<x₁<...<x_m-1<x_m (рис 3.50).

Рис. 3.50 Приближение сплайном

 

Интересно отметить, что функция у=S(х), описывающая профиль линейки, обладает следующими интересными свойствами:

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

на всем промежутке [ х₀, х_m ] функция у=S(х) дважды непрерывно дифференцируемая.

Построенная функция S(х) относится к так называемым интерполяционным кубическим сплайнам. Этот класс в полной мере удовлетворяет высказанным выше требованиям и обладает еще целым рядом замечательных свойств.

Перейдем, однако, к точным формулировкам.

Интерполяционным кубическим сплайном называется функция S(х), обладающая следующими свойствами:

1) график этой функции проходит через каждую точку этого массива, S(х_i)=y_i, i=0,1,...,m;

2) на каждом из отрезков [ х_i, х_i+1 ], i=0,1,...,m-1, функция является многочленом третей степени,

3) на всем отрезке задания [ х₀, х_m ] функция S(х_i) имеет непрерывную вторую производную.

Так как на каждом из отрезков [ х_i, х_i+1 ] сплайн S(х) определяется четырьмя коэффициентами, то для полного построения на всем отрезке задания необходимо найти 4 m чисел.

Третье условие будет выполнено, если потребовать непрерывности сплайнов во всех внутренних узлах х_i , i=0,1,...,m-1 (это дает m-1 условий на коэффициенты), а также его первой (m-1 условий) и второй (еще m-1 условий) производных в этих узлах. Вместе с первым условием получаем

m-1+m-1+m-1+m+1=4m-2

равенства. Недостающие два условия для полного определения коэффициентов можно получить, задав, например, значения первых производных на концах отрезка [ х₀, х_m ] (граничные условия):

S^'(х₀)=1₀, S^'(х_m)=1_m.

Существуют граничные условия и других типов.

Б. Случай двух переменных

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

Пусть на плоскости задан набор из (m+1)(n+1) точек (рис 3.51)

(x_i, y_j), i=0,1,...,m; j=0,1,..,n, где х₀<x₁<...<x_m-1<x_m, y₀<y₁<...<y_n-1<y_n.

Рис. 3.51 Набор (m+1)(n+1) точек на плоскости

 

Добавим к каждой паре (x_i, y_j) третью координату z_ij (x_i, y_j, z_ij). Тем самым мы получаем массив (x_i, y_j, z_ij), i=0,1,...,m; j=0,1,..,n.

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

Интерполяционным бикубическим сплайном называется функция двух переменных S(x,y), обладающая следующими свойствами:

график этой функции проходит через каждую точку заданного массива, S(х_i,y_i)=z_i, i=0,1,...,m; j=0,1,..,n.

2) на каждом частичном прямоугольнике [x_i, x_j+1]´[y_i, y_j+1], i=0,1,...,m-1; j=0,1,..,n-1, функция представляет собой многочлен третей степени по каждой из переменных,

3) на всем прямоугольнике задания [ x₀, x_m ] ´[ y₀, y_n ] функция S(х, y) имеет по каждой переменной непрерывную вторую производную.

Для того чтобы построить по заданному массиву {(x_i, y_j, z_ij)} интерполяционный бикубический сплайн, достаточно определить все 16mn коэффициентов. Как и в одномерном случае, отыскание коэффициентов сплайн-функции сводится к построению решения системы линейных уравнений, связывающих искомые коэффициенты a^ij_lk.

Последняя возникает из первого и третьего условий после добавления к ним недостающих соотношений путем задания значений произвольной искомой функции в граничных узлах прямоугольника [ x₀, x_m ]´[ y₀, y_n ] (или иных соображений).

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

Вместе с тем изменение лишь одной точки (случай на практике довольно типичный) при описанном подходе заставляет пересчитывать заново, как правило, все коэффициенты.

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

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