автореферат диссертации по инженерной геометрии и компьютерной графике, 05.01.01, диссертация на тему:Геометрическое моделирование кривых линий и поверхностей методом адаптивной полиномиальной интерполяции

Л\ИНИСТЕРСТВО ВЫСШЕГО И СРЕДНЕГО СПЕЦИАЛЬНОГО ОБРАЗОВАНИЯ УКРАИНЫ

Киевский ордена Трудового Красного Знамени инженерно-строительный институт

ГЕОМЕТРИЧЕСКОЕ МОДЕЛИРОВАНИЕ КРИВЫХ ЛИНИЙ И ПОВЕРХНОСТЕЙ

МЕТОДОМ АДАПТИВНОЙ ПОЛИНОМИАЛЬНЪй ИНТЕРПОЛЯЦИИ

Специальность 05.01.01 — Прикладная геометрия и инженерная графика

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

НАЙДЫШ Андрей Владимирович

УДК 515.2:681.3

Д п т о р е ф е р а I диссертации на соискание ученом степени кандидата технических наук

Киев — 1092

Диссертационная работа выполнена в Мелитопольском ордена Трудового Красного Знамени институте механизации сельского хозяйства.

Научный руководитель — заслуженный деятель науки Украины, доктор технических наук, профессор Михайленко В. Е.

Официальные оппоненты:

доктор технических наук, профессор Бадаев Ю. И.

кандидат технических наук, доцент Седлецкая Н. И.

Ведущее предприятие —. производственное объединение «АвтоЗАЗ».

Защита состоится 17 июня 1992 г. в 13 часов на заседании специализированного совета Д068.05.03 в Киевском ордена Трудового Красного Знамени инженерно-строительном институте по адресу: 252037, г. Киев, Воздухофлотский проспект, 31.

С диссертацией можно ознакомиться в библиотеке Киевского ордена Трудового Красного Знамени инженерно-строительного института.

Автореферат разослан _Ь 1992 г.

Ученый секретарь специализированного совета кандидат технических наук, доцент

Подписано к печати 4. 05. 92. Объем 1,375 п. л. Формат 60X841/,6. Заказ 1224. Тираж 100. Типография ВА ПВО СВ.

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

Актуальность. Геометрическое моделирование является мощным инструментом решения многих научных и производственных задач, основой создания новых САПР на базе современны). ПЭВМ. Среди объектов моделирования исключительное место занимают дискретно представленные кривые (ДПК) и поверхности (ДПГО,- в задачу моделирования которых входит получение расчетных алгоритмов или формул приближения Функций.

Основой геометрического моделирования и составления расчетных алгоритмов являются методы прикладной геометрии кривых линий и поверхностей, в разработку которых большой вклад внесли ведущие отечественные ученые Бадаев Ю. И., Иванов Г. С. , Ковалев С. Е, Котов И. И. , Михайленко В. Е. , Надол'.нный В. А. , Осипов В. А. / Павлов А. В. , Подгорный А. Л., Подкорытов А. Е , Полозов В. С., Рыков Е Е , Скидан И. А. , Тевлин \ М., Филиппов П. а , .Якунин В. И. и их ученики, а такие зарубежные ученые Безье Р. , Гилой 3. , Куне С., Кькмен У. , Принс \1, Сазерленд А., Фокс А., Фэррест А. и другие, интенсивно развивающее методы вычислитель' ной геометрии.

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

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

сти повышения точности неизмеримо возрастают, если решение искать на множестве указанных полиномов, т. к. каждый из них обладает своими особенностями и их учет при составлении и использовании моделей может повысить устойчивость процесса и снизить осциляцию решения. В связи с этим возникают 2 проблемы: 1) разработка, критериев соответствия ДПК и модели, анализ ДЛЯ и расчет характеристик, по которым происходит сравнение геометрии ДПК и модели; 2) оценка погрешности метода и разработка мер ::о ее уменьшению. Цель работы состоит в разработке, программной реализации и практическом, внедрении метода интерполяции, обеспечивамего минимальную погрешность приближения.

