Многомерная аппроксимация функциями специального вида

Многомерная аппроксимация — сложная и мало разработанная проблема. К ней относится, в частности, задача аппроксимации функции многих переменных суммой произведений функций, каждая из которых зависит лишь от одной из переменных. Аппроксимация такого вида нашла свое применение в проблеме «сжатия» информации. Например, при численном решении многомерных задач, при их реализации на ЭВМ большие трудности возникают в связи с использованием в качестве исходных данных или в качестве полученного результата функции многих переменных. Объем таблиц таких функций обычно очень большой и результат из-за огромного количества материала трудно обозрим. Один из возможных способов преодоления возникающих здесь затруднений состоит в црименении аппроксимации рассматриваемого вида. Аппроксимация функции многих переменных суммой произведений функций одной переменной находит свое применение в вопросах повышения эффективности систем передачи информации, в теории обработки изображений [25,36,37], в задачах распознования образов, а также при численном решении некоторых дифференциальных и интегральных уравнений [31]. В работе [5], например, приведены результаты применения такой аппроксимации к задачам сжатия данных и фильтрации сильно защум-ленных сигналов.

Для функции двух переменных задача ставится следующим образом. Пусть непрерывная функция | (и, я*) задана на II «V, где 11 и V — некоторые метрические компакты. Зафиксируем некоторое целое число 1. Требуется найти такие системы непрерывных функций заданных на V, где. ? 1 ъ, которые решают следующую задачу.

Решение поставленной задачи тесно связано с тем какая норма используется в формуле (I). Исследованию такой задачи посвящено много работ, например, [8-И, 20, 26−28, 31−35, 38−47] .

Наиболее полные результаты получены для задачи (I) в норме пространства Lj. По-видимому, впервые рассмотрел эту задачу Е. Шмидт в работе [34], опубликованной еще в 1907 году. Наиболее важные результаты для решения указанной задачи были получены М.Р.Шура-Бурой в работе [28] и В. А. Даугавет в работах [б, 7, 9]. Алгоритм решения дискретного варианта задачи (I) в норме пространства ^ описан в работе [12] на языке АЛГОЛ-бО.

В диссертации рассматривается задача (I) в норме пространства С, т. е.

UxV 1 т 1.

Самостоятельный интерес задача (2) представляет в дискретном случае, когда компакты U и V состоят из конечного числа точек, т. е. Ue {u^-u^., гдж^, Vе ., .

Тогда задачу (2) можно рассматривать как задачу цриближения заданной матрицы V порядка щ * п произведением двух матриц X и «Y, где X имеет порядок, a Y — .

Обозначив llFlI = 'wax F [i>j]| «задачу (2) в дискретном ialuYri 1 l VI варианте можно записать в виде.

УгСХ.^ИР-Х-УЦ".-* tni", (3) где)0(Хг — множество пар матриц «имеющих указанный выше порядок.

Заметим, что задача (3) относится к нелинейным задачам че-бышевского приближения, для которых существует хорошо разработанная альтернансная теория [13, 17]. Однако, црименение этой теории не дает возможности получить приемлимые результаты, особенно в построении достаточных условий оптимальности. Специфика рассматриваемой задачи требует иццивидуального подхода к ее исследованию.

Теоретические основы для решения задач (2) и (3) были впервые даны В. А. Даугавет в работах [8−10]. В этих работах были выведены некоторые необходимые и достаточные условия локального минимума функции ^(ХХ) • Было Д 9,110 понятие стационарной пары для задачи (3) и выведены необходимые и достаточные условия стационарности. Позже эти же условия стационарности были получены К. Зентак в [42−45]. В работах [9, 1С)] В. А. Даугавет вводит понятие двумерного альтернанса и показывает, что для невырожденного случая существование двумерного альтернанса является необходимым условием локального минимума для задачи (3). Относительно достаточных условий оптимальности доказано лишь, что наличие квадратного альтернанса у пары означает, что эта пара является точкой локального минимума функции •.

