Наилучшее приближение дискретного многозначного отображения алгебраическим полиномом

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

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

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

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

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

В диссертации рассматривается следующая задача: p (A):=kmaXN max {y2kpn{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 <. < tN и зафиксировано натуральное число п — степень алгебраического полинома р"(А, /). Требуется минимизировать максимальное уклонение алгебраического полинома от значений дискретной функции.

Р'-= min maxkpn (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], (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, то есть ph{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.

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

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

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

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

Ф (0)=[0−4], Ф (0.5)={2},.

О <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) для амплитудной функции.

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

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.

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 yjk>k-Чётно, y2jk, к—нечётно, tjk ecr, к е[0:л + 1].

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

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

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

Лл= Я J #. ,.

Уи, =<�Ро?'Ь,) -«-¦-> t Л h.

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

6).

AeR где.

Pi (4.

Задачи (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{Aqk)=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.