Наилучшая параметризация в задачах приближения кривых и поверхностей Якимович Анна Юрьевна
Актуальность темы. Задачи приближения играют исключительно важную роль в современной вычислительной математике, так как идеи приближения лежат в основе многих численных методов (см., например, [3, 5, 6, 56, 59, 70]).
Параметрическое приближение обладает рядом преимуществ по сравнению с традиционным. Параметрические функции позволяют дать простое математическое описание пространственных кривых, кривых и поверхностей, имеющих вертикальные касательные, в том числе замкнутых. Кроме того, параметрический способ задания кривых и поверхностей освобождает от привязки к какой либо определенной системе координат, позволяя наиболее просто осуществлять аффинные преобразования, такие как перенос и вращение. Благодаря данным преимуществам методы параметрического приближения получили широкое применение в компьютерной графике, при программировании станков с числовым управлением и других практических задачах, требующих построения кривых и поверхностей геометрически сложной формы. Достоинства параметрического приближения более подробно обсуждаются в работах [2, 14, 19, 67, 68, 106, 115].
Главной особенностью задач параметрического приближения кривых и поверхностей, как отмечается в [19], является то, что кривые и поверхности бывают заданы совокупностью точек, лежащих на них, а информация о способах параметризации отсутствует.
В задачах приближения кривых необходимо выбрать некоторый параметр и каждой заданной точке поставить в соответствие значение этого параметра. Во многих работах, например [2, 20, 58, 67, 100, 104, 105, 114, 115, 116, 124, 127, 139], при исследовании различных методов параметрического приближения кривых отмечается, что выбор параметра имеет критическое влияние на форму интерполирующей или аппроксимирующей кривой. При неудачном выборе параметра на кривой появляются осцилляции, а в некоторых случаях даже петли. Однако проблема выбора наилучшего параметра в данных работах не рассматривалась.
Для реализации параметрического приближения поверхности необходимо выбрать два параметра, задающих криволинейные координаты на поверхности таким образом, чтобы поверхность отображалась на прямоугольник в плоскости выбранной криволинейной системы координат. Как отмечается в работах [2, 20, 67, 104, 116, 124], выбор таких параметров имеет значительное влияние на форму приближающей поверхности. При неудачном выборе параметров на поверхности появляются нежелательные плоские и складчатые области. Проблема выбора наилучших параметров в задаче приближения поверхностей ни в одной работе не рассматривалась.
Цель и задачи работы. Целью данной работы является развитие общего подхода использования наилучшей параметризации в задачах приближения.
В связи с поставленной целью были решены следующие задачи
Сформулировать и доказать необходимые и достаточные условия наилучшей параметризации в задаче интерполяции поверхностей.
Сформулировать и доказать необходимые и достаточные условия наилучшей параметризации в задачах интерполяции и среднеквадратичной аппроксимации пространственных кривых.
Провести обзор и сравнительный анализ методов параметрического приближения кривых и поверхностей и способов параметризации кривых и поверхностей в задачах параметрического приближения.
Разработать алгоритмы и программы, реализующие параметрическое приближение кривых и поверхностей различными методами и с использованием различных способов параметризации. Сравнить результаты численных экспериментов с теоретическими утверждениями.
Методы исследования. В работе используются методы теории приближений, линейной алгебры, математического анализа, вычислительной геометрии.
Для построения кривых и поверхностей использовались методы интерполяции сплайнами, полиномиальной интерполяции и среднеквадратичной аппроксимации.
Доказательство необходимых и достаточных условий наилучшей параметризации основано на методе продолжения решения по параметру, с выбором наилучшего параметра, развитом в работах Шалашилина В.И. и Кузнецова Е.Б. [16, 28-34, 71, 138]. Данный метод применим для построения однопараметрических множеств, таких как решение нелинейных алгебраических и трансцендентных уравнений, задач Коши для ОДУ, краевых задач для ОДУ, дифференциально-алгебраических, функционально-дифференциальных, интегральных уравнений и т.п. При этом наилучшим параметром является длина дуги, вычисляемая вдоль кривой множества решений задачи. В работе [35] идея наилучшей параметризации обобщается на многомерный случай. В работах [32, 71, 138] рассмотрены необходимые и достаточные условия наилучшей параметризации в задачах интерполяции и среднеквадратичной аппроксимации плоских кривых.
Научная новизна работы заключается в следующем:
Сформулированы и доказаны необходимые и достаточные условия наилучшей параметризации в задаче интерполяции поверхностей. Проведены численные эксперименты, подтверждающие доказанные утверждения.
Сформулированы и доказаны необходимые и достаточные условия наилучшей параметризации в задаче интерполяции и среднеквадратичной аппроксимации пространственных кривых. Проведены численные эксперименты, подтверждающие доказанные утверждения.
3. Установлена эффективность метода представления аппроксимирующих полиномов в виде линейной комбинации ортогональных полиномов в задаче среднеквадратичной аппроксимации параметрическими полиномами.
Достоверность научных утверждений и выводов подтверждена строгими математическими доказательствами и численными экспериментами.
Практическая значимость работы обеспечивается широким лрименением параметрического приближения во многих современных практических задачах, требующих построения кривых и поверхностей геометрически сложной формы, например таких, как обводы летательных аппаратов, корпусы судов, кузова автомобилей, лопасти турбин. Параметрическое приближение используется как на стадии проектирования, для визуализации кривых и поверхностей на экране дисплея ЭВМ и подготовки информации для автоматических чертежных устройств, так и на стадии производства, при программировании станков с числовым управлением.
Краткое содержание диссертации.
Диссертационная работа состоит из введения, двух глав и заключения.
Первая глава посвящена задачам параметрического приближения кривых. В параграфе 1.1 формулируются задачи параметрического приближения кривых. В параграфах 1.2 - 1.7 описываются методы интерполяции кривых. В параграфе 1.8 описываются наиболее распространенные способы параметризации кривых. В параграфе 1.9 рассматривается проблема наилучшей параметризации в задаче интерполяции кривых. Параграф 1.10 посвящен методам среднеквадратичной аппроксимации кривых. В параграфе 1.11 рассматривается проблема наилучшей параметризации в задаче среднеквадратичной аппроксимации кривых.
Вторая глава посвящена задачам параметрического приближения поверхностей. В параграфе 2.1 формулируются задачи параметрического приближения поверхностей и проблема параметризации поверхности. В параграфах 2.2 - 2.8 рассматриваются методы интерполяции поверхностей. В параграфе 2.9 рассматривается проблема наилучшей параметризации в задаче интерполяции поверхностей.
Публикации. По теме диссертации опубликованы работы [36-40, 118-119].
Апробация работы. Основные результаты диссертационной работы докладывались на XII Международной конференции "Вычислительная механика и современные прикладные программные системы", г. Владимир, 30 июня-5 июля 2003г.; в Крымской осенней математической школе, г. Севастополь, 15-30 сентября, 2004 г.; на Международной конференции "International Conference of Computational Methods in Sciences and Engineering 2004", Аттика, Греция, 19-23 ноября 2004 г.; на XI Международном симпозиуме "Динамические и технологические проблемы конструкций и сплошных сред", с. Ярополец, Моск. обл., 14-18 февраля, 2005 г.; на XIV Международной конференции "Вычислительная механика и современные прикладные программные системы", г. Алушта, Крым, 25-31 мая 2005 г.
Полиномиальная интерполяция
Пусть задано упорядоченное множество точек Р,, / = 0,«, в пространстве Е2 или R3 и каждой точке поставлено в соответствии значение параметра /. Задача полиномиальной интерполяции состоит в построении вектор-функции р(0 = 2 /, A,.eR3, /є[ґ0;/я], (1.2.1) удовлетворяющей условиям Р( ,) = А// = Р„ / = 0,/1. (1.2.2) Для каждого набора узловых точек (t,,Р,), і = 0,п, существует единственный интерполяционный полином (1.2.1).
Определитель матрицы системы (1.2.3) является определителем Вандермонда, который отличен от нуля для любых попарно различных значений tr Следовательно, векторы коэффициентов полинома Ау однозначно определены. См., например, [18, 70].
На практике система (1.2.3) не используется для вычисления коэффициентов интерполяционного полинома, поскольку она часто бывает плохо обусловленной. Существуют различные удобные явные формы записи интерполяционного полинома, которые и применяются при интерполяции.
Интерполяционный полином в форме Лагранжа имеет вид у=о (1.2.4) где \j - базисные полиномы, называемые лагранжевыми многочленами влияния МО=ГЇт-т- (L2-5) /=0, tj - tt
Достоинством этой формы записи интерполяционного полинома является то, что число арифметических операций, необходимых для построения полинома Лагранжа пропорционально пг и является наименьшим для всех форм записи. К достоинствам можно также отнести то, что формула (1.2.4) содержит в явном виде значения Р ? что бывает удобно при некоторых вычислениях, например, при построении формул численного интегрирования.
К недостаткам полинома Лагранжа можно отнести то, что при изменении числа узлов приходится все вычисления проводить заново. Интерполяционный полином в форме Ньютона имеет вид p(0=Po+( -Wo i]+( -0( -A)[W ] + "-+( - o)-"( -0[V. /J, гпр Tt t Л _ "і "о 7 f t 1 _ U» 2J "l/o J Г 1 _ \?У" піУОТ--Лп-\і _ 0 2 0 л " 0 разделенные разности.
Для полинома Ньютона, в отличие от полинома Лагранжа, добавление новых узлов интерполяции приводит лишь к добавлению новых слагаемых, без изменения остальных. Интерполяционный многочлен Ньютона удобен для построения формул численного дифференцирования. Кроме того, он удобен для проведения апостериорных оценок погрешности интерполяции.
Кривая Безье степени п на отрезке 0 ґ 1 определяется при помощи векторного уравнения p„(0=2d,B;(o, (1.2.6) .7=0 Здесь базисными полиномами B"(t) являются полиномы Бернштейна В"( = чҐ .4, 0-0 - (1.2.7) В случае, если отрезок изменения параметра произволен a t b, уравнение кривой Безье имеет вид t-a р.(0=2Хв; у=о ч «. (1.2.8) Коэффициенты dj в формулах (1.2.6) и (1.2.8) представляют собой координаты опорных точек кривой Безье. Коэффициенты dy могут быть найдены из условий (1.2.2).
Кривые Безье предназначены для интерактивного построения кривых на экране ЭВМ. Кривая Безье лежит внутри выпуклой оболочки, натянутой на ее опорные точки, начинается в первой и заканчивается в последней точке. Опорные точки определяют касательные векторы кривой в узловых точках. Меняя расположение опорных точек можно получить желаемую форму кривой. Теория кривых Безье изложена в работах [46, 47, 88-90, 108, 113].
На практике не рекомендуется использовать интерполяционные полиномы степени больше 5. Полиномы больших степеней имеют тенденцию к осцилляциям (см. напр. [3, 56, 116]), и их значения между узлами могут значительно отличаться от значений интерполируемой функции. Эту тенденцию хорошо иллюстрирует пример Рунге [131] интерполяции функции f