Кубический интерполяционный сплайн

↑

▷ Содержание

Стр 1 из 7Следующая ⇒

Слово сплайн (английское слово "spline") означает гибкую линейку, используемую для проведения гладких кривых через заданные точки на плоскости. Форма этого универсального лекала на каждом отрезке описывается кубической параболой. Сплайны широко используются в инженерных приложениях, в частности, в компьютерной графике. Итак, на каждом i –м отрезке [ x_{i –1}, x_i ], i= 1, 2,…, N, решение будем искать в виде полинома третьей степени:

S_i (x) =a_i+b_i (x–x_i) +c_i (x – x_i)²/2 +d_i (x–x_i)³/6

Неизвестные коэффициенты a_i, b_i, c_i, d_i, i= 1, 2,..., N, находим из:

• условий интерполяции: S_i (x_i) =f_i, i= 1, 2,..., N; S ₁(x ₀) =f ₀,

• непрерывности функции S_i (x_{i– 1} )=S_{i– 1}(x_{i –1}), i= 2, 3,..., N,

• непрерывности первой и второй производной:

S ^/_i (x_{i– 1})= S ^/_{i– 1}(x_{i –1}), S ^//_i (x_{i –1}) =S ^//_{i –1}(x _{i –1}), i= 2, 3,..., N.

Учитывая, что , для определения 4 N неизвестных получаем систему 4 N –2 уравнений:

a_i=f_i, i= 1, 2,..., N,

b_i h_i – c_ih_i ²/2 + d_i h_i ³/6 =f_i – f_{i –1}, i= 1, 2,..., N,

b_i – b_i–1 = c_i h_i – d_i h_i ²/2, i= 2, 3,..., N,

d_i h_i = c_i – c_{i– 1}, i= 2, 3,..., N.

где h_i=x_i – x_{i– 1.} Недостающие два уравнения выводятся из дополнительных условий: S ^// (a) =S ^// (b) =0. Можно показать, что при этом . Из системы можно исключить неизвестные b_i , d_i , получив систему N+ 1 линейных уравнений (СЛАУ) для определения коэффициентов c_i:

c ₀ = 0, c_N = 0,

h_ic_{i –1} + 2(h_i+h_{i +1}) c_i+h _{i +1} c_{i +1} = 6 , i= 1, 2,…, N –1. (1)

После этого вычисляются коэффициенты b_i, d_i:

, i= 1, 2,..., N. (2)

В случае постоянной сетки h_i=h этасистема уравнений упрощается.

Данная CЛАУ имеет трехдиагональную матрицу и решается методом прогонки.

Коэффициенты определяются из формул:

Для вычисления значения S (x) в произвольной точке отрезка z ∈[ a, b ] необходимо решить систему уравнений на коэффициенты c_i, i= 1,2,…, N –1, затем найти все коэффициенты b_i, d_i. Далее, необходимо определить, на какой интервал [ x_{i 0,} x_{i 0–1}] попадает эта точка, и, зная номер i₀, вычислить значение сплайна и его производных в точке z

S (z) =a_{i 0} +b_{i 0}(z–x_{i 0}) +c_{i 0}(z–x_{i 0})²/2 +d_{i 0}(z–x _{i 0})³/6

S ^/ (z) =b_{i 0} +c_{i 0}(z–x_{i 0}) +d_{i 0}(z–x _{i 0})²/2, S ^// (z) =c_{i 0} +d_{i 0}(z–x _{i 0}).

Пример.

Требуется вычислить значения функции в точках 0.25 и 0.8, используя сплайн – интерполяцию.

В нашем случае: h_i=1/4, .

Выпишем систему уравнений для определения :

Решая эту систему линейных уравнений, получим: .

Рассмотрим точку 0.25, которая принадлежит первому отрезку, т.е. . Следовательно, получим,

Рассмотрим точку 0.8, которая принадлежит четвертому отрезку, т.е. .

Следовательно,

Глобальная интерполяция

В случае глобальной интерполяции отыскивается единый полином на всем интервале [ a, b ], т.е. строится полином, который используется для интерполяции функции f(x) на всем интервале изменения аргумента x. Будем искать интерполирующую функцию в виде полинома (многочлена) m –ой степени P_m (x) =a ₀ +a ₁ x+a ₂ x ² +a ₃ x ³ +…+a_m x^m. Какова должна быть степень многочлена, чтобы удовлетворить всем условиям интерполяции? Допустим, что заданы две точки: (x ₀, f ₀) и (x ₁, f ₁), т.е. N=1. Через эти точки можно провести единственную прямую, т.е. интерполирующей функцией будет полином первой степени P ₁(x) =a ₀ +a ₁ x. Через три точки (N=2) можно провести параболу P ₂(x) =a ₀ +a ₁ x+a ₂ x ² и т.д. Рассуждая таким способом, можно предположить, что искомый полином должен иметь степень N.

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

Данная система является линейной относительно искомых коэффициентов a ₀, a ₁, a ₂, …, a_N. Известно, что СЛАУ имеет решение, если ее определитель отличен от нуля. Определитель данной системы

носит имя определителя Вандермонда. Из курса математического анализа известно, что он отличен от нуля, если x_k ≠ x_m (т.е. все узлы интерполяции различные). Таким образом, доказано, что система имеет решение.