Для достижения поставленной цели в работе решаются следующие задачи:

- разработка способа анализа исходных дачных с цель» установления соответствия геометрии ДПК или ДПП и интерполирующей функции;

- формирование интерполирующего аппарата;

- оценка' погрешности интерполяции; .

- разработка алгоритмического й программного обеспечения предлагаемого метода; . ■

- практическое внедрение результатов исследований.

Методика исследований. Б процессе решения поставленных в работе задач использовались методы начертательной, аналитической и дифференциальной геометрии; теории интерполяции; математического анализа и вычислительных методов. -

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

- понятие обобщенных разделенных разностей и способ их расчета;

- интерполяционные формулы на основе обобщенных разделенных разностей;

- понятие обобщенных производных, их формирование и расчет;

- оценка предельной погрешности показательной.;: тригонометрической интерполяций;

- зависимость погрешности от переноса и скатия отрезка- интерполяции;

- способ адаптивного определения алгебраической производной в

заданной точке ДНК;

- способ адаптивьой дискретной полиномиальной интерполяции ДПК;

- обобщенные частные разделенные разности для ДПП;

- формулы двумерной интерполяции ДШ на основе обобщенных частных разделенных разностей.

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

lía зоезяу заносятся положения, представляющие научную новизну.

Рсаджацл:; результатов 1^следований. Результаты исследований в виде ППП внедрены в лаборатории коренной мелиорации склонов Украинского ffiOI защиты почв от эрозии (г.Луганск) при подготовке исходных данных о рельефе местности и решении задач проектирования противозрозионных гидротехнических сооружегчй; при гэделиро-вании топографической поверхности в в/ч 35533; в учебном процессе в ХВВКИУ PS (г. Харьков).

Апробация работы. Основные результаты работы доложены и обсуждены на X Всесоюзном научно-методическом семинаре "Инженерная и машинная графика" в Полтаве в 1991 г., на Всесоюзной конференции "Ко?л1ыотерная геометрия и графика в инженерном образовании" -"КОГРА<1>-91" в Н-Новгороде в 1991 г., на международной конференции в Севастополе в 1991 г., на республиканском научно-практическом семинаре "Компьютерная графическая подготовка специалистов" в Витебске в 1992 г.; на семинаре "Прикладная геометрия и инженерная графика" КИСИ в 1991 г.; на научно-методических конференциях Мелитопольского института механизации сельского хозяйства в 1990, 1991, 1992 г.

Объем работы. Диссертация состоит из введения, пяти глав, заключения, списка литературы из 194 наименований и приложения. Работа содержит 198 страниц машинописного текста, 59 рисунков и 18 таблиц.

СОДЕРЖАНИЕ

Во введении .обоснована актуальность исследован' Я, выполнен

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

Б первой гласе работы рассматриваются разделенное- разности." (РР), как средство анализа заданной ДПК. Алгебраически разделенные разности к-го порядка'для заданного точечного ряда^Хч^}, ¿ =С,т определяются по формуле

У1

[хР... хР»1 = 2. ^ (XI -хз)' Р = °'т*(1)

и названы нами алгебраическими потому, что их свойства ссответ- • ствуют алгебраическим полиномам. Разность т-го порядка для (гсн-1) заданных точек рагна старшему коэффициенту От ПР;; Хт в уравнении алгебраического полинома. Если Ц-, -О , то точки рас-полокены на графике полинома степени (т-1), если разности порядка (ш-1) не равны нулю. Не равная нулю разность ггг-го порядка для (т+1) точек показывает меру их приближения к графику полинома степени (т-1) . .

Естественно, что не всегда точки ЛПК тяготеют к графику алгебраического полинома. Предположим, что точки ДПК расположены на показательном полиноме

У = аа + й1-с,х+а2с*г+ ... +Отс£ ,9Ч

ч

Введем показательные РР первого порядка [Хд Хр-ц] с

Г., и 1 _ Ур+1 - Ур ■ ъ—--

.1ля ХР+1\С~ ¿Хр+1_СХР , Р— О; /7?о)

