Сплайн (англ. spline – планка, рейка) – функция, область определения которой разбита на конечное число отрезков, на каждом из которых сплайн совпадает с некоторой алгебраической функцией. Максимальная степень использованных функций (обычно это полиномы) называется степенью сплайна. Разность между степенью сплайна и гладкостью его очертания (отсутствие разрывов по координатам, по первой и второй производным) называется дефектом сплайна. Например, непрерывная ломаная из отрезков прямых есть сплайн степени 1 и дефекта 1 (в точках сопряжения отрезков сплайна происходит разрыв первой производной – гладкость нарушается).

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

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

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

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

2.4. Аппроксимация

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

2.4.1. Полиномиальная аппроксимация

Полином – выражение вида: у =а 0 +а 1 Чх +а 2 Чх 2 +...+а n Чx n

В каждой из n точек, для которых известны значения x i и y i , найдем сумму квадратов отклонений вычисленных и измеренных значений

Для того чтобы отыскать наилучшее приближение, необходимо найти минимум этой функции для переменных: а о, а 1 , а 2 , ..., а n .

Решение : продифференцируем функцию f по каждой из этих переменных и приравняем производную нулю. После несложных преобразований получим систему линейных уравнений. Решив эту систему, можно найти неизвестные коэффициенты полинома а о, а 1 , а 2 , ..., а n .

Коэффициенты при неизвестных	Свободный
a n	...	a 2	a o	член
	...
	...
...	...	....	.....	....
	...		N

Пример полиномиальной аппроксимации данных представлен на рис. 2.10.

Рис. 2.10 Полиномиальная аппроксимация

2.4.2. Линейная аппроксимация

Частным, но и наиболее востребованным случаем полиномиальной аппроксимации является линейная аппроксимация. При линейной аппроксимации функция y (x ) описывает отрезок прямой и имеет вид y (x ) = a + bx (рис. 2.11).

Рис. 2.11. Линейная аппроксимация

2.4.3. Метод наименьших квадратов для произвольной функции

Функция y (x ) может быть представлена произвольной дифференцируемой функцией (рис. 2.12). На практике не рекомендуется использовать функции со степенями выше 4-6 – погрешности реализации при этом сильно возрастают.

Рис. 2.12. Аппроксимация произвольными функциями

2.5. Сглаживание данных

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

При этом вычисляется множество Z =z 1 ,z 2 ,...z n сглаженных значений функции f (x ,y ), заданной множествами значений аргумента X =x 1 ,x 2 ,...x n и Y =y 1 ,y 2 ,...y n соответствующих значений функции.

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

Рис. 2.13. Сглаживание данных

При k = 3 – по каждым трем последовательным точкам (x j -2 ,y j -2),(x j -1 ,y j -1), (x j ,y j) для j =3,...n строится последовательность многочленов первой степени W j (x )=m j x +b j , дающих в этих точках наименьшее отклонение от заданных в смысле наименьших квадратов.

Определение коэффициентов m j и b j многочлена W j (x ) производится методом наименьших квадратов.

Искомые сглаженные значения z j = W j (x ) = m j x + b j вычисляются по формуле:

2.6. Экстраполяция данных (предсказание)

При экстраполяции по ряду заданных точек рассчитывается некоторое число N последующих точек.

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

Рис. 2.14. Экстраполяция данных

2.7. Численное дифференцирование

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

При вычислении производной функции , заданной таблицей – нужно определить значения функции y слева и справа на равном расстоянии от того значения x , для которого мы хотим подсчитать величину производной, и разделить их разность на h (практически это сводится к приближенному определения тангенса угла наклона касательной, чем меньше h , тем точнее результат (рис. 2.15):

Рис. 2.15. Численное дифференцирование

.

Значения можно найти интерполяцией.

2.8. Вычисление определенного интеграла

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

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

Рис. 2.16. Метод трапеций

Соответствующая формула имеет вид:

где для краткости обозначено .

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

Разделим участок интегрирования от x = a до x = b на четное число равных интервалов. Границы интервалов: . Длину интервала обозначим h , так что .

Эта формула называется формулой Симпсона . Преимущества формулы Симпсона по сравнению с формулой трапеций особенно сказывается при увеличении числа n интервалов разбиения. Можно показать, что при этом ошибка формулы трапеций убывает обратно пропорционально n 2 , а ошибка формулы Симпсона – обратно пропорционально n 4 .

2.9. Численное решение дифференциальных уравнений

Дифференциальное уравнение первого порядка : ,

где y – неизвестная функция от x .

Обычно считается, что это уравнение разрешимо относительно производной, т.е. имеет вид: . Для решения уравнения необходимо задание начальных условий: x = x 0 и y = y 0 .

Если уравнение имеет вид и заданы начальные условия x =x 0 и y =y 0 , то, подставляя значения x 0 и y 0 в функцию , мы найдем величину производной в точке x 0: .

Значение функции: , где Dx – малое приращение x .

Отсюда значение функции y 1 = y (x 1) = ,

где x 1 = x 0 + Dx .

Теперь, принимая точку (x 1 ,y 1) за исходную, можно точно таким же образом получить точку y 2 = y (x 2) = , где x 2 = x 1 + Dx . Таким образом, шаг за шагом, можно последовательно вычислять значения функции для различных x .

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

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

, где – удельная равнодействующая сила. (1)

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

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

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

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

Отсюда , и процесс можно повторить для промежутка и т.д. Число h является шагом таблицы.

Рабочая формула для определения значений y по методу Эйлера имеет вид , где

Геометрическая интегральная кривая заменяется ломаной, называемой ломаной Эйлера (рис. 2.17).

Метод Эйлера обладает малой точностью, к тому же погрешность каждого нового шага, вообще говоря, систематически возрастает. Наиболее приемлемым для практики методом оценки точности является в данном случае метод двойного счета – с шагом h и с шагом h/ 2. Совпадение десятичных знаков в полученных двумя способами результатах дает естественные основания считать их верными. Ошибка метода пропорциональна h 2 . Существуют различные уточнения метода Эйлера, повышающие его точность так, что ошибка метода становится пропорциональной h 3 .

Рис. 2.17. Интегральная кривая и ломаная Эйлера

На рис. 2.18 показана кривая скорости, построенная в полном соответствии с вычислительной схемой метода Эйлера.

Рис. 2.18. Предполагаемая схема построения кривой скорости

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

На рис. 2.19 показана кривая скорости, построенная в соответствии с фактически реализуемым алгоритмом.

Рис. 2.19. Фактическая схема построения кривой скорости

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

Причиной такого несоответствия является, вероятно, следующее.

При построении кривой скорости основное уравнение движения поезда приводится к виду

или (2)

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

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

Основное уравнение движения поезда можно интегрировать только по скорости – единственной действительно независимой переменной, входящей в его состав, а метод Эйлера предполагает интегрирование по пути.

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

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

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

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

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

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

Все эти алгоритмы легко реализуемы в современных условиях.

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

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

На рис. 2.20 приведены графики приращений пути и скорости, полученные при построении кривой путем аналитического интегрирования основного уравнения движения поезда по времени ( мин) на площадке с разгоном поезда до установившейся скорости.

Именно такой подход реализован в известной программе тяговых расчетов «ЭРА-ТЭП» – типовой программе ОАО РЖД (Анисимов В.А., ДВГУПС).

Рис. 2.20. Кривая скорости (а) и графики приращений пути и скорости в функции пройденного пути (б)

2.10. Моделирование рельефа местности

Конечным итогом инженерно-геодезических и инженерно-геологических изысканий в настоящее время является цифровая модель местности .

Цифровая модель местности (ЦММ) – множество, элементами которого является топографо-геодезическая информация о местности. Она включает в себя:

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

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

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

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

Общую информацию – название участка, система координат и высот, номенклатура.

Топографическая ЦММ характеризует ситуацию и рельеф местности. Она состоит из цифровой модели рельефа местности (ЦМР) и цифровой модели контуров (ситуации) местности (ЦМК). Кроме этого ЦММ может дополняться моделью специального инженерного назначения (ЦМИ).

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

Рис. 2.21. Электронная карта на основе ЦММ полученной по данным лазерного сканирования

При решении инженерно-геодезических задач на ЭВМ применяют математическую интерпретацию цифровых моделей. Ее называют математической моделью местности (МММ).

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

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

Цифровая модель рельефа местности (ЦМР) представляет собой массив координат съемочных точек X ,Y ,H .

Математическая модель рельефа (ММР) объединяет цифровую модель рельефа и методы аппроксимации точек съемки и интерполяции поверхности земли между ними.

Существует большое число типов ЦМР и ММР, каждая из которых отличается способом аппроксимации рельефа, моделируемого сетью точек съемки и правилами аппроксимации точек съемки и интерполяции – порядка вычисления отметки H точки, заданной координатами X,Y в общем случае, то есть когда данная точка не совпадает ни с одной из точек съемки.

Возможна линейная и сплайновая интерполяция отметок.

По цифровой модели рельефа можно получить продольный профиль земли по любому назначенному направлению (рис. 2.22).

Рис. 2.22. Цифровая модель рельефа и продольный профиль земли по заданному направлению

Наиболее распространенной является триангуляционная модель рельефа местности (TIN ) с линейной интерполяцией отметок.

Суть модели TIN в ее наименовании – «Нерегулярная треугольная сеть» (в английском оригинале – Triangulated Irregular Network ). В своем пространственном выражении это сеть треугольников с высотными отметками в узлах, что позволяет представить моделируемую поверхность как многогранную (рис. 2.23).

Рис. 2.23. Пример триангуляции

Впервые задача построения триангуляционной модели была поставлена в 1934 г. в работе советского математика Б.Н. Делоне.

Для понимания метода триангуляции Делоне необходимо ввести несколько определений.

Определение 1. Триангуляцией называется планарный граф, все внутренние области которого являются треугольниками (рис. 2.23).

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

Определение 3. Триангуляция называется оптимальной, если сумма длин всех рёбер минимальна среди всех возможных триангуляций, построенных на тех же исходных точках (при этом внутрь окружности, описанной вокруг любого построенного треугольника, не попадает ни одна из заданных точек триангуляции) (рис. 2.24).

Рис. 2.24. Триангуляция Делоне

Все известные в настоящее время системы автоматизированного проектирования (САПР) поддерживают функцию создания TIN .

2.11. Моделирование продольного профиля и плана при реконструкции железных дорог

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

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

Цифровая модель продольного профиля (рис. 2.25) позволяет использовать оптимизационные и интерактивные методы проектирования, получить отметки головки рельса между точками съемки. За ось абсцисс всегда принимается ось пути.

Рис. 2.25. Моделирование продольного профиля железных дорог

Проектные отметки продольного профиля вычисляются с учетом наличия вертикальных кривых, устраиваемых в местах переломов проектной линии при достижении разностью уклонов сопрягаемых элементов определенной величины, точнее, если поправка от вертикальной кривой превышает 0,01 м и алгебраическая разность уклонов , где R V - радиус вертикальной кривой (рис. 2.26).

Рис. 2.26. Вертикальная кривая, расчетная схема

В общем случае проектная отметка определяется по следующему алгоритму:

Отметка перелома профиля;

- уклон j -го элемента профиля;

- разность уклонов, ‰;

если , то поправка не вводится, иначе

- отметка в расчетной точке без учета вертикальной кривой;

тангенс вертикальной кривой;

если поправка не вводится - точка лежит за пределами вертикальной кривой), иначе

