ВАРИАНТ ДВУМЕРНОГО ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ХААРА С УЗЛАМИ НА $\Pi_0$-СЕТКАХ

ISSN 2074-1863 Уфимский математический журнал. Том 5. № 1 (2013). С. 56-62.
УДК 517.518.87
ВАРИАНТ ДВУМЕРНОГО ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ХААРА С УЗЛАМИ НА П0-СЕТКАХ
К.А. КИРИЛЛОВ, М.В. НОСКОВ
Аннотация. Предложен вариант двумерного дискретного преобразования Хаара с 2d узлами, образующими По-сетки, связанный с треугольными частичными суммами ряда Фурье-Хаара заданной функции. Вследствие структуры По-сеток вычисление коэффициентов этого дискретного преобразования основано на кубатурной формуле с 2d узлами, точной для полиномов Хаара степеней, не превосходящих D, благодаря чему все коэффициенты построенного преобразования совпадают с коэффици-
ентами Фурье-Хаара Cml’ml для функций, являющихся полиномами Хаара степеней не выше D — max{mi,m2} (0 ^ Ш\ + Ш2 ^ d, где d ^ D). Стандартное двумерное
дискретное преобразование Хаара с 2d узлами таким свойством не обладает.
Ключевые слова: кубатурные формулы, точные для полиномов Хаара, дискретное преобразование Хаара, По-сетки.
1. Введение
Существенный интерес в вычислительной математике вызывает задача применения ку-батурных формул, точных на некоторой конечной ортонормированной системе функций, к дискретному преобразованию Фурье по этой системе. Так, приложения кубатурных формул высокой тригонометрической точности к дискретному преобразованию Фурье по тригонометрической системе рассмотрены в [1].
Идея использования треугольных частичных сумм ряда Фурье заданной функции при построении дискретного преобразования Фурье, реализованная в статье [1] для случая тригонометрической системы, в настоящей работе применена к построению варианта двумерного дискретного преобразования Хаара с узлами, образующими П0-сетки, являющиеся сетками, узлы которых распределены достаточно равномерно - если П0-сетка образована 2d узлами, то каждый двоичный прямоугольник площади 2-D содержит ровно один ее узел. Благодаря указанной структуре П0-сеток, вычисление коэффициентов построенного в данной работе дискретного преобразования основано на кубатурной формуле с 2d узлами, точной для полиномов Хаара степеней, не превосходящих D, вследствие чего для любой функции, являющейся полиномом Хаара степени, не выше D — max{m1,m2} (0 ^ m1 + m2 ^ d, где d ^ D), все коэффициенты ЛЦ!’^1 построенного преобразования равны соответствующим коэффициентам Фурье-Хаара Cmi ’ml. Последнее свойство отсутствует у стандартного двумерного дискретного преобразования Хаара, связанного с прямоугольными частичными суммами ряда Фурье-Хаара функции и основанного на кубатурной формуле с прямоугольной сеткой узлов, для которой степень точности Ха-ара равна M = min{M1, M2}, где 2Ml и 2Ml - число индексов по каждой компоненте при построении узлов кубатурной формулы, M1 + M2 = D.
K.A. Kirillov, M.V. Noskov, A version of discrete Haar transform with nodes of По-grids.
© Кириллов К.А., Носков М.В. 2013.
Поступила 20 декабря 2011 г.
2. Основные определения и вспомогательные утверждения
В настоящей работе используется оригинальное определение функцийхт,^ (х), введенное А.Хааром [2], отличное от определения этих функций из [3] в их точках разрыва.
Двоичными промежутками /т]- назовем промежутки с концами в точках (7 — 1)/2т-1, 7/2т-1 (т =1, 2,..., 7 = 1, 2,..., 2т-1). Если левый конец двоичного промежутка сов-
падает с 0, то будем считать этот промежуток замкнутым слева, если правый конец совпадает с 1 - замкнутым справа. Остальные двоичные промежутки считаются открытыми. Левую и правую половины /т]- (без середины этого двоичного промежутка) будем обозначать I— и /+ • соответственно. т,] т,]
Двоичными прямоугольниками назовем множества /ть]1 х 1т2,]2, замкнутыми двоичными прямоугольниками - замыкания этих множеств, тп = 1, 2,..., 7п = 1, 2,... , 2тп-1,
п = 1, 2.
Система функций Хаара строится группами: группа номер т содержит 2т-1 функций Хт,] (х), где т =1, 2,..., 7 = 1, 2,..., 2т-1. Функции Хаара Хт,з (х) определим следую-
щим образом:
nm-1 ,
2 2 при x Є l,
m — 1
m,ji
Xm,j (x) = <
m —1 I
—2 2 при x G /m,j,
0 при x G [0,1] \ lm,j,
2 [Xm,j (x — 0) + Xm,j (x + 0)], если X — внутренняя
точка разрыва,
1т,] = [2]—], т = 1, 2,... , 7 = 1, 2,... , 2т-1. В систему функций Хаара включают также функцию Ход (х) = 1, которую отнесем к нулевой группе.
В двумерном случае полиномами Хаара степени d будем называть линейные комбинации с вещественными коэффициентами функцийхт1,]г (х1)хт2,]2 (х2), называемых мономами Хаара (т1 + т2 - степень монома), т1 + т2 = 0,1,... , d, ]п Е Лтп,
л _ ) {1,..., 2тп-1}, если тп > 0,
Лт
{1}, если = 0, v !
n = 1, 2, при этом хотя бы один из коэффициентов при мономах Хаара степени d должен быть отличен от нуля.
Пусть функция f (xi,x2) определена и суммируема на [0,1]2. Будем говорить, что куба-турная формула
11 N
1 [f] И f (x1, x2) dx1 dx2 ~ ^ Cif (x1i),x2i}) = Q[f] (2)
0 0 i=1
с узлами (х^х«) Е [0,1]2 и коэффициентами при узлах С € К (г =1, 2,... , N) обладает d-свойством Хаара, или просто - d-свойством, если она точна для любого полинома Хаара Р(х1,х2) степени, не превосходящей d, т. е.
3[Р ] = I [Р ].
Кубатурную формулу (2) будем называть формулой степени точности d Хаара, или d-точной, если она обладает d-свойством, но (d + 1)-свойством не обладает.
Имеет место
Предложение 1. [4] Если кубатурная формула (2) обладает d-свойст,вом, то число ее узлов N удовлетворяет неравенству
N ^ 2^-1 + 1.
В [3] используется определение функций Хаара, отличное от определения этих функций, введенного в [2], - в [3] функции Хаара считаются непрерывными справа в точках разрыва, в связи с чем двоичные промежутки /mj (m = 1, 2,..., j = 1, 2,..., 2m-1) определяются следующим образом:
{[0,1], если m =1, j = 1,
[ 2m—г, m-т), если m G N \ {1}, j G {1, 2,..., 2m-1 - 1}, (3)
[1 - 2m—i, 1], если m G N \ {1}, j = 2m-1.
Будем говорить, что 2d точек единичного квадрата [0,1]1 образуют П0-сетку, если каждый двоичный прямоугольник 1mi j х /m2,j2 площади 2-d (m1 + m2 = d + 2, jn =1, 2,... , 2mn-1, n = 1, 2), являющийся декартавым произведением двоичных промежутков, определенных согласно (3), содержит ровно одну из этих точек.
В [5] показано, что существуют функции Km,j (x), являющиеся линейными комбинациями функций Хаара групп номер 0, 1, . . . , m, которые удовлетворяют равенству
i2m при x G m+1j,
2m-1 при x G 1m+1j \ m+1 j, (4)
0 при x G [0, 1] \ 1m+1,j,
m = 0,1, 2,..., j = 1, 2,..., 2m.
Функции Kmi,j1 (x1)Km2,j2(x2) будем называть к-мономами степени d, где m1 + m2 = d, jra = 1, 2,..., 2m", n =1,2.
Имеет место
Предложение 2. [4] Кубатурная формула (2) обладает d-свойством, тогда и только тогда, когда она точна для всех к-мономов степени d.
Замечание 1. Из равенства (4) следует, что каждый замкнутый двоичный прямоугольник площади 2-d является носителем некоторого к-монома степени d, именно:
1m, + 1,ji х 1m2+1,j2 suPP{Kmi,ji (x1) кт2 ,j2 (x2) }, mn 0, 1, 2, . . ., jn 1, 2,..., 2 n , n 1, 2.
Докажем
Предложение 3. Если Kd(x1,x1) - произвольный к-моном степени d, то
1 1
I[Kd] = JJ Kd(x1,xi) dx1 dxi = 1. (5)
00
Доказательство. Из соотношения (4) следует, что Kd(x1 ,x2) = 2d во внутренних точках множества supp {Kd}. Учитывая, что supp {Kd} является двоичным прямоугольником площади 2-d (замечание 1), приходим к равенству (5). Предложение доказано.
Имеет место
Предложение 4. [4] В точках непрерывности функции Хаара Xmj (x) (m = 1, 2,..., j = 1,... , 2m-1) имеет место равенство:
Xmj (x) = кт— 1 j (x). (6)
Всюду, за исключением точек, в которых функции Xk,i(x) и Xmj(x) одновременно терпят
разрыв (если такие точки существуют), произведение этих функций
{k — i , v 7 7
2^Xm,j(x), если, 1m,j ^ l-^,
-2k—iXm,j(x), если, Zmj ^ /+^, (7)
0 в остальных случаях,
где m ^ k, i = j при m = k.
Из предложения 4 следует
Предложение 5. Всюду, за исключением точек, в которых полиномы Хаара Р(х1; х2), Л(х1;х2) степеней, не превосходящих д, одновременно терпят разрыв (если такие точки существуют), функция ^(х1;х2) = Р(х1;х2)Д(х1;х2) есть полином Хаара степени, не превосходящей 2д.
3. Стандартный метод дискретного преобразования Хаара
Пусть f (xi,x2) - функция, определенная и суммируемая на [0,1]2, допускающая разложение в абсолютно сходящийся ряд Фурье - Хаара:
2 ОО
f(xi,x2cmi’,m2xmijo^xmjы, (8)
n=1 m„=0 jn €Лтп
где Лтп определяется равенством (1), n = 1, 2.
При стандартном двумерном дискретном преобразовании Хаара устанавливается взаимно однозначное соответствие между последовательностью значений функции f (x1,x2) в узлах (ж1г),ж2г)) G [0,1]2 (i = 1, 2,... , 2D) и множеством коэффициентов этого преобразования Й (mn = 0,1,..., Mn, G Лтп, n = 1, 2, M1 + M2 = D) так, что полином
Хаара
2 M„
H (Xi,X2) = EE E Am i , m2
Xmi,ji (x1)Xm2,j2 (x2) (9)
n=1 m„=0 j„eЛm„
восстанавливает функцию f (x1,x2) в указанных узлах:
H(ж1г), ж2г)) = f (ж1г), ж2г)), i = 1, 2,..., 2d;
при этом число Ami’,m2 есть кубатурная сумма в кубатурной формуле
1 1
= ii f (x1,X2)Xmi,ji (X1)xm2,j2 Ы d^1 dx2 «
0 0
2
D
:io)
2 ”E f (x<l‘>,x2‘>)Xmi.,1 (x<l‘))Xm2,)2 (x2‘>) = Ami;i2>i
i= l
т. е. приближенное значение коэффициента Фурье - Хаара Cmim функции f (x 1,x2), mn = 0,1,... , Mn, G Лтп, n =1, 2. Узлы (x 1г), х2г)) (i = 1, 2,... , 2D), в которых вычисляются значения функции f (x 1,x2), считаются принадлежащими прямоугольной сетке
|((2i 1 - 1)2-Mi- 1, (2i2 - 1)2-M2-1) : in = 1, 2,..., 2Mn, n =1, 2}.
Таким образом, в соответствии с (9) стандартный метод двумерного дискретного преобразования Хаара предполагает множество индексов m 1,m2 таковым, что
2
S (x1,x2) = ЕЕ Е cmijm Xmi,ji (x1)xm,2,j2 (x2) (11)
n=1 mn jn еЛт„
есть прямоугольная частичная сумма ряда (8) (mn в сумме из правой части (11) принимает значения 0,1,..., Mn, n =1, 2), а вычисление приближенных значений коэффициентов
Фурье - Хаара по формуле (10) проводится на основе кубатурной формулы
1 1
I [f ] = И f (x1,X2) dx1 dx2 w
0 0 (12)
f ((2i1 - 1)2-Mi-1, (2i2 - 1)2-M2-1) = Qf],
ii = 1 2 = 1
являющейся декартовым произведением двух квадратурных формул с 2Mi и 2M2 узлами.
Предложение 6. Степень точности Хаара кубатурной формулы (12) равна M = min{M1, M2}.
Доказательство. Каждому замкнутому двоичному прямоугольнику площади 2-M принадлежат ровно 2max{Mi,M2} узлов кубатурной формулы (12), причем все эти узлы являются его внутренними точками. Тогда в соответствии с замечанием 1 и равенствами (4), (5) для каждого к-монома Km(x1 ,x2) степени M имеем:
Q1[Km] = 2-Mi-M2 x 2max{Mi’M2> x 2min{Mi’M2> = 1 = I [Km].
В силу предложения 2 отсюда следует, что кубатурная формула (12) обладает M-свойством. Однако (M + 1)-свойством она не обладает, так как в случае M = M1 не точна, например, для к-монома км+1,1(x1), а в случае M = M2 - для км+1;1(х2). Таким образом, степень точности Хаара формулы (12) равна M. Предложение доказано.
Из предложений 5, 6 следует, что при условии m1 + m2 ^ M для коэффициентов Фурье
- Хаара функций f (x1,x2), являющихся полиномами Хаара степеней, не превосходящих M - max{m1 ,m2}, в приближенном равенстве (10) имеет место точное равенство
A (ji ,j2) = c(ji,j2) j 1 л n = 12 (13)
Ami,m2 = cmbm2, G Лтп , n =1 ,2 ,
а если m1 + m2 > M, то выполнение равенства (13) нельзя гарантировать даже для f (x1,x2) = const ни при каких значениях индексов m1,m2.
4. Дискретное преобразование Хаара с узлами, образующими П0-сетки
Рассматриваемый вариант дискретного преобразования Хаара с 2D узлами связан с треугольной частичной суммой ряда (8), т. е. с суммой (11), у которой нижние индексы m1, m2 входящих в нее коэффициентов ряда Фурье - Хаара удовлетворяют условию
m1 + m2 ^ d, (14)
где d ^ D - некоторое фиксированное натуральное число. Вычисление коэффициентов Ami,mm. (m1 + m2 ^ d, G Л^, n = 1, 2) данного дискретного преобразования проводится
по формулам (10), при этом считается, что узлы (х1г),х2г)) G [0,1]2 (i = 1,..., 2D) не
лежат на границах двоичных прямоугольников /mi,ji x Zm2,j2 площади 2-D (m1 + m2 = D + 2) и образуют П0-сетку. Таким образом, вычисление коэффициентов Ami,,m)2 основано на кубатурной формуле
1 1 2л
f (Х1,Х2) dx1 dx2 W 2-D ^ f (х(1г),х2г)) = Q2[f] (15)
=1
с вышеуказанным расположением узлов.
Предложение 7. Степень точности Хаара формулы (15) равна D.
2Mi 2^2
2-mi-m2 ^ у2
Доказательство. Каждому замкнутому двоичному прямоугольнику площади 2-Д принадлежит ровно 1 узел кубатурной формулы (15), который является его внутренней точкой. Тогда в соответствии с замечанием 1 и равенствами (4), (5) для каждого к-монома (х1,х2) степени Д
^[Кд ] = 1 = I [Кд ].
В силу предложения 2 отсюда следует, что кубатурная формула (15) обладает Д-свойством. Однако (Д + 1)-свойством она не обладает, так как число узлов любой кубатурной формулы, обладающей (Д + 1)-свойством, не меньше, чем 2д + 1 (предложение 1). Таким образом, степень точности Хаара формулы (15) равна Д. Предложение доказано.
Из предложений 5, 7 следует, что в приближенном равенстве (10) имеет место точное равенство (13) для коэффициентов Фурье - Хаара функций f (х1,х2), являющихся полиномами Хаара степеней, не превосходящих Д — тах{т1,т2}.
Число коэффициентов Фурье - Хаара, нижние индексы которых удовлетворяют неравенству (14), обозначим через N(д). Указанное число находится по формуле:
N (д) = 2^(0.5 д +1). (16)
Значение параметра д в неравенстве (14) будем выбирать следующим образом:
д = тах{р е N :2Р(0.5р + 1) ^ 2д}. (17)
Предложение 8. Для каждого Д е N существует единственное представление вида
В = 2Г+1 + г + 5 — 1, где в = 0,1,..., 2Г+1, г = 0,1, 2,... (18)
Значение д, удовлетворяющее равенству (17), находится по формуле
д =2Г+1 + 8 — 2 = Б — г — 1, (19)
где г, в - значения параметров в представлении (18) соответствующего числа Д.
Доказательство. При фиксированном г е N и {0}
Дг = {2Г+1 + г + в — 1 : в = 0,1,... , 2Г+1}
есть множество натуральных чисел отрезка [2Г+1 + г — 1, 2Г+2 + г — 1], причем различным значениям в е {0,1,..., 2Г+1} соответствуют различные натуральные числа этого отрезка. Дг+1 есть множество натуральных чисел отрезка [2Г+2 + г, 2Г+3 + г], не пересекающегося с [2Г+1 + г — 1, 2Г+2 + г — 1]. Следовательно, различным упорядоченным парам (г, в) соответствуют различные значения 2Г+1 + г + в — 1 (в = 0,1,..., 2Г+1, г = 0,1, 2,...), и тогда представление (18) единственно для тех значений Д, для которых оно существует. А так как
ГО ОО
у Дг = у {[2Г+1 + г — 1, 2Г+2 + г — 1] п N = N
г=0 г=0
то существует оно для любого Д е N.
Докажем теперь, что значение д, найденное по формуле (19), удовлетворяет условию (17).
Действительно, в соответствии с (16)
N(2Г+1 + в — 2) = N(Д — г — 1) = 2д-1 + 2д-г-2в ^ 2д, так как в ^ 2Г+1. В то же время
N(2Г+1 + в — 1) = N(Д — г) = 2д + 2д-г-1(в + 1) > 2д.
Предложение доказано.
Замечание 2. Если значение d найдено по формуле (19), то N(d) = 2D только в случае s = 2r+1, т. е. для D = 2r+2 + r — 1, r = 0,1, 2,... В случае s = 0 (D = 2r+1 + r — 1, r = 0,1, 2,...) N(d) = 2D-1, а случае 0 < s < 2r+1 величина N(d)/2D G (0.5,1) и увеличивается с ростом s.
Таким образом, при D = 2r+2 + r — 1, r = 0,1, 2,..., в треугольной частичной сумме (11), содержащей мономы Хаара Xmui (x1)xm2j2 (x2) степеней не выше d, меньше слагаемых, чем в соответствующей прямоугольной частичной сумме, включающей мономы Хаара, для которых mn ^ Mn, n = 1, 2, M1 + M2 = D. Однако, учитывая стремление к нулю коэффициентов Cmim при увеличении m1 + m2, можно ожидать, что качество предлагаемого варианта дискретного преобразования Хаара не хуже, чем при использовании стандартной схемы.
В то же время предложенный в настоящей работе вариант дискретного преобразования Хаара обладает некоторыми преимуществами по сравнению со стандартным преобразованием. Во-первых, при том же числе узлов, что и в стандартном преобразовании, расширяется множество функций f (x1,x2), для коэффициентов которых имеет место равенство (13), причем в отличии от стандартного преобразования все коэффициенты Amim совпадают с соответствующими коэффициентами Фурье-Хаара с^гl’rm-i для полиномов Хаара первых нескольких степеней. Во-вторых, уменьшение числа слагаемых в частичной сумме (11) приводит к уменьшению объема вычислений при аппроксимации функции указанной частичной суммой, в которой вместо коэффициентов Фурье-Хаара cmim заданной функции берутся соответствующие значения Ami'm ~ Cmlm.
СПИСОК ЛИТЕРАТУРЫ
1. Кашкин В.Б., Носков М.В., Осипов Н.Н. Вариант дискретного преобразования Фурье с узлами на параллелепипедальных сетках // Журнал вычислительной математики и математической физики. Т. 41. 2001. № 3. С. 355-359.
2. A. Haar Zur Theorie der orthogonalen Funktionensysteme // Math. Ann. 1910. Vol. 69. P. 331-371.
3. Соболь И.М. Многомерные квадратурные формулы и функции Хаара. М.: Наука, 1969. 288 с.
4. M.V. Noskov, K.A. Kirillov Minimal cubature formulas exact for Haar polynomials // Journal of Approximation Theory. Vol. 162. Issue 3. March 2010. P. 615-627.
5. Кириллов К.А., Носков М.В. Минимальные квадратурные формулы, точные для полиномов Хаара // Журнал вычислительной математики и математической физики. 2002. Т. 42. № 6. С. 791-799.
Кирилл Анатольевич Кириллов,
Сибирский федеральный университет, ул. Киренского, 26,
660074, г. Красноярск, Россия E-mail: KKirillov@rambler.ru
Михаил Валерианович Носков,
Сибирский федеральный университет, ул. Киренского, 26,
660074, г. Красноярск, Россия E-mail: MVNoskov@yandex.ru