Теория сплайнов примеры решения

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

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

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

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

где a i ,b i ,c i ,d i - коэффициенты сплайна, определяемые из дополнительных условий; i = 1,2,3,....n - номер сплайна.

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

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

1. Равенство значений сплайнов и функции f(x) в узловых точках - условия Лагранжа:

, . (6.10)

2. Непрерывность первой и второй производных от сплайнов в узлах:

Кроме перечисленных условий, следует добавить условия на концах, т. е. в точках x 0 и x n . В общем случае эти условия зависят от конкретной задачи. Мы воспользуемся условиями свободных концов сплайнов, т.е. вне интервала функция описывается полиномом первой степени - прямой линией:

, . (6.12)

Условия (6.10)-(6.12) позволяют найти коэффициенты a i ,b i ,c i ,d i всех n сплайнов. Их значения выражаются следующими формулами:

, (6.13)

где в первых трех уравнениях i = 1,2,...n , а в третьем i = 2,3,..n ;

h i =x i -x i -1 - i -й шаг аргумента.

Учитывая индексацию для с i , добавим значения этого коэффициента на концах сплайна

Сначала решается система из n - 1 линейных уравнений для с i . Затем определяются b i и d i по известным коэффициентам с i , а i известно - это значения функции f(x) в узловых точках. В каждое уравнение для определения с i входит только три неизвестных с последовательными значениями индексов c i - 1 ,c i ,c i +1 . Такая матрица, имеющая отличные от нуля только элементы главной и двух соседних диагоналей, называется трехдиагональной.

Программная реализация рассмотренного алгоритма приведена ниже (ПРОГРАММА 6.2). Приведен фрагмент, в котором рассчитываются коэффициенты сплайнов по узловым значениям интерполируемой функции.

Для формирования трехдиагональной матрицы Kc использован массив шагов аргумента h i . В процедуре Gauss рассчитывается вспомогательный массив cv, имеющий на 2 элемента меньше, чем массив с., так как с 0 и c n +1 известны и равны нулю. При большом числе уравнений для решения систем с трехдиагональной матрицей применяют метод прогонки , являющийся вариантом метода последовательных исключений. Результаты расчетов с использованием интерполяции сплайнами приведены на рис.6.4. В качестве интерполируемой функции был взят ток катушки электромагнита.

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

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

Рассмотрим задачу проведения гладких кривых по заданным граничным точкам, или задачу интерполяции. Поскольку через две точки можно провести сколь угодно много гладких кривых, то для решения этой задачи необходимо ограничить класс функций, которые будут определять искомую кривую. Математическими сплайнами называют функции, используемые для аппроксимации кривых. Важным их свойством является простота вычислений. На практике часто используют сплайны вида полиномов третьей степени. С их помощью довольно удобно проводить кривые, которые интуитивно соответствуют человеческому субъективному понятию гладкости. Термин “сплайн” происходит от английского spline – что означает гибкую полоску стали, которую применяли чертежники для проведения плавных кривых, например, для построения обводов кораблей или самолетов.

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

1) Функция должна проходить через все заданные точки: , .

2) Функция должна быть дважды непрерывно дифференцируема, то есть иметь непрерывную вторую производную на всем отрезке .

На каждом из отрезков , будем искать нашу функцию в виде полинома третьей степени:

Рис. 40. Сплайновая функция.

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

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

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

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

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

Перепишем выражение для в векторном виде:

Обозначим вектор строку и вектор столбец коэффициентов , тогда .

Из (*) следует, что , . Для касательных ,

Отсюда получаем векторно-матричное уравнение:

Эта система решается относительно нахождением обратной матрицы размером .

Здесь - эрмитова матрица, - геометрический вектор Эрмита. Подставим выражение для нахождения : . Аналогично для остальных координат: , .

Выпишем в явном виде формулы для вычисления координат точек сплайна. Так как , то умножая справа на , получаем:

Четыре функции в скобках называются функциями сопряжения.

Форму кривой, заданной в форме Эрмита, легко изменять если учитывать, что направление вектора касательной задает начальное направление, а модуль вектора касательной задает степень вытянутости кривой в направлении этого вектора, как показано на рис. 41.

Рис. 41. Параметрический сплайн в форме Эрмита. Вытянутость кривой вправо обеспечивается тем, что .

Рассмотрим форму Безье, которая отличается от формы Эрмита способом задания граничных условий, а именно, вместо векторов и вводятся точки (и соответствующие им радиус векторы) и , как показано на рис.42, такие что выполняются условия: и .

Рис. 42. Параметрический сплайн в форме Безье.