геометрическая суть которых на функциональной сетке С** ___ сКт представлена на рис. 1 в сравнении с алгебраическими РР. '

В процессе перехода к функциональной сетке ДПК претерпевает деформацию растяжения - сжатия вдоль оси ОХ. Если точки исходной ЛПК на равномерной сетке принадлежат полиному У — 0.0 + 0.1С? на сетке С*1 произойдет "выравнивание" полинома б прямую (¡>но. £) т. е.' показательный полином 1-го порядка на заданна! сетке перейдет е алгебраический полином 1-го порядка на функциональной сетке.

Для гп-й показательной РР на равномерной сетке с пзгом Ь имеем у ц

г , _ _¿То к'

Xi Xz x3 0 c*° с*1

Рас. 1. Г еометрический с мыс а алгебраической, и показательной разделенных разностей.

LXoXila ~ % PX,XzJa ~ tg oCf

ÍXoXi"}q1 Zg c(0

[XiX^Jcf-ig^t

У A

Рис. 2 8ыра6ни8ание полинома y=a0+aiC «а покагательной сетке CiXLt 1=013.

гдеЗ^"* - симметрические по::иномы от ш переменных СД порядка т-к. Рассматриваются свойства показательных РР.

Свойство 1. Показательная разность является симметрической функцией своих аргументов, так что порядок узлов при расчете не играет роли'.

Оойетва 2. Для произвольных (т+1) и более точек показательного полинома порядка (ш-1) РР порядка гг и вьке равны нулю.

Свойство 3. Значение ш-й РР равно старшему коэффициенту ат при показательного полинома, определяемого (г:-1) заданными точками.

Свойство 4. Значение показательной РР, в отличие от алгебраической, зависит от полог,¿ния отрезка интерполяции на оси ОХ

Свойство 5. Показательные РР в значительной степени ззвисят от погрешностей исходных данных.

Свойства показательного полинома зависят от того, какими бу- ■ дут числа С1г .. Ст ■ Практический интерес представляют -поликомы, у которых ё г неотрицательное, действи-

тельное число. В работе рассматриваются степенные показательные полиномы с основанием <3=2 и экспоненциальные полиномы (¡З-е). Степенная показательная РР т-го порядка имеет вид

V У к .

гп ж*3 . _ . (5)

■¡""¿-¿■к

и позволяет определять ¡¿еру близости точечного ряда ЛПК к показательному полиному той или иной степени.

Свойство 6. Каждая операция взятия показательной РР при основании с! от' степенного показательного полинома с тем же основанием понижает его степень на единицу, так что на определенном шаге РР обнуляются (см. рис. 3), как и в случае воздействия алгебраических РР на алгебраический полином.

Для точек, расположенных на графике четного тригонометрического полинома 1-го рода у = йу СО, предлагался четные тригонометрические РР 1-го порядка

г-, -, _ Ур -

№ Хр+1]С« - со5Хр+<-со%хр > О; т-1 (о;

Значение РР разно тангенсу угла наклона &ьена ¿эудхноГ точочне/о

Обобщенные разделенные разности различных ДПК Графика дискретно представленных кривых

■ 991

|[? .„тГт-Ж

ТГ

I и»'-"

гп

Графит первых разностей

Т

0 6 6 й

Графики вторых разностей .

ЦР33"

А А,1г?£раичгсл'ае РР' Алгебраические РР косинусные РР

неза.кснсп1ермй £,ПК алгебраической ДПК косинусной АПК ■

__Рис.3

ш

ЦТГ!

±1

ш

тптттттш

• Показательные РР показательной ДПК

ряда к оси ОХ на функциональной сетке СОЪХс. Выравнивание косинусного полинома происходит, как "по горизонтали", в процессе перехода к сетке Со&х1 , так и "по вертикали", в процессе последо вательного расчета РР (рис.3). Формулы для расчета т-й РР приведены в табл. 1.

Значение т-й РР показывает' меру близости ДПК к косинусному полиному (п>-1)-й степени. Если это значение равно нулю, то точки ДПК расположены на графике указанного полинома

Аналогично (6) вводятся косинусные РР для степенного-косинусного полинома (2-го рода) у = О^ ■ Соб^Х . В отличие от формул разностей 1-го рода (см. табл.1) разности 2-го рода не имеют множителей 2т~/ и являются обобщением алгебраических РР, если вместоХу в формулы ввестиС05х}- "С геометрической точки эре ния это не означает, что свойства алгебраических РР автоматически переносятся на степенные косинусные РР, т. к. поведение функции накладывает свои особенности на устойчивость вычислительного процесса, поведение погрешности и осцилляцию результатов.

Во избежание нулевых значений в знаменателе (6) при расчете косинусных РР обязателен переход от отрезка интерполяции [х0; Хт. к отрезку СО; 13.

. Для точек синусных полиномов 1-го и 2-го рода аналогично косинусным, предлагаются синусные РР 1-го и 2-го рода(см. табл. 1) отличающиеся наличием множителя £т • .

Так как синусоида и косинусоида являются конгруэнтными кривы ми, то и их РР имеют одинаковые свойства

Значение синусной разности показывает степень близости ДПК к соответствующему синусному полиному.

Таким образом предложенные РР позволяют расчетным путем определить тип ДПК и вид полинома (алгебраический,- показательный, косинусный, синусный), если соответствующие разности «а определенном шаге становятся равными нулю. Если ни одна из разностей не становится равной нулю, то из их сопоставления (см. гл.4) можно сделать вывод о предпочтительности применения того или ино' го полинома для моделирования ДПК Обобщенные РР являются, таким образом, средством анализа ДПК и выбора оптимального вида и степени полинома

Во второй главе на основе обобщенных РР предложены формулы

Таблица 1

..... N »/« Вид полинома Разделенная разность Интерполяционная ф-ла 8 ф. Лаграмжа Интерполяционная ф-ла в tp. Ньнзтона Остаточный, член

1 АлгеНраический. У =(7j -XJ РРа-l -рГ~- y=fy п X"Xj у ¿-Ук'Л XK-XJ n» m-f /?о= /7(X-ij) J"0

О Показательный рр _ Ái У* п C&'HtfC) y-íy«-jr -

3 Степенной показательный У - QjdJX РР u ^ Ук 1 h/lsf-^) Г n d*-d*j yfy«-akd« к*о j*k о Mi m-f y-ysLppn-n(dx-d«) K*o j'O *d=PPd-n(f-d*¡) jwO

4 Косинусный Uto раза у= aj-casjx рр .г у* ico J^a.itx u-fu-ñ cos*-cos*j у ¿-У«¡J casXK-mxj *-0 Jtk "? m-f m-l • /f(cosx-easxj) J-o

5 Косинусный 2-города y--Oj.oos2x рр ^— ""hjQjír*-"^ Umfy^fí to WUCCSXj m m У my¿j~PPL' Í1(C0SX-C0ÍX¡) fz eH7 j'S m

6 Синусный. 1-го рода У"- Qj • SLnjX рр -f я* Sl ¿—2 -súiJVnÍJiií-Ciit^ к-а ' ,,Xa -sin* П etax-cuaS ¿i" Щи, asx?i<axj **0 ' Uk m m кшо -i"0 . m П (cosx-cosxj) J-0

7 '-Уносный 2-гоpeda У= a'j ■ Sinx 42- Уг ГГ V S:j7a .fl&MtSLnxj) f " JtZJt* ' yfy-ñ iU,x-sinxJ JФК П7 У-Уyjfpp • /7 (6¿njf-5tnxj) /».a 2 j=o

полиномиальной интерполяции. За основу взяты известные алгебраические формулы Лагранжа ' .

Ук-Л. (7>

и Ньютона

к-1

с остаточным членом Яа(х)-= [х.х.а...хп^а-%т{х) , где ■ _

-П(Х-Ха)- алгебраический фундаментальный полином, 5= /;/77 На основе степенных показательных Р? предложены для показательных ДПК интерполяционные формулы в форме Лагранжа Л} т г! х ¿х)

и е форме Ньютона

от

У = Уо 4 X Гхс.х*] %к (х)+йЫ(Х) (10)

