автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Моделирование многомерных объектов и методы полиномиальной оптимизации

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

ЯШИНА Марина Витальевна

МОДЕЛИРОВАНИЕ МНОГОМЕРНЫХ ОБЪЕКТОВ И МЕТОДЫ ПОЛИНОМИАЛЬНОЙ ОПТИМИЗАЦИИ

05.13.18 — Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

0034Ьиаго

Санкт-Петербург — 2009

003460976

Работа выполнена на кафедре математического моделирования энергетических систем факультета прикладной математики — процессов управления Санкт-Петербургского государственного университета.

Научный руководитель: доктор физико-математических наук,

профессор Утешев Алексей Юрьевич Официальные оппоненты: доктор физико-математических наук,

профессор

Демьянов Владимир Федорович доктор физико-математических наук, профессор

Флегонтов Александр Владимирович Ведущая организация: Объединенный институт ядерных

исследований, г. Дубна Московской обл.

Защита состоится " 15 " ср££]иа.1-Ш< 2009 г. в ч. &-р мин. на заседании диссертационного совета Д.212.232.50 по защите диссертаций на соискание ученой степени доктора наук при Санкт-Петербургском государственном университете по адресу: 199034, Санкт-Петербург, В.О., Университетская наб., 7/9, Менделеевский Центр.

С диссертацией можно ознакомиться в научной библиотеке им. М. Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, В.О., Университетская наб., 7/9. Автореферат размещен на сайте www.spbu.ru

Автореферат разослан " ".ЬАА&^иЬ 2009 г.

Ученый секретарь

диссертационного совета

доктор физико-математических наук,

профессор Курбатова Г.И.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Алгебраическая геометрия и геометрическое моделирование имеют дело с кривыми и поверхностями в М", заданными полиномиальными (алгебраическими) уравнениями. Алгебраическая геометрия исследует теоретические свойства алгебраических кривых и поверхностей; геометрическое моделирование использует полиномиальные, кусочно-полиномиальные н дробио-рациональпые функции для построения компьютерных моделей механических компонент при конструировании промышленных объектов и производств1.

Среди множества математических задач, возникающих в этом разделе вычислительной геометрии (computational geometry), одной из важнейших является

1) задача вычисления расстояния между алгебраическими многообразиями и, связанные с ней,

2) задача установления наличия пересечения этих многообразий что соответствует, например, столкновению движущихся объектов (collision detection) и

3) задача кластеризации точечного множества в К" эта задача возникает естественным образом при анализе результатов измерений, подверженных воздействию случайных погрешностей.

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

'Algebraic Geometry and Geometric Modeling : сб. ст. / под ред. L. Gonzalez-Vega. ACIGM'OG. Barcelona, 200C. - 139 P.

алгебраической геометрии. Объектом его применения стали полиномиальные целевые функции и множества, границы которых описываются алгебраическими уравнениями. В рамках этого подхода были получены решения некоторых теоретических и практических задач в R2 и R3. Вместо. с тем, остался нерешенным ряд актуальных задач, одной из которых является задача определения расстояния между квадратичными поверхностями в М3 — главным образом, эллипсоидами. Актуальность задачи обусловлена тем обстоятельством, что эллипсоиды оказались наиболее простыми геометрическими объектами подходящими для моделирования трехмерных множеств и физических тел в молекулярной физике, геодезии, приборостроении, компьютерной графике (особенно в задачах компьютерного зрения (computer vision))2. Особенный интерес представляют динамические задачи — когда объекты перемещаются в пространстве по известным траекториям.

В n-мерпом пространстве эллипсоиды возникают естественным образом в задаче класспфнкции (кластеризации) данных. При описании объекта набором из п признаков, каждая серия их измерений задаст точку в параметрическом пространстве. При недостоверности результатов измерений, каждую из точек можно рассматривать как аппроксимацию объекта, самым простым приближением которого может считаться эллипсоид (который может быть иптерпротнрован как эллипсоид рассеяния из математической статистики)'5. Однако отсутствие общего алгоритма нахождения расстояния от точки до эллипсоида в К" приводит к тому, что при расчетах вместо точного расстояния используется его приближенная оценка (панример, расстояние Махалонобиса).

Целью диссертационной работы является разработка конструктивных алгоритмов нахождения расстояния между объектами в Rn, а

^Bischoff S., Kobbelt L. Ellipsoid decomposition of 3D-modcls. // First International Symposium on 3D Data Processing Visualization and Transmission, 2002. Proceedings, pp. 480—488.

'Лагутин М.Б. Наглядная математическая статистика. M.: БИНОМ. Лаборатория знаний, 2007.

472 с.

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

1) нахождение условии пересечения эллипсоида и линейного многообразия и в случае их нспсрессчспия вычисление расстояния между этими поверхностями как корпя алгебраического уравнения,

2) нахождение условий пересечения эллипсоида и квадрики, и в случае нх иеперсссчения вычисление расстояния между поверхностями как корпя алгебраического уравнения,

3) нахождение ближайших точек рассмотренных поверхностен,

4) исследование влияния па функцию расстояния параметров, входящих в уравнения поверхностей и возможности моделирования поверхностей с заданными аппроксимирующими свойствами.

Методы исследований. Применением метода множителей Лагран-жа задача сводится к решению системы алгебраических уравнений. Для решения этой системы предлагается использовать не численные (итерационные) методы, а аналитические — технику многомерных результантов для исключения переменных в системах алгебраических уравнений. Именно этот альтернативный подход к решению классической задачи является принципиально новым.

Основные положения, выносимые на защиту:

1) критерий пересечения алгебраических поверхностей в К": эллипсоида и линейного многообразия, эллипсоида и квадрики;

