СКАЧАТЬ:  optimizm-2.zip [600,31 Kb] (cкачиваний: 97)

Министерство образования и науки РТ

Альметьевский государственный нефтяной институт

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

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

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

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

                                                    Выполнил:   

                                                  Проверил: ст.преподаватель

Альметьевск

ЦЕЛЬ И СОДЕРЖАНИЕ РАБОТЫ:

Объектом изучения в данной лабораторной работе является нахождение интерполированное значение.

Цель работы заключается в следующем:

· закрепление полученных в теоретической части курса знаний о постановке, формализации и методах решения оптимизационных задач для различных интерполяции;

· получение практических навыков решения реальных оптимизационных задач на ЭВМ;

ОСНОВНЫЕ СВЕДЕНИЯ ИЗ ТЕОРИИ

ЛИНЕЙНАЯ ИНТЕРПОЛЯЦИЯ

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

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

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

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

                                                      (1)

Следовательно,  при  использовании  линейной  интерполяции  сначала

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

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

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

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

Пусть интерполируемая функция f(x) задана своими значениями у_i в уз­лах x_i , (i = 0, 1 …, n). Обозначим длину частичного отрезка [x_i-1, x_i] h_i =х_i- х_i-1 , (i = 0, 1 …, n). Будем искать кубический сплайн на каждом из частичных отрезков [x_i-1, x_i] в виде:

S(x)=a_i+b_i(x-x_i-1)+c_i(x-x_i-1)²+ d_i(x-x_i-1)³                                            (2) 

где a_i, b_i, c_i, d_i — четверка неизвестных коэффициентов. Можно доказать, что задача нахождения кубического сплайна имеет единственное решение.

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

S(x_i-1)=y_i-1=a_i ,                                           (3)

S(x_i)= у_i = a_i + b_ih_i + c_i h_i² + d_i h_i³.                      (4)

Число этих уравнений (2п) в два раза меньше числа неизвестных коэффициентов. Для того чтобы получить дополнительные условия, потребуем также непрерывности первой и второй производных сплайна во всех точках, включая узлы. Для этого следует приравнять левые и правые производные S'(x-0), S"(x + 0), S"(х-0), S''(x + 0) во внутреннем узле x_i.

Вычислив выражения для производных S'(x), S"(x), последовательным диф­ференцированием (2):

S'(x)= b_i + 2c_i (x-x_i-1)+3d_i ( x-x_i-1)²,                      (5)

S"(х) = 2c_i +6d_i ( x-x_i-1).                              (6)

найдем правые и левые производные в узле:

S'(x-0)= b_i + 2c_i h_i+2 d_i h_i²,

S'(x_i+0)=b_i+1.

где i = 1,2,…,n-1.

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

S"(x-0)= 2c_i +6 d_i h_i,

S"(x+0)= 2c_i+1. 

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

b_i+1 = b_i + 2c_i h_i+2 d_i h_i²,                                               (7)

c_i+1 ⁼ c_i +3 d_i h_i.                                           (8)

где i = 0,1,…,n-1.

Уравнения (7), (8) дают еще 2(n-1) условий. Для получения недостающих уравнений накладывают требования к поведению сплайна на концах отрезка интерполяции. Если потребовать нулевой кривизны сплайна на концах отрезка интерполяции (т. е. равенство нулю второй производной), то получим:

с₁ = 0, c_n+ 3d_nh_n =0.                                          (9) 

Исключив из уравнений (3)—(8) п неизвестных а_i, , получаем систему уравнений:

b_ih_i - c_i h_i² - d_i h_i³=y_i- y_i-1,

b_i+1 - b_i – 2c_i h_i  -3d_i h_i²=0,

c_i+1 - c_i -3d_i h_i²=0,                                                  (10) 

c₁=0,

c_n + 3d_n h_n=0.

где i = 0,1,…,n-1.

Система (10) состоит из 3n уравнений. Решив систему (10), получаем значения неизвестных b_i, c_i, d_i, определяющих совокупность всех формул для искомого интерполяционного сплайна:

S_i(x)=a_i+b_i(x-x_i-1)+c_i(x-x_i-1)²+ d_i(x-x_i-1)³                                           (11) 

где i = 0,1,...,n-1.

Программа, реализующая метод сплайн-интерполяции, оказывается доста­точно громоздкой, поэтому мы ограничимся обсуждением решения задачи об интерполяции синуса с помощью сплайнов, используя функции пакета Mathcad: interp(VS, X, у, z), lspline(x, y), pspline(x, y), cspline(x, y).

РАСЧЕТНАЯ ЧАСТЬ

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

         Интерполируемая функция задана табл.1, состоящей из четырех узлов (п = 3):

Таблица 1. Исходные данные к задаче интерполяции

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

Найти значение коэффициентов a_i, b_i

Решение:

Воспользуемся формулой (1) и реализуем ее на «Mathcad»:

Найдем  коэффициенты a и  b по  ф .(1):

Запишем уравнение в общем виде:

Выполним проверку:

=> коэффициенты a и b найдены правильно.

Найдем интерполяцию (приближенное значение функции) с шагом 0,5:

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

Находим:

Выполним линейную интерполяцию с помощью встроенного функции linterp (VX,VY,x):

Построим график (Приложение 1).

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

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

Решение: 

1. Составляем систему, состоящую из девяти уравнений которую можно решить одним из методов.

Получим значения коэффициентов b_i , с_i, d_i, которые определяют иско­мый сплайн.

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

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

Запишем сплайн функции:

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

Пример найти f(0.5)

Построим график (Приложение 2)

Вывод: Таким образом, мы закрепили свои знания о постановке и методах решения оптимизационных задач, решили систему уравнений на ЭВМ в программе Mathcad. Нашли приближенное значение функции с помощью линейной и сплайновой интерполяции, а также с помощью Mathcad. Интерполяция  сплайнами  сопряжена  с  немалым  объемом вычислительной работы. Весьма необычна и форма окончательного результата, ибо сплайн имеет различные представления на различных частичных отрезках интерполяции.  Это  осложняет  доступ  к  значениям  сплайна  в  каждой конкретной  точке,  так  как  предполагает  прежде  всего  поиск  параметров, определяющих  соответствующую  формулу  сплайна.  Эти  трудности  легко предотвратимы  при  использовании ЭВМ.

Приложение 1

Приложение 2