Слово сплайн (английское слово "spline") означает гибкую линейку, используемую для проведения гладких кривых через заданные точки на плоскости. Форма этого универсального лекала на каждом отрезке описывается кубической параболой. Сплайны широко используются в инженерных приложениях, в частности, в компьютерной графике. Итак, на каждом i –м отрезке [x i –1 , x i ], i= 1, 2,…, N, решение будем искать в виде полинома третьей степени:

S i (x )=a i +b i (x–x i )+c i (x –x i ) 2 /2+d i (x–x i ) 3 /6

Неизвестные коэффициенты a i , b i , c i , d i , i= 1, 2,..., N, находим из:

Условий интерполяции: S i (x i )=f i , i= 1, 2,..., N ; S 1 (x 0)=f 0 ,

Непрерывности функции S i (x i– 1 )=S i– 1 (x i –1), i= 2, 3,..., N,

Непрерывности первой и второй производной:

S / i (x i– 1)=S / i– 1 (x i –1), S // i (x i –1)=S // i –1 (x i –1), i= 2, 3,..., N .

Учитывая, что , для определения 4N неизвестных получаем систему 4N –2 уравнений:

a i =f i , i= 1, 2,..., N,

b i h i – c i h i 2 /2 + d i h i 3 /6=f i – f i –1 , i= 1, 2,..., N,

b i – b i–1 = c i h i – d i h i 2 /2, i= 2, 3,..., N,

d i h i = c i – c i– 1 , i= 2, 3,..., N.

где h i =x i – x i– 1. Недостающие два уравнения выводятся из дополнительных условий: S // (a )=S // (b )=0. Можно показать, что при этом . Из системы можно исключить неизвестные b i , d i , получив систему N+ 1 линейных уравнений (СЛАУ) для определения коэффициентов c i :

c 0 = 0, c N = 0,

h i c i –1 + 2(h i +h i +1)c i +h i +1 c i +1 = 6 , i= 1, 2,…, N –1. (1)

После этого вычисляются коэффициенты b i , d i:

, i= 1, 2,..., N. (2)

В случае постоянной сетки h i =h этасистема уравнений упрощается.

Данная CЛАУ имеет трехдиагональную матрицу и решается методом прогонки.

Коэффициенты определяются из формул:

Для вычисления значения S (x ) в произвольной точке отрезка z ∈[a, b ] необходимо решить систему уравнений на коэффициенты c i , i= 1,2,…, N –1, затем найти все коэффициенты b i , d i . Далее, необходимо определить, на какой интервал [x i 0, x i 0–1 ] попадает эта точка, и, зная номер i 0 , вычислить значение сплайна и его производных в точке z

S (z )=a i 0 +b i 0 (z–x i 0)+c i 0 (z–x i 0) 2 /2+d i 0 (z–x i 0) 3 /6

S / (z )=b i 0 +c i 0 (z–x i 0)+d i 0 (z–x i 0) 2 /2, S // (z )=c i 0 +d i 0 (z–x i 0).

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

В нашем случае: h i =1/4, .

Выпишем систему уравнений для определения :

Решая эту систему линейных уравнений, получим: .

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

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

Следовательно,

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

В случае глобальной интерполяции отыскивается единый полином на всем интервале [a, b ], т.е. строится полином, который используется для интерполяции функции f(x) на всем интервале изменения аргумента x. Будем искать интерполирующую функцию в виде полинома (многочлена) m –ой степени P m (x )=a 0 +a 1 x+a 2 x 2 +a 3 x 3 +…+a m x m . Какова должна быть степень многочлена, чтобы удовлетворить всем условиям интерполяции? Допустим, что заданы две точки: (x 0 , f 0) и (x 1 , f 1), т.е. N=1. Через эти точки можно провести единственную прямую, т.е. интерполирующей функцией будет полином первой степени P 1 (x )=a 0 +a 1 x. Через три точки (N=2) можно провести параболу P 2 (x )=a 0 +a 1 x+a 2 x 2 и т.д. Рассуждая таким способом, можно предположить, что искомый полином должен иметь степень N .

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

