close

Вход

Забыли?

вход по аккаунту

?

О сплайнах максимальной гладкости.

код для вставкиСкачать
2004
ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА
Сер. 1
Вып. 4
МАТЕМАТИКА
УДК 519
И. Г. Бурова, Ю. К. Демьянович
О СПЛАЙНАХ МАКСИМАЛЬНОЙ ГЛАДКОСТИ∗
1. Введение
Полиномиальные и неполиномиальные сплайны широко известны (см., например,
[1–8]). Среди полиномиальных сплайнов значительную роль играют B-сплайны; они
однозначно характеризуются носителем из m + 1 соседних сеточных промежутков и
гладкостью m − 1 (принадлежностью к классу C m−1 ).
В данной работе рассматриваются неполиномиальные сплайны, которые принадлежат классу C 1 и имеют носитель, состоящий из трех соседних сеточных промежутков.
Здесь устанавливаются условия существования и единственности пространств таких
сплайнов, предлагаются формулы для их построения и приведены примеры их применения.
def
Пусть Z — множество всех целых чисел, а A = {aj }j∈Z — множество трехмерных
вектор-столбцов aj с вещественными компонентами. Квадратную матрицу третьего порядка с трехкомпонентными вектор-столбцами a, b, c будем обозначать (a, b, c).
На вещественной оси R1 введем сетку
X :
. . . < x−2 < x−1 < x0 < x1 < x2 < . . . ,
(1.1)
и положим
lim xj = a, lim xj = b.
j→−∞
Объединение M
значения
def
=
j→+∞
(1.2)
∪j∈Z (xj , xj+1 ) назовем сеточным подразделением. Введем обоSj
[xj−1 , xj+2 ], Jk = {k − 1, k, k + 1},
def
Aj = aj−1 , aj , aj+1 , k, j ∈ Z.
def
def
=
Множество A называется полной цепочкой векторов, если
detAj = 0
∀j ∈ Z.
(1.3)
Совокупность всех полных цепочек будем обозначать A.
∗ Работа выполнена при частичной финансовой поддержке РФФИ (гранты № 01-01-00336 и
№ 01-01-00394).
c И. Г. Бурова, Ю. К. Демьянович, 2004
3
Линейное пространство вещественнозначных функций, заданных на множестве M ,
обозначим через X.
Рассмотрим трехкомпонентную вектор-функцию ϕ(t) с компонентами из X. Пусть
A = {aj }j∈Z — полная цепочка векторов, а функции ωj ∈ X, j ∈ Z, удовлетворяют
тождествам (называемым аппроксимационными соотношениями [7])
aj ωj (t) ≡ ϕ(t)
∀t ∈ (xk , xk+1 ), ∀k ∈ Z,
(1.4)
j ∈Jk
ωj (t) ≡ 0
∀t ∈
/ Sj ∩ M, ∀j ∈ Z.
(1.5)
При каждом фиксированном t ∈ (xk , xk+1 ) соотношения (1.4) можно рассмотреть
как систему линейных алгебраических уравнений относительно неизвестных ωj (t). Ввиду предположения (1.3) система (1.4) однозначно разрешима. По формулам Крамера
из (1.4) находим
det {aj }j ∈Jk ,j =j j ϕ(t)
ωj (t) =
det {aj }j ∈Jk
∀t ∈ (xk , xk+1 ), ∀j ∈ Jk ,
(1.6)
где значок j означает, что определитель в числителе получается из определителя
в знаменателе заменой столбца aj на столбец ϕ(t) с сохранением прежнего порядка
следования столбцов. Из соотношения (1.5) ясно, что supp ωj ⊂ Sj .
Дадим более наглядную, но менее удобную для использования запись соотношений
(1.4)–(1.6):
ak−1 ωk−1 (t) + ak ωk (t) + ak+1 ωk+1 (t) ≡ ϕ(t),
∀t ∈ (xk , xk+1 ), ∀k ∈ Z,
(1.7)
ωj (t) ≡ 0
∀t ∈ M \Sj , ∀j ∈ Z.
det aj−2 , aj−1 , ϕ(t)
ωj (t) =
при t ∈ (xj−1 , xj ),
det aj−2 , aj−1 , aj
det aj−1 , ϕ(t), aj+1
ωj (t) =
при t ∈ (xj , xj+1 ),
det aj−1 , aj , aj+1
det ϕ(t), aj+1 , aj+2
ωj (t) =
при t ∈ (xj+1 , xj+2 ).
det aj , aj+1 , aj+2
(1.8)
Рассмотрим линейное пространство
⎧
⎨
def
= X
(A,ϕ) (M ) = u
X
cj ωj (t),
|u
(t) =
⎩
j∈Z
∀t ∈ M, ∀cj ∈ R1
(1.9)
(1.10)
(1.11)
⎫
⎬
⎭
.
(1.12)
⊂ X. Пространство X
называется пространством минимальных
Очевидно, что X
(A, ϕ)-сплайнов второго порядка, а функции ωj , j ∈ Z, — образующими простран
ства X.
4
2. Непрерывность минимальных сплайнов
Рассмотрим возможность продолжения функции ωj , j ∈ Z, непрерывным образом
на интервал (a, b). В дальнейшем предполагается, что вектор-функция ϕ(t) задана и
непрерывна на (a, b).
Лемма 1. Пусть A — полная цепочка векторов, и пусть фиксированы k ∈ Z и
t∗ ∈ [xk , xk+1 ]. Для того чтобы
lim
t→t∗ , t∈(xk ,xk+1 )
ωj (t) = 0,
необходимо и достаточно, чтобы
det {aj }j ∈Jk ,j =j j ϕ(t∗ ) = 0.
Доказательство вытекает из формулы (1.6).
Лемма 2. Пусть A — полная цепочка векторов, и в узле xk выполнены условия
lim ωk−2 (t) = 0,
lim ωk+1 (t) = 0.
(2.1)
lim ωj (t) при j ∈ {k − 1, k}.
(2.2)
t→xk −0
t→xk +0
Тогда справедливо соотношение
lim ωj (t) =
t→xk −0
t→xk +0
Доказательство. Заменяя k на k − 1 в соотношении (1.4), имеем
aj ωj (t) ≡ ϕ(t)
∀t ∈ (xk−1 , xk ),
j∈Jk−1
откуда в пределе при t → xk − 0 ввиду первого из предположений (2.1) получаем
aj lim ωj (t) = ϕ(xk ).
(2.3)
j∈{k−1,k}
t→xk −0
Аналогично из (1.4) и второго соотношения в (2.2) находим
aj lim ωj (t) = ϕ(xk ).
j∈{k−1,k}
t→xk +0
(2.4)
Поскольку векторы ak−1 , ak линейно независимы, то из тождеств (2.3)–(2.4) следуют
соотношения (2.2).
Теорема 1. Если A — полная цепочка векторов, и предельные значения функций
ωj (t) (∀j ∈ Z) на границе носителя каждой из них равны нулю, то эти функции
могут быть продолжены до функций, непрерывных на интервале (a, b).
Доказательство. Благодаря непрерывности вектор-функции ϕ(t), достаточно
исследовать непрерывность функций ωj (t) в узлах сетки X . Если узел xk находится на
границе множества Sj , то непрерывность ωj в этой точке вытекает из условия доказываемой теоремы. Если же узел xk лежит внутри этого множества, то в ней выполнены
условия теоремы 1 и, следовательно, справедливо соотношение (2.2).
5
Теорема 2. Если выполнены соотношения
det aj , aj+1 , ϕ(xj+1 ) = 0
∀j ∈ Z,
(2.5)
то функции ωj (t) ∀j ∈ Z, могут быть продолжены до функций, непрерывных на
интервале (a, b).
Доказательство. Покажем, что условие равенства нулю предельных значений
функций ωj (t) (∀j ∈ Z) на границе носителя каждой из них эквивалентно условию
(2.5). Ввиду леммы 1 и формулы (1.6) ясно, что упомянутое условие эквивалентно
соотношениям
det {aj }j ∈Jk ,j =j j ϕ(t) =0
t∈[xk ,xk+1 ] ∩{xj−1 ,xj+2 }
∀k ∈ {j − 1, j, j + 1}, ∀j ∈ Z.
(2.6)
Здесь возможны два случая:
а) в первом случае k = j − 1, и здесь соотношение (2.6) принимает форму
det {aj }j ∈Jj−1 ,j =j j ϕ(t) =0
t=xj−1
∀j ∈ Z,
(2.7)
что в силу формул Jk = {k − 1, k, k + 1}, Jj−1 = {j − 2, j − 1, j} эквивалентно записи
det aj−2 , aj−1 , ϕ(xj−1 ) = 0
∀j ∈ Z,
что, как не трудно видеть, эквивалентно условию (2.5);
б) здесь k = j + 1, и теперь (2.6) имеет вид
det {aj }j ∈Jj+1 ,j =j j ϕ(t) =0
t=xj+2
∀j ∈ Z,
(2.8)
что в силу формулы Jj+1 = {j, j + 1, j + 2} эквивалентно соотношению
det ϕ(xj+2 ), aj+1 , aj+2 = 0
∀j ∈ Z,
что, в свою очередь, тоже эквивалентно условию (2.5).
Теорема 3. Если ϕ ∈ C 1 (a, b) и выполнены соотношения
det aj , aj+1 , ϕ (xj+1 ) = 0
∀j ∈ Z,
(2.9)
то функции ωj (t) ∀j ∈ Z, могут быть продолжены до функций, непрерывных на
интервале (a, b).
Доказательство. Для доказательства достаточно продиффернцировать соотношения (1.4)–(1.5) и применить предыдущие рассуждения.
Определение 1. Минимальные (A, ϕ)-сплайны второго порядка, продолжимые
до функций пространства C 1 (a, b), называются Bϕ -сплайнами второго порядка.
6
3.
Свойства и построение Bϕ -сплайнов второго порядка
В этом разделе будем считать, что ϕ ∈ C 1 (a, b).
Предположим, что векторы ϕ(xj ) и ϕ (xj ) линейно независимы для всех j ∈ Z. В
пространстве R3 рассмотрим двумерные подпространства Γj , натянутые на векторы
ϕ(xj ) и ϕ (xj ):
Γj = L{ϕ(xj ), ϕ (xj )} ∀j ∈ Z;
(3.1)
здесь символ L{. . .} означает линейную оболочку векторов, находящихся в фигурных
скобках.
Пусть Nj — нормаль к пространству Γj , определяемая формулой
Nj
def
=
ϕ(xj ) × ϕ (xj );
(3.2)
здесь символ × означает векторное произведение. Положим Nϕ
векторы bj равенствами
def
bj = Nj × Nj+1 ∀j ∈ Z.
def
=
{Nj | j ∈ Z} и введем
(3.3)
Лемма 3. Пусть даны трехмерные векторы a, b, c, d, и каждая из троек a, b, c
и b, c, d является линейно независимой системой. Тогда векторы
a × b,
b × c,
c×d
(3.4)
линейно независимы.
Доказательство. Проведем доказательство от противного. Допустим, что существуют числа α и β такие, что
α a × b + β b × c = c × d.
(3.5)
Умножая (3.5) скалярно на вектор c и используя представление смешанного произведения векторов через определитель, из очевидных равенств det(b, c, c) = 0, det(c, d, c) = 0
найдем α det(a, b, c) = 0, откуда ввиду линейной независимости векторов a, b, c получим α = 0. Теперь из (3.5) вытекает равенство βb × c = c × d; последнее эквивалентно
соотношению (βb + d) × c = 0. Таким образом векторы βb + d и c коллинеарны; отсюда
вытекает линейная зависимость векторов b, c, d вопреки условию леммы. Полученное
противоречие доказывает утверждение.
Теорема 4. Пусть последовательность векторов Nj образует полную цепочку.
Тогда последовательность векторов bj также является полной цепочкой.
Доказательство. Для доказательства достаточно установить, что каждая тройка векторов bj , bj+1 , bj+2 линейно независима. Ввиду обозначений (3.3) эта тройка
совпадает с векторами (3.4), если положить
a = Nj ,
b = Nj+1 ,
c = Nj+2 ,
d = Nj+3 .
Осталось воспользоваться леммой 3 и заметить, что j можно считать любым целым
числом.
Лемма 4. Пусть a, b, c, e, d, f — трехмерные векторы. Линейная независимость
векторов a × b, c × d, e × f эквивалентна неравенству
det(a, c, d) det(b, c, d)
det
= 0.
(3.6)
det(a, e, f) det(b, e, f)
7
Доказательство. Линейная независимость векторов a × b, c × d, e × f эквивалентна неравенству нулю определителя det(a × b, c × d, e × f). Рассматривая последний
как смешанное произведение векторов a × b, c × d, e × f, запишем его в виде векторного
произведения первых двух из них, скалярно умноженного на третий вектор (точкой
обозначено скалярное произведение векторов):
det(a × b, c × d, e × f) = [(a × b) × (c × d)] · (e × f).
Итак
[(a × b) × (c × d)] · (e × f) = 0.
(3.7)
Используя известную формулу для векторного произведения четырех векторов
x, y, z, u ∈ R3 ,
(x × y) × (z × u) = det(x, z, u)y − det(y, z, u)x
(3.8)
при x = a, y = b, z = c, u = d, видим, что формула (3.7) эквивалентна соотношению
[det(a, c, d)b − det(b, c, d)a)] · (e × f) = 0;
отсюда с помощью представления смешанного произведения в виде определителя, приходим к эквивалентной записи
det(a, c, d)det(b, e, f) − det(b, c, d)det(a, e, f) = 0.
Лемма доказана.
Теорема 5. Для того, чтобы последовательность векторов Nϕ образовывала полную цепочку, необходимо и достаточно выполнение условия
⎞
⎛
det(ϕj−1 , ϕj , ϕ j−1 )
det(ϕ j−1 , ϕj , ϕ j )
⎠ = 0
∀j ∈ Z,
(3.9)
det ⎝
det(ϕj−1 , ϕj+1 , ϕ j+1 ) det(ϕ j−1 , ϕj+1 , ϕ j+1 )
где для краткости применяются обозначения ϕj = ϕ(xj ) и ϕ j = ϕ (xj ).
Доказательство. Согласно определению полнота цепочки Nϕ эквивалентна линейной независимости векторов Nj−1 , Nj , Nj+1 для любого j ∈ Z, что согласно формуле (3.2) означает линейную независимость векторов ϕj × ϕ j−1 , ϕj × ϕ j , ϕj+1 × ϕ j+1 .
Полагая a = ϕj , b = ϕ j−1 , c = ϕj , d = ϕ j , e = ϕj+1 , f = ϕ j+1 и пользуясь леммой 4, придем к эквивалентности утверждения о линейной независимости векторов
Nj−1 , Nj , Nj+1 и соотношений (3.9).
Теорема 6. Пусть непрерывно дифференцируемая на (a, b) вектор-функция ϕ(t)
такова, что последовательность векторов {bj }j∈Z образует полную цепочку. Тогда
во множестве {X(A,ϕ) (M ) | A ∈ A} пространств минимальных (A, ϕ)-сплайнов второго порядка на подразделении M существует единственное пространство минимальных Bϕ -сплайнов.
Доказательство. Пусть {cj } — произвольная последовательность ненулевых чисел из R1 . Положим
(3.10)
aj = cj bj .
def
def
Согласно теореме 4 система векторов {bj } образует полную цепочку, а значит и {aj } —
тоже полная цепочка, так что решение аппроксимационных соотношений (1.4)–(1.5) существует, единственно и дается формулами (1.6) (или, что то же самое — формулами
8
(1.9)–(1.11)). Из теорем 2 и 3 следует, что сплайны ωj (t) продолжимы непрерывным
образом вместе со своей первой производной на интервал (a, b); таким образом, ωj (t) —
минимальные Bϕ -сплайны. Для доказательства единственности пространства минимальных Bϕ -сплайнов заметим, что согласно определению 3 минимальные Bϕ -сплайны
должны удовлетворять соотношениям (2.5) и (2.9). Это означает, что пространства
L{aj , aj+1 } и Γj должны совпадать для всех j ∈ Z; таким образом, выбор направлений векторов aj предопределен: они должны лежать на линии пересечения пространств
Γj−1 и Γj , т. е. с точностью до постоянных ненулевых множителей должны выражаться
формулой вида (3.3). Согласно теореме 4 полученная последовательность векторов aj
полная, и потому аппроксимационные соотношения (1.4)–(1.5) однозначно разрешимы,
а их решение ωj (t) получается по формулам (1.6); согласно теоремам 2 и 3 эти функции
непрерывно дифференцируемы. Нетрудно видеть, что выбор длины векторов aj влияет
лишь на нормировку соответствующих функций ωj , а на пространство X(A,ϕ) (M ), натягиваемое на эти функции, никакого влияния не оказывает. Итак, доказана единственность пространства минимальных Bϕ -сплайнов во множестве {X(A,ϕ) (M ) | A ∈ A} всех
пространств минимальных (A, ϕ)-сплайнов второго порядка на подразделении M .
Следствие. Если непрерывно дифференцируемая на (a, b) вектор-функция ϕ(t)
такова, что выполнено условие (3.9), то справедливо заключение теоремы 6.
Доказательство получается применением теорем 4 и 5.
Из формул (3.2)–(3.3) выводим
bj = (ϕj × ϕ j ) × (ϕj+1 × ϕ j+1 ).
Применяя формулу (3.8) при x = ϕj , y = ϕ j , z = ϕj+1 , u = ϕ j+1 , получим
def
def
def
def
bj = det(ϕj , ϕj+1 , ϕ j+1 )ϕ j − det(ϕ j , ϕj+1 , ϕ j+1 )ϕj .
(3.11)
Итак, установлено следующее утверждение.
Теорема 7. Пусть выполнены предположения теоремы 6. Тогда в качестве обB
разующих функций ωj ϕ пространства Bϕ -сплайнов можно взять функции, отысB
киваемые по формулам (1.9)–(1.11), где ωj = ωj ϕ и aj = cj bj , {cj }j∈Z — произвольная
последовательность чисел, отличных от нуля, а векторы bj определяются равенствами (3.11).
Замечание. Как было отмечено выше, выбор последовательности ненулевых чисел cj не меняет пространства Bϕ -сплайнов: для любых двух последовательностей
B
{cj,1 }j∈Z и {cj,2 }j∈Z ненулевых чисел соответствующие образующие функции ωj,1ϕ и
def
B
def
B
c
B
ωj,2ϕ отличаются лишь постоянным множителем, ωj,1ϕ = cj,2
ωj,2ϕ .
j,1
Рассмотрим три примера.
⎛ ⎞
1
1. Пусть ϕ(t) = ⎝ t ⎠; по формулам (3.11) находим полную цепочку векторов
t2
⎛
⎞
1
bj = 2(xj+1 − xj ) ⎝ xj+12+xj ⎠ .
xj+1 xj
Положим cj = 12 (xj+1 − xj )−1 ; после подстановки aj = cj bj в равенства (1.9)–(1.11)
получаем известный полиномиальный B-сплайн ωjB второй степени,
supp ωjB = [xj−1 , xj+2 ],
9
ωjB (t) =
(t − xj−1 )2
(xj − xj−1 )(xj+1 − xj−1 )
при
t ∈ [xj−1 , xj ),
ωjB (t) = (xj+1 − xj−1 )−1 (xj+1 − xj )−1 (xj+2 − xj )−1 ×
× (xj−1 − xj+1 − xj+2 + xj ) t2 − 2(xj xj−1 − xj+1 xj+2 ) t+
+ xj−1 xj xj+2 − xj−1 xj+1 xj+2 + xj−1 xj xj+1 − xj xj+1 xj+2 при t ∈ [xj , xj+1 ),
(t − xj+2 )2
при t ∈ [xj+1 , xj+2 ].
(xj+2 − xj+1 )(xj+2 − xj )
⎛
⎞
1
2. Возьмем теперь ϕ(t) = ⎝ sin t ⎠; предполагая, что
cos t
ωjB (t) =
xj+1 − xj < π
∀j ∈ Z,
по формулам (3.11) получаем полную цепочку векторов
Пусть cj = − 21 sin−1
⎛ xj+1 −xj ⎞
cos
xj+1 − xj ⎝ xj+12+xj ⎠
bj = −2sin
.
sin 2
2
x
+x
cos j+12 j
xj+1 −xj
2
. После подстановки aj = cj bj в равенства (1.9)–(1.11)
Bϕ
находим тригонометрический Bϕ -сплайн ωj
Bϕ
supp ωj
ωj ϕ (t) = sin2
B
t − x
j−1
2
sin−1
x
j+1
второго порядка,
= [xj−1 , xj+2 ],
− xj−1 −1 xj − xj−1 sin
2
2
(3.12)
при t ∈ [xj−1 , xj ),
(3.13)
x
x −x
1
j+1 + xj+2
j
j−1
− t cos
+
sin
=
2
2
2
xj−1 + xj xj+2 − xj+1
+ sin t −
cos
+
2
2
x
xj + xj−1 − xj+1 − xj+2
j+1 − xj
sin−1
sin−1 ×
+ sin
2
2
x
x
j+2 − xj
j+1 − xj−1
sin−1
при t ∈ [xj , xj+1 ), (3.14)
×
2
2
t − x
x
x
B
j+2
j+2 − xj
j+2 − xj+1
sin−1
sin−1
при t ∈ [xj+1 , xj+2 ].
ωj ϕ (t) = sin2
2
2
2
(3.15)
Bϕ
B
Аналогично B-сплайну ωj (t), функция ωj (t), задаваемая формулами (3.12)–
(3.15), непрерывно дифференцируема на вещественной оси, вогнута на интервалах
B
ωj ϕ (t)
10
(xj−1 , xj ) и (xj+1 , xj+2 ), выпукла на интервале (xj , xj+1 ), положительна на интервале (xj−1 , xj+2 ), а ее вторая производная имеет неустранимые разрывы первого рода в
точках xj−1 , xj , xj+1 , xj+2 .
⎛ ⎞
1
def
3. В третьем примере возьмем ϕ(t) = ⎝ et ⎠; тогда на равномерной сетке xj = jh, j ∈
e2t
B
Z, экспоненциальные Bϕ -сплайны с носителем supp ωj ϕ = [xj−1 , xj+2 ] могут быть
заданы выражениями
ωj ϕ (t) = (ejh − et+h )2
B
при t ∈ [xj−1 , xj ),
ωj ϕ (t) = 2ejh+t − e2(j+1)h + 2et+(j+2)h − e2t+h − e(2j+1)h − e2t
B
ωj ϕ (t) = (e(j+2)h − et )2 e−h
B
при t ∈ [xj , xj+1 ),
при t ∈ [xj+1 , xj+2 ].
Summary
I. G. Burova, Yu. K. Demjanovich. On splines of maximal smoothness.
Continuously differentiable splines with three intervals in support are considered. The conditions
of existence and uniqueness of spaces generated with discussed splines are established. Algorithms
for spline constructions and examples of their applications are suggested.
Литература
1. Стечкин С. Б., Субботин Ю. Н. Сплайны в вычислительной математике. М., 1976. 248 с.
2. Малоземов В. Н., Певный А. Б. Полиномиальные сплайны. Л., 1986. 120 с.
3. Schumaker L. L. On super splines and finite elements. SIAM J. Numer. Anal., 1989. Vol. 26.
P. 997–1005.
4. Buhmann M. D. Multiquadratic Prewavelets on Nonequally Spaced Knots in One Dimension.
Math. of Comput. 1995. Vol. 64. N 212. P. 1611–1625.
5. Калиткин Н.Н., Шляхов Н.М. B-сплайны произвольной степени // Доклады Акад.
наук. 1999. Т. 367. № 2.
6. Davydov O., Nurnberger G. Interpolation by C 1 splines of degree q ≥ 4 on triangulations //
J. Comput. and Appl. Math. 2000. Vol. 126. P. 159–183.
7. Бурова И. Г., Демьянович Ю. К. Теория минимальных сплайнов. СПб., 2000. 316 с.
8. Демьянович Ю. К. Калибровочное соотношение для B-сплайнов на неравномерной сетке.
Матем. модел. Т. 13. № 9. 2001. С. 98–100.
Статья поступила в редакцию 19 февраля 2004 г.
Документ
Категория
Без категории
Просмотров
4
Размер файла
237 Кб
Теги
гладкости, сплайнах, максимальной
1/--страниц
Пожаловаться на содержимое документа