к-1

с остаточным членом •

,/хС

Представление формул в форме Ньютона обладает многими вычислительными преимуществами по сравнению с формой Лагранка.

Аналогичные формулы предложены для тригонометрической интерполяции (см. табл. 1).

Для сравнения различных моделей одной и той же незакономерной ДПК в табл. 2 представлены результаты интерполяции (абсциссы узлов подчеркнуты), откуда видно, что косинусная модель, геометрия которой в наиЭольшей мере не соответствует ДПК, на отрезке [0,74; 1,05) осциллирует.

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

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

- И -

Таблица 2

Ордината У Аг-ебра- ичезкая модель Показательная молель "осикус-нак модель Синусная | модель

Абсцисса X

■ 0,07 30,0000 30,0000 30,0000 '0,0000 !

0.12 54,4000 54,144С 47 ,6594 54,67 2г. |

0,19 73,0000 78,0000 78,0000 77..99*59

0,25 90,3970 90,6547 ?°,С166 9 0,;0 02

0.33 98,5650 98,8604 111,3370 93 ,3049

0,39 100.1990 100,3 5 33 106,3975 99,8967 ;

0.42 100,0000 100,0000 100,0000 100,0^03

0,52 96,5269 96,2147 £3,8635 96,5754 !

0.5<"- 95,4340 95,?374 г?,4650 Э 5 ,5 г 7 Э :