Данная система является линейной относительно искомых коэффициентов a 0 , a 1 , a 2 , …, a N. Известно, что СЛАУ имеет решение, если ее определитель отличен от нуля. Определитель данной системы

носит имя определителя Вандермонда . Из курса математического анализа известно, что он отличен от нуля, если x k ≠ x m (т.е. все узлы интерполяции различные). Таким образом, доказано, что система имеет решение.

Мы показали, что для нахождения коэффициентов
a 0 , a 1 , a 2 , …, a N надо решить СЛАУ, что является сложной задачей. Но есть другой способ построения полинома N –й степени, который не требует решения такой системы.

Полином Лагранжа

Решение ищем в виде , где l i (z ) – базисные полиномы N –й степени, для которых выполняется условие: . Убедимся в том, что если такие полиномы построены, то L N (x) будет удовлетворять условиям интерполяции:

Каким образом построить базисные полиномы ? Определим

, i= 0, 1,..., N.

Легко понять, что

Функция l i (z ) является полиномом N –й степени от z и для нее выполняются условия "базисности":

0, i≠k;, т.е. k=1,…,i-1 или k=i+1,…,N.

Таким образом, нам удалось решить задачу о построении интерполирующего полинома N– й степени, и для этого не нужно решать СЛАУ. Полином Лагранжа можно записать в виде компактной формулы: . Погрешность этой формулы можно оценить, если исходная функция g (x ) имеет производные до N+ 1 порядка:

Из этой формулы следует, что погрешность метода зависит от свойств функции g (x ), а также от расположения узлов интерполяции и точки z. Как показывают расчетные эксперименты, полином Лагранжа имеет малую погрешность при небольших значениях N <20 . При бόльших N погрешность начинает расти, что свидетельствует о том, что метод Лагранжа не сходится (т.е. его погрешность не убывает с ростом N ).

Рассмотрим частные случаи. Пусть N=1, т.е. заданы значения функции только в двух точках. Тогда базовые полиномы имеют вид:

, т.е. получаем формулы кусочно–линейной интерполяции.

Пусть N=2. Тогда:

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

Пример: Заданы значений некоторой функции:

x				3.5
f	-1	0.2	0.5	0.8

Требуется найти значение функции при z= 1, используя интерполяционный полином Лгранжа. Для этого случая N =3, т.е. полином Лагранжа имеет третий порядок. Вычислим значения базисных полиномов при z =1:

Подбор эмпирических формул

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

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

Для практики важен случай аппроксимации функции многочленами, т.е. .

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

Метод наименьших квадратов

Пусть для исходных данных x i , f i , i= 1,…,N (нумерацию лучше начинать с единицы), выбран вид эмпирической зависимости: с неизвестными коэффициентами . Запишем сумму квадратов отклонений между вычисленными по эмпирической формуле и заданными опытными данными:

Параметры будем находить из условия минимума функции . В этом состоит метод наименьших квадратов (МНК).

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

(1)

Рассмотрим применение МНК для частного случая, широко используемого на практике. В качестве эмпирической функции рассмотрим полином

Формула (1) для определения суммы квадратов отклонений примет вид:

Вычислим производные:

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

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

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

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

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

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

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

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

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

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

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

Указания предназначены для студентов всех форм обучения направления 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) будет иметь вид:

Пример .

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

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

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

Для разных краевых условий (4), (5), (6) найдем коэффициенты кубических сплайнов.

1. Рассмотрим первые краевые условия.

В нашем случае n =3,
,
,
. Чтобы найти
используем систему уравнений (3.18):

Вычислим и, используя формулы (7) и (11):

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

.

Решение системы:

С учетом первых краевых условий коэффициенты сплайна:

Рассмотрим определение коэффициентов сплайна с учетом краевых условий (3.5):

Найдем производную функции
:

Вычислим
и
:

Подставим в систему уравнений (21) значения и:

Используя формулу (20) определим  0 и  3:

С учетом конкретных значений:

и вектор коэффициентов:

Рассчитаем значения кубического сплайна S(x) в серединах отрезков интерполяции.

Середины отрезков:

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

3.1.

Найдем и
:

В формулу (3.9) подставляем коэффициенты

3.2.

Найдем и
:

, для краевых условий (4), (5), (6):

