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

• Андреев, Николай Николаевич
• кандидат физико-математических наук
• 2000

Оглавление диссертации кандидат физико-математических наук Андреев, Николай Николаевич

Введение

1. Задача о минимальном дизайне

1.1. Многочлены Гегенбауэра и дизайны

1.2. Оценка снизу мощности D-дизайна.

1.3. Минимальный дизайн 11 порядка на 53.

2. Задача о максимальном сферическом коде

2.1. Оценка сверху мощности т-кода.

2.2. Максимальный (cos f )-код на S3.

3. Задача об энергии, произведении и сумме

3.1. Оценка общего случая.

3.1.1. Задача об энергии.

3.1.2. Задача о сумме.

3.1.3. Задача о произведении.

3.2. Интерполяционные многочлены Эрмита.

3.3. Случай 12 точек на икосаэдр

3.4. Случай 120 точек на S3: сферическая конфигурация Ш

3.5. Случай 196560 точек на S23: решетка Лича.

Введение диссертации (часть автореферата) на тему «Приближение с ограничениями индивидуальных функций и экстремальные задачи расположения точек на сфере»

Теория приближения индивидуальных функций берет начало с пионерских работ П.Л. Чебышева второй половины XIX века и до сих пор является мощным инструментом, используемым как при решении задач самой математики, так и прикладных задач. Диссертация посвящена решению старых классических задач дискретной геометрии о расположении точек на сфере с помощью экстремальных задач теории приближения индивидуальных функций с ограничениями на аппарат приближения.

Во многих экстремальных задачах расположения точек на сфере, при решении которых удается воспользоваться методами теории приближений, большую роль имеет понятие дизайна. Конечное множество точек X = С 5т1 С Мт и весов {рк}^=\ называется взвешенным сферическим дизайном порядка д, если кубатурная формула верна для всех алгебраических полиномов /(ж) степени не выше д (под степенью монома ха = ж"1 • . • хпонимается сумма показателей а\ + . + ат). Множества являющиеся дизайнами представляют большой интерес, так как кубатурные формулы находят большое применение в вычислительной математике и во многих других областях. Кроме того, дизайны оказываются решением многих задач об экстремальных расположениях точек на сфере. В диссертации рассматривается случай положительных весов: р^> 0, к = 1,. ^ N.

Основная задача состоит в нахождении множеств X и весов {рк}^=\ для которых выполняется (1). Особый интерес представляют множества X содержащие минимальное количество точек, необходимое для

1) з выполнения (1). Такие множества называются минимальными взвешенными сферическими дизайнами. Отдельный интерес представляет случай равных весов — кубатурные формулы Чебышевского типа. В этом случае употребляются термины дизайн и минимальный дизайн.

Простейший минимальный сферический дизайн — две противоположные точки сферы 5т1 являющиеся минимальным дизайном первого порядка. Примерами дизайнов являются вершины правильных многогранников. Так правильный симплекс вписанный в сферу 5т1 (множество из т + 1 точки с равными попарными расстояниями, рис. 1) является минимальным дизайном 2 порядка для любого га. Октаэдр вписанный в сферу (множество точек пересечения б™-1 с координатными осями, рис. 2) является минимальным дизайном 3 порядка на сфере любой размерности. Вершины икосаэдра (рис. 3) образуют минимальный дизайн порядка 5 на 52. В то же время вершины куба и додекаэдра являясь дизайнами соответственно 3 и 5 порядка не являются минимальными. Все вышеперечисленные минимальные дизайны являются минимальными и в классах взвешенных дизайнов соответствующих порядков. В общей ситуации это не всегда так: минимальный дизайн 5 порядка на 53 с равными весами содержит 24 точки, в то же время существует [1] взвешенный дизайн 5 порядка содержащий 23 точки.

Простейшими квадратурными формулами на отрезке — формулой прямоугольника, формулой трапеций, формулой Симпсона — математики пользовались с давних времен. К. Гаусс построил квадратурную формулу на отрезке из N узлов и весов, точную для алгебраических многочленов степени 2N — 1 и доказал, что меньшим количеством узлов обойтись нельзя.

П.Л. Чебышев рассматривал задачу нахождения N узлов квадратурной формулы с равными весами на отрезке, точной для алгебраических многочленов порядка N. Он в явном виде указал узлы при N = 1,. ,7. Впоследствии, С.Н Бернштейн показал, что такая квадратурная формула возможна лишь для N = 1,., 7, 9.

