Оглавление
Введение 4
0.1 Обзор содержания диссертации... 7
0.2 Характеристика работы... 11
0.3 Обозначения... 12
' 1 Задачи о наименьшем уклонении 14
1.1 Примеры оптимизации... 14
1.1.1 Обращение симметричной матрицы... 14
1 1.1.2 Задача на собственные значения ... 15
,> 1.1.3 Явные методы Рунге-Кутты... 15
*"' 1.1.4 Другие приложения... 16
1.2 Анализ оптимизационных задач... 16
1.3 Чебышёвские подпространства... 18
1.4 Задача Лебедева... 19
4 2 Чебышевское представление многочленов 21
2.1 Вещественные гиперэллиптические кривые... 22
2.1.1 Пространство гомологии и решётка Ьм ... 23
2.1.2 Пространство дифференциалов на кривой... 25
• 2.2 Многочлены и кривые... 25
2.2.1 Устойчивость чебышёвского представления... 27
\ 3 Представления пространства модулей 28
3.1 Четыре определения... 28
'<5 . 3.1.1 Пространство Тайхмюллера... 29
1 3.1.2 Деформационное пространство клейновой группы... 29
I * 3.1.3 Пространство лабиринтов ... 30
3.2 Вспомогательные результаты ... 31
3.2.1 Фундаментальная группа пространства модулей... 31
3.2.2 Пространство модулей - орбиты группы Mod... 32
3.2.3 Топология деформационного пространства... 33
3.2.4 Группа разветвлённого накрытия х(и)... 33
4 3.2.5 Действие модулярной группы на группе (5 ... 35
\ 3.2.6 Эквивалентность лабиринтов ... 36
3.2.7 Квазиконформная деформация... 37
** * 3.3 Эквивалентность представлений... 38
3.3.1 Изоморфность Тк и Qk... 39
3.3.2 Изоморфность Тк и П)... 42
3.3.3 Изоморфность Ck\\Qk ... 45
, • ^ < 4 Разбиение пространства модулей на клетки 46
• 4.1 Кривые и деревья... 46
\ 4.1.1 Слоения и глобальная функция ширины... 46
4.1.2 Граф Г кривой М... 47
i 4.1.3 Характеристики графа Г... 48
4.1.4 Свойства графа кривой... 48
4.1.5 Восстановление кривой М по ее графу Г... 50
4.2 Координатное пространство графа... 53
4.2.1 Координатное пространство в пространстве модулей... 54
4.3 Классификация экстремальных многочленов... 58
¦ 5 Уравнения Абеля 61
5.1 Отображение периодов... 62
5.1.1 Гомологическое расслоение и перенос циклов... 62
1 5.1.2 Расслоение дифференциалов и отображение периодов... 63
,» 5.1.3 Свойства отображения периодов... 63
f 5.2 Уравнения Абеля на пространстве модулей... 66
5.3 Образ отображения периодов... 68
6 Вычисления в пространстве модулей 73
6.1 Теория функций в модели Шоттки... 74
« 6.1.1 Линейные тэта ряды Пуанкаре... 74
6.1.2 Сходимость линейных рядов Пуанкаре... 75
6.1.3 Организация суммирования рядов Пуанкаре ... 77
6.1.4 Автоморфные функции и их струи... 79
i • 6.2 Вариационная теория...-... 81
* 6.2.1 Зависимость дифференциалов от модулей... 81
6.2.2 Вариации абелевых интегралов... 82
\ 6.2.3 Квадратичные тэта ряды Пуанкаре... 84
! 6.2.4 Формулы Хейхала... 85
^ 6.2.5 Базис квадратичных тэта рядов Пуанкаре... 87
' 6.3 Вычисление многочленов... 89
I , 6.3.1 Параметрическое представление... 89
; 6.3.2 Уравнения Абеля в пространстве Qk... 90
6.3.3 Схема алгоритма ... 91
6.4 Открытые вопросы ... 92
Заключение 93
Литература 95
•' ВВЕДЕНИЕ
В начале 1850-х годов П.Л.Чебышёв совершил поездку в Англию для ознакомления с высокими технологиями того времени. Вернувшись в Россию, он занялся чисто инженерной задачей о минимизации трения в шарнирах параллелограмма Уатта, передававшего вращение от паровой машины на колёса. Следствием исследований стала замена парал-лелограммного механизма на кривошипно-шатунный, использующийся по сей день. Как сопутствующий продукт технического прогресса были открыты многочлены Чебышёва, вошедшие с тех пор во все учебники и названные Ж.Бертраном ип miracle d'analyse. Именно эти многочлены оказались решениями простейших задач об условной минимизации на пространстве вещественных многочленов
(0.1)
величины уклонения
\\Рп\\Е:=тьх\Рп(х)\,
Е - компакт на вещественной оси. За минувшие полтора века паровые машины вышли из употребления, однако интерес к задачам о "наименьшем уклонении сохранился [13, 50]. В наши дни он связан, например, с оптимизацией численных алгоритмов [93, 39] и обработкой сигналов [4, 73]. Приведём примеры типичных задач.
Задача А: Пусть Е ~ совокупность нескольких вещественных отрезков. Минимизировать норму \\Рп\\е многочлена при заданных линейных связях на его коэффициенты co,ci, ...,сп. Задача Е.И.Золотарёва [50] соответствует Е = [—1,1] и нескольким заданным старшим коэффициентам многочлена.
Задача Б: Найти максимальный отрезок Е = [Q,t], t > 0, для которого единичный шар {Рп : \\Рп\\е < 1} пространства (0.1) пересекается с плоскостью коразмерности г, образованной многочленами, приближающими в нуле ехр(—х) с порядком г — 1. Задача (В.И.Лебедева) возникает при построении устойчивых явных схем (г — 1)-го порядка точности для интегрирования жёстких (stiff) систем обыкновенных дифференциальных уравнений.
Численное решение подобных экстремальных задач при практически интересных степенях п ~ 1000 известно своей трудностью. Существующие на сегодняшний день алгоритмы Ремеза [44, 94, 83], Лебедева [91], Пехерсторфера-Шифермайра [101], методы выпуклого программирования [45, 50] требуют больших вычислительных затрат по следующим причинам, (i) Решение ищется итерациями в пространстве высокой (порядка п) размерности и (И) норма многочлена - негладкая и трудновычисляемая функция его коэффициентов.
От этих недостатков свободен классический подход, при котором решение принято давать в виде явной формулы [43]. Сто пятьдесят лет назад электронных цифровых машин
не существовало, поэтому итерационные методы решения не считались удовлетворительными. Первые задачи о наименьшем уклонении были решены в терминах параметрических выражений (П.Л.Чебышёв [57], 1853 и Е.И.Золотарёв [22], 1868 ):
, ч Тп(и) := cos(nu); x(u) := cos(u), иеС, (0.2)
'\ ZM := 21 [Щ^п)\ + [hWTU)\ I; (аз)
m»(u) + 8n»(a) ue sn2(u) -sn2(a)
где Н(-) - эллиптическая тэта функция в (устаревших) обозначениях Якоби [52], sn(«) - эллиптический синус того же модуля А; € (0,1), фазовый сдвиг а := пгК(к)/п, тп = 1,2, ...,п — 1, К(к) - полный эллиптический интеграл модуля к. Эти параметрические формулы можно понимать так. Функция х(и) является автоморфной относительно группы (3, разрывно действующей в комплексной плоскости. Многообразие орбит C/G5 является сферой Римана в первом случае и тором - во втором. Выражения для Тп(и), Zn(u) корректно определены на соответствующих факторах и оказываются многочленами степени п от переменной х. Как видим, классические решения связаны с алгебраическими кривыми небольшого рода д = 0,1, а сложность их вычислений не зависит от степени п многочлена.
Новизна предлагаемого подхода к задачам наименьшего уклонения в равномерной норме - это поиск решения не во всем пространстве многочленов (0.1), а на некоторых его маломерных подмногообразиях. Открытый П.Л.Чебышёвым принцип альтернанса [13, 50], в дальнейшем объясненный выпуклым анализом, говорит о типичности следующей ситуации. Подавляющее большинство критических точек решения Т(х) - простые со значениями ±||Т(:г)||е и лежат на множестве Е. Такие многочлены весьма специ- фичны и заполняют в пространстве (0.1) многобразия малой размерности. Вот геометри- ческая интерпретация. Решению экстремальной задачи соответствует касание (линейного) многообразия, описывающего в пространстве (0.1) ограничения задачи, и сферы, образо- ванной многочленами одинаковой нормы. Шар, порождённый равномерной нормой, есть выпуклый криволинейный многогранник: его граница не является гладкой, но разбита на гладкие грани разных размерностей. Маломерные грани шара являются его наиболее вы- ступающими частями и неудивительно, что касание различных плоскостей и этих граней осуществляется наиболее часто. Так, у старого чемодана наиболее истёрты углы; каран- даш падает на пол как правило острием, а не плашмя и т.д. Напротив, многомерные грани шара являются линейчатыми многообразиями и могут касаться линейных многообразий по континууму - соответствующая задача на минимум не будет однозначно разрешима. Мы покажем, что многочлены, наиболее часто встречающиеся среди решений задач наименьшего уклонения, имеют описаный выше вид. Эти наблюдения приводят к следующему определению:
Вещественный многочлен Р(х) назовем (нормированным) g-экстремальным многочленом, если все его критические точки, за исключением g из них, простые со значениями ±1. Параметр g этого определения (= количество исключительных критических точек) подсчитывается по формуле
9= Е ovdP'(x)+ ? ¦ [ioid **(*)], (0.4)
х: Р{х)ф±\ х: Р{х)=±\ *
где ord P'(x) - порядок нуля производной многочлена Р в точке х €<С, [•] - целая часть числа. Многочлены с параметром экстремальности д = 0 и д = 1 были открыты полтора века назад и известны как многочлены Чебышёва и Золотарёва соответственно. Графики нескольких 2-экстремальных многочленов приведены на рис. 6.3. В приложении к задачам о наименьшем уклонении важны многочлены с небольшим д.
Цель диссертации - описание, параметризация и эффективное вычисление у-экстре- мальных многочленов.
Идейно и технически предлагаемый подход к решению задач о наименьшем уклонении в равномерной норме более сложен, чем упомянутые ранее. Выгода же его в том, что сложность вычисления решения по явным аналитическим формулам не зависит от степени п многочлена, что ясно видно для классических формул Чебышёва и Золотарёва. Вместе с тем, объём вычислений быстро растёт вместе с параметром д, поэтому естественная область применения этого метода - большая степень п решения при малом числе связей на его коэффициенты и малом числе компонент множества Е.
Многочлены, а также рациональные и алгебраические функции, с небольшим чис- лом критических значений - классический предмет математического исследования, находящийся на стыке непрерывного и дискретного. Одна традиция в этих исследованиях восходит к А.Гурвицу ([89], 1891) и связана с перечислением разветвлённых накрытий над сферой, изучением стратов возникающего дискриминантного множества, отображения Ляшко-Лойенги, парами Белого и детскими рисунками Гротендика. Этот подход интенсивно развивается в последнее время московской математической школой - см. комментарии и библиографию к задаче 1970-15 в "Задачах Арнольда" [5], также диссертацию [28]. Так, в работе [106] изучаются многочлены с двумя конечными критическими значениями - многочлены Шабата - и их приложения к теории чисел.
Другая традиция в исследованиях восходит к П.Л.Чебышёву ([57], 1853), а по существу к Н.Абелю ([64], 1826). Она связана с изучением уравнения Пелля1 с полиномиальным коэффициентом, разложениями в цепные дроби и условиями вырождения гиперэллиптических интегралов, при которых они выражаются через логарифмы. Обзор этого направления можно найти в [46, 49]. Характерной особенностью этой второй традиции являются эффективные вычисления и связь с приложениями. Учитывая приведённую в начале работы мотивацию, мы избираем второй подход и хотим довести его до эффективных компьютер- ных расчётов [113, 115].
Программа Чебышёва В работе [57] П.Л.Чебышёв отмечает, что решения сформулированных им задач на минимум удовлетворяют уравнению Пелля (=Ферма-Абеля), решение которого он предлагает искать в виде косинуса от гиперэллиптического интеграла. При этом необходимо, чтобы этот интеграл выражался через логарифмы. Соответствую- щий критерий (хотя и не конструктивный) давал остроумный метод Абеля. Для эллиптических интегралов эта программа исследований была намечена самим П.Л.Чебышевым, и полностью выполнена его учеником Е.И.Золотарёвым в 1868-1877 годах [22, 23]. Следующее крупное продвижение по реализации чебышёвской программы принадлежит Н.И.Ахиезеру, применившему в этих задачах язык геометрической теории функции комплексного переменного. В 1928 году Н.И.Ахиезер предложил [6] для решения задачи Золотарёва с тремя
1Диофантово уравнение Р2 — DQ2 = 1, где D - заданный целый коэффициент, а целые Р и Q нужно найти, "изучалось У.Броункером (1657), П.Ферма и Дж.Валлисом. Л.Эйлер по недоразумению связал его с именем Дж.Пелля" [35]. Н.Абель первым рассмотрел [64] то же уравнение с коэффициентом D(x) -многочленом. Автор работ [91, 92] предлагает называть последнее уравнение именами Ферма и Абеля
фиксированными коэффициентами использовать анзатц, включающий функции Шоттки t кривых рода д = 2. Применение анзатца не было однако полностью обосновано. Например,
не была выяснена разрешимость системы трансцендентных уравнений (Абеля) по определению параметров аизатца. Методология этой работы основывалась на аппарате функций < f Грина надлежаще разрезаной плоскости, что затемняло связь задачи с алгебраическими
* кривыми. К сожалению, Н.И.Ахисзер в дальнейших исследованиях [7, 9] по теории при-\ ближений ограничился применением эллиптических функций, т.е. по сути использовал
многочлены Золотарёва.
В последние 15 лет мы наблюдаем возобновление интереса к эллиптическим функциям, теорию которых Ф. Клейн назвал жемчужиной математики XIX века [24]. Интерес этот возник в теории экстремальных и ортогональных многочленов [38, 92, 100], в алгебро-геометрическом подходе в теории интегрируемых систем и рассеянием на двояко-периодических потенциалах [75, 80, 81], комплексно геометрической теории одномерных интегральных уравнений [118, 119]. Работы по реализации геометрического подхода к задачам о наименьшем уклонении в случае рода д > 1 ограничивались до сих пор кривыми
* с точками ветвления, лежащими на вещественной оси либо окружности [46].
Большой объем знаний, накопленый математиками об алгебраических кривых и их деформационных пространствах позволяет сегодня использовать эти объекты для реальных вычислений. Здесь следует назвать прежде всего пионерские работы А.И.Бобенко ([15],
* 1986) по нелинейным волнам. Ключом к численному анализу на пространстве модулей алгебраических кривых служит теорема этого автора о том, что вещественные кривые можно униформизовать специальными группами Шоттки ©, линейные тэта-ряды Пуанкаре которых сходятся абсолютно и равномерно на компактах в области разрывности группы. Для общих групп Шоттки такой факт неверен (А.Пуанкаре даже считал что это неверно всегда) - историю вопроса и обзор результатов см. в [65, 97].
0.1 Обзор содержания дассертащш
0
Глава 1 посвящена обоснованию данного нами определения экстремальных многочленов. Приведён пример оптимизации численного алгоритма, приводящий к задаче о наименьшем уклонении. Далее экстремальные задачи изучаются при помощи выпуклого анализа, в частности получен критерий разрешимости такой задачи - обобщение принципа
* альтернанса для задач с несколькими линейными связями. Подсчитывается частота появления различных многочленов среди решений задач с заданным числом г связей. Ока-
, зывается, что чаще всего решениями становятся многочлены которые мы назвали экстре-
мальными с параметром д = п + 2 — г.
Глава 2. Обсуждаемое здесь представление экстремальных многочленов восходит к П.Л.Чебышёву и является геометрической интерпретацией уравнения Пелля с полиномиальным коэффициентом. Мы сопоставляем всякому многочлену Р(х) гиперэллиптическую кривую
* . 2д+2
M = M(e) = {(x,w)eC2: w2 = Ц (х - es)}, (0.5)
* s=l
'* с дивизором ветвления е := {е,}^ - нулями нечетной кратности многочлена Р2{х) — 1.
^ Род д этой кривой равен количеству исключительных критических точек многочлена Р{х)
при их грамотном подсчёте (0.4). Многочлен Р(х) естественно порождает отображение Р(х, w) накрывающих пространств в диаграмме
(x,w)G М(е) -А СР! Эй
4-х 1<г (0.6)
хе
V
гдех(?)ЭД) := ? -двулистное накрытие, ветвящееся над точками е;а (и) := |(и+1 /и) -двулистное накрытие, ветвящееся над ±1. Отображение Р(х, w) оказывается эквивариантным по отношению к скольжениям (=смене листов) на накрывающих: P(x,—w) — \/P(x,w), поэтому дивизор функции Р(х, w) состоит из двух точек: полюса порядка п := dcgP на бесконечности со+ одного листа и нуля того же порядка на бесконечности оо_ другого листа. Верно и обратное: всякая мероморфная функция Р на М(е) с дивизором п(оо_ — оо+) удовлетворяет (после перенормировки) условию эквивариантности и опускается до отображения Р(х) в базах. Последнее оказывается многочленом степени п и автоматически будет иметь нужное количество простых критических точек со значениями ±1.
В рамках этой конструкции задача описания ^-экстремальных многочленов данной
степени п эквивалентна перечислению кривых М вида (0.5), допускающих мероморфиую
» функцию с дивизором п(оо_ — оо+). Задача о существовании и представлении такой функ-
? ции замкнуто решается в терминах самой кривой М при помощи критерия Абеля [19]. На
всякой кривой (0.5) существует единственный абелев дифференциал 3-го рода
dVM = (x9 + y?csxs)— (0.7)
* с чисто мнимыми периодами. Указанная нормировка имеет ясный физический смысл: в точки оо± нужно посадить электрические заряды ±1, тогда возникающее распределение потенциала на римановой поверхности М будет вещественной частью соответствующего
0 абелевого интеграла г)м- В терминах дифференциала, приписанного кривой М, многочлен
Р(х) степени п можно восстановить с точностью до знака по явной формуле
г{х,ги)
* P(x) = ±cos(ni drjM), xeC; (x,w) € М, (0.8)
У(е,О)
** где выражение в левой части не зависит от выбора пути интегрирования, точки ветвле-
ния (е,0) и точки (х, w) на кривой М, накрывающей аргумент многочлена. Последняя , ' формула обобщает классические представления (0.2), (0.3) для многочленов Чебышёва
и Золотарёва, а также представление Пехерсторфера для (неклассических) чебышёвских многочленов на нескольких отрезках [100]. Эта формула описывает ^-экстремальные многочлены с помощью небольшого количества параметров - модулей кривой М. Модули эти однако не произвольны, а связаны некоторыми соотношениями.
Для кривой М, порождённой многочленом степени п, дифференциал <к]м совпадает
* с n~1d\ogP(x,w), поэтому те и только те кривые М порождаются многочленами степе-, ни п, для которых периоды связанного с кривой дифференциала dr\u лежат в решётке
2тгг n-1Z. Для вещественной кривой М, допускающей отражение J(x,w) := (х, id), половина этих периодов автоматически будет нулевой, а остальные должны удовлетворять
к
системе уравнений Абеля:
_j / dviM — 27Г_- s = О 1 о (0 9)
Jcr п
•* где та - некоторые целые числа; {C~}9S=Q - базис в решетке целочисленных 1-циклов
• кривой М, меняющих знак при отражении J.
\ Глава 3. "Удобно считать, что сопоставляемая многочлену кривая М - это точка прост-
ранства модулей вещественных гиперэллиптических кривых рода д с отмеченной точкой оо+ на ориентированном вещественном овале. Это пространство состоит из компонент Tig, к = 0,...,д+1, различающихся количеством вещественных точек в (переменном) дивизоре ветвления е. Каждая компонента пространства модулей это 2^-мерное гладкое вещественное многообразие, гомеоморфное произведению клетки на конфигурационное пространство (полу)плоскости. Фундаментальная группа Tig - группа кос Артииа с д — к + 1 нитями -скольжениями действует на универсальной накрывающей Tig пространства модулей. Для
. пространства Ц* = Шд мы рассматриваем четыре представления, одно из которых явля-
ется аналитической униформизацией пространства модулей Tig и используется в дальнейшем для эффективного вычисления экстремальных многочленов.
Глава 4. Развита графическая техника, применяемая для наглядного перечисления всех экстремальных многочленов. Всякая точка М пространства модулей определяет на ¦» римановой сфере горизонтальное слоение (drj^)2 > 0 ассоциированного с ней квадратично-
го дифференциала (drj^)2- Подобные слоения изучает теория Штребеля [107]. Наше слоение ортогонально линиям уровня функции W(x) := \Ref(eO) dr]\, глобально определённой на сфере в силу нормировки дифференциала drjM- В результате, слоение {drj^)2 > 0 устроено очень просто - его траектории не могут замыкаться или перемешиваться. Специально выбранные отрезки критических траекторий слоения вместе с множеством нулевого уровня функции W{x) образуют граф Г, рёбрам которого приписаны их длины в метрике квадратичного дифференциала. Все ограничения на топологию и веса графа Г могут быть легко перечислены, так что абстрактный нагруженный граф Г, удовлетворяющий этим формальным ограничениям, имеет реализацию как граф, связанный с некоторой кривой М пространства модулей. Фиксируя топологию графов Г и варьируя их веса, мы разбиваем каждое пространство модулей Tig на конечное число клеток А[Г], в которых частью естественных координат выступают периоды ассоциированного с кривой абелевого дифференциала drjM- В частности, сопоставляемые многочленам данной степени кривые М из пространства модулей в каждой клетке Л[Г] описываются системой линейных уравнений (0.9) в естественных координатах. Рассмотренное нами слоение (drju)2 > 0 Для кривой М, связанной с многочленом Рп(х), совпадает со слоением конфокальных гипербол с фокусами ±1, поднятым отображением Рп(х) на плоскость своего аргумента х.
Глава 5. Изучаются уравнения Абеля (0.9), описывающие в фиксированном пространстве модулей Tig точки, отвечающие многочленам степени п. Интегралы drjM по независимым нечётным 1-циклам С~ := —JC~ на кривой М локально задают отображение периодов на Tig. Как правило, пространство модулей неодносвязно и отображение периодов не продолжается до глобального, поскольку нетривиальный обход в пространстве модулей приводит к замене базиса в решётке нечётных 1-гомологий на кривой. Возникающая монод-ромия описывается представлением Бурау ([71], 1932) группы кос и исчезает при переходе к универсальной накрывающей Tig. В точках последней существует выделенный базис
пространства нечётных гомологии. Он получается параллельным переносом фиксированного базиса в отмеченной точке Mq по естественной плоской связности (Гаусса-Манина) в гомологическом расслоении. При этом левые части уравнений (0.9) задают глобальное отображение периодов из универсальной накрывающей в (д + 1)-мерное вещественное евк-i * лидово пространство. Образ Икд при этом отображении лежит на плоскости коразмернос-
* ти 1, т.к. интеграл по нечётному циклу, огибающему полюс дифференциала drjM, всегда *. одинаков. Мы найдём образ универсальной накрывающей в явном виде: при к — д + 1
это внутренность ^-симплекса, при к = д это объединение к открытых ^-симплексов и при к < д - счётное объединение открытых ^-симплексов, перечисляемых косами. Также мы покажем, что отображение периодов является субмерсией. В частности, порождённые многочленами степени п точки пространства модулей заполняют гладкие многообразия Т(-) размерности д, соответствующие решётке в правой части уравнений Абеля (0.9). При п —? со эти многообразия становятся всюду плотными в пространстве модулей.
Глава 6. Как же решать конкретные задачи о наименьнем уклонении в рамках предлагаемого подхода? Мы предлагаем решать такие задачи выбором подходящей подстановки
* (анзатца). Сначала необходимо "угадать" анзатц, т.е. провести исследование задачи и определить дискретные параметры д, к; то, mi,..., тд, соответствующие решению. Это связано с определением маломерной грани шара в пространстве многочленов (0.1), на которую попадает решение. Далее нужно составить и численно решить в пространстве модулей
* кривых систему из 2д трансцендентных уравнений для определения ассоциированной решению Рп(х) точки М 6 Ид. Уравнения Абеля выделяют многообразие Т(-) размерности д, точка на котором определяется при помощи данных экстремальной задачи - связей коэффициентов многочлена и границ множества Е. Мы преследуем две цели:
» , • Эффективное решение уравнения Абеля (0.9) в пространстве модулей кривых М.
• Эффективное вычисление экстремальных многочленов и их производных разных порядков по формуле (0.8) - для подчинения связям задачи о наименьшем уклонении.
Формулу (0.8) восстановления многочлена Рп по порождаемой им кривой М можно сделать эффективной при помощи римановых тэта функций [34, 77], либо функций Шот-
* тки [105, 72, 68]. Второй подход несколько проще, поскольку позволяет обойти численное решение известной проблемы Шоттки. Он был намечен Н.И.Ахиезером в [6] и доведён до
,Л численных результатов в [113,116]. Для эффективного решения уравнений Абеля и после-
дующего восстановления многочлена, мы униформизуем кривые М пространства модулей i специальными группами Шоттки. Суммируя тэта ряды Пуанкаре, мы получим абелевы
¦* дифференциалы на кривых и в частности dr)M. Уравнения Абеля и представление экстре-
мальных многочленов можно переписать в терминах глобальных координат универсальной накрывающей "Щ, связанных с параметрами образующих группы Шоттки &. После этого перед нами встаёт задача о навигации в пространстве модулей. Из произвольной точки И* нужно спуститься на высекаемое уравнениями Абеля гладкое многообразие Т и двигаясь
ф вдоль него найти точку М, отвечающую многочлену Рп{х) с заданными связями. Вариа-
ционные формулы главы 6 позволяют организовать различные варианты методов спуска [11] для решения задачи навигации.
* Заключение содержит основные результаты диссертации.
10
'* лись:
0.2 Характеристика работы
Методы исследования. В диссертации используются методы выпуклого анализа, ком- плексного анализа, численного анализа, теория приближений, римановы поверхности, гра- фы, теория групп, косы и их представления, квазиконформные отображения, пространства Тайхмюллера, гиперболическая геометрия, штребелевы слоения, теория униформизации, неравенства.
Практическая значимость. Результаты работы предоставляют возможность оптимизации следующих алгоритмов вычислительной математики, (i) Построение явных устойчивых разностных схем решения обыкновенных дифференциальных уравнений типа реализованных в известной программе DUMKA [84]. (ii) Чебышёвское ускорение при итерацион- ном решении больших систем линейных уравнений с невырожденной симметричной матри- цей. Методы данной работы могут быть применены при оптимизации электротехнических схем и частотных фильтров. Разработанные автором методы вычисления специальных функций, связанных с римановыми поверхностями, можно использовать при численном моделировании в конформной теории поля и теории конечнозонного интегрирования. Апробация работы. Результаты диссертации неоднократно докладывались и обсужда-
• в МИРАН им. Стеклова на семинаре Отдела комплексного анализа под руководством академика А.А.Гончара и профессора Е.М.Чирки;
• на Механико-математическом факультете МГУ на семинаре кафедры ОПУ под ру- ководством профессора В.М.Тихомирова;
• в МИРАН им. Стеклова на семинаре Отдела дифференциальных уравнений под руководством академиков Д.В.Аносова, А.А.Болибруха и профессора Ю.С.Ильяшенко;
• в Независимом Московском Университете на семинаре "Римановы поверхности, алгебры Ли и математическая физика" под руководством профессоров С.М.Натанзона, О.В.Шварцмана и О.К.Шейнмана;
• на Механико-математическом факультете МГУ на семинаре под руководством профессора Г.Б.Шабата;
• в ИВМ РАН на семинаре "Вычислительная математика и математическая физика" под руководством академика Н.С.Бахвалова и профессора В.И.Лебедева;
• в университете Кеплера (Линц, Австрия) на семинаре отдела теории приближений факультета естественных наук под руководством профессора Ф.Пехерсторфера;
«на Механико-математическом факультете МГУ на семинаре под руководством профессора А.И.Аптекарева;
• на международной конференции, посвященной 175-летию П.Л.Чебышёва; (Обнинск, 1996)
11
• на международной конференции "Теория приближений и гармонический анализ" (Тула, 1998);
• на международном семинаре "Orthogonal Polynomials" (Мадрид, 1998);
! * «на международной конференции "Foundations of computational mathematics" (Окс-
;J форд, 1999);
к
• на 6-м международном симпозиуме "Orthogonal polynomials, Special Functions and
Applications" (Рим, 2001);
На основе материалов диссертации в весеннем семестре 2000 года был прочитан курс лекций в университете Кеплера (Линц, Австрия).
Публикации Основные результаты диссертации содержатся в пяти печатных работах [112, 113, 114, 115, 116]. К теме диссертации относятся также следующие работы автора [117, 118, 119].
• Благодарности. Во время работы над диссертацией в 1997-2002 гг. автор получал стипендию OAD "Bewerber tiber aller Welt", грант Благотворительного фонда поддержки отечественной науки, грант РФФИ для молодых учёных 01-01-06299 и был поддержан грантами РФФИ 99-01-00141, 02-01-00651. Автор считает своим приятным долгом поблагодарить
• участников всех вышеперечисленных семинаров и своего научного консультанта профес-
• сора В.И.Лебедева.
0.3 Обозначения
С, Ж, Q, Wj, N - соответственно комплексные, вещественные, рациональные, целые, натуральные числа
Ш - расширенная вещественная прямая, окружность CPi = С - сфера Римана
• Ш:— (1бС; Im(x) > 0} - открытая верхняя полуплоскость ¦ - конец доказательства
М(е) - вещественная гиперэллиптическая кривая с дивизором ветвления е е := {^s}stzi — неупорядоченный набор из Ik вещественных точек и (д — к + 1) пар комплексно сопряжённых точек
• J - гиперэллиптическая инволюция кривой М J - антиконформная инволюция кривой М
1 С+, С~ - чётные и нечётные 1-циклы на кривой М
Н^(М,Щ - решётка (ранга д + 1) нечётных целых 1-циклов на кривой М LM - подрешётка Н{(М, Z)
(С*\С) -значение функционала (коцикла) С* на цикле С
df]M ~~ связанный с М (вещественный) абелев дифференциал 3-го рода с простыми полюсами на бесконечности, вычетами ±1 и чисто мнимыми периодами
* 21Х — компонента единицы афинной группы вещественной прямой
4 Вгт - группа чистых кос плоскости из т нитей
Ид - пространство модулей кривых М
Нк = Жд - универсальная накрывающая пространства модулей
12
Тдк - пространство Тайхмюллера д — к + 1 раз проколотого диска с 2к + 1 отмеченными
точками на его границе
(3 - свободное произведение д + 1 групп ранга 2 с образующими Gs, s = 0,1,... ,д; также
реализация этой абстрактной группы клейновой группой ; • fix Gs - неподвижные точки дробно линейного отображения Gs(u)
\ * & - группа Шоттки с образующими Si := GiGo, подгруппа индекса 2 в 0
¦ * бд - деформационное пространство специальной клейновой группы 0
д = {Gs}g=0 - элемент деформационного пространства, упорядоченный набор образующих
Gs группы 0
{ся,г3}1=1 - глобальные координаты в бд, связанные с параметрами дробнолинейных вращений Gs второго порядка
7Z(Q) - ограниченная мнимой осью и окружностями С\, Сг,..., Сд фундаментальная об-i ласть клейновой группы 0, порождённой элементом Q
ц(х), fi(x) dx/dx - коэффициент и дифференциал Бельтрами
Скд - пространство лабиринтов, модель универсальной накрывающей И*
• Л - собственно лабиринт, система из д + 1 специальных разрезов, попарно соединяющих точки дивизора ветвления е
HiHg - гомологическое расслоение над пространством модулей H^Tig - подрасслоение нечётных 1-гомологий
* QlrHg - расслоение вещественных абелевых дифференциалов с полюсами на бесконечности
П : uxVh -> Ж - глобальное отображение периодов
П_ : Ид —у Шд - сужение глобального отображения периодов на многообразие дифференциалов йг]м, ассоциированных с кривыми М
W{x) := \ReЩ^1 dr)M\ - глобально определённая функция (Грина) на сфере Г - конечное дерево, связанное со слоением (drjM)2 > О Г| - часть графа Г, множество нулей функции W(x) Г°. := Г.ПЕ; Г°+ := Г.пН, индекс • = I, _, или пустой
а(х) - срезающая функция ("шапочка"), равная 1 в комплексной окрестности х = О ae(t) - функция-домик Куранта вещественной переменной t 6(t) - ступенька Хэвисдйда вещественной переменной t jj{...} - число элементов множества i - подмножество в {1,2,..., д} мощности д — к + 1 ге(1) - коса из д + 2 нитей, построенная по i
72. - ограниченная 2д окружностями — Сд, ..., —Сг, —С\, С\, Сг,..., Сд фундаментальная область группы Шоттки © в главе б
{и, и'; z, z') - функция Шоттки, экспонента от абелева интеграла 3-го рода с полюсами z, z' на кривой в пределах и, и'
Еа(и) - экспонента от абелева интеграла 1-го рода в пределах со, и Esi - экспоненты от элементов матрицы периодов кривой diam(-) - евклидов диаметр множества
dist(-, •) - евклидово расстояние между точками и множествами Т>(&) - множество разрывности клейновой группы 0 Л(С5) — множество разрывности группы (3 Mod(e) - модулярная группа проколотой полуплоскости Н\е Dlu - частная производная порядка I по переменной и.
13
Глава 1
Задачи о наименьшем уклонении
Эту главу мы начнём с перечисления областей науки и техники, где встречаются задачи о ' наименьшем уклонении. Далее задачи наименьшего уклонения исследуются при помощи
* выпуклого анализа. Мы выводим обобщённый принцип альтернанса - критерий решения такой задачи. Этот принцип и является мотивировкой данного нами во введении определения экстремального многочлена: мы увидим, что чаще всего решениями становятся многочлены, которые во введении мы назвали экстремальными. Наконец, мы исследуем
* задачу Лебедева, решением которой оказывается экстремальный многочлен с д = г — 2.
1.1 Примеры оптимизации
1.1.1 Обращение симметричной матрицы
* : Рассмотрим типичный вычислительной алгоритм, оптимизация которого приводит к зада-
че о наименьшем уклонении. Решаем систему линейных уравнений Аи = / с невырожденной симметричной матрицей А и правой частью /. Для больших матриц, возникающих при дискретизации уравнений математической физики, прямые методы вроде гауссова исключения не работают, поэтому применяют итерационные алгоритмы определения решения. Рассмотрим простейший двучленный итерационный метод
fc uj+1 := Uj - olj{Auj - /), j = 0,1,2,...,
в котором параметры a.j находятся из условия минимизации ошибки Cj := Uj — и после п шагов метода. Ошибка на n-том шаге линейно выражается через начальную ошибку:
' ч €„ = Рп(А)е0, Pn(t) := П С1 - «**).
3=0
а её евклидова норма не превосходит нормы начальной ошибки умноженной на отклонение многочлена на спектре матрицы: maxtesp a \Pn(t)\. Вычисление спектра - задача ещё более трудоёмкая, чем решение системы линейных уравнений. Однако часто, например из t физических соображений, известен диапазон Е, в котором лежит спектр матрицы. В этом
случае за параметры итерационного процесса берут величины, обратные корням решения
• следующей задачи на минимум. Среди многочленов пространства (0.1), удовлетворяю-
• щих ограничению Рп{0) = 1, найти многочлен с минимальной равномерной нормой на компакте Е вещественной оси.
14
1.1.2 Задача на собственные значения
Для нахождения собственных значений Л симметричной матрицы А, лежащих вблизи данного числа, применяют итерации вектора щ общего положения [11]:
:= Рп{А)щ
,
с некоторым вещественным многочленом Рп{х). Если многочлен велик вблизи собственного числа Ло и мал на остальном спектре матрицы (а таким свойством обладают, например подходящие многочлены Золотарёва (0.3)), тогда отношение (uj+1,Uj)/(uj,Uj) при j —> со сходится к Рп(Ао). Соответствующее собственное значение Ло можно найти решением алгебраического уравнения.
1.1.3 Явные методы Рунге-Кутты
Явные схемы решения задачи Коши для обыкновенных дифференциальных уравнений
обладают многими достоинствами: они просты при реализации, легко распараллеливаются и требуют немного памяти по сравнению с неявными схемами. Вместе с тем, условие устойчивости Куранта накладывает в случае жёстких задач (когда решение обладает быстро меняющейся компонентой) чрезмерные ограничения на величину шага h. Скажем, для простейшей схемы Эйлера
\ t* \ J i^ ft * & j ^T * *~ J •* Y is j / J / i J л^ * j 7 */ / j у
локальное условие устойчивости принимает вид /г < 2/А, где А - спектральный радиус матрицы Якоби отображения /(г/, t) в текущий момент. Если решаемая система уравнений (1.1) получена дискретизацией по пространственным переменным эволюционного уравнения математической физики, то величина А может быть очень большой: например, разностный оператор Лапласа в пределе неограничен. Использование переменных шагов по времени позволяет значительно увеличить среднюю величину шага без потери устойчивости метода [31]. При грамотном построении разностной схемы первого порядка точности коэффициент увеличения среднего шага по сравнению с методом Эйлера может достигать нескольких миллионов. Применяя многостадийный метод Рунге-Кутты с шагом h, составленным из п более мелких шагов, к простейшему уравнению dy/dt = —Ay, A > О, получаем связь приближенных решений в соседних узлах: yJ+i := Pn(Xh)yj, где Рп{х) -вещественный многочлен степени п, называемый функцией устойчивости метода. Если метод Рунге-Кутты имеет порядок точности г — 1, то его функция устойчивости должна приближать с тем же порядком показательную функцию в нуле [84]:
Рп{х) = 1-х + х2/2 -... + {-x)r-l/(r - 1)! + xrPn.r(x), deg Fn_r (x)
Максимизация области устойчивости {х : |Pn(a:)| < 1} метода Рунге-Кутты на вещественной оси, например при решении уравнений параболического типа методом прямых, и приводит к задаче Б из введения [32, 96]. Корни классических многочленов Чебышева и Золотарёва используются в алгоритме программы DUMKA [84], оказавшейся эффективной при решении многих нелинейных эволюционных задач математической физики [111].
15
4
1.1.4 Другие приложения
задач типа наименьшего уклонения в равномерной метрике включают:
• Выбор узлов интерполяции определённых на Е функций заданной гладкости [11].
• Одномерные квадратурные формулы типа Гаусса [93, 11].
• Проектирование электротехнических приборов, частотные фильтры [4, 73].
1.2 Анализ оптимизационных задач
Среди решений задач наименьшего уклонения чаще других встречаются многочлены, становящиеся после нормировки экстремальными в смысле данного ранее определения. Причину этого объясняет выпуклый анализ [50, 45]. Исследуем задачу А из введения:
Минимизировать норму ||Рп||б многочлена при заданных линейных связях на его коэффициенты, Е - совокупность нескольких вещественных отрезков.
Решение задачи ищется в пространстве (0.1) на заданной афинной плоскости Ln+i-r коразмерности г. Такую [п +1 — г)-плоскость можно описывать как сдвинутый аннулятор r-мерного подпространства L* сопряженного пространства. Всякому ненулевому многочле- ну Т(х) пространства (0.1) сопоставим определяемый ниже многогранный выпуклый конус в этом же сопряженном пространстве. Экстремальными точками многочлена Т(х) относительно Е назовём множество ех^(Г) := {х € Е : Т(х) = ±||Т||?;}, с каждой точкой х которого свяжем функционал х* над пространством многочленов: (х*\Р) := P(x)-signT(x). Многочлену Т мы сопоставим коническую оболочку этих функционалов
m
sx*s: as > 0;?as > 0}, m = textE(T). (1.3)
S=l 3=1
Эта оболочка не содержит нуля, т.к. (^Llaex*\T) = X^iQ^H^IU > 0. Двойственным конусом назовём конус многочленов, положительных на каждом функционале из (1.3) (отметим, что стандартное определение требует лишь неотрицательности).
Теорема 1 Многочлен Т 6 Ln+i-r доставляет минимум в задаче А о наименьшем уклонении тогда и только тогда, когда направляющая плоскость L* пересекает ассоции- рованный с многочленом конус (1.3).
Замечание: Конус в формулировке теоремы, порождённый всеми экстремальными точками многочлена Т, можно по принципу Каратеодори заменить на конус, порожденный не более чем п + 2 — г экстремальными точками. С этим уточнением теорема 1 является интерпретацией критерия экстремальности из [108, 50].
Доказательство: Многочлен Т € Ln+\-r не является решением задачи А если и только если норма многочленов уменьшается в некотором выпущенном из Т направлении, лежащем в плоскости Ln+i-r. Такое направление задается многочленом Р(х), обнуляющим все функционалы подпространства L* и имеющим в экстремальных точках Т тот же знак что и сам Т. Тем самым, равносильны два утверждения: Т - решение задачи А и аннулятор
16
L* не пересекает конуса, двойственного к (1.3). Дуализация второго утверждения даёт критерий теоремы.
1. Пусть пересечение подпространства L* с конусом (1.3) непусто и содержит функционал р*. Пересечение двойственных объектов: (L*)1 П {двойственный конус} Э Р{х)
4 приводит к противоречию 0 = (р*|Р) > 0.
« 2. Пусть подпространство L* не пересекает конуса (1.3), напомним что последний не
¦ содержит своей вершины. По индукции мы расширим L* до гиперплоскости, не пересекающей конус. Эта гиперплоскость является аннулятором многочлена, лежащего и в двойственном конусе и в аниуляторе L*. На каждом шаге, если г < п, проведём двумерное подпространство L\, линейно независимое с L*. Его пересечение с выпуклым конусом L* + сопе{х\,Х2, ...,:г^,} есть двумерный выпуклый конус с углом раствора меньшим тг, ибо он не содержит нуля. Значит, L*2 содержит одномерное подпространство L\, не пересекающее L* + сопе{х\,Х2, ...,Хт, }• Полагая L*+1 — Ь^+Ь*, мы совершаем шаг индукции.
-и
* При фиксированном множестве Е вещественной оси, задачи А о наименьшем уклонении
* различаются положением плоскости Ln+i_r, а значит перечисляются точками вещественного проективного грассманиана Gr(n + 2, п + 2 — г) размерности г(п + 2 — г). Как видим, возможных задач намного больше чем решений, поэтому естественно подсчитать частоту появления каждого многочлена из (0.1) среди решений задач о наименьшем уклонении.
« Афинные плоскости .Ln+i_r, проходящие через заданную точку пространства перечисля-
* ются направляющими подпространствами L* € Gr(n + 1,г).
Теорема 2 Фиксированный многочлен Т является решением задач А, которым в грассманиане Gr(n+1, г) отвечает лежащее на цикле Шуберта коразмерности max(0, п+ 2 — г — ^extis(T)) замкнутое множество с непустой внутренностью.
Доказательство: Пересекающие конус (1.3) подпространства L* образуют замкнутое множество в грассманиане Gr(n + 1,г), т.к. присоединение вершины делает конус замкнутым. Всё это множество лежит на некотором цикле Шуберта.
• Функционалы, порождающие конус (1.3) многочлена Т(х), линейно независимы, если их число m := Цех^(Т) не превосходит размерности пространства многочленов (0.1). Пусть линейная оболочка конуса (1.3) содержится в фильтрации сопряжённого пространства:
0/— TCP* /— Ш>2 г- г- ТО>п+1 с к с к. с ... с ж.
Если подпространство L* пересекает конус, то справедливо первое неравенство в системе (а остальные - из соображений размерности):
dim(L; П Mmin(ro'n+1)) > 1; dim(L; П Rn+i+1-r) > s, s = 1,2,..., г,
означающей что L* принадлежит циклу Шуберта, диаграмма Юнга которого это прямоугольник размеров (п + 1 — г) х г, с вырезанной из правого нижнего угла горизонтальной строкой длины max(n + 2 — г — га, 0). Укажем теперь область на этом цикле Шуберта, все элементы которой пересекают конус (1.3).
• В ходе доказательства теоремы 1 мы установили существование проходящей через вер-, шину конуса (1.3) опорной гиперплоскости, не пересекающей его самого. Рассмотрим любое подпространство L* размерности / := min(m, п + 2 — г) — 1 в пересечении этой опорной
17
ICQ: 638099552 (в сети)
Тел.: +7 (928) 260-05-38 (на связи)
Почта.: 
Интересные работы (за сутки)
Новые поступления
