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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

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

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

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

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

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

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

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

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

Автор: Моисеенко Александр Николаевич

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

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

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

2012 г.

ЗАДАНИЕ

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

Студент: Моисеенко Александр Группа ВБМО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₁ в точке x₀ было бы нулевым, т.е.

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



,

,

,

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

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

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

,

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

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

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})² + d_i(x -₁)³,

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_ih_i + c_ih + d_ih = 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 и 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₁ = 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 = х₀, х₁, . . ., х_n, которые называются узлами интерполяции, и значения некоторой функции f(x) в этих точках

f(x₀) = y₀, f(x₁) = y₁, . . ., f(x_n) = y_n.

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

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

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

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

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

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

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

kjj



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/сплайн

Размещено на Allbest.ru