Переход от формы Эрмита к форме Безье осуществляется преобразованием:

, (*)

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

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

Заметим, что матрица вида

- называется матрицей Безье.

Список литературы

1. Ньюмен, Спрулл, Основы интерактивной машинной графики, М. Мир, 1976.

2. Энджел Й. Практическое введение в машинную графику, Радио и Связь, 1984.

3. А. Вэн-Дэм, Дж. Фоли, Основы интерактивной машинной графики, т.1-2, М. Мир, 1985.

4. Е.В. Жикин, А.В.Боресков, Компьютерная графика. Динамика, реалистические ихображения, М., Диалог-МИФИ, 1995, 1997.

5. Л. Аммерал, Машинная графика на языке С, в 4-х томах, изд-во Сол. Систем, 1992.

6. Компьютер обретает разум. Пер. с англ. Под ред. В.Л.Стефанюка, М. Мир, 1990.

7. Роджерс, алгоритмические основы машинной графики. М. Мир, 1989.

8. Грайс, Графические средства персональных компьютеров, М., Мир, 1980.

9. Роджерс, Адамс, Математические основы машинной графики, М. Машиностроение, 1985.

10. Гилой, Интерактивная машинная графика, М., Мир, 1981.

11. Ф. Препарата, М. Шеймос, Вычислительная геометрия: Введение, М. Мир, 1989.

12. А.Фокс, М. Пратт, Вычислительная геометрия, М., Мир, 1982.

13. А.Б.Боресков, Е.В.Шикина, Г.Е.Шикина, Компьютерная графика: первое знакомство, Под ред. Е.В.Шикина, М., Финансы и статистика, 1996.

14. А.В.Фролов, Г.В.Фролов, Графический интерфейс GDI в MS WINDOWS, Москва, Изд-во Диалог-МИФИ, 1994.

15. Майкл Ласло, Вычислительная геометрия и компьютерная графика на С++, Москва, Бином, 1997.

16. Ю.Тихомиров, Программирование трехмерной графики, С.-Пб.: БХВ‑Санкт-Петербург,1999.

17. А.Хонич, Как самому создать трехмерную игру. М.:МИКРОАРТ, 1996.

18. М.Маров, 3D Studio MAX 2.5: справочник – СПб: «Питер», 1999. – 672 с.

19. А.Ла Мот, Д.Ратклифф и др. Секреты программирования игр/ Перев с англ. – СПб: Питер, 1995. – 720 с.

20. Н. Томпсон, Секреты программирования трехмерной графики для Windows 95. Перев с англ. – СПб: Питер, 1997. – 352 с.

* В этом определении при замене, скажем, оси Oz на ось Ox остальные оси заменяются по правилу циклической перестановки, то есть Oy заменится на Oz, а Ox заменится на Oy. Всего циклических перестановок может быть три: (x,y,z)®(y,z,x)®(z,x,y).

* Более строгое определение однородных координат дается в разделе линейной алгебры «Проективные пространства».

Это функция, которая:

Проходит через все заданные точки
,
;

На каждом отрезке между соседними точками является кубической параболой;

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

интерполяция
локальная			глобальная

линейная	параболическая	кубическая парабола	полином степени (N -1)	кубический сплайн
Рис. 1.5.

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

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

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

Если имеем непрерывную или дискретную функцию, то обычно используют 5 видов преобразований функций:

Непрерывная в дискретную (дискретизация),

Дискретная в непрерывную (интерполяция),

Дискретная в непрерывную (аппроксимация),

Непрерывная в непрерывную (интерполяция),

Дискретная в дискретную (сглаживание).

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

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

Кубический сплайн - это функция, которая:

Проходит через все заданные точек
,
;

На каждом отрезке между соседними точками является кубическим полиномом;

Непрерывна вместе со своими первой и второй производными во всех точках.

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

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

(2.1)

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

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

(2.2)

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

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

Постановка задачи: даны точек , . Определить все коэффициенты сплайна , , , т.е. всего
коэффициентов,
, т.к. отрезок.

Рассмотрим два любых соседних отрезка
и
с номерами
и . Точка для них является общей, см. рис. 2.1.

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

(2.3)

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

Такие тройки уравнений можно записать для всех внутренних узлов ,
, что даёт
уравнений.

В результате получаем

уравнений. Эти уравнения содержат

неизвестных, т.к. для каждого отрезка между узлами имеем 3 неизвестных. Очевидно, что для однозначного определения коэффициентов нужны ещё два уравнения.

Эти дополнительные два уравнения могут быть произвольными, но обычно полагают, что функция
вблизи её концов является линейной. Тогда, имеем из последнего и первого уравнений (2.4) и уравнения (2.5):

