СОДЕРЖАНИЕ
Введение____________________________________________________ 3
ГЛАВА I. СВОЙСТВА РЕШЕНИЯ ЗАДАЧИ__________________________ 15
§ 1. Постановка задачи_________________________________ 15
§ 2. Решение задачи для случая N < п______________________ 21
§ 3. О существовании решения задачи_______________________ 25
§ 4. Необходимые и достаточные условия решения____________ 29
§ 5. Критерий единственности решения______________________ 48
§ 6. О крайних точках множества решений___________________ 71
§ 7. Случаи сведения к задаче П.Л. Чебышева_______________ 83
ГЛАВА II. АЛГОРИТМ РЕШЕНИЯ________________________________ 89
§ 8. Схема алгоритма общего решения задачи________________ 89
§ 9. Алгоритм решения для случая N = п +1_________________ 93
§10. Монотонный алгоритм решения для случая \М\ > п + 2 97
Библиографический список_______________________________ 108
ВВЕДЕНИЕ
1. Задачи по аппроксимации и оценке многозначных отображений математическими объектами простой структуры находят обширные приложения в естествознании, в том числе в самой математике, и представляют один из разделов негладкого анализа.
Локальными аппроксимациями многозначных отображений занимались многие отечественные и зарубежные математики (Пшеничный Б.Н. [17] - [18], Демьянов В.Ф. [2] - [5], Рубинов А.М. [20] - [21], Никольский М.С., Половинкин Е.С. [15] - [16], Минченко Л.И. [12], Обен Ж.-П. [14], Гороховик В.В. [1] и др.).
К задачам, имеющим нелокальный характер, относятся внешнее и внутреннее эллипсоидальное оценивание многозначных отображений. Эллипсоидальными оценками множеств достижимости динамических систем занимались Черноусько Ф.Л. [24], Куржанский А.Б. и многие другие известные математики.
Относительно немного известно работ по равномерному приближению многозначных отображений на некотором заданном множестве. Так в работе Никольского М.С. [13] рассматривается задача о равномерном приближении непрерывного многозначного отображения, заданного на отрезке, постоянным многозначным отображением.
Задача о приближении графика сегментной функции графиком полинома заданной степени на отрезке в метрике Хаусдорфа, которую рассматривал Сендов Б. [23] и др. (см. напр. [22]), также, по сути, относится к задачам нелокальной аппроксимации многозначных отображений.
В диссертации рассматривается следующая задача:
p(A)v= max max {y2k-pn(A,tk),p„(A,tk)-ylk} > inf О)
ke[0:N\ АеR
где Г = {г0 </, с...</„}, ф{<к)=[у\л 1УгЛ Уг.к *е[0:ЛГ],
p„(A,t) = a0 +alt + ... + a„t", А = (a0,a],...,a„ )eR"+'.
3
Требуется минимизировать максимальное по всем узлам сетки Т уклонение образов многозначного отображения (м.о.) Ф(-) от значений алгебраического полинома.
Функцию
/{А, к)шах{у2>* - рп (А, !к ) р„ (А, 1к) - у1к }
будем называть амплитудным модулем. Поскольку эта функция является выпуклой по А, то целевая функция в задаче (1) также является выпуклой.
2. Приведём сравнение задачи (1) с некоторыми известными задачами.
Задача о равномерном наилучшем приближении функции алгебраическим . полиномом заданной степени была сформулирована ПЛ. Чебышевым в 1854 году. Приведём формулировку этой задачи для дискретного случая ([3]).
Задана таблица значений некоторой функции ук = >>(/*), &е[0:7У], г0 <с... <и зафиксировано натуральное число п - степень алгебраического полинома рп(А , г). Требуется минимизировать максимальное уклонение алгебраического полинома от значений дискретной функции
р*^^ЫУ1~рМ- (2)
В случае если у^к — У2,к : ^]> задача (1) вырождается в задачу
(2). Поэтому возникает естественная гипотеза: решение задачи (1) можно получить, осуществив чебышевскую интерполяцию ([3]) для функции, заданной в узлах сетки Т значениями
У\,к+Уг,к , Гл О)
У к > ке[0^\.
Эта гипотеза опровергается простыми примерами.
Пример 1. Пусть п - 1, Т = { 0, 0.5, 1 },
Ф(0) = [0;2], <*>(0.5) = [0;2 ], Ф{\) = {2}.
Тогда
4
Уо =1> ^1 =1» У2 =2*
Решение задачи (1) единственно р{ (/) = 1, причём минимальное
значение целевой функции равно 1. Решение задачи (2) для функции, за-
Пример 2. В примере 1 исправим многозначное отображение в точке Г, = 0.5, положив Ф(0.5)={1}.
Ясно, что решение задачи (2) для функции, заданной на сетке значе-
р - 0.25. А задача (1) в таком случае будет иметь бесконечно много реше-
Известно, что решение задачи Чебышева П.Л. при условии N > п единственно. Пример 2 одновременно показывает, что решение задачи (1) может быть неединственным.
Следует вспомнить также о других задачах теории приближений, например, о задаче об «ужах» или о наилучшем хаусдорфовом приближении графика сегментной функции отрезком графика алгебраического полинома заданной степени.
Рис. 1. Пунктирной линией отмечено решение задачи (2) для функции, заданной на сетке значениями (3).
о
ниями (3), останется таким же, как и в примере 1, то есть р\сН(() = / + 0.75,
ний /?,*(*,а) = а/ +1, а е[0;2] (рис.1), и ни одно из них не совпадает с по линомом р,сЛ(/).
5
Сендов Б. в своей монографии «Хаусдорфовые приближения» ([23]) рассматривал непрерывную задачу о наилучшем приближении графика сегментной функции графиком алгебраического полинома заданной степени на отрезке
h(Gr0,Grpn(A,•))-------> inf t, te[a;b]f (4)
где
AeRn+'
h(AyB)= max 4 sup inf p(a, b); sup inf p(ay b) > -
ь*ваеА J
4
Л
расстояние Хаусдорфа между множествами А и В из R ,
p{w,v) = max{| и-, - V, |,|w2 — v2 I} -
расстояние между точками w = (w,,>v2) и v = (vl,v2) из R2 в метрике Минковского,
О ф = {('. [ У\ (?)• У г (01 )>' 6 [°> Ь\}иСг р„ (А,) = {(t, рп (А, /)), / е [а; Ь)} -
отрезки графиков сегментной функции и алгебраического полинома на [a;b], соответственно.
Рассмотрим дискретный аналог этой задачи. Под графиком дискретного м.о. </>( •), заданного на сетке Т, будем понимать множество
Gr<P = { (tk,[yu;у2к ]), £е[0: JV]}, а под графиком полинома - множество
» Рп (А,) = {(Г*; Р„ {А,1к )), * е [О: N]}.
Пример 3. Пусть N = 2, п = 1, Т = { 0, 0.5, 1 },
Ф{0) = [0;4 ], Ф(0.5) = {2}, Ф(1) = {0}.
Графиком м.о. на сетке Т будет множество
Gr0 = {( 0; [0; 4]), (0.5;2), (l;0)}, а графиком полинома P\(A,t)=a0 + axt - множество
Gr /?,(/*,•) = {(0;я0), (0.5;а0 +0.5a,),(l;a0 +а,)}.
6
Требуется найти алгебраический полином степени п = 1, который будет решением задачи (4) при (еТ. Решением этой задачи будет алгебраический полином р,с(г) = 3-4г. Расстояние Хаусдорфа между графиком этого полинома и графиком заданного м.о. при t еТ составляет 1 и совпадает с расстоянием Минковского между следующими точками графиков м.о.. и полинома, соответственно:
ь[сгФ,рхс{-))= р((О;ОМ0.5;1))= р((0;0>(1;-1))= р((0;4>(0;3)) =
= р((0.5;2)1(0.5;1))= Д0.5;2>(0;3))= Д(1;0И1;-1)) = р((1;0>(0.5;1)) = 1.
Решением задачи (1) является множество
/?1*(г,сг)= а г + 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) является множество прямых {Ж}, где 2 - любая точка отрезка ПМ.
Решением задачи (4) является множество прямых {ХС}, где X - любая точка отрезка ОЭ.
Минимальное значение целевой функции в задаче (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,1.5), 5(1,0), 0(0,-0.5). Прямая ВРXОС.
Множества решений задач (1) и (4) изображены на рис. 2. Решением задачи (1) является множество р,*(г)= 0.75 + а(/-1), ае[0;1.5], а реше-
7
ниєм задачи (4) является множество р,с(/) = 1 + а(г-1), ає[і;1.5]. Очевидно, что эти множества не содержат общих прямых линий.
В теории приближений хорошо известно понятие ужа (см. напр. [8]). Применим понятие ужа для дискретного случая.
Верхним (нижним) ужом м.о. <£>(•) называется алгебраический полином, рп(/) ) степени и, который удовлетворяет условиям:
(а) У\,к ^ Рп ('<) ^ У2,к • У\,к ^ р„ (ік ) ^ У2.к • V к є [0: N],
(б) существует выборка Л := < /^ <...</^)с7’, такая, что
рЛ<МУ2'\к~ЧётН°' Р,иАУ]'Чк\~ЧётНО' *е[°:и].
У\лк, * “ нечетно у —п'Чк' у 2 к — нечетно у
Заметим, что об ужах имеет смысл говорить только в том случае, если N > пу у2к > ух к, V к є [О: ЛГ].
Пример 5. Пусть N = 2, п = 1, Г = {0,0.5,1},
Ф(0)=[0;1],Ф(0.5) = [0;1], Ф(і)= [ 1;1.5 ].
Верхним ужом на выборках Лх ={0,1} и Л2 ={0.5,1} будет полином рх(г)&1. Для выборки = {0,0.5} верхнего ужа не существует.. Нижний уж существует только на выборке ЛХу р (/)=1.5/. Ни один из ужей не является решением задачи (1) (рис.З).
Нижний и верхний ужи
о
▲ А . /
і ' к.»»««»..
►
Рис. 3.
0.5
Решение задачи (1)-полином р/(0 = 0.5/ + 0.375 ,совпадает
с решением задачи (2) для амплитудной функции ф0(’).
Решением задачи (1) является полином рх (г) = 0.5/ + 0.375, а минимальное значение целевой функции в задаче (1) составляет 0.625. Это решение совпадает с решением задачи Чебышева (2), если в качестве при-
8
ближаемой функции взять функцию <p0Q, заданную в узлах дискретной сетки Т значениями
В дальнейшем такие функции будем называть амплитудными.
3. Диссертация состоит из двух глав, содержащих 10 параграфов. Приведём основные результаты исследования задачи (1).
Обозначим через
р' = Ы p(A)f<R = {a eRn+l:p(A)=p*}.
AeRn"
Пусть, далее,
Уг,к ~ У\,к
т :=
:= max -А € [0:/V ]
2
В первой главе диссертации исследуются свойства решения задачи
(і).
В § 1 вводятся основные обозначения, а также приводится ряд фактов, следующих непосредственно из вида целевой функции задачи (1), используемых в дальнейшем.
В § 2 даётся описание множества решений задачи (1) при N <п.
Теорема 2.1. Пусть N й п. Задача (1) эквивалентна следующей линейной относительно компонент (а0, аап ) вектора А системе уравнений
, п У\,к+У2,к , [ У2,к~У\,к
a0+a\tk+... + antk =----------- + ак\ т--------
(5)
к е [ 0: N ],
где аАе[-1;1], £е[0:А]. А именно, любое решение А* = (а0*>т*»•••>оп) задачи (1) является решением системы (5) при некотором наборе параметров а*е[-1;1], £е[0:А] и, наоборот,
9
- Киев+380960830922