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

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) таким образом, чтобы:

77

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).

78

Для того чтобы решение существовало и было единствен-ным, необходимо выполнение условия  _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 крае-вых условий по полученному полному набору геометри-ческих условий определяют коэффициенты полиномов, входящих в сплайн. В общем случае для этого можно, как и у многочленов, использовать метод неопределённых коэф-фициентов, в котором все неизвестные определяются из одной линейной системы уравнений. Более оптимальный метод для построения кубических сплайнов будет рас-смотрен ниже.

79

Допустим, каждый 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 задаёт полный набор коэффи-циентов, входящих в многочлены сплайна,

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

80

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

В общем случае решение системы (вектор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 , то для однознач-ности решения задачи необходимо задать еще два краевых условия. Зададим оба условия в начальной точке:

81

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.

82