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

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

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

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

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

Простейший минимальный сферический дизайн — две противоположные точки сферы 5т1 являющиеся минимальным дизайном первого порядка. Примерами дизайнов являются вершины правильных многогранников. Так правильный симплекс вписанный в сферу 5т1 (множество из т + 1 точки с равными попарными расстояниями, рис. 1) является минимальным дизайном 2 порядка для любого га. Октаэдр вписанный в сферу (множество точек пересечения б&trade—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 точек вида (±½, ±½, ±½, ±½);

96 точек полученных четными перестановками координат из 8 точек вида (±(>/5 ± 1)/4, ±½, ±-(/б — 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 зная сам код — набор точек со сферы, которые могли быть переданы — всегда можно однозначно восстановить передававшуюся информацию. Желание передавать максимально большой объем информации приводит к задаче нахождения сферических кодов, содержащих максимально возможное число точек при заданных тит.

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

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

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

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

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

1. /(*) ^Опри* &euro-[-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, ., х^) — = iij 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 = 196 560 и сходные с ней экстремальные задачи теории функций в главе 3 мы получим решения задач об энергии, сумме и произведении в следующих случаях. т = 3, N = 12. Экстремальная конфигурация есть вершины правильного икосаэдра, вписанного в сферу (см. [30]). т = 4, N = 120. Экстремальной является сферическая конфигурация Ш (см. [32]). га = 24, N = 196 560. Экстремальная конфигурация задается концами минимальных векторов решетки Лича (см. [31]).

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

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

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

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.