3.3.

Найдем и
:

В формулу (9) подставляем коэффициенты
, для краевых условий (4), (5), (6):

Составим таблицу:

	(1 кр.усл.)	(2 кр.усл.)	(3 кр.усл.)

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«Донской государственный университет»

Кафедра «Программное обеспечение вычислительной техники и автоматизированных систем» «ПОВТ и АС»

Специальность: Математическое обеспечение и администрирование информационных систем

КУРСОВАЯ РАБОТА

по дисциплине «Методы вычисления»

на тему: «Интерполяция сплайнами»

Руководитель работы:

Медведева Татьяна Александровна

Ростов-на-Дону

ЗАДАНИЕ

на курсовую работу по дисциплине «Методы вычислений»

Студент: Моисеенко Александр Группа ВБМО21

Тема: «Интерполяция сплайнами»

Срок представления работы к защите “__” _______ 201_ г.

Исходные данные для курсовой работы: конспект лекций по методам вычислений, ru.wikipedia.org , кн. Практикум по высшей математике Соболь Б.В.

Разделы основной части: 1 ОБЗОР, 2 ФОРМУЛА ИНТЕРПОЛЯЦИИ, 3 АЛГОРИТМ КУБИЧЕСКОЙ ИНТЕРПОЛЯЦИИ, 4 ПРОГРАММНОЕ КОНСТРУИРОВАНИЕ, 5 РЕЗУЛЬТАТЫ РАБОТЫ ПРОГРАММНОГО СРЕДСТВА.

Руководитель работы: /Медведева Т.А./

РЕФЕРАТ

Отчет содержит: страниц-19, графиков-3, источников-3, блок-схема -1.

Ключевые слова: ИНТЕРПОЛЯЦИЯ, СПЛАЙН, Система Mathcad, КУБИЧЕСКАЯ ИНТЕРПОЛЯЦИЯ СПЛАЙНАМИ.

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

ВВЕДЕНИЕ

1. ТЕОРЕТИЧЕСКИЙ ОБЗОР

2. ИНТЕРПОЛЯЦИЯ

2.1 Интерполяция с помощью квадратичного сплайна

2.2 Интерполяция с помощью кубического сплайна

2.3 Постановка задачи

3. АЛГОРИТМ ИНТЕРПОЛЯЦИИ С ПОМОЩЬЮ КУБИЧЕСКОГО СПЛАЙНА

4. ПРОГРАММНОЕ КОНСТРУИРОВАНИЕ

5. РЕЗУЛЬТАТ РАБОТЫ ПРОГРАММНОГО СРЕДСТВА

5.1 Описание примеров

5.2 Результат тестирования

5.3 Контрольный пример 1

5.4 Контрольный пример 2

5.5 Контрольный пример 3

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ

ВВЕДЕНИЕ

Аппроксимация функций заключается в приближенной замене заданной функции f (x ) некоторой функцией j(x ) так, чтобы отклонение функции j(x ) от f (x ) в заданной области было наименьшим. Функция j(х ) при этом называется аппроксимирующей. Типичной задачей аппроксимации функций является задача интерполяции. Необходимость интерполяции функций в основном связана с двумя причинами:

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

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

1. ТЕОРЕТИЧЕСКИЙ ОБЗОР

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

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

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

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

2. ИНТЕРПОЛЯЦИЯ

2.1 Интерполяция с помощью квадратичного сплайна

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

Коэффициенты сплайнов будем искать из следующих условий:

а) условия Лагранжа

б) непрерывность первой производной в узловых точках

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

Подстановка этих выражений приводит к следующим уравнениям

где введено обозначение

Выразим из второго уравнения коэффициенты c 1 , предварительно подставив в него значения коэффициентов a 1 из первого уравнения:

Затем, подставив это выражение в уравнение системы, получим простое рекуррентное соотношение для коэффициентов

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

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

2.2 Интерполяция с помощью кубического сплайна

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

1. На каждом сегменте [x i - 1 , x i ], i = 1, 2, ..., N функция S (x ) является полиномом третьей степени,

2. Функция S (x ), а также ее первая и вторая производные непрерывны на отрезке [a, b ],

