§ 11.11. Интерполяция сплайнами

1. Определение сплайна.

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

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

Естественная потребность в наличии аппроксимирующих функций, которые сочетали бы в себе локальную простоту многочлена невысокой степени и глобальную на всем отрезке гладкость, привела к появлению в 1946 г. так называемых сплайн-функций или сплайнов — специальным образом построенных гладких кусочно-многочленных функций. Получив в 60-х годах распространение как средство интерполяции сложных кривых, сплайны к настоящему времени стали важной составной частью самых различных вычислительных методов и нашли широчайшее применение в решении разнообразных научно-технических и инженерных задач.

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

1) функция непрерывна на отрезке вместе со всеми своими производными до некоторого порядка

2) на каждом частичном отрезке функция совпадает с некоторым алгебраическим многочленом степени

Разность между степенью сплайна и наивысшим порядком непрерывной на отрезке производной называется дефектом сплайна.

Простейший пример сплайна дает непрерывная кусочно-линейная

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

Рис. 11.8

Рис. 11.9

Наиболее широкое распространение на практике получили сплайны третьей степени (кубические сплайны) с дефектом, равным 1 или 2. Такие сплайны на каждом из частичных отрезков совпадают с кубическим многочленом:

и имеют на отрезке по крайней мере одну непрерывную производную

Термин "сплайн" происходит от английского слова (гибкая линейка, стержень) — названия приспособления, использовавшегося чертежниками для проведения гладких кривых через заданные точки. Бели гибкую стальную линейку поставить на ребро и, изогнув, зафиксировать ее положение в узловых точках (рис. 11.9), то получится механический аналог кубического сплайна. В самом деле, из курса сопротивления материалов известно, что уравнение свободного равновесия профиля линейки таково: Следовательно, в промежутке между двумя соседними узлами представляет собой многочлен третьей степени. В то же время отсутствие у линейки изломов свидетельствует о непрерывности касательной к графику функции и кривизны, т. е. производных

2. Интерполяционный сплайн.

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

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

Здесь

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

3. Локальный сплайн.

Если в точках х, известны значения производной то естественно положить для всех Тогда на каждом частичном отрезке в соответствии с формулой (11.64) сплайн однозначно определяется значениями (поэтому его и называют локалъныл сплайном). Заметим, что он совпадает с кубическим интерполяционным многочленом Эрмита (11.31) для отрезка

Из неравенства (11.33) получается следующая оценка погрешности интерполяции локальным кубическим сплайном:

где Ащах максимальная из длин частичных отрезков.

Заметим, что для построенного указанным образом сплайна можно гарантировать непрерывность на отрезке только функции и ее первой производной 53, т.е. его дефект равен 2.

Существуют и другие способы выбора коэффициентов а, приводящие к локальным сплайнам (кубический многочлен Бесселя, метод Акимы и др. [16]).

4. Глобальные способы построения кубических сплайнов.

Для того чтобы сплайн имел непрерывную на отрезке вторую производную необходимо выбирать наклоны а, так, чтобы в точках х, "стыка" многочленов совпадали значения их вторых производных:

Пользуясь формулой (11.64), найдем значение

Из подобной формулы, записанной

Таким образом, равенства (11.66) приводят к следующей системе уравнений относительно коэффициентов

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

1°. Если в граничных точках известны значения первой производной то естественно положить

Дополняя систему (11.69) уравнениями (11.70), приходим к системе уравнений с трехдиагональной матрицей, которая легко решается методом прогонки (см. гл. 5). Полученный таким образом сплайн называется фундаментальным кубическим сплайном.

2°. Если в граничных точках известны значения второй производной то можно наложить на сплайн граничные условия что приводит к следующим уравнениям:

(достаточно в равенстве (11.68) взять а в равенстве

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

4°. Часто нет, никакой дополнительной информации о значениях производных на концах отрезка. Один из применяемых в этой ситуациии подходов состоит в использовании условия "отсутствия узла". Выбор наклонов производят таким образом, чтобы для получаемого сплайна выполнялись условия Для этого достаточно потребовать совпадения в точках соответствующих третьих производных:

Эквивалентные алгебраические уравнения выглядят так:

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

5°. Если периодическая функция с периодом, равным о то систему (11-69) следует дополнить условиями

Существуют и другие подходы к заданию граничных условий (подробнее об этом см. [16]).

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

Решал ее, получаем значения . Теперь на каждом частичном отрезке значения сплайна можно вычислить по формуле (11.64). Соответствующий график приведен на рис 11.10 (ср. с рис. 11.6 и 11.7).

Пример 11.14. Интерполируем функцию, заданную табл. 11.12, кубическим сплайном, используя условие "отсутствия узла". В этом случае уравнения останутся прежними, а уравнения (11 75) и (11.79) заменяются следующими:

Рис. 11.10

Решая систему получаем значения График соответствующего сплайна мало отличается от графика, изображенного на рис. 11.10.

5. Погрешность приближения кубическими сплайнами.

Теорема 11.9. Пусть функция имеет на отрезке непрерывную производную четвертою порядка и Тогда для интерполяционною кубическою сплайна удовлетворяющею граничным условиям типов 1°, 2°, 4° иди 5° (последнее — для случая периодической функции), справедлива следующая оценка погрешности:

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

Теорема 11.10. При выполнении условий теоремы 11.9 для указанных в ней сплайнов справедливы неравенства

Замечание. Благодаря большей простоте записи и благозвучному названию естественные сплайны получили значительное распространение. Однако искусственное наложение условий при интерполяции функций, которые этим условиям не удовлетворяют, приводит к значительной потере точности. Вместо четвертого порядка точности (как локальный кубический сплайн или кубические сплайны с граничными условиями типов 1°, 2°, 4°, 5°) естественный сплайн обладает лишь вторым порядком точности. Если использование естественного сплайна не вызвано какими-либо специальными причинами, то следует, по-видимому, отказаться от него в пользу кубического сплайна с граничным условием типа 4°.