Моделирование многомерных объектов и методы полиномиальной оптимизации

• Автор: Яшина, Марина Витальевна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Санкт-Петербург
• Количество страниц: 113 с. : ил.

СОДЕРЖАНИЕ
Введение

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

исследований

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

Глава 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. Вычислительные эксперименты.
3.6. Приложение к задаче СР8навигации.
3.7. Расстояние между центральными квадриками
3.8. Некоторые свойства полинома Тг
Глава 4. Решение оптимизационных задач для
параметрически зависящих объектов
4.1. Огибающая и эквидистанта как дискриминантные
кривые.
4.2. Вычисление расстояния до семейства квадрик
Заключение
Литература


Однако отсутствие общего алгоритма нахождения расстояния от точки до эллипсоида в Rn приводит к тому, что при расчетах вместо точного расстояния используется его приближенная оценка (например, расстояние Махалонобиса). В идеологии решения общей задачи нахождения расстояния между гладкими поверхностями лежит вариационный принцип трансверсальности: кратчайшее расстояние между этими поверхностями достигается на их общей нормали (см. В случае поверхностей, заданных алгебраическими уравнениями, этот принцип дает возможность использовать метод множителей Лагранжа. УгА2У + 2В2ГУ — 1] = 0. X - У)Г(Х - У). Система (3) является нелинейной алгебраической относительно входящих в нее неизвестных: каждое из 8 ее уравнений является квадратным. Для решения подобных систем имеются два подхода: первый основан на применении приближенных мегодов решения систем нелинейных уравнений; все подобные методы представляют из себя модификации метода Ньютона. В этом русле велись исследования [, |. В подтверждении этого произведем качественную оценку потенциально возможной ситуации. В главе 3 будет показано, что система (3) имеет, как правило. Таким образом, имеется не более потенциально возможных результатов итерационных процедур для произвольных стартовых значений итерационного процесса. Если бы применение итерационного метода дало с необходимой точностью все вещественных решения, то задача поиска расстояния была бы решена однозначно. Однако вещественность всех решений системы (3) вовсе не гарантирована (см. Это обстоятельство отмечается во всех исследованиях, посвященных разработке итерационного подхода: в некоторых случаях удастся установить эмпирически (с помощью вспомогательных оценок) сходимость метода к истинному решению, обеспечивающему минимум целевой функции. Тем нс менее, универсальных рекомендаций, подходящих для любой задачи, нет. В связи с отмеченными выше недостатками итерационных методов, в последние лет стал активно развиваться альтернативный подход, основанный на алгебраических методах исключения переменных в алгебраических системах. Возвращаясь к системе (3), такой подход позволяет свести систему из нескольких уравнений от нескольких переменных к одному уравнению от одной переменной. При этом гарантирована абсолютная достоверность полученного результата: это обеспечивается тем, что аналитические алгоритмы используют только точную арифметику рациональных чисел; так что отсутствуют ошибки округления. Аналитические методы требуют достаточного развития компьютерных мощностей (они более ресурсоемки, чем итерационные) и разработки вспомогательных пакетов символьных вычислений (так, па с. Тем не менее, уровень развития современных персональных компьютеров, а также таких прикладных пакетов как МАРЬЕ, МАТНЕМАТ1СА, МАСБУМА, МиРЛО и других позволяет решать подобные задачи за вполне обозримое время. Так что постепенно аналитический подход становится все более и более конкурентноспособным по сравнению с численным; это обстоятельство заметно из сравнения количеств публикаций, посвященных каждому из этих подходов. Имеется еще одно существенное преимущество аналитического подхода: итерационные методы практически бесполезны при решении задач с параметрами. К таким задачам относятся, например, динамические задачи компьютерной графики, связанные с моделированием движения одного трехмерного объекта относительно другого. Кроме того, в задаче аппроксимации множества точек в Еп с помощью алгебраического многообразия возникает задача параметрического синтеза: когда требуется подобрать коэффициенты поверхности так, чтобы удоблетворить некоторым требованиям оптимальности приближения. Следует отметить еще одно важное обстоятельство, усложниющее решение задачи. Выше излагаемые рассуждения, основанные на применении метода множителей Лагранжа, приведут к истинному решению только при одном дополнительном условии: поверхности (I) и (2) не должны пересекаться, т. При размерности пространства п большей двух, система (4) является недоопределенной и поиск ее вещественных решений (или, хотя бы, доказательство факта их существования или отсутствия) становится нетривиальной задачей.