Часто систему уравнений (2.8) записывают для вторых производных в узлах, обозначая их
. Тогда она принимает вид (Бахвалов, Численные методы, М., 2002):

(2.9)

, причем

и формально введено

В промышленном производстве, например, судо-, автомобиле- и авиастроении, окончательная форма в реальном или близком к нему масштабе определяется в процессе доводки.

Автоматизация этого процесса представляла значительный интерес для машинной графики. Форма математического сплайна повторяет контур физического сплайна (рис. 5-4), т.е. гибкой деревянной или пластмассовой линейки, проходящей через определенные точки. Для изменения формы сплайна используются свинцовые грузики. Меняя их количество и расположение, получившуюся кривую стараются сделать более гладкой, красивой и «приятной для глаза».

Если рассматривать физический сплайн как тонкую гибкую рейку, его форма (отклонение ) определяется уравнением Эйлера (5-2) для момента изгиба вдоль рейки:

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

Для малых отклонений радиус приближенно равен

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

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

и после двойного интегрирования

Таким образом, форма сплайна задается кубическим полиномом.

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

Уравнение одного параметрического сегмента сплайна таково:

, , (5-1)

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

Рис. 5-5 Один сегмент кубического сплайна.

Каждая составляющая имеет вид, похожий на , т.е.

, ,

, .

Постоянные коэффициенты вычисляются исходя из четырех граничных условий для сегмента сплайна. Запишем уравнение (5-1) в виде

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

, . (5-3)

Запишем результат

, . (5-4)

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

Получим четыре уравнения для неизвестных :

, (5-6b)

, (5-6c)

. (5-6d)

Решения для и имеют вид:

(5-7a)

. (5-7b)

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

Подставив уравнения (5-6) и (5-7) в (5-1), получим уравнение для одного сегмента кубического сплайна:

. (5-8)

Это уравнение для одного сегмента. Чтобы получить кривую целиком, нужно соединить множество сегментов. На рис. 5-6 показаны два соседних сегмента. Если известны векторы , , , касательные векторы , , и значения параметров , , то форма каждого сегмента определяется из уравнения (5-8). Однако маловероятно, что известен касательный вектор в точке соединения. К счастью, его можно вывести из условия непрерывности.

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

, . (5-9)

Рис. 5-6 Два кусочно кубических сегмента сплайна.

Для первого куска сплайна параметр изменяется в пределах . Подставим в уравнение (5-9):

Для второго участка сплайна параметр изменяется в диапазоне . Подставим в уравнение (5-9) значение в начале второго участка

Приравнивая полученные результаты и пользуясь уравнениями (5-6a,b) и (5-7а), получим

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

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

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

Рис. 5-7 Обозначения множества кусочно кубических сегментов сплайна.

Обобщенное уравнение для двух любых соседних сегментов сплайна и в обозначениях рис. 5-7 имеет вид:

(5-11)

для первого сегмента и

(5-12)

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

Приравнивание вторых производных в точках стыковки для любых соседних сегментов, , дает общий результат, эквивалентный уравнению (5-10),

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

Рекурсивное использование уравнения (5-13) для всех сегментов сплайна порождает уравнений касательных векторов , . В матричной форме:

(5-14)

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

(5-15)

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

. (5-16)

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

Так как и - это векторные величины, то и тоже векторные; если и имеют , составляющие, значит, и также имеет эти составляющие.

В матричной форме уравнение любого сегмента сплайна таково:

. (5-17)

Пусть требуется задать кубический сплайн, проходящий через точек , с касательными векторами на концах и . Из уравнения (5-16) находим внутренние касательные векторы , . Затем из уравнения (5-17) с известными координатами концов каждого сегмента и касательными векторами определяются , , для каждого сегмента. Окончательное обобщение уравнения (5-1)

, , , (5-18)

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

В матричном виде уравнение (5-18) выглядит следующим образом:

, . (5-19)

Подставляя уравнение (5-17) и перегруппируя члены, получим

, , , (5-20)

, (5-21a)

, (5-21b)

, (5-21с)

, (5-21d)

называются весовыми функциями.

Рис. 5-8 Весовые функции кубического сплайна для

Пользуясь этими определениями, запишем уравнение (5-20) в матричном виде

где - матрица весовой функции

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

