Аппроксимация сингулярными вейвлетами

УДК 519.6

В. М. РОМАНЧАК

АППРОКСИМАЦИЯ СИНГУЛЯРНЫМИ ВЕЙВЛЕТАМИ

Задача аппроксимации является актуальной практически для любого инженерного исследования. В этой связи представляют интерес универсальные методы аппроксимации. В работе развивается метод непараметрической аппроксимации - метод сингулярных вейвлетов. Метод включает в себя эффективный численный алгоритм, основанный на суммировании рекуррентной последовательности функций. Универсальность алгоритма означает, что его можно применять для приближения одномерных и многомерных функций, в системах поддержки принятия решений, при обработке стохастической информации, распознавании образов, решении краевых задач.

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

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

Ключевые слова: вейвлет преобразование, окно Парзена-Розенблатта, непараметрическая аппроксимация, ядерная оценка Надарая-Ватсона.

Введение

Распространение методов непараметрической аппроксимации объясняется возможностью их применения для построения сложных математических моделей [1]. В прикладных работах используют аппроксимацию ядерными функциями [2], [3], [4], [5] и аппроксимацию вейвлетами [6], [7], [8]. В данной работе развивается метод сингулярных вейвлетов, в котором используется вейвлет преобразование с ядерными функциями.

Метод сингулярных вейвлетов был предложен и сформулирован нами в работах [9], [10]. Пусть у(х) - это базисный вейвлет [6] («маленькая волна», «всплеск»). В вейвлете варьируют значения параметра масштабирования а и параметра сдвига Ь:

ДО и вейвлет функции (1), которое называют вейвлет-преобразованием:

1 ~ (1; - Ь

Ж/(Ь,а) = -\ /а)у(-

а V а

Можно показать, что если функция у(х) в среднем равна нулю,

| у( t) dt = 0,

1 (t - Ь а V а

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

то в преобразовании (2) «малый всплеск» приводит к «маленькой волне», т. е. функция Ж/Ь, а) для малых а будет близка к нулю [7]. Если базисный вейвлет у(0 в среднем не равен нулю, то назовем такой вейвлет сингулярным. Если вейвлет является сингулярным («большой всплеск»), то преобразование Ж/Ь, а) может привести к «большой волне», т. е. функция Ж/Ь, а) не будет стремиться к нулю при малых а.

Аппроксимация сингулярными вейвлетами, основывается на регуляризации вейвлет преобразования (2) по формуле:

—оо

1 да (г - Ь w(f-f (Ь))(Ь,а)= -1 (f (г)-f (Ъ))у(-

Если вейвлет не является сингулярным, то регуляризованное вейвлет преобразование (4) совпадает с вейвлет преобразованием (2). Но для сингулярного вейвлета «большой всплеск» по-прежнему будет приводить к «маленькой волне», т.е. функция W(f-А(Ь))(Ь, а) для малых а будет близкой к нулю. В качестве вейвлета в преобразовании W(f -А(Ь))(Ь, а) можно взять дельта-образные функции, которые применяют при ядерной оценке регрессии [2], например вейвлетом может быть функция плотности стандартного нормального распределения. Тогда, если интеграл в выражении (4) заменить суммой и считать преобразование W(f — А(Ь))(Ь, а) достаточно малой величиной, получим непараметрическую ядерную оценку На-дарая-Ватсона [3], [4]:

f Ф):

п (х - ь пА (и

¿=1_Ч а

п (- ь ЕуН—

¿=1 I а

) <

Ч

1 + X2

Для дельта-вейвлета, регуляризация (4) равна разности вейвлет-преобразования и значения функции_ДЬ): W(f—f(Ь))(Ь, а) = Wf(Ь, а) -/Ь). Для классического вейвлета регуляризация (4) совпадет с вейвлет-преобразованием: Щ(А — А(Ь))(Ь, а) = ЩЦЬ, а). В работе [10] доказаны теоремы.

Теорема 1. Пусть у - базисный сингулярный вейвлет. Если функция у(Х) четная, у(Х) е Ь2, Ху(Х) е L1, тогда для любой непрерывной в точке X функции_Дх) из X2 (Я):

1 да да 1

f (и) = п! '"Г Щ (f - f (Ь)) f (Ь, а)у

С о —да а

X - Ь

Ъdа

где

причем

С <да.

где ¥(х) - преобразование Фурье для функций У(Х):

1

¥( х) =

| у(и)elхtdt.

Для ядерной оценки (5) существенно условие положительности ядра. Мы видим, что регуляризация вейвлет преобразования позволяет объединить теорию вейвлетов с ядерными оценками регрессии. Такое объединение названо нами методом сингулярных вейвлетов.

Сингулярный вейвлет

Определение. Пусть у(Х) - убывающая на бесконечности функция, причем такая, что