Дальнейшее развитие математики привело к изучению кубатурных формул на сфере. Интерес к рассматриваемому вопросу в конце XIX века был связан (см. [2]) с исследованиями по проблеме Варинга, а так же с задачей представления (xf + . + в виде суммы четных степеней линейных форм от Xi,. ,хт (в современных терминах — задачей изометрического вложения в ^/г)- Так в 1859 г. Лиувилль нашел (будем использовать современную терминологию) дизайн 5 порядка на 53. В 1876, 1877 гг. Лукач находит дизайны 5 порядка на S2 и S3. В начале века Гурвиц нашел дизайн 8 порядка на 53. Примерно в это же время А.И. Коркиным, Е.И. Золотаревым, Блихфельдом и рядом других математиков проводились исследования по теории квадратичных форм и решетчатым упаковкам пространств. Впоследствии выяснилось, что минимальные вектора некоторых решеток являются хорошими сферическими дизайнами. В середине XX века интерес к дизайнам снова возрос. В 1948 г. В.А. Диткин доказал, что вершины икосаэдра являются дизайном 5 порядка на S3. Многочисленные исследования по конструированию дизайнов на основе орбитных кодов принадлежат С.Л. Соболеву (см. [3]) и его ученикам.

Количество точек минимального взвешенного дизайна порядка q на 5m1 будем обозначать N(m,q), а минимального дизайна с равными весами — 7V*(m, g); очевидно N*(m, q) ^ N(m, q). Оценкам снизу мощности минимальных сферических дизайнов посвящено много работ. Бурное развитие эта тематика получила после работы Ф. Дельсарта, Дж. Гетелса, Я. Зейделя [4] в которой они начали использовать методы анализа для решения задач дискретной геометрии; ввели термин "дизайн" и получили оценку снизу мощности сферического дизайна с равными весами /т + «-1\/т + «-2\

V т - 1 )

Оценка (2) дала возможность доказать минимальность дизайнов, образованных вершинами октаэдра, вершинами икосаэдра, решеткой Лича и еще ряда других известных дизайнов. Однако в целом эта оценка оказалась [5] плохой — она может быть точна лишь на небольшом количестве дизайнов. Возникшие новые методы получения оценок снизу мощности сферических дизайнов стали использовать свойство положительной определенности специальных функций в задаче оценки мощности сферических дизайнов. Затем эта тематика получила развитие в ряде работ, среди которых следует отметить работы Н. Слоэна, А. Одлыжко, Ф. Дельсарта, Дж. Гетелса, Я. Зейделя, В.И. Левенштейна, В.М. Сидельникова, В.А. Юдина. Основная идея, принадлежащая Ф. Дельсарту, состоит в использовании многочленов Гегенбауэра — многочленов, ортогональных на отрезке

1,1] с весом (1 — ¿2)(т~3)/2 (см. пункт 1.1) и их свойства положительной определенности ([6, стр. 318]): для любого конечного множества точек . из 5т1, любого и £ N и любых £1,., £лг Е С справедливо неравенство N

0. (3) к,1=1

Определение дизайна может быть переписано в следующем, эквивалентном, виде: взвешенный дизайн порядка q есть множество точек X = С /6>т1 и весов {рк}к=1^ Для которого справедливы равенства N 0 для 1/ = 1,2,.,д. к,1=1

Такая запись дает возможность ввести новое определение Б-дизайна, по-видимому возникшее у Ф. Дельсарта (см. [7]). Множество точек X = С и весов {рк}к=1 называется взвешенным

-дизайном, где Б С N есть подмножество натурального ряда, если справедливы равенства N

YJGtn)(x^x^)pkpl = 0 для и еИ. к,1=1

При В = {1, 2,.,д} это определение совпадает с классическим определением взвешенного дизайна порядка д. Многие дизайны порядка д являются В-дизайнами для более широкого чем {1, 2,., д} множества И и этот факт иногда оказывается важным при оценке мощности дизайнов и в других вопросах.

Интересным является ^-множество 120 вершин правильного многогранника в Ж4 с символом Шлефли {3,3,5} [8, с. 494]. Эта конфигурация состоящая из

8 точек вида (±1,0,0,0), (0, ±1,0,0), (0,0, ±1,0), (0,0,0,±1);

16 точек вида (±1/2, ±1/2, ±1/2, ±1/2);

96 точек полученных четными перестановками координат из 8 точек вида (±(>/5 ± 1)/4, ±1/2, ±(\/б - 1)/4, 0); обладает многочисленными замечательными свойствами и мы обозначим ее ЯЯ. Как было показано в [9] множество Ш является дизайном 11 порядка. На самом деле ЭДТ является (см. [29]) Дщ-дизайном для множества

От — {все нечетные натуральные числа}и и {2,4,6,8,10,14,16,18, 22, 26,28, 34,38,46,58}.

