Многомерная аппроксимация функциями специального вида тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

Введение

§ I. Постановка задачи и ее разрешимость.

§ 2. Квадратная чебышевская интерполяция.

2.1. Разбиение множества М^ на конечное число знаковых областей.

2.2. Решение задачи (2.1) в альтернансной знаковой области

2.3. Оценка типа оценки Валле-Пуссена.

2.4. Решение задачи квадратной чебышевской интерполяции

2.5. Вспомогательные экстремальные задачи.

2.6. Признак оптимальности альтернансной пары.

§ 3. Достаточные признаки оптимальности.

§ 4. Необходимые признаки оптимальности.

§ 5. Приближение функции двух переменных произведением функций одной переменной.

5.1. Определение двумерного альтернанса.

5.2. Первый достаточный признак оптимальности.

5.3. Второй достаточный признак оптимальности.

5.4. Необходимые и достаточные условия оптимальности в альтернансной форме

§ 6. Опровержение некоторых опубликованных результатов

§ 7. Построение решения для одного класса функций.

§ 8. Об поперечниках в цространстве С

§ 9. Численные методы.

9.1. Метод решения задачи квадратной чебышевской интерполяции

У стр.

9.2. Метод решения задачи (1.2)

9.3. Метод решения задачи равномерной аппроксимации матрицы цроизведением векторов.

§ 10. Решение некоторых вычислительных задач.

10.1. Примеры аппроксимации некоторых гладких функций

10.2. Выбор начального цриближения

10.3. Оценка снизу для величины наилучшего приближения

10.4. Способ аппроксимации для одного класса функций.

10.5. Задача, связанная с теорией обработки изображений

Многомерная аппроксимация - сложная и мало разработанная проблема. К ней относится, в частности, задача аппроксимации функции многих переменных суммой произведений функций, каждая из которых зависит лишь от одной из переменных. Аппроксимация такого вида нашла свое применение в проблеме "сжатия" информации. Например, при численном решении многомерных задач, при их реализации на ЭВМ большие трудности возникают в связи с использованием в качестве исходных данных или в качестве полученного результата функции многих переменных. Объем таблиц таких функций обычно очень большой и результат из-за огромного количества материала трудно обозрим. Один из возможных способов преодоления возникающих здесь затруднений состоит в црименении аппроксимации рассматриваемого вида. Аппроксимация функции многих переменных суммой произведений функций одной переменной находит свое применение в вопросах повышения эффективности систем передачи информации, в теории обработки изображений [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) в дискретном iálüYri 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.0036374, НИИМ, ЛГУ им.А.А.Дцанова, Л.,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. Cotatî L. AppxoxUymtLoh èy Functions o-J Fe.we*. Vûn-labEe*, Lee-t, tfoUs m Hath.3 280, <972 > p. 46-51.

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

33. Sew oik V. Al^ovûtais {оъ sepamtüons o| -fune-tUms of se^Y-ai va^i-a^es i-nto c^mfelrurUons o( function eocJi ünVoCVDhjj, Oh^ on-e. o| t^e va^büßfe . In|. Ргос. Math-э 497i, p. 469--Î82.

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 ÎJ. L,. The ck&üjn oj muttL-btoge аерйгйЬЕе pianos J-i.£te/t& э p^e&enteol at tke Ancien House, Workshop ои Fittetùn^, ,hartman , n.y. û£&o lh IEEETxohs.keosel. EUcbtOKi, n/oC. &E-9, Üan. 1971 , p.40-27.

36. Zi-^tciK. K. RoiWra^iQMLQ -uГ 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ßohügo nle£uiiovje^o 'LoWhQnüo maele^ioweep XY=A. Rapott Nt, \М05, Inst. In}. T/nl^etc. V^oc.*tQWtl<Le^o j Pa^cliCe*,-«bk , 1981.

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<u?pettiM o-f tlne Mimtnixx.ttoh o{ Q ^oи-¿ineat. Mat^x* E^ua-kon. XY=A IM.А ЯоигиаЯ o-( Wumex.tea4 Attö^sU , 5,229-2M».

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 J9îb

43. Zle^ta к К. A и ote. on Q ßha4üe,4-ei,Ucitvön oí the btotumat/^ jpoi/Vfb* o i a e*/t/bcùn imùniroûx p»tobßem. Report д/t Inst. Inf WwctaWaUe -jo 5 VltoetaW .

44. Z¿e,tal< |<. The. Ch«,ßys.hev oppwumaitori <o| a VAcMûntJtf^at, mat/cU ituvKiee«, of bmaEEet гол(4 as the HimíA oj íp-app^oxùmaiton. Report д/г Л/-ЛЧЪ-Institute, о J- Computer ^ eXene.fi. , UnWe^ditj o -f UwdavJ , Ш2. ^PotaW .

45. Zúlale К. The -tp-soiutuon о 4 tu цок tinea*. mat-члл equation XY=A. Institute <?■{ Compu-fet. Retende, UnlveTCùtj o| WioßtaW ^ 4 , vKoctavJ ^ Potcuiol .