- поправка от вертикальной кривой;

если то иначе

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

Моделирование плана позволяет произвести расчет параметров его элементов – прямых, круговых и переходных кривых.

Модель плана существующего пути в прямоугольной системе координат (рис. 2.27) предполагает использование и аналогичной координатной модели плана проектного пути (рис. 2.28). Работа с такими моделями «вручную» настолько трудоемка, что до появления ЭВМ такой подход не использовался.

Рис. 2.27. Координатная модель плана существующего пути

Рис. 2.28. Координатная модель плана проектного пути

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

Применялись два типа моделей – угловая диаграмма и график кривизны (стрел).

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

На угловой диаграмме (рис. 2.29) по оси ординат откладываются углы поворота кривой.

На прямых – угол постоянный,

На круговых кривых – изменяется линейно,

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

Рис. 2.29. Угловая диаграмма

Для придания оси пути правильного геометрического очертания необходимо выполнить сдвиги (рихтовки) его оси на некоторую величину, определяемую расчетом.

При использовании угловых диаграмм величина сдвига:

, где U g , U v – углы поворота проектной и существующей оси пути в функции расстояния от начала съемки (угловые диаграммы), S - расстояние от начала съемки до расчетной точки.

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

На графике кривизны (стрел) (рис. 2.30) по оси ординат откладывается кривизна пути (стрелы изгиба). Кривизна – величина обратная радиусу . Стрела (рис. 2.31), f – расстояние от оси пути до хорды определенной длины a , (обычно, 20 м). График кривизны отличается от графика стрел тем, что кривизна определяется в точке, а стрела на хорде. Различия проявляются только в зонах перехода с прямой на переходную кривую и с переходной кривой на круговую кривую.

Рис. 2.30. График кривизны (стрел)

Рис. 3.31. Измерение стрел изгиба

Если стрелу измерять в миллиметрах, то при а = 20 м: .

Для проектного пути, укладываемого в правильное геометрическое положение:

На прямых – кривизна (стрела) равна нулю,

На круговых кривых – кривизна (стрела) постоянна,

На переходных кривых - кривизна (стрела) изменяется линейно.

Сдвиг , где: K g , K v – кривизна оси пути в проектном и существующем положениях в функции расстояния от начала участка съемки, s ; S – расстояние от начала участка до расчетной точки.

Двойной интеграл вычисляется путем двойного суммирования площадей графика кривизны (стрел).

3. МАТЕМАТИЧЕСКИЕ МЕТОДЫ

3.1. Реализация численной модели на ЭВМ

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

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

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

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

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

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

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

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

Исходные положения:

Постановка задачи и предположения о рациональном подходе к ее решению;

Дополнительная информация об исходных данных (числовая область, вид числового материала и др.);

Характеристики вычислительной техники (быстродействие, память и др.);

Представление данных, точность, округление и др.

Требования:

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

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

Минимизация стоимости (времени счета).

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

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

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

3.2. Целевая функция. Ограничения

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

