Наилучшее приближение дискретного многозначного отображения алгебраическим полиномом тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

САРАТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМ. Н.Г. ЧЕРНЫШЕВСКОГО

НАИЛУЧШЕЕ ПРИБЛИЖЕНИЕДИСКРЕТНОГО МНОГОЗНАЧНОГО ОТОБРАЖЕНИЯ АЛГЕБРАИЧЕСКИМ ПОЛИНОМОМ

Ql.01.09 - дискретная математика и математическая кибернетика

Автореферат диссертации на соискание учёной степени кандидата физико-математических наук

На правах рукописи

Выгодчикова Ирина Юрьевна

Саратов - 2004

Работа выполнена на кафедре математической экономики механико-математического факультета Саратовского государственного университета им. Н.Г. Чернышевского.

Научный руководитель: доктор физико-математических на) к,

доцент Дудов Сергей Иванович

Официальные оппоненты: доктор физико-математических наук,

профессор Розен Виктор Владимирович,

кандидат физико-математических наук, доцент Камышова Галина Николаевна

Ведущая организация: Волгоградский государственный

университет

Защита состоится « » октября 2004 года в 15 ч. 30 мин. на заседании диссертационного совета К 212.243.02 при Саратовском государственном университете им. Н.Г. Чернышевского по адресу: 410012, г. Саратов, ул. Астраханская, 83, IX корпус СГУ, механико-математический факультет.

С диссертацией можно ознакомиться в научной библиотеке Саратовского государственного университета.

Автореферат разослан « .» сентября 2004 года.

А%,

Ученый секретарь диссертационного совета

канднлэтф!С1п<о^1а1»1ат1меаакна\'к,доцент В.В. Корпев

