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

Содержание к диссертации

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

8. Об YI- поперечниках в пространстве С 76

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

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

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

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

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

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

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

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

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

Литература

• Решение задачи (2.1) в альтернансной знаковой области
• Первый достаточный признак оптимальности
• Метод решения задачи равномерной аппроксимации матрицы произведением векторов
• Оценка снизу для величины наилучшего приближения

Введение к работе

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

Для функции двух переменных задача ставится следующим образом. Пусть непрерывная функция \ Ы,^) задана на U *V , где U и V - некоторые метрические компакты. Зафиксируем некоторое целое число 1 . Требуется найти такие системы непрерывных функций 2Е^в|*^(и)і , заданных на U , HJ^e^

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

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

В диссертации рассматривается задача (І) в норме пространства С , т.е. UxV 4r*i mua . (2)

Самостоятельный интерес задача (2) представляет в дискретном случае, когда компакты U и V состоят из конечного числа точек, т.е. U^e {гіі^г,. . .^И^Д , V^s |і\₅^,..., ^«j . Тогда задачу (2) можно рассматривать как задачу приближения заданной матрицы г порядка ш*и произведением двух матриц X и "Y , где X имеет порядок nixt , а Y - Y*m . Обозначив llFll = wax F[i,j]| , задачу (2) в дискретном варианте можно записать в виде ^(XtfV-llP-X-YH-,-* «іч (3) где )0(Х_г - множество пар матриц {xXj » имеющих указанный выше порядок.

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

Теоретические основы для решения задач (2) и (3) были впервые даны В.А.Даугавет в работах [8-Ю^-]. В этих работах были выведены некоторые необходимые и достаточные условия локального минимума функции H^QCX) Было дано понятие стационарной пары ]X,Yr для задачи (3) и выведены необходимые и достаточные условия стационарности. Позже эти же условия стационарности были получены К.Зентак в [42-45]. В работах [9, 10] В.А.Даугавет вводит понятие двумерного альтернанса и показывает, что для невырожденного случая существование двумерного альтернанса является необходимым условием локального минимума для задачи (3). Относительно достаточных условий оптимальности доказано лишь, что наличие квадратного альтернанса у пары їХ^Г означает, что эта пара является точкой локального минимума функции ч(ЭС,У) Наиболее полные результаты для задачи (3) получены при t = і в работе [8]. В этой работе кроме двумерного альтернанса вводится понятие вырожденного одномерного альтернанса. Это позволило необходимые условия локального минимума функции 4^(XJQ приблизить к достаточным условиям.

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

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

Большое внимание в литературе уделялось и уделяется задаче приближения функции двух переменных суммой функций одной переменной, т.е. задаче

Основные теоретические результаты для этой задачи даны Ю.П.Оф-маном, М.-Б.А.Бабаевым, С.Я.Хавинсоном и В.П.Моторным в работах [19, 2-4, 24, I8J. Укажем на связь решения задачи (4) с решением задачи (2) при Ч-= . Допустим, что решением задачи (2) для некоторой функции 4С">^ ( *-~ 2- ) являются функции одной переменной tej.(tt) , Хъ(у!) » Ч(?) і Чг(?) » такие что ж_г(іі)=і и ^(*)sl . Тогда 3Ci.(ii) и ^2.(у) являются решением задачи (4), поэтому теоретические результаты, полученные для задачи (4), в какой-то мере могут быть использованы для задачи (2).

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

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

В первом параграфе дается постановка задачи и рассматривается вопрос о ее разрешимости.

Второй параграф посвящен задаче (2) для простейшего случая, когда каждый из компактов "U и V состоит из ъ**. точки. Проводя аналогию с одномерной задачей линейной чебышевской аппроксимации, этот частный случай назван квадратной чебышевской интерполяцией. В данном параграфе показывается, что задача квадратной чебышевской интерполяции сводится к простой экстремальной задаче, решение которой при небольших t весьма несложно. Для доказательства этого основного результата устанавливаются некоторые вспомогательные утверждения, представляющие и самостоятельный интерес. Кроме этого, получена оценка типа оценки Валле-Пуссена и установлен простой достаточный признак оптимальности альтернансной пары.

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

В четвертом параграфе выводятся необходимые признаки решения для задачи (3). Как уже было отмечено, необходимые признаки оптимальности для этой задачи были получены в работах В.А.Даугавет и К.Зентак. В диссертации приводится другой, более наглядный вывод этих условий, использующих теорию линейного программирования.

Задача (2) при 4=1 , т.е. задача приближения функции двух переменных произведением функций одной переменной рассматривается в параграфе пять. Этот случай исследован наиболее полно. В частности, получены достаточные признаки решения, связанные не только с квадратным, но и с общим двумерным альтернансом. Введено понятие вырожденного точечного альтернанса. Это позволило для дискретной задачи построить общие необходимые и достаточные условия локального минимума функции ^iC^xX) Для задачи (2) общие необходимые и достаточные условия оптимальности пары {ху} пока получить не удается.

В шестом параграфе приведены контрпримеры к некоторым утверждениям, имеющимся в работах [26, 27, 20].

В параграфе семь описывается класс функций, для которых решение задачи (2) при 4-і можно получить в аналитическом виде. При построении таких решений существенно используются результаты второго и третьего параграфов. Для описанного класса функций приводится теорема характеризации, в которой необходимые и достаточные признаки решения совпадают.

Восьмой параграф посвящен вопросу связи задачи (2) с задачей нахождения и - поперечника некоторого компакта в пространстве непрерывных функций, которую установил И.К.Даугавет. Эта связь между двумя различными задачами полезна в том отношении, что позволяет переносить результаты, полученные для одной из них на другую, в частности, показано, что обе эти задачи могут не иметь решения.

В параграфе девять приведен алгоритм решения задачи квадратной чебышевской интерполяции. Кроме того, описан известный - ю - метод построения стационарной пары, который использовался для нахождения решения задачи (2) в дискретном варианте, т.е. задачи (3). Очень просто реализуется алгоритм решения задачи (3) при ч,= 1 . Для этого случая выведены простые формулы.

Последний десятый параграф посвящен приложениям задачи (3). В нем приведены некоторые вычислительные примеры и решена задача, связанная с теорией обработки изображений. Особое внимание автор обращает на выбор начального приближения, так как функция ^(х^ имеет не только глобальный, но и локальный минимумы. В диссертации предлагается в качестве начального приближения для задачи (3) брать решение задачи (І) в дискретном варианте в норме пространства 1_р .

В диссертации получены следующие новые результаты:

1. определена задача квадратной чебышевской интерполяции и проведено ее полное исследование, в частности, показано, что она сводится к простой экстремальной задаче; получена оценка типа оценки Валле-Пуссена для величины yv\iy\ ^(xjy) ^в задаче (2); доказано три достаточных признака решения для задачи (2); построены примеры, опровергающие некоторые опубликованные результаты, касающиеся общих необходимых и достаточных условий решения задачи (2); построены для дискретной задачи (3) при г- і общие необходимые и достаточные условия локального минимума функции описан класс функций, для которых решение задачи (2) при t = і можно получить в аналитическом виде. - II -

Основные результаты диссертации опубликованы в работах [14, 15, 21-23]. Работы [14, 15] написаны совместно с научным руководителем. Результаты, полученные в диссертации, докладывались на семинаре по нелинейным задачам аппроксимации, на семинаре кафедры исследования операций, на семинаре по теории приближения функций кафедры математического анализа математико-механическо-го факультета в 1980-1984 гг. в ЛГУ. Полученные результаты докладывались также на заседании физико-математической секции научно-технической конференции Ленинградского института киноинженеров и киноорганизаций г.Ленинграда и на III симпозиуме по методам решения нелинейных уравнений и задач оптимизации, в г.Таллине в 1984 г.

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

Для вектора X^е Е символом X Ы обозначается l -я ком-понента. Норма со значком "I^й означает ІІХІ^ - 2, |Х [1] J . Соотношение Х = 0 означает, что все компоненты вектора X равны нулю. Через Х^т будем обозначать вектор-строку.

Для произвольной матрицы А символом А [ч>^1 будем обозначать ее элемент, расположенный на пересечении I -ой строки и j -го столбца. Соотношение А=0 означает, что все элементы матрицы А равны нулю. Через А будем обозначать матрицу транспонированную к А .

Для конечного множества Т символом (11 обозначено количество элементов в Т

Пусть Ct - произвольная величина. Тогда ¹ -1 _э Of ^0 fctciTi Of = і , Of *0

Вместо символа — будет использоваться символ : = - ІЗ -

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

Рассмотрим задачу (I.I) в простейшем случае, когда каждый из компактов U и V состоит из і+ і точки. Проводя аналогию с одномерной задачей линейной чебышевской аппроксимации, назовем этот частный случай квадратной чебышевской интерполяцией. Он совпадает с дискретной задачей (1.2) при и п-г+і . В настоящем параграфе показывается, что задача квадратной чебышевской интерполяции сводится к экстремальной задаче, решение которой при небольших ъ весьма просто.

Пусть F - произвольная квадратная матрица порядка г 1 . Обозначим Лх - множество матриц Т порядка ч, і , имеющих ранг не превосходящий X . Квадратная чебышевская интерполяция заключается в решении задачи М(Т): Fw- Vnln . (2.1) Ясно, что если ранг Р не превосходит % , то решением задачи (2.1) является сама матрица Р и гиСп и (тЛ = 0 .

В дальнейшем будем считать, что Р - неособенная матрица и поэтому и(т) 0 для любых Те Цг . Обозначим и и - ( t+і )- мерные векторы с компонентами -1 И + І Основной результат этого параграфа заключается в следующем. Решением задачи (2.1) является матрица где S) , , ti есть решение следующей экстремальной задачи

При этом, если максимум в (2.2) достигается на единственной паре (і ,пЛ (с точностью до общего знака), то Т - единственное решение задачи (2.1).

Ясно, что при малых t (t 3 ) обратить матрицу V и решить задачу (2.2) методом перебора не представляет трудности.

Прежде чем непосредственно доказать этот результат, установим некоторые вспомогательные утверждения, представляющие и самостоятельный интерес.

Разбиение множества 14. на конечное число знаковых областей Покажем, что множество И-с можно представить в виде объединения конечного числа некоторых множеств (знаковых областей), на каждом из которых легко оценивается снизу функция J (Т) . Определим эти множества. Любая матрица ТеМг имеет ранг не превосходящий "t , поэтому для ТеМ. системы линейных уравнений

Множество 8 ($;{) будем называть знаковой областью И t . Очевидно, что знаковых областей конечное число и каждая матрица Те Мг принадлежит хотя бы одной из них. Заметим, что Ц ч , G-, =-6.-. Легко видеть, что достаточно рассмотреть знаковые области 2 ( ,УЛ для пары векторов ЇД\ только из множества

Выделим из множества W так называемые альтернансные пары м » сРеДи которых и будем в дальнейшем искать решение задачи (2.2). Определение. Пару ЛД6 будем называть альтернанс-ной, если она удовлетворяет условию f lWrVKHL (2.3) - 19 Легко понять, что условие (2.3) равносильно тому, что компонента [і] равна знаку I -ой компоненты вектора vjj Р" , если она ненулевая, a ир.} совпадает со знаком t -ой ненулевой компоненты вектора F .

Соответствующую альтернансной паре {%л\ знаковую область 3(эд} также будем называть альтернансной.

Решение задачи (2.1) в альтернансной знаковой области Покажем, что всякая альтернансная пара ї цЛ позволяет найти минимум м(г) в альтернансной знаковой области SCVJV » т.е. решить задачу МСТУ.-ІІРIL- іетілі . (2.4) Пусть ta - альтернансная пара и № = р.а," Построим матрицу То= F-JW.YI . (2.5) Легко проверить, что ТоєЬ П& о . Действительно, положим Zo = F"lo . Из (2.3) и (2.5) получаем, что ToZ0=0 и (Zos 0)= i I Г"А о= Ц2.ІІІ » т«е Т. е b 0 . Аналогично показывается, что Т0 е &«0 , т.е. То є Ь с П б 0 Заметим, что матрицу вида (2.5) можно построить для любой пары (эЧ} Однако только для альтернансной пары эта матрица будет одновременно принадлежать областям 6« и L ,

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

При исследовании альтернансных свойств решения будем предполагать, что сама функция j( M ) не представима в виде произведения ос (у)- ( -) , так что для любых ос (ід) є С (U) ,

Введем обозначения. Через n (u , обозначим функцию невязки, т.е. при этом Ґ( ) = Sign [h (14,1] и f (14 = ( U, -) bC [x(tT) -Ц(&)] .

Через Q (pt, как и раньше, обозначим множество точек из tbV на которых невязка Ь(-и) достигает максимального по модулю значения, т.е. Так же как в дискретном случае (см. [8]) введем понятие двумерного альтернанса для задачи (5.1).

Определение. Циклическую систему из 2 fy ( ty» 2L ) точек назовем двумерным альтернансом, если для некоторой пары функций \зс(г0,ч(,1 )] выполнены условия АсіК 2) Т( 1 )= 9(-іУ+і , где Эе\-1 , т.е. эс и №) отличны от нуля на А и t i., /) имеют чередующиеся знаки. На рис. I изображен один из вариантов расположения точек альтернанса ( = 4 ) с указанием знака ( А) .

Двумерный альтернанс наименьшей мощности состоит из 4 точек. Он называется квадратным. Заметим, что данное здесь определение двумерного альтернанса при су = 2. , т.е. когда он оказывается квадратным, равносильно определению квадратного альтернанса для произвольного t (см. 2). Действительно, матрицы {ЗС,У}Є УП-ч, при і і вырождаются в пару векторов и, следовательно, в определении альтернанса участвуют уже не определители, а компоненты векторов X и Y .

Первый достаточный признак оптимальности Покажем теперь, что если пара зс», } обладает двумерным альтернансом и связана с функцией }(и,1 некоторым знаковым соотношением (см. теорему 5.1), то ос , } - решение задачи.

Предварительно докажем два вспомогательных утверждения. Зафиксируем некоторые функции ж (у)є С (U) , (і )є С (У) и для произвольных х[ц)еС(и) , ц(&) є С (у) положим где Лемма 5.1. Пусть пара # Л обладает двумерным альтернатом А . Тогда глип Ц Ы -i) 0 (5.3) ltti, i}6A для любых { 02, ] е С (U) х С (у) .

Доказательство. Заметим, что если функция эс( и) такова, что Я (lit) 0 хотя бы для одного і , то либо в точке {ИІ. І\ , либо в точке i, L-ij значение ( 1,) будет отрицательно, т.е. выполняется (5.3). Поэтому будем рассматривать те Х(гі) , для которых зе(і і) 4= 0 при всех u = i,2v-. a. Зафиксируем такое Х. и) и произвольное ч(у) . Заметим, что по определению аль-тернанса Ч ( і)ї О при всех L»i,2,..., а, . Положим ЯК Л = - і , J»i,a -, V v d) l MI-M j)l 4 K , где Uy cMc . Ясно, что -(. , ) 0 Рассмотрим следующую линейную комбинацию « «(ui j) с коэффициентами Л (111,) на А , т.е. сумму г 2_ (ІІ У К 4). (5.4) - 47 -Подставляя значения Я(ІІЩ?І) В сумму (5.4), получим Щ[ Mull J=i L=j J» і t-j Ч ш І МІ

Каждое слагаемое в скобках встречается ровно два раза, причем с разными знаками. Следовательно, полученная сумма равна нулю. А тогда либо все ot« (1 ,1 )=0 , либо среди - (ui ) есть отрицательные. И в том и в другом случае получаем выполнение (5.3). Лемма доказана. В различных примерах, проделанных автором, при нахождении решения задачи (5.1) для разных конкретных функций }К ") всегда получался квадратный альтернанс, для которого условие (5.6) было выполнено. Поэтому возник вопрос, не является ли наличие альтернанса со знакоЛегко показать, что функция эё й ) на А как раз и есть матрица ТА . Таким образом, j ] - решение задачи (5.1) на А . Покажем, что j j - решение задачи на U V Имеем

Решая уравнения Ьм=0 , lv = О получаем точку lj в которой М « , і) = 0 Осталось функцию h Ы,&) исследовать на границах прямоугольника [- i]x[o,l] . Легко видеть, что на границах этого прямоугольника функция К (u ) есть прямая, поэтому экстремумов у нее нет.

Таким образом, . г[ \ - решение задачи (5.1). Однако, в точке j-jj »o( условие (5.6) нарушается.

Второй достаточный признак оптимальности Допустим, что пара W 5 } обладает двумерным альтернатом А к , но не удовлетворяет достаточному признаку оптимальности с условием (5.6). В этом случае пару ог Л можно подвергнуть еще одной проверке на оптимальность. Выведем этот второй достаточный признак оптимальности.

Пусть пара функций 4а , Д обладает двумерным альтер нансом А . По » , 1 и А построим множество пар функций S є С(іО С(у) следующим образом

В работе [в] было доказано , что если пара Ьс ,у т обладает двумерным альтернансом А , то она является точкой локального минимума У( іУ) и одновременно решением задачи (5.1) на множестве функций [ ,} таких, что si.on Ot(uiV ьілп зсж(и-ь) для всех uei: y , или ь мп ч($) = Ы п J/ () для je i-y.

Множество S шире указанного в этих формулах множества пар функций. Докажем более общее утверждение. Теорема 5.2. Если х ,t #J обладает двумерным альтернансом А , то {»«д»] - решение задачи (5.1) в области 8 .

Доказательство. Возьмем произвольную пару [эс ]е S# . Пусть для определенности )х ]еФ+. Покажем сначала, что для этой пары р.(т$) о . (б.її) Заметим, что если х(ід;) = О хотя бы для одного Lei-, cj, , то (5.II) выполнено. Действительно, в этом случае либо ( )-0, либо (t ;, t Л= 0 . Пусть теперь CU( U ± 0 , 1=1,2,..., о, . вым правилом (5.6) необходимым условием оптимальности. Следующий пример показывает, что это не так.

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

Необходимость. Пусть Jx«sY«] точка локального минимума функции (ХГО . Допустим, что она не обладает ни двумерным, ни вырожденным альтернансом. Согласно теореме 5.4, тогда условие (5.17) для нее не выполнено. Это означает, что существуют пары (хотя бы одна) индексов к]є &(Х„,У,Г) такие, что Y [K] = X„[] =0 . Очевидно, что каждая строка матрицы Н(ХВ , такая, что Х М=0 удовлетворяет условию леммы 5.3 (иначе существовал бы строчный вырожденный альтернанс). Применяя последовательно к каждой такой строке лемму 5.3 построим новый вектор

X , для которого Ч $:0 YQW0 Так как 1Х«Х ] точка локального минимума функции Ч (XjO , а X можно сделать сколь угодно близким к X , то Ч (X У ) = М (X i ). Значит X,Y„j тоже точка локального минимума функции Ч (Х. ) и по построению Х,УЛ удовлетворяет условию (5.17). По лемме 5.3 также ясно, что R(X,Y«V «X)H в подправленных строках точки из R(X»y» ) , для которых Ч"»[Л 0 не будут принадлежать множеству й(Х,У,Г) . Отсюда ясно, что в результате пос-троения вектора X двумерный альтернанс возникнуть не может. Не может возникнуть также и вырожденный столбцовый альтернанс. Докажем последнее более подробно. Пусть для пары индексов ,к!е R (Х»У» ) выполнено X [i]=Y [K.]=0 . Если в к -ом столбце нет точек цк]ей(Х ) , для которых Х Й 0 , то доказательство очевидно. Пусть в К -ом столбце есть точки [ь,к]є R(X ) , для которых X [i"l 0 , тогда величина GK(Х»У») X» [I] одного знака для всех і (иначе существовал бы столбцовый вырожденный альтернанс). Рассмотрим теперь строку с номером . . Если в -ой строке нет точек \JL \\ є Q(X»" f») для которых Y« [і] 4 О , то положим X И = (ЧкС Х»УХ [і-] . Ясно, что тогда в К -ом столбце вырожденный столбцовый альтернанс возникнуть не может. Пусть в t -ой строке есть точки f .j}e R X Y ) , для которых Y 01= 0 Так как величины G.(X ,Y«YY»Cn для всех j имеют один и тот же знак, то по лемме 5.3 положим А это означает выполнение условий в определении вырожденного точечного альтернанса для пары х»хЛ » что невозможно по предположению.

Итак, полученная точка локального минимума [xj»j не обладает ни двумерным, ни вырожденным строчным или столбцовым альтернансом и удовлетворяет условию (5.17), что противоречит условию теоремы 5.4. Теорема доказана.

Можно привести различные примеры множеств матриц Р , для которых наличие двумерного альтернанса является необходимым и достаточным условием локального минимума функции Ч (Х;0 Приведем пример одного такого множества.

Пусть матрица Р такова, что в каждой строке и в каждом столбце у нее один максимальный по модулю элемент. Множество таких матриц обозначим через F . Для функций из этого множества нетрудно доказать следующее утверждение.

Теорема 5.6. Пусть е г . Для того чтобы Х ҐК} была точкой локального минимума функции 4(xxY) необходимо и достаточно, чтобы пара JX Y»} обладала двумерным альтернан-сом.

В работах А.С.Церетели [26, 27] формулируются необходимые и достаточные признаки решения задач (I.I) и (5.1). Приведем их.

Теорема 6.1. Для того чтобы сумма T.xJu)-4K(ti) ДОСТаВ-ляла наилучшее равномерное приближение непрерывной ( 1,17-) (среди всех сумм, состоящих из непрерывных функций), необходимо и достаточно, чтобы существовала молния L с U V со следующими свойствами: 1) L либо замкнута, либо содержит бесконечное число звеньев; 2) в вершинах L разность }- Г.Хк. Ук. принимает значения і М , где М = то)и}- 1_зскг) I , причем знаки разности в сосед них вершинах L противоположны.

Под молнией здесь понимается ломаная, все звенья которой параллельны либо Oil , либо otf- и два звена, имеющие общую вершину перпендикулярны. В более ранней работе [24] С.Я.Хавинсоном аналогичная теорема была доказана для случая приближения функции двух переменных суммой функций одной переменной, т.е. имела место

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

Вычисляя (0,0) = -1 , z(0,- )«z(- ,o)-z(- ,- )»0, получим z (ii,tf-)i. для всех {up} , находящихся внутри множества D . Рассматривая z(u,tf) на границах множества D , легко также получить выполнение условия (Е(гі і .

Таким образом, приведены два решения задачи (5.1) и оба эти решения обладают альтернансом А .

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

Теорема 7.2. Для того чтобы пара функций \ , «) доставляла наилучшее равномерное приближение функции (iJ,tf)fc 1(D) не обходимо и достаточно, чтобы эта пара обладала свойством: в вершинах D разность Jl y W W достигает по модулю максимального значения и имеет чередующиеся знаки.

Доказательство. Достаточность очевидно следует из теоремы 7.1. Докажем необходимость/Заметим, что приближающая матрица единственна на А , так как максимум величины Vі г. достигается на единственной паре {$ дЛ см теоРемУ 2.3). Значит для любого решения \ъ,ц\ матрица Т должна быть одна и та же. Теорема доказана. Замечание. В [20] для задачи (5.1) было приведено следующее утверждение. Пусть D»U V - ограниченное замкнутое множество в плоскости ио& ; J(tJ,tf) - непрерывная на D функция.

Теорема 7.3. Для того чтобы пара j-зіо е C(U)xC(y) доставляла наилучшее равномерное приближение непрерывной l(ti, необходимо и достаточно, чтобы существовала молния ЬсТ) со следующими свойствами: 1) L либо замкнута, либо содержит бесконечное число звеньев; 2) в вершинах Ь разность \ - эсо о принимает значения ± Ч , где Ч = ятак I { -ос0 0 » причем знаки разности в соседних вер шинах Ь противоположны. Здесь под молнией, как и ранее, понимается ломаная линия, каждое звено которой параллельно либо 014 , либо 0 и два звена, имеющие общую вершину перпендикулярны.

Как уже отмечалось в 6 для любой непрерывной функции -}(ц$ теорема 7.3, как частный случай теоремы 6.1 неверна. Однако, для функций из класса (D) теорема 7.3 справедлива, что и сформулировано в теореме 7.2.

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

Пусть U - метрический компакт, C(U) - пространство вещественных непрерывных на V функций, Vc С(и) - компактное множество.

Определение, (см., например, [іб] ). п - поперечником (Колмогорова) компакта Y называется число (UV):= LtiJ &UP LnJ lliNdl , где внешний I M I берется по всем подпространствам C cCtu) размерности ті . Если обозначить через яt (if),xz(if),..., зс (u) - базис произвольного подпространства пространства С , то определение поперечника можно записать в форме: сЦ(У)= tn SUP Ln{ SUP Ы)- LCKQCKW ... „єС tfeV cly..,c„eft UU Ksi l