2) метод нахождения расстояний между указанными поверхностями;

3) алгоритм нахождения расстояния от заданной точки до эллипса в К2, движущегося по уппкурсальпой траектории;

4) метод нахождения ближайших точек во всех указанных задачах;

5) созданный па основе разработанных алгоритмов и оттестированный па примерах комплекс программ (с применением системы аналитических вычислений MAPLE), позволяющий выявить наличие пересечения двух поверхностей в Rn, и, в противном случае, произвести расчет расстояния между ними и нахождение ближайших точек.

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

Теоретическая и практическая цешшость. Абсолютная достоверность полученных качественных и количественных результатов позволяет использовать разработанные алгоритмы для моделирования тестовых примеров при расчете различных вычислительных схем. Результаты работы могут быть использованы для задач многомерного моделирования в молекулярной физике, химии, компьютерной графике, геодезии и приборостроении.

Результаты исследований прошли апробацию па

• международном математическом конгрессе ICM'06 (Мадрид);

• международном конгрессе но индустриальной и прикладной математике 1С1АМ'07 (Цюрих);

• международной конференции "Компьютерная алгебра в научных вычислениях" CASC'07 (Бонн);

• научных конференциях "Процессы управления и устойчивость" факультета прикладной математики - процессов управления Санкт-Петербургского государственного университета (С.-Петербург, 2005 и 2006 гг.);

• семинарах кафедры математического моделирования энергетических систем факультета прикладной математики - процессов управления.

G

Публикации. По материалам диссертации опубликованы семь работ, три из которых в изданиях, входящих в перечень ВАК рецензируемых научных журналов [4, 6, 7]. Список работ приведен в конце автореферата.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Объем работы составляет ИЗ страниц, работа содержит 9 рпсупков. Синеок литературы включает 48 наименовании.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

Первая глава носит вспомогательный характер и содержит краткую сводку результатов высшей алгебры, используемых в диссертационном исследовании. Основным математическим аппаратом при решении задач, поставленных в диссертации, является теория исключения неременных в системах нелинейных полиномиальных уравнений. Существенно используется понятие дискриминанта V полинома одной н двух переменных — как функции коэффициентов полинома, отвечающей за наличие у него кратных корней. Указываются конструктивные способы построения дискриминанта, а также вычисления кратного корня (в случае наличия), по коэффициентам заданного полинома.

Вторая глава содержит шесть параграфов и посвящена нахождению расстояния от эллипсоида

ХТАХ + 2ВТХ = 1 (1)

до линейного многообразия, заданного системой уравнений

С^Х = О, С%Х = 0,..., С%Х = 0. (2)

Здесь X е К" -■- столбец переменных; {B,Ci, С2, ■ ■ ■ ,Ck} С Е" — заданные столбцы, причем С\, ..., Ск (к < п) предполагаются линейно независимыми; А — заданная симметричная, зиакооиределепная матрица п -го порядка; т означает транспонирование. Расстояние понимается в евклидовой метрике: требуется найти

d min yJ(X - Y)T{X - Y) при X € (1), Y e (2).

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

Теорема 1. Условие

;(—l)fc_1, если А положительно определена, (—1)", если А отрицательно определена

(3)

необходимо и достаточно для того, чтобы поверхности (1) и (2) пересекались; в этом случае d = 0. Здесь матрица

С '= [СЬС2,... ,Ck\-

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

V(X) = ХТАХ + 2ВТХ - 1

па поверхности (2). Условие (3) получается сравненном знаков функции V(X) в стационарной точке на многообразии и на бесконечности.

Во втором параграфе решается задача нахождения расстояния между поверхностями (1) и (2). Доказана следующая теорема:

Теорема 2. Если условие (3) не выполняется, то квадрат расстояния между поверхностями (1) и (2) совпадает с минимальным положительным корнем уравнения

T{z)dävll{likm{ß,z)) = o, (4)

о <

АБС ВТ -1 О

сг о о

в предположении, что этот корень не является кратньш. Здесь Т> дискриминант полинома, рассматриваемого по переменной //./ а

А В

ВТ -1+цг

ст О

1 г

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

Р(Х,У) = {Х- У)Т{Х - У), при условии X е (1), У 6 (2).

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

г - (X - У)Т(Х - У) = 0.

Переменная г отвечает за критические значения минимизируемой функции. К полученной расширенной системе уравнений применяются методы теории исключения; за счет удачного введения параметра удастся свести задачу к решению одного алгебраического уравнения (4) относительно переменной 2.

В третьем параграфе предложен метод, позволяющий но найденному минимальному положительному корню полипома (4) восстановить координаты ближайших точек рассматриваемых поверхностей. При выполнении условия теоремы 2 эти координаты можно выразить в виде рациональных функций указанного корня. Таким образом, идейное содержание предложенного в этой главе (и развиваемого в последующих главах) подхода заключается в реверсии традиционной для задач оптимизации схемы решения: стационарные точки —> критические значения целевой функции.

Четвертый параграф поевящеи исследованию важного частного случая -- когда линейное многообразие (2) вырождается в точку.

Теорема 3. Квадрат расстояния от точки Хо € до эллипсоида (1) совпадает с минимальным положительным корнем уравнения

Х0

'а В ' ' -Е

Вт -1

= 0, (5)

в предположении, что этот корень не является кратным и

Х^АХо + 2ВТХ0 -1^0.

Здесь Т> дискриминант, полинома, рассматриваемого по переменной ц, Е единичная матрица порядка п.

В частном случае, когда Х0 = О, можно привести более удобный вариант последнего результата.

Теорема 4. Квадрат, расстояния от начала координат до э.алипсоида (1) совпадает с минимальным положительным корнем уравнения