В пункте 1.3 решена следующая экстремальная задача связанная со сферической конфигурацией Ш.

На классе непрерывных на отрезке [—1,1] функций /(¿) удовлетворяющих условиям:

1. /№^0, /(1)>0;

2- /(*) = Е,евт % ^ (*), 0 приг/> 12; найти величину вирДЯ (5) о

Найдены экстремальные многочлены 17 порядка.

Из общей оценки мощности дизайна, приведенной в пункте 1.2 следует, что решение этой экстремальной задачи дает оценку снизу мощности сферического дизайна 11 порядка на 53. За последние годы доказана минимальность лишь нескольких дизайнов (см. обзор [10], и работу [1]). Задача нахождения минимального дизайна 11 порядка на 53 рассматривалась несколькими авторами. Из общей оценки работы [4] следует, что мощность дизайна 11 порядка на 53 не меньше 112. В работе [11] приведена общая оценка, из которой следует, что мощность минимального дизайна 11 порядка на 53 не меньше 117. Такая же оценка получена в [12].

На основе решения задачи (5) в пункте 1.3 доказывается, что минимальный сферический дизайн 11 порядка на 5'3 содержит 120 точек.

Глава 2 посвящена задаче о максимальном сферическом коде. С давних времен существует потребность в передаче информации на расстояния. Однако при передаче сигнала на расстояния возникают искажения. Необходимость обмена информации без искажений привела к появлению кодов исправляющих ошибки. В связи с естественными ограничениями, возникающими в прикладных задачах, стали изучаться сферические коды.

Конечное подмножество точек X = С 5т1 называется сферическим г-ко дом, если х^х^ ^ т для всех 1 ^ г, у, ^ N. г ф у.

Действительно, если известно, что при передаче точки х^ искажения не слишком велики и принятая точка х^' всегда удовлетворяет условию х^х^' > > т/2 зная сам код — набор точек со сферы, которые могли быть переданы — всегда можно однозначно восстановить передававшуюся информацию. Желание передавать максимально большой объем информации приводит к задаче нахождения сферических кодов, содержащих максимально возможное число точек при заданных тит.

При т = 1/2 это знаменитая задача о контактном числе шаров, возникшая задолго до появления сферических кодов, исправляющих ошибки: сколько шаров одинакового радиуса в пространстве Жт могут касаться одного фиксированного шара того же радиуса. Решение задачи о контактном числе известно только при т = 2, 3, 8, 24 [6, с. 45]. При т — 2 решение тривиально. Случай га = 3 был предметом знаменитой дискуссии И. Ньютона и Д. Грегори 1649 г. Гипотеза И. Ньютона (12 шаров) была доказана лишь в конце XIX века (см. [6]). В размерностях 8 и 24 решение задачи, полученное В.И. Левенштейном и одновременно А. Одлыжко и Н. Слоэном, было основано на использовании экстремальных задач теории функций.

Использование свойств ортогональных многочленов в задачах кодирования было начато Ф. Дельсартом. Для оценок мощности кодов из пространства Хемминга (вершины единичного т-мерного куба) использовалось свойство положительной определенности многочленов Кравчука — аналог свойства (3) многочленов Гегенбауэра. Задача, первоначально поставленная для многочленов, разлагающихся с положительными коэффициентами по многочленам Гегенбауэра, получила развитие в работах Г.А. Кабатянского, В.И. Левенштейна, В.М. Сидельникова, А. Одлыжко, Н. Слоэна [13, 14, 15, 16, 17].

На этом пути были получены принципиально новые оценки плотности упаковки шаров в евклидовом пространстве.

В настоящее время экстремальная задача, используемая для оценки мощности сферических кодов, выглядит следующим образом.

Пусть /С(т, т) есть класс непрерывных на [-1,1] функций удовлетворяющих условиям:

1. /(*) ^Опри* €[-1,т];

2- /М - % То > 0, 0 для всех

Найти величину

К(т,т)= и* (6)

С(ш,г)

Эта величина дает (см. пункт 2.1) оценку сверху мощности сферического т-кода на Экстремальные функции являются наилучшим приближением снизу ступенчатой функции, равной 0 на [—1, г] и положительной константе на (т, 1], классом /С(т,г) в метрике L\ с весом (1 ¿2)(т-3)/2

В пункте 2.2 задача (6) решена для т — 4 и г = cos |. Найдены многочлены 17 степени, являющиеся экстремальными в этой задаче при рассматриваемых значениях параметров.

На основе решения этой задачи в п. 2.2 показано (см., также [33]), что при т — 4 максимальный сферический (cos |)-код содержит 120 точек.