>(¿01 б ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Локальными аппроксимациями многозначных отображений занимались многие отечественные и зарубежные математики (Б.Н. Пшеничный, В.Ф. Демьянов, A.M. Рубинов, М.С. Никольский, Е.С. Половинкин, Л И. Минченко, Ж.-П. Обен, В.В. Гороховик и др .

К задачам, имеющим нелокальный характер, относятся внешнее и внутреннее эллипсоидальное оценивание многозначных отображений. Эллипсоидальными оценками множеств достижимости динамических систем занимались Ф.Л. Черноусько, А.Б. Куржанский и многие другие известные математики.

Относительно немного известно работ по равномерному приближению многозначных отображений на некотором заданном множестве. Так в одной работе М.С. Никольского1 рассматривается задача о равномерном приближении непрерывного многозначного отображения, заданного на отрезке, постоянным.

В диссертации рассматривается задача минимизации по всем узлам дискретной сетки уклонения образов многозначного

отображения (м.о.) <?(•) от значений алгебраического полинома:

' М С Никольский Об нппроксичаиии непрерывного многошачного отпИртиг iгид птгтоппнын налгл значныч отооражеиием Вестник МГУ Сер 15 Выч члтеч и киберне^игЙОСРМАЦИОМЛЛЪПАЯ J

БИБЛИОТЕКА

Функция

/(Л,к):= шах{у2> -р„{А,(кЫ(М)->и}.

называемая далее амплитудным модулем, является непрерывной и выпуклой по А, но не является всюду дифференцируемой. Такими же свойствами обладает и целевая функция в задаче (1). Поэтому задача (1) относится к задачам недифференцируемой оптимизации.

С одной стороны, задача (1) имеет сходство с известной задачей П.Л. Чебышёва о наилучшем приближении дискретной функции алгебраическим полиномом заданной степени

С другой стороны, в плане постановки, её также можно сравнить с задачей Б. Сендова2 о наилучшем приближении графика сегментной функции графиком алгебраического полинома заданной степени в метрике Ха-усдорфа, если иметь в виду дискретный вариант этой задачи Однако, как показано во введении диссертации, задача (1) не сводится ни к задаче Б. Сендова, ни к другим известным задачам теории приближений.

Цель работы заключалась в исследовании свойств решения задачи (1), а именно, требовалось получить

• необходимые и достаточные условия решения задачи,

• необходимые и достаточные условия единственности её решения,

• описание множества крайних точек решения задачи, а также в разработке алгоритма решения задачи.

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

(2)

где Л =Жк). *е[0:ЛГ].

" Ссндов Б Хауслорфовые приближения София 1979

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

• необходимые и достаточные условия решения задачи (1);

• критерий единственности решения задачи (1);

• критерий распознавания крайних точек множества решений зада-чи(1);

• достаточные (и необходимые, в случае N =п + 1) условия, при которых решение задачи (2) для дискретной функции

является одновременно решением задачи (I).

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

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

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

Апробация работы. Результаты исследования опубликованы в десяти печатных работах и докладывались на научных семинарах по неглад-

кому анализу кафедры математической экономики СГУ (2000 - 2004 гг.), на весенних научных конференциях механико-математического факультета (2000 - 2004 гг.), на Саратовских зимних школах-конференциях «Современные проблемы теории функций и их приложения» (2002,2004 г.), на 24-й конференции молодых учёных МГУ (Москва, 2003), на школах - конференциях «Современные методы теории функций и смежные проблемы» (Воронеж, 2003), «Теория функций, её приложения и смежные вопросы» (Казань, 2003), на научном семинаре кафедры теории функций и приближений (май, 2004 г.), объединённом научном семинаре по дискретной математике и математической кибернетике механико-математического факультета и факультета компьютерных наук и информационных технологий СГУ.

Публикации по теме диссертации приведены в конце автореферата.

Структура диссертации. Диссертация состоит из введения, двух глав, разделённых на десять параграфов и списка литературы из 33 наименований. Общий объём диссертации - 110 страниц.

СОДЕРЖАНИЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

Приведём основные результаты исследования задачи (1).

Во введении диссертации на простых примерах показывается, что задача (1) отличается от известных задач теории приближений, таких как задача П.Л. Чебышёва (2), задача Б. Сендова, задача «об ужах». Здесь же приводится краткая аннотация основных результатов диссертации.

В первой главе получены основные свойства решения задачи (1).

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

Далее понимаем под

р = 1п[+1р(л), Э1 = (4 е р(а)=р]

АеН"

У 2 к ~У\к

т - тах

Л е [О Л' 3 2

В § 2 показано, что при N <п решение задачи (1) сводится к решению системы линейных алгебраических уравнений

Теорема 2.1. Пусть N <п Задача (I) эквивалентна с бедующей тнейной относительно компонент (я0,<2|, ,а„) вектора А системе уравнений

л. , .. ^ , " у1* +у1к ^

+ +а„(к =---+ак

У2к~У I т--

\

(4)

к е [ О N1

где ак е [-1,1 ], Ж е [ О /V ] А именно, любое решение

А* =(оо >а\ 7 >ап) задачи (1) является решением системы (4) при некотором наборе параметров ак е[-1,1] к е[0 Л'] и, наоборот, для любого набора параметров ак е [-1,1] к е [о Л'] решение системы (4) является решением задачи (1) При этом р -т

Следствие 2.1. При N <п задача (1) имеет единственное решение тогда и точько тогда, когда N =п и вьтопняются равенства

£ е[0 и]

Угк ~У\к

/71 = -

2

В оста1ьных аучаях задача (1) имеет бесконечно много решений Из теоремы 2 1 также следует, что решение задачи (1) при N < п сводится к решению системы неравенств

Угк ~У\к

ао + + <*„/*----

<т-£2±—£1£д6[о л?] (5)

относительно неизвестных компонент вектора А € .. Каждое неравенство (5) определяет в пространстве «слой» гиперплоскостей с общей нормалью причём хотя бы для одного

правая часть неравенства из системы (5) обращается в ноль, и соответствующий «слой» сжимается в одну гиперплоскость.

В § 3 доказано, что задача (1) всегда имеет решение, причём множество решений задачи (1) является выпуклым и замкнутым, а при оно, кроме того, ограничено.

Теорема о необходимых и достаточных условиях решения задачи (1) является, пожалуй, самой важной по значимости в диссертации. Эта теорема доказана в § 4. Для её формулировки введём некоторые обозначения.

Базисом и назовём (п + 2) - точечную подсистему узлов множества Т вида

* = <-<',

Амплитудными функциями (рис. I), заданными на базисе а, назовём функции и со значениями

/ ; у7]к,к-чётно, <• Г у1/к,к-чётно,

к-нечётно, ^ \у2/к,к-нечётно,

¡л б с, к е[0:« + 1].

2» =«'»(?■'»)

Уз п "Л^-'л)

I

"I „ )

Н-»-»-■-г

Рис.1. Амплитудные функции

... 1,в ... /л

Если в качестве приближаемой функции в задаче Чебышёва П.Л. (2) взять амплитудную функцию для i = 0 или i = 1, эта задача запишется в виде

Задачи (6) будем называть также амплитудными а -подзадачами задачи (1).

Теорема 4.1. (необходимое и достаточное условие решения). Для того чтобы вектор А являлся решением за-

дачи (1), необходимо и достаточно, чтобы выполнялось хотя бы одно из условий

Поясним приведённое утверждение. Равенство (а) означает, что алгебраический полином степени п с вектором коэффициентов А «проходит» через середины максимальных по длине отрезков, являющихся образами м.о.

Если выполняется условие (б), то вектор будет решением одной из амплитудных - подзадач (6).

В § 5 рассматривается вопрос о единственности решения задачи (1), являющийся одним из самых трудных по доказательству в диссертации.

Теорема 5.2. (критерий единственности решения). Для того чтобы задача (1) имела единственное решение, необходимо и достаточно, чтобы выполнялось хотя бы одно из условий:

содержит не менее чем (п +1) элемент.

Условие (а) означает, что полином наилучшего приближения для задачи (1) «проходит» через середины максимальных по длине отрезков, являющихся образами м.о., и таковых не менее чем (р +1) штук.

Условие (/?) теоремы 5.2 совпадает с условием (б) теоремы 4.] при

условии, что вектор А является решением задачи (1).

В § 6 решается вопрос о распознавании крайних точек множества решений задачи (1) и даётся оценка их количества. Поскольку при N < п множество решений задачи не имеет крайних точек, считаем

Теорема 6.1 (критерий распознавания крайних точек). Вектор А еШ является крайней точкой множества решений 91 тогда и только тогда когда значение амплитудного модуля совпадает с минимальным значением целевой функции задачи (1) в (и + 1) различных узлах сетки Т, то есть

Если установлено, что решение задачи (1) не единственно, то

В таком случае несложно отыскать все крайние точки множества

решений задачи. Приведём утверждение, которое можно непосредственно

использовать для их отыскания.

Следствие 6.1. Пусть решение задачи (1) не единственно.

Вектор А 6 является крайней точкой множества решений задачи (1) тогда и только тогда, когда существует выборка

такие, что

выполняются равенства

Й [рп[А, О-УК',1.)+ 0~ к е[0: и], О)

и

тах ,/{А,к)=

гфЛ']

Следствие 6.2. Множество крайних точек мне

решений задачи (1) при N>n конечно и справедлива оценка

множества

1<|£(Ж|<С

2'

Обозначим через А(а) решение системы (4) для фиксированного на-

Следствие 6.5 Пусть N = п Множество крайних точек множества решений задачи (1) представимо в виде

Легко видеть, что множество решений задачи (1) в этом случае имеет -Л+1-М

I краиних точек

В § 7 приводятся условия, при выполнении которых решение задачи (2) для функции, заданной в узлах сетки значениями (3), является одновременно решением задачи (1) Пусть N '¿п +1

Теорема 7.1. Для того чтобы решение задачи (2) было одновременно решением задачи (I) достаточно, а в случае N = п + 1 и необходимо, чтобы выпочнялось хотя бы одно из условий

бора параметров ОС = (ат0, ,Оп) Введем множество

£(«)={,ф) |а4| = 1, Ае[0 и]Ш}

|Л/| = // + 1,

(9)

(10)

При этом р* = р + т, где

Следствие 7.1. Для того чтобы решение задачи (2) было единственным решением задачи (1) достаточно, а в случае N -п + \ и необходимо, чтобы выполнялось хотя бы одно из условий (9) или

Во второй главе диссертации на основе полученных фактов предлагается алгоритм решения задачи (1).

В § 8 приводится общая схема решения задачи, основанная на переборе базисов и выборок (п +1) различных точек сетки Т.

В § 9 приводится алгоритм решения задачи для случая N = п + 1. В этом случае возможен только один базис а, который совпадает с Т. Обозначим через решения соответствующих амплитудных а - подзадач (6), и пусть Аа =(\-а)А0 +аА^ где

а= т~Ь' , 2т - й0 - Л)

Ао = >'2,,к ~ Рп(Л>'Л ). к ~ четно, К = РЛАо>'л )~У\,ц • к-нечетно,

~ А| = Укл ~Р">'>*)> к~четн0> = РЛА1>'л)-У2,,к> к -нечетно,

к б[0:и + 1], \ = р* < р', /€0:1.

Теорема 9.1. Пусть А0ё 5Я, А\ Тогда вектор Аа является

решением задачи (1).

Таким образом, решением задачи (1) будет либо решение одной из амплитудных -подзадач (6), либо выпуклая комбинация этих решений с параметром а.

В § 10 излагается монотонный алгоритм для случая По

аналогии с известным алгоритмом Валле-Пуссена решения задачи (2).

происходит переход от одного базиса О" к другому Каждый раз выбирается одна из амплитудных <Т-подзадач, организуется переход к следующему базису и указывается та из амплитудных подзадач нового базиса, минимальное значение целевой функции которой больше, чем у предыдущей выбранной подзадачи

Автор выражает искреннюю и глубокую признательность своему научному руководителю доктору физико-математических наук С И Дудову за постановку задачи и большое внимание к работе.

ПЕЧАТНЫЕ РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

1 Выгодчикова И Ю О наилучшем приближении непрерывного многозначного отображения алгебраическим полиномом // Математика Механика Сб науч тр Вып 2 Изд во Сарат ун-та, 2000 С 13-15

2 Выгодчикова И Ю О наилучшем приближении дискретного мультиотображе-ния алгебраическим полиномом // Математика Механика Сб науч тр Вып 3 Изд-во Сарат ун-та, 2001 С 25-27

3 Выгодчикова И Ю Об алгоритме решения задачи о наилучшем приближении дискретного многозначного отображения алгебраическим полиномом // Математика Механика Сб науч тр Вып 4 Изд-во Сарат ун-та, 2002 С 27-31

4 Выгодчикова ИЮ О крайних точках множества решений задачи о наилучшем приближении многозначного отображения алгебраическим полиномом // Математика Механика Сб науч тр Вып 5 Изд-во Сарат ун-та, 2003 С 15-18

5 Выгодчикова ИЮ О монотонном алгоритме решения задачи наилучшего приближении многозначного отображения алгебраическим полиномом // Математика Механика Сб науч тр Вып 6 Изд-во Сарат ун-та, 2004

6 Выгодчикова И Ю О наилучшем приближении дискретного мультиотобра-жения алгебраическим полиномом // Тезисы саратовской зимней матем школы «Современные проблемы теории функций и их приложения» Саратов 2002 С 4344

7 Выгодчикова И Ю О наилучшем приближении м о алгебраическим полиномом // Тезисы воронежской зимней матем школы «Современные методы теории функций и смежные проблемы» Воронеж, 2003 г С 62-63

8 Выгодчикова ИЮ О задаче наил)чшею приближения многозначного отображения алгебраическим полиномом алгоритм решения // Сб матер 24-ой конфер мол ученых Москва изд-во МГУ. 2003

9 Выгодчикова ИЮ Критерий единственности решения задачи о наилучшем приближении дискретного многозначного отображения алгебраическим полиномом // Тезисы Сб науч трудов матем центра им НИ Лобачевского Казань, 2003 г С 52-54

10 Выгодчикова И 10 Процедура решения задачи приближения многозначного отображения алгебраическим полиномом //Тезисы саратовской зимней матем школы «Современные проблемы теории функций и их приложения» Саратов, 2004 С 48-50

Подписано в печать 31 08 2004 Формат 60x84 1/16 Бумага офсетная Гарнитура Tunes Печать RISO Объем 1,0печл Тираж 100 экз Заказ №351

Отпечатано с готового оригинал-макета Центр полиграфических и копировальных услуг Предприниматель Серман Ю Б Свидетельство №3117 410600, Саратов, ул Московская, д.152, офис 19

» 173 67

РНБ Русский фонд

2005-4 16026

Введение

ГЛАВА I. СВОЙСТВА РЕШЕНИЯ ЗАДАЧИ

§ 1. Постановка задачи

§ 2. Решение задачи для случая N < п

§ 3. О существовании решения задачи

§ 4. Необходимые и достаточные условия решения

§ 5. Критерий единственности решения

§ 6. О крайних точках множества решений

§ 7. Случаи сведения к задаче П.Л. Чебышева

ГЛАВА И. АЛГОРИТМ РЕШЕНИЯ

§ 8. Схема алгоритма общего решения задачи

§ 9. Алгоритм решения для случая N = п +

§10. Монотонный алгоритм решения для случая \М\ >п +

1. Задачи по аппроксимации и оценке многозначных отображений математическими объектами простой структуры находят обширные приложения в естествознании, в том числе в самой математике, и представляют один из разделов негладкого анализа.

Локальными аппроксимациями многозначных отображений занимались многие отечественные и зарубежные математики (Пшеничный Б.Н. [17] - [18], Демьянов В.Ф. [2] - [5], Рубинов A.M. [20] - [21], Никольский М.С., Половинкин Е.С. [15] - [16], Минченко Л.И. [12], Обен Ж.-П. [14], Гороховик В.В. [1] и др.).

К задачам, имеющим нелокальный характер, относятся внешнее и внутреннее эллипсоидальное оценивание многозначных отображений. Эллипсоидальными оценками множеств достижимости динамических систем занимались Черноусько Ф.Л. [24], Куржанский А.Б. и многие другие известные математики.

Относительно немного известно работ по равномерному приближению многозначных отображений на некотором заданном множестве. Так в работе Никольского М.С. [13] рассматривается задача о равномерном приближении непрерывного многозначного отображения, заданного на отрезке, постоянным многозначным отображением.

Задача о приближении графика сегментной функции графиком полинома заданной степени на отрезке в метрике Хаусдорфа, которую рассматривал Сендов Б. [23] и др. (см. напр. [22]), также, по сути, относится к задачам нелокальной аппроксимации многозначных отображений.

В диссертации рассматривается следующая задача: p(A):=kmaXN max {y2k -pn{A,tk),pn(A,tk)-уи}-, (l) где T = {t0 </, <.Ф((к)=[уи ;у2Л], Уг,к ke[0:N], pn{A,t) = a0+axt + . + antn, A = (a0,alt.,an)eRn+1.

Требуется минимизировать максимальное по всем узлам сетки Г уклонение образов многозначного отображения (м.о.) ф(-) от значений алгебраического полинома. Функцию

А, к) := max{y2 А - рп (.А, tk \ рп (.А, tk ) - ухк } будем называть амплитудным модулем. Поскольку эта функция является выпуклой по А, то целевая функция в задаче (1) также является выпуклой.

2. Приведём сравнение задачи (1) с некоторыми известными задачами.

Задача о равномерном наилучшем приближении функции алгебраическим , полиномом заданной степени была сформулирована П.Л. Чебышёвым в 1854 году. Приведём формулировку этой задачи для дискретного случая ([3]).

Задана таблица значений некоторой функции ук = y(tk ), &е[0 :N], t0 <tl <. < tN и зафиксировано натуральное число п - степень алгебраического полинома р„(А , /). Требуется минимизировать максимальное уклонение алгебраического полинома от значений дискретной функции

Р'-= min maxk -pn(A,tk). (2)

В случае если yl k = y2j, A e [О: JV], задача (1) вырождается в задачу

2). Поэтому возникает естественная гипотеза: решение задачи (1) можно получить, осуществив чебышевскую интерполяцию ([3]) для функции, заданной в узлах сетки Т значениями

У\,к+У2,к , rn Ari (3)

Ук :=-2-'

Эта гипотеза опровергается простыми примерами. Пример 1. Пусть п =

1,Г = {0, 0.5, 1 }, Ф(0)=[0;2], ф(0.5)= [0;2], <Z>(l)={2}.

Тогда

Уо =1» У\ = 1> У2 =2-Решение задачи (1) единственно рх (/)=1, причём минимальное значение целевой функции равно 1. Решение задачи (2) для функции, заданной на сетке значениями (3), иное, а именно, p]cfl{t) = t + 0.75, причём р = 0.25 (рис.1).

Pl(t)=2t + l

Рис. 1. Пунктирной линией отмечено ре-2й , /Р\ (0 = г + шение задачи (2) для функции, заданной на сетке значениями (3).

Л ('И

Пример 2. В примере 1 исправим многозначное отображение в точке tx = 0.5, положив Ф(0.5) = {l}.

Ясно, что решение задачи (2) для функции, заданной на сетке значениями (3), останется таким же, как и в примере 1, то есть p\h{t) = t + 0.75, р = 0.25. А задача (1) в таком случае будет иметь бесконечно много решений p*(t,a) = at + \, а е [0;2] (рис.1), и ни одно из них не совпадает с полиномом pxch{t).

Известно, что решение задачи Чебышёва П.Л. при условии N >п единственно. Пример 2 одновременно показывает, что решение задачи (1) может быть неединственным.

Следует вспомнить также о других задачах теории приближений, например, о задаче об «ужах» или о наилучшем хаусдорфовом приближении графика сегментной функции отрезком графика алгебраического полинома заданной степени.

Сендов Б. в своей монографии «Хаусдорфовые приближения» ([23]) рассматривал непрерывную задачу о наилучшем приближении графика сегментной функции графиком алгебраического полинома заданной степени на отрезке h(Gr0iGrpn(A>-))-► inf ,te[a-b], (4) где h(A,B) = max<jsupinf /?(tf,b);supinf p(a,b)\

Ue/ib&B ЬеВ J 4 расстояние Хаусдорфа между множествами А и В из R , p(w,v) = max{| w, -v, |,|w2 -v2 |} расстояние между точками w = ,w2) и v = (v1}v2) из R2 в метрике Минковского,

Or Ф = { (/, [ ух (0; У г (/)])»> е [a; b]} » Gr рп (А/) = {( рп (A, t% t е [a;b]} -отрезки графиков сегментной функции и алгебраического полинома на \a\b\, соответственно.

Рассмотрим дискретный аналог этой задачи. Под графиком дискретного м.о. ф( •), заданного на сетке Т, будем понимать множество а под графиком полинома - множество

Gr Рп (А,-) = { (tk; рп (A, tk ) ), к е [0 : N]}. Пример 3. Пусть N = 2, п = 1, Т = { 0, 0.5, 1 },

Ф(0)=[0;4], Ф(0.5)={2}, <P(l)={0}. Графиком м.о. на сетке Т будет множество

О <2> = { ( 0; [0; 4]), (0.5;2), (l;0) }, а графиком полинома а0 +a{i - множество

Gr рх {.А,-) = {(0;а0), (0.5;а0 + 0.5 ах),(l;а0 + а,)}.

Требуется найти алгебраический полином степени п — 1, который будет решением задачи (4) при t еГ. Решением этой задачи будет алгебраический полином plc(t) = 3-4t. Расстояние Хаусдорфа между графиком этого полинома и графиком заданного м.о. при t е Т составляет 1 и совпадает с расстоянием Минковского между следующими точками графиков м.о. и полинома, соответственно: h [сгФ,рхс{.))= /?((0;0),(0.5;l)) = p((0;0),(l;-l)) = Д(0;4К0;3)) = = р{{0.5;2), (0.5;1)) = /?((0.5;2), (0;3)) = р{{1;0), (l;-l)) = p((l;0> (0.5;l)) = 1.

Решением задачи (1) является множество pl*(t,a) = at + 2, ае[—4;0], причём минимальное значение целевой функции составляет 2. Очевидно, что ни один из полиномов указанного множества не совпадает с решением задачи (4).

Пример 4. Пусть Лг = 2,л = 1,Г = {0, 0.5, 1 },

Ф(0)= {0}, ф(0.5)= [0;0.75 ],Ф(1)= [0;1.5 ].

Рис. 2. Решением задачи (1) является множество прямых {ZK}, где Z — любая точка отрезка NM.

Решением задачи (4) является множество прямых {ХС}, где X - любая точка отрезка OD.

Минимальное значение целевой функции в задаче (1) составляет 0,75.

Минимальное значение целевой функции в задаче (4) составляет 0,5.

Координаты точек #(0,-0.75), М(0,0.75), 1,0.75), С(1,1), 0(0,0), Р(0.5,0.5), Л(1,1.5), ,5(1,0), D(0,~0.5). Прямая BP±ОС.

Множества решений задач (1) и (4) изображены на рис. 2. Решением задачи (1) является множество рх (f)= 0.75 + a(f-l), ае[0;1.5], а решением задачи (4) является множество p^{t)-\ + a{t — Y)t а е [l;1.5]. Очевидно, что эти множества не содержат общих прямых линий.

В теории приближений хорошо известно понятие ужа (см. напр. [8]). Применим понятие ужа для дискретного случая.

Верхним (нижним) ужом м.о. ф(-) называется алгебраический полином, p„{t) ) степени и, который удовлетворяет условиям: а) Уи * Рп {h )* У 2,к > У\,к * Рп ih )^У2,к, V к е [0 : JV], (б) существует выборка Л := < tqx <. < / J сг Т, такая, что

У-у п. к — четно.

Vi к - нечётно, i></*>

У\,дк, к ~ четно, У2,дк, к-нечётно,

А: е [0:«].

Заметим, что об ужах имеет смысл говорить только в том случае, если N>n, у2к >уи, V£e[0:iV].

Пример 5. Пусть jV = 2, и = 1, Т = {0,0.5,1},

Ф(0)=[0;1],Ф(0.5) = [0;1], Ф(1)=[1;1.5]. Верхним ужом на выборках Al ={0,1} и Л2 = { 0.5,1} будет полином p\(t)= 1. Для выборки А3 ={0,0.5} верхнего ужа не существует. Нижний уж существует только на выборке Alt p](t)=l.5t. Ни один из ужей не является решением задачи (1) (рис.3).

Нижний и верхний ужи

Рис. 3.

Решение задачи (1)- полином

Р\ = 0-5/+ 0.375,совпадает с решением задачи (2) для амплитудной функции <pq (•).

Решением задачи (1) является полином pi{t) = 0.51 + 0.375, а минимальное значение целевой функции в задаче (1) составляет 0.625. Это решение совпадает с решением задачи Чебышёва (2), если в качестве приближаемой функции взять функцию <pQ (•), заданную в узлах дискретной сетки Т значениями

0(0) = 1, ^0(0.5) = 0, ^0(1) = 1.5.

В дальнейшем такие функции будем называть амплитудными.

3. Диссертация состоит из двух глав, содержащих 10 параграфов. Приведём основные результаты исследования задачи (1). Обозначим через р = in tp(A),4l = \AeRn+X'.p(A)=p*).

AeRn+l

Пусть, далее,

Уг,к -У\л т := max —!-. к е [0:yV ] 2

В первой главе диссертации исследуются свойства решения задачи

1).

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

В § 2 даётся описание множества решений задачи (1) при N < п.

Теорема 2.1. Пусть N<n. Задача (1) эквивалентна следующей линейной относительно компонент (а0,а{,.,ап) вектора А системе уравнений a0+axtk+. + antk =---+ ак\т

5) к ], где aAe[-l;l], &е[0://]. А именно, любое решение

А* = [а0* ,а* задачи (1) является решением системы (5) при некотором наборе параметров a^e[-l;l], £e[0:JV] и, наоборот, для любого набора параметров ак е [-1; l], к е [0: N], решение системы (5) является решением задачи (1).

При этом р* = т. В § 3 обсуждается вопрос о существовании решения задачи (1). Доказано, что задача (1) всегда имеет решение, причём множество решений задачи (1) является выпуклым и замкнутым, а при N > п оно, кроме того, ограничено.

Один из основных результатов диссертации - необходимые и достаточные условия решения. Они получены в § 4. Чтобы сформулировать соответствующий факт, введём обозначения.

Базисом сг назовём (я+ 2) - точечную подсистему узлов сетки Т вида сг

Амплитудными (рис.4) назовём функции, заданные на базисах а значениями {;Уо <гЛ+(}с:Г

Ро1

У2,]к > к — четно, y^ j , к—нечётно, рх I y\jk>k-Чётно, y2jk, к—нечётно, tjk ecr, к е[0:л + 1].

У2.М =е>о1^'Уп) . .

Рис.4. Амплитудные

Уг.и ~ Ч>\. 'л) ф ункции

Лл= Я J # . ,

Уи, =<Ро\?'Ь,) -«-♦-► t Л h

Если в качестве приближаемой функции в задаче П.Л.Чебышёва (2) взять амплитудную функцию, эта задача запишется в виде ю >> p*(<j):= min( Pi (A, a), /eO:l,

6)

AeR где

Pi (4 <r) := ^ max J ^ (x, )- (л, tJk )|.

Задачи (6) будем называть также амплитудными а — подзадачами задачи (1).

Теорема 4.1. (необходимое и достаточное условие решения). Для того чтобы вектор A gR являлся решением задачи (1), необходимо и достаточно, чтобы выполнялось хотя бы одно из условий а) р{а*)=ш\ б) 3 а : р(л*)= р*{сг*^, где / = О или i = 1.

Поясним приведённое утверждение. Равенство (а) означает, что алгебраический полином степени п с вектором коэффициентов А «проходит» через середины максимальных по длине отрезков, являющихся образами м.о. (рис.5).

Рис.5. Имеем >2.0 - До =У2.\ -У\,I = 2т' (а* Л Я.0+Л.0

М=-i-» Угл

Если выполняется условие (б), то вектор а будет решением соответствующей амплитудной сг - подзадачи (7).

В § 5 рассматривается вопрос о единственности решения задачи (1), являющийся одним из самых трудных по доказательству в диссертации.

Теорема 5.2. (критерий единственности решения). Для того чтобы задача (1) имела единственное решение, необходимо и достаточно, чтобы выполнялось хотя бы одно из условий: а) множество Z := содержит не менее чем (п +1) элемент; 3 а* : р = р* (сг*), / = О или i = 1.

Утверждение (а) означает, что полином наилучшего приближения для задачи (1) «проходит» через середины максимальных по длине отрезков, являющихся образами м.о., и таковых не менее чем (п +1) штук.

Утверждение (/?) теоремы 5.2 совпадает с условием (б) теоремы 4.1 в предположении, что вектор А является решением задачи (1).

В § 6 решается воцрос о распознавании крайних точек множества решений задачи (1) и даётся оценка их количества.

Теорема 6.1 (критерий распознавания крайних точек). Вектор A* является крайней точкой множества решений тогда и только тогда когда значение амплитудного модуля совпадает с минимальным значением целевой функции задачи (1) в (л+ l) различных узлах сетки Г, то есть

3 Л* = [tqQ <. < tqn }: f{A\qk)=p\ Уке[0:п]. О)

Если решение задачи (1) единственно, то оно само будет крайней точкой. Учитывая определение функции /(-,-), мы имеем в (7) систему из (п +1) линейных уравнений относительно {п + 2) неизвестных (неизвестны компоненты вектора А и оптимальное значение целевой функции р ).

В § 7 приводятся достаточные условия, при выполнении которых решение задачи (2) для функции, заданной в узлах сетки значениями (3), является одновременно решением задачи (1). А при N = п +1 эти условия являются и необходимыми.

Во второй главе диссертации на основании полученных фактов предлагается алгоритм решения задачи (1).

В § 8 приводится общая схема решения задачи, основанная на переборе базисов и выборок (я + l) различных точек сетки Т.

В § 9 приводится алгоритм решения задачи для случая N = п +1. В этом случае решением (или одним из решений) задачи (1) будет либо решение одной из амплитудных сг-подзадач (6), либо специально подобранная выпуклая комбинация решений этих подзадач.

В § 10 излагается монотонный алгоритм для случая | М | > п + 2. По аналогии с известным алгоритмом Валле-Пуссена, происходит переход от одного базиса сг к другому. Каждый раз выбирается одна из амплитудных сг-подзадач, организуется переход к следующему базису и указывается та из амплитудных подзадач нового базиса, минимальное значение целевой функции которой больше, чем у предыдущей выбранной подзадачи, и которая будет использоваться для дальнейшего анализа.

Результаты исследования опубликованы в работах [25] - [33] и докладывались на научных семинарах по негладкому анализу кафедры математической экономики (2000 — 2004 гг.), на весенних научных конференциях механико-математического факультета (2000 - 2004 гг.), на Саратовских зимних школах-конференциях «Современные проблемы теории функций и их приложения» (2002, 2004 г.), на 24-й конференции молодых учёных МГУ (Москва, 2003), на школах - конференциях «Современные методы теории функций и смежные проблемы» (Воронеж, 2003), «Теория функций, её приложения и смежные вопросы» (Казань, 2003), на научном семинаре кафедры теории функций и приближений (май, 2004 г.), объединённом научном семинаре по дискретной математике и математической кибернетике механико-математического факультета и факультета компьютерных наук и информационных технологий СГУ.

1. Гороховик В.В., Забрейко П.П. Дифференцируемость мультиотображений в смысле Фреше // Труды института математики НАН Беларуси, 1998, т.1, с. 34 - 49.

2. Демьянов В.Ф. Минимакс: дифференцируемость по направлениям. JL: Изд-во ЛГУ, 1974.

3. Демьянов В.Ф., Малоземов В.Н. Введение в минимакс. М.: Наука, 1972.

4. Демьянов В.Ф., Васильев JI.B. Недифференцируемая оптимизация. М.: Наука,1981.

5. Демьянов В.Ф., Рубинов А.М. Основы негладкого анализа и квазидифференциальное исчисление. М.: Наука, 1990.

6. Дзядык В.К. Введение в теорию равномерного приближения функций полиномами. М.: Наука, 1977.

7. Ильин В.А, Поздняк Э.Г. Линейная алгебра. М.: Наука, 1974.

8. Карлин С. и Стадден В. Чебышевские системы и их применение в анализе и статистике. М.: Наука, 1976 (перев.).

9. Карманов В.Г. Математическое программирование. М.: Наука, 1975.

10. Курош А.Г. Курс высшей алгебры. М.: Наука, 1965.

11. Лейхтвейс К. Выпуклые множества. М.: Наука, 1985.

12. Минченко Л.И., Борисенко О.Ф., Грицай С.И. Многозначный анализ и возмущённые задачи нелинейного программирования. Минск: Наука и техника, 1993.

13. Никольский М.С. Об аппроксимации непрерывного м.о. постоянными многозначными отображениями // Вестник МГУ. Сер. 15. Вычисл. Матем. и кибернетика. 1990, № 1, с. 76 80.

14. Обен Ж.-П., Экланд И. Прикладной нелинейный анализ. М.: Мир, 1988.

15. Половинкин Е.С. Элементы теории многозначных отображений. М.: Изд-во МФТИ, 1982.

16. Половинкин Е.С. Теория многозначных отображений. М.: Изд-во МФТИ,1983.

17. Пшеничный Б.Н. Выпуклый анализ и экстремальные задачи. М.: Наука, 1980.

18. Пшеничный Б.Н. О дифференцируемости функции минимума со связанными ограничениями // Кибернетика, 1985, № 1, с. 123 125.

19. Рокафеллар Р. Выпуклый анализ. М.: Мир, 1973.

20. Рубинов A.M. Сопряжённая производная м.о. и дифференцируемость Н максимума при связанных ограничениях // Сиб. матем. ж., 1985, т. 26, № 3, с. 147 155.

21. Рубинов A.M. Аппроксимация многозначных отображений и дифференцируемость маргинальных функций // ДАН СССР, 1987, т. 292, № 2, с. 269 -272.

22. Сендов Б. Хаусдорфовые приближения. София, 1979.

23. Черноусько Ф.Л. Оценивание фазового состояния динамических систем: метод эллипсоидов. М.: Наука, 1988.ПЕЧАТНЫЕ РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

24. Выгодчикова И.Ю. О наилучшем приближении непрерывного многозначного отображения алгебраическим полиномом // Математика. Механика: Сб. науч. тр.Вып. 2. Изд-во Сарат. ун-та, 2000. С. 13-15.

25. Выгодчикова И.Ю. О наилучшем приближении дискретного мультиотображения алгебраическим полиномом // Математика. Механика: Сб. науч. тр. Вып. 3. Изд-во Сарат. ун-та, 2001. С. 25-27.

26. Выгодчикова И.Ю. Об алгоритме решения задачи о наилучшем приближении дискретного многозначного отображения алгебраическим полиномом // Математика. Механика: Сб. науч. тр. Вып. 4. Изд-во Сарат. ун-та, 2002. С. 27-31.

27. Выгодчикова И.Ю. О крайних точках множества решений задачи о наилучшем приближении многозначного отображения алгебраическим полиномом // Математика. Механика: Сб. науч. тр. Вып. 5. Изд-во Сарат. ун-та, 2003. С. 15 -18.

28. Выгодчикова И.Ю. О наилучшем приближении дискретного мультиотображения алгебраическим полиномом. // Тезисы саратовской зимней матем. школы «Современные проблемы теории функций и их приложения». Саратов, 2002. С. 43-44.

29. Выгодчикова И.Ю. О наилучшем приближении многозначного отображения алгебраическим полиномом. // Тезисы воронежской зимней матем. школыА>Современные методы теории функций и смежные проблемы». Воронеж, 2003 г. С. 6263.

30. Выгодчикова И.Ю. О задаче наилучшего приближения многозначного отображения алгебраическим полиномом: алгоритм решения. // Сб. матер. 24-ой Конфер. мол. учёных. Москва: изд-во МГУ, 2003.

31. Выгодчикова И.Ю. Критерий единственности решения задачи о наилучшем приближении дискретного многозначного отображения алгебраическим полиномом. // Тезисы. Сб. науч. трудов матем. центра им. Н.И. Лобачевского. Казань, 2003 г. С. 52-54.

32. Выгодчикова И.Ю. Процедура решения задачи приближения многозначного отображения алгебраическим полиномом. // Тезисы саратовской зимней матем. школы. «Современные проблемы теории функций и их приложения». Саратов, 2004. С. 48-50.