0,61 91,9996 92,0001 Ь» 1 ,'9999 32 ,0001

0,69 89,3160 89,6212 103,7914 89 ,2075

0,7 4 86,3989 69,0002 33,9996 39 ,0001

0,80 90,6137 89,6723 18, 1990 91,0333

0,81 . 91,1413 89,9447 ' -0,9101 91,6625

0.Э8 114,6536 •07,3222 -434,9464 116,7626

1,05 134,5522 132,6553 -18,0744 13г ,0323

1.06 137,9998 , 137,9999 13",9981 ' 138,0004

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

Вводится показательная производная у'п , как предел отношения (3) при ха+< —хо кмом

и' —

" ~ ¿л С, ■ С* ' (12)

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

Уе,~е" т' еп с,, еп^-. •е, '

. Сг • £?2 Ст-2

На следующем саге Ус ст~® ' полиномы являются

бесконечно диффер нцнруемыми в смысле производной (12).

Рассматриваются степенные показательные производные г.; яов&г.и» с и, в частности, экспоненциальные производные Еетстзую^сс полнаоуэв, а таккэ произвольной непрерывно дисое-

ренц-лруемой функции К-/;.

fi"-¿r U^^'Zl+r2-1 L-J-

K-iTm. ii«

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

С геометрической точки зрения значение показательной производной по основанию Cf равно тангенсу угла наклона к оси ОХ касательной к графику функции на функциональной сетке С*1 .

Вводится понятие четной тригонометрической (косинусной) производной ур05 , как предел отношения (6) при Хрн-^Хр,

и' - &

»cos —sin X (15)

■ Старшая косинусная производная для косинусного полинома 1-го рода равна . _

Усо& = Qm-т! ■ 2 > (16)