3. S (x i ) = f (x i ), i = 0, 1, ..., N.

На каждом из отрезков [x i - 1 , x i ], i = 1, 2, ..., N будем искать функцию S (x ) = S i (x ) в виде полинома третьей степени:

S i (x ) = a i + b i (x - x i - 1) + c i (x - x i - 1) 2 + d i (x - 1) 3 ,

x i - 1 Ј x Ј x i ,

где a i , b i , c i , d i - коэффициенты, подлежащие определению на всех n элементарных отрезках. Чтобы система алгебраических уравнений имела решение, нужно, чтобы число уравнений точно равнялось числу неизвестных. Поэтому мы должны получить 4n уравнения.

Первые 2n уравнения мы получим из условия, что график функции S (x ) должен проходить через заданные точки, т. е.

S i (x i - 1) = y i - 1 , S i (x i ) = y i .

Эти условия можно записать в виде:

S i (x i - 1) = a i = y i - 1 ,

S i (x i ) = a i + b i h i + c i h + d i h = y i ,

h i = x i - x i - 1 , i = 1, 2, ..., n.

Следующие 2n - 2 уравнения вытекают из условия непрерывности первых и вторых производных в узлах интерполяции, т. е. условия гладкости кривой во всех точках.

S" i + 1 (x i ) = S" i (x i ), i = 1, ..., n - 1,

S" " i + 1 (x i ) = S" " i (x i ), i = 1, ..., n - 1,

S" i (x ) = b i + 2 c i (x - x i - 1) + 3 d i (x - x i - 1),

S" i + 1 (x ) = b i + 1 + 2 c i + 1 (x - x i ) + 3 d i + 1 (x - x i ).

Приравнивая в каждом внутреннем узле x = x i значения этих производных, вычисленные в левом и правом от узла интервалах, получаем (с учетом h i = x i - x i - 1):

b i + 1 = b i + 2 h i c i + 3h d i , i = 1, ..., n - 1,

S" " i (x ) = 2 c i + 6 d i (x - x i - 1),

S" " i + 1 (x ) = 2 c i + 1 + 6 d i + 1 (x - x i ),

если x = x i

c i + 1 = c i + 3 h i d i , i = 1, 2, ..., n - 1.

На данном этапе мы имеем 4n неизвестных и 4n - 2 уравнений. Следовательно, необходимо найти еще два уравнения.

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

S 1" " (x 0) = 0 и S n" " (x n ) = 0,

c i = 0 и 2 c n + 6 d n h n = 0.

Уравнения составляют систему линейных алгебраических уравнений для определения 4n коэффициентов: a i , b i , c i , d i (i = 1, 2, . . ., n ).

Эту систему можно привести к более удобному виду. Из условия сразу можно найти все коэффициенты a i .

i = 1, 2, ..., n - 1,

Подставляя, получим:

b i = - (c i + 1 + 2c i ) , i = 1, 2, ..., n - 1,

b n = - (h n c n )

Исключаем из уравнения коэффициенты b i и d i . Окончательно получим следующую систему уравнений только для коэффициентов с i :

c 1 = 0 и c n + 1 = 0:

h i - 1 c i - 1 + 2 (h i - 1 + h i ) c i + h i c i + 1 = 3 ,

i = 2, 3, ..., n.

По найденным коэффициентам с i легко вычислить d i ,b i .

2.3 Постановка задачи

На отрезке [a, b ] заданы n + 1 точки x i = х 0 , х 1 , . . ., х n , которые называются узлами интерполяции, и значения некоторой функции f (x ) в этих точках

f (x 0) = y 0 , f (x 1) = y 1 , . . ., f (x n ) = y n .

С помощью кубических сплайнов построить интерполяционную функцию f (x ).

3. АЛГОРИТМ ИНТЕРПОЛЯЦИИ С ПОМОЩЬЮ КУБИЧЕСКОГО СПЛАЙНА

Познакомимся с алгоритмом работы программы.

1. Вычисляем значения и

2. На основе этих значений считаем коэффициенты прогонки и о.

3. На основе полученных данных высчитываем коэффициенты

4. После чего вычисляем значение функции с помощью сплайна.

