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

• Выгодчикова, Ирина Юрьевна
• кандидат физико-математических наук
• 2004

Оглавление диссертации кандидат физико-математических наук Выгодчикова, Ирина Юрьевна

Введение

ГЛАВА 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 г.), объединённом научном семинаре по дискретной математике и математической кибернетике механико-математического факультета и факультета компьютерных наук и информационных технологий СГУ.

Список литературы диссертационного исследования кандидат физико-математических наук Выгодчикова, Ирина Юрьевна, 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.