Глава 3 посвящена задаче об энергии и сходной с ней задачам. Для N точек {а^}^! С Sm~l введем функционалы N

VF(m, N, х

S(m,N,x{1\. Ы0 - хЩ

J=1 1 1 N т-2

Xх 1 гфд N гф]

Рассмотрим задачи о нахождении величин

W{m, N) = inf W(m, iV, x

S(m,N)= sup S{m,N,x^\.,xiN)), (8)

P{m,N)= sup P(m,iV,z(1),.,z(Ar)). (9)

Наилучшие, в смысле минимума потенциальной энергии системы, расположения зарядов на отрезке были найдены Г. Сегё [18, с. 149]. Им было показано, что если в концах отрезка [—1,1] помещено два положительных заряда, то N единичных зарядов на [—1,1] расположенных в нулях многочлена Якоби (с параметрами определяемыми по зарядам, расположенным на концах отрезка) доставляют минимум потенциальной энергии рассмотренной системы.

Задача (7) о нахождении величины W(m, N) является обобщением классической проблемы расположения зарядов на сфере в трехмерном пространстве. В начале века английский физик Дж.Дж. Томсон проводил [19] эксперимент по нахождению наилучших расположений небольших количеств зарядов на сфере трехмерного пространства. При N = 4,6,12 эксперименты приводили к классическим конфигурациям: тетраэдру, октаэдру и икосаэдру. Аналогичная задача, о нахождении расположения точек с минимальной энергией в дискретных пространствах, была поставлена C.B. Яблонским (см. [20]). Случай (8) суммы попарных расстояний S(d, N) был рассмотрен Л.Ф. Тотом в [21, гл. 5]. Задача (9) о произведении, связанная с проблемой Фекете о расположении, максимизирующем определитель Вандермонда, N точек в заданной области, появилась в начале XX века (см. [22]). В настоящее время, она нашла применение в теории сложности.

Решение этих классических задач было известно лишь в следующих случаях, причем экстремальные конфигурации одинаковы для всех трех задач. m = 2, N — любое (считается, что W(2, N, ., х^) — = iïj ln ~ Экстремальная конфигурация — вершины правильного iV-угольника. Решение задачи об энергии и произведении в этом случае приведено в [23]. m — произвольное, N = 2, 3 — тривиально. Экстремальные конфигурации — две противоположные точки сферы и вершины правильного треугольника, вписанного в большую окружность сферы соответственно. m — произвольное, N = т+1. Экстремальная конфигурация — вершины симплекса вписанного в сферу. Этот случай, как и предыдущий, несложно доказывается с помощью неравенств о средних гармоническом, геометрическом, арифметическом и квадратичном. m — произвольное, N = 2т. Экстремальная конфигурация — вершины октаэдра, вписанного в единичную сферу (см. [24]). m = 8, N = 240. Экстремальная конфигурация — концы минимальных векторов решетки Коркина-Золотарева (в [25] доказательство приведено только для энергии, случаи суммы и произведения делается аналогично).

Доказательство последних двух случаев стало возможным лишь после привлечения техники экстремальных задач теории приближения. Отталкиваясь от экстремальных задач применяемых в теории кодирования, рассмотренных выше, в связи с задачей об энергии В.А. Юдин рассмотрел задачу приближения функции 1/{2(1 — ¿)}(т2)/2 снизу на отрезке [—1,1] в метрике Li с весом (1 — ¿2)(т~3)/2 конусом положительно определенных функций.

На классе У{т) непрерывных на отрезке [—1,1] функций f(t) удовлетворяющих условиям:

1. f(t) ^ 1/{2(1 - 1)Ут~2У2, -1 < t < 1;

2- № = I I > 0 для всех г/ G N; найти величину

Y(m, N) = sup {N2f0-Nf(l)}. (10) fey(m)

Эта величина оценивает функционал энергии снизу (см. пункт 3.1.1):

W(m,N) > Y(m,N).

Именно на этом пути основывалось нахождение величин W(m, 2m), W{8,240) [25, 26]. При решении экстремальной задачи (10) для проверки условия 1 класса У(т) стали использоваться свойства интерполяционных многочленов Эрмита.

Сходные с (10) экстремальные задачи могут быть рассмотрены (см. пункты 3.1.2 и 3.1.3) и для оценок сверху величин (8), (9).

Оценки с другой стороны во всех трех задачах доставляют хорошо известные конфигурации точек на сфере.

Решая экстремальную задачу (10) для m = 3,iV = 12;m = 4, N — = 120; m = 24, N = 196560 и сходные с ней экстремальные задачи теории функций в главе 3 мы получим решения задач об энергии, сумме и произведении в следующих случаях. т = 3, N = 12. Экстремальная конфигурация есть вершины правильного икосаэдра, вписанного в сферу (см. [30]). т = 4, N = 120. Экстремальной является сферическая конфигурация Ш (см. [32]). га = 24, N = 196560. Экстремальная конфигурация задается концами минимальных векторов решетки Лича (см. [31]).

Отметим еще раз, что применение экстремальных задач теории функций к решению задач дискретной геометрии стало возможным за счет использования свойства положительной определенности. Подобные идеи использовались в теории вероятностей, теории кодирования, теории функций. Примерами могут служить исследования И. Шенберга по функциональным неравенствам, исследования А.Г. Бабенко, В.И. Иванова, Н.И. Черных по экстремальным задачам, связанным с теоремой Джексона в пространствах Ьр.

Мы видим, что начиная с классических работ П.Л. Чебышева теория приближения на протяжении уже многих лет помогает в решении задач, возникающих в самых разных областях математики.

Я выражаю благодарность Владимиру Александровичу Юдину за постоянное внимание и многочисленные обсуждения, а так же Сергею Владимировичу Конягину за внимание к работе. Я выражаю благодарность Мише Фейгину и всем друзьям за дружбу и поддержку.

Список литературы диссертационного исследования кандидат физико-математических наук Андреев, Николай Николаевич, 2000 год

1. Odlyzko A.M., Sloane N.J.A. New bounds on the number of unit spheres that can touch a unit sphere in n dimensions //J. Comb. Theory. A. 26. 1979. P. 210-214.

2. Delsarte Ph. Bounds for unrestricted codes, by linear programing // Philips Res. Rep. 1972. V. 2. P. 272-289.

3. Кабатянский Г.А., Левенштейн В.И. О границах для упаковок на сфере и в пространстве // Пробл. передачи информации. 1978. V. 14, № 1. Р. 3-25.

4. Левенштейн В.И. О границах для упаковок в n-мерном евклидовом пространстве // ДАН СССР. 1979. Т. 245. С. 1299-1303.

5. Сиделъников В.М. Об экстремальных многочленах, используемых при оценках мощности кода // Пробл. передачи информации. 1980. Т. 16, № 3. С. 17-30.

6. Сегё Г. Ортогональные многочлены. — М.: Физматлит, 1962.

7. Whyte L.L. Unique arrangements of points on a sphere // The Amer. Math. Monthly. 1952. V. 59, № 9. P. 606-611.

8. Леонтьев В.К. Асимптотически устойчивые расположения зарядов в вершинах единичного n-мерного куба // Пробл. кибернетики. 1970. Т. 23. С. 27-42.

9. Тот Л.Ф. Расположения на плоскости, на сфере и в пространстве. — М.: Физматлит. 1958.

10. Ахиезер Н.И. Лекции по теории аппроксимации. — М, 1947.

11. Карлин С., Стадден В. Чебышевские системы и их применение в анализеи статистике. —М.: Наука, 1976.

12. Kolushov А. V., Youdin V.A. Extremal dispositions of points on a unit sphere // Analysis Mathematica 1997. V. 23, № 1. P. 25-34.

13. Колушов А.В., Юдин В.А. О конструкции Коркина-Золотарева // Дискретная математика. 1994. Т. 6, вып. 1. С. 155-157.

14. Юдин В.А. Минимум потенциальной энергии точечной системы зарядов // Дискр. мат. 1992. Т. 4, № 2. С. 115-121.

15. Арестов В.В., Вабенко А.Г. О схеме Дельсарта оценки контактных чисел // Труды МИР АН. 1997. Т. 219. С. 44-73.

16. Уолш Дж. Интерполяция и аппроксимация рациональными функциями в комплексной области. — М.: ИЛ, 1961.гэе*й*рст8ЕНН^'--¡ШЯМОТЕКА

17. Andreev N.N., Yudin V.A. Problems of Approximation Theory in Discrete Geometry // Mathematical Research. 1999. V. 107 (Advances in Multivariate Appr.), P. 19-32.

18. Andreev N.N. An extremal property oh the icosahedron // East Journal on Approximations 1996. V. 2, N. 4, pp. 459-462.

19. Андреев Н.Н. Расположение точек на сфере с минимальной энергией // Труды МИРАН. 1997. Т. 219. С. 27-31.

20. Андреев Н.Н. Минимальный дизайн 11 порядка на трехмерной сфере // Матем. заметки. 2000. Т. 67, № 4. С. 489-497.

21. Андреев Н.Н. Один сферический код // Успехи матем. наук. 1999. Т. 54, № 1. С. 255-256.