Теорема 2. Пусть _Дх) е Ь1, у(Х) — базисный дельта-вейвлет, тогда преобразования Щ(А — А(Ь))(Ъ, а) в каждой точке непрерывности функции А(Ь) при а —^ 0, а > 0 стремится к нулю:

W(f— №)(Ъ а) — 0.

Последовательность вейвлет-преобразований

Лемма. Если функция Ах) е Ь1 и непрерывна в точке х, то преобразование F(х) = W(f— А(х))(х, а) непрерывно в точке х и F(х) е Ь1, [10].

Введем последовательность регуляризован-ных вейвлет-преобразований F(х):

Ч — некоторая константа, ч > 0, для которой существует конечное среднее значение. Такую функцию будем называть базисным вейвлетом. Базисный вейвлет у(Х) равный нулю в среднем (условие (3)) будем называть классическим, а не равный нулю - сингулярным. Базисный сингулярный вейвлет, удовлетворяющий условию нормировки,

да

-да

будем называть дельта-вейвлетом.

Fk+1( х) = Fk (х) - WFk (х, ак):

где WFk (х, ак ) = — | Fk (и)у

(и - х >

лk -да

ч ^ ;

Ж

вейв-

лет преобразование, k = 0, 1, ..., К - 1, F0(х) =Ах) -начальная функция. Тогда справедлива следующая теорема.

Теорема 3. Для непрерывной в точке х функции Ах) существует разложение по формуле

к-1 , г

А

k=0

да

и

где ак- произвольная последовательность действительных чисел, ак > 0, к - номер преобразования, ЕК(х) = - ЕК-1(х))(х, аК-1) - остаточный член, ЕК(х) ^ 0, при аК-1 ^ 0, К - порядок аппроксимации.

Доказательство проиллюстрируем на примере разложения второго порядка, К = 2. В этом случае рекуррентные формулы (9) имеют вид

Е1( х) = Е 0( х) - ЖЕ 0( х, а0), Е 2( х) = Е 1( х) - ЖЕ1( х, а1).

Сложив эти равенства, получим

Е2

и

Ряд

1 да

ЖЕк (х,ак) = — | Ек ^)у

ак -да

Е ЖЕк (х, ак ), к=0

^ - х^

Л .

Доказательство. Запишем регуляризован-ное вейвлет-преобразование (9) в виде

да

Ек+1(х) = | (Ек (х) - Ек (х + аки))у(и)Ли,

где Е0(х) = /х), к = 0, 1, .... Тогда

Ек+1

да ,

Ек

/(х) = ЖЕ0 (х, а0) + ЖЕ1(х, а1) + Е2 (х).

Причем функции Е1(х), Е^х) - принадлежат пространству L1[A, 5] и непрерывны в точке х (на основании Леммы). Остаточный член Е2(х) можно сделать сколь угодно малым, подходящим выбором а1 на основании Теоремы 1. Для произвольного порядка К, формула доказывается аналогично. В случае К = 1 разложение (10) совпадает с оценкой регрессии Нада-рая-Ватсона.

Равномерная сходимость вейвлет-ряда

Пусть Ек(х) - последовательность вейвлет-преобразований (9) с начальной функцией Пх) = /х) и

Ек (х + аки + Ах) -Ек (х + ) )|у(и)|Ли.

В частном случае для к = 0 из неравенства

(14) и условия Липшица |/(х + Ах) - /х)|<А|Ах| и |/(х + а1и + Ах) -/х + а1м)| < А1Ах1, получим

да

-да

для положительного дельта-вейвлета

да I I | у( и ) Ли = 1 .

-да

Далее, для к =1 на основании (14) с учетом

(15), будет выполняться

Е 2

< 22 А Ах .

Аналогично в общем случае

Ек

<2к АI Ах|

Теперь для Ек+ 1(х) в формуле (13) с помо-

щью оценки (16), получим

к+1 да

Е (х) < 1 -да

будем называть вейвлет-рядом.

В формуле (10) значение функции/х) равно частичной сумме вейвлет-ряда (12) и остаточного члена. Рассмотрим, при каких условиях вейвлет-ряд (12) сходится равномерно.

Теорема 4. (Достаточное условие равномерной сходимости.) Пусть начальная функция, Е°(х) = /х), для ряда (12) удовлетворяет условию Липшица, /х) -/у)| < А|х -у|, х, у е R, А - постоянная и у(и) - положительный дельта-вейвлет, иу(и) е L1. Вейвлет-ряд (12) сходится равномерно для всех х е R, если ак = аoqk, ак > 0, к = 0, 1, -, где 0 < q < 1/2.

к к Е

у(и ) Ли <

к = 0, 1, 2, ..., и, следовательно,

Ек+1

< 2к а кС,

