Сплайны.

Линейная и квадратичная интерполяция.

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

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

.

Отсюда

(9).

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

Блок-схема линейной интерполяции.

Рассмотрим случай квадратичной интерполяции. В качестве интерполяционной функции на отрезке принимается квад­ратный трехчлен. Такую интерполяцию называют параболической.

Уравнение квадратного трехчлена

(10).

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

(11).

Блок-схема алгоритма такая же, как и для линейной интерполяции . Только нужно использовать формулы (10) с учетом решения системы линейных уравнений (11). Интерполяция для любой точки проводит­ся по трем ближайшим к ней узлам.

В настоящее время широкое распространение для интерполяции получило использование кубических

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

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

(12).

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

.

Эти условия можно записать в виде

(13)

(14) .

Эта система содержит уравнений. Для получения недостающих урав­нений зададим условия непрерывности первых и вторых производных в узлах интерполяции, т.е. условия гладкости кривой во всех точках.

Вычислим производные многочлена (12):

Приравнивая в каждом внутреннем узле значения этих производных, вычисленные в левом и правом от узла интервалах, получаем уравнений.

(15)

(16)

Недостающие два уравнения получаются из условий закрепления кон­цом сплайна.

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

, (17).

Уравнения (13-17) со­ставляют систему линейных алгебраических уравнений для определения коэффициентов . Она решается известными методами.

Однако с целью экономии памяти ЭВМ и машинного времени эту систему можно привести к более удобному виду. Из условия (13) сразу можно найти все коэффициенты . Далее, из (16) и (17) получим

, , . (18)

Подставим эти соотношения, а также значения в (14) и най­дем отсюда коэффициенты

, , . (19)

Учитывая выражения (18) и (19), исключаем из уравнения (15) ко­эффициенты и . Окончательно получим следующую систему урав­нений только для коэффициентов :

, , , (20).

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