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

Для определенности будем говорить о приближении функции на отрезке [0, 1]. Разобьем его на части и обозначим это разбиение через . Назовем сплайном порядка функцию, являющуюся многочленом степени m на каждом из отрезков , т.е.

(1)

и удовлетворяющую условиям непрерывности производных до порядка в точках :

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

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

Эта система распадается на системы уравнений относительно коэффициентов отдельных многочленов

Отсюда находим

Многочлен является многократно рассматривавшимся интерполяционным многочленом первой степени с узлами интерполяции .

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

Сплайны первой степени возникают из рассмотрения следующей вариационной задачи. Рассмотрим множество кусочно-дифференцируемых функций , удовлетворяющих условиям

Поставим задачу найти функцию , реализующую

Уравнение Эйлера для этого функционала имеет вид Таким образом, линейна на каждом из отрезков и, следовательно, .

Этот подход к приближению функции, при котором естественным образом возник сплайн , допускает различные обобщения. Рассмотрим, например, множество непрерывных, непрерывно-дифференцируемых и дважды кусочно непрерывно-дифференцируемых функций , удовлетворяющих условиям

Ищется функция , реализующая . Решением этой задачи оказывается сплайн третьей степени, удовлетворяющий условиям .

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

Уравнением Эйлера для рассматриваемого функционала является уравнение

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

Положим

Поскольку по предположению , то

Представим величину в виде ,

и произведем в выражении для дважды интегрирование по частям. Получим

Вследствие (3) и равенства имеем

После суммирования по получим

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

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

Подставляя такие в равенство

получаем уравнение

(5)

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

а условия непрерывности в точках порождают уравнения

В совокупности нами получено уравнений (5)-(7) относительно 4N неизвестных коэффициентов многочленов .

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

здесь . Из этого соотношения и из условий

можно получить, что

на . Условия

порождают уравнения

Кроме того, имеем условия

иначе . После подстановки и соответственно в первое и последнее уравнения (8) получим систему

из уравнения с неизвестным:

Элементы матрицы С согласно (9) задаются соотношениями

а элементы столбца d — соотношениями

Эта система решается методом прогонки (см. гл. 9) примерно за арифметических операций. После нахождения по формуле (8) определяем многочлены .

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

имеет только нулевое решение. Предположим противное, т. е. что существует ненулевое решение системы (12). Пусть — значение , при котором достигается , т.е.

В уравнении перенесем в правую часть все слагаемые, кроме . Получим

Из соотношений (11), определяющих , следует, что при любом справедливы соотношения

поэтому имеем цепочку неравенств

Вычтем из обеих частей результирующего неравенства

выражение, стоящее в правой части. Получим . Поскольку . Мы пришли к противоречию с предположением о существовании у системы (12) ненулевого решения.

Подведем итог проведенным построениям. Доказано существование решения системы (10). Сплайн третьей степени, определяемый соотношениями (8), будет искомым сплайном, удовлетворяющим условиям (5)-(7).

Лемма. Полученный сплайн реализует .

Доказательство. Пусть — произвольная функция из . Положим . Имеем

Поскольку удовлетворяет условиям (5), то в соотношении (14) имеем . Таким образом, при любой функции справедливо соотношение

Отсюда следует справедливость утверждения леммы.

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

Задача 1. Доказать, что решение системы (10) удовлетворяет неравенству

получить отсюда однозначную разрешимость системы .

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

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

Получить оценку

— абсолютные постоянные, не зависящие от .

Из оценки (15) следует, что значение сплайна в точке слабо зависит от значений при большом .

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

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

Последняя формула может быть записана в виде

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

Коэффициенты будем находить из системы уравнений, состоящей из совокупности уравнений (9) при и уравнений

(16)

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

Задача 3. Пусть . Показать, что для сплайна, определяемого системой соотношений (9), (16), выполнены оценки

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

Чтобы избежать этого, используем так называемые локальные (аппроксимационные) сплайны.

Локальный сплайн первой степени совпадает с построенным выше сплайном .

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

Построение локального сплайна третьей степени опишем на примере случая постоянного шага . Для этого используется стандартный сплайн третьей степени, определяемый соотношениями

Локальные сплайны третьей степени и записывают в виде

способ выбора будет указан ниже.

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

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

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

Конкретные формулы для вычисления величин имеют вид

Задача 5. Показать, что значение зависит только от значений в четырех ближайших к точках , а значения к шести.

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

Задача 6. Показать, что

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

Задача 7. Пусть при . Показать, что

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

постоянную с порядка 1 выбирают экспериментально.

Как правило, левая и правая части условия (17) равны в точке минимума . Поэтому обычно вместо исходной задачи рассматривают задачу безусловной минимизации по и s функционала

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

Рис. 4.8.1

Литература

1. Бабенко К. И. Основы численного анализа. — М.: Наука, 1986.

2. Бейкер Дж., Грейвс-Моррис П. Аппроксимации Паде. — М.: Мир, 1986.

3. Завьялов Ю. С., Квасов Б.И., Мирошниченко B.Л. Методы сплайн-функций.— М.: Наука, 1980.

4. Стечкин С. Б., Субботин Ю. Н. Сплайны в вычислительной математике.— М.: Наука, 1976.

5. Васильев Ф. П. Численные методы решения экстремальных задач. — М.: Наука, 1980.

6. Васильев Ф. П. Методы решения экстремальных задач. — М.: Наука, 1981.