Мы показали, что для нахождения коэффициентов
a ₀, a ₁, a ₂, …, a_N надо решить СЛАУ, что является сложной задачей. Но есть другой способ построения полинома N –й степени, который не требует решения такой системы.

Полином Лагранжа

Решение ищем в виде , где l_i (z) – базисные полиномы N –й степени, для которых выполняется условие: . Убедимся в том, что если такие полиномы построены, то L_N(x) будет удовлетворять условиям интерполяции:

.

Каким образом построить базисные полиномы? Определим

, i= 0, 1, ..., N.

Легко понять, что

, и т.д.

Функция l_i (z) является полиномом N –й степени от z и для нее выполняются условия "базисности":

=0, i≠k;, т.е. k=1,…,i-1 или k=i+1,…,N.

.

Таким образом, нам удалось решить задачу о построении интерполирующего полинома N– й степени, и для этого не нужно решать СЛАУ. Полином Лагранжа можно записать в виде компактной формулы: . Погрешность этой формулы можно оценить, если исходная функция g (x) имеет производные до N+ 1 порядка:

.

Из этой формулы следует, что погрешность метода зависит от свойств функции g (x), а также от расположения узлов интерполяции и точки z. Как показывают расчетные эксперименты, полином Лагранжа имеет малую погрешность при небольших значениях N <20. При бόльших N погрешность начинает расти, что свидетельствует о том, что метод Лагранжа не сходится (т.е. его погрешность не убывает с ростом N).

Рассмотрим частные случаи. Пусть N=1, т.е. заданы значения функции только в двух точках. Тогда базовые полиномы имеют вид:

, т.е. получаем формулы кусочно–линейной интерполяции.

Пусть N=2. Тогда:

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

Пример: Заданы значений некоторой функции:

Требуется найти значение функции при z= 1, используя интерполяционный полином Лгранжа. Для этого случая N =3, т.е. полином Лагранжа имеет третий порядок. Вычислим значения базисных полиномов при z =1:

Подбор эмпирических формул

При интерполировании функций мы использовали условие равенства значений интерполяционного полинома и данной функции в узлах интерполяции. Если же исходные данные получены в результате опытных измерений, то требование точного совпадения не нужно, так как данные не получены точно. В этих случаях можно требовать лишь приближенного выполнения условий интерполяции . Это условие означает, что интерполирующая функция F(x) проходит не точно через заданные точки, а в некоторой их окрестности, так, например, как это показано на рис.

Тогда говорят о подборе эмпирических формул. Построение эмпирической формулы состоит из двух этапов6 подбора вида этой формулы , содержащей неизвестные параметры , и определение наилучших в некотором смысле этих параметров. Вид формулы иногда известен из физических соображений (для упругой среды связь между напряжением и деформацией) или выбираются из геометрических соображений: экспериментальные точки наносятся на график и примерно угадывается общий вид зависимости путем сравнения полученной кривой с графиками извесиных функций. Успех здесь в значительной степени определяется опытом и интуицией исследователя.

Для практики важен случай аппроксимации функции многочленами, т.е. .

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

Метод наименьших квадратов

Пусть для исходных данных x_i, f_i, i= 1 ,…,N (нумерацию лучше начинать с единицы), выбран вид эмпирической зависимости: с неизвестными коэффициентами . Запишем сумму квадратов отклонений между вычисленными по эмпирической формуле и заданными опытными данными:

.

Параметры будем находить из условия минимума функции . В этом состоит метод наименьших квадратов (МНК).

Известно, что в точке минимума все частные производные от по равны нулю:

(1)

Рассмотрим применение МНК для частного случая, широко используемого на практике. В качестве эмпирической функции рассмотрим полином

.

Формула (1) для определения суммы квадратов отклонений примет вид:

(2)

Вычислим производные:

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

Данная система уравнений называется нормальной. Решая эту систему линейных уравнений, получаем коэффициенты .

В случае полинома первого порядка m=1, т.е. , система нормальных уравнений примет вид:

При m=2 имеем:

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

Пример. Заданы координаты точек:

т.е. N=6. Требуется найти эмпирические зависимости: линейную , квадратичную , гиперболическую по методу МНК и выбрать среди них наилучшую по наименьшей сумме квадратов отклонений.

Система нормальных уравнений для линейной зависимости:

Учитывая, что N=6, , получим

Решая систему линейных уравнений, получим . Следовательно, линейная зависимость имеет вид: .

Вычислим сумму квадратов отклонений: .

Рассмотрим квадратичную зависимость. Система нормальных уравнений имеет вид

Найдем неподсчитанные суммы:

Решая СЛАУ, получим

Следовательно, квадратичная зависимость имеет вид: .

Вычислим сумму квадратов отклонений: .

Выпишем систему нормальных уравнений для гиперболической зависимости. Согласно МНК находим сумму квадратов отклонений:

. Составляем систему нормальных уравнений:

Или

Учитывая, что , получим

Сумма квадратов отклонений:

Из трех зависимостей выбираем наилучшую, т.е. квадратичную.

Познавательные статьи:



Психологические особенности спортивного соревнования

Приготовление дезинфицирующих растворов различной концентрации

Занятость населения и рынок труда

Социальный статус семьи и её типология