Содержание к диссертации
Введение
1 Двойственность в задаче Дельсарта 24
1.1 Прямая и двойственная задачи Дельсарта. Теоремы двойственности 24
1.2 Сведение задачи к системе нелинейных алгебраических уравнений 33
1.3 Оценки параметров экстремальных функций и мер 43
2 Алгоритмы и их реализация 47
2.1 Интервальная арифметика и интервальная теорема Штурма 47
2.2 Сведение полиномиальных задач бесконечномерного линейного программирования к задачам SDP 52
2.3 Решение задачи Дельсарта с помощью построения базиса Гребнера 60
2.4 Программа в Maple построения базиса Гребнера системы (1.2.2) 64
3 Задача Дельсарта в конкретных размерностях 66
3.1 Задача Дельсарта в трехмерном пространстве 66
3.2 Результаты для новых больших размерностей 82
3.3 Решение задачи Дельсарта в размерности 173 86
Список литературы 92
Публикации автора по теме диссертации
- Сведение задачи к системе нелинейных алгебраических уравнений
- Оценки параметров экстремальных функций и мер
- Сведение полиномиальных задач бесконечномерного линейного программирования к задачам SDP
- Результаты для новых больших размерностей
Сведение задачи к системе нелинейных алгебраических уравнений
Новые методы решения задачи Дельсарта основаны на теории двойственности в выпуклом анализе, которая впервые была применена в [2]. Численные результаты основаны на использовании методов решения задач полуопределенного программирования с применением кластера «Уран» ИММ УрО РАН. Дальнейшие результаты получаются за счет применения вычислительной коммутативной алгебры (алгоритмы для многочленов одной переменной и базисы Гребнера) и интервальной арифметики.
Научная новизна. Результаты диссертации являются новыми. Основные из них заключаются в следующем.
1. Разработано два новых метода исследования задач бесконечномерного линейного программирования, возникающих из схемы Дельсарта оценки мощности сферических кодов. В этих методах используется информация о численном решении задачи Дельсарта через полуопределенное программирование (SDP) с использованием открытого пакета для решения задач SDP — SDPA-GMP. На основе этой информации строится система нелинейных алгебраических уравнений для решения прямой и двойственной задачи Дельсарта. В первом методе получившаяся система решается с помощью построения базиса Гребнера. Второй метод использует SDP для получения численных решений ряда вспомогательных задач бесконечномерного линейного программирования; затем из этой информации при помощи интервальной арифметики устанавливается вид экстремального многочлена в задаче Дельсарта и его единственность. Все необходимые алгоритмы реализованы на языке программирования Haskell и в системе символьных вычислений Maple.
2. Дано решение задачи Дельсарта в 11 новых больших размерностях: 147, 157, 158, 159, 160, 162, 163, 164, 165, 167, 173; найдены экстремальные многочлены и доказана их единственность. Структура полученных экстремальных многочленов отличается от структуры экстремальных многочленов в меньших размерностях 4 т 146 (т ф 8,24). Для исследования использовалось SDP и построение базисов Гребнера.
3. Исследована задача Дельсарта в трехмерном случае. Доказано, что единственной экстремальной функцией задачи является многочлен 27 степени, который представим в виде линейной комбинации многочленов Лежандра порядков 0,1, 2, 3,4, 5,8,9,10, 20, 27 с положительными коэффициентами, имеет простой нуль в точке 1/2 и пять двойных нулей в интервале (—1, 2). Установлены близкие двусторонние оценки для коэффициентов этого многочлена. Исследована двойственная задача для неотрицательных мер на отрезке [—1, 2], в частности, доказано, что экстремальная мера единственная.
Научная значимость. Разработанные методы могут быть использованы для решения задач бесконечномерного линейного программиро вания типа задачи Дельсарта. Например, для исследования задачи об упаковке в размерностях 8 и 24. Свойства новых экстремальных многочленов в больших размерностях могут быть применены для уточнения скорости роста величины при 8.
Методы вычислительной коммутативной алгебры, полуопределенного программирования и интервальной арифметики, примененные в работе, могут быть использованы для исследования других родственных задач с использованием компьютера.
Апробация работы. Результаты диссертации были представлены на летних Школах С.Б.Стечкина по теории функций (Миасс, 2010–2014); международной конференции «Алгоритмический анализ неустойчивых задач», посвященной памяти В.К.Иванова (Екатеринбург, 2011); международных конференциях «Современные проблемы математики, механики, информатики» (Тула, 2012, 2013); молодежных конференциях, проводимых ИММ УрО РАН (Екатеринбург, 2010–2012, 2014). Автор выступал с докладами по теме диссертации на следующих научных семинарах: «Экстремальные задачи теории функций и операторов» под руководством В.В.Арестова в Уральском федеральном университете (2010–2014); «Сферические коды» под руководством А.Г. Бабенко и А.Н.Борбунова в Уральском федеральном университете (2010–2013); на совместном семинаре отделов Аппроксимации и приложений и Теории приближения функций в ИММ УрО РАН (2012–2014).
Публикации. Основные результаты по теме диссертации изложены в 10 публикациях [38–47], 3 из которых — в журналах, рекомендованных ВАК [38–40], 7 — в трудах и тезисах конференций [41–47].
Оценки параметров экстремальных функций и мер
Так же как и в предыдущем параграфе, зафиксируем 2. В данной работе для описания экстремального многочлена задачи (1.1.2) выделена экономная и прозрачная (по нашему мнению) характеристика, названная типом многочлена. Гипотеза относительно экстремального многочлена и, как следствие, его типа строится на основании предварительных численных экспериментов. В данном параграфе предложена процедура, с помощью которой по типу экстремального многочлена строится система нелинейных алгебраических уравнений, решения которой содержат параметры экстремального многочлена задачи (1.1.2) (а также и параметры экстремальной меры задачи (1.1.4)). Результаты этого параграфа развивают и обобщают результаты работ [2,25].
Если формальные переменные (1.2.3) приравнять некоторым комплексным числам, то многочлены (1.2.1) становятся многочленами от одной переменной t. Многочлен сро имеет степень р + г + 2. Обозначим его корни через to, t\,... , tp+r = l/2,tp+r+i = 1; с каждым из этих корней ti свяжем многочлен uj{{t) = po(t) (t — t i) l и число
Определим многочлен С из (1.2.1) через корни /, лежащие на (—1, ): С( ) = ОГ=» {t ti)i t Е - По многочленам р и ( строятся все остальные многочлены из (1.2.1). Отметим, что ifj(t)dfi(t) = 0, поскольку из условия (D2) следует, что supp(/i) сі {to, , tp+r} (здесь, как указано перед (1.2.4), to = —1, если р = 1 и tp+r = ).
Определим линейное пространство К[] g/ многочленов с вещественными коэффициентами степени не выше /. Справедливы равенства U&IXU/ = {р є Ф фк = 0, к /}, dim (K[] g/) = 1 + 1.
Подставляя в функционал многочлены ,j, 0 — — — 3, определенные в (1.2.1), и многочлен = /, получаем первые три равенства из (1.2.2). Таким образом, мы можем заключить, что существует решение системы (1.2.2), для которого = = (1). Ясно, что о = 1/ и = /о] неравенства в (С1) и (С2) следуют из допустимости многочлена . Докажем равенство (1.2.6). Как уже было сказано выше, supp() сі {o, . . ., p+r}, поэтому нужно доказать равенства {} = i для всех 0 + . При указанных многочлены і имеют степень + + 1 + 2 + 1 , поэтому таким образом, (С5) также имеет место. Следующая теорема устанавливает достаточные условия того, чтобы многочлен некоторого типа был единственной экстремальной функцией задачи (1.1.2).
Теорема 1.2.2. Пусть (d,N,p,r) — некоторый тип и существует решение системы (1.2.2), удовлетворяющее условиям (С1)–(С6) теоремы 1.2.1. Тогда многочлен f = о /pо имеет тип задачи (1.1.2), а мера /І — единственной экстремальной мерой задачи (1.1.4). (d,N,p,r) и является экстремальным в задаче (1.1.2), а дискретная мера (1.2.6) является экстремальной в задаче (1.1.4). то найденный экстремальный многочлен f является единственной экстремальной функцией
Доказательство. Пусть переменные (1.2.3) из системы (1.2.2), а также числа ti, Li, 0 і p + r + 1, и Gk, к d, выбраны как указано в условии теоремы. Под многочленами (1.2.1), а также многочленами ШІ, О і р + r + l, мы будем понимать многочлены, зависящие лишь от переменного t, в которые вместо остальных неизвестных подставлены значения из предположения теоремы. Через / и /І мы будем обозначать многочлен и меру, определенные в предположениях теоремы.
Добавим к набору { } =о многочлены /?о, ty?i, , (fid-p-r-з и многочлен о" и покажем, что получившаяся система образует базис в пространстве К[] . Для этого заметим, что deg(cfj) = р + г + j + 2, 0 j d — р — г — 3, deg(cr) = i и степень многочлена (/?о на единицу больше степени многочленов ; в то же время степень многочлена (fd-p-r-з на единицу меньше степени мно гочлена . Из этого следует, что набор из + 1 указанных многочленов образует базис в пространстве К[] . которое совпадает со вторым уравнением в системе (1.2.2) с точностью до множителя 0, поэтому равно нулю. Точно таким же образом из оставшихся уравнений системы (1.2.2) следуют равенства () = (j) =0, 0 — — — 3.
Мы показали, что линейный функционал зануляется на всех базисных многочленах пространства К[] . Из этого следует, что он обра щается в нуль на всех многочленах степени не выше d. Для всех к d j: є lR[rJ gd, поэтому получаем равенства
Из условия (СЗ) видно, что мера /І является неотрицательной, поэтому /І є ]\Л. Неравенство Д& — 1 может выполняться лишь для к є N или для к d, но для этих номеров к имеем /& = 0, поэтому справедливо условие (D1). Кроме того, supp(/i) = {ti I 0 і р + г, Lj 0}, поэтому многочлен / обращается в нуль на supp(/i), т. е. выполнено условие (D2).
Для проверки условий теоремы 1.1.5 осталось доказать, что многочлен / является допустимым. Из (С2) имеем /о = pо/pО = 1, fk = pк/pо 0 для всех к 1. Из условия (С1) получаем неравенство Таким образом, многочлен / и мера /І удовлетворяют условиям теоремы 1.1.5, а потому являются экстремальными в задачах (1.1.2) и (1.1.4) соответственно. Также очевидны равенства и = /(1) = S.
Перейдем к доказательству единственности. Пусть д є Т и v є Л4 . Покажем, что при дополнительных условиях (Е1)–(Е4) выполняются равенства д = f и v = /І. Пары (g,/i) и (/, z/), состоящие из экстремальной функции и экстремальной меры, удовлетворяют условиям дополняющей нежесткости. Из этого получаем следующие четыре условия на многочлен д и меру v: (1) из (ЕЗ) имеем jpk = S -Gk — 1 —1 для к є N и к і, поэтому для этих номеров к выполняются равенства pk = О, т. е. д — также многочлен
Рассмотрим многочлен h = (/ + д)/2 и меру А = (/І + v)/2. Они являются экстремальными, так как h(l) = (/(1) + д(1))/2 = 2и/2 = и и 1 + А = 1 + (/i +Н)/2 = 2и/2 = и. Более того, справедливо равенство supp(A) = supp(/i), на отрезке [—1, ] многочлен h имеет точно такие же нули, что и /. Более того, следующие соотношения эквивалентны: аким образом, многочлен h имеет тип (d,N,p,r). Из теоремы 1.2.1, примененной к паре (А, /г), получаем, что экстремальная мера А и экстремальный многочлен h являются решениями той же системы, что и пара (/І, /). Из условия (Е4) получаем равенства X = fi = iyиh = f = g.\Z\ 1.3 Оценки параметров экстремальных функций и мер
Сведение полиномиальных задач бесконечномерного линейного программирования к задачам SDP
В данном параграфе мы приводим основные определения и результаты об идеалах в кольцах многочленов и базисах Гребнера. Затем описываем метод решения задачи Дельсарта с использованием теоремы 1.2.2. Подробную информацию о базисах Гребнера, а также основные алгоритмы можно найти в монографии [12, гл. 2].
Рассмотрим коммутативное кольцо), многочленов от n переменных над полем Q, т. е. конечных сумм вида это мультииндекс. Множество мультииндек-сов образует коммутативный моноид относительно поэлементного сложения а + (3 = («і + /Зі, «2 + /#2,.. , OLVJ + fin), ск, /3 є Z, с нейтральным элементом 0 = (0,0,... ,0) є Z. Для мономов выполняются равенства z = 1, za z13 = za+l3.
На множестве всех мультииндексов определим лексикографический порядок , т.е. будем считать, что а /3, когда существует номер 1 к п такой, что х,- = (3j для всех 1 j к и о (3k. Порядок является линейным и обладает двумя свойствами:
Лексикографический порядок на множестве мультииндексов порождает соответствующий порядок на множестве всех мономов.
Старшим мономом LM(/) ненулевого многочлена / є Q[z\ назовем наибольший моном с ненулевым коэффициентом. Обозначим коэффициент перед старшим мономом через LC(/); также введем обозначе ние LT() = LC() LM(). Для подмножества a Q[\ обозначим
Непустое множество X a Q[] называется идеалом кольца Q[], если оно замкнуто относительно сложения многочленов и обладает свойством є I для любых Е Q[\, el. Пересечение любого семейства идеалов снова есть идеал, поэтому любое множество многочленов a Q[] порождает идеал () — наименьший идеал, содержащий все многочлены из множества. Выполняется равенство
Базисом Гребнера идеала I называется конечный набор многочленов а X такой, что (LM()) = (LM(X)). Данное условие позволяет легко решать задачу о принадлежности многочлена идеалу, а именно, предположим, что є X и — базис Гребнера идеала X, тогда LM() делится на старший моном некоторого многочлена є . Проведем процедуру деления с остатком на :
Из свойств идеала следует, что остаток от деления также принадлежит идеалу X, причем старший моном остатка меньше, чем LM(). Повторяя эту процедуру для остатка, мы в конечном итоге придем к нулю. Наоборот, если для некоторого є Q[\ остаток от деления на є равен нулю, то є X. Из вышесказанного также следует равенство () = X.
Базис Гребнера существует для любого идеала (см. [12, гл. 2, 5, следствие 6]), причем редуцированный базис Гребнера определяется единственным образом. Определение и алгоритм построения (редуцированного) базиса Гребнера впервые появились в работе [28] (см. также [12, гл. 2, 7]). Более современный алгоритм разработан в [30] и реализован в системе символьных вычислений Maple. Отметим, что в Maple отсутствует требование п. (1) из определения редуцированного базиса Гребнера, т. е. коэффициенты перед старшими мономами не обязаны равняться единице.
Для конечного набора многочленов Q = {qi,q2,... , q{\ сі Q[z\ обозначим через V(Q) = {z є Cn I qi(z) = 0, q2{z) = 0,..., qi(z) = 0} множество решений системы уравнений в поле комплексных чисел. Отметим, что из равенства (Qi) = (Q2) следует равенство V(Qi) = V(Q2), так как любой многочлен из Q\ есть сумма многочленов, каждый из которых делится на некоторый многочлен из Q2, и аналогично для ( 2. В частности, если G — базис Гребнера идеала (Q), то V(Q) = V(G). Будем называть G базисом Гребнера системы (2.3.1). Чтобы применить теорему 1.2.2, мы сначала находим приведенный базис Гребнера многочленов системы (1.2.2). Для задания лексикографического порядка на мономах полагаем (в обозначениях 1.2) одинаковой степени. Локализуя корни последнего многочлена дп, зависящего только от одной переменной zn, мы легко можем найти все решения системы (2.3.2), а значит и системы (1.2.2), с любой наперед заданной точностью. Это позволит проверить условия теоремы 1.2.2.
Отметим, что вид системы (2.3.2) не является случайным. Лексикографический порядок , который мы ввели на мономах, иногда называют исключающим, так как при вычислении базиса Гребнера он приводит к системе, в уравнениях которой последовательно исключены переменные, причем порядок исключения соответствует порядку на переменных. Описание методов исключения переменных в системах полиномиальных уравнений содержится в [12, гл. 3].
Результаты для новых больших размерностей
Пусть / — некоторая экстремальная функция задачи (1.1.2) при т = З, а /І — некоторая экстремальная мера соот ветствующей двойственной задачи (1.1.4). В соответствии со следстви ем 3.1.8, функция / имеет по одному двойному нулю t Е Ті, 1 і 5, и простой нуль Ц = . В силу условия (D1), экстремальная мера /І может быть сосредоточена лишь в нулях {t } =l функции /. Другими словами, мера /І дискретная и сосредоточена не более чем в шести точках {t } =l. Учитывая лемму 3.1.2, заключаем, что точки {t } =l как раз и составля ют носитель меры /І. Поскольку пара функция / и мера /І произвольные, то точки {t } =l от них не зависят. Лемма 3.1.10. Множество J- содержит единственную функцию. Эта функция является многочленом типа (3.1.1).
Доказательство. Рассмотрим следующую систему десяти линейных уравнений с интервальными коэффициентами и десятью неизвестными gi , к Е D = (1, 2, 3,4, 5,8, 9,10, 20, 27}: через (Pj: ) обозначена производная многочлена Лежандра Р степени к. Пусть / є J7 . Из следствия 3.1.4 и леммы 3.1.9 заключаем, что вектор gk = fk, к є D, является решением системы (3.1.3). Таким образом, утверждение будет установлено, если мы покажем, что решение системы единственно для любых значений коэффициентов системы из соответствующих интервалов PJ: (Т) и (PJ: ) (Т). Обозначим через X матрицу системы (3.1.3) размера 10 х 10 с интервальными элементами. Используя интервальную арифметику в методе Гаусса поиска определителя квадратной матрицы, можно установить соотношение det(X) є [—0.31664386200784, —0.12414427041161], т.е. определитель ненулевой и решение системы (3.1.3) единственно при любом значении нулей из интервалов TJ, 1 г 5.
В итоге получено следующее утверждение, которое составляет основной результат данного параграфа.
Теорема 3.1.11. Единственной экстремальной функцией задачи (1.1.2) при т = 3 является многочлен типа (3.1.1). Напомним, что в силу теоремы 1.2.1 экстремальный многочлен может быть однозначно восстановлен из решения системы (1.2.2), соответствующей типу (3.1.1).
Двойственная задача (1.1.4) при т = 3 также имеет единственное решение. Теорема 3.1.12. Экстремальная мера задачи (1.1.4) при т = 3 единственная. Эта мера дискретная и сосредоточена в шести нулях экстремального многочлена задачи (1.1.2). Доказательство. Рассмотрим систему линейных уравнений с интервальными коэффициентами и неизвестными
Из лемм 3.1.6 и 3.1.9 следует, что экстремальная мера дает решение этой интервальной системы в следующем смысле: мера сосредоточена в шести точках i Е i, 1 5, 6 = -, и вектор является решением системы (3.1.4).
Интервальная матрица системы (3.1.4) имеет размер б х 6. Используя интервальную арифметику, можно установить соотношение det() є [0.0211619, 0.0211621]. Таким образом, определитель ненулевой и решение единственно при зна чении нулей Е І, 1 5. 3.2 Результаты для новых больших размерностей
Если есть гипотеза о типе экстремального многочлена, полученная, например, при численном решении задачи Дельсарта, то теорема 1.2.2 позволяет свести нахождение экстремального многочлена такого типа и доказательство того, что других экстремальных функций нет, к решению системы нелинейных алгебраических уравнений.
Для установления типа экстремального многочлена мы решали задачу Дельсарта численно при помощи методов 2.2. На кластере «Уран» ИММ УрО РАН было одновременно запущено 297 программ SDPA-GMP, каждая из которых численно решала задачу Дельсарта в размерности 4 300 с высокой точностью. В итоге за 10 минут был получен предполагаемый тип во всех размерностях до 300.
При помощи теоремы 1.2.2 нам удалось решить задачу (1.1.2) во всех случаях, разобранных в работах [2,25], т.е. в случаях = 4 и (0.2), а также в новых размерностях Сформулируем в виде теоремы полученные нами результаты для размерностей (3.2.1). Ввиду громоздкости вычислений мы в следующем параграфе разберем подробно лишь случай = 173.
Теорема 3.2.1. В каждой из размерностей (3.2.1) единственной экстремальной функцией задачи (1.1.2) является многочлен типа (,,,) с параметрами из табл. 1. Таблица 1 Параметры экстремальных многочленов для новых размерностей
Отметим, что в размерности 147 у экстремального многочлена появляется новая особенность: множество номеров нулевых коэффициентов экстремального многочлена состоит из двух «отрезков» натуральных чисел, что отличает данный многочлен от многочленов в размерностях = 4 и (0.2). Для сравнения в таблице 3 приведены параметры экстремальных многочленов для размерности 147 и двух соседних размерностей.
Вид системы (2.3.2) позволяет легко найти остальные неизвестные (3.3.3); коэффициенты многочлена вычисляются по формуле (1.1.1); корни —1 o i --- i8 многочлена находятся численно; \g = 2; соответствующие веса i, 0 19, экстремальной меры вычисляются по формулам (1.2.4). Константа в выражении (3.3.2) вычисляется по формуле = 1/ pQ = 7.269325804828220 1026. Приближенные значения всех параметров сведены в табл. 4.