Определим на произведении компактов U V функцию, положив 1( ) = 1 ( ) для tie U , eV И.К.Даугавет установил некоторую связь, которая существует между задачей отыскания П - поперечника некоторого компакта в пространстве непрерывных функций и задачей приближения функции двух переменных суммой произведений функций одной переменной, т.е. задачей (I.I). Имеет место

Указанную эквивалентность двух задач используем теперь для того, чтобы показать, что как задача (I.I), так и задача построения экстремального подпространства, т.е. подпространства, на котором реализуется И - поперечник, могут не иметь решения.

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

Дробно-рациональная аппроксимация функций и приложения Петрак Лариса Владимировна

Вэйвлет-сплайновая аппроксимация функций с особенностямиАрсентьева, Евгения Петровна

Наилучшие оценки в методах аппроксимации производных функции, заданной с погрешностьюСкорик Георгий Григорьевич

Метод аппроксимации эволюционных операторов с помощью экспоненциального представления и рациональных функций в гильбертовом пространствеСелин Алексей Владимирович

Влияние различных видов производственной функции и схем налогообложения на поведение инвестораТрубачева Анна Евгеньевна

Аппроксимация нуля значениями аналитических функций специального видаСакович, Наталья Владимировна

О сложности реализации функций многозначной логики формулами специального видаТрущин, Дмитрий Владимирович

Аппроксимация полугрупп гомоморфизмами специального видаСнетков Олег Александрович

О вложениях классов функций Н w в классы функций ограниченной обобщенной вариации и некоторые вопросы теории аппроксимации функцийМедведева Мария Викторовна

Аппроксимация функций полиномиальными решениями эллиптических уравненийФедоровский, Константин Юрьевич