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

ЛЕКЦИЯ №11

Одним из способов интерполирования на всем отрезке является интерполирование с помощью сплайн функций. Сплайн функцией или сплайном называют кусочно – полиномиальную функцию, определенную на всем отрезке [a,b] и имеющую на этом отрезке некоторое число непрерывных производных.

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

Построение кубического сплайна.

Пусть на [a, b] задана непрерывная функция f(x). Введем сетку

и обозначим fi=f(xi), i=0,1, ,N.

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

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

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

3.

Последнее условие называется условием интерполирования, а сплайн, определяемый условиями 1)-3), называется также интерполяционным кубическим сплайном.

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

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

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

(1)

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

(2)

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

3)

Недостающие два условия обычно получают из естественного предположения о нулевой кривизне графика на концах:

, (4)

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

Уравнения (1-4) образуют систему линейных уравнений для определения 4N неизвестных коэффициентов. Эту систему можно решить методом исключения Гаусса, но выгоднее привести ее к специальному виду.

Уравнение (1) дает сразу все коэффициенты аi. Из уравнений (3) и (4)

(5)

Подставим (5) в (1), одновременно исключая аi=fi-1, получим:

(6)

Исключая теперь из (3) bi и bi+1 по (6) и di по (5), получаем систему уравнений для сi:

Матрица этой системы 3-х диагональная. Такие системы экономно решаются методом прогонки.

В силу диагонального преобладания система имеет единственное решение.

После нахождения сi определяются ai, bi и di и определяется вид кубических многочленов (сплайнов) на каждом отрезке.

Таким образом, доказано, что существует единственный кубический сплайн, определяемый условиями 1)-3) и граничными условиями

Заметим, что можно рассматривать и другие граничные условия.

Можно рассмотреть и более общую задачу интерполяции функции сплайном – многочленом n-ой степени

,

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

На практике наиболее употребительны 2 случая: один при n=3 (кубические многочлены) уже рассмотрен, второй при n-1 (многочлены Ньютона 1-ой степени) соответствует аппроксимации графика ломаной, построенной по узлам; определение коэффициентов при этом очевидно.

ЧИСЛЕННОЕ ИНТЕГРИРОВАНИЕ

 

 

 

 

ПРОСТЫЕ КВАДРАТУРНЫЕ ФОРМУЛЫ

 

 

Общая формула прямоугольников

 

1. Квадратурная формула левых прямоугольников.

 

Пусть

 

 

2. Формула правых прямоугольников

 

 

3. Квадратурная формула средних прямоугольников

 

 

Расчет погрешности формул численного интегрирования.

 

Пусть

 

Пусть h>0 достаточно мало, x0=0.

 

Разложим функцию в ряд Тейлора в окрестности x0=0.:

 

Тогда

Локальная погрешность для малого отрезка h -

 

, то есть

 

 

 

 

Свойство аддитивности

 

 

- погрешность на отрезке [a,b].

 

Квадратурные формулы Ньютона-Котеса

 

 

 

 

 

 

Если многочлен n - степени, то

Это квадратурные формулы интерполяционного типа. Здесь Ск – коэффициенты Котеса

 

Безразмерные формулы.

 

 

Тогда

 

 

Итак

 

 

Квадратурные формулы интерполяционного типа выглядят следующим образом:

 

Свойства коэффициентов Котеса

 

 

Важные частные случаи n=1, n=2

 

1. Квадратурная формула трапеций (n=1)

 

 

 

или, используя запись интерполяционного многочлена в форме Ньютона, получим:

 

Остаточный член для

 

 

2. Квадратурная формула Симпсона (формула парабол) (n=2)

 

 

 

или, используя запись интерполяционного многочлена в форме Ньютона, получим:

 

Итак

- формула Симпсона на отрезке

 

Остаточный член для

 

3. Частные формулы Ньютона - Котеса, n=k, n=3,4,5…

 

Общая формула интерполяционного типа имеет вид:

 

 

k
1/2      
1/3    
3/8  
2/45
               

Составные квадратурные формулы.

 

 

 

1. Общая формула трапеций.

 

 

 

 

 

 

 

 

2. Составная формула Симпсона

 

 

 

 

 

 

 

ЛЕКЦИЯ № 12

Методы Эйлера и Рунге- Кутты решения
начальных задач для обыкновенных дифференциальных уравнений

 

Будем рассматривать обыкновенное дифференциальное уравнение (сокращенно ОДУ) первого порядка

(1)

С начальным условием

(2)

Где - некоторая заданная, в общем случае, нелинейная функция двух переменных. Будем считать, что для данной задачи (1)-(2) называемой начальной задачей или задачей Коши, обеспечиваются существование и единственность на отрезке ее решения .

 

Метод Эйлера – разные подходы к построению.

 

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

X X0 X1 … Xn=b
Y Y0 Y1 … yn » y(b)

приближенных значений yiрешения задачи (1)-(2) в расчетных точках .