Г(г) ^ V|l{f{^^){^^г - 1) - Втд(А,/х)Б) = 0,

(6)

в предположении, что этот корень не является кратным. Здесь Т> — дискриминант полинома, рассматриваемого по переменной /г; /(/¿) ''== ёеЦА — /хЕ) — характеристический полином матрицы А, а q(A,|l) -- присоединенная матрица для характеристической матрицы А - ¡¿Е.

Следствием последней теоремы является известное в литературе экстремальное свойство собственных чисел симметричной матрицы: расстояние от начала координат до эллипсоида ХТАХ = 1 равно 1 / >/Атах, где Ашах обозначает максимальное собственное число матрицы А. _ Наряду с доказанными теоремами этот параграф содержит ряд примеров, носящих иллюстративный и качсствснпо-аналитичсекпй характер. Также в этом параграфе обсуждаются исключительные случаи: как,

например, существенность содержащегося в теоремах 2 4 условия простоты минимального положительного корпя полипома

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

Теорема 5. Расстояние от эллипсоида (1) до (п — I)—мерной плоскости СТХ = 0 дается формулой

в предположении, что указанные поверхности не пересекаются.

В шестом параграфе анализируются некоторые свойства полиномов из теорем 2 и 3. Показывается, что в общем случае степень из теоремы 2 равна 2к. В случае п = 2 анализ количества вещественных корней полинома 3-(г) из формулы (5) в зависимости от положения точки Хо € К2 приводит к классической задаче античности задаче Аполлония о количестве перпендикуляров, которые можно опустить из точки плоскости па коническое сечение.

Результаты данной главы опубликованы в работах [1, 3, 4, 6].

Третья глава содержит восемь параграфов и посвящена нахождению расстояния от эллипсоида

Здесь X € К" — столбец переменных; {Вг, В2} С Ж" заданные столбцы; Аь Аг — заданные симметричные матрицы п - го порядка, причем матрица А1— знакоонрсделенная. Расстояние понимается в евклидовой

ХТА1Х + 2В1X = 1

(7)

до квадрики

ХТА2Х + 2В$Х = 1.

(8)

метрике: требуется найти

ф(2) = Т>х det

-А 'А! В,'

.в! -1.

= 0

(9)

d dÜ min yJ(X - Y)T(X - Y) при X e (7), Y € (8).

В первом параграфе доказано необходимое и достаточное условие пересечения поверхностей.

Теорема 6. Поверхности (7) и (8) пересекаются тогда и только тогда, когда среди вещественных корней уравнения

А2 В2 Bl -1-z

имеются числа разных знаков или нуль; в этом случае d = 0. Здесь Т> — дискриминант полинома, рассматриваемого относительно переменной А.

Идея доказательства аналогична той, что лежит в основе доказательства теоремы 1.

Во втором параграфе решается задача поиска расстояния между поверхностями (7) и (8). Доказана следующая теорема:

Теорема 7. Если условие пересечения из теоремы 6 не выполняется, то квадрат расстояния от эллипсоида (7) до квадрики (8) совпадает с минимальным положительным корнем уравнения

F{z) d= T>lh ,,l2 ( det (

A2 B2 BT -1

- (10)

= 0

А! Вг В1 -1 А2А1 А 2Вх

В2В\ - 1Л1Ц2г

в предположении, что этот корень не является кратным. Здесь V — дискриминант полинома, рассматриваемого по переменным и ц2.

Идея доказательства схожа с той, что лежит в основе доказательства теоремы 2. Применение метода множителей Лагранжа и введение дополнительного уравнения г — (X — У)Т(Х — У) = 0 позволяет свести задачу к исключению переменных из системы алгебраических уравнений.

Третий параграф посвящен алгоритму нахождения координат ближайших точек поверхностей но вычисленному минимальному положительному корню полинома (10). При выполнении условия теоремы 7 эти координаты можно выразить в виде рациональных функций указанного корпя. Здесь же подробно разобран иллюстрирующий пример для случая п = 3.

В четвертом параграфе приводятся блок-схемы комплекса программ, реализующего разработанные в главах 2 и 3 алгоритмы в среде системы аналитических вычислений МАРЬЕ, позволяющих для двух поверхностей выявить наличие пересечения, и в противном случае произвести вычисление расстояния между поверхностями и нахождение соответствующих ближайших точек. Результаты расчетов тестовых примеров приведены в пятом параграфе.

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

В седьмом параграфе проводится анализ важного частного случая рассматриваемые квадрики становятся центральными: В\ — О, В2 = О.

Теорема 8. Пусть ХТАхХ = 1 и Хт А^Х = 1 — квадрики в Еп, причем первая является эллипсоидом. Квадрики не пересекаются тогда и только тогда, когда матрица А} — А2 является знакоопределенноу}. При выполнении этого условия квадрат расстояния между квадриками совпадает с минимальным положительным корнем уравнения

Т{£) =' аде^АА! + (г- А)А2 - \{г - \)А1А2)) = 0, (11)

4Услошк? пересечения известно п литературе, оно не принадлежит актору диссертации

в предположении, что этот корень не является кратным. Здесь V — дискрилшнант полинома, рассматриваемого относительно переменной А.

В восьмом параграфе анализируются некоторые свойства полиномов 2-(г) из теорем 7 и 8, выявляется структура их "посторонних" множителей.

Результаты данной главы опубликованы в работах [2-7].

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

Во втором параграфе решается задача о нахождении расстояния от точки до движущегося плоского объекта. Эта задача рассматривается на частном примере движения эллипса но траектории, описываемой рационально иараметризпруемой (упикурсальной) кривой, т.е. кривой в Е2, заданной параметрическими уравнениями х = ф(Ь),у = при ф(Ь) и ф(Ь) рациональных функциях от параметра Фактически, ставится задача нахождения расстояния от точки до семейства эллипсов