-да

1, ..., где 0 < q < 1/2, тогда ряд (12) сходится равномерно на основании (17), поскольку в этом случае ЕК+1(х) ^ 0. Аппроксимация дельта-вейвлетами (12) может служить обоснованием численного алгоритма дискретной аппроксимации.

—да

—да

Алгоритм аппроксимации

Пусть задан набор точек x, i = 0,1, ..., n, а также значения функции y в этих точках. Требуется построить функцию fix), проходящую близко к значениям y t в точках хг-, fx) « y h i = 1, ..., n.

Присваиваем начальные значения y t коэффициентам вейвлета нулевого порядка W0 :

W0 = yi, i = 1, ..., n.

Вычисляем коэффициенты регуляризован-ного вейвлет-преобразования, используя дискретный аналог формулы (9):

ZW k-1y

Wk = Wk-1 - -

j j

v «k-1 ;

Zy

k-1

к

ZWk-1y

fK (x) = ZX

k=1

V «k-1 ;

Zy

'к - x^

4-1

здесь k = 1, .... К - 1, Щ - значения коэффициентов вейвлета ^го порядка в точке х , г, ] = 1, ..., п, ak = а2-^ а - постоянная.

Восстанавливаем функцию АК(х) « Дх) во всех точках интервала [А, В], используя аналог формулы (10):

-0.5 0 0.5

Аппроксимация функции Рунге

по формуле (18) приведены в таблице (ввиду симметрии представлена только половина коэффициентов, г = 8, 9, ..., 16). Номер строки т, т = 1, 2, ..., 7, соответствует номеру итерации k = т - 1.

Коэффициенты вейвлетов

Пример.

В 1901 г. Рунге исследовал интерполяцию полиномами на отрезке [-1, 1] функции А(х) = 1/(1 + 25х2) при равномерном распределении узлов сетки и показал, что при бесконечном увеличении степени п интерполяционного полинома Рп последовательность Рп расходится на интервале [-1, 1]. Выполним квази-интерпо-ляцию функции Рунге А(х) методом сингулярных вейвлетов, равномерно распределив узлы интерполяции на промежутке [-1, 1]. Выберем базисный сингулярный вейвлет у(х) = е~х , хг = -1 + ¡И, г = 0, 1, ..., 16, h = 1/8, уг = Ах). Найденные значения коэффициентов вейвлетов k

1 0,72 0,39 0,22 0,14 0,09 0,07 0,05 0,04

0,72 0,44 0,11 -0,05 -0,13 -0,17 -0,18 -0,19 -0,19

0,68 0,40 0,08 -0,07 -0,13 -0,16 -0,16 -0,15 -0,15

0,50 0,24 -0,03 -0,12 -0,12 -0,09 -0,06 -0,04 -0,04

0,27 0,06 -0,09 -0,08 -0,04 -0,01 0,01 0,01 0

0,09 -0,01 -0,04 -0,01 0 0 0 0 0

0 0 0 0 0 0 0 0 0

Значения аппроксимирующей функции были рассчитаны по формуле (19). На рисунке

представлены график функции Рунге--А(х),

аппроксимирующей функции-----Ак(х) и • -

узлы интерполяции.

Выводы

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

ЛИТЕРАТУРА

1. Хардле, В. Прикладная непараметрическая регрессия: пер. с англ. /В. Хардле. М.: Мир, 1993. 349 с.

2. Parzen E. On estimation of a probability density function and mode / Ann. Math. Statistic. 1962. V. 33. No. 3. P. 10651076.

3. Watson, G. S. Smooth regression analysis / G. S. Watson // Sankhya. Ser. A. -1964. - V. 26, - P. 359-372

4. Надарая, Э. А. Об оценке регрессии / Э. А. Надарая // Теория вероятностей и ее применение. - 1964. Т. 9, № 1. - C. 157-159.

5. Деврой, Л. Непараметрическое оценивание плотности. L-1 подход: пер. с англ. / Люк Деврой, Ласло Дьерфию-М.: Мир, 1988. - 407 с.

6. Чуи, К. Введение в вейвлеты: пер. с англ. /К. Чуи - М.: Мир, 2001. - 412 с.

7. Добеши, И. Десять лекций по вейвлетам: пер. с англ. / И. Добеши. - Ижевск: НИЦ « Регулярная и хаотическая динамика «, 2001. - 464 с

8. Фрейзер, М. Введение в вэйвлеты в свете линейной алгебры: пер. с англ. / М. Фрейзер. - М.: БИНОМ: Лаборатория знаний, 2008. - 487 с.

9. Серенков, П. С. Система сбора данных о качестве как техническая основа функционирования эффективных систем менеджмента качества / П. С. Серенков, В. М. Романчак, В. Л. Соломахо // Доклады акад. наук Республики Беларусь. - 2006. - Т. 50, № 4. - С. 100-104.

