3.2. Построение интерполяционных сплайнов

3.2.1. Общая постановка задачи. Решение методом неопределённых коэффициентов

Рассмотрим решение одномерной задачи. Обозначим величины параметра t в узловых точках P₀, P₁,...,Р_n через t₀, t₁, ... ,t_n. При этом t₀ <t₁< ...<t_n. На каждом i-ом сегменте интерполирования [t_i-1, t_i ] (i=1,...,n) искомый кусочно-полиномиальный сплайн задается отдельным многочленом S_i(t) таким образом, чтобы:

74

1. в узловых точках t_i-1, t_i многочлен S_i(t) совпадал со зна-чениями y_i-1, y_i;

2. в тех точках t_i-1, t_i, которые являются внутренними, у многочлена S _i (t) совпадали производные от 1-го до m-го

порядков с аналогичными производными соседних много-членов.

В математической форме выражение искомой кусоч-но-полиномиальной функции P(t) можно представить в виде:

P(t)=S_i(t) при t_i-1  t  t_i ; i=1,2,…,n – условие кусочности сплайна P(t);

S_i(t_i-1)=P_i-1;S_i(t_i)=P_i, i=1,2,…,n – условия прохождения через заданные точки;

S_i^-j(t_i)=S_i+1^-j(t_i), j=1,…,m, i=1,…,n-1 - условия на глад-кость во внутренних точках. (3.6)

Поскольку методика интерполирования одинакова по всем координатам (x,y,z), то рассмотрим интерполирование только по одной координате х. Соответствующие сплайны обозначим нижним индексом х. Постановка задачи имеет вид:

1. x(t)=S_{х i}(t); t_i-1  t  t_i, i=1,…,n;

2. S_{х i} (t_i-1)=x_i-1 ; S _{х i} (t_i)=x_i , i=1,…,n;

3. S_{х i} ^j(t_i)=S_{х (i+1)} ^j(t_i), j=1,…,m, i=1,…,n-1. (3.7)

Число геометрических условий связи, налагаемых на искомую кусочно-полиномиальную функцию x(t) системой (3.7), складывается из 2n (во второй строке) и m(n-1) (в третьей). Суммарное их число равно:

_s = 2n + m(n - 1) = n(m + 2) - m.

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

 _K = n(k+1).

75

Для того чтобы решение существовало и было един-ственным, необходимо выполнение условия  _S =  _K. Для этого:

1. принимают степень многочленов сплайна k = m+1;

2) дополнительно вводят m условий связи, которые называют краевыми условиями , поскольку обычно их задают в конечных точках P_0, P_n , исходя из специфики решаемой задачи.

Наиболее распространенным случаем является ин-терполяция при m = 2 (гладкость 2-ой степени). В этом случае необходимо использовать кубические сплайны (k = 3) и добавить 2 дополнительных краевых условия на производные. Чаще всего налагают следующие виды крае-вых условий.

1) S₁ ¹(t₀)=f ¹(t₀), S_n ¹(t_n)=f ¹(t_n ) - условия на первые производные. Применяют в том случае, когда сплайн в концевых точках необходимо гладко соединить с некоторой кривой f(t ).

2) S₁ ¹¹(t₀)=f ¹¹(t₀), S_n ¹¹(t_n)=f ¹¹(t_n ) - условия на вторые производные. Обычно они используются для уменьшения осцилляции сплайна.

3) S₁ ¹(t₀) = S_n ¹(t_n); S₁ ¹¹(t₀) = S_n ¹¹(t_n) - условия для периодических функций, заключающиеся в том, что в конечных точках интервала равны не только значения, но и две первых производных сплайна.

После определения степени сплайна k и задания m краевых условий по полученному полному набору гео-метрических условий определяют коэффициенты поли-номов, входящих в сплайн. В общем случае для этого можно, как и у многочленов, использовать метод неопре-делённых коэффициентов, в котором все неизвестные определяются из одной линейной системы уравнений. Бо-лее оптимальный метод для построения кубических сплай-нов будет рассмотрен ниже.

76

Допустим, каждый i –тый участок сплайна имеет вид

S_xi(t)=C_i0+C_i1t+...+C_ikt^k .

Каждое из условий второй строки системы (3.7) даёт по одному уравнению:

C_i0 + C_i1 t_i-1 + ... + C_ik t_i-1 ^k = x_i-1 ;

C_i0 + C_i1 t_i + ...+ C_ik t_i ^k = x_i .

Рассмотрим равенство первых производных во внутренних точках S_хi ¹(t_i)=S_х(i+1)¹(t_i) в третьей строке системы (3.7). После взятия первых производных по t в S_xi и S_{x( i+1)} и подстановки t = t_i получим уравнение

C_i1+2C_i2t_i+…+kC_ikt_i^k-1 = C_(i+1)1+2C_(i+1)2t_i+…+kC_(i+1)kt_i^k-1 .

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

C_i1+2C_i2t_i+…+kC_ikt_i^k-1-C_(i+1)1-2C_(i+1)2t_i-…-kC_(i+1)kt_i^k-1=0.

При j = 2 из условия S_xi¹¹(t_i) = S_x(i+1)¹¹(t_i) после

а) определения вторых производных,

б) подстановки в них узловых точек и

в) переноса всех слагаемых, содержащих неизвестные (коэффициенты полдиномов сплайна),получим:

2C_i2+…+k (k-1) C_ikt_i^k-2- 2C_(i+1)2-…-k(k-1)C_(i+1)k t_i^k-2 = 0 .

Для более высоких степеней производных действия аналогичны.

После объединения всех полученных уравнений полу-чаем линейную систему вида

AC=Х,

в которой:

- неизвестный векторC задаёт полный набор коэффи-циентов, входящих в многочлены сплайна,

- матрица А содержит сомножители при коэффициентах, с которыми они входят в уравнения, ненулевые значения в ней располагаются на главной, а также соседних с ней диагоналях,

77

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

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

Пример. Построить сплайн P(t), проходящий через три точки ( х(t₀)=x₀ , x(t₁)=x₁, x(t₂)=x₂ ) , который во внутренней точке x(t₁)=x₁ имел бы гладкость 2-ой степени (Рис.3.1).

x

S₁(t) S₂(t)

x₁

x₂

x₀

0

t₀ t₁ t₂ t

Рис.3.1

Решение. Интервала два, поэтому искомые многочлены на них обозначим S₁(t), S₂(t). Зададим их следующим образом:

S₁(t)=C₀₁+C₁₁t+C₂₁t²+C₃₁t³; S₂(t)=C₀₂+C₁₂t+C₂₂t²+C₃₂t³.

Условия I рода имеют вид:

S₁(t₀)=x₀; S₁(t₁)=x₁; S₂(t₁)=x₁; S₂(t₂)=x₂.

Условия II рода при m=2 и n=3 будут следующими:

S₁ (t₁)= S₂ (t₁); S₁ (t₁)= S₂ (t₁).

Поскольку n(k+1) - n(m+2) = m = 2 , то для одно-значности решения задачи необходимо задать еще два крае-вых условия. Зададим оба условия в начальной точке:

78

S₁(t₀)=0; S₁ (t₀)=0.

Подставляя в уравнения многочленов значения пара-метра, из условий I рода получаем:

C₀₁+C₁₁t₀+C₂₁t²₀+C₃₁t³₀=x₀ ;

C₀₁+C₁₁t₁+C₂₁t²₁+C₃₁t³₁=x₁ ;

C₀₂+C₁₂t₁+C₂₂t²₁+C₃₂t³₁=x₁ ;

C₀₂+C₁₂t₂+C₂₂t²₂+C₃₂t³₂=x₂ .

Дифференцируя многочлены по параметру и подстав-ляя в первые и вторые производные t = t₁ , из условий II рода получаем:

C₁₁ + 2C₂₁t₁ + 3C₃₁t₁² - C₁₂ - 2C₂₂t₁ - 3C₃₂t₁² = 0;

2C₂₁ + 6C₃₁t₁ - 2C₂₂ - 6C₃₂t₁ = 0.

Из краевых условий получаем:

C ₁₁ + 2C₂₁t₀ + 3C₃₁t₀ ² = 0;

2C₂₁ + 6C₃₁t₀ = 0.

Объединим все полученные уравнения в систему ви-да AC=Х, где

Коэффициенты обоих многочленов сплайна находят-ся одновременно при решении данной системы:

C = A ^–1 Y.

79