Содержание к диссертации
Введение
Глава 1. Использемые результаты высшей алгебры 15
Глава 2. Расстояние от эллипсоида до линейного многообразия 24
2.1. Условия пересечения 24
2.2. Нахождение расстояния 27
2.3. Нахождение ближайших точек поверхностей 36
2.4. Расстояние от точки до эллипсоида 39
2.5. Расстояние от (п — 1)-мерной плоскости до элипсоида 45
2.6. Некоторые свойства полинома T{z) 49
Глава 3. Расстояние от эллипсоида до квадрики 60
3.1. Условия пересечения 60
3.2. Нахождение расстояния 63
3.3. Нахождение ближайших точек поверхностей 73
3.4. Программная реализация алгоритмов 74
3.5. Вычислительные эксперименты 79
3.6. Приложение к задаче GPS-навигации 85
3.7. Расстояние между центральными квадриками 87
3.8. Некоторые свойства полинома T{z) 96
Глава 4. Решение оптимизационных задач для параметрически зависящих объектов 98
4.1. Огибающая и эквидистанта как дискриминантные кривые 98
4.2. Вычисление расстояния до семейства квадрик 102
Заключение 107
Литература 108
- Использемые результаты высшей алгебры
- Нахождение ближайших точек поверхностей
- Расстояние между центральными квадриками
- Вычисление расстояния до семейства квадрик
Введение к работе
Постановка задачи, ее значение, обзор предшествующих исследований
Алгебраическая геометрия pi геометрическое моделирование имеют дело с кривыми и поверхностями в Шп, заданными полиномиальными (алгебраическими) уравнениями. Алгебраическая геометрия исследует теоретические свойства алгебраических кривых и поверхностей; геометрическое моделирование использует полиномиальные, кусочно-полиномиальные и дробно-рациональные функции для построения компьютерных моделей механических компонент при конструировании промышленных объектов и производств [29].
Среди множества математических задач, возникающих в этом разделе вычислительной геометрии (computational geometry), одной из важнейших является
задача вычисления расстояния между алгебраическими многообразиями и, связанные с ней,
задача установления наличия пересечения этих многообразий — что соответствует, например, столкновению движущихся объектов (collision detection) и
задача приближения (аппроксимации) точечного множества в Жп — эта задача возникает естественным образом при использовании результатов измерений, подверженных воздействию случайных погрешностей.
Решение общей задачи вычисления расстояния между алгебраическими многообразиями, заданными в Rn системами уравнений вида
(хЛ
дг{Х) = О,... ,дк(Х) = 0 при X =
\ Хп J
при полиномиальных д\,... ,дк, достаточно просто в случае многообразий линейных. Так, к примеру, растояние от точки Л~п Є Ш.п до многообразия
СТХ = Н при С =
/
Сітп c2m
\
tt =
/'лЛ
^ cni
/ nx
\hm J
(предполагается, что m < n и что ранг матрицы С равен т; здесь и далее Т означает транспонирование; расстояние понимается в евклидовой метрике) определяется по формуле
( Ст С СТХ0 - Н
\ (стх0 -
d =
det(CT С)
т.е. фактически сводится к решению квадратного уравнения [26].
Формула для расстояния между двумя линейными многообразиями в Rn также известна в литературе. Пусть линейные многообразия в R" заданы параметрически
X = Х0 + AiXi + ... + ХкХк и Y = У0 + діУі + ... + fj.eYt
при {Лі,..., Afc, ці,..., fii} С Ж и при фиксированных столбцах
{Xq, Xi,..., Хк, Yq, Yi, ..., 1^} с Mn.
Составим из этих столбцов матрицы
Р = [ХЬ . . . , Хк, УІ, . , ^]nx(fc+^) и
-Р = [Хь..., Xk, Y\,..., Ye, Х0 - *o]nx(fc+m) Тогда расстояние вычисляется по формуле
В случае когда хотя бы одна из поверхностей задается нелинейными уравнениями, задача существенно усложняется и не была полностью решена даже в такой ее частной постановке, как нахождение расстояния от точки Х0 Є Кп до квадрики в Rn, заданной уравнением
ХТАХ + 2ВТХ -1 = 0
при фиксированных симметричной матрице А и столбце В єШп. Практическая же важность этой задачи обусловлена тем обстоятельством, что, например, в случае п = 3 эллипсоиды оказались наиболее простыми геометрическими объектами, подходящими для моделирования множеств и физических тел в молекулярной физике, геодезии, приборостроении, компьютерной графике (особенно в задачах компьютерного зрения (computer vision))[31]. В n-мерном пространстве эллипсоиды возникают естественным образом в задаче классификции (кластеризации) данных. При описании объекта набором из п признаков, каждая серия их измерений задает точку в параметрическом пространстве. При недостоверности результатов измерений, каждую из точек можно рассматривать как аппроксимацию объекта, самым простым приближением которого может считаться эллипсоид (который может быть интерпретирован как эллипсоид рассеяния из математической статистики) [7, 11]. Однако отсутствие общего алгоритма нахождения расстояния от точки до эллипсоида в Шп приводит к тому, что при расчетах вместо точного расстояния используется его приближенная оценка (например, расстояние Махалонобиса).
В идеологии решения общей задачи нахождения расстояния между гладкими поверхностями лежит вариационный принцип трансверсальности: кратчайшее расстояние между этими поверхностями достигается на их общей нормали (см. 54 книги [10]). В случае поверхностей, заданных алгебраическими уравнениями, этот принцип дает возможность использовать метод множителей Лаграпжа. Так, к примеру, для задачи вычисления расстояния между двумя квадриками в М3, заданными
алгебраическими уравнениями
ХТА1Х + 2В{X -1 = 0
(1)
ХТА2Х + 2В\Х -1 = 0,
(2)
функция Лагранжа будет иметь вид
F{X,Y,Xl,X2) = (Х-У)т(Х-У)-Лі(ХгАіХ + 2Б;гХ-1)-- А2(УТА2У + 22ТУ-1),
= 2 [(X - У) - Аі(АіХ + В,)] = О, = 2 [(У - X) - А2(А2Х + В2)] = О, = - [ХтАгХ + 2В\Х - 1] = 0, = - [УГА2У + 2В\У - 1] = 0.
а соответствующая система: ' dF
дХ dF_ dY dF дХг dF , дХ2
(3)
Требуется найти решения этой системы относительно векторов {X, У} С К3, обеспечивающих минимум целевой функции
{X - Y)T{X - У).
Система (3) является нелинейной алгебраической относительно входящих в нее неизвестных: каждое из 8 ее уравнений является квадратным. Для решения подобных систем имеются два подхода: первый основан на применении приближенных методов решения систем нелинейных уравнений; все подобные методы представляют из себя модификации метода Ньютона. В этом русле велись исследования [39, 40]. К достоинствам такого подхода следует отнести быструю сходимость итераций к экстремуму целевой функции, к недостаткам — традиционное для ньютоно-подобных методов отсутствие гарантии того, что найденный экстремум
обеспечивает глобальный минимум целевой функции. В подтверждении этого произведем качественную оценку потенциально возможной ситуации. В главе 3 будет показано, что система (3) имеет, как правило, 24 решения, в общем случае комплексных. Таким образом, имеется не более 24 потенциально возможных результатов итерационных процедур для произвольных стартовых значений итерационного процесса. Если бы применение итерационного метода дало с необходимой точностью все 24 вещественных решения, то задача поиска расстояния была бы решена однозначно. Однако вещественность всех решений системы (3) вовсе не гарантирована (см. пункт 2.6), так что после нахождения какого-то одного из этих решений мы не можем быть уверены, что отсутствует другое, более оптимальное. Это обстоятельство отмечается во всех исследованиях, посвященных разработке итерационного подхода: в некоторых случаях удается установить эмпирически (с помощью вспомогательных оценок) сходимость метода к истинному решению, обеспечивающему минимум целевой функции. Тем не менее, универсальных рекомендаций, подходящих для любой задачи, нет.
В связи с отмеченными выше недостатками итерационных методов, в последние 20 лет стал активно развиваться альтернативный подход, основанный на алгебраических методах исключения переменных в алгебраических системах. Возвращаясь к системе (3), такой подход позволяет свести систему из нескольких уравнений от нескольких переменных к одному уравнению от одной переменной. При этом гарантирована абсолютная достоверность полученного результата: это обеспечивается тем, что аналитические алгоритмы используют только точную арифметику рациональных чисел; так что отсутствуют ошибки округления. Аналитические методы требуют достаточного развития компьютерных мощностей (они более ресурсоемки, чем итерационные) и разработки вспомогательных пакетов символьных вычислений (так, на с. 83 будет показано, что даже в случае, когда уравнения исходных поверхностей имеют коэффи-
циенты в пределах трех десятичных знаков, "окончательное" уравнение имеет коэффициенты из чуть менее 200 цифр; и эту ситуацию следует считать нормой!). Тем не менее, уровень развития современных персональных компьютеров, а также таких прикладных пакетов как MAPLE, MATHEMATICA, MACSYMA, MuPAD и других позволяет решать подобные задачи за вполне обозримое время. Так что постепенно аналитический подход становится все более и более конкурентноспособным по сравнению с численным; это обстоятельство заметно из сравнения количеств публикаций, посвященных каждому из этих подходов.
Имеется еще одно существенное преимущество аналитического подхода: итерационные методы практически бесполезны при решении задач с параметрами. К таким задачам относятся, например, динамические задачи компьютерной графики, связанные с моделированием движения одного трехмерного объекта относительно другого. Кроме того, в задаче аппроксимации множества точек в Rn с помощью алгебраического многообразия возникает задача параметрического синтеза: когда требуется подобрать коэффициенты поверхности так, чтобы удоблетворить некоторым требованиям оптимальности приближения.
Следует отметить еще одно важное обстоятельство, усложняющее решение задачи. Выше излагаемые рассуждения, основанные на применении метода множителей Лагранжа, приведут к истинному решению только при одном дополнительном условии: поверхности (1) и (2) не должны пересекаться, т.е. система алгебраических уравнений
ХтАгХ + 2В\X -1 = 0, ХТА2Х + 2В\Х -1 = 0 (4)
не должна иметь вещественных решений. При размерности пространства п большей двух, система (4) является недоопределенной и поиск ее вещественных решений (или, хотя бы, доказательство факта их существования или отсутствия) становится нетривиальной задачей.
В работах [36, 44, 45] эта задача исследовалась только для случая п = 3 и в следующем частном случае: требовалось установить условия
возможности разделения поверхностей с помощью плоскости. Полученные условия являются достаточно конструктивными и сводятся к анализу знаков корней некоторого полинома от одной переменной. Вместе с тем, вовсе не исследовался случай, когда одна поверхность находится целиком внутри другой; кроме того, обобщение предлагаемого подхода на случай п > 3 не было предложено (и кажется проблематичным).
Принимая во внимание все сказанное выше, можно сделать вывод, что задача о взаимном расположении алгебраических многообразий в Жп, а также вычислении расстояния между ними, является актуальной как в теоретическом, так и в практическом отношении. Сформулируем теперь задачи, решаемые в настоящем диссертационном исследовании.
Пусть в Шп заданы два алгебраических многообразия. Первое из них является квадрикой
ХТА1Х + 2Bf X -1 = 0 (как правило, эллипсоидом), а вторая — либо линейным многообразием
Сг X = h\,..., Ск X = hk, либо же квадрикой
ХТА2Х + 2В%Х -1 = 0. Требуется
найти необходимые и достаточные условия пересечения этих многообразий и, в случае отсутствия пересечения,
найти расстояние между многообразиями;
найти координаты их ближайших точек;
произвести анализ алгоритмов на предмет зависимости уравнений от параметров.
Общая характеристика работы
Актуальность темы. Анализ взаимного расположения объектов в трехмерном пространстве — исключительно важная задача в астрономии, навигации, робототехнике, компьютерной графике. При моделировании движений объектов необходимо гарантировать их от столкновения, и, следовательно, получать актуальную информацию о величине расстояния между ними. Аналогичные проблемы в n-мерном пространстве возникают в задачах классификации (кластеризации) данных и математической статистики.
Задача вычисления расстояния между множествами в Шп, а также связанная с ней задача о наличии нетривиального пересечения этих множеств, решались в разных разделах математики. Традиционный подход к решению задач нелинейной оптимизации заключается в построении подходящей итерационной процедуры. Однако даже использование свойств выпуклости часто не гарантирует сходимости этой процедуры к глобальному минимуму функции расстояния между точками рассматриваемых множеств. В последние десятилетия в вычислительной геометрии и в теории полиномиальной оптимизации наметился подход альтернативный итерационному, основанный на методах алгебраической геометрии. Объектом его применения стали полиномиальные целевые функции и множества, границы которых описываются алгебраическими уравнениями. В рамках этого подхода были получены решения некоторых теоретических и практических задач геометрического моделирования в Ж2 и Ж3. В развитие этого подхода, в настоящей работе решаются задачи, связанные с поиском расстояний между некоторыми классами алгебраических поверхностей в Шп.
Целью диссертационной работы является разработка конструктивных алгоритмов нахождения расстояния между объектами в Rn, а также установления их взаимного расположения (пересечения, касания). В работе задача решается в следующих частных случаях
нахождение условий пересечения эллипсоида и линейного многообразия, и в случае их непересечения вычисление расстояния между этими поверхностями как корня алгебраического уравнения,
нахождение условий пересечения эллипсоида и квадрики, и в случае их непересечения вычисление расстояния между поверхностями как корня алгебраического уравнения,
нахождение ближайших точек рассмотренных поверхностей,
исследование влияния на функцию расстояния параметров, входящих в уравнения поверхностей и возможности моделирования поверхностей с заданными аппроксимирующими свойствами.
Методы исследований. Применением метода множителей Лагран-жа задача сводится к решению системы алгебраических уравнений. Для решения этой системы предлагается использовать не численные (итерационные) методы, а аналитические — технику многомерных результантов для исключения переменных в системах алгебраических уравнений. Именно этот альтернативный подход к решению классической задачи является принципиально новым.
Основные положения, выносимые на защиту:
критерий проверки пересечения алгебраических поверхностей в R": эллипсоида и линейного многообразия, эллипсоида и квадрики;
метод нахождения расстояний между указанными поверхностями;
нахождение расстояния от заданной точки до эллипса в Ш2, движущегося по уникурсальной траектории;
метод нахождения ближайших точек поверхностей во всех указанных задачах;
созданный на основе разработанных алгоритмов и оттестированный на примерах комплекс программ (с применением системы аналити-
ческих вычислений MAPLE), позволяющий для двух поверхностей выявить наличие пересечения, и в противном случае произвести расчет расстояния между ними и нахождение координат их ближайших точек.
Научная новизна работы и личный вклад автора. Все результаты, выносимые на защиту, являются новыми. Вычислительные алгоритмы и реализующие их программные комплексы разработаны лично автором.
Обоснованность и достоверность полученных результатов гарантируется строгостью математических доказательств, подтверждается сравнением полученных результатов с полученными в предшествующих исследованиях других авторов, а также проверяется вычислительными экспериментами.
Теоретическая и практическая ценнность. Абсолютная достоверность полученных качественных и количественных результатов позволяет использовать разработанные алгоритмы для моделирования тестовых примеров при расчете различных вычислительных схем. Результаты работы могут быть использованы для задач многомерного моделирования в молекулярной физике, химии, компьютерной графике, геодезии и приборостроении.
Результаты исследований прошли апробацию на
международном математическом конгрессе ICM'06 (Мадрид);
международном конгрессе по индустриальной и прикладной математике 1С1АМ'07 (Цюрих);
международной конференции "Компьютерная алгебра в научных вычислениях" CASC07 (Бонн);
научных конференциях "Процессы управления и устойчивость" факультета прикладной математики - процессов управления Санкт-
Петербургского государственного университета (С.-Петербург, 2005 и 2006 гг.);
семинарах кафедры математического моделирования энергетических систем факультета прикладной математики - процессов управления.
Публикации. По материалам диссертации опубликованы 7 работ, 3 из которых в изданиях, входящих в перечень ВАК рецензируемых научных журналов [22, 28, 47].
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы; она включает 113 листов машинописного текста, 9 рисунков, список цитируемой литературы состоит из 48 наименований.
Использемые результаты высшей алгебры
Анализ взаимного расположения объектов в трехмерном пространстве — исключительно важная задача в астрономии, навигации, робототехнике, компьютерной графике. При моделировании движений объектов необходимо гарантировать их от столкновения, и, следовательно, получать актуальную информацию о величине расстояния между ними. Аналогичные проблемы в n-мерном пространстве возникают в задачах классификации (кластеризации) данных и математической статистики.
Задача вычисления расстояния между множествами в Шп, а также связанная с ней задача о наличии нетривиального пересечения этих множеств, решались в разных разделах математики. Традиционный подход к решению задач нелинейной оптимизации заключается в построении подходящей итерационной процедуры. Однако даже использование свойств выпуклости часто не гарантирует сходимости этой процедуры к глобальному минимуму функции расстояния между точками рассматриваемых множеств. В последние десятилетия в вычислительной геометрии и в теории полиномиальной оптимизации наметился подход альтернативный итерационному, основанный на методах алгебраической геометрии. Объектом его применения стали полиномиальные целевые функции и множества, границы которых описываются алгебраическими уравнениями. В рамках этого подхода были получены решения некоторых теоретических и практических задач геометрического моделирования в Ж2 и Ж3. В развитие этого подхода, в настоящей работе решаются задачи, связанные с поиском расстояний между некоторыми классами алгебраических поверхностей в Шп.
Целью диссертационной работы является разработка конструктивных алгоритмов нахождения расстояния между объектами в Rn, а также установления их взаимного расположения (пересечения, касания). В работе задача решается в следующих частных случаях 1) нахождение условий пересечения эллипсоида и линейного многообразия, и в случае их непересечения вычисление расстояния между этими поверхностями как корня алгебраического уравнения, 2) нахождение условий пересечения эллипсоида и квадрики, и в случае их непересечения вычисление расстояния между поверхностями как корня алгебраического уравнения, 3) нахождение ближайших точек рассмотренных поверхностей, 4) исследование влияния на функцию расстояния параметров, входящих в уравнения поверхностей и возможности моделирования поверхностей с заданными аппроксимирующими свойствами. Методы исследований. Применением метода множителей Лагран-жа задача сводится к решению системы алгебраических уравнений. Для решения этой системы предлагается использовать не численные (итерационные) методы, а аналитические — технику многомерных результантов для исключения переменных в системах алгебраических уравнений. Именно этот альтернативный подход к решению классической задачи является принципиально новым. Основные положения, выносимые на защиту: 1) критерий проверки пересечения алгебраических поверхностей в R": эллипсоида и линейного многообразия, эллипсоида и квадрики; 2) метод нахождения расстояний между указанными поверхностями; 3) нахождение расстояния от заданной точки до эллипса в Ш2, движущегося по уникурсальной траектории; 4) метод нахождения ближайших точек поверхностей во всех указанных задачах; 5) созданный на основе разработанных алгоритмов и оттестированный на примерах комплекс программ (с применением системы аналити ческих вычислений MAPLE), позволяющий для двух поверхностей выявить наличие пересечения, и в противном случае произвести расчет расстояния между ними и нахождение координат их ближайших точек.
Научная новизна работы и личный вклад автора. Все результаты, выносимые на защиту, являются новыми. Вычислительные алгоритмы и реализующие их программные комплексы разработаны лично автором.
Обоснованность и достоверность полученных результатов гарантируется строгостью математических доказательств, подтверждается сравнением полученных результатов с полученными в предшествующих исследованиях других авторов, а также проверяется вычислительными экспериментами.
Теоретическая и практическая ценнность. Абсолютная достоверность полученных качественных и количественных результатов позволяет использовать разработанные алгоритмы для моделирования тестовых примеров при расчете различных вычислительных схем. Результаты работы могут быть использованы для задач многомерного моделирования в молекулярной физике, химии, компьютерной графике, геодезии и приборостроении.
Нахождение ближайших точек поверхностей
По найденному наименьшему положительному корню z полинома (2.9) (вычисленному точно или приближенно) восстановить точки X и Кк поверхностей, в которых достигается значение г квадрата расстояния.
Нахождение ближайших точек поверхностей ведется следующим образом. Единственное значение параметра fj, — ц , соответствующее z = z , можно отыскать с помощью следствия 1 к теореме 1.3: где Т№ — определитель, получающийся из дискриминанта, находящегося в правой части (2.9), представленного в виде (1.10), вычеркиванием первой и последней строк, первого и предпоследнего столбца, а М — первый субдискриминант для этого дискриминанта. Подставляя найденное значение /л в (2.18) восстанавливаем точки поверхностей, квадрат расстояния между которыми равен z .
Однако, в некоторых случаях (например, при z кратном) однозначное восстановление по z точек поверхностей X и У оказывается невозможным. Это связано с тем, что матрица М = СТ(/І А-1 — Е)С становится вырожденной. Тем не менее, в случае совместности системы (2.17), с помощью условий (2.1) и (2.15) удается выделить несколько пар точек.
После нахождения ближайших точек поверхностей правильность вычислений можно проверить двумя способами. Во-первых, найденные точки X и У должны удовлетворять уравнениям поверхностей (2.1) и (2.2), а также условию (X —Y )T(X —У ) = z . Во-вторых, согласно вариационным принципам, кратчайшее расстояние между двумя поверхностями достигается по их общей нормали (условие трансверсальности переходит в условие ортогональности, см. 54 книги [10]), следовательно, градиенты поверхности (2.1) в точке X и поверхности (2.2) в точке У должны быть коллинеарны. Проверка коллинеарности может быть осуществлена путем вычисления определителя матрицы Грама, составленной для градиентов поверхностей. В случае коллинеарности градиентов этот определитель равен нулю.
Проиллюстрируем на примере результаты этого и предыдущих разделов. Теперь определим ближайшие точки этих поверхностей. Согласно приведенному выше алгоритму, по найденному значению z± = 0.05712805 определяем значение
Рассмотрим частный случай решаемой задачи: поверхность (2.2) вырождается в точку, причем эта точка не лежит на поверхности (2.1).
Обозначим f(fj,) = det(A — /iE) — характеристический полином матрицы A, a q(A, fi) — присоединенную матрицу для характеристической матрицы А — fiE.
Присоединенная матрица определяется как матрица, удовлетворяющая матричному тождеству Её можно построить с помощью алгебраических дополнений элементов характеристической матрицы А — /лЕ.
Замечание. Если матрица А имеет большую размерность, то для одновременного вычисления Дд) и д(А, ц) можно воспользоваться методом Леверье — Фаддеева [23].
Л Замечание. В геодезии имеется понятие геодезической или эллипсоидальной высоты точки как расстояния от точки (космического) пространства до эллипсоида, представляющего собой приближение поверхности Земли. Подробнее см. [12]. Теперь проверим результат теоремы 2.3, рассмотрев частный случай задачи нахождения расстояния до эллипсоида от его центра.
Теорема 2.4 Величина квадрата расстояния от центрального эллипсоида ХТАХ = 1 до начала координат X = О совпадает с мипималь def ным положительным корнем полинома f (z) = znf(l/z).
Действительно, согласно формуле (1.16), от решения уравнения (2.29) можно перейти к решению эквивалентного уравнения f (z) = 0: T{z) = V,(f(y)(liz-l)-BTq(A )B) =2 (/(/0( -1)) = = V,(zf (/,)(/2 - 1/z)) = z2nV»(f(v)(v - 1/z)) = {1=6) ЭДМ) x (znf(l/z)f = P,(/(M)) x (r(z)f.
Таким образом, квадрат расстояния содержится среди корней уравнения f (z) = 0, т.е. среди величин l/Aj, где Xj — собственные числа матрицы А, что подтверждает известное в литературе экстремальное свойство собственных чисел симметричной матрицы [4].
Расстояние между центральными квадриками
Рассмотрим следующую задачу спутниковой альтиметрии (GPS-навигации). Имеется система искусственных спутников Земли, каждый из которых движется по известной траектории и служит источником и приемником радарных сигналов. Для определения местонахождения Р точки на поверхности Земли GPS-навигатор принимает сигнал, посылаемый спутником-излучателем Si, и передает (отражает) этот сигнал на спутник-приемник $2- Обычно для такой альтиметрии достаточно иметь один спутник-излучатель и два спутника-приемника. Однако иногда возникают ситуации, когда один из спутников-приемников "теряет" передаваемый сигнал — тогда задача навигации усложняется. Рассмотрим ее в следующей постановке. Известно, что поверхность Земли достаточно хорошо аппроксимируется эллипсоидом вращения (известным в геодезии как WGS-84) — обозначим его W\. Считаем, что спутники S\ и , движутся по геостационарным орбитам, и их размерами можно пренебречь: в системе координат, связанной с эллипсоидом W\ мы считаем их точками с известными (и постоянными во времени) координатами — бистатичная альтиметрия. Считаем также известной длину 5 сигнала — как сумму длин сигналов, получаемых и отражаемых GPS-приемником. Для решения задачи определения местоположения приемника Р построим поверхность W2, исходя из условия постоянства суммы расстояний до ее точек от заданных S\ и ,. Из аналитической геометрии известно, что эта поверхность является эллипсоидом вращения с фокусами в точках S\ и S?.. В идеальном случае искомая точка Р должна быть точкой касания эллипсоидов W\ и W i. Однако в реальности — ввиду погрешностей приближения поверхности Земли эллипсоидом — эти эллипсоиды не пересекаются, и в этом случае за точку Р берут точку, ближайшую на W\ к эллипсоиду И .
Следующий числовой пример взят из статьи [41], в последней поиск ближайших точек проводился итерационным методом с выбором в ка честве начального приближения точки пересечения прямой, проходящей через центры эллипсоидов с эллипсоидом W\.
Решение проводилось с предварительной конвертацией данных в рациональные дроби. Полином T{z) имеет степень 12, что в два раза меньше оценки из предыдущего пункта. По-видимому, это понижение вызвано особенностью задачи: оба эллипсоида являются эллипсоидами вращения, и их оси параллельны друг другу.
Расстояние оказывается равным 0.00077943; на эллипсоиде (3.39) ему соответствует точка Р с координатами Результат совпадает с полученным в [41].
Рассмотрим частный случай решаемой задачи — когда поверхности (3.1) и (3.2) вырождаются в центральные квадрики.
Условие пересечения центральных квадрик содержится в качестве упражнения 1241 в [13] и может быть получено как следствие теоремы 3.1 при Bi = О и В2 = О: квадрики в Rn, причем первая является эллипсоидом. Квадрики не пересекаются тогда и только тогда, когда матрица Ai — А2 является знакоопределенной.
Следствие 1 Эллипсоид (3.40) касается поверхности (3.41) тогда и только тогда, когда det(Ai — А2) = 0.
Следствием теоремы 3.2 является следующая теорема: в предположении, что этот корень не является кратным. Здесь V — дискриминант полинома рассматриваемого относительно переменной А.
Доказательство в этом частном случае не может быть получено как следствие общего случая (теоремы 3.2), так как при предельном переходе В\ — О, .В2 —» О мы сталкиваемся с исключительным случаем — вырожденностью матрицы (3.18).
Стартовой точкой доказательства является система уравнений (3.12)— (3.15), которая в нашем случае может быть представлена в виде при некоторой константе 7- В самом деле, легко установить, что любой собственный вектор матрицы М, соответствующий ненулевому собственному числу, будет собственным и для матрицы М: Если det М = 0, то характеристический полином матрицы М имеет нулевое собственное число, а соответствующий этому числу собственный вектор будет собственным и для матрицы М (соответствующим собственному числу Мц + М22 + ... + Мпп, где Mjj обозначает алгебриче-ское дополнение к j—му диагональному элементу матрицы М). Таким образом, для любого столбца Z ф О, удовлетворяющего (3.54), будет выполнено (3.58) при некоторой константе
Вычисление расстояния до семейства квадрик
В настоящей главе, посвященной применению полученных результатов для решения некоторых задач моделирования, мы будем исследовать од-нопараметрические семейства квадрик в Rn. Нас интересуют две задачи: возможность аналитического выражения огибающих этих семейств и нахождение расстояний до них от заданной точки. Подобные задачи возникают в небесной механике (нахождение расстояния до объекта, движущегося по известной траектории), в машиностроении (при проектировании деталей машин и механизмов), в трехмерной графике [33]. Кроме указанных областей приложений отметим ещё работы А.Б. Куржанского и его учеников [9, 37, 38], в которых исследуются области достижимости некоторых. гибридных линейных систем управления — когда (невыпуклое) множество достижимости аппроксимируется семейством эллипсоидов, и ставится задача об оценке диаметра этой области. Рассмотрим семейство плоских кривых {К(Л)}, зависящих от параметра Л, принимающего значения из интервала [а, Ь] Є Ш. Если существует некоторая кривая L, которая в каждой своей точке касается некоторой кривой рассматриваемого семейства, но при этом не совпадает ни с одной из них на протяжении какого-либо своего участка, то эта кривая L называется огибающей семейства кривых {К(Л)} [14]. Пусть кривые семейства {К(Л)} заданы уравнением где Ф(ж, у, А) — функция, непрерывно дифференцируемая по своим аргументам. Геометрическое место точек плоскости, удовлетворяющих уело Рассмотрим важный частный случай огибающей: эквидистанту. Возьмем гладкую кривую К на плоскости, в каждой ее точке М проведем перпендикуляр и возьмем на этом перпендикуляре точки, находящиеся на некотором фиксированном расстоянии h от точки М. Полученные точки формируют две кривые, каждую из которых назовем эквидистан-той кривой К. Легко показать, что эквидистанта является огибающей семейства окружностей радиуса h с центрами на кривой К. Если считать точки кривой источниками излучения равной мощности, распространяющегося в изотропной среде, заполняющей плоскость, то эквидистанта образует фронт волны. Это её свойство имеет практические применения в задачах физики.
Эта теорема является следствием теоремы 2.5, касающейся вычисления расстояния от точки до квадрики в Rn. Покажем ее применение на примере. Л Покажем на примере применение эквидистанты к вопросам моделирования — рассмотрим задачу аппроксимации множества точек эллипсом.
Если мощность множества достаточно велика, то вычислять расстояние от каждой его точки до аппроксимирующего эллипса будет довольно трудоемко. Можно пойти другим путем: строить семейство эквидистант эллипса в виде алгебраических кривых Фь(х:у) = 0. Фиксировать параметр эквидистанты — расстояние h от эллипса. Подставлять координаты точек в это уравнение и анализировать знак &h{x,y)- Качество аппроксимации оценивать количеством точек, попадающих в h—окрестность эллипса. Здесь J- (z,t) — полином (2.31), дискриминант Т вычисляется относительно переменной t, а указанный корень не является кратным. Доказательство. При каждом конкретном значении t расстояние от XQ ДО соответствующего эллипсоида семейства (4.1) определяется как корень по z уравнения
Здесь функция J-(z, t) задается формулой (2.31) и, на основании вида этой формулы и предположения о полиномиалыюсти зависимости коэффициентов семейства (4.1) от параметра, эта функция является полиномом по t. Уравнение можно трактовать как неявную функцию, определяющую корни полинома (по переменной z) в виде функций от параметра t. Известно (см. [27], с. 80-83), что корни полинома являются непрерывно дифференцируемыми функциями коэффициентов, т.е. для любого корня z = z (t) уравнения (4.2) будет существовать производная dz (t)/dt. По теореме о дифференцировании неявной функции, будем иметь (здесь после вычисления частных производных производится подстановка z = z (t)).
При t Є [а, Ь], минимум функции z (t) достигается либо на границах интервала, либо в стационарной точке t — t, в которой Но тогда из (4.3) следует, что в этой же точке должно быть выполнено Кроме того, в этой же точке должно сохраняться условие (4.2). Тогда необходимо, чтобы соответствующее значение z удовлетворяло системе уравнений Ввиду полиномиальности функции Т, исключение переменной t из си стемы (4.5) проводится с помощью дискриминанта.