10. Романчак, В. М. Аппроксимация экспертных оценок сингулярными вейвлетами / В. М., Романчак, П. М. Лап-по / Вестник Гродненского государственного университета. Серия 2: Математика. Физика. Информатика, вычислительная техника и управление/ Изд. Гродненский государственный университет имени Янки Купалы. - Гродно, 2017. - Т. 7, № 1. - С. 132-139.

REFERENCES

1. Hardle, W. Prikladnaja neparametricheskaja regressija. Applied nonparametric regression. Moscow, 1993, 349 p.

2. Parzen E. On estimation of a probability density function and mode // Ann. Math. Statistic. 1962. V. 33. No. 3. P. 1065-1076.

3. Watson G. S. Smooth regression analysis. Sankhya, Ser. A., 1964, vol. 26, pp. 359-372.

4. Nadaraya E. A. Ob ocenke regressii. About a regression assessment. Probability theory and its application,1964, vol. 9, no. 1, pp. 157-159.

5. Devroye, L. Neparametricheskoe ocenivanie plotnosti. L-1 podhod. Nonparametric Density Estimation: The L1. / Devroye, L. & L. Gyorfi. - Мoscow, 1988, 407 p.

6. Chui K. Vvedenie v vejvlety. Introduction in wavelet. Moscow, 2001, 412 p.

7. Daubechies I. Desjat' lekcij po vejvletam. Ten Lectures on Wavelets, Izhevsk, 2001. - 464 с

8. Frazier M. Vvedenie v vjejvlety v svete linejnoj algebry. An introduction to wavelet through linear algebra./ Moscow, 2008, 487 p.

9. Serenkov P. S., Ramanchak V. M., Solomakho V. L. Sistema sbora dannyh o kachestve kak tehnicheskaja osnova funkcionirovanija jeffektivnyh sistem menedzhmenta kachestva. System of collection of data on quality as technical basis of functioning of effective systems of quality management. Reports of the academician of sciences of Republic of Belarus, 2006, vol. 50, no. 4, pp. 100-104.

10. Ramanchak V. M., Lappo P. M. Approksimacija jekspertnyh ocenok singuljarnymi vejvletami. Approximation of expert estimates by singular wavelets. Bulletin of the Grodno State University. Series 2: Mathematics. Physics. Informatics, Computer Science and Management, 2017, vol. 7, no. 1, pp. 132-139.

Поступила После доработки Принята к печати

22.03.2018 14.05.2018 01.06.2018

Romanchak V. M. vmracer@yandex.by, Romanchak@bntu.by

The problem of approximation is relevant for most engineering applications. In this connection, the universal methods of approximation are of interest. The method of nonparametric approximation is developing in the paper - the method of singular wavelets. The method includes an effective numerical algorithm based on the summation of a recursive sequence offunctions. The universal algorithm of approximation makes it possible to apply it to approximate one-dimensional and multidimensional functions, in decision support systems, in the processing of stochastic information, pattern recognition, and solution of boundary-value problems.

The introduction explain the idea of the method of singular wavelets - to combine the theory of wavelets with the Nada-raya-Watson kernel regression estimator. Usually, Nadaraya-Watson kernel regression are considered as an example of nonparametric estimation. However, one parameter, the smoothing parameter, is still present in the traditional kernel regression algorithm. The choice of the optimal value of this parameter is a complex mathematical problem, and numerous studies have been devoted to this question. In the approximation by the method of singular wavelets, summation of Nadaraya-Watson kernel regression estimates with the smoothing parameter takes place, which solves the problem of the optimal choice of this parameter.

In the main part of the paper theorems are formulated that determine the properties of the regularized wavelet transform. Sufficient conditions for uniform convergence of the wavelet series are obtained for the first time. To illustrate the effectiveness of the numerical approximation algorithm, we consider an example of the quasi-interpolation of the Runge function by wavelets with a uniform distribution of interpolation nodes.

Keywords: Wavelet transform, the Parzen-Rosenblatt window method, nonparametric estimator, Nadaraya-Watson kernel regression

Романчак Василий Михайлович - доцент кафедры инженерной математики БНТУ, кандидат физ.мат. наук (1987), доцент (1991). Научные интересы в области обработки экспертных оценок и методов непараметрической аппроксимации (метод сингулярных вейвлетов). Опубликовано более 20 журнальных публикаций и монография.

Ramanchak Vasily Mikhaylovich is the associate professor of engineering mathematics of BNTU, the candidate of physical and mathematical sciences (1987), associate professor (1991). Scientific interests in the field of processing of expert estimates and methods of nonparametric approximation (method of singular wavelet). More than 20 journal publications and the monograph are published.