Кривые и поверхности, встречающиеся в практических задачах, часто имеют довольно сложную форму, не допускающую универсального аналитического задания в целом при помощи элементарных функций. Поэтому их собирают из сравнительно простых гладких фрагментов - отрезков (кривых) или вырезков (поверхностей), каждый из которых может быть вполне удовлетворительно описан при помощи элементарных функций одной или двух переменных. При этом вполне естественно потребовать, чтобы гладкие функции, которые используются для построения частичных кривых или поверхностей, имели схожую природу, например, были бы многочленами одинаковой степени. А чтобы получающаяся в результате кривая или поверхность оказалась достаточно гладкой, необходимо быть особенно внимательным в местах стыковки соответствующих фрагментов. Степень многочленов выбирается из простых геометрических соображений и, как правило, невелика. Для гладкого изменения касательной вдоль всей составной кривой достаточно описывать стыкуемые кривые при помощи много-членов третьей степени, кубических многочленов. Коэффициенты таких многочленов всегда можно подобратьтак, чтобы кривизна соответствующей составной кривой была непрерывной. Кубические сплайны, возникающие при решении одномерных задач, можно приспособить к посгрое нию фрагментов составных поверхностей. И здесь вполне естественно появляются бикубические сплайны, описываемые при помощи многочленов третьей степени по каждой из двух переменных. Работа с такими сплайнами требует уже значительно большего объема вычислений. Но правильно организованный процесс позволитучесть непрерывно нарастающие возможности вычислительной техники в максимальной степени. Сплайн-функции Пусть на отрезке , то есть Замечание. Индекс (t) у чисел а^ указывает на то. что набор коэффициентов, которым определяется функция 5(х), на каждом частичном отрезке Д, свой. На каждом из отрезков Д1, сплайн 5(х) является многочленом степени р и определяется на этом отрезке р + 1 коэффициентом. Всего частичных отрезков - то. Значит, для того, чтобы полностью определить сплайн, необходимо найти (р + 1)то чисел Условие) означает непрерывность функции 5(ж) и ее производных во всех внутренних узлах сетки ш. Число таких узлов m - 1. Тем самым, для отыскания коэффициентов всех многочленов получается р(т - 1) условий (уравнений). Для полного определения сплайна недостает (условий (уравнений). Выбор дополнительных условий определяется характером рассматриваемой задачи, а иногда и просто - желанием пользователя. ТЕОРИЯ СПЛАЙНОВ примеры решения Наиболее часто рассматриваются задачи интерполяции и сглаживания, когда требуется построить тот или иной сплайн по заданному массиву точек на плоскости В задачах интерполяции требуется, чтобы график сплайна проходил через точки что накладывает на его коэффициенты m + 1 дополнительных условий (уравнений). Остальные р - 1 условий (уравнений) для однозначного построения сплайна чаще всего задают в виде значений младших производных сплайна на концах рассматриваемого отрезка [а, 6] - граничных (краевых) условий. Возможность выбора различных граничных условий позволяет строить сплайны, обладающие самыми разными свойствами. В задачах сглаживания сплайн строят так, чтобы его график проходил вблизи точек (я»» У»), * = 0, 1,... , т, а не через них. Меру этой близости можно определять по-разному, что приводит к значительному разнообразию сглаживающих сплайнов. Описанные возможности выбора при построении сплайн-функций далеко не исчерпывают всего их многообразия. И если первоначально рассматривались только кусочно полиномиальные сплайн-функции, то по мере расширения сферы их приложений стали возникать сплайны, «склеенные» и из других элементарных функций. Интерполяционные кубические сплайны Постановка задачи интерполяции Пусть на отрезке [а, 6) задана сетка ш Рассмотрим набор чисел Задача. Построить гладкую на отрезке (а, 6] функцию которая принимает в узлах сетки о» заданные значения, то есть Замечание. Сформулированная задача интерполяции состоит в восстановлении гладкой функции, заданной таблично (рис. 2). Ясно, что такая задача имеет множество различных решений. Накладывая на конструируемую функцию дополнительные условия, можно добиться необходимой однозначности. В приложениях часто возникает необходимость приблизить функцию, заданную аналитически, при помощи функции с предписанными достаточно хорошими свойствами. Например, в тех случаях, когда вычисление значений заданной функции /(х) в точках отрезка [а, 6] связано со значительными трудностями и/или заданная функция /(х) не обладает требуемой гладкостью, удобно воспользоваться другой функцией, которая достаточно хорошо приближала бы заданную функцию и была лишена отмеченных ее недостатков. Задача интерполяции функции. Построить на отрезке [а, 6] гладкую функцию а(х), совпадающую в узлах сетки ш с заданной функцией /(х). Определение интерполяционного кубического сплайна Интерполяционным кубическим сплайном S(x) на сетке ш называется функция, которая 1) на каждом из отрезков, представляет собой многочлен третьей степени, 2) дважды непрерывно дифференцируема на отрезке [а, Ь], то есть принадлежит классу С2[а, 6], и 3) удовлетворяет условиям На каждом из отрезков сплайн S(x) является многочленом третьей степени и определяется на этом отрезке четырьмя коэффициентами. Всего отрезков - т. Значит, для того, чтобы полностью определить сплайн, необходимо найти 4т чисел Условие означает непрерывность функции S(x) и ее производных S"(x) и 5"(х) во всех внутренних узлах сетки ш. Число таких узлов - m - 1. Тем самым, для отыскания коэффициентов всех многочленов получается еще 3(m - 1) условий (уравнений). Вместе с условиями (2) получается условия (уравнения). Граничные (краевые) условия Два недостающих условия задаются в виде ограничений на значения сплайна и/или его производных на концах промежутка [а, 6]. При построении интерполяционного кубического сплайна наиболее часто используются краевые условия следующих четырех типов. A. Краевые условия 1-го типа. - наконцах промежутка [а, Ь] задаются значения первой производной искомой функции. Б. Краевые условия 2-го типа. - наконцах промежутка (а, 6) задаются значения второй производной искомой функции. B. Краевые условия 3-го типа. называются периодическими. Выполнения этих условий естественно требовать в тех случаях, когда интерполируемая функция является периодической с периодом Т = Ь-а. Г. Краевые условия 4-го типа. требуют особого комментария. Комментарий. Во внутренних узлах сепси третья производная функции S(x), вообще говоря, разрывна. Однако число разрывов третьей производной можно уменьшить при помоши условий 4-го типа. В этом случае построенный сплайн будет трижды непрерывно дифференцируем на промежутках Построение интерполяционного кубического сплайна Опишем способ вычисления коэффициентов кубического сплайна, при котором число величин, подлежащих определению, равно. На каждом из промежутков интерполяционная сплайн-функция ищется в следующем виде Здесь ТЕОРИЯ СПЛАЙНОВ примеры решения а числа являются решением системы линейных алгебраических уравнений, вид которой зависит от типа краевых условий. Для краевых условий 1-го и 2-го типов эта система имеет следующий вид где Коэффициенты зависят от выбора краевых условий. Краевые условия 1-го типа: Краевые услоемв 2-го типа: В случае краевых условий 3-го типа система для определения чисел записывается так Число неизвестных в последней системе равно тп, так как изусловия периодичности вытекает, что по = пт. Для краевых условий 4-го типа система для определения чисел, имеет вид где По найденному решению системы числа по и пт можно определить при помощи формул Важное замечание. Матрицы всех трех линейных алгебраических систем являются матрицами с диагональным преобладавшем. Тамие матрицы не вырождены, и потому каждая из этих систем имеет единственное решение. Теорема. Интерполяционный кубический сплайн, удовлетворяющий условиям (2) и краевому условию одного из перечисленных четырех типов, существует и единствен. Таким образом, построить интерполяционный кубический сплайн - это значит найти его коэффициенты Когда коэффициенты сплайна найдены, значение сплайна S(x) в произвольной точке отрезка [а, Ь] можно найти г!о формуле (3). Однако для практических вычислений больше подходит следующий алгоритм нахождения величины 5(ж). Пусть х 6 [х», Сначала вычисляются величины А и В по формулам а затем находится величина 5(ж): Применение этого алгоритма существенно сокращает вычислительные затраты на определение величины Советы пользователю Выбор граничных (краевых) условий и узлов интерполяции позволяет в известной степени управлять свойствами интерполяционных сплайнов. А. Выбор граничных (краевых) условий. Выбор граничных условий является одной из центральных проблем при интерполяции функций. Он приобретает особую важность в том случае, когда необходимо обеспечить высокую точность аппроксимации функции f(x) сплайном 5(ж) вблизи концов отрезка [а, 6). Граничные значения оказывают заметное влияние на поведение сплайна 5(ж) вблизи точек а и Ь, и это влияние по мере удаления от них быстро ослабевает. Выбор граничных условий часто определяется наличием дополнительных сведений о поведении аппроксимируемой функции f(x). Если на концах отрезка (а, 6] известны значения первой производной f"(x), то естественно воспользоваться краевыми условиями 1-го типа. Если на концах отрезка [а, 6) известны значения второй производной f"(x), то естественно воспользоваться краевыми условиями 2-го типа. Если есть возможность выбора между краевыми условиями 1-го и 2-го типов, то предпочтение следует отдать условиям 1- го типа. Если f(x) - периодическая функция, то следует остановиться накраевых условиях 3-го типа. В случае, если никакой дополнительной информации о поведении аппроксимируемой функции нет, часто используют так называемые естественные граничные условия Однако следует иметь ввиду, что при таком выборе граничны*условий точность аппроксимации функции f(x) сплайном S(x) вблизи концов отрезка (а, ft] резко снижается. Иногда используются краевые условия 1-го или 2-го типа, но не с точными значениями соответствующих производных, а с их разностными аппроксимациями. Точность такого подхода невысока. Практический опыт расчетов показывает, что в рассматриваемой ситуации наиболее целесообразным является выбор граничных условий 4-го типа. Б. Выбор узлов интерполяции. Если третья производная f""(x) функции терпитразрыв в не которыхточках отрезка [а, Ь], то для улучшения качества аппроксимации эти точки следует включить в число узлов интерполяции. Если разрывна вторая производная /"(х), то для того, чтобы избежать осцилляции сплайна вблизи точек разрыва, необходимо принять специальные меры. Обычно узлы интерполяции выбирают так, чтобы точки разрыва второй производной попадали внутрь промежутка \xif), такого, что. Величину а можно выбрать путем численного эксперимента (часто достаточно положить а =0,01). Существует набор рецептов по преодолению трудностей, возникающих при разрывной первой производной f"{x). В качестве одного из самых простых можно предложить такой: разбить отрезок аппроксимации на промежутки, где производная непрерывна, и на каждом из этих промежутков построить сплайн. Выбор интерполяционной функции (плюсы и минусы) Подход 1-й. Интерполяционный многочлен Лагранжа По заданному массиву ТЕОРИЯ СПЛАЙНОВ примеры решения (рис.3) интерполяционный многочлен Лагранжа определяется формулой Свойства интерполяционного многочленаЛагранжа целесообразно рассматривать с двух противоположных позиций, обсуждая основные достоинства отдельно от недостатков. Основные достоинства 1 -го подхода: 1) график интерполяционного многочлена Лагранжа проходит через каждую точку массива, 2) конструируемая функция легко описывается (число подлежащих определению коэффициентов интерполяционного многочлена Лагранжа на сетке и> равно m + 1), 3) построенная функция имеет непрерывные производные любого порядка, 4) заданным массивом интерполяционный многочлен определен однозначно. Основные недостатки 1 -го подхода: 1) степень интерполяционного многочлена Лагранжа зависит от числа узлов сетки, и чем больше это число, тем выше степень интерполяционного многочлена и, значит, тем больше требуется вычислений, 2) изменение хотя бы одной точки в массиве требует полного пересчета коэффициентов интерполяционного многочлена Лагранжа, 3) добавление новой точки в массив увеличивает степень интерполяционного многочлена Лагранжа на единицу и таиже приводит к полному пересчету его коэффициентов, 4) при неограниченном измельчении сетки степень интерполяционного многочлена Лагранжа неограниченно возрастает. Поведение интерполяционного многочлена Лагранжа при неограниченном измельчении сетки вообше требует особого внимания. Комментарии А. О приближении непрерывной функции многочленом. Известно (Вейерштрасс, 1885 год), что всякая непрерывная (а тем более гладкая) на отрезке функция может быть как угодно хорошо приближена на этом отрезке многочленом. Опишем этот факт на языке формул. Пусть f(x) - функция, непрерывная на отрезке [а, 6]. Тогдадл я любого е > 0 найдется такой многочлен Р„(х),чтодля любого х из промежутка [а, 6] будет выполняться неравенство (рис. 4) Отметим, что многочленов даже одной степени, приближающих функцию f(x) с указанной точностью, существует бесконечно много. Построим наотрезке [а, 6] сетку w. Ясно, что ее узлы, вообще говоря, не совпадают с точками пересечения графиков многочлена Рп(х) и функции f(x) (рис. 5). Поэтому для взятой сетки многочлен Рп(х) не является интерполяционным. При аппроксимации непрерывной функции интерполяционным многочленом Jla-гракжа его график не только не обязан быть близким графику функции f(x) в каждой точке отрезка [а, Ь), но может уклоняться от этой функции как угодно сильно. Приведем два примера. Пример 1 (Рунг, 1901 год). При неограниченном увеличении числа узлов для функции на отрезке [-1, 1] выполняется предельное равенство (рис.6) Пример 2 (Бериштейн, 1912год). Последовательность интерполяционных многочленов Лагранжа построенных на равномерных сетках шт для непрерывной функции /(х) = |х| на отрезке с возрастанием числе узлов т не стремится к функции /(х) (рис.7). Подход 2-й. Кусочно-лииейнм интерполяция При отказе от гладкости интерполируемой функции соотношение между числом достоинств и числом недостатков можно заметно изменить в сторону первых. Построим кусочно-линейную функцию путем последовательного соединения точек (xit у,) прямолинейными отрезками (рис. 8). Основные достоинства 2 -го подхода: 1) график кусочно-линейной функции проходит через каждую точку массива, 2) конструируемая функция легко описывается (число подлежащих определению коэффициентов соответствующих линейных функций для сетки (1) равно 2т), 3) заданным массивом построенная функция определена однозначно, 4) степень многочленов, используемых для описания интерполяционной функции, не зависит от числа узлов сетки (равна 1), 5) изменение одной точки в массиве требует вычисления четырех чисел (коэффициентов двух прямолинейных звеньев, исходящих из новой точки), 6) добавление дополнительной точки в массив требует вычисления четырех коэффициентов. Кусочно-линейная функция достаточно хорошо ведет себя и при измельчении сетки. я Основной недостаток 2-гоподхода: аппроксимирующая кусочно-линейная функция не является гладкой: первые производи ые терпят разрыв в узлах сетки (ушах интерполяции). Подход 3-й. Сплайн-интерполяция Предложенные подходы можно объединить так, чтобы число перечисленных достоинств обоих подходов сохранилось при одновременном уменьшении числа недостатков. Это можно сделать путем построения гладкой интерполяционной сплайн-функции степени р. Основные достоинства 3 -го подхода: 1) график построенной функции проходит через каждую точку массива, 2) конструируемая функция сравнительно легко описывается (число подлежащих определению коэффициентов соответствующих многочленов для сетки (1) равно 3) заданным массивом построенная функция определена однозначно, 4) степень многочленов не зависит от числа узлов сетки и, следовательно, не изменяется при его увеличении, 5) построенная функция имеет непрерывные производные до порядка р - 1 включительно, 6) построенная функция обладает хорошими аппроксимационными свойствами. Краткая справка. Предложенное название - сплайн - не является случайным - введенные нами гладкие ку-сочно-полиномиальныефункции и чертежные сплайны тесно связаны. Рассмотрим гибкую идеально тон кую линейку, проходящую через расположенные на плоскости (х, у) опорные точки массива. Согласно закону Бернулли-Эйлера линеаризованное уравнение изогнутой линейки имеет вид где S(x) - изгиб, М(х) - изменяющийся линейно от опоры к опоре изгибающий момент, Е1 - жесткость линейки. Функция S(x), описывающая формулинейки, является многочленом третьей степени между каждым и двумя соседними точками массива (опорами) и дважды непрерывно дифференцируема на всем промежутке (а, 6). Комментарий. 06 интерполировании непрерывной функции В отличие от интерполяционных многочленов Лагранжа, последовательность интерполяционных кубических сплайнов на равномерной сетке всегдасходится к интерполируемой непрерывной функции, причем с улучшением дифференциальных свойств этой функции скорость сходимости повышается. Пример. Для функции кубический сплайн на сетке с числом узлов m = 6 дает погрешность аппроксимации того же порядка, что и интерполяционный многочлен Ls(z), а на сетке с числом узлов m = 21 эта погрешность настолько мала, что в масштабе обычного книжного рисунка просто не может быть показана (рис.10) (интерполяционный многочлен 1>2о(г) дает в этом случае погрешность около 10 000 Ж). Свойства имтерполяцкокного кубического сплайна А. Алпроксимационмые свойства кубического сплайна. Аппроксимационные свойства интерполяционного сплайна зависят от гладкости функции f(x) - чем выше гладкость интерполируемой функции, тем выше порядок аппроксимации и при измельчении сетки тем выше скорость сходимости. Если интерполируемая функция f(x) непрерывна на отрезке Если интерполируемая функция f{x) имеет на отрезке [а, 6] непрерывную первую производную, то есть интерполяционный сплайн, удовлетворяющий граничным условиям 1-го или 3-го типа, то при h О имеем В этом случае не только сплайн сходится к интерполируемой функции, но и производная сплайна сходится к производной этой функции. В случае, если сплайн S(x) аппроксимирует на отрезке [а, Ь] функцию f(x), а его первая и вторая производные аппроксимируют соответственно функции Б. Экстремальное свойство кубического сплайна. Интерполяционный кубический сплайн обладает еще одним полезным свойством. Рассмотрим следующий пример. ример. Построить функцию/(х), минимизирующую функционал на классе функций из пространства С2, графики которых проходят через точки массива Среди всех функций, проходящих через опорные точки (х;, /(х,)) и принадлежащих указанному пространству, именно кубический сплайн 5(х), удовлетворяющий краевым условиям доставляет Экстремум (минимум) функционалу Замечание 1. Часто именно это экстремальное свойство берут в качестве определения интерполяционного кубического сплайна. Замечание 2. Интересно отметить, что интерполяционный кубический сплайн обладает описанным выше экстремальным свойством на очень широком классе функций, а именно, на классе |о, 5 ]. 1.2. Сглаживающие кубические сплайны О постановке задачи сглаживания Пусть заданы сетка и набор чисел Комментарий к исходным данным На практике часто приходится иметь дело со случаем, когда значения у, в массиве заданы с некоторой погрешностью. Фактически это означает, что для каждого указан интервал и любое число из этого интервала может быть взято в качестве значения у, . Величины у, удобно интерпретировать, например, как результаты измерений некоторой функции у(х) при заданных значениях переменной х, содержащие случайную погрешность. При решении задачи восстановления функции по таким ее «экспериментальным» значениям вряд ли целесообразно использовать интерполяцию, поскольку интерполяционная функция будет послушно воспроизводить причудливые осцилляции, обусловленные случайной компонентой в массиве {у,}. Более естественным является подход, основанный на процедуре сглаживания, призванной как-то уменьшить элемент случайности в результате измерений. Обычно в таких задачах требуется найти функцию, значения которой при х = ж, * = 0, 1,.... т, попадали бы в соответствующие интервалы и которая обладала бы, кроме того, достаточно хорошими свойствами. Например, имела бы непрерывные первые и вторые производные, или же ее график был бы не слишком сильно искривлен, то есть не имел бы сильных осцилляций. Задача подобного рода возникает и тогда, когда по заданному (точно) массиву требуется построить функцию, которая проходилабы нечереззаданныеточки, а вблизи них и к тому же изменялась достаточно плавно. Другими словами, искомая функция как бы сглаживала заданный массив, а не интерполировала его. Пусть заданы сетка ш и два набора чисел ТЕОРИЯ СПЛАЙНОВ примеры решения Задача. Построить гладкую на отрезке [а, А] функцию, значения которой в узлах сетки и» отличались от чисел у,- на заданные величины -Зшочтио. Сформулированная задача сглаживания состоит в восстановлении гладкой функции, заданной таблично. Ясно, что такая задача имеет множество различных решений. Накладывая на конструируемую функцию дополнительные условия, можно добиться необходимой однозначности. Определение сглаживающего кубического сплайна Сглаживающим кубическим сплайном S(x) на сетке ш называется функция, которая 1) на каждом из отрезков представляет собой многочлен третьей степени, 2) дважды непрерывно дифференцируема на отрезке [а, 6], то есть принадлежит классу С2 [а, Ь], 3) доставляет минимум функционалу где - заданные числа, 4) удовлетворяет граничным условиям одного из трех указанных ниже типов. Граничные (краевые) условия Граничные условия задаются в виде ограничений на значения сплайна и его производных в граничных узлах сетки ш. А. Граничные условия 1-го типа. - наконцах промежутка [а, Ь) задаются значения первой производной искомой функции. Граничные условия 2-го типа. - вторые производные искомой функции на концах промежутка (а, Ь] равны нулю. В. Граничные условия 3-го типа. называются периодическими. Теорема. Кубический сплайн S(x), минимизирующий функционал (4) и удовлетворяющий краевым условиям одного из указанных трех типов, определен однозначно. Определение. Кубический сплайн, минимизирующий функционал J(f) и удовлетворяющий граничным условиям i-готипа, называется сглаживающим сплайном i-готипа. Замечание. На каждом изотрезков(,сплайн 5(х) является миоючасном третьей степени и определяется на этом отрезке четырьмя коэффициентами. Всего отрезков - т. Значит, для того, чтобы полностью определять сплайн, необходимо найти 4т чисел Условие означает непрерывность функции 5(аг) и се производных во всех внутреннж узлах сетки о». Число таких узлов - m - 1. Тем самым, для отысивния коэффициентов всех многочленов получается 3(m - 1) условий (уравнений). Построение сглаживающего кубического сплайна Опишем способвычисления коэффициентов кубическогосплайна, при котором число величин, подлежащих определению, равно 2т + 2. На каждом из промежутков сглаживающая сплайн-функция ищется в следующем виде Здесь а числа и, являются решением системы линейных алгебраических уравнений, вид которой зависитот типа краевых условий. Опишем сначала, как находятся величины п*. Для краевых условий 1-го и 2-го типов система линейных уравнений для определения величин Hi записывается в следующем виде где известные числа). Коэффициенты зависят от выбора граничных условий. Граничные условия 1-го типа: Граничные условия 2-го типа: В случае граничных условий 3-го типа система для определения чисел записывается так: причем все коэффициенты вычисляются по формулам (5) (величины с индексами к и т + к считают я равными: Важно* замечание. Матрицы систем не вы рождены и потому каждая из этих систем имеет единственное решение. Если числа п,- найдены, то величины легко определяются по формулам где В случае периодических граничных условий Выбор еесоеш коэффициентов Выбор весовых коэффициентов р,-, входящих в функционал (4), позволяете известной степени управлять свойствами сглаживающих сплайнов. Если все и сглаживающий сплайн оказывается интерполяционным. Это, в частности, означает, что чем точнее заданы величины, тем меньше дошкн ы быть соотпетствуюшие весовые коэффициенты. Если же необходимо, чтобы сплайн прошел через точку (х^, Ук), то отвечающий ем у весовой множитель р\ следует поломить равным нулю. В практический вычислениях наиболее важым является выбор величин pi-Пусть Д, - погрешность измерения величины у,. Тогда естественно потребовать, чтобы сглаживающий сплайн удовлетворял условию или, что то же, В простейшем случае весовые коэффициенты pi можно задать, например, форму- где с - некоторая достаточно малая постоянная. Однако такой выбор весов р, не позволяет использовать «коридор», обусловленный погрешностями величин у,-. Более рациональный, но и более трудоемкий алгоритм определения величин р,- может выглядеть следующим образом. Если на fc-й итерации величины найдены,то полагают где е - малое число, которое выбирается экспериментально с учетом разрядной сетки компьютера, значений Д, и точности решения системы линейных алгебраических уравнений. Если на fc-й итерации в точке я, нарушилось условие (6), то последняя формула обеспечит уменьшение соответствующего весового коэффициента р,. Если же то на следующей итерации Увеличение р, приводит к более полному использованию «коридора» (6) и, в конечном счете, более плавно изменяющемуся сплайну. Немного теории А. Обоснование формул для вычисления коэффициентов интерполяционного кубического сплайна. Введем обозначения где m, - неизвестные пока величины. Их число равно m + 1. Сплайн, записанный в форме, где удовлетворяет условиям интерполяции и непрерывен на всем промежутке [а, Ь\: положив в формуле, получим соответственно Кроме того, он имеет на промежутке [а, 6] непрерывную первую производную: продифференцировав соотношение (7) и положив, пОлучим соответ-. ственно. Покажем, что числа т, можно выбрать так, чтобы сплайн-функция (7) имела на отрезке [а, 6] непрерывную вторую производную. Вычислим на промежутке вторую производную сплайна: В точке х, - 0 (при t = 1) имеем Вычислим на промежутке вторую производную сплайна В точке имеем Из условия непрерывности второй производной во внутренних узлах сетки а; получаем m - 1 соотношение где Добавляя к этим т - 1 уравнениям еще два, вытекающих и з краевых условий, получаем систему из m+ 1 линейного алгебраического уравнения с т + I неизвестной miy i = 0, 1. ... , m. Система уравнений для вычисления величин гщ в случае краевых условий 1-го и 2-го типов имеет вид где (краевые условия 1 -го типа), (краевые условия 2 -го типа). Для периодических краевых условий (краевыеусловия 3-го типа) сетку о; удлиняют еще на один узел и полагают Тогда система для определения величин го* будет иметь вид Для того чтобы получить систему уравнений для определения чисел го, в случае краевых условий 4-го типа, найдем на отрезке [ третью производную сплайна (7) и потребуем ее непрерывности во втором и (го - !)-м узлах сетки. Имеем Из последних двух соотношений получаем недостающие два уравнения, отвечающие краевым условиям 4 -го типа: Исключая из уравнений неизвестное гоо, а из уравнений неизвестное пц, в результате получим систему уравнений Отметим, что число неизвестных в этой системе равно го - I. 6. Обоснование формул дм вычисления юэффиие кто« сглаживающего субичессого сплайна. Введем обозначения где Zi и nj - неизвестные пока величины. Их число равно 2т + 2. Сплайн-функиия, записанная в форме непрерывна на всем промежутке (а, 6]: положив в этой формуле, получим соответственно Покажем, что числа z, и п, можно выбратьтак, чтобы сплайн, записанный в форме (8), имел на промежутке [а, 6] непрерывную первую производную. Вычислим первую производную сплайна S(x) на промежутке : В точке х^ - 0 (при t = 1) имеем Вычислим первую производаую сплайна 5(х) на промежутке : В точке имеем Из условия непрерывности первой производой сплайна во внутренних узлах сетки и --> получаем m - 1 соотношение Эту связь удобно записать в матричной форме Здесь использованы следующие обозначения Кроме того, сплайн на промежутке [а, 6} имеет непрерывную вторую производную: продифференцировав соотношение (8) и положив, получим соответственно Еше олю матричное соотношение получается из условия минимума функционала (4). Имеем Два последних матричных равенства можно рассматривать как линейную систему 2т+2 линейных алгебраических уравнений относительно 2т + 2 неизвестных. Заменяя в первом равенстве столбец г его выражением, полученным из соотношения (9), приходим к матричному уравнению ТЕОРИЯ СПЛАЙНОВ примеры решения для определения столбца М. Это уравнение имеет единственное решение вследствие того, что матрица A + 6HRH7 всегда невырождена. НаЙдяего, мылегко определяем г. Эамсшине. Элементы трелдмаголальн ых матриц А и Н определяющие я только параметрами сетки и (сс шагами hi) и не зависят от величин у^. Линейное пространство кубических сплайн-функций Множество кубических сплайнов, построенных на отрезке [а, 6) по сетке wcra+l узлом, является линейным пространством размерности т + 3: 1) сумма двух кубических сплайнов, построенных по сетке и>, и произведение кубического сплайна, построенного по сетке и>, на произвольное число тайнее являются кубическими сплайнами, построенными по этой сетке, 2) любой кубический сплайн, построенный по сетке и из узла, полностью определяется т + 1 значением величин у» в этих узлах и двумя граничными условиями - всего то + 3 параметрами. Выбрав в этом пространстве базис, состоящий из m + 3 линейно независимых сплайнов, мы можем записать произвольный кубический сплайн а(х) в виде их линейной комбинации причем единственным образом. Замечание. Подобное задание сплайна широко распространено в вычислительной практике. Особенно удобным является базнс, состоящий из так называемых кубических В -сплайнов (базовых, или фундаментальных, сплайнов). Применение Д-сплайнов позволяет существенно снизить требования к объему памяти компьютера. Л-сплайны. В -сплайномнулевой степени, построенным на числовой прямой по сетке ш, называется функция вила В -сплайн степени к ^ I, построенный на числовой прямой по сетке иг, определяется посредством рекуррентной формулы Графики В -сплайнов первой В,-1"(ж) и второй в\7\х) степеней представлены на рис. 11 и 12 соответственно. В-сплайн произвольной степени к может быть отличен от нуля только на некотором отрезке (определяемом к + 2 узлами). Кубические В-сплайны удобнее нумеровать так, чтобы сплайн В,-3* (я) был отличен от нуля на отрезке яг,-+2]. Приведем формулу для кубического сплайна третьей степени для случая равномерной сетки (с шагом Л). Имеем в остальных случаях. Типичный график кубического В-сплайна представлен на рис. 13. Займами*. функция а) дважды непрерывно дифференцируема на отрезке то есть принадлежат классу С2[а, »}, к б) отлична от нуля толь ко на четырех последовательных отрезках (Дополним сетку ш вспомогательными узлами взятыми совершенно произвольно. По расширенной сетке ш* можно построить семейство из m + 3 кубических В -сплайнов: Это семейство образует базис в пространстве кубических сплайнов на отрезке (а, Ь]. Тем самым, произвольный кубический сплайн S(z), построенный на отрезке |в, 6] посетке о; изт+1 узла, может быть представлен наэтом отрезке в виде линейной комбинации Условиями задачи коэффициенты ft, этого разложения определяются однозначно. ... В случае, когда заданы значения у* функции в узлах сетки и значения у о и Ут первой производной функции на концах сетки"(задача интерполяций с граничными условиями первого рода), эти коэффициенты вычисляются из системы следующего вида После исключения величин б-i и &m+i получается линейная система с неизвестными 5q, ... , Ьт и трех диаюнальной матрицей. Условие обеспечивает диагональное преобладание и, значит, возможность применения метода прогонки для ее разрешения. 3ММЧМЮ 1. Линейные системы аналогичного вида возникают лрн рассмотрении и других задач интерполяции. Зммчнм* 2. В сравнении с алгоритмами, описанными в раздеде 1.1, применение Я-сплайн в * задачах интерполяции позволяет уменьшит* объем хранимой информации, то есть сушественно снизить требования к объему памяти компьютере, хотя и приводит к увеличению числа операций. Построение сплайноаых кривых при помощи сплайн-функций Выше рассматривались массивы, точки которых были занумерованы так, что их абсциссы образовывали строго возрастающую последовательность. Например, случай, изображенный на рис. 14, когда у разных точек массива одинаковые абсциссы, не допускался. Это обстоятельств о определяло и выбор класса аппроксимирующих кривых (трафики функций), и способ их построения. Однако предложенный выше метод позволяет достаточно успешно строить интерполяционную кривую и в более общем случае, когда нумерация точек массива и их расположение на плоскости, как правило, не связаны (рис. 15). Более того, ставя задачу построения интерполяционной кривой, можно считать заданный массив неплоски м, то есть Ясно, что для решения этой общей задачи необходимо существенно расширить класс допусти мых кривых, включив в него и замкнутые кривые, и кривые, имеющие точки самопересечения, и пространственные кривые. Такие кривые удобно описывать при помощи параметрических уравнений Потребуем. дополнительно, чтобы функции обладали достаточной гладкостью, например, принадлежали классу С1 [а, /0] или классу Для отыскания параметрических уравнений кривой, последовательно проходящей через все точки массива, поступают следующим образом. 1-й шаг. На произвольно взятом отрезке {\displaystyle } , называется полиномиальным сплайном порядка m {\displaystyle m} с узлами x j ∈ (a ≤ x 0 < . . . < x n ≤ b) {\displaystyle x_{j}\in (a\leq x_{0}<..., если на каждом из отрезков [ x j − 1 , x j) {\displaystyle (3) {\displaystyle \left[{\begin{array}{*{20}{c}}{{P_{j}}({t_{j}})=f({t_{j}})}\\{{P_{j}}({t_{j-1}})=f({t_{j-1}})}\\{{{P"}_{j}}({t_{j}})=f"({t_{j}})}\\{{{P"}_{j}}({t_{j-1}})=f"({t_{j-1}})}\\\end{array}}\right]\qquad (3)}

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

Для полиномов чётных степеней при сборке системы (3):

• остаётся неопределённой производная в одном из концов отрезка;
• и условие равенства производных (гладкости кривой) не будет выполняться,

поэтому для полинома 2-й степени невозможно достичь равенства 1-й производной в точках стыка, а для 4-й степени - 2-й производной и т. д. Для построения сплайнов с чётными степенями искусственно добавляют дополнительные условия, чтобы сформировать систему уравнений, подобную (3). Если производные полинома сплайна определяются так же, как соответствующие производные интерполируемой функции, сплайн называется эрмитовым .

P j (n) (t j) = f n (t j) , P j (n) (f j − 1) = f n (t j − 1) (4) {\displaystyle P_{j}^{(n)}({t_{j}})={f^{n}}({t_{j}}),\qquad P_{j}^{(n)}({f_{j-1}})={f^{n}}({t_{j-1}})\qquad (4)}

Существуют локальные методы построения сплайнов Бесселя и Акими, B - сплайны [ ] . В основном, когда речь идёт о сплайнах, то имеют в виду сплайны, построенные из алгебраических полиномов. Именно к ним относится приведённое выше определение. Именно эти сплайны являются наиболее изученными. Однако, сплайн может состоять из фрагментов функций любого класса. В [ ] рассмотрено построение таких сплайнов и исследуются их свойства. Автор [кто? ] не даёт общего определения построенных сплайнов. Очевидно, что для любых классов функций, из которых состоит сплайн, приведённое в начале статьи определение не совсем подходит. Например, если сплайн состоит из отрезков экспоненты, то понятие дефекта сплайна теряет смысл. Хотя количество непрерывных производных останется важной характеристикой. Построение сплайна, фрагментами которого являются разрывные функции (рациональные функции, функции Паде), несколько выходит за рамки сплайновой идеи, поскольку одним из основных преимуществ сплайнов является их гладкость. Если произвольно расширять такие конструкции, то стираются различия сплайнов от кусковых функций. Другим преимуществом сплайнов является эффективность вычислений. Чрезмерное усложнение фрагментов существенно снижает преимущество сплайнов перед классическими функциями.

Для сплайнов характерны следующие признаки: сплайн состоит из фрагментов - функций одного класса, которые отличаются только своими параметрами, на соседние фрагменты в точках стыковки накладываются определённые условия, которые сводятся к непрерывности значений и некоторых первых производных. Сплайны - направление прикладной математики, которое интенсивно развивается. В Интернете содержится обширная библиография по сплайнам (Spline bibliography database (SBD)).

Классификация сплайнов

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

Назначение сплайнов . По назначению можно выделить три основные группы сплайнов: «интерполяционные сплайны» или «функциональные сплайны» - проходящие точно через заданные точки, «сглаживающие сплайны» - проходящие через заданные точки с учётом погрешностей их определения; «корреляционные сплайны» - проходящие через корреляционное множество точек и отображающие его генеральную зависимость (тренд, регрессию). Интерполяционные и функциональные сплайны используют в задачах геометрического моделирования, например, задания обводов корпусов водных и воздушных судов. Сглаживающие сплайны используют чаще всего для описания зависимостей физических экспериментов с известной погрешностью измерений. Корреляционные сплайны используют в качестве нелинейных графиков регрессии, простейшими из которых можно считать описание зависимости ступенчатой и кусочно-линейной функцией (сплайнами нулевой и первой степени).

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

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

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

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

Тригонометрическими являются сплайны, фрагменты которых описываются тригонометрическими полиномами . Имеют достаточно сложные расчётные выражения. Более пятидесяти различных по виду фрагментов сплайнов описаны в работах Б. А. Попова.

Также существуют рациональные сплайны и сплайны Паде. Их особенностью является возможность разрыва производных на фрагментах, при непрерывности в узлах. М. Ансерме строит фракциональные сплайны, где фрагменты заданы с помощью гамма-функции.

Целесообразность применения фрагментов определённого вида основана на конкретных условиях задачи и ограничениях реализации. Как правило, основное требование - это достижение заданной точности интерполяции при приемлемых затратах времени и ресурсов на реализацию. Удачный выбор фрагментов, который соответствует характеру процесса, позволяет сократить время вычислений и требуемый объём памяти.

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

Ширина фрагментов . Следует выделить сплайны с равной шириной фрагментов. Это позволяет значительно упростить расчётные выражения, ускорить работу алгоритмов и снизить затраты на реализацию. Определённого упрощения можно достичь за счёт применения фрагментов с кратной шириной. Существуют сплайны с нулевой шириной фрагментов (Де Бур). Это приводит к кратности узлов и возможности приближать сплайны с неразрывными фрагментами разрывных функций. Расчётные выражения получают в результате предельных переходов. Сплайны могут иметь также фрагменты с бесконечной шириной. Эти фрагменты должны быть крайними. Иногда это позволяет естественно задать краевые условия. Строго говоря, ширина фрагментов зависит от выбора параметра - аргумента сплайн-функции, а для этого требуется решать отдельную задачу параметризации. Идеальным выбором в качестве параметра является длина интерполируемой функции, которая не всегда известна, поэтому существует множество способов решения этой задачи. Наиболее распространён способ параметризации по хордам.

Условия стыковки фрагментов . Ещё один важный признак, что отличает сплайны. Когда идёт речь о сплайнах, как правило, считают, что фрагменты стыкуются гладко. То есть обеспечивается непрерывность значений и первой производной. Понятие дефекта сплайна связано с числом непрерывных производных, которые имеет функция-фрагмент определённого вида и числом производных, непрерывность которых гарантирована в узлах. Экспонента , синусоида имеют бесконечное число производных. Для них это понятие не имеет смысла. Поэтому удобнее говорить прямо о числе производных, непрерывность которых гарантирована в узлах сплайна. Практически речь идёт о непрерывности значений и первой, максимум второй производной. Разрыв второй и высших производных визуально не заметно, поэтому учитывается редко. Понятно, что первая производная в точках стыка может задаваться по-разному. Наиболее распространены два приёма. Значение первой производной выбирается так, чтобы обеспечить непрерывность второй (глобальные кубические сплайны минимального дефекта). Первая производная равняется первой производной интерполируемой функции (возможно приближённо) в эрмитовых сплайнах.

Краевые условия . Имеется 4 типа классических краевых условий и ряд неклассических. Если сплайны имеют ограниченное число фрагментов, то, естественно, у них отсутствуют крайние фрагменты слева и справа, поэтому крайние узлы не с чем стыковать. Исключением являются лишь периодические сплайны, которые имеют естественное продолжение (3-й тип классических краевых условий). Иногда естественными называют краевые условия с нулевой производной, хотя никаких оснований считать их более естественными, чем другие, нет, но для кубического сплайна естественные (натуральные) краевые условия являются частным случаем 2-го типа классических краевых условий, задающего вторые производные на краях сплайна. В этом случае приравнивание вторых производных к нулю высвобождает края металлической линейки от нагружения изгибающим моментом, что естественным образом и происходило бы при прикладывании её к фиксированным (заданным) узлам в физическом пространстве. В 1-м типе классических краевых условий задают первые производные (касательные) на краях сплайна; во 2-м типе - задают вторые производные (кривизну); 3-й тип используется для интерполяции замкнутых или периодических линий и заключается в стыковке крайних фрагментов сплайна; 4-й тип используется когда на краях сплайна неизвестны ни первая, ни вторая производные и заключается в стыковке соседних пар крайних фрагментов (1-го со 2-м и последнего с предпоследним) по третьим производным, что на практике реализуется в проведении по узлам пар соседних крайних фрагментов функции, аналогичной одному фрагменту сплайна (у полиномиального сплайна - полинома той же степени, что и фрагмент сплайна). Используются различные комбинации краевых условий, которые сводятся к данным 4-м типам классических условий. В случае, если краевые условия нельзя свести к этим четырём типам, как, например, изменение на паре соседних крайних фрагментах сплайна его третьей производной по линейному (афинному) закону, предложенное в работах Снигирева В. Ф., то такие условия называют неклассическим вариантом краевых условий. Далее приведены некоторые варианты, сводящиеся к классическим краевым условиям. Если сплайн имеет фрагменты одинаковой ширины, считают недостающие фрагменты той же ширины. Другой вариант - это считать недостающие фрагменты продлёнными в бесконечность. Преимущество такого подхода в возможности экстраполяции . Можно считать ширину фрагментов нулевой. Расчётные выражения получают предельными переходами. Если взглянуть на краевые условия с точки зрения формирования сплайна из базисных функций, то они сводятся к продолжению соответствующих локальных базисных функций. Ширина соседних фрагментов влияет на их форму. А простое обрезание часто приводит к осцилляции и росту погрешности на краях. Важное значение краевые условия имеют при обработке изображений и в задачах с экстраполяцией.

Дополнительные ограничения . Они чаще всего касаются производных в узлах. Иногда они вытекают из физики процесса. Условия: неотъемлемость значений, равенство моментов, площадей, условия нормирования. Дополнительные условия иногда упрощают анализ свойств сплайнов, но могут серьёзно затруднять построение и затраты реализации.

Сетка точек интерполяции. Может существенно влиять на эффективность расчётов. Важны случаи равномерной сетки и равномерной сетки, с расстоянием между точками, кратным расстоянию между узлами сплайна. Нахождение сетки точек интерполяции (интерполяционных узлов) является задачей параметризации, о которой уже сказано в разделе «Ширина фрагментов».

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

Форма представления . Функции, задающие фрагменты сплайна, как правило, зависят от множества параметров, благодаря которым они меняют свою форму. Значения параметров на каждом из фрагментов индивидуальны. Эти параметры могут задавать конкретный сплайн. Для полиномиальных сплайнов это полиномиальные коэффициенты. Так, сплайн можно представить множеством параметров функций на каждом из фрагментов. Назовем это представление пофрагментным. Такое представление является наглядным, часто имеет явный физический смысл. Но число параметров является чрезмерным. Так, для кубического сплайна необходимо иметь 4 * (r-1) параметров (r - число узлов сплайна). Данное представление получается в результате неопределённого интегрирования фрагмента исходного сплайнового дифференциального уравнения и называется аналогичной кусочно-полиномиальной формой (pp-формой) по аналогии с полиномиальными сплайнами. Для явного выражения коэффициентов через уже известные значения координат узловых точек, применяют разложение аналогичной кусочно-полиномиальной формы на базисные функции путём подстановки её в краевые условия Эрмита (граничные условия фрагмента сплайна, условия интерполирования и опирания на производные). В результате получается базисная форма (B-форма) сплайна. Такое представление сплайна является значительно более компактным и записывается через базисные сплайн-функции в виде:

S (x) = ∑ j = 1 r a j B j (x) {\displaystyle S(x)=\sum \limits _{j=1}^{r}{{a_{j}}{B_{j}}(x)}} ,

где B j (x) {\displaystyle {B_{j}}(x)} - базисные сплайн-функции (как правило локальные), a j {\displaystyle a_{j}} - числовые коэффициенты, задающие вес базисных функций при формировании сплайна, физическим смыслом которых являются обобщённые (линейные и угловые) перемещения металлической линейки в узлах. Число параметров, задающих сплайн, равно числу узлов сплайна. Между параметрами функции на фрагменте и коэффициентами полинома-сплайна существует зависимость, что позволяет с одними коэффициентами находить другие, хотя формулы могут иметь достаточно сложный вид.

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

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

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

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

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

См. также

Примечания

Вершинин В. В., Завьялов Ю. С, Павлов Н. Н. Экстремальные свойства сплайнов и задача сглаживания. - Новосибирск: Наука, 1988, УДК 519.651

Роженко Александр Иосифович. Теория и алгоритмы вариационной сплайн-аппроксимации : Дис. … д-ра физ.-мат. наук: 01.01.07: Новосибирск, 2003 231 c. РГБ ОД, 71:05-1/136

Шикин Е. В., Плис Л. И. Кривые и поверхности на экране компьютера. Руководство по сплайнам для пользователей. - М.: ДИАЛОГ-МИФИ, 1996. - 240 с. ISBN 5-86404-080-0 , УДК 681.3 Ш57

Хакимов Б.В. Моделирование корреляционных зависимостей сплайнами на примерах в геологии и экологии. - СПб. : Нева, 2003. - 144 с. - ISBN 5-211-04588-2 .

Павленко Алексей Петрович. Применение обобщённых решений для проектирования балочных элементов конструкций самолёта и формирования функциональных сплайнов : Дис. … канд. техн. наук: 05.07.02, 05.13.18 Казань, 2007. 185 РГБ ОД, 61 07-5/5391

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

Основными элементами сплайнов являются вершины (Vertex) и сегменты (Segment). Вершинами называют точки, расположенные на сплайне, при этом первая вершина, обозначающая начало сплайна, отмечается квадратиком белого цвета. Под сегментом принято понимать участок линии сплайна, ограниченный двумя соседними вершинами, - сегменты могут быть как прямо-, так и криволинейными отрезками. Вершины сплайна различаются по типу, от которого зависит степень кривизны прилегающих к данным вершинам сегментов сплайна. Всего выделяют четыре типы вершин (рис. 1):
Corner (Угловая) - вершина, в которой сплайн имеет излом, а примыкающие к ней сегменты лишены кривизны.
Smooth (Сглаженная) - вершина, через которую кривая сплайна проводится с плавным изгибом, а кривизна прилегающих к вершине сегментов одинакова с обеих сторон.
Bezier (Безье) - вершина, напоминающая сглаженную и отличающаяся от нее возможностью управления степенью кривизны обоих сегментов. Последнее осуществляется благодаря наличию в вершине касательных векторов, ограниченных на концах маркерами в виде квадратиков зеленого цвета и называемых ручками Безье. Перемещая ручки Безье, можно изменять направление, в соответствии с которым сегменты сплайна входят в вершину и выходят из нее, а изменяя расстояние от маркеров до вершины - регулировать степень кривизны сегментов сплайна. У вершин данного типа ручки Безье связаны между собой, и перемещение одной из них автоматически вызывает перемещение второй.
Bezier Corner (Безье угловая) - вершина, имеющая касательные векторы, позволяющие управлять степенью кривизны сегментов, однако, в отличие от вершин Bezier, у вершин Bezier Corner касательные векторы не связаны друг с другом и перемещение одного из маркеров не зависит от перемещения другого.

Сегменты также различаются по типу: Curve (Кривая) или Line (Линия). Выбрав типа Curve, можно получить криволинейные сегменты, если вершины являются гладкими или имеют тип Безье, в случае же угловых вершин даже при установке типа Curve сегмент останется линейным. Выбор типа Line приводит к игнорированию типа вершин, в результате чего сегмент данного типа всегда выглядит линейным.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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