{К(} = {Хг А(*)Х + 2ВГ(^Х - 1 = 0 | I € [о, Ь]} . (12)

Доказана следующая теорема:

Теорема 9. Квадрат расстояния от точки Хо € К" до ближайшего эллипсоида семейства (12) совпадает с минимальным положительным корнем одного из уравнений

Здесь ^(г, £) — полином (5), дискриминант V вычисляется относительно переменной Ь, а указанный корень не является кратным.

В заключении сформулированы результаты диссертационной работы, выносимые на защиту:

1) критерий пересечения алгебраических поверхностей в R": эллипсоида н линейного многообразия, эллипсоида и квадрики;

2) метод нахождения расстояний между указанными поверхностями;

3) алгоритм нахождения расстояния от заданной точки до эллипса в R2, движущегося по уиикурсалыюй траектории;

4) метод нахождения ближайших точек во всех указанных задачах;

5) па основе разработанных алгоритмов создай и оттестирован па примерах комплекс программ (с применением системы аналитических вычислений MAPLE), позволяющий выявить наличие пересечения двух поверхностей в К", и, в противном случае, произвести расчет расстояния между ними и нахождение ближайших точек.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. А.Ю.Утсшев, М.В.Яшина. Нахождение расстояния между эллипсоидом и гиперплоскостью в R". //Процессы управления и устойчивость: труды 36-й межвузовской научной конференции аспирантов и студентов. СПб. 11-14 апреля 2005 г. СПб.: Изд-во С.-Петерб. ун-та, 2005. С. 112-115.

2. А.Ю.Утсшев, М.В.Яшина. Нахождение расстояния между поверхностями второго порядка в К.". //Процессы управления и устойчивость: труды 37-й межвузовской научной конференции аспирантов и студентов. СПб. 10-13 апреля 2006 г. СПб.: Изд-во С.-Петерб. ун-та, 2006. С. 103-107.

3. A.Yu.Utcshev, M.V.Yashina. Distance computation from an ellipsoid to a linear or quadric surface in R". //International Congress of Mathematicians. Madrid 2006. Abstracts. European Mathematical Society, 2006. P. 504.

4. A.Yu.Uteshev, M.V.Yashina. Distance Computation from an Ellipsoid to a Linear or a Quadric Surface in Rn. // Proceedings of the 10th Workshop

CASC07 (Computer Algebra in Symbolic Computations), Bonn 2007, Springer, Lecture Notes in Computer Science V. 4770, 2007. P. 392-401.

5. A.Yu.Uteshev, M.V.Yashina. Distance evaluation between quadric surfaces in R". //6th International Congress on Industrial and Applied Mathematics, Zurich, 2007. Abstracts. ICIAM 07, 2007. P. 444.

6. А.Ю.Утсшев, М.В.Яшина. Нахождение расстояния от эллипсоида до плоскости и квадрики в К". //Доклады Академии наук, т. 419, № 4, 2008. С. 471-474.

7. М.В.Яшина. О метрической проблеме для поверхностей второго порядка в К". //Вестник СПбГУ, серия 10 (прикладная математика), выи. 3, 2008. С. 53-57.

Подписано в печать: 12-01-2009 Тираж: 100 экз. Заказ № 0030 объем: 1 п.л.

Отпечатано в цифровой типофафии АКТ-ХРЯЕББ 199155, Санкт-Петербург, ул. Уральская, д. 17 тел.: 331-33-22 www.art-xpress.ru

Введение.

Постановка задачи, ее значение, обзор предшествующих исследований.

Общая характеристика работы.

Глава 1. Использемые результаты высшей алгебры.

Глава 2. Расстояние от эллипсоида до линейного многообразия.

2.1. Условия пересечения.

2.2. Нахождение расстояния.

2.3. Нахождение ближайших точек поверхностей.

2.4. Расстояние от точки до эллипсоида.

2.5. Расстояние от (п — 1)-мерной плоскости до элипсоида

2.6. Некоторые свойства полинома Т{г).:.

Глава 3. Расстояние от эллипсоида до квадрики.

3.1. Условия пересечения.

3.2. Нахождение расстояния.

3.3. Нахождение ближайших точек поверхностей.

3.4. Программная реализация алгоритмов.

3.5. Вычислительные эксперименты.

Постановка задачи, ее значение, обзор предшествующих исследований

Алгебраическая геометрия pi геометрическое моделирование имеют дело с кривыми и поверхностями в IRn, заданными полиномиальными (алгебраическими) уравнениями. Алгебраическая геометрия исследует теоретические свойства алгебраических кривых и поверхностей; геометрическое моделирование использует полиномиальные, кусочно-полиномиальные и дробно-рациональные функции для построения компьютерных моделей механических компонент при конструировании промышленных объектов и производств [29].

Среди множества математических задач, возникающих в этом разделе вычислительной геометрии (computational geometry), одной из важнейших является

1) задача вычисления расстояния между алгебраическими многообразиями и, связанные с ней,

2) задача установления наличия пересечения этих многообразий — что соответствует, например, столкновению движущихся объектов (collision detection) и

3) задача приближения (аппроксимации) точечного множества в Rn — эта задача возникает естественным образом при использовании результатов измерений, подверженных воздействию случайных погрешностей.

Решение общей задачи вычисления расстояния между алгебраическими многообразиями, заданными в Мп системами уравнений вида

9i{X) = 0,., 9к(Х) = 0 при X = хп / при полиномиальных д\,.достаточно просто в случае многообразий линейных. Так, к примеру, растояние от точки Хо 6 до многообразия

