Основная задача интерполяции - нахождение значения таблично заданной функции в тех точках внутри данного интервала, где она не задана. Исходные табличные данные могут быть получены как экспериментально (в этом случае принципиально отсутствуют промежуточные данные без дополнительных работ), так и расчетным путем по сложным зависимостям (в этом случае найти с помощью интерполяции значение сложной функции бывает проще, чем непосредственным вычислением по сложной формуле)
Концепция интерполяции
Решение задач интерполяции и экстраполяции обеспечивается построением интерполяционной функции 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).
Министерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
«Донской государственный университет»
Кафедра «Программное обеспечение вычислительной техники и автоматизированных систем» «ПОВТ и АС»
Специальность: Математическое обеспечение и администрирование информационных систем
КУРСОВАЯ РАБОТА
по дисциплине «Методы вычисления»
на тему: «Интерполяция сплайнами»
Руководитель работы:
Медведева Татьяна Александровна
Ростов-на-Дону
ЗАДАНИЕ
на курсовую работу по дисциплине «Методы вычислений»
Студент: Моисеенко Александр Группа ВБМО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
Задача нахождения экстремума: сущность и содержание, оптимизация. Решение методами квадратичной интерполяции и золотого сечения, их сравнительная характеристика, определение основных преимуществ и недостатков. Количество итераций и оценка точности.
Пусть задана таблица значений функции y i в узлах х 0 < х 1 < ... < х п .Обозначим h i = x i – x i -1 , i = 1, 2, ... , п .
Сплайн – гладкая кривая, проходящая через заданные точки (х i , y i ), i = 0, 1, ... , п . Интерполяция сплайнами заключается в том, что на каждом отрезке [х i -1 , x i ]используется многочлен определенной степени. Наиболее часто применяется многочлен третьей степени, реже – второй или четвертой. При этом для определения коэффициентов многочленов используются условия непрерывности производных в узлах интерполяции.
Интерполяция кубическими сплайнами
представляет собой локальную интерполяцию, когда на каждом отрезке [х i
-1 , x i
], i =
1, 2, ... , п
применяется кубическая кривая, удовлетворяющая некоторым условиям гладкости, а именно, непрерывности самой функции и ее первой и второй производных в узловых точках. Использование кубической функции вызвано следующими соображениями. Если предположить, что интерполяционная кривая соответствует упругой линейке, закрепленной в точках (х i
, y i
),то из курса сопротивления материалов известно, что эта кривая определяется как решение дифференциального уравнения f
(IV) (x
) = 0 на отрезке [х i
-1 , x i
](для простоты изложения мы не рассматриваем вопросы, связанные с физическими размерностями). Общим решением такого уравнения является многочлен 3-й степени с произвольными коэффициентами, который удобно записать в виде
S i
(x
) = а i
+ b i
(х
- x i
-1) + с i
(x
- x i
-1) 2 + d i
(x
- x i
-1) 3 ,
х i
-1 £ х
£ х i
, i =
1, 2, ... , п
.(4.32)
Коэффициенты функций S i (x )определяются из условий непрерывности функции и ее первой и второй производных во внутренних узлах x i , i = 1, 2,..., п - 1.
Из формул (4.32) при х = х i -1 получим
S i (x i- 1) = y i -1 = a i , i = 1, 2,..., п ,(4.33)
а при х = х i
S i (x i ) = а i + b i h i + с i h i 2 + d i h i 3 ,(4.34)
i = 1, 2,..., n .
Условия непрерывности интерполяционной функции записываются в виде S i (x i ) = S i -1 (x i ), i = 1, 2, ... , n - 1 и из условий (4.33) и (4.34) следует, что они выполнимы.
Найдем производные функции S i (x ):
S" i (x ) = b i + 2с i (х - x i -1) + 3di (х – x i -1) 2 ,
S" i (x ) = 2c i + 6d i (x - x i -1).
При x = x i -1 , имеем S" i (x i -1) = b i , S" (x i -1) = 2с i , а при х = х i получим
S" i (x i ) = b i + 2с i h i + 3dih i 2 , S" (x i ) = 2с i + 6d i h i .
Условия непрерывности производных приводят к уравнениям
S" i (x i ) = S" i +1 (x i ) Þ b i + 2с i h i + 3dih i 2 = b i +1 ,
i = l, 2,... , п - 1. (4.35)
S" i (x i ) = S" i +1 (x i ) Þ 2с i + 6d i h i = 2c i +1 ,
i = l, 2,..., n - 1. (4.36)
Всего имеем 4n – 2 уравнений для определения 4n неизвестных. Чтобы получить еще два уравнения, используют дополнительные краевые условия, например, требование нулевой кривизны интерполяционной кривой в концевых точках, т. е. равенства нулю второй производной на концах отрезка [а , b ] а = х 0 , b = х n :
S" 1 (x 0) = 2c 1 = 0 Þ с 1 = 0,
S" n (x n ) = 2с n + 6d n h n = 0 Þ с n + 3d n h n = 0. (4.37)
Систему уравнений (4.33)–(4.37) можно упростить и получить рекуррентные формулы для вычисления коэффициентов сплайна.
Из условия (4.33) имеем явные формулы для вычисления коэффициентов a i :
a i = y i -1 , i= 1,..., n . (4.38)
Выразим d i через c i с помощью (4.36), (4.37):
; i = 1, 2,...,n ; .
Положим с n +1 = 0, тогда для d i получим одну формулу:
, i = 1, 2,...,n . (4.39)
Подставим выражения для а i и d i в равенство (4.34):
, i = 1, 2,..., n .
и выразим b i , через с i :
, i = 1, 2,..., n . (4.40)
Исключим из уравнений (4.35) коэффициенты b i и d i с помощью (4.39) и (4.40):
i = 1, 2,..., n -1.
Отсюда получим систему уравнений для определения с i :
Система уравнений (4.41) может быть переписана в виде
Здесь введено обозначение
, i =1, 2,..., n - 1.
Решим систему уравнений (4.42) методом прогонки. Из первого уравнения выразим с 2 через с 3:
c 2 = a 2 c 3 + b 2 , , . (4.43)
Подставим (4.43) во второе уравнение (4.42):
h 2 (a 2 c 3 + b 2) + 2(h 2 + h 3)c 3 + h 3 c 4 = g 2 ,
и выразим с 3 через с 4:
с 3 = a 3 с 4 + b 3 , (4.44)
Предполагая, что с i -1 = a i -1 c i + b i -1 из i -го уравнения (4.42) получим
c i = a i с i +1 + b i
, i = 3,..., n – 1, a n = 0, (4.45) c n +1 = 0,
c i = a i с i +1 + b i , i = n , n -1,..., 2, (4.48)
c 1 = 0.
3. Вычисление коэффициентов а i , b i , d i :
a i = y i -1 ,
i = 1, 2,..., n .
4. Вычисление значения функции с помощью сплайна. Для этого найти такое значение i ,что данное значение переменной х принадлежит отрезку [x i -1 , x i ] и вычислить
S i (x ) = а i + b i (х - x i -1) + с i (x - x i -1) 2 + d i (x - x i -1) 3 . (4.50)
Интерполяционные формулы Лагранжа, Ньютона и Стирлинга и др. при использовании большого числа узлов интерполяции на всем отрезке [a
, b
] часто приводят к плохому приближению из-за накопления погрешностей в процессе вычислений . Кроме того, из-за расходимости процесса интерполяции увеличение числа узлов не обязательно приводит к повышению точности. Для снижения погрешностей весь отрезок [a
, b
] разбивается на частичные отрезки и на каждом из них функциюзаменяют приближенно полиномом невысокой степени. Это называется кусочно-полиномиальной интерполяцией
.
Один из способов интерполирования на всем отрезке [a
, b
] является интерполирование сплайнами
.
Сплайном
называется кусочно-полиномиальная функция, определенная наотрезке [a
, b
] и имеющая на этом отрезке некоторое количество непрерывных производных. Преимущества интерполяции сплайнами по сравнению с обычными методами интерполяции – в сходимости и устойчивости вычислительного процесса.
Рассмотрим один из наиболее распространенных в практике случаев – интерполирование функции кубическим сплайном
.
Пусть на отрезке [a
, b
] задана непрерывная функция. Введем разбиение отрезка:
и обозначим , 
.
Сплайном, соответствующим данной функциии узлам интерполяции (6) называется функция , удовлетворяющая следующим условиям:
1) на каждом отрезке , функция является кубическим многочленом;
2) функция , а также ее первая и вторая производные непрерывны на отрезке [a , b ] ;
Третье условие называется условием интерполирования
. Сплайн, определяемый условиями 1) – 3), называется интерполяционным кубическим сплайном
.
Рассмотрим способ построения кубического сплайна .
На каждом из отрезков ,
будем искать сплайн-функцию в виде полинома третьей степени:
(7)
где 
искомые коэффициенты.
Продифференцируем (7) трижды по х :
откуда следует
Из условия интерполирования 3) получаем:
Из условий непрерывности функции вытекает.