Наиболее полные результаты для задачи (3) получены при г = 1 в работе [б]. В этой работе кроме двумерного альтернанса вводится понятие вырожденного одномерного альтернанса. Это позволило необходимые условия локального минимума функции приблизить к достаточным условиям.

В работах [9, II] предложен алгоритм решения задачи (3). При г * 1 в работе [в! доказана сходимость этого алгоритма к стационарной точке, а при приведен пример [9, 10|, в котором предложенный алгоритм приводит к нестационарной точке. Однако этот алгоритм нашел широкое применение и будет использоваться в дальнейшем, так как во многих численных экспериментах он приводит не только к стационарной точке, но и к решению задачи.

Остановимся теперь на вопросе существования решения задач (2) и (3). Нетрудно показать, что задача (3) всегда разрешима. Нельзя сделать аналогичный вывод о разрешимости задачи (2), что было показано в работе [32]. Таким образом, задача (2) может и не иметь решения в пространстве непрерывных функций. Однако заметим, что в работе [27] доказано существование оптимальных систем X и для любых ограниченных на компакте функций «если решение искать среди функций не обязательно непрерывных, но удовлетворяющих некоторым дополнительным условиям.

Большое внимание в литературе уделялось и уделяется задаче приближения функции двух переменных суммой функций одной переменной, т. е. задаче тчсхХ I 4 ЭьМ — НОЛ I (4Л.

Основные теоретические результаты для этой задачи даны Ю.П.Оф-маном, М.-Б.А.Бабаевым, С. Я. Хавинсоном и В. П. Моторным в работах [19, 2−4, 24, 18]. Укажем на связь решения задачи (4) с решением задачи (2) при. Допустим, что решением задачи (2) для некоторой функции 4 (и (0.) являются функции одной переменной, а: г (У), «» такие что осг (11)=1 и. Тогда и являются решением задачи (4), поэтому теоретические результаты, полученные для задачи (4), в какой-то мере могут быть использованы для задачи (2).

В работах [26, 27] была сделана попытка получить теорему харак-теризации решения задачи (2) аналогичную теореме характеризации решения задачи (4) [24]. Однако эта попытка оказалась неудачной. В диссертации (см. § 6) приведены контрпримеры.

Диссертация состоит из введения и десяти параграфов.

1. Ахиезер Н. И. Лекции по теории аппроксимации. — М., Наука, 1965.

2. Бабаев М.-Б.А. О цриближении многочленов двух переменных суммой функций одной переменной. Изв. АН Аз. ССР, сер. физ.-мат. и техн. наук, № 6,1962, с.25−39.

3. Бабаев М.-Б.А. О наилучшем приближении функций многих переменных суммами функций одной переменной в обобщенном пространстве Лебега. В сб.: Исследования по теории дифференциальных уравнений и теории функций, Баку, 1965, с.11−24.

4. Бабаев М.-Б.А. О единственности наилучшей приближающей функции при приближении функций многих переменных суммами функций одной переменной в обобщенном пространстве Лебега. -Изв. АН Аз. ССР, сер. физ.-мат. и техн. наук, № 3, 1965, с.8−14.

5. Баглай Р. Д., Смирнов К. К. К обработке двумерных сигналов на ЭВМ. ЖВМ и Ш, 15, «1, 1975, с.241−248.

6. Даугавет В. А. Один практический прием приближения функции многих переменных. В сб.: Методы вычислений, вып. 6, Изд-во ЛГУ, 1970, с.3−8.

7. Даугавет В. А. Об одном варианте ступенчатого степенного метода для отыскания нескольких первых собственных значений симметричной матрицы. ШВМ и Ш, 8, № 1, 1968, с.158−165.

8. Даугавет В. А. О равномерном приближении функции двух переменных, заданной таблично, цроизведением функций одной переменной. ЖВМ и М$, II, № 2, 1971, с.289−303.

9. Даугавет В. А. Одна задача аппроксимации функции двух переменных. Автореф. канд. дис., Л., 1972, 8с.

10. Даугавет В. А. Приближение функции двух переменных суммой цроизведений функций одной переменной. В сб.: Методы вычислений, вып. 12, Изд-во ЛГУ, 1981, с.174−186.

11. Даугавет В. А. Равномерное приближение матрицы суммой произведений векторов. В сб.: Алгол-процедуры, вып. 9, Л., 1973, с.5−7.

12. Даугавет В. А. Приближение матрицы суммой произведений векторов в метрике iz. В сб.: Алгол-процедуры, вып. 9, Л., 1973, с.3−5.

13. Даугавет В. А., Малоземов В. Н. Нелинейные задачи аппроксимации. В кн.: Современное состояние теории исследования операций, M., 1979, с.336−363.

14. Даугавет В. А., Сазонова Л. В. Двумерная чебышевская интерполяция. Вестн. Ленингр. ун-та, вып. 2, F7, 1984, с.89−91.

15. Даугавет В. А., Сазонова Л. В. Задача сокращения объема двумерных таблиц. Тезисы доклада III симпозиума по методам решения нелинейных уравнений и задач оптимизации., Таллин, 1984.

16. Даугавет И. К.

Введение

в теорию приближения функций.,-Л., Изд-во Ленингр. ун-та, 1977.

17. Малоземов В. Н., Певный А. Б. Альтернансные свойства решения нелинейных минимаксных задач. ДАН СССР, т. 212, № 1, 1973, с.37−39.

18. Моторный В. П. К вопросу о наилучшем приближении функций двух переменных функциями вида ^(х) + Y (^). В сб.: Исследования по современным проблемам конструктивной теории функций., Баку, 1965, с.66−73.

19. Офман Ю. П. 0 наилучшем цриближении функции двух переменных функциями вида ^(ху Y ('ty). Изв. АН СССР, сер. матем., т.25, 1961, с.232−252.

20. Поспелов B.B. О приближении функций нескольких переменных произведениями функций одного переменного. Препринт. Ин. прикл. математ. АН СССР, № 32, 1978.

21. Сазонова Л. В. Замечание по поводу одной задачи аппроксимации функции двух переменных. В сб.: Методы вычислений., вып. 12, Л., 1981, с.186−189.

22. Сазонова JI.B. Аппроксимация функции двух переменных суммой произведений функций одной переменной. В отчете о НИР: Разработка методов и алгоритмов синтеза нелинейных систем. Инв. № 0284.36 374, НИИМ, ЛГУ им. А. А. Дцанова, Л., 1983, с.32−36, 0.39−45.

23. Сазонова Л. В. Достаточный признак оптимальности в задаче приближения функции двух переменных суммой произведений функций одной переменной. Л., 1984 — Рукопись представлена Ленингр. ун-том. Деп. в ВИНИТИ 31 мая 1984 г., № 3555−84.

24. Хавинсон С. Я. Чебышевская теорема для цриближения функции двух переменных суммами. Изв. АН СССР, сер. мат., 33, № 3, 1969, с.650−666.

25. Хуанг, Шрейбер, Третьяк. Обработка изображений. В сб.: Обработка изображений при помощи цифровых вычислительных машин. — Мир, 1973, с. 17−47.

26. Церетели A.C. Чебышевские теоремы для приближения функции двух переменных функциями вида ^(•aOYC'tf). Сообщения АН Груз. ССР, т.68, № 3, 1972, с.519−520.

27. Церетели A.C. Об аппроксимации функции двух переменных. -Труды Тбил. универ., т.225, 1981, с.63−80.

28. Шура-Бура М. Р. Аппроксимация функций многих переменных функциями, каждая из которых зависит от одного переменного. -В сб.: Вычислительная математика., вып. 2, М., Изд-во АН СССР, 1957, с.3−19.

29. Юдин Д. В., Голыптейн Е. Г. Линейное программирование. М., Наука, 1969.

30. Янке Е., Эмде Ф., Леш Ф. Специальные функции., М., Наука, 1977.

31. Cotati L. AppxoxUymtLoh ey Functions o-J Fe. we*. Vun-labEe*, Lee-t, tfoUs m Hath.3 280, <972 > p. 46−51.

32. Schmidt E. ZutТЬеогСе de* Iiпеачлп und mlcivtUfteQlttt Inte^E^udiun^en., Math. Ann., LXHI, 1907, s. кЬЪ-Ц76.

33. Sew oik V. Al^ovutais {оъ sepamtuons o| -fune-tUms of se^Y-ai va^i-a^es i-nto c^mfelrurUons o (function eocJi unVoCVDhjj, Oh^ on-e. o| t^e va^bu?fe. In|. Ргос. Math-э 497i, p. 469—I82.

34. Ttctiax. 0.3. App^oxwviatin^ a matrix a s"um o} products. MIT/PL E Quart, ptoji. Rep ., 9S, -1970 .

35. TWteE g. ahd Shanks IJ. L,. The ck&ujn oj muttL-btoge аерйгйЬЕе pianos J-i.?te/t& э p^e&enteol at tke Ancien House, Workshop ои Fittetun^,, hartman, n.y. u?&o lh IEEETxohs.keosel. EUcbtOKi, n/oC. &E-9, Uan. 1971, p.40−27.

36. Zi-^tciK. K. RoiWra^iQMLQuГ notmle ni. e?mloweqo^oVhanLa macLe/t-zoWego XY=A. Ropc^t |s/a. A/-84. Intt. Inj. Unlw^s. W-ujcthWakcetjo, Wioe-ta*/, ?Lstopaci 1980 .

37. ZLe^tak. К. 0 zbLe^vtoscu o^o^tmu P у^гпасгапиэ ^ozv/ia^iQHia иГ HOYJnie. naoioktes? ohugo nle? uiiovje^o 'LoWhQnuo maele^ioweep XY=A. Rapott Nt, М05, Inst. In}. T/nl^etc. V^oc.*tQWtl.

38. Z Legale K. Zwia^ek mie^oUij,^{obWlOjicmlomL} ui notmie? p L Y (?WHahuq. mocXe-^-ioWegoXY = A. Ropott А/г Л/—106. Institute o-j Computer $>?lence3 TJinuvetcitij of VJioc? aW, 19И 0 VitoclaW, Potcmci .

39. Zle, tctL I^skte-tna Qp^oics^macla C^e?tjs^ewQd*/och im^enn^cli 2Q pomocc^ suni iioz-ZtjtioW {uhkcjC jecln^j ?imlennej. Rapo^t л/г A/-G6% Ivistytut Tn-fccmat^kL UHiWefcs^teiu. WtottqvA/sIcie"^, Wto&taW, Up Lee. Ш9.

40. Zu>tqk К. 0 punkcLe stQcjoMQr’h^m hunlmaKSOWe-^o zoctanLa nle-UttloWe^o ton/nomla macle/t-iowego XYsA. Ropovt fit, Inst. Ihjcwn. Umwets. «W'cafttQWsliLe^o, Vlboataul) frstopaot -1980.

41. Zi^tak K. TKe. p.

42. Zi^tak K. Tke Cke? jpkev Solution o-ftb" -Rin-ea-b maitCx Emulation АХ+YB = 0. Re. pot/t Ait. А/Ч21. Institute o{ Computer ScLe. hce ^ Ики/е^еД^ o{Wtc>ciawy*o"fcaW J9ib.

43. Zle^ta к К. A и ote. on Q? ha4ue, 4-ei, Ucitvon oi the btotumat/^ jpoi/Vfb* o i a e*/t/bcun imuniroux p"tob?em. Report д/t Inst. Inf WwctaWaUejo 5 VltoetaW ..

44. Z? e, tal< |<. The. Ch",?ys.hev oppwumaitori.

45. Zulale К. Thetp-soiutuon о 4 tu цок tinea*. mat-члл equation XY=A. Institute .