СТХ — Н при С = Си . с1т ^

021 • • • С2т

Л^ Кп ) пхт у Сп\ . • . Спт у предполагается, что т < п и что ранг матрицы С равен ш; здесь и далее Т означает транспонирование; расстояние понимается в евклидовой метрике) определяется по формуле

I =

1е1 Ст • С СГХ0 - Н

V (СГХ0 ну О det(Cт • С) т.е. фактически сводится к решению квадратного уравнения [26].

Формула для расстояния между двумя линейными многообразиями в ]КП также известна в литературе. Пусть линейные многообразия в К" заданы параметрически

X = + АЛ + . + ХкХк и У = У0 + Д1У1 + . + при {Ах,., /¿1,., [11} С М и при фиксированных столбцах

Х0) Х\,., Хк, Уо, У1;., С Мп.

Составим из этих столбцов матрицы

Р = [Хи ., Хк, Ух, • ■ •, Уе]пх(к+е) и

Р = [^ъ ■ • • > Хк, Уъ • ■ •> Уе, Х0 - Уо]пх(^+1) •

Тогда расстояние вычисляется по формуле

1еЬ(Рт • Р) det(Pт • Р)

В случае когда хотя бы одна из поверхностей задается нелинейными уравнениями, задача существенно усложняется и не была полностью решена даже в такой ее частной постановке, как нахождение расстояния от точки Х0 Е Rn до квадрики в Rn, заданной уравнением

ХТАХ + 2ВТХ -1 = 0 при фиксированных симметричной матрице А и столбце В £ Мп. Практическая же важность этой задачи обусловлена тем обстоятельством, что, например, в случае п = 3 эллипсоиды оказались наиболее простыми геометрическими объектами, подходящими для моделирования множеств и физических тел в молекулярной физике, геодезии, приборостроении, компьютерной графике (особенно в задачах компьютерного зрения (computer vision))[31]. В n-мерном пространстве эллипсоиды возникают естественным образом в задаче классификции (кластеризации) данных. При описании объекта набором из п признаков, каждая серия их измерений задает точку в параметрическом пространстве. При недостоверности результатов измерений, каждую из точек можно рассматривать как аппроксимацию объекта, самым простым приближением которого может считаться эллипсоид (который может быть интерпретирован как эллипсоид рассеяния из математической статистики) [7, 11]. Однако отсутствие общего алгоритма нахождения расстояния от точки до эллипсоида в Мп приводит к тому, что при расчетах вместо точного расстояния используется его приближенная оценка (например, расстояние Махалонобиса).

В идеологии решения общей задачи нахождения расстояния между гладкими поверхностями лежит вариационный принцип трансверсальности: кратчайшее расстояние между этими поверхностями достигается на их общей нормали (см. §54 книги [10]). В случае поверхностей, заданных алгебраическими уравнениями, этот принцип дает возможность использовать метод множителей Лаграпжа. Так, к примеру, для задачи вычисления расстояния между двумя квадриками в М3, заданными алгебраическими уравнениями

ХтАгХ + 1В\Х -1 = 0

1) и

ХтА2Х + 2В\Х -1 = 0, (2) функция Лагранжа будет иметь вид

Х% У, Ах, Л2) = (X - У)Т(Х - У) - Х^АгХ + 2ВГ{Х -1) -- А2(УтА2У + 2£2тУ-1), а соответствующая система: дГ 2 [(X — У) — \1{АгХ + В0] = О, = 2 [(У — X) — \2{А2Х + В2)} = О, = - [ХГА1Х + 2В\Х — 1] = 0, ^ дх = - [УгА2У + 25;гУ — 1] = 0. ар

9У ар алх дР1

3)

Требуется найти решения этой системы относительно векторов {X, У} С К3, обеспечивающих минимум целевой функции

X - У)Т{Х - У).

Система (3) является нелинейной алгебраической относительно входящих в нее неизвестных: каждое из 8 ее уравнений является квадратным. Для решения подобных систем имеются два подхода: первый основан на применении приближенных методов решения систем нелинейных уравнений; все подобные методы представляют из себя модификации метода Ньютона. В этом русле велись исследования [39, 40]. К достоинствам такого подхода следует отнести быструю сходимость итераций к экстремуму целевой функции, к недостаткам — традиционное для ньютоно-подобных методов отсутствие гарантии того, что найденный экстремум обеспечивает глобальный минимум целевой функции. В подтверждении этого произведем качественную оценку потенциально возможной ситуации. В главе 3 будет показано, что система (3) имеет, как правило, 24 решения, в общем случае комплексных. Таким образом, имеется не более 24 потенциально возможных результатов итерационных процедур для произвольных стартовых значений итерационного процесса. Если бы применение итерационного метода дало с необходимой точностью все 24 вещественных решения, то задача поиска расстояния была бы решена однозначно. Однако вещественность всех решений системы (3) вовсе не гарантирована (см. пункт 2.6), так что после нахождения какого-то одного из этих решений мы не можем быть уверены, что отсутствует другое, более оптимальное. Это обстоятельство отмечается во всех исследованиях, посвященных разработке итерационного подхода: в некоторых случаях удается установить эмпирически (с помощью вспомогательных оценок) сходимость метода к истинному решению, обеспечивающему минимум целевой функции. Тем не менее, универсальных рекомендаций, подходящих для любой задачи, нет.

