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

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

Якимович Анна Юрьевна

НАИЛУЧШАЯ ПАРАМЕТРИЗАЦИЯ В ЗАДАЧАХ ПРИБЛИЖЕНИЯ КРИВЫХ И ПОВЕРХНОСТЕЙ

Специальность 05.13.18 -"Математическое моделирование, численные методы и комплексы программ"

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

»-д.

Москва-2005

Работа выполнена на кафедре "Дифференциальные уравнения" факультета "Прикладная математика и физика" Московского авиационного института (государственного технического университета)

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

Кузнецов Евгений Борисович

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

Лопаницин Евгений Анатольевич;

заседании Диссертационного совета Д212.125.04 при Московском авиационном институте (государственном техническом университете) по адресу: 125993, Москва, Волоколамское ш., 4.

С диссертацией можно ознакомиться в библиотеке МАИ.

кандидат физико-математических наук, доцент Иванов Игорь Эдуардович

Ведущая организация: Институт механики МГУ

Защита диссертации состоится

2005 г. в

часов на

Автореферат разослан

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

диссертационного совета Д212.125.04, кандидат физико-математических наук

/

ще-ч 22(1/0 /3

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

Актуальность темы. Задачи приближения играют исключительно важную роль в современной вычислительной математике, так как идеи приближения лежат в основе многих численных методов.

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

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

Выбор параметризации оказывает большое влияние на форму

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

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

поверхности - нежелательные плоские и складчатые области. Актуальность

данной проблемы отмечают в своих работах Завьялов Ю.С., Квасов Б.И.,

Мирошниченко B.JL, Jleyc В.А., Скороспелое В.А., Faux I.D., Pratt M.J.,

Hoschek J., Lasser D., Nielson G.M., Foley Th.A., Hartley P.J., Judd C.J., Mastin

C.W., Töpfer H.J., Ahlberg J.H., Nilson E.N., Walsh J.L. и др. при исследовании

различных методов параметрического приб! ИМЙИЙДЦИОНАЛЬНАЯ 1

1 БИБЛИОТЕКА [

i - - ------—' Ф

В работах Шалашилина В.И., Кузнецова Е.Б. рассмотрены необходимые и достаточные условия наилучшей параметризации в задачах интерполяции и полиномиальной среднеквадратичной аппроксимации плоских кривых.

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

1. Сформулировать и доказать необходимые и достаточные условия наилучшей параметризации в задаче интерполяции поверхностей.

2. Сформулировать и доказать необходимые и достаточные условия наилучшей параметризации в задачах интерполяции пространственных кривых.

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

4. Провести обзор и сравнительный анализ методов параметрического приближения кривых и поверхностей и способов параметризации кривых и поверхностей в задачах параметрического приближения.

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

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

Для приближения кривых и поверхностей использовались методы интерполяции сплайнами, полиномиальной интерполяции и среднеквадратичной аппроксимации.

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

Научная новизна работы состоит в следующем:

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

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

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

Достоверность научных утверждений и выводов подтверждена строгими математическими доказательствами и численными экспериментами.

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

Публикации. По результатам диссертации опубликовано 7 печатных работ, из них 3 статьи в российских и зарубежных реферируемых журналах, 1 статья в сборнике трудов и 3 публикации в тезисах докладов международных конференций.

Апробация работы. Основные результаты диссертационной работы докладывались

1. на XII Международной конференции "Вычислительная механика и современные прикладные программные системы", г. Владимир, 2003г.;

2. в Крымской осенней математической школе, г. Севастополь, 2004 г.;

3. на "International Conference of Computational Methods in Sciences and Engineering 2004", Греция, 2004 г.;

4. на XI Международном симпозиуме "Динамические и технологические проблемы конструкций и сплошных сред", с. Ярополец, Моск. обл., 2005 г.;

5. на XTV Международной конференции "Вычислительная механика и современные прикладные программные системы", г. Алушта, 2005г.;

6. на семинаре кафедры "Дифференциальные уравнения" Московского авиационного института, Москва, 2005 г.;

7. на семинаре Института механики МГУ, Москва, 2005 г.

Структура и объем работы. Диссертация состоит из введения, двух глав и заключения. Общий объем диссертации составляет 110 страниц, включая 38 рисунков. Библиография содержит 140 наименований.

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

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

Первая глава посвящена параметрическому приближению кривых.

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

В параграфах 1.2-1.7 описываются различные методы параметрической интерполяции кривых: полиномиальная интерполяция, интерполяция сплайнами, составными кривыми Ферпосона, метод В-сплайнов. Проводится обзор литературы. Приводятся примеры, сравнивающие результаты параметрической интерполяции с выбором наилучшего параметра и обычной интерполяции. При параметрической интерполяции с выбором наилучшего параметра погрешности получаются в несколько раз меньше.

В параграфе 1.8 описываются некоторые способы параметризации кривых. Наиболее распространенными из них являются равномерная, естественная, хордовая, и центростремительная параметризация. При равномерной параметризации отрезок изменения параметра \а,Ь\ делится на равные части. Значения параметра в заданных узловых точках Р( =(xl,yl,z,)T, i = 0,п, принимаются равными tf = (b-a)i/n+a, i = 0,n. Частный случай равномерной параметризации - целочисленная параметризация, при которой в

качестве значений параметра в узловых точках принимаются номера узловых точек г = 0,п. Естественная параметризация - параметризация, при

которой в качестве узловых значений параметра г,, / = 0,«, выбирается длина дуги приближаемой кривой, отсчитываемая от начальной до /-той точки. Хордовая параметризация - параметризация, при которой в качестве параметра выбирается длина ломаной, соединяющей узловые точки. Тогда в узловых точках параметр принимает значения

'о = °- + ' = 0,и-1, (1)

где <4 =у1(хм ~х,)2+(ум-у,)1 + (г,+1 -г,)2, / = 0,и-1. (2)

Центростремительная параметризация - параметризация, при которой значения параметра в узловых точках вычисляются по формуле (1), при этом в качестве приращений параметра принимаются величины

д/,=((х,+1-х,)2+0(3)

В параграфе 1.9 изучается проблема наилучшей параметризации в задаче интерполяции пространственных кривых. Задача интерполяции состоит в построении функций Х(1), У(/), 2(0, которые для выбранных значений параметра принимает заданные узловые значения у„ 2,, т.е. удовлетворяют условиям

х,=Х(0, ' = (4)

Если параметрические уравнения

х = Х(г), У = Г(0, 2 = (5)

кривой, проходящей через заданные точки (х^у^гУ, 1 = 0,п, уже построены, то задача вычисления межузловых значений х,у,г в общем случае сводится к решению системы нелинейных уравнений

*-Х(Г) = 0, у-т = 0, г-г(1) = 0. (6)

Предположим, что из уравнений (6) удается исключить переменную /. Для того, чтобы это было возможно сделать, достаточно, чтобы хотя бы одна из функций Х{г), У (г), 7(7) удовлетворяла теореме об обратной функции. В результате задача вычисления межузловых значений х, у, г сведется к решению системы нелинейных уравнений

= Ф(х,у,г)=0. (7)

В силу интерполяционных условий (4) и + 1 решений (х^у^г,) этой системы известны.

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

Введем некоторый параметр таким образом, чтобы в окрестности каждой точки (х,у,г)т кривой множества решений системы (7) параметр отсчитывался вдоль оси, направление которой определяется вектором а = (а1,а2,а3)т. Тогда дифференциал параметра можно представить в виде

Л = а^х+а2с1у + . (8)

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

«,2 + + «з = 1. (9)

Задавая различные наборы значений а,, а2, аг, мы можем описать все возможные параметры и выбрать среди них в некотором смысле наилучший.

Решения х, у, г системы (7) будем искать как функции параметра Г. Разделив равенство (8) на и продифференцировав уравнения (7) по г, получим систему дифференциальных уравнений продолжения решения системы (7) по параметру

/ а1 а2 \ а3 Г !\ Х1 т

К Р' У К у, = = 0

ф' V * ф' У {<)

где Р'х=дР1Ьх, Р^ = дР/ду, Р; = дР18г, Ф'х = дФ/8х, Ф'у = дФ/ду, Ф', = дФ/дг, х\ = (к/Л, у\ = <Ь>/А, 2\ = (к/Ж.

При заданных начальных условиях решением задачи Коши для этой системы будут искомые параметрические функции (5). В качестве начальных условий можно, например, выбрать Х(0) = х0, У(0) = у0, 7(0) = г0.

Систему (10) можно рассматривать как систему линейных алгебраических уравнений относительно производных х'„ у'„ 2\.

Для интегрирования системы (10) необходимо привести ее к нормальному виду, т.е. разрешить ее относительно производных х\, у', г'г Процесс разрешения системы (10) относительно производных будет тем эффективнее, чем лучше обусловлена матрица этой системы. В качестве меры обусловленности |£>) примем абсолютную величину определителя матрицы, деленную на произведение квадратичных норм ее строк. В силу неравенства Адамара для определителей |£>|е [0,1]. Большему значению |0| соответствует лучшая обусловленность.

Мера обусловленности системы (10) может быть представлена в виде

где А - определитель матрицы системы (10), с/ = + + Е2 + Ф'/ + Ф'2 - произведение квадратичных норм строк

матрицы системы (10) с учетом равенства (9).

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

Исследовав на экстремум величину £> = как функцию от а1, а2, аг при условии (9), получим, что модуль этой функции |£)| достигает максимума, когда от,, а2, аъ определяются выражениями

а1 = х;, аг = у',, а3 = г\. (12)

Подставляя выражения (12) в равенство (8) и умножая полученное равенство на Л, получим

(сИ)г = (<йс)2 + Ыу)г + Ыг?. (13)

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

Теорема 1. Для того, чтобы в задаче параметрической интерполяции кривой (5), (4) выбрать наилучший параметр, необходимо и достаточно в качестве такого параметра принять длину дуги Л, вычисляемую вдоль интерполируемой кривой.

Если кривая задана дискретно, для построения интерполяционных функций, необходимо задать узловые значения параметра Л,, /=0,и, а длину дуги кривой, в свою очередь, нельзя вычислить, не задав функций Х(Л), У (Л),

9

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

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

¥(х,у) = (х1+у2У-(х1~у2) = 0, (14)

параметрическими кубическими сплайнами. Интерполяция проводилась по семи узловым точкам, обозначенным на Рис. 1 и Рис. 3, последняя точка совпадает с первой.

Оценки близости множеств точек полученных параметрических кривых к множеству точек исходной кривой, заданной уравнением (14), рассчитывались в метрике Хаусдорфа. Под хаусдорфовым расстоянием между двумя точечными ограниченными множествами Е и F понимается величина

г{Е,Р) = тах^тахппп р(Р,0),тахтт (15)

где /р(Р,<2) - евклидово расстояние между точками Р и р.

Рис.1

На Рис. 1 сплошной линией изображены графики полученных интерполяционных параметрических сплайнов, пунктирной линией изображен график функции (14). При использовании естественной параметризации (Рис. 1л) ошибка приближения составила г = 0.0354, при использовании хордовой параметризации (1), (2) (Рис. 1.6) - г = 0.0358, при использовании целочисленной параметризации (*,=/, / = 0,и) (Рис. 1.в) - г = 0.1516, при использовании центростремительной параметризации (1), (3) (Рис. 1.г) -г = 0.1084. Т.е. при использовании наилучшей параметризации (Рис. 1.а), ошибка интерполяции более чем в два раза меньше ошибки интерполяции с использованием центростремительной параметризации (Рис. 1.г) и более чем в четыре раза меньше ошибки интерполяции с использованием целочисленной параметризации (Рис. 1 .в). При использовании хордовой параметризации (Рис. 1.6) получаются результаты близкие к наилучшим.

Рассмотрим, теперь, случай, когда в одной из узловых точек значение параметра отлично от наилучшего, при этом значения параметра в остальных узлах являются наилучшими -Х^.

На Рис. 2 изображен график зависимости ошибки интерполяции, вычисленной по формуле (15), от значения параметра ^ в точке №5. Длина дуги заданной кривой, от точки №0 до точки №5 равна А, =3.19. Из графика видно, что ошибка интерполяции достигает минимума г = 0.0354, когда =Л5. На Рис. З.а показаны результаты интерполяции при /5 = 3, а на Рис. З.б - при Ц = Соответствующие ошибки интерполяции обозначены точками на графике Рис. 2. Видно, что при отклонении параметра от наилучшего интерполяционная картина значительно ухудшается (см. Рис. 1 .а, Рис. 3).

Ряс. 2

Рис. 3

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

На Рис. 4.а изображены результаты интерполяции при использовании естественной параметризации, на Рис. 4.6 - при использовании хордовой параметризации, на Рис. 4.в - при использовании целочисленной параметризации, на Рис. 4.г - при использовании центростремительной параметризации.

Рис.4

Из Рис. 4 видно, что наилучшие результаты получаются при использовании естественной параметризации (Рис. 4.а). При использовании хордовой параметризации (Рис. 4.6) получаются результаты близкие к наилучшим.

Параграф 1.10 посвящен методам среднеквадратичной аппроксимации кривых.

Пусть задано упорядоченное множество точек Р, =(дс(,^,г<)г, / = 0,и, и каждой точке поставлено в соответствие значение параметра Задача среднеквадратичной аппроксимации состоит в построении обобщенных полиномов степени т<п,

= о, ^> = 1^(0, (16)

к=0 *=0 *=0

минимизирующих среднеквадратичное отклонение

* = Я1 = (х1-ХМ)1 + (у,-Гя(0)2 + (*,-2М)г. (17)

(=0

Здесь {<%(/)}, к-0,т - некоторая выбранная система базисных функций. Наиболее часто применяется аппроксимация полиномами, т.е. в качестве базисных функций выбираются степенные функции % = 1, =

<рг(/) = ... ,0>я(/) = 1т. Однако при таком выборе базисных функций с увеличением степени т приближающих полиномов линейная алгебраическая система для определения коэффициентов полинома становится плохо обусловленной. Плохая обусловленность приводит к большой потери точности в ходе вычислений: появление даже самых малых ошибок в правых частях и коэффициентах системы приводит к появлению больших ошибок в решении системы. Кроме того, полиномы больших степеней имеют тенденцию к осцилляциям, причем для параметрических полиномов эта тенденция более выражена, чем для обычных. Поэтому на практике при реализации среднеквадратичной аппроксимации обычно используют полиномы небольших степеней. Однако, при параметрической аппроксимации полиномов маленьких степеней часто бывает недостаточно для описания кривой сложной формы.

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

Для сравнения двух методов построения аппроксимирующих полиномов рассматривается несколько примеров. Приведем пример параметрической аппроксимации строфоиды по 17 узловым точкам.

В первом методе в качестве базисных функций выбираются степенные функции <рк(() = **. Результаты решения задачи данным методом обозначены на Рис. 5-7 пунктирной линией. Во втором методе в качестве базисных функций выбираются ортогональные полиномы, = О» к = 0,т. Результаты

решения задачи этим методом обозначены на Рис. 5-7 сплошной линией. В обоих случаях в качестве параметра использовалась длина ломаной, соединяющей узловые точки (1), (2). соединяющей узловые точки (1), (2).

На Рис. 5

ои+ \ изображена

зависимость

ом, среднеквадратичного

отклонения

од»

0Л4

0Л2 ■

от

в 7

т

Рис.5

ю

т=б

т=11

степени приближающих многочленов т. На Рис. 6 и Рис. 7 показаны результаты аппроксимации

полиномами б и 11 степени соответственно.

Из Рис. 6 видно, что

полиномов шестой степени недостаточно для описания кривой. А при т > 6 на результатах вычислений

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

Рис.6

Рис.7

на Рис. 5, среднеквадратичное отклонение полиномов, построенных традиционным методом больше, чем среднеквадратичное отклонение полиномов той же степени, построенных методом ортогональных полиномов. Кроме того, как видно из Рис. 7 у полиномов больших степеней, построенных вторым методом в значительно меньшей степени проявляется склонность к осцилляциям, чем у полиномов, построенных первым методом.

В параграфе 1.11 рассматривается проблема наилучшей параметризации в задаче среднеквадратичной аппроксимации пространственной кривой параметрическими обобщенными полиномами (16).

Наилучшим параметром назовем параметр, доставляющий выражению (17) наименьшее значение.

Значения t¡ будем подсчитывать по формуле (1). Приращение параметра А/, примем в виде

Аг, = аиАх1 + а2,Ау, + а}1 Аг(, (18)

где Ддс, =х1+1-х„ Ау1=у1+1-у„ Дг, = г,+1 - ¿г,, а аи, а21, а3, - пока не определенные константы, которые по смыслу представления (18) можно рассматривать как компоненты векторов а1, указывающих в каждой точке Р, направление изменения параметра t. Для того, чтобы все направления были равноправными, будем определять их единичными векторами, поэтому должны иметь место равенства

аи+а1,+а1 = 1, 1=0,л-1. (19)

Задача выбора параметра Г и построения аппроксимирующих полиномов (16), сводится к исследованию на экстремум функции (17) при условии (19).

Минимум соответствующей функции Лагранжа доставляют выражения

А*,- ДУ/ _

^(Ах,)2 +(4у/У +(Аг/)2' ^'^Ах^НАу^ЧАг/' ^ ^(Ах^ЦАу^Н^/

Подставив эти выражения в (18), получим значения приращений параметра I в виде (2).

Таким образом, наилучший параметр среднеквадратичной параметрической аппроксимации определяется формулами (1), (2), т.е. является длиной ломаной, соединяющей заданные узловые точки.

Теорема 2. Для того чтобы аппроксимирующие функции (16), наилучшим образом приближали заданные узловые точки Р,, ¿ = 0,и, необходимо и достаточно в качестве параметра выбрать длину ломаной, соединяющей эти точки.

Наилучший параметр обозначим, как и ранее, через Л.

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

х — 2соэ$, у = 2%\пв, 2 = 0. (20)

Аппроксимация проводилась по двадцати двум неравноотстоящим узловым точкам обобщенными параметрическими многочленами десятой степени. В качестве базисных функций использовались ортогональные полиномы. Расстояния между аппроксимирующими кривыми и кривой, задаваемой функциями (20), рассчитывались в метрике Хаусдорфа (15).

На Рис. 8 изображены полученные аппроксимирующие кривые и заданные узловые точки. При использовании хордовой параметризации (Рис. 8.а) хаусдорфово расстояние составило г = 0.23, при использовании целочисленной параметризации (Рис. 8.6) - г = 1.18, при использовании центростремительной параметризации (Рис. 8.в) - г = 0.75. Т.е. при использовании наилучшей параметризации погрешность аппроксимации более чем в три раза меньше погрешности аппроксимации с использованием центростремительной параметризации и более чем в пять раз меньше погрешности аппроксимации с использованием целочисленной параметризации.

») б) в)

Рис. 8

Рассмотрим случай, когда в одной из узловых точек значение параметра отлично от наилучшего, при этом значения параметра в остальных узлах являются наилучшими г, = Л,. На Рис. 9 изображен график зависимости ошибки аппроксимации, вычисленной по формуле (15) от значения параметра г10 в

точке №10. Длина ломаной,

1

0.9 0.8 0.7 0.6 0.5 0.4 0.3

14

15

16

Рис.9

17

1»

соединяющей узловые точки 0-10равна Л,0 = 16.15.

Из графика на Рис. 9 видно, что ошибка аппроксимации достигает своего минимума г = 0.23, когда значение параметра совпадает с наилучшим, т.е. Г10 = Л,0. На Рис. 10.а показаны результаты

аппроксимации при ¿10 = 14, на Рис. 10.6 - при /10=18. Соответствующие ошибки обозначены точками на графике на Рис. 9.

«) 6) Рис. 10

Видно, что результаты аппроксимации, представленные на Рис. 10 существенно хуже результатов аппроксимации с использованием наилучшей параметризации (Рис. 8.а).

Вторая глава посвящена параметрическому приближению поверхности.

17

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

Параметрические уравнения поверхности имеют вид

г = г(к, у) = (Х(и, у), У (и, V), 2{и, у))т, где к и у - некоторые параметры,

а<и<,Ь, с<>\<>й.

Для реализации параметрического приближения поверхности необходимо построить на поверхности сетку из и+1 продольных и т +1 поперечных параметрических линий. Эта сетка делит поверхность на п т топологически прямоугольных ячеек. Каждая ячейка ограничена четырьмя гладкими кривыми. Вдоль линий сетки параметры принимают постоянные значения. Вдоль продольных линий - и = и,, 1 = 0,п, вдоль поперечных линий - V = V,, у = 0,т. Линии сетки, г = г(и,,у), /=0,и, и г = г(и,у;), / = 0,ти, могут быть построены

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

В параграфах 2.2 - 2.8 рассматриваются методы параметрической интерполяции поверхностей: интерполяция двумерными полиномами, двумерными сплайнами, методы Кунса, Ферпосона, В-сплайнов.

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

Если параметрические уравнения *

х = Х(и,у), у = г = 7(«,у), (21)

поверхности, удовлетворяющие интерполяционным условиям

хц=Х(и,^), уц =Г(м,,у;), ги=г(и„г;), г = оЯу = оЯ (22)

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

у) = 0, >> —У(и,у) = 0, = 0, (23)

Исключив из уравнений (23) переменные и и у получим нелинейное уравнение

Р(х,у,г) = 0, (24)

Причем в силу условий (22) (и + 1)(т + 1) решений (хи,уц,г0) этого уравнения известны.

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

Введем некоторые параметры и и V, представляя их дифференциалы в

виде

<1и = а1(Ь+а^у + а3(к, ¿/у = +Р^у + . (25)

По смыслу представления (25) векторы а = (а1,аг,а3)т и р = (Д,/?2,Д)г задают в окрестности каждой точки поверхности направления осей, вдоль которых отсчитываются параметры и и V. Для того чтобы все направления были равноправны, они должны определяться векторами одинаковой длины. Пусть векторы аир будут единичными, тогда их компоненты должны удовлетворять равенствам

+а2+а3 =1> А2+Д2+/?=1. (26)

Записав равенства (25) и выражение для дифференциала уравнения (24), получим систему уравнений продолжения

/ от, а2 \ аъ 'л? 'Ли

А Рг Рг ¿у = = А>

Г \ * К К

где Р^ = д¥/дх, Гу = ^!ду, Г^дТ/дг.

Для того, чтобы осуществить процесс продолжения, необходимо разрешить эту систему относительно дифференциалов с1х, (¡у, йг. Процесс разрешения системы (27) относительно дифференциалов будет тем эффективнее, чем лучше обусловлена матрица этой системы.

Мера обусловленности системы (27) задается формулой

d'

где, A - определитель матрицы системы (27) d = ^jf.+ Ff + F!2 -

произведение квадратичных норм ее строк.

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

Исследуя на экстремум величину D = A/d как функцию компонентов векторов аир при условиях (26) приходим к выводу, что максимум мере обусловленности |£>| доставляют выражения

A-V / = 1,2,3, (29)

Л Л

где Ah - алгебраическое дополнение, соответствующее элементу аг,, Аъ -алгебраическое дополнение, соответствующее элементу Д, i = 1,2,3, матрицы системы (27).

Можно показать, что векторы а и р, компоненты которых удовлетворяют равенствам (29) лежат в плоскости касательной к поверхности и взаимно ортогональны. Кроме того при v = const дифференциал параметра и удовлетворяет равенству для дифференциала длины дуги, а при и = const дифференциал параметра v удовлетворяет равенству для дифференциала длины дуги.

Таким образом в параграфе 2.9 доказана следующая теорема.

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

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

x*-y2+2?-l = О, параметрическими бикубическими сплайнами.

Ошибки интерполяции вычислялись в метрике Хаусдорфа (15).

При использовании естественной параметризации линий сетки (Рис. 11.а) ошибка приближения составила г = 0.08, при использовании хордовой

параметризации (Рис. 11.6) - г = 0.11, при использовании целочисленной параметризации (Рис. 11.в) - г = 0.22, при использовании центростремительной параметризации (Рис. 11.г) - г = 0.19.

В) г)

Рис. 11

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

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

21

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

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

1. Кузнецов Е.Б., Якимович А.Ю. Аппроксимация неявно заданных функций параметрическими многочленами // Тезисы докладов XII международной конференции по вычислительной механике и современным прикладным программным системам. - М.:Изд-во МГУ, 2003, Т.2, с.396-397.

2. Кузнецов Е.Б., Якимович А.Ю. Моделирование кривых параметрическими многочленами по методу наименьших квадратов // Матем. моделирование, 2004, Т. 16, № 6, с.48-51.

3. Kuznetsov Е. В., Yakimovich A.Yu. The best parameterization for parametric splines interpolation // Lecture series on computer and computational science, 2004, V.l,p.l201-1204.

4. Кузнецов Е.Б., Якимович А.Ю. Наилучшая параметризация в задачах интерполяции параметрическими сплайнами кривых и поверхностей // Материалы XI международного симпозиума "Динамические и технологические проблемы конструкций и сплошных сред". - М.:Изд-во МАИ, 2005, Т. 1, с.78-79.

5. Кузнецов Е.Б., Якимович А.Ю. Наилучшая параметризация поверхностей // Материалы XII международной конференции по вычислительной механике и современным прикладным программным системам. - М.: Вузовская книга, 2005, с.263.

6. Кузнецов Е.Б., Якимович А.Ю. Наилучшая параметризация в задачах приближения кривых и поверхностей // Ж. вычисл. математ. и математич. физики, 2005, Т.45, № 5, с.760-774.

7. Kuznetsov Е.В., Yakimovich A.Yu. The best parameterization for parametric # interpolation // Journal of computational and applied mathematics, 2006 (в

печати, доступна на сайте http://www.sciencedirect.com/science/joumal/03770427).

e-mail: anna_ya@msn.com - Якииович Анна Юрьевка

22

к исполнению 01/10/2005 Исполнено 02/11/2005

Заказ № 1177 Тираж: 80 экз.

ООО «11-й ФОРМАТ» ИНН 7726330900 Москва, Варшавское ш., 36 (095) 975-78-56 (095) 747-64-70 www.autoreferat.ni

2 15 70

РНБ Русский фонд

2006-4 22002

ВВЕДЕНИЕ.

Глава 1. ПАРАМЕТРИЧЕСКОЕ ПРИБЛИЖЕНИЕ КРИВЫХ

1.1. Постановка задач параметрического приближения кривых

1.2. Полиномиальная интерполяция.

1.3. Сплайн-приближение.

1.4. Параметрические сплайны.

1.5. Интерполяционные кубические параметрические сплайны.

1.6. Составные кривые Фергюсона.

1.7. Параметрические В-сплайны.

1.8. Способы параметризации кривой.

1.9. Наилучшая параметризация в задаче интерполяции кривой

1.10. Среднеквадратичная аппроксимация.

1.11. Наилучшая параметризация в задаче среднеквадратичной аппроксимации кривой.

Глава 2. ПАРАМЕТРИЧЕСКОЕ ПРИБЛИЖЕНИЕ ПОВЕРХНОСТЕЙ

2.1. Параметризация поверхности.

2.2. Классификация методов параметрического приближения поверхностей

2.3. Интерполяция двумерными полиномами.

2.4. Поверхности Кунса.

2.5. Поверхности Фергюсона.

2.6. Параметрические двумерные сплайны.

2.7. Бикубические параметрические интерполяционные сплайны

2.8. В-сплайновые поверхности.

2.9. Наилучшая параметризация в задаче интерполяции поверхности

Актуальность темы. Задачи приближения играют исключительно важную роль в современной вычислительной математике, так как идеи приближения лежат в основе многих численных методов (см., например, [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], выбор таких параметров имеет значительное влияние на форму приближающей поверхности. При неудачном выборе параметров на поверхности появляются нежелательные плоские и складчатые области. Проблема выбора наилучших параметров в задаче приближения поверхностей ни в одной работе не рассматривалась.

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

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

1. Сформулировать и доказать необходимые и достаточные условия наилучшей параметризации в задаче интерполяции поверхностей.

2. Сформулировать и доказать необходимые и достаточные условия наилучшей параметризации в задачах интерполяции и среднеквадратичной аппроксимации пространственных кривых.

3. Провести обзор и сравнительный анализ методов параметрического приближения кривых и поверхностей и способов параметризации кривых и поверхностей в задачах параметрического приближения.

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

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

Для построения кривых и поверхностей использовались методы интерполяции сплайнами, полиномиальной интерполяции и среднеквадратичной аппроксимации.

Доказательство необходимых и достаточных условий наилучшей параметризации основано на методе продолжения решения по параметру, с выбором наилучшего параметра, развитом в работах Шалашилина В.И. и Кузнецова Е.Б. [16, 28-34, 71, 138]. Данный метод применим для построения однопараметрических множеств, таких как решение нелинейных алгебраических и трансцендентных уравнений, задач Коши для ОДУ, краевых задач для ОДУ, дифференциально-алгебраических, функционально-дифференциальных, интегральных уравнений и т.п. При этом наилучшим параметром является длина дуги, вычисляемая вдоль кривой множества решений задачи. В работе [35] идея наилучшей параметризации обобщается на многомерный случай. В работах [32, 71, 138] рассмотрены необходимые и достаточные условия наилучшей параметризации в задачах интерполяции и среднеквадратичной аппроксимации плоских кривых.

Научная новизна работы заключается в следующем:

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

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

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

Достоверность научных утверждений и выводов подтверждена строгими математическими доказательствами и численными экспериментами.

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

Краткое содержание диссертации.

Диссертационная работа состоит из введения, двух глав и заключения.

ЗАКЛЮЧЕНИЕ

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

1. Айвазов С.Р., Айрапетян Р.Т., Барсуков В.Е., Белкин В.К., Вермель В.Д. Геометрические задачи для двумерных параметрических кубических сплайнов // Труды ЦАГИ, 1995, вып. 2581.

2. Алберг Дж., Нилъсон Э., УолшДж. Теория сплайнов и ее приложения. — М.: Мир, 1972.

3. Амосов A.A., Дубинский Ю.А., Копченова Н.В. Вычислительные методы для инженеров.-М.: Высш. шк., 1994.

4. Ашкеназы В.О. Сплайн-поверхности. Тверь, 1993.

5. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. — М.: Лаборатория Базовых Знаний, 2001.

6. Бахвалов Н.С. Численные методы. М.: Наука, 1973.

7. Бердышев В.И., Субботин Ю.Н. Численные методы приближения функций. — Свердловск: Среднеуральское кн. изд-во, 1979.

8. Брудный Ю.А., Гопетауз И.Е. Приближение кусочно-полиномиальными функциями // Известия АН СССР. Сер. матем., 1963, Т.27, №4, с.723-746.

9. Василенко В.А. Сплайн-функции: теория, алгоритмы, программы. — Новосибирск: Наука, 1983.

10. Вержбицкий В.М. Основы численных методов. -М.: Высш. шк., 2002.13 .Гардан К, Люка М. Машинная графика и автоматизация конструирования. Пер. с франц. М.:Мир, 1987.

11. Ы.Гилой В. Интерактивная машинная графика.—М:Мир, 1982.

12. Григолюк Э.И., Мамай В.И. Нелинейное деформирование тонкостенных конструкций. -М.:Наука. Физматлит, 1997.

13. Завьялов Ю.С., Квасов Б.И., Мирошниченко B.JI. Методы сплайн-функций. — М.: Наука, 1980.

14. Ю.Завьялов Ю.С., Jleyc В.А., Скороспелое В.А. Сплайны в инженерной геометрии —М.: Машиностроение, 1985.

15. Завьялов Ю.С. Интерполирование кубическими многозвенниками. // В сб.: Вычислительные системы. Новосибирск, АН СССР. Сиб. отд. Ин-т математики, 1970, вып.38, с.23-73.

16. Завьялов Ю.С .Интерполирование бикубическими многозвенниками. // В сб.: Вычислительные системы. Новосибирск, АН СССР. Сиб. отд. Ин-т математики, 1970, вып.38, с.74-101.

17. Завьялов Ю.С. Экстремальное свойство кубических многозвенников и задача сглаживания // В сб.: Вычислительные системы. Новосибирск, АН СССР. Сиб. отд. Ин-т математики, 1970, выл.42, с.89-108.

18. Завьялов Ю.С. Экстремальное свойство бикубических многозвенников и задача сглаживания // В сб.: Вычислительные системы. — Новосибирск, АН СССР. Сиб. отд. Ин-т математики, 1970, вып.42, с.109-158.

19. Игнатов М.И., Певный А.Б. Натуральные сплайны многих переменных. -Ленинград: Наука, 1991.

20. Колмогоров А.Н. О некоторых асимптотических характеристиках вполне ограниченных метрических пространств И Доклады АН СССР, 1956, Т.108,№3,с385-388.

21. П.Корнейчук Н.П., Лушпай Н.Е. Наилучшие квадратурные формулы для классов дифференцируемых функций и кусочно-полиномиальное приближение // Известия АН СССР. Сер. матем. 1969, Т.ЗЗ, №6, 14161437.

22. Кузнецов Е.Б. Метод продолжения решения по параметру решения дифференциальных уравнений. М.: Изд-во МАИ, 1997.

23. Кузнецов Е.Б. Наилучшая параметризация при построении кривых // Ж. вычисл. математ. и математич. физики, 2004, Т.44, №9, с.1540-1551.

24. Кузнецов Е.Б., Шалашилин В.И. Параметрическое приближение // Ж. вычисл. математ. и математич. физики, 1994, Т.34, №12, с. 1757-1769.

25. ЪЪ.Кузнецов Е.Б., Шалашилин В.И. Наилучший параметр продолжения решения // ДАН, 1994, Т.334, №5, с. 566-568.

26. Кузнецов Е.Б., Шалашилин В.И. Наилучший параметр параметрического интерполирования // УМН, 1996, Т.51, вып.2(308), с. 167-168.

27. ЪЪ.Кузнецов Е.Б., Шалашилин В. И. О наилучшей многомерной параметризации//Дифференц. уравнения, 2000, Т.З, №6, с. 841-843.

28. ЪП.Кузнецов Е.Б., Якимович А.Ю. Моделирование кривых параметрическими многочленами по методу наименьших квадратов // Матем. моделирование, 2004, Т. 16, № 6, с.48-51.

29. Кузнецов Е.Б., Якимович А.Ю. Наилучшая параметризация поверхностей // Материалы XII международной конференции по вычислительной механике и современным прикладным программным системам. М.: Вузовская книга, 2005, с.263.

30. Кузнецов Е.Б., Якимович А.Ю. Наилучшая параметризация в задачах приближения кривых и поверхностей // Ж. вычисл. математ. и математич. физики, 2005, Т.45, № 5, с.760-774.41 .КурошА.Г. Курс высшей алгебры. М.: Физматлит, 1963.

31. Мамай В.И., Ананченко Т.Н., Кудрина Т.Д., Корнейчук Л.Г. К построению геометрических характеристик поверхности в задачах теории оболочек. Отчет института механики МГУ №3540, 1987.

32. Мамай В.И., Кудрина Т.Д. Об использовании сплайнов в задачах динамики тонкостенных конструкций. Отчет института механики МГУ №2865,1983.

33. Мамай В.И., Кудрина Т.Д. Об одном двухступенчатом методе приближения дифференцируемых функций // В сб.: Задачи механики твердого деформируемого тела. / Под ред. Нетребко. М.:МГУ, 1985, с. 100-107.

34. Мамай В.И., Кудрина Т.Д., Ананченко Т.Н., Корнейчук Л.Г., Кулаков A.A. Сплайн-функции в задачах теории приближений оболочек неканонической формы. Препринт № 7-94. - М.: Изд-во НИИ Механики Моск. ун-та, 1994.

35. Математика и САПР. В 2-х кн. Кн 1. Пер. с франц. / Шенен П, Коснар М, Гардан И. и др. -М.:Мир, 1988.

36. Назаренко H.A. О приближении плоских кривых параметрическими эрмитовыми сплайнами // Укр. мат. журнал, 1979, Т.31, №2, с.201-205.

37. Носач В.В. Решение задач аппроксимации с помощью персональных компьютеров. М.: МИКАП, 1994.

38. Ортега Дж.М., Пул У.Дж. Введение в численные методы для решения дифференциальных уравнений. М.: Наука, 1986.

39. Павлов H.H., Скороспелое В.А. Моделирование кривых и поверхностей в системе автоматизации геометрических расчетов // Сплайн-функции в инженерной геометрии. Вычислительные системы. Ин-т математ. СО АН СССР. 1989, вып.86, с.44-59.

40. Переверзев C.B. Точные значения приближения эрмитовыми сплайнами на одном классе функций двух переменных // Укр. мат. журнал, 1979, Т.31, №5 с. 510-516.

41. Пирумов A.A. Численные методы. М.:Вагриус, 2004.

42. Попов В.А., Сеидов Б.Х. О классах, характеризуемых наилучшим приближенем сплайн-функциями // Матем. заметки, 1970, Т.8, №2, 137148.

43. Роджерс Д, Адаме Дж. Математические основы машинной графики. -М.: Мир, 2001.

44. Самарский A.A., Гулин A.B. Численные методы. М.: Наука, 1989.

45. СеберДж. Линейный регрессионный анализ. -М.: Мир, 1980.61 .Сендов Б. Хаусдорфовы приближения. София: Болгарская АН, 1979.

46. Снигирев В.Ф. Вычисление параметров срединной поверхности оболочки методами сплайн-функций // Актуальные проблемы механики оболочек. Казанский авиац. ин-т. 1985, с. 113-121.

47. Стечкин С.Б., Субботин Ю.Н. Сплайны в вычислительной математике. -М.гНаука, 1976.

48. Субботин Ю.Н Об одном линейном методе приближения дифференцируемых функций // Математ. заметки, 1970, Т.7, №4, с.423-430.

49. Субботин Ю.Н., Черных Н.И. Порядок наилучших сплайн-приближений некоторых классов функций // Математ. заметки, 1970, Т.7, №1, с.31-42.

50. Треногин В.А. Теорема Люстерника и наилучшая параметризация // Функц. анализ и его приложения, 1998, Т.32, №1. с.87-90.

51. Фокс А., Пратт М. Вычислительная геометрия. -М.: Мир, 1982. б&.Фоли Дж, вэн Дэм А. Основы интерактивной машинной графики. В 2-хкн. Кн.2. М.: Мир, 1985.

52. Форсайт Дж, Малькольм М., Моулер К. Машинные методы математических вычислений. -М.: Мир, 1980.

53. Хемминг Р.В. Численные методы. М.: Наука 1972. 1\.Шалашилин В.И., Кузнецов Е.Б. Метод продолжения решения попараметру и наилучшая параметризация в прикладной математике и механике. М.: Эдиториал УРРС, 1999.

54. Advances in CAD/CAM. / In T.M.R. EUis, O.I. Semencov ed. Amsterdam / New York / Oxford: North-Holland Publishing Company, 1983.

55. Advances in computer-aided manufacture. / In McPher D. son ed. -Amsterdam / New York / Oxford: North-Holland Publishing Company, 1977.

56. AhlbergJ.H., Nilson E.N., Walsh J.L. Convergence properties of generalized splines // Proc. Nat. Acad. Sci. USA. 1965, V.54, №2, p.344-350.

57. Atteia M.M. "Spline-Fonctions" généralisées // Comptes Rendys de l'Académie des Sciences. Paris. 1965, V.261, №11,2149-2152.

58. Barnhill R.E. Coons' Patches // Computers in Industry, 1983, V.3, p. 37-43.

59. S3.Barnhill R.E. Computer aided surface representation and design. // in Barnhill R.E., Boehm W. ed.: Surfaces in Computer Aided Geometric Design. -Amsterdam, North-Holland, 1983, p. 1-24.

60. Barsky B.A. End conditions and boundary conditions for uniform B-spline curve and surface representations // Computers in Industry, 1982, V.3, 17-29.

61. Barsky B. A. Computer graphics and geometric modeling using Beta-splines. Springer Verlag, 1988.

62. S6.Bartels R.H., Beatty J.C., Barsky B.A. An introduction to spline for use in computer graphics and geometric modeling. Morgan Kaufmann Publishers, 1987.

63. ButteifieldK.R. Ph. D. Thesis. Brunei University Uxbridge. Middlesex. 1978.

64. Bezier P. Example of an existing system in the motor industry: The UNISURF System // Proc. Roy. Soc. Lond, 1971, A 321, p.207-218.

65. Bezier P. Numerical control: mathematics and applications. London, Wiley, 1972.

66. Bezier P. The mathematical basis of the UNISURF CAD system. London, Butterworth, 1986.9 l.Birkhoff G. Local spline approximation by moments I I J. Math and Mech., 1967, V.16, №9, p.987-990.

67. Birkhoff G., De Boor C. Error bounds for spline interpolation // J. Math and Mech. 1964, V.13, №5, p.827-835.

68. Butzer P.L., Schmidt M, Stark E.L Observations on the history of central B-splines // Archive for history of exact science. 1988, V.39, p. 137-156.

69. Computer language for numerical control. / In Barhnhill R.E. and Riesenfeld R.F. ed. Amsterdam: North-Holland Publishing Company, 1973.

70. Coons S.A. Surfaces for computer aided design. MIT, Mechan. Engin. Department, Design Division, 1964.

71. Coons S.A. Surfaces for computer aided design of space forms. MIT, Project MAC, Report MAC-TR-41, 1967.

72. Cox M.G. The numerical evaluation of B-spline I I Nat. Phys. Lab. England: Teddingston, 1971.

73. Curry H.B., Schoenberg I.J. On Polya frequency functions IV: The fundamental spline functions and their limits // J. Analyse Math. 1966, V.17, p.71-107.

74. De Boor C. On calculating with B-splines // Journal of Approximation theory, 1972, №6 50-62.

75. Epstain M.P. On the influence of parametrization in parametric interpolation // SI AM Journal on Numerical Analysis, 1976, V.13, №2, 261-268.

76. Farin G. Curves and surfaces for computer aided geometric design. A practical guide, third adition. Cambridge, Massachusetts: Academic Press Inc., 1993.

77. Ferguson J.C. Multivariable Curve Interpolation. Report №D2-22504, The Boeing Co., Seattle, Washington, 1963.

78. Ferguson J.C. Multivariable Curve Interpolation // Journal ACM, 1964, V.ll,№2, p.221-228.

79. Foley Th.A. Weighted bicubic spline interpolation to rapidly varying data.// AC M Transactions on Graphics, 1987, V.6, p. 1-18.

80. Foley Th.A, Nielson G.M. Knot Selection for Parametric Spline Interpolation // in Lyche T., Schumaker L.L. ed.: Mathematical Methods in Computer Aided Geometric Design. Academic Press, 1989, p.261-272.

81. Forrest A.R. Curves and surfaces for computer-aided design, Ph. D. Thesis, University of Cambridge, 1968.

82. Forrest A.R. Mathematical Principles for curve and surface representation // Proc. Curved Surfaces Eng., IPC Science and Technology Press, London, 1972, p. 5-13.

83. Forrest A.R. Interactive interpolation and approximation by Bezier polynomials // Computer Journal, 1972, V.15, p.71-79.

84. Gordon W.J. Distributive lattices and the approximation of multivariate functions // in Schoenberg I.J. ed. Approximations with Special Emphasis on Spline Functions Academic Press, New York, 1969, p.223-277.

85. Gordon W.J. Spline-blended surface interpolation through curve networks // J. Math, and Mech., 1969, V.18, №io, p.931-952.

86. Gordon W.J. Blending function methods of bivariate and multivariate interpolation and approximation // SIAM Journal of Numerical Analysis, 1971, V.8, p. 158-177.

87. Gordon W.J., Riesenfeld R.F. B-spline curves and surfaces. In Barhnhill R.E. and Riesenfeld R.F. ed., New York: Academic Press, 1974.

88. Gordon W.J., Riesenfeld R.F. Bernstein-Bezier method for the computer-aided design of free form curves and surfaces // Journal ACM 1974, V.21, №2, p.293-310.

89. Hartley P.J., Judd C.J. Parametrization and shape of B-spline curves for CAD // Computer-Aided Design, 1980, V.12, p.235-238.

90. Hoschek J. Intrinsic parametrization for approximation // Computer Aided Geometric Design, 1988, V.5, p.27-31.

91. Hoschek J., Lasser D. Fundamentals of computer aided geometric design. -Massachusetts, Wellesley: AK Peters Ltd., 1993.

92. Wl.Holladay J.C. A smoothest curve approximation // Math. Tables and Aids Computation., 1957, V.l 1, №60, p.233-243.

93. Kuznetsov E. B., Yakimovich A. Yu. The Best Parameterization for Parametric Splines Interpolation // Lecture Series on Computer and Computational Science, 2004, V.l, p. 1201-1204.

94. Kuznetsov E.B., Yakimovich A.Yu. The best parameterization for parametric interpolation // Journal of Computational and Applied Mathematics (in print).

95. Lee E.T.Y. Choosing nodes in parametric curve interpolation. // Computer-Aided Design, 1989, V.21, p.363-370.

96. Loh R. Convex B-spline surfaces // Computer-Aided Design, 1981, V.13, p.145-149.

97. Mas tin C.W. Parametrization in grid generation I I Computer-Aided Design, 1986, V.18, p.22-24.

98. Melum E. Curve and surface fitting based on variational criterion for smoothness. Central Institute of Industrial Research, Oslo, 1969.

99. Melum E. Non-linear splines // In Barhnhill R.E. and Riesenfeld R.F. ed. Computer Aided Geometric Design New York: Academic Press, 1974.

100. Reinsch C.H. Smoothing by spline functions. I //Numer. Math. 1967, Bd 10, Hft3, s. 177-183.

101. Reinsch C.H. Smoothing by spline fonctions. II // Numer. Math. 1971, Bd 16, Hft 6, s.451-454.131 .Runger C. Über empirische Funktionen und die Interpolation zwischen äquidistanten Ordinaten // ZAMM 1901, №46, s.224-243.

102. Schoenberg I.J. Contributions to problem of approximation of equidistant data by analytic functions // Quart. Appl. Math., 1946, V.4, № 1, c 54-99, №2, 112-141.

103. Schoenberg I.J. Spline interpolation and the higher derivatives // Proc. Nat. Acad. Sei. USA. 1964, V.51, № 1, p. 24-28.

104. Schoenberg I.J., Whitney A. On Pôlya frequence functions. III. The positivity of translation determinants with an application to the interpolation problem by spline curves // Trans. Amer. Math. Soc. 1953, V.74, №2, p.246-259.

105. Schoenberg I.J., Greville T.N.E. On spline functions // In Shisha O. ed.: Inequalities. Academic Press. 1967, p.255-291.

106. Schweikert D.G. An interpolation curve using a spline in tension // Journal Mathematics and Physics. 1966, V.45, p.312-317.

107. Shalashilin V.l., Kuznetsov E.B. Parametric Continuation and Optimal Parametrization in Applied Mathematics and Mechanics. Dordrecht / Boston / London: Kluwer Academic Publishers, 2003.

108. Töpfer H.J. Models for smooth curve fitting // Numerical Methods of Approximation Theory Birkhäuser Verlag, 1982, V.6, p.209-224.

109. Van Rooj P.L.J., Schurer F. A bibliography on spline functions I I II-Natherlands, Technological University Eindhoven, Department of Mathematics, T.H.Report, 73-WSK-01,1973.