а для степенного косинусного полинома

у£>=ат-т.1 . (17)

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

, ' • Для произвольной функции f(x) косинусные производные можно рассчитать по рекуррентной формуле

MKJ _ 1 d Г" - с' , 7-

Тсоз ~ SLPX ' Ж V+cos Л Тсoj -Та , К= 1 ,т. (is) Вводится понятие нечетной тригонометрической (синусной) производной

и' ~ fa

у* г cos* (10>

Стачанной синусный полином ("-го рода) явдлется конечно днф-'ixjpeiiLi: 1!-уо-мой функцией в смысле производной (19), так что

|/f= Om-m.' (ZO)

Oo?aJibHi;e поликомы - бесконечно дифференцируем* ь смжле (19). iiwi произвольной функции П. X)

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

£е[х0;хт], . (22)

откуда вытекает [х.... Xirij - О. и flm*(x)=0/n-m! для всех видов степенных полиномов и им соответственных производных.

В четвертой главе рассматривается оценка погрешности интерполяции некоторой функции f(x) предложенными в гл.2 поликомами Р( х). При этом учитывается то, что погрешность R(x)=f(x)-P(x) есть функция от х, поэтому отыскивается предельная ее оценка в предположении, что разделенная разность £хх0... XmJ и фундаментальный полином ^(х)принимают свои максимальные по модулю значения.

/?rx}=f(x)-PCx)-[xxo...xm] -VW (23)

Имея в виду, что f(x) - (пн-1) раз дифференцируемая функция, Р( х) - один из рассматриваемых полиномов степени го, Ф(Х) - соответственный ему полином степени (rm-l), и дифференцируя (ш+1) раз обе части (23) соответствующей виду полиномов Р(х) и f(x) производной, имеем равенство (22). Так как положение точки £ неизвестно, то вместо {<,т\4>) берется модуль-максимум М соответствующей старшей производной, т.е. М ~ (х)/. Тогда для всех полиномов предельная оценка равна

/?т(х)= (тУвГ-Чах) ■ (24)

Из (24) следует, что если заданную f(x) представить на соответствующей ей функциональной сетке так, что ее старшая производная, а значит и старшая РР (см. (22)), станет равной нулю то и погрешность интерполяции будет равна нулю. На этом и основан поиск вида функциональной сетки и расчет РР,. чтобы узнать порядок полинома Р(х) и при которых Rm(x) — Q.

Рассматриваются факторы, влияющие на величину погрешности, из которых главным является несоответствие геометрии ДПК и интерполирующего. полинома.

Исследуется возможность уменьшения погрешности интерполяции. Доказано, что перенос и сжатие отрезка интерполяции не влияет на

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

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

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

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

В пятой гяавс рассматривается суть метода адаптивной интерполяции, включающего з себя: • ]. Переход ит заданного отрезка [Хо; Х/п] к отрезку, обеепечива-. ющему минимум погрешности;

2. Анализ ДПК при помощи обобщенных РР;

3. Расчет максимальных значений фундаментальных маогочленрв по ■ -каждому из полиномов;

4. Определение абсолютной величины К-последнего слагаемого в

Pua. .4. Сравнение результатов похазатс/ьнгй с основанием 2 интерполяции да ц после сжатий отрезка интерполяции. -

интерполяционных формулах з форме Ньютона и выбор адаптивного полинома по минимальному И. 5. Расчет ДПК и репенке прикладной задачи.

Кроме глобально?, полиномиальной интерполяции предлагается способ адаптивной дискретной интерполяции, гаг-люча.'эп.йся з построении точек сгуЕ?к;:з на .зжальиом участке кг основе адаптивного полинома согласно приведенном:/ ылгг алгоритму. Сормулы для

' - 16 -

расчета точек сгущения ДПК выбирается .из табл. 1 для соответс-. твенного полинома г, форме Лзгрсш:гл. 5,!отодп;;а определения адаптивного полинома программно реализована б ППП "МЭПЕЬ".

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

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