В связи с отмеченными выше недостатками итерационных методов, в последние 20 лет стал активно развиваться альтернативный подход, основанный на алгебраических методах исключения переменных в алгебраических системах. Возвращаясь к системе (3), такой подход позволяет свести систему из нескольких уравнений от нескольких переменных к одному уравнению от одной переменной. При этом гарантирована абсолютная достоверность полученного результата: это обеспечивается тем, что аналитические алгоритмы используют только точную арифметику рациональных чисел; так что отсутствуют ошибки округления. Аналитические методы требуют достаточного развития компьютерных мощностей (они более ресурсоемки, чем итерационные) и разработки вспомогательных пакетов символьных вычислений (так, на с. 83 будет показано, что даже в случае, когда уравнения исходных поверхностей имеют коэффициенты в пределах трех десятичных знаков, "окончательное" уравнение имеет коэффициенты из чуть менее 200 цифр; и эту ситуацию следует считать нормой!). Тем не менее, уровень развития современных персональных компьютеров, а также таких прикладных пакетов как МАРЬЕ, МАТНЕМАТ1СА, МАСБУМА, МиРАБ и других позволяет решать подобные задачи за вполне обозримое время. Так что постепенно аналитический подход становится все более и более конкурентноспособным по сравнению с численным; это обстоятельство заметно из сравнения количеств публикаций, посвященных каждому из этих подходов.

Имеется еще одно существенное преимущество аналитического подхода: итерационные методы практически бесполезны при решении задач с параметрами. К таким задачам относятся, например, динамические задачи компьютерной графики, связанные с моделированием движения одного трехмерного объекта относительно другого. Кроме того, в задаче аппроксимации множества точек в Мп с помощью алгебраического многообразия возникает задача параметрического синтеза: когда требуется подобрать коэффициенты поверхности так, чтобы удоблетворить некоторым требованиям оптимальности приближения.

Следует отметить еще одно важное обстоятельство, усложняющее решение задачи. Выше излагаемые рассуждения, основанные на применении метода множителей Лагранжа, приведут к истинному решению только при одном дополнительном условии: поверхности (1) и (2) не должны пересекаться, т.е. система алгебраических уравнений

ХтАгХ + 2В\X -1 = 0, ХТА2Х + 2В\Х -1 = 0 (4) не должна иметь вещественных решений. При размерности пространства п большей двух, система (4) является недоопределенной и поиск ее вещественных решений (или, хотя бы, доказательство факта их существования или отсутствия) становится нетривиальной задачей.

В работах [36, 44, 45] эта задача исследовалась только для случая п = 3 и в следующем частном случае: требовалось установить условия возможности разделения поверхностей с помощью плоскости. Полученные условия являются достаточно конструктивными и сводятся к анализу знаков корней некоторого полинома от одной переменной. Вместе с тем, вовсе не исследовался случай, когда одна поверхность находится целиком внутри другой; кроме того, обобщение предлагаемого подхода на случай п > 3 не было предложено (и кажется проблематичным).

Принимая во внимание все сказанное выше, можно сделать вывод, что задача о взаимном расположении алгебраических многообразий в К71, а также вычислении расстояния между ними, является актуальной как в теоретическом, так и в практическом отношении. Сформулируем теперь задачи, решаемые в настоящем диссертационном исследовании.

Пусть в М" заданы два алгебраических многообразия. Первое из них является квадрикой

ХТА1Х + 2В\X -1 = 0 (как правило, эллипсоидом), а вторая — либо линейным многообразием с\х = /¿1,., С^Х = либо же квадрикой

ХтА2Х + 2В\Х -1 = 0.

Требуется

1) найти необходимые и достаточные условия пересечения этих многообразий и, в случае отсутствия пересечения,

2) найти расстояние между многообразиями;

3) найти координаты их ближайших точек;

4) произвести анализ алгоритмов на предмет зависимости уравнений от параметров.

Общая характеристика работы

Актуальность темы. Анализ взаимного расположения объектов в трехмерном пространстве — исключительно важная задача в астрономии, навигации, робототехнике, компьютерной графике. При моделировании движений объектов необходимо гарантировать их от столкновения, и, следовательно, получать актуальную информацию о величине расстояния между ними. Аналогичные проблемы в п-мерном пространстве возникают в задачах классификации (кластеризации) данных и математической статистики.

Задача вычисления расстояния между множествами в Мп, а также связанная с ней задача о наличии нетривиального пересечения этих множеств, решались в разных разделах математики. Традиционный подход к решению задач нелинейной оптимизации заключается в построении подходящей итерационной процедуры. Однако даже использование свойств выпуклости часто не гарантирует сходимости этой процедуры к глобальному минимуму функции расстояния между точками рассматриваемых множеств. В последние десятилетия в вычислительной геометрии и в теории полиномиальной оптимизации наметился подход альтернативный итерационному, основанный на методах алгебраической геометрии. Объектом его применения стали полиномиальные целевые функции и множества, границы которых описываются алгебраическими уравнениями. В рамках этого подхода были получены решения некоторых теоретических и практических задач геометрического моделирования в Ж2 и Ж3. В развитие этого подхода, в настоящей работе решаются задачи, связанные с поиском расстояний между некоторыми классами алгебраических поверхностей в Мп.

Целью диссертационной работы является разработка конструктивных алгоритмов нахождения расстояния между объектами в Еп, а также установления их взаимного расположения (пересечения, касания). В работе задача решается в следующих частных случаях

1) нахождение условий пересечения эллипсоида и линейного многообразия, и в случае их непересечения вычисление расстояния между этими поверхностями как корня алгебраического уравнения,

2) нахождение условий пересечения эллипсоида и квадрики, и в случае их непересечения вычисление расстояния между поверхностями как корня алгебраического уравнения,

3) нахождение ближайших точек рассмотренных поверхностей,

4) исследование влияния на функцию расстояния параметров, входящих в уравнения поверхностей и возможности моделирования поверхностей с заданными аппроксимирующими свойствами.

