Содержание к диссертации
Введение
ГЛАВА I. Свойства решения задачи 15
1. Постановка задачи 15
2. Решение задачи для случая м < п 21
3. О существовании решения задачи 25
4. Необходимые и достаточные условия решения 29
5. Критерий единственности решения 48
6. О крайних точках множества решений 71
7. Случаи сведения к задаче П.Л. Чебышева 83
ГЛАВА II. Алгоритм решения 89
8. Схема алгоритма общего решения задачи 89
9. Алгоритм решения для случая N = п +1 93
10. Монотонный алгоритм решения для случая \М\ 97
Библиографический список 108
- Необходимые и достаточные условия решения
- О крайних точках множества решений
- Схема алгоритма общего решения задачи
- Монотонный алгоритм решения для случая \М\
Введение к работе
1. Задачи по аппроксимации и оценке многозначных отображений математическими объектами простой структуры находят обширные приложения в естествознании, в том числе в самой математике, и представляют один из разделов негладкого анализа.
Локальными аппроксимациями многозначных отображений занимались многие отечественные и зарубежные математики (Пшеничный Б.Н. [17] - [18],. Демьянов В.Ф. [2] - [5], Рубинов A.M. [20] - [21], Никольский М.С., Половинкин Е.С. [15] - [16], Минченко Л.И. [12], Обен Ж.-П. [14], Гороховик В.В. [1] и др.).
К задачам, имеющим нелокальный характер, относятся внешнее и внутреннее эллипсоидальное оценивание многозначных отображений. Эллипсоидальными оценками множеств достижимости динамических систем занимались Черноусько Ф.Л. [24], Куржанский А.Б. и многие другие известные математики.
Относительно немного известно работ по равномерному приближению многозначных отображений на некотором заданном множестве. Так в работе Никольского М.С. [13] рассматривается задача о равномерном приближении непрерывного многозначного отображения, заданного на отрезке, постоянным многозначным отображением.
Задача о приближении графика сегментной функции графиком полинома заданной степени на отрезке в метрике Хаусдорфа, которую рассматривал Сендов Б. [23] и др. (см. напр. [22]), также, по сути, относится к задачам нелокальной аппроксимации многозначных отображений.
В диссертации рассматривается следующая задача:
/M:=ft^v]maX \уг,к-Р*{А**к)>Рп(А>*к)-Уи) >А^п+1 ' (1)
где T = {t0
Требуется минимизировать максимальное по всем узлам сетки Г уклонение образов многозначного отображения (м.о.) Ф(-) от значений алгебраического полинома.
Функцию
f{Ayk):= тазх\уи ~Рп(А>h IРп(4h )-ylk } будем называть амплитудным модулем. Поскольку эта функция является выпуклой по А, то целевая функция в задаче (1) также является выпуклой.
2. Приведём сравнение задачи (1) с некоторыми известными задачами.
Задача о равномерном наилучшем приближении функции алгебраическим , полиномом заданной степени была сформулирована П.Л. Чебышёвым в 1854 году. Приведём формулировку этой задачи для дискретного случая ([3]).
Задана таблица значений некоторой функции ук ~ y{tk), є[0:ЛГ),
и зафиксировано натуральное число п - степень алгебраического полинома рп {А , г). Требуется минимизировать максимальное уклонение алгебраического полинома от значений дискретной функции
В случае если у^ к = у2^ Д є [О : JV], задача (1) вырождается в задачу
(2). Поэтому возникает естественная гипотеза: решение задачи (1) можно получить, осуществив чебышевскую интерполяцию ([3]) для функции, заданной в узлах сетки Т значениями
Эта гипотеза опровергается простыми примерами. Пример 1. Пусть п = 1, Т - { 0, 0.5, 1 },
Ф(0)= [052], <Р(0.5)- [0;2], Ф(і)= {2}. Тогда
Уо =1> У\ = 1> Уі =2-Решение задачи (1) единственно рх (У)=1, причём минимальное значение целевой функции равно 1. Решение задачи (2) для функции, заданной на сетке значениями (3), иное, а именно, p{c {t)=t + QJ5, причём /)=0.25 (рисі).
Рис. 1. Пунктирной линией отмечено ре-21 d ш /Р^ v)~t + ^-^5 шение задачи (2) для функции, заданной
Л (0 = 1
на сетке значениями (3).
Пример 2. В примере 1 исправим многозначное отображение в точке fi = 0.5, положив ф(0.5) = {і}.
Ясно, что решение задачи (2) для функции, заданной на сетке значениями (3), останется таким же, как и в примере 1, то есть pf (/) = / + 0.75, р = 0.25. А задача (1) в таком случае будет иметь бесконечно много решений рх (t,a)=at + \, а є [0;2] (рис.1), и ни одно из них не совпадает с полиномом рхс {t).
Известно, что решение задачи Чебышёва П.Л. при условии N >п единственно. Пример 2 одновременно показывает, что решение задачи (1) может быть неединственным.
Следует вспомнить также о других задачах теории приближений, например, о задаче об «ужах» или о наилучшем хаусдорфовом приближении графика сегментной функции отрезком графика алгебраического полинома заданной степени.
Сендов Б. в своей монографии «Хаусдорфовые приближения» ([23]) рассматривал непрерывную задачу о наилучшем приближении графика сегментной функции графиком алгебраического полинома заданной степени на отрезке
h(Gr0,Grpn{AA) > inf. f є [а; 6], <4)
h (А, В) — max^ supinf р{а, b); sup inf p{a, b) > -
ШАыв ь^в ^a J
расстояние Хаусдорфа между множествами А и В из R ,
р (w, v) = max{j Wj — Vj I, [w2 — v2 [ j -
расстояние между точками w = (wl, w2 ) и v = (v}, v2 ) из R в метрике Минковского,
ОгФ ={{t\yx{t)-yM\t ^AUGr pn{A^{{tiP^)lt ФМ) -отрезки графиков сегментной функции и алгебраического полинома на [а;Ь\, соответственно.
Рассмотрим дискретный аналог этой задачи. Под графиком дискретного м.о. ф(-), заданного на сетке Г, будем понимать множество
Gr
&рЛ4-)={{*кш>Рн(4'*))> ке[0**]}. ПримерЗ. Пусть JV = 2, и = 1, Г = { 0, 0.5, і},
Ф(0)=[0;4], Ф(0.5)= {2}, <Р(1)={0}. Графиком м.о. на сетке Т будет множество
СгФ = {(0;[0;4]),(0.5;2И1;0)}, а графиком полинома Pi{A,t)= aQ+axt - множество
Gr Pi(A,)^{(0;a0\(0.5;a0 + 0.5^),(1^+^)}.
Требуется найти алгебраический полином степени п = 1, который будет решением задачи (4) при t є Г. Решением этой задачи будет алгебраический полином 7?,c(f) = 3 - 4f. Расстояние Хаусдорфа между графиком этого полинома и графиком заданного м.о. при г є Г составляет 1 и совпадает с расстоянием Минковского между следующими точками графиков м.о.. и полинома, соответственно:
к{сгФ,Ріс(.р />((0;OU0.5;1))= р((0;0) (1-1)) = Д(0;4)(0;3)) =
= p((0.5;2]L (0.5;1)) = р((0.5;2), (0;3)) = р{{\;0\ (l;-l)) = p((l;0), (0.5;l)) = 1.
Решением задачи (1) является множество
Pi (t,a) = at + 2, ає[-4;0]? причём минимальное значение целевой
функции составляет 2. Очевидно, что ни один из полиномов указанного множества не совпадает с решением задачи (4).
Пример 4. Пусть TV = 2, л = 1, Г = { О, 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), C(U), 0(0,0), Р(0.5Д5), Л(1,1.5), 5(1,0), /5(0,-0.5).
Прямая ВР±ОС.
Множества решений задач (1) и (4) изображены на рис. 2. Решением задачи (1) является множество рх (f) = 0.75 + cr(f-l), ає[0;1.5], а реше-
ниєм задачи (4) является множество /7^)=1 + 0:(/-1), а є [1; 1.5]. Очевидно, что эти множества не содержат общих прямых линий.
В теории приближений хорошо известно понятие ужа (см. напр. [8]). Применим понятие ужа для дискретного случая.
Верхним (нижним) ужом м.о. Ф(-) называется алгебраический полином, p„{t) ip {t) 1 степени п, который удовлетворяет условиям:
(б) существует выборка Л := \tq < t <... < tq \с.Т, такая, что
-('„)='
Уїт *~четно, і \ Г ух к-четно, . .
Vi „ к — нечётно, —п^Чк' у, А; — нечётно. Заметим, что об ужах имеет смысл говорить только в том случае, если N>n,y2k >ylk, Vke[0:N].
Пример 5. Пусть N = 2, и = 1, Г = {0,0.5,1},
ф(0) = [0;і], Ф(0.5) = [0;1],
Верхним ужом на выборках Лх ={0,1} и Л2 ={0.5,1} будет полином p\(t)=l. Для выборки Л3 ={0,0,5 } верхнего ужа не существует.. Нижний уж существует только на выборке Лх, р (/)=1.51. Ни один из
ужей не является решением задачи (1) (рис.3).
Нижний и верхний ужи
Рис, 3.
Решение задачи (I)- полином
Р\ \Ч= 0-5/ + 0.375, совпадает с решением задачи (2) для амплитудной функции #>о О^-
РешениеМ задачи (1) является полином р1 (ґ) = 0.5 ґ +0.375, а минимальное значение целевой функции в задаче (1) составляет 0.625. Это решение совпадает с решением задачи Чебышёва (2), если в качестве при-
ближаемой функции взять функцию <р0(;), заданную в узлах дискретной сетки Т значениями
?о(0) = 1. р0(0.5) = 0,р0(1)=1.5. В дальнейшем такие функции будем называть амплитудными.
3. Диссертация состоит из двух глав, содержащих 10 параграфов. Приведём основные результаты исследования задачи (1).
Обозначим через
//= inf р(А), Зг=[4єЛ"+1 ;р(А)=р*}.
AzR"+l
Пусть, далее,
У2,к~У\л
т := max
кє[0:Х] 2
В первой главе диссертации исследуются свойства решения задачи
(1)-
В 1 вводятся основные обозначения, а также приводится ряд фактов, следующих непосредственно из вида целевой функции задачи (1), используемых в дальнейшем.
В 2 даётся описание множества решений задачи (1) при N <п.
Теорема 2.1. Пусть N
системе уравнений
aQ+a^k+... + antk = + ак\т
(5)
где сск є[-1;і], *є[0:ЛГ]. А именно, любое решение А* = ^д0*,ах*,..,,ал*] задачи (1) является решением системы (5) при некотором наборе параметров aAe[-l;l], ke\0:N] и, наоборот,
для любого набора параметров ак є [-1; і], к є [О: JV], решение системы (5) является решением задачи (1).
* При этом р =т.
В 3 обсуждается вопрос о существовании решения задачи (1). Доказано, что задача (1) всегда имеет решение, причём множество решений задачи (1) является выпуклым и замкнутым, а при N > п оно, кроме того, ограничено.
Один из основных результатов диссертации - необходимые и достаточные условия решения. Они получены в 4. Чтобы сформулировать соответствующий факт, введём обозначения.
Базисом <у назовём (гг + 2) - точечную подсистему узлов сетки Т вида
tT = {tM
значениями
—четно, —нечётно.
^.'лЬ
y2jyk-четно, у^ і,Л~ нечётно,
tj є а, к є[0:и + і].
JbA=Po(5VjJ
Ухьтъ№н)
Рис.4. Амплитудные функции
'л
Если в качестве приближаемой функции в задаче П.Л.Чебышёва (2) взять амплитудную функцию, эта задача запишется в виде
ю і
р* (сг) := min i pi (At а), і є 0:1,
(6)
Pi (A, a) := k max І щ (a,tJk )- Pn(л,'л )| -
= [0:д+і]
Задачи (6) будем называть также амплитудными а -подзадачами задачи (1).
Теорема 4.1. (необходимое и достаточное условие
__ ^ п 1
решения). Для того чтобы вектор А єК являлся решением задачи (1), необходимо и достаточно, чтобы выполнялось хотя бы одно из условий
(а) р\А*)-т\
(б) 3 сг*: p\A*j= pi \ar* J, где і = О или / = 1.
Поясним приведённое утверждение. Равенство (а) означает, что ал-гебраический полином степени п с вектором коэффициентов А «проходит» через середины максимальных по длине отрезков, являющихся образами м.о. (рис.5).
Рис.5. Имеем
Уг,<а-У\9-У2,\-У\,\ =2от'
Ра\А ''о/= 2 '
(л* Л Уи+Угл
РМ '«)= J
Если выполняется условие (б), то вектор А будет решением соответствующей амплитудной сг- подзадачи (7).
В 5 рассматривается вопрос о единственности решения задачи (1), являющийся одним из самых трудных по доказательству в диссертации.
Теорема 5.2. (критерий единственности решения). Для того чтобы задача (1) имела единственное решение, не-
обходимо и достаточно, чтобы выполнялось хотя бы одно из условий:
(а) множество Z := -j к є [О: N]: —— — = р
содержит не менее чем (я +1) элемент; (/?) 3 а : р* = р* (сг* J, i = 0 или г = 1.
Утверждение (а) означает, что полином наилучшего приближения для задачи (1) «проходит» через середины максимальных по длине отрезков, являющихся образами м.о., и таковых не менее чем (« +1) штук.
Утверждение (/?) теоремы 5.2 совпадает с условием (б) теоремы 4Л
в предположении, что вектор А является решением задачи (1).
В 6 решается вопрос о распознавании крайних точек множества решений задачи (1) и даётся оценка их количества.
Теорема 6.1 (критерий распознавания крайних точек). Вектор А є 9 является крайней точкой множества решений 9? тогда и только тогда когда значение амплитудного модуля совпадает с минимальным значением целевой функции задачи (1)в (л + l) различных узлах сетки Г, то есть
3 /={v<-<'
Если решение задачи (1) единственно, то оно само будет крайней точкой. Учитывая определение функции /(-,), мы имеем в (7) систему из (я +1) линейных уравнений относительно (« + 2) неизвестных (неизвестны компоненты вектора А и оптимальное значение целевой функции р ).
В 7 приводятся достаточные условия, при выполнении которых решение задачи (2) для функции, заданной в узлах сетки значениями (3),
является одновременно решением задачи (1). А при N = п +1 эти условия являются и необходимыми.
Во второй главе диссертации на основании полученных фактов предлагается алгоритм решения задачи (1).
В 8 приводится общая схема решения задачи, основанная на переборе базисов и выборок (п +1) различных точек сетки Т.
В 9 приводится алгоритм решения задачи для случая N = п +1. В этом случае решением (или одним из решений) задачи (1) будет либо решение одной из амплитудных а — подзадач (6), либо специально подобранная выпуклая комбинация решений этих подзадач.
В 10 излагается монотонный алгоритм для случая | М \ > п + 2. По
аналогии с известным алгоритмом Валле-Пуссена, происходит переход от одного базиса а к другому. Каждый раз выбирается одна из амплитудных а-подзадач, организуется переход к следующему базису и указывается та из амплитудных подзадач нового базиса, минимальное значение целевой функции которой больше, чем у предыдущей выбранной подзадачи, и которая будет использоваться для дальнейшего анализа.
Результаты исследования опубликованы в работах [25] - [33] и докладывались на научных семинарах по негладкому анализу кафедры математической экономики (2000 — 2004 гг.), на весенних научных конференциях механико-математического факультета (2000 — 2004 гг.), на Саратовских зимних школах-конференциях «Современные проблемы теории функций и их приложения» (2002, 2004 г.), на 24-й конференции молодых учёных МГУ (Москва, 2003), на школах - конференциях «Современные методы теории функций и смежные проблемы» (Воронеж, 2003), «Теория функций, её приложения и смежные вопросы» (Казань, 2003), на научном семинаре кафедры теории функций и приближений (май, 2004 г.), объединённом научном семинаре по дискретной математике и математической
кибернетике механико-математического факультета и факультета компьютерных наук и информационных технологий СГУ.
Необходимые и достаточные условия решения
Утверждение (а) означает, что полином наилучшего приближения для задачи (1) «проходит» через середины максимальных по длине отрезков, являющихся образами м.о., и таковых не менее чем (« +1) штук.
Утверждение (/?) теоремы 5.2 совпадает с условием (б) теоремы 4Л в предположении, что вектор А является решением задачи (1). В 6 решается вопрос о распознавании крайних точек множества решений задачи (1) и даётся оценка их количества. Теорема 6.1 (критерий распознавания крайних точек). Вектор А є 9 является крайней точкой множества решений 9? тогда и только тогда когда значение амплитудного модуля совпадает с минимальным значением целевой функции задачи (1)в (л + l) различных узлах сетки Г, то есть Если решение задачи (1) единственно, то оно само будет крайней точкой. Учитывая определение функции /(-,), мы имеем в (7) систему из (я +1) линейных уравнений относительно (« + 2) неизвестных (неизвестны компоненты вектора А и оптимальное значение целевой функции р ). В 7 приводятся достаточные условия, при выполнении которых решение задачи (2) для функции, заданной в узлах сетки значениями (3), является одновременно решением задачи (1). А при N = п +1 эти условия являются и необходимыми. Во второй главе диссертации на основании полученных фактов предлагается алгоритм решения задачи (1). В 8 приводится общая схема решения задачи, основанная на переборе базисов и выборок (п +1) различных точек сетки Т. В 9 приводится алгоритм решения задачи для случая N = п +1. В этом случае решением (или одним из решений) задачи (1) будет либо решение одной из амплитудных а — подзадач (6), либо специально подобранная выпуклая комбинация решений этих подзадач. В 10 излагается монотонный алгоритм для случая М \ п + 2. По аналогии с известным алгоритмом Валле-Пуссена, происходит переход от одного базиса а к другому. Каждый раз выбирается одна из амплитудных а-подзадач, организуется переход к следующему базису и указывается та из амплитудных подзадач нового базиса, минимальное значение целевой функции которой больше, чем у предыдущей выбранной подзадачи, и которая будет использоваться для дальнейшего анализа.
Результаты исследования опубликованы в работах [25] - [33] и докладывались на научных семинарах по негладкому анализу кафедры математической экономики (2000 — 2004 гг.), на весенних научных конференциях механико-математического факультета (2000 — 2004 гг.), на Саратовских зимних школах-конференциях «Современные проблемы теории функций и их приложения» (2002, 2004 г.), на 24-й конференции молодых учёных МГУ (Москва, 2003), на школах - конференциях «Современные методы теории функций и смежные проблемы» (Воронеж, 2003), «Теория функций, её приложения и смежные вопросы» (Казань, 2003), на научном семинаре кафедры теории функций и приближений (май, 2004 г.), объединённом научном семинаре по дискретной математике и математической кибернетике механико-математического факультета и факультета компьютерных наук и информационных технологий СГУ. В первой главе обсуждаются основные свойства решения задачи о наилучшем приближении дискретного многозначного отображения алгебраическим полиномом.
О крайних точках множества решений
Если S = ! и... W 5„, то разбиение завершено. Если 5 \{5і u.-.u +i , полагаем р:=р + \. Если при этом wv 0 Z, переходим к шагу 4. Если же wv є Z, переходим к шагу 5. Приведём обоснование процедуры. Если w,,..., w/ є Z, то каждый такой индекс составляет отдельное множество Sk, к є [і:/] (шаги L-2). Поскольку ZJ « +1, ввиду (5.39), мы обязательно перейдём к шагу 3. На шаге 3 определяется число і0 є {l»2}, и тем самым указывается порядок, при котором амплитудный модуль f\A ,-J поочерёдно принимает значение, совпадающее то со значением fio\A ,-J, то со значением /з_/_ \Л ,) при переходе от одного множества разбиения к другому. Для этого сначала отыскивается минимальный элемент р множества S, не принадлежащий множеству Z. Пусть, например р - нечётно и /j 4 ,wv J f2\A ,wv J. Тогда из (5.42) находим /0 -1. Ввиду (5.44), теперь всё множество индексов Sр = {wv ... wv +и } удовлетворяет неравенству f\A\ w/ )= /, [Л\WJ ) /2 (A ,w,), V / є [vp, vp + ир]. В процессе построения разбиения указанный порядок чередования сохраняется, в силу (5.45), (5.46), то есть на множествах разбиения Sp с нечётными номерами р имеем равенства /\А ,wiJ=f.\A ,wtJ, V / є [v _, v + ир ], а на множествах S „ с чётными номерами р имеем равенства f\A 9Wif=/24\A ,w/) V Ie[vp,vp +up \. Отсюда следует, что разбиение удовлетворяет свойству 2). Очевидно, что подмножества разбиения имеют вид (5.41). По построению, справедливо свойство 3). Свойство 4) следует из (5.46). Нетрудно увидеть, что свойство 5) также будет выполняться. 4. Теперь докажем основной результат этого параграфа — критерий единственности решения задачи (1.1). Теорема 5.2. (критерий единственности решения). Для того чтобы задача (1.1) имела единственное решение, необходимо и достаточно, чтобы выполнялось хотя бы одно из условий: (a) Z n + l; (ft) 3 а :р = pi [a ), і = 0 или / = 1. Доказательство, Достаточность. Пусть А є 9Ї и выполняется (а). Покажем, что А - единственное решение задачи (1.1). Согласно утверждению 4.2, значением полинома наилучшего приближения для задачи (1.1) в любой точке tk с индексом eZ, является середина отрезка, являющегося образом м.о. в точке tk. По условию, таких индексов не менее чем (и +1). Таким образом, полином наилучшего приближения степени п интерполирует (и + 1) различные точки, а, следовательно, он единствен. Пусть теперь выполняется {ft), то есть За :р pt \рг 1, где і є 0:1. Поскольку А є9ї, то р\А )= р . В этом случае выполняется условие (б) теоремы 4.1. В соответствии со следствием 4.2, получаем, что вектор А является решением амплитудной т - подзадачи (1.8), то есть РІ\А ,сг )= р (ег ). Согласно теореме 2.1 из [3, с. 14], решение задачи П.Л. Чебышева единственно и, следовательно, Р1{АУ) Р\А\ У \ V А Я \АФА\ (5.47) Из равенств РІ\А ,& )= р; \сг J, p \pr )= p , (1.23) и (5.47) вытекает со отношение р(А) Рі(А,а ) РІ(Л\СГ )= р (а)= р , V A zRn+l ,А А . Таким образом, получили Р(А) Р{А \ УАЄИП+1,А А\ Это и означает, что решение А задачи (1.1) единственно. Необходимость. Пусть вектор А является единственным решением задачи (1.1). Предположим, условие (а) не выполняется, то есть Z « + 1 (возможно Z = 0). Покажем, что выполняется условие (/?). В соответствии со следствием 5.1, S п + 2. Применяя описанную выше процедуру, произведём разбиение множества S вида (5.40) на максимальное количество следующих друг за другом непустых непересекающихся подмножеств Si,...ySr, удовлетворяющих свойствам 1) - 5). 1. Сначала рассмотрим случай, когда г п + 2. Возьмём в качестве у множество точек {tj tj ,.. tj } таких, что Jk Sk+\ к є [Определение 6.1. Элемент АеХ называется крайней точкой множества X, если в множестве X не существует элементов АЇ7 А2, А1Ф Аг и а є (О, і) таких, что А = аАх+(\.-а)А2. (6.1) Если N п, то множество решений задачи (1.1) замкнуто, выпукло, неограниченно. Множество решений системы (2.1), а значит, и задачи (1.1), для каждого фиксированного набора параметров аАє[-1;і], ke[0:N] представляет собой линейное многообразие размерности п — N, а совокупность решений - это объединение таких линейных многообразий. Следовательно, это множество не имеет крайню: точек. Далее считаем N n. Обозначим ЕІ Я) множество крайних точек множества 9. По следствию 3.1, множество решений задачи (1.1) Щ является выпуклым и компактным. Следовательно, Е(їН) Ч 0 (см., например, [19], с. 184). 2. Докажем необходимое и достаточное условие принадлежности не которого решения задачи (1.1) множеству крайних точек Е(р{). Теорема 6.1 (критерий распознавания крайних точек). Вектор А єШ является крайней точкой множества решений 93 тогда и только тогда когда значение амплитудного модуля совпадает с минимальным значением целевой функции задачи (1.1) в (и + 1) различных узлах сетки Г, то есть 3 A = {t% ... tJ: f{A\qk)=p\ Ve[0:«]. (6 2 Доказательство. Достаточность. Пусть выполняется условие (6.2). Если решение единственно, то оно само и является крайней точкой множества решений рассматриваемой задачи. Пусть ] Ж j = оо. Покажем, что А є (). В силу следствия 5Л, 1 \Z\ п +1. Возьмём произвольно АХіА2 єй: Ах А2. Поскольку \1\Д ) =и + 1, то 3 кєї\А у. /\Ах,к)ф/\А2,к)- Без потери общности считаем, что f(Alfk)-f(A2,k) 0. (6.3) Поскольку Ах и Аг - решения задачи (1.1), имеем /(4, ) / \іє1:2. (6 4) Из линейности функций /і(А,к),ієІ:2 по первому аргументу, вытекает выпуклость амплитудного модуля f(A, к) по первому аргументу. Учитывая (6.3), (6.4), для любого а є ( 0; 1) оценим величину /(а41+(і-«К, ) 1, )+(і-а)/(і42і ) = f{A2,k)+a{f{Altk)-f(A2,k)) p\ Таким образом получили f(aAl + (l -а)А2 ,к) р\ (6-5) Далее, ввиду (6.2), f[A , kj= р . Следовательно А ФаАх +(1-а)А2. (6.6) Последнее, в силу произвольности выбора АХ,А2 є її, or є ( 0; 1), означает, что А является крайней точкой множества решений 9Ї.
Схема алгоритма общего решения задачи
Если равенство (9.7) не выполняется, переходим к шагу 2. Шаг 2. Применяя для амплитудной функции рх чебышевскую интерполяцию в узлах 4Дє[0:л + і] ([3]), находим решение Аг амплитудной а - подзадачи (1.8) для і — 1. Если выполняется равенство тогда, как и на предыдущем шаге, получаем р = p(At) и делаем вывод о том, что вектор А\ будет искомым, причём единственным, решением задачи (1.1). Работа алгоритма завершается. Если равенство (9.8) также как и (9.7), не выполняется, то Z Ф 0 по теореме 4.1, переходим к шагу 3. Шаг 3. Подсчитываем величину а в соответствии с (9.1) и строим вектор Аа =(l — CC)AQ +ССА]. В силу теоремы 9.1, этот вектор будет решением задачи (1.1). Если требуется отыскать только частное решение задачи (1.1), на этом алгоритм завершает свою работу. Для получения общего решения задачи (1.1) следует обратиться к шагу 6 процедуры, описанной в предыдущем параграфе. При решении классической задачи П.Л. Чебышева, например, по ал горитму Валле-Пуссена, ([3]), происходит переход от одной базисной подза дачи к другой с тем, чтобы максимальное уклонение полинома от значения дискретной функции на очередном базисе каждый раз увеличивалось. Таким образом, за конечное число шагов алгоритм приводит к «экстремальной под задаче» (оптимальное значение целевой функции для такой подзадачи макси мально, а её решение является одновременно решением исходной задачи). Результаты предыдущего исследования позволяют построить решения задачи (1.1) через конечное число шагов. В общем случае это весьма трудоёмкая процедура. Возникает естественный вопрос, при каких условиях возможен монотонный алгоритм решения задачи. Монотонность понимается в том смысле, что перебор базисов осуществляется так» что на каждой итерации max{/i0 ( тк+і), Лj (crk+i)} max{/i( {ak \ h\ (crk)}. Это делает алгоритм более рациональным по сравнению с перебором всех базисов. В этом параграфе такой алгоритм предлагается для случая \М\ п + 2. 2. Приведём используемую алгоритмом процедуру преобразования ба зиса. Пусть CFCZT - произвольный базис вида (1.4). Находим /3 є {0,1} из условия где Ар{а) - решение соответствующей амплитудной т-подзадачи (1.8). Определим индекс к0 є [0:N ] из условия Опишем S -преобразование базиса : т r [3, C.28J Вариант З Рассмотрим 3 варианта расположения точки tk : Для каждого варианта расположения точки tk преобразование S определяется по-своему. Вариант 1. tj tk t, . Пусть целое число и таково, что Рис. 10.1. Вариант 1 расположения точки к В таком случае полагаем jt := jt; IФ и; IФ о +1; V / є [О: п +1]. Если выполняются равенства f[A0 ( т\ kQ )= yUo - pn (Ap (a), tk(j ), то осуществляем присвоение: ju := k0, j0+l := ju+l. Если ни (10.4), ни (10.5) не выполняются, полагаем tj := tj , ju+] := k0. Далее, полагаем Вариант 2. tk tj . Определяем jQ := kQ. Если выполняются равенства (10.4) или (10.5) для и = 0, то полагаем jt = jt, V / є [і: и +1], и осуществляем присвоение (10.6). Если (10.4) и (10.5) для о = 0 не выполняются, полагаем Л:=Ум» v /є[і:и + і]и fi з 1-0. (10-7) Вариант 3. tk tj . Определяем jn+i := k0. Если выполняются равенства (10.4) или (10.5) для и = п +1, то полагаем J{ :=jt, VІ є [о: и], и осуществляем присвоение (10.6). Если (10.4) и (10.5) при и = п + 1 не выполняются, полагаем Л-у/+1,У/е[0:п]иД:=1.
Монотонный алгоритм решения для случая \М\
Пусть теперь выполняется условие (б) теоремы 4.1 для сг-подзадачи, то есть р (сг) = hp{a). Поскольку вектор Ар{а) не является решением задачи (1.1), то р[Ар(сг)) р . Из (1.24), р рр (а), следовательно, Жі ЛАЛ М )= p{Afi (")) Р М = hft М= Р{лр ( г\ ")= ке \0:N (10.28) Из (10.28) получаем max f\Ap (с), к J hp (сг ). Отсюда и из (10.3) вытекает (10.8). 2) Пусть теперь вектор Ар (сг) не является решением а -подзадачи. В силу теоремы 4.1 и утверждения 4.1, применённых сг -подзадаче, имеем Поскольку Z — 0, то У) Покажем, что Действительно, если 1( т) с; М, то По теореме 5.2, решение сг -подзадачи единственно и, по следствию 4.3, само решение А удовлетворяет /» \ у\ ,. +у2 і. г і (10.31) Рассмотрим случай р = 0. Учитывая (10.2), запишем соотношения (1.9) для / = 0: h {сг)=j/2 , - р„ (А0 (СГ) Л ) к - четно, \(сг) = /7ДЛ0(о-),ГЛ)-;;1іЛ, к-нечётно, (10.32) Л: є [0: и + l], / (сг) = р0 (сг). Учитывая (10.29) и (10.30), перепишем (10.32) в виде Рп (-4) М л )= Уг,ік - ho Н У2,л " 2 я 2 ,л - чйя" Рп (Л (о") л )= ДЛ + К (сг) Ад + ХЛ 2 1Л » - счётно, Л: Є [О : п + l]. Отсюда получаем pAM\tJ yiJkly2Jk к-чётно, 2 є[0:я + і]. О0-33) Рп \Ао (&) jk I z у - нечетно, Из (10.31) и (10.33) следует, что различные алгебраические полиномы р„ \AttJ и рп [Ар ip\t) степени п имеют (п +1) общих точек, что невозможно. Случай р = 1 рассматривается аналогично. 105 4) Итак, 3 k є M \ І [с). Отсюда, ввиду (1.10), (1.11), получаем равенство Утверждение доказано. 5. Приведём алгоритм решения задач (1.1), для которых выполняется неравенство (10.20). Шаг 1. Подсчитаем величину т, определённую в (1.10), и найдём множество М из (1.11). Пусть М - упорядоченное множество вида М — \к1 ... км г. Переходим к шагу 2. Шаг 2. Берём М = {кх ... кп+1} и решаем относительно А систему (10.22). Если выполняется равенство то А будет единственным решением задачи (1.1). При этом р = /я, Z = М. Алгоритм завершается. Если равенство (10.24) не выполняется, то есть имеет место (10.21), то, в силу утверждения 10.1, Z = 0. Берём базис сг := {/0 ... tn+l} с Г и переходим к шагу 3. 106 ШагЗ. Для амплитудных функций (1.7) текущего базиса а осуществляем чебышевскую интерполяцию и находим решения задач (1.8). Определяем /З в соответствии с (10.1). Проверяем равенство p{A0{ r))=hp( j). (10.38) Если равенство (10.38) выполняется, в силу теоремы 4.1, вектор А я ( т) будет решением задачи (1.1). Алгоритм завершается, 9 = [Ар (а)}. Пусть равенство (10.38) не выполняется, то есть имеет место (10.24). Применяя процедуру % из 4 (п. 4), проверяем, является ли вектор Ар ( х) решением задачи. Если является, то алгоритм завершается. Если вектор Ар(а) не является решением задачи (1.1), переходим к шагу 4. Шаг 4. Находим индекс из условия (10.3). Осуществляем S - преобразование базиса а и переходим к базису а = { tj ,.. t-j . Переходим к шагу 3. Поскольку решение задачи (1.1), для которой выполняется (10.20), единственно, то либо выполняется условие {а) теоремы 5.2, и решение будет получено на шаге 2, либо выполняется условие (/?) теоремы 5.2, то есть решение задачи (1 Л) будет являться одновременно решением одной из амплитудных подзадач (1.6). Следовательно, неравенство (10.9) означает, что Рв ( ) Р0 У7)- Таким образом обеспечивается монотонность алгоритма и более рациональный перебор базисов (который в данном случае означает выбор нового базиса и выбор одной из амплитудных подзадач на новом базисе) по сравнению с общим методом.