На полученной модели решаются следующие задачи:

1. Построение произвольной точки ДПК.

2. Определение касательной к ДПК в произвольной ее точке.

3. Расчет нормали к ДПК в произвольной ее точке.

4. Определение длины кривой или ее отрезка.

5.- Вычисление площади, ограниченной замкнутой ДПК.

6. Локальная коррекция формы ДПК. •

7. Нахождение локальных экстремумов'ДПК

Основой решения задач является способ адаптивной дискретной интерполяции. Перечисленное множество, задач позволяет в автоматизированном режиме определить точки линий водотоков (линий наибольшего ската рельефа местности) и водоразделов (линий наименьшего ската). Методик^ расчета реализована в ППП "КШУ и внедрена в УНШЗПЭ (г. Луганск) йри проектирований противозрозионных пиротехнических сооружений.

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

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

Естественным сбс5к;еннем адаптивного моделирования ДПК на плоскости является моделирование ДПП. Для заданного дискретного упорядоченного точечного каркаса {х;., 1~0,т,

ДПП рассматривается известнке а?ге6раические двумерные модели в форме Лаграшс*

^ттшг . <»>

и з форме Ньютона

л. ^ 1-< ;-(

2С (х.у)= 2. I- [Хо...хси>,...!/1 ■ П(*-хР)-П(У-Уч), (25)

где Г-0,,. XI ; у0...уз\а ~ частны- алгебраические РР.

Рассматривается геометрическая суть частной смешанной РР ; и} Ш-и] . При равенстве ее нули четыре определяйте ее точки располагаются в одной плоскости, так что для многогранной поверхности из 4-угольных ячеек смешанные РР для каждой ячейки равны нулю.

Базируясь на геометрических представлениях, частные РР -можно использовать для геометрического анализа исходны:-: данных. Г; частности, если все частные РР 2-го порядка равны нулю, то точки каркаса"располагается в одной плоскости. У параболоида 2-го порядка все .разности 3-го порядка равны кулю в то время, когда хотя бы одна из РР 2-го порядка не равна нулю. Используя резуль таты такого анализа, можно регать вопрос о целесообразности применения алгебраического полинома для моделирования заданной ДПП.

Естественно, что по аналогии с ДПК точки ДПП могут не относиться к алгебраическому типу, а представлять собой показательные или тригонометрические поверхности. Для обеспечения возможности их анализа вводятся частные степенные показательные РР с сснова-НИЯМ.. ПО X Л по у

[*«»■• »Л«^».»4,, <?п

и т. д. Предлагаются формулы показательной двумерной интерполяции в форме Ньютона, если в (25) и (26) заменить х на ^ к у ка<£\ На основе частных показательных РР можно осуществить^аналогично частным алгебраическим РР, анализ ДПП с целью дальнейкего моделирования ее показательными двумерными моделям!. Та-:, например, для показательного полинома ^-^«-¿¿/юс/^+Яо*йн^с^т

0-гос17^-+с1о2(^^астные показательные РР третьего порядка во всех точках каркаса равны нулю, а Еторые РР - не' равны кулю • (рис.5). Этот анализ можно продолжить для разностей более высо-

Рис„ 5. Каркас ДПП показательного полинома Х-га порпока (Аххх=Ахху ~Ахщ ~Аууу~и,

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

Таким образом введенные 4 типа частных.РР позволяют осуществить чискретный анализ ДПП и определить тип интерполирующего полинома, если соответствующе РР становятся равными нучю. "ели этого не происходит, то адаптивный полином выбирается по минимуму абсолютной величины алгебраической суммы последних слагаемых в формуле в форме Ньютона, содержащих разнос 1 и одного и того же порядка.

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

1. Построение произвольной точки ДПП.

2. Определение вектора нормали в произвольной ичке ДПП.

3. Построение линии пересечения ДПП плоскостью.

4. Локальная коррекция ДПП.

Адаптивная последовательная интерполяция ДПТ, решение яса-зангых задач программно реализованы в ППП ЯАБРОУ.

ЗАКЛЮЧЕНИЕ

ф

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

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

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

3. На основе указанных обобщенных разделенных разностей полу-

' - 20 -

чены интерполяционные формулы, соответствующие отмеченным типам ДПК, ■ в форме Лагранжа и форме Ньютона с остаточными -»ленами.

4. Предложены обобщенные производные, позволяющие произвести оценку продельной погрешности соответствующей интерполяпли.

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

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

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

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

9. Решения задач геометрического моделирования на основе предложенного метода адаптивной полиномиальной интерполяции программно реализованы в ППП расчета ДПК и ДПП и внедрены в условиях проектирования противоэрозионных гидротехнических сооружений в УНИИЗПЭ (г. Луганск), при моделировании и расчете топографической поверхности (в/ч 35533), в учебном процессе ХВВКИУ РВ

(г. Харьков).

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

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

• Основное содержание диссертации изложено в следующих' работах:

1. Найдыш А. В. Узагальнен1 розд1лен1 ,.р1знищ. //Прикл. геом. и

инж.граф. - К.; БуД1велъник, 1991, вып. 52,- с. 124-126.

2. Найдыш A. B. Тригонометрические разделенные разности. Мелитоп. ин-т мех. с. х., Мелитополь, 1991, 8 с. (Депонир. в ВИНИТИ 25.06.91 Н 2697-В 91).

3. Найдыш A.B. Показательные разделенные разности. Мелитоп. ин-т мех. с. х., Мелитополь, 1991, 10 с. (Дег.онкр. в ВИНИТИ 23. Об. 91

. N 2698-В 91).

4. Найдыш А. Е Повышение точности интерполяции на основе обобщенных разделенных разностей. У/Инкенерная и машинная графика: Тезисы докл. X Всесоюзного семинара, 6-7 июня 1991 г. -Полтава: ПолтИСИ, 1991,-с. 31.

5. Найдьпл А. R Основные вопросы адаптивной полиномиальной интерполяции. //Проблемы графической технологии:- Тезисы док.1 Международного семинара, октябрь 1991 г., - Севастополь: Севас-топ. приборо-строит. ин-т, 1991,- с.

6. Найдыш -А. В. Программное обеспечение адаптивной полиномиальной интерполяции. //Компьютерная геометрия в инженерном образовании: Тезисы докл. Всесоюзн.конф. КОГРА&-91, октябрь 1991 г., Н-Новгород, 1991,- с. 125-126.

7. Найдыш А. В.. Моделирование кривых линий и поверхностей на основе адаптивной полиномиальной интерполяции. //Материалы научно-практического семинара "Компьютерная графическая подготовка специалистов 11-12 февраля 1992, - Витебск: 1991,

с, 66-6?.

8. Найдрш A.R Обобщенные производные. //Материалы научно-практического семинара "Компьютерная графическая подготовка специалистов 11-12 февраля 1992, - Витебск: 1991, с. 96.

В робот! розглянутс розв'язання проблеми шдвищення точное?! геометричного моделювакня кривих л)н1й тр поверхонь в результата застосування методу адаптивно! пол1ном1ально1 ттерполящ i, до складу якого входить: анал1з ДПК та ДПП га допомогою узагалъне-них роздиених рхзниць (РР), виб1р адаптивного поганома, оц-.нка похибки та розрахунок, зпдно з випов^днон формулою. алгебра;ч-HOi, ПОКаЗНИКОВО!, KOCHHyCHOi чи синусно! ютерполяцн на ОСНОВ; запропонованих РР. Розроблен1 алгоритми та програми автоматиьова-ного розрахунку ДПК газв'язання прккладних задач.