Методы исследований. Применением метода множителей Лагран-жа задача сводится к решению системы алгебраических уравнений. Для решения этой системы предлагается использовать не численные (итерационные) методы, а аналитические — технику многомерных результантов для исключения переменных в системах алгебраических уравнений. Именно этот альтернативный подход к решению классической задачи является принципиально новым.

Основные положения, выносимые на защиту:

1) критерий проверки пересечения алгебраических поверхностей в К": эллипсоида и линейного многообразия, эллипсоида и квадрики;

2) метод нахождения расстояний между указанными поверхностями;

3) нахождение расстояния от заданной точки до эллипса в М2, движущегося по уникурсальной траектории;

4) метод нахождения ближайших точек поверхностей во всех указанных задачах;

5) созданный на основе разработанных алгоритмов и оттестированный на примерах комплекс программ (с применением системы аналитических вычислений MAPLE), позволяющий для двух поверхностей выявить наличие пересечения, и в противном случае произвести расчет расстояния между ними и нахождение координат их ближайших точек.

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

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

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

Результаты исследований прошли апробацию на

• международном математическом конгрессе ICM'06 (Мадрид);

• международном конгрессе по индустриальной и прикладной математике 1С1АМ'07 (Цюрих);

• международной конференции "Компьютерная алгебра в научных вычислениях" CASC'07 (Бонн);

• научных конференциях "Процессы управления и устойчивость" факультета прикладной математики - процессов управления Санкт

Петербургского государственного университета (С.-Петербург, 2005 и 2006 гг.);

• семинарах кафедры математического моделирования энергетических систем факультета прикладной математики - процессов управления.

Публикации. По материалам диссертации опубликованы 7 работ, 3 из которых в изданиях, входящих в перечень ВАК рецензируемых научных журналов [22, 28, 47].

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы; она включает 113 листов машинописного текста, 9 рисунков, список цитируемой литературы состоит из 48 наименований.

ЗАКЛЮЧЕНИЕ

Подводя итог проделанной работе, перечислим результаты, выносимые на защиту:

1) критерий проверки пересечения алгебраических поверхностей в Мп: эллипсоида и линейного многообразия, эллипсоида и квадрики;

2) метод нахождения расстояний между указанными поверхностями;

3) нахождение расстояния от заданной точки до эллипса в М2, движущегося по уникурсальной траектории;

4) метод нахождения ближайших точек поверхностей во всех указанных задачах;

5) на основе разработанных алгоритмов создан и оттестирован на примерах комплекс программ (с применением системы аналитических вычислений МАРЬЕ), позволяющий для двух поверхностей выявить наличие пересечения, и в противном случае произвести расчет расстояния между ними и нахождение их ближайших точек.

1. Бохер, М. Введение в высшую алгебру / М. Бохер ; пер. А.Г. Курош. М. : ЛКИ, 2008. - 296 с.

2. Bpio, Ш. Аналитическая геометр1я / Ш. Bpio и Ж.К. Буке ; пер. В. Синцов. — СПб.-М. : Издаше книгопродавца-типографа М.О.Вольфа, 1868. 508 с.

3. Галеев, Э.М. Оптимизация: теория, примеры, задачи / Э.М. Галеев, В.М. Тихомиров. М. : Эдиториал УРСС, 2000. - 320 с.

4. Гантмахер, Ф.Р. Теория матриц / Ф.Р. Гантмахер. — М. : Физмат-лит, 2004. 560 с.

5. Гельфанд, И.М. Лекции по линейной алгебре / И.М. Гельфанд. — М. : МЦНМО, 2007. 320 с.

6. Гурса, Э. Курсъ математическаго анализа: в 3 т. Т. 1. Производныя и дифференциалы. Определнные интегралы. Разложение в ряды. Геометрическия приложения. / Э. Гурса ; пер. А.И. Некрасов. — М. : Издание торгового дома "В.И.Знаменский и К°", 1911. — 630 с.

7. Зиновьев, А.Ю. Визуализация многомерных данных / А.Ю. Зиновьев. — Красноярск : Изд. КГТУ, 2000. 168 с.

8. Калинина, Е.А. Теория исключения: учебное пособие / Е.А. Калинина, А.Ю. Утешев. СПб. : НИИ Химии СПбГУ, 2002. - 72 с.

9. Куржанский, A.B. Задачи динамики и управления в гибридных системах / A.B. Куржанский, П. Варайя // Теория управления и теория обобщенных решений уравнений Гамильтона-Якоби : тр. международ. сем. / Екатеринбург , 2005. С. 74-81.

10. Лаврентьев, M. Основы вариационного исчисления: в 2 т. Т. 1. 4.II. Функции многих переменных / М. Лаврентьев, Л. Люстерник. — город : ОНТИ НКТП, 1935. 400 с.

11. Лагутин, М.Б. Наглядная математическая статистика / М.Б. Лагутин. — М. : БИНОМ. Лаборатория знаний, 2007. — 472 с.

12. Огородова, Л.В. Высшая геодезия: в 3 ч. Ч. 3. Теоретическая геодезия: учебник для вузов / Л.В. Огородова. — М. : Геодезкартиздат, 2006. 381 с.

13. Проскуряков, И.В. Сборник задач по линейной алгебре / И.В. Проскуряков. — М. : Наука, 1974. — 384 с.

14. Рашевский, П.К. Курс дифференциальной геометрии / П.К. Ра-шевский. — М. : Эдиториал УРСС, 2003. — 428 с.

15. Розенфельд, Б.А. Аполлоний Пергский / Б.А. Розенфельд. — М. : МЦНМО, 2004. 176 с.

16. Садовничий, В.А. Задачи студенческих математических олимпиад / В.А. Садовничий, A.A. Григорьян, C.B. Конягин. — М. : МГУ, 1987. — 310 с.