Из уравнения (5-21) видно, что каждая весовая функция имеет третий порядок. Любая точка на сегменте кубического сплайна это взвешенная сумма конечных точек и касательных векторов. Коэффициенты выступают в роли весовых функций. На рис. 5-8 изображены для . Из рисунка видно, что и , т.е. кривая проходит через вектор-точку . Аналогично и , т.е. кривая также проходит через вектор-точку . Далее отметим симметрию и , и и . Фактически . Наконец, обратим внимание на относительный порядок , , и . Значительная разница величин говорит о том, что в общем случае положение конечных точек имеет большее влияние, чем касательные векторы.

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

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

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

Рассмотрим пример.

Пример 5-2 Кубический сплайн Пусть даны четыре вектор-точки на плоскости: , , , (см. рис. 5-9). Найти кусочный кубический сплайн, проходящий через них, используя хордовую аппроксимацию . Касательные векторы в концах: и . Найти промежуточные точки при для каждого сегмента. Сначала найдем Внутренние касательные векторы и вычисляются из уравнения (5-15): . Рис. 5-9 Кусочный кубический сплайн. (а) вычислены с помощью хордовой аппроксимации; (b) нормализованы к 1. Сделав подстановку, получим . С помощью инверсии и умножения вычисляются касательные векторы .





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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное автономное образовательное учреждение

высшего профессионального образования

«Уральский федеральный университет имени первого Президента России Б.Н.Ельцина»

Институт радиоэлектроники и информационных технологий - РТФ

Кафедра Автоматика и информационные технологии

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

МЕТОДИЧЕСКИЕ УКАЗАНИЯ К лабороторной работе ПО ДИСЦИПЛИНЕ «Численные методы»

Составитель И.А.Селиванова, ст.преподаватель.

ИНТЕРПОЛЯЦИЯ СПЛАЙНАМИ: Методические указания к практическим занятиям по дисциплине «Численные методы»

Указания предназначены для студентов всех форм обучения направления 230100 – «Информатика и вычислительная техника».

Ó ФГАОУ ВПО «УрФУ имени первого Президента России Б.Н.Ельцина», 2011

1. ИНТЕРПОЛЯЦИЯ СПЛАЙНАМИ. 4

1.1. Кубические сплайны. 4

1.2. Специальная форма записи сплайна. 5

1.3. Квадратичные сплайны. 13

1.4. Задание на практику. 18

1.5. Варианты заданий. 19

Список литературы 21

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

В случаях, когда промежуток [a ,b ], на котором требуется заменить функцию f (x ) велик, можно применить интерполяцию сплайнами.

1.1. Кубические сплайны.

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

Пусть на отрезке [a , b ] вещественной оси x задана сетка , в узлах которой определены значения
функцииf (x ). Требуется построить на отрезке [a , b ] непрерывную функцию-сплайн S (x ), которая удовлетворяет следующим условиям:

Для построения искомого сплайна требуется найти коэффициенты
многочленов
,i =1,… n , т.е. 4 n неизвестных коэффициента, которые удовлетворяют 4 n -2 уравнениям (1), (2), (3). Чтобы система уравнений имела решение, добавляют еще два дополнительных (краевых) условия. Используется три типа краевых условий:

Условия (1), (2), (3) и одно из условий (4), (5), (6) образуют СЛАУ порядка 4 n . Решение системы можно провести с помощью метода Гаусса. Однако, выбрав специальную форму записи кубического многочлена, можно существенно снизить порядок решаемой системы уравнений.

1.2. Специальная форма записи сплайна.

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

Здесь
- длина отрезка
,

,
- вспомогательные переменные,

x – промежуточная точка на отрезке
.

Когда x пробегает все значения на интервале
, переменнаяизменяется от 0 до 1, а
изменяется от 1 до 0.

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

Переменные и
определяются применительно к конкретному отрезку интерполяции.

Найдем значение сплайна
на концах отрезка
. Точка
является начальной для отрезка
, поэтому=0,
=1 и в соответствии с (3.8):
.

На конце отрезка
=1,
=0 и
.

Для интервала
точка
является конечной, поэтому=1,
=0 и из формулы (9) получаем:
. Таким образом, выполняется условие непрерывности функцииS (x ) в узлах стыковки кубических многочленов независимо от выбора чисел  i .

Для определения коэффициентов  i , i =0,… n продифференцируем (8) дважды как сложную функцию от x . Тогда

Определим вторые производные сплайна
и
:

Для многочлена
точкаявляется началом отрезка интерполяции и=0,
=1, поэтому

Из (15) и (16) следует, что на отрезке [a ,b ]сплайн-функция, «склеенная» из кусков многочленов 3-го порядка, имеет непрерывную производную 2-го порядка.

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

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

и система уравнений (17) будет иметь вид:

Пример .

Исходные данные:

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