4. ПРОГРАММНОЕ КОНСТРУИРОВАНИЕ

5. РЕЗУЛЬТАТЫ РАБОТЫ ПРОГРАММНОГО СРЕДСТВА

5.1 Описание тестовых примеров

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

5.2 Результаты тестирования

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

5.3 Контрольный пример 1

Рисунок 1.1 -результат работы программы

Контрольный пример 2

Рисунок 1.2 -результат работы программы

Контрольный пример 3

Рисунок 1.3 -результат работы программы

ЗАКЛЮЧЕНИЕ

сплайн интерполяция функция вычислительный

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

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

СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ

1. Б.В.Соболь, Б.Ч.Месхи, И.М.Пешхоев. Практикум по вычислительной математике. - Ростов-на-Дону: Феникс, 2008;

2. Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков. Численные методы. Изд-во "Лаборатория базовых знаний". 2003

3. www.wikipedia.ru/сплайн

Подобные документы

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

лабораторная работа , добавлен 06.02.2004


В вычислительной математике существенную роль играет интерполяция функций. Формула Лагранжа. Интерполирование по схеме Эйткена. Интерполяционные формулы Ньютона для равноотстоящих узлов. Формула Ньютона с разделенными разностями. Интерполяция сплайнами.

контрольная работа , добавлен 05.01.2011


Построить интерполяционный многочлен Ньютона. Начертить график и отметить на нем узлы интерполяции. Построить интерполяционный многочлен Лагранжа. Выполнить интерполяцию сплайнами третьей степени.

лабораторная работа , добавлен 06.02.2004


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

курсовая работа , добавлен 10.04.2011


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

курсовая работа , добавлен 14.03.2014


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

курсовая работа , добавлен 09.08.2015


Проблеми глобальної та локальної інтерполяції за Лагранжем і Ньютоном; коливна поведінка інтерполяційного многочлена; функції Рунге. Сплайн – група пов"язаних кубічних многочленів з неперервною першою і другою похідною, переваги сплайн-інтерполяції.

презентация , добавлен 06.02.2014


Методы численного дифференцирования. Вычисление производной, простейшими формулами. Численное дифференцирование, основанное на интерполяции алгебраическими многочленами. Аппроксимация многочленом Лагранжа. Дифференцирование, с использованием интерполяции.

курсовая работа , добавлен 15.02.2016


Описание методов решения системы линейного алгебраического уравнения: обратной матрицы, Якоби, Гаусса-Зейделя. Постановка и решение задачи интерполяции. Подбор полиномиальной зависимости методом наименьших квадратов. Особенности метода релаксации.

лабораторная работа , добавлен 06.12.2011


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

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

Концепция интерполяции

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

В связи с интерполяцией рассматриваются три основные проблемы.

1) выбор интерполяционной функции L (x );

2) оценка погрешности интерполяции R (x );

3) размещение узлов интерполяции для обеспечения наивысшей возможной точности восстановления функции (x 1 , x 2 ,…,x n ).

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

Рис. 3.2 Иллюстрация интерполяции

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

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

Линейная интерполяция

Простейшим и часто используемым видом локальной интерполяции является линейная интерполяция. Она состоит в том, что заданные точки М (x i , y i ) (i = 0, 1, …, n ) соединяются прямолинейными отрезками, и функция f (x ) приближается к ломаной с вершинами в данных точках (рис. 3.3).

Рис. 3.3 Линейная интерполяция

Уравнения каждого отрезка ломаной линии в общем случае разные. Поскольку имеется n интервалов (x i , x i + 1), то для каждого из них в качестве уравнения

интерполяционного полинома используется уравнение прямой, проходящей через две точки. В частности, для i — го интервала можно написать уравнение прямой, проходящей через точки (x i , y i ) и (x i + 1 , y i + 1), в виде:

(3.2)

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

На рисунке 3.4 представлен пример использования линейной интерполяции в программе MathCAD. Для линейной интерполяции используется функция linterp (x ,y ,z ). Здесь x , y – исходные данные, z – точка, в которой находится значение функции.

Рис. 3.4. Линейная интерполяция

Квадратичная интерполяция

В случае квадратичной интерполяции в качестве интерполяционной функции на отрезке (x i — 1 ,x i + 1) принимается квадратный трехчлен. Уравнения квадратного трехчлена имеет вид

y = a i x 2 + b i x + c i , x i — 1 x x i + 1 , (3.3)

Интерполяция для любой точки x [x 0 , x n ] проводится по трем ближайшим точкам.

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

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

Рассмотренные выше методы локальной интерполяции, по существу, является простейшим сплайном первой степени (для линейной интерполяции) и второй степени (для квадратичной интерполяции).

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

В общем случае для функции y = f (x ) требуется найти приближение y= j (x ) таким образом, чтобы f (x i ) = j (x i ) в точках x = x i , a в остальных точках отрезка [a, b ] значения

функций f (x ) и j (x ) были близкими между собой. При малом числе экспериментальных точек (например, 6-8) для решения задачи интерполяции можно использовать один из методов построения интерполяционных полиномов. Однако при большом числе узлов интерполяционные полиномы становятся практически непригодными. Это связано с тем, что степень интерполяционного полинома лишь на единицу меньше числа экспериментальных значений функций. Можно, конечно, отрезок, на котором определена функция, разбить на участки, содержащие малое число экспериментальных точек, и для каждого из них построить интерполяционные полиномы. Однако в этом случае аппроксимирующая функция будет иметь точки, где производная не является непрерывной, т. е. график функции будет содержать точки “излома”.

Кубические сплайны лишены этого недостатка. Исследования теории балок показали, что гибкая тонкая балка между двумя узлами достаточно хорошо описывается кубическим полиномом, и поскольку она не разрушается, то аппроксимирующая функция должна быть, по меньшей мере, непрерывно дифференцируемой. Это означает, что функции j (x ), j’ (x ), j» (x ) должны быть непрерывными на отрезке [a, b ].

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

1. на каждом сегменте [x i — 1 , x i ], i = 1, 2, ..., n функция y (x ) является полиномом третьей степени,

Функция y (x ), а также ее первая и вторая производные непрерывны на отрезке [a,b ],

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

Для всего интервала будет соответственно п кубических полиномов, отличающихся коэффициентами а i , b i , c i , d i . Чаще всего узлы при сплайновой интерполяции располагают равномерно, т.е. х i +1 -х i = const = h (хотя это и необязательно).

Необходимо найти четыре коэффициента при условии прохождения каждого полинома через две точки (x i , y i ) и (x i +1 , y i +1 ) , следствием чего являются следующие очевидные уравнения:

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

Так как и , то

(y ’ (x i +1 ) в конце i -го участка равна у’ (х i +1 ) в начале (i +1 )-го),

(у» (х i +1 ) в конце i -го участка равна у» (х i +1 ) в начале (i +1)-го).

Получилась система линейных уравнений (для всех участков), содержащая 4n — 2 уравнения с 4n неизвестными (неизвестные a 1 , a 2 ,…, a n , b 1 ,…, d n - коэффициенты сплайнов). Для решения системы добавляют два граничных условия одного из следующих видов (чаще применяют 1):

Совместное решение 4n уравнений позволяет найти все 4n коэффициента.

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

Решим задачу об интерполяции с помощью программы MathCAD. Для этого воспользуемся встроенной функцией interp(VS,x,y,z) . Переменные x и y задают координаты узловых точек, z является аргументом функции, VS определяет тип

граничных условий на концах интервала.

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

Здесь cspline ( VX , VY ) возвращает вектор VS вторых производных при приближении в опорных точках к кубическому полиному;

pspline (VX , VY ) возвращает вектор VS вторых производных при приближении к опорным точкам к параболической кривой;

lspline (VX , VY ) возвращает вектор VS вторых производных при приближении к опорным точкам прямой;

interp (VS , VX , VY , x ) возвращает значение y (x ) для заданных векторов VS , VX , VY и заданного значения x .

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

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

Рис. 3.5 Кубическая сплайн интерполяция

Если функция задана дискретно, то для интерполяции задаются матрицы данных.

При глобальной интерполяции наиболее часто используется интерполяция полиномом n -ой степени или интерполяция Лагранжа.

Классический подход основывается на требовании строгого совпадения значений f (х ) и j (х ) в точках х i (i = 0, 1, 2, … n ).

Будем искать интерполяционную функцию j (х ) в виде полинома степени n .

Этот полином имеет n + 1 коэффициент. Естественно предположить, что n + 1 условий

j (x 0) = y 0 , j (x 1) = y 1 , . . ., j (x n ) = y n (3.4)

наложенные на полином

позволяют однозначно определить его коэффициенты. Действительно, требуя для j (х ) выполнение условий (3.4), получаем систему n + 1 уравнений с n + 1 неизвестными:

(3.6)

Решая эту систему относительно неизвестных a 0 , a 1 , …, a n мы получим аналитическое выражение полинома (3.5). Система (3.6) всегда имеет единственное решение, т.к. её определитель

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

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

Интерполяционная формула Лагранжа

Пусть известны значения некоторой функции f (х) в п+ 1 различных произвольных точках y i = f (x i ) , i = 0,…, п. Для интерполирования (восстановления) функции в какой-либо точке х, принадлежащей отрезку [х 0 ,х п ], необходимо построить интерполяционный полином n-го порядка, который в методе Лагранжа представляется следующим образом:

Причем нетрудно заметить, что Q j (x i ) = 0, если i ¹ j , и Q j (x i ) =1, если i = j . Если раскрыть произведение всех скобок в числителе (в знаменателе все скобки - числа), то получим полином n-го порядка от х, так как в числителе содержится n сомножителей первого порядка. Следовательно, интерполяционный полином Лагранжа не что иное, как обычный полином n-го порядка, несмотря на специфическую форму записи.

Оценить погрешность интерполяции в точке х из [х 0 ,х n ] (т.е. решить вторую

проблему интерполяции) можно по формуле

В формуле - максимальное значение (n+1)-й производной исходной функции f (х) на отрезке [х 0 ,х n ]. Следовательно, для того чтобы оценить погрешность интерполяции, необходима некоторая дополнительная информация об исходной функции (это должно быть понятно, так как через заданные исходные точки может проходить бесчисленное количество различных функций, для которых и погрешность будет разной). Такой информацией является производная n+1 порядка, которую не так просто найти. Ниже будет показано, как выйти из такого положения. Отметим также, что применение формулы погрешности возможно, только если функция дифференцируема n +1 раз.

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

if (cond , х, у )

Возвращает значение х, если cond отличен от 0 (истина). Возвращает значение у, если cond равен 0 (ложь) (рисунок 3.6).

Кривые и поверхности, встречающиеся в практических задачах, часто имеют довольно сложную форму, не допускающую универсального аналитического задания в целом при помощи элементарных функций. Поэтому их собирают из сравнительно простых гладких фрагментов - отрезков (кривых) или вырезков (поверхностей), каждый из которых может быть вполне удовлетворительно описан при помощи элементарных функций одной или двух переменных. При этом вполне естественно потребовать, чтобы гладкие функции, которые используются для построения частичных кривых или поверхностей, имели схожую природу, например, были бы многочленами одинаковой степени. А чтобы получающаяся в результате кривая или поверхность оказалась достаточно гладкой, необходимо быть особенно внимательным в местах стыковки соответствующих фрагментов. Степень многочленов выбирается из простых геометрических соображений и, как правило, невелика. Для гладкого изменения касательной вдоль всей составной кривой достаточно описывать стыкуемые кривые при помощи много-членов третьей степени, кубических многочленов. Коэффициенты таких многочленов всегда можно подобратьтак, чтобы кривизна соответствующей составной кривой была непрерывной. Кубические сплайны, возникающие при решении одномерных задач, можно приспособить к посгрое нию фрагментов составных поверхностей. И здесь вполне естественно появляются бикубические сплайны, описываемые при помощи многочленов третьей степени по каждой из двух переменных. Работа с такими сплайнами требует уже значительно большего объема вычислений. Но правильно организованный процесс позволитучесть непрерывно нарастающие возможности вычислительной техники в максимальной степени. Сплайн-функции Пусть на отрезке , то есть Замечание. Индекс (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-й шаг. На произвольно взятом отрезке }