17. Смирнов, В.И. Курс высшей математики: в 5 т. Т. 2. / В.И. Смирнов. — СПб. : BHV-Санкт-Петербург, 2008. — 848 с.

18. Смирнов, В.И. Курс высшей математики: в 5 т. Т. 5. / В.И. Смирнов. — М. : Наука, 1959. — 657 с.

19. Утешев, А.Ю. К задаче полиномиальной оптимизации / А.Ю. Уте-шев, Т.М. Черкасов // Доклады РАН. — 1998. Т. 361. - №2. — С. 168-170.

20. Утешев, А.Ю. Нахождение расстояния от эллипсоида до плоскости и квадрики вГ / А.Ю. Утешев, М.В. Яшина // Доклады Академии наук. 2008. - Т. 419. - №4. - С. 471-474.

21. Фаддеев, Д.К. Вычислительные методы линейной алгебры / Д.К. Фаддеев, В.Н. Фадеева. — СПб. : Лань, 2002. — 736 с.

22. Фаддеев, Д.К. Лекции по алгебре / Д.К. Фаддеев. — СПб. : Лань, 2004. — 416 с.

23. Хорн, Р. Матричный анализ / Р. Хорн, Ч. Джонсон ; пер. Х.Д. Икрамов. — М. : Мир, 1989. — 656 с.

24. Чезаро, Э. Элементарный учебник алгебраического анализа и исчисления бесконечно малых /Э. Чезаро ; пер. К.А. Поссе. — Одесса : Ма!;!^, 1913. — 632 с.

25. Шилов, Г.Е. Математический анализ (функции нескольких вещественных переменных): в 3 ч. Ч. 1-2. / Г.Е. Шилов. — М. : Наука, 1972. — 624 с.

26. Яшина, М.В. О метрической проблеме для поверхностей второго порядка вГ / М.В. Яшина // Вестник СПбГУ. Серия 10 (прикладная математика). — 2008. — Вып. 3. — С. 53—57.

27. Algebraic Geometry and Geometric Modeling : сб. ст. / под ред. L. González-Vega. AGGM'06, Barcelona, 2006. - 139 P.

28. Bikker, P. On the Bézout construction of the resultant / P. Bikker, A.Yu. Uteshev // J. Symb. Comput. 1999. - V. 28. - M. P. 4588.

29. Bischoff, S. Ellipsoid decomposition of 3D-models / S. Bischoff, L. Kobbelt // Proceedings on First International Symposium on 3D Data Processing Visualization and Transmission. — 2002. — P. 480—488.

30. Chen, X-D. Computing minimum distance between two implicit algebraic surfaces / X-D. Chen, J-H. Yong, G-Q. Zheng, J-C. Paul, J-G. Sun // Computer-Aided Design. 2006. - V. 38. - P. 10531061.

31. Encyklopádie der Mathematischen Wissenschaften mit Einschluss ihrer Anwendungen. Bd. I. Arithmetik und Algebra / под ред. W.F. Meyer. — Leipzig : Teubner, 1898-1904.

32. Fitzgibbon, A. Direct least square fitting of ellipses / A. Fitzgibbon, M. Pilu, R.B. Fisher // IEEE transactions on pattern analysis and machine intelligence. — 1999. — V. 21. — №5. P. 476-480.

33. Kurzhanskiy, A.B. On ellipsoidal techniques for reachability analysis. Parts I,II / A.B. Kurzhanskiy, P. Varaiya // Optimization Methods and Software. 2002. - V. 17. - P. 187-237

34. Kurzhanskiy, A.A. Ellipsoidal toolbox (ET) / A.A. Kurzhanskiy, P. Varaiya // 45th IEEE Conference on Decision and Control / 13—15 Dec. 2006. P. 1498-1503.

35. Lin, A. A class of methods for projection on the intersection of several ellipsoids / A. Lin, S-P. Han // SIAM J.Optim. 2004. - V. 15. -№. - P. 129-138.

36. Lin, A. On the distance between two ellipsoids / A. Lin, S-P. Han // SIOPT. 2002. - V. 13. - Issue 1. - P. 298-308.

37. Olivik, S. / Position of reflecting points in bistatic satellite altimetry: theretical solutions for ellipsoid / S. Olivik, M. Kocandrlova, J. Kostelecky, J. Klokocnik // European Geosciences Union. Vienna, 2006. / 02-07 April 2006. P. 153.

38. Preparata, F.P. Computational geometry / F.P. Preparata, M.I. Shamos NY : Springer, 1985. - 398 P.

39. Schneider, P.J. Geometric tools for computer graphics /P.J. Schneider, D.H. Eberly — San Francisco : Elsevier, 2003. — 1009 P.

40. Wang, W. An algebraic condition for the separation of two ellipsoids / W. Wang, J. Wang, M-S. Kim // Computer Aided Geometric Design. 2001. - V. 18. - P. 531-539.

41. Wang, W. Efficient collision detection for moving ellipsoids using separating planes / W. Wang, Y-K. Choi, B. Chan, M-S. Kim, J. Wang // Computing. 2004. - V. 72. - P. 235-246.

42. Uteshev, A.Yu. Distance computation from an ellipsoid to a linear or quadric surface in Mn / A.Yu. Uteshev, M.V. Yashina // International

43. Congress of Mathematicians. Madrid, 2006 : abstracts / European Mathematical Society, 2006. — P. 504.

44. Yashina, M. Distance evaluation between quadric surfaces in Rn / M. Yashina, A. Uteshev // 6th International Congress on Industrial and Applied Mathematics. Zurich, 2007 : abstracts / 16—20 July 2007. — P. 444.