СКАЧАТЬ:  ptimizayiya-laba-2.zip [101,15 Kb] (cкачиваний: 137)

Лабораторная работа №2

по дисциплине: «Оптимизация и оптимальные управления»

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

Вариант №18

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

Краткие сведения из теории

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

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

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

Уравнения каждого отрезка ломаной в общем случае разные. Поскольку имеется n интервалов (x_i-1,x_i), то для каждого из них в качестве уравнения интерполяционного многочлена используется уравнение прямой, проходящей через две точки. В частности, для i-го интервала можно написать уравнение прямой, проходящей через точки (x_i-1, y_i-1) и (х_i, у_i), в виде:

Отсюда

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

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

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

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

Функция S_m(x) называется интерполяционным сплайном порядка т для функции f(x), заданной таблицей 1.

Таблица 1

Если:

1) на каждом отрезке [x_i; x_i-1] (i=0,1,…,n-1) S(x) является многочленом порядка т;

2) S(x) и ее производные до (т-1)-го порядка включительно непрерывны на [x₀, x_n];

3) S(x_i)=y_i (i=0,1,…,n) – непосредственное условие интерполяции.

Можно доказать, что эти условия достаточны для существования сплайна порядка т (т≥2), но не гарантируют его единственности.

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

Согласно определению кубический сплайн S(x) можно представить в виде:

где каждый из Р_i(х) – многочлен третьей степени:

Коэффициенты a_i можно определить:

Условие непрерывности S(x) в каждом узле приводит к равенствам  (i=1,…, п-1). В развернутом виде с учетом (4) эти равенства примут вид:

Введем обозначение шага . Понижая в равенствах (6) индекс на единицу и учитывая (5), получим:

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

Осталось использовать непрерывность второй производной сплайн - функции, т.е. условие . Оно порождает равенства:

Совокупность равенств (7) – (9) образует систему 3п-2 линейных алгебраических уравнений относительно 3п неизвестных {b_i}, {c_i}, {d_i} (i=1,2,…n). Для однозначной разрешимости ее следует доопределить.

Наиболее распространенный способ доопределения – потребовать «гладкости» второй производной сплайна на концах отрезка , что в принятых обозначениях сводится к равенствам , или с учетом (6):

Отметим, что первое из уравнений (10) совпадает формально с (9) при i=0, если ввести коэффициент с₀ (которого нет на самом деле в наборе {c_i}) и положить его равным нулю.

На практике удобно не решать непосредственно систему (7) - (10), а предварительно исключить из нее все неизвестные каких-либо двух групп. Начнем с исключением совокупности переменных {b_i}. Для этого выразим b_i из (7):

Перепишем (11), понизив индекс на единицу:

Вычтем (11) из (12) и подставим полученную разность  в (8). После простых преобразований получим:

Теперь исключим из (13) величины {d_i}. Для этого выразим {d_i} из (9):

Подставим это выражение в (11), понизив индекс там, где это необходимо. Получим:

Система (15) содержит лишь неизвестные {c_i} и является системой линейных алгебраических уравнений с трехдиагональной матрицей, которую удобно решать методом прогонки. При этом необходимое для «обратной прогонки» значение величины с_n уже известно.

Найдя неизвестные {c_i}, по формулам (14) и первого из уравнений (10) определим неизвестные {d_i}, а затем с помощью (11) неизвестные {b_i}. На этом построение кубического сплайна завершится.

Задание

Для функции, заданной таблицей узловых значений

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

Решение:

Кубический сплайн S(x) можно представить, на основании формулы (3), в виде:

Многочлены Р_i(х) выразим по формуле (4):

Нужно найти коэффициенты a, b, c, d полиномов третьей степени.

Для нахождения a_i  воспользуемся формулой (5), тогда:

Введем обозначение шага , тогда:

Теперь мы можем найти коэффициенты с_i  на основании формулы (15):

;

Известно, что с₀=с_т=0, т.е. с₀=с₃=0, тогда система упростится:

;       

         Можно определить коэффициенты d_i , исходя из формулы (14):

                Найдем величины b_i по формуле (11):

Коэффициенты найдены, можно строить сплайн:

                Возьмем точку х=2 из второго интервала [2;5] и определим значение функции в этой точке.

Проверим полученное начение в программе MathCad.

Вывод: как видно, из расчетов и графика, значения сплайна в точке   х=-4 равны. Это говорит о правильности полученных результатов, т.е. о правильности построения кубического сплайна, как при помощи специальных формул, так и при помощи программы MathCad.

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