Описание поверхностей на основе экспериментальных данных с помощью интерлинации функций и его применение тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

> •

" Ьтсгитут кібернетики імені В.М. Глупгкова

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

Крикова Інна Володимирівна

УДК 517.5

Опис поверхонь на основі експериментальних даних з допомогою інтерлінацн функцій та його застосування

01.01.07 - обчислювальна математика

Автореферат дисертаїрїна здобуття тукового ступеня кандидата . фізжо-матгматичних тук

Київ - 1998

Робота виконана на кафедрі вищої математики та на кафедрі прикіадної математики Української інженерно-педагогічно! академії (Харків).

Науковий керівник:

Офіційні опоненти:

доктор фізико-математичних наук, професор Ліітеин Олег Миколайович, Українська інженерно-педагогічна академія, зав. каф. прикладної математики;

1) доктор фізлко-матемагичних наук, ст. науковий співробітник Гладкий Анатолій Васильович,

Інститут кібернетики ім. В.М. Глушкова НАНУ, провідний науковий співробітник;

2) кандидат фізико-математичних наук, ст. науковий співробітник Жуковський Олександр Миколайович, Інститут математики НАНУ,

. ст. науковий співробітник.

Провідна організація - Національний університет імені Тараса Шевченка, кафедра обчислювальної математики, Міністерство освіти України

Захист відбудеться “ 40 “ 1998 р. о // годині на засіданні

спеціалізованої вченої ради Д 26.194.01 в Інституті кібернетики НАН України імені В.М.Глушкова за адресою: 252207, Київ, пр. ахад. Глушкова, 40, Інститут кібернетики НАНУ.

З дисертацією можна ознайомитися в науково-технічному архіві Інституту кібернетіки.

Автореферат розісланий 1998 року.

Вчений секретар спеціалізованої вченої ради Д 26.194.01

кандидат технічних наук

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

тщальяість теми.. Сучасний розвиток науки та техніки, пов'язаний з ержанням та обробкою величезних масивів інформації про Землю і П з чуючий простір настійно диктує необхідність пошуку шляхів едставлення інформації про місцевість в формі, зручній для швидкого іду та обробки її на цифрових ЕОМ.

На практиці часто виникає задача відновлення поверхні за нчегош набором координат або за слідами на фіксованій системі ліній жм чином, щоб були збережені ділянки опуклості (вгнутості), нотогаюсті початкової поверхні. Така задача виникає, наприклад, при делюванні корпусів літальних апаратів, автомобілів, суден, в геодезії, ггографії, при відновленні форми поверхні Землі за даними радіолокації ) при обробці відомих карт і т.д.

В розробку методів та алгоритмів, що дозволяють будувати шиження функції одній та декількох змінних, щоб була збережена геометрія, вагомий внесок зробиш дослідження Березовського АІ., оталаї.І., Гребениікова О.І., Завьялова Ю.С., Капитана М.М. і Кузьміної

Квасова Б.І. і Яценка С.О., Лаппо Н.П., Литвина О.М., Мадишева L, Мірошниченка В.Л., Субботіна Ю.М., Чернишова Ю.К., Constantini >lo, Grimson W.E.L., Hahler Ante, Hdlger Mettke, Lahtinen A., Schmidt r., Shirman Leon A, Shumaker Lany L. та інших. В роботах Корнейчука

1. та Переверзєва С.В., Шабозова М. та інших отримані точні оцінки ибки наближення диференишовних функцій операторами сплайн-їрлінації на системі взаємо-перпендикупяряих прямих.

Хоча запропоновані методи побудови сллайн-інгерполятів однієї та ж змінних досить ефективні, але в ряді випадків поведінка цих сллайнів узгоджується з якісними характеристиками початкових даних. Це і являється у присутності викидів, осцкляцій, різноманітних відхилень, не характерні для початкового набору точок, тобто порушується готонність, з'являються точки перегину нз ділянках монотонності та клості початкових даних. Аналіз відомих результатів з теорії сплайн-їрполяції функцій однієї та двох змінних та сгаїайн-ііггерліііації функцій х змінних дозволяє стверджувати, що на даний час немає загального соду до побудови:

плашгів одній та двох змінних із збереженням ізогеометрії; операторів ілтерлінаїої, які б відновлювали з достатньою точністю ерхні Z=f(x,y) за ВІДОМИМИ ЇХ ЛІНІЯМИ рівня f(x,y) і = \,N, тобто

в’язували задачу картографії. Крім того, на сьогоднішній день є ряд ково-технічних проблем, де відомі методи не дозволяють розв'язати що

проблему ефективно, бо потребують для досягнення даної точнос наближення дуже великого числа експериментальних даних. Тому, ] дивлячись на різке зменшення габаритів та ваги сучасних ЕОМ, зада1 зменшення числа експериментальних даних є актуальною, що пояснюєте також і потребою зменшення втрат на одержання, зберігання та обробі цих даних.

Зв’язок роботи з науковими програмами, планами, темами. Дисертац виконувалася за держбюджетною темою: ’’Розробка методу мінімізаі числа експериментальних даних в алгоритмі відновлення рельєф місцевості та створення на його основі програмного забезпечення” (96-ЗГ § 1). Дисертацію виконано протягом 1991-1995 рр. на кафедрі вшц математики, а протягом 1995-1996 рр. на кафедрі прикладної махемагга Української інженерно-педагогічної академії (Харків).

Мета і задачі дослідження:

1. Розробка ефективних метода і алгоритмів відновлення поверх: місцевості за відомим набором ліній рівня (так як це задається топографічних картах) з допомогою иггерлінації функцій із збереження ізогеометрії.

2. Розробка ефективних методів і алгоритмів відновлення кривих поверхонь на ослові експериментальних даних і деяких якісні характеристик про наближуваний об’єкт (монотонність, опуклість тохцо) і основі використання параболічних та кубічних сплайнів однієї та двс змінних із збереженням ізогеометрії.

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

4. Створення пакету програм для реалізації запропонованих методів. Головні вимоги до таких алгоритмів: забезпечення заданої точності пр збереженні якісних характеристик (монотонність, опуклість тощо) кривих поверхонь; достатня гладкість результуючого сплайна або сплайнов< поверхні, можливість ефективної реалізації на ЕОМ.

Для досягнення та мети в дисертації були поставлені такі задачі-

1. Побудувати ізогеометричш стишиш одній змінної.

2. Розробити загальний підхід до оцінки похибки наближени сплайпамн одній змінної.

3. Побудувати в кожному з елементів, на які розбивається обласі наближення (трикутники з криволінійною стороною, п'ятикутники прямолінійними та криволінійними сторонами) формули наближення допомогою інтерлшації функцій.

Означення. Фігуру в = ^х, у)\х( < х < хм, у} < у < і{х), £(х) < 0 (> 0) будемо називати трикутником з криволінійною гіпотенузою.

з

4. Розробити метод відновлення поверхні сплайнами на нерегулярній ітці, оснований на використанні сшгайн-ііггерлінадії.

5. Розробити загальний підхід до побудови біквадратичних сгогайнів.

6. Розробити методи відновлення поверхні із збереженням югеометрії за допомогою формул інтершнації і методів квадратичного роїрзмування за інформацією лише на лініях рівня.

Таукова новизна одержаних результате. В роботі отримані нові езультати, які виносяться до захисту:

1. Розроблено метод явної побудови сллайнів парного степеня, жрема, другого, який

а) дає явне представлення цих сгагашгів (не вимагає розв'язання істеми штітих рівнянь);

б) не вимагає введення додаткової системи вузлів, крім вузлів пгерполяції;

в) не вимагає використання жпх-небудь граничних умов; осліджено оцінку похибки наближення, виведені достатні умови іукпості, монотонності тощо.

іайдепі точні оцінки у нормах деяких підаросторів, якщо (х)^і(і)=\/(х)*с2(і),і^Щ |/"!!0<1}.

2. Розроблено новий метод відновлення функції одній змінної із іереженняи ізогеометрії (оснований на явній формулі О.М. Литвина трального представлення залишку наближення даференщйовних ітїкцій інтерполяційними поліномами Ерміта) за даними інтерполяції, який

а) гарантує збереження опуклості (вгнутості) нз довільній сітці алів, якщо функцію задано тільки її значеннями на цій сітці;

б) за допомогою цього методу можна будувати інтерполяційні ^геометричні сллайни будь-якого степеня;

в) для даного методу запропоновано загальний підхід до оцінки іближення.

3. Розроблено метод відновлення функції однієї змінної, якщо в яких точках нам невідомо значення функції, але є якісна інформація про іведінку цій функції. Чим більше використовується точок, значення икціі в яких невідомо, тим ефективніхшш цей метод, бо для досягнення даної точності він використовує менше експериментальних даних, що іеншує витрати на отримання та зберігання інформації про відновлювану

ЯПЩІІО.

4. Вперше отримані оцінки похибки залишкового члена наближення х,у), що інтерлінують Дх,у) є С( 7) на 9Т інтерлінзнтами /т(х,у), де Т-апиця трикутника з криволінійною гіпотенузою.

5. Розроблено ефективний метод побудови формуй інгерлшації н границі опуклих областей складної форми, що використовує інформації про сліди функції/тільки в точках границі.

6. Розроблено алгоритм автоматичного розбиття області н підобласті, включаючи алгоритм автоматичної типізації елементів т автоматичного визначення підобласті с Dkj, /=1,2, в яку потралил

довільна т. М(х,у).

7. Розроблено та реалізовано алгоритм згладжуючої апроксішац функцій двох змінних з використанням інтєрлшацп.

8. Розроблено алгоритм побудови біквадратичних інтерполяційни сшіашгів без використання та з використанням інтерлінації, який не вимага введення додаткової системи вузлів (крім вузлів інтерполяції) і да представлення спиайнів в явній формі, не вимагаючи розв’язання систем рівнянь і не вимагає використання яких-небудь граничних умов.

9. Розроблено метод відновлення поверхні Землі за данимі радіолокації або картографії, що :

а) використовує інформацію про поверхню лише на лініях рівня, я вона задана в звичайних топографічних картах;

б) зберігає значення функції на лініях рівня, які використовуютьс. д ля відновлення поверхні;

в) вимагає по порядку менше експериментальних даних, ш класичний метод сгтайл-іятерподяції на регулярній сітці, що важливо прі обробці великого числа даних;

. г) використовує і зберігас додаткову інформацію про наближувану поверхню (монотонність, опуклість, тощо) на деяких лініях або під о бластях Практичне значення одержаних результата. Теоретична цішііст роботи полягає в застосуванні ефективного апарату інтерлінації д< розв’язання задачі відновлення поверхонь. Інтерліішцією функції Дх,у) на А ліліях Гі (к=],...М) (інші назви: bknding function interpolation (мішан інтерполяція функцій), поверхні Кунса, інтерполяція Манжерона і т.д. називається відновлення (можливо, наближене) функції / за II слідам) фк(х,у) /гк^/Ігк на цих лініях. Інтерлінантом називається деяка фугасці Li/(x,y), яка має властивості: Ім Дх.у) !п =ЫХ>У) /гг (тобто інгерліну функцію /на лініях , к= Всі теоретичні результат наведені

вигляді лем, теорем, описів алгоритмів, які в значній своїй частив наводяться вперше, або узагальнюють вже відомі. Результати дасертащ можуть бути використані для створення нових, а також при модернізаці існуючих методів побудови цифрових карг та методів відновлення рельєф місцевості. Очікуваний економічний ефект:

1) зменшення експериментальних даних, використаних для іщовлення рельєфу місцевості із заданою точністю;

2) економія затрат при одержанні і зберіганні експериментальних них про рельєф місцевості;

3) можливість створення економічних електронних аналогів пографічних карт.

:о6иапий внесок здобувана. Усі результати дисертаційної роботи римано за особистою участю автора. Дисертантом проведена така ібота:

1) розробка, чисельна апробація, програмне забезпечення і аналіз ’тості наближення загального методу побудови сгагайнів однієї змінної із ереженням ізогеометрії (детально параболічні та кубічні сплайни);

2) розробка, чисельна апробація, програмне забезпечення і аналіз члосгі наближення загального методу побудови сішайнів двох змінних із ереженням ізогеометрії;

3) розробка і аналіз похибки наближення методу іптерліпаціі функції і даним ліній рівня функції (включаючи побудову явних формул герліяації на п’ятикутниках, на границях опуклих областей, що надаються із частин відомих кривих).

ікож проведено чисельний експеримент (програмна реалізація всіх пропонованих у дисертації методів); розв'язані тестові приклади, доведено порівняння з відомими методами; також розроблено алгоритм 'Збиття області на елементи (автоматичної тяпизації елементів та тематичного визначення підобласті, в яку потрапила т. М(х,у)); виведені >рмули поліноміальпої іягерлшації для п’ятикутних областей тощо, гесок здобувача в роботах із співавгором:

[1] проведено чисельний експеримент, доведення теорем, аналіз :сельного експерименту. В [2] досліджено оцінку похибки наближення та «ведено чисельний експеримент, порівняння з відомими результатами. В І дисертантом створено алгоритм побудови сгаїайіив двох змінних, юведено чисельний експеримент, створено пакет програм. В роботі [4] сертант побудував раціональний ііггерлінант, що для відновлення функції ох змінних використовує інформацію про сліди функції лише в точках аниці. В [5] дисертантом зроблено аналітичний огляд та необхідна огрампа перевірка ефективності різних методів. В [б] виведено достотні юви монотонності та опуклості, досліджено оцінки похибки, проведено сельний експеримент, аналіз та порівняння отриманих результатів з їомими методами. В роботі [7] розроблено метод побудови явних герполяційних сил шагів. В роботах [8,11] дисертанту належить розробка [тематичної моделі рельєфу місцевості, алгоритму і пакету програм для

відновлених функції по їх лініям рівня (як в звичайних топографічних картах) із збереженням ізогеометрії. В [9] досліджено похибку наближення для деяких норм, доведено теореми. В роботі [10] виведено достатні теореми про збереження опуклості, вгнутості початкових даних.

Апробація результатів дисертації. Результати дисертації доповідалися на -XVIII науково-методичній конференції "Проблеми ступеневої інженерно-педагогічної освіти" (Харків, УІГІА, березень, 1995);

-Третій міжнародній науково-технічній конференції "Контроль та управління в технічних системах” (Вінниця, вересень, 1995);

-Всеукраїнській науковій конференції "Розробка та застосування математичних методів в науково-технічних дослідженнях “ (присвяченій 70 річчю від дня народження проф. П.С.Казимирського) (Львів, жовтень, 1995);

-на У-ій міжнародній конференції ім. академіка М.Кравчука (Київ, Національний технічний Університет України, травень, 1996);

-Міжнародній конференції "Теорія апроксимації та чисельні метода" (присвяченій 100-річчю з дня народження Е. Ремеза) (Рівне, червень, 1996);

-Школі-семшарі “Нелінійні крайові задачі математичної фізики та їх застосування” (Кам'янець-Подільск, жовтень, 1996);

- на семінарах кафедр обчислювальної математики, математичної фізики та чисельних методів Національного університету імені Тараса Шевченка, факультет кібернетики (квітень, 1997 р.);

-на семінарі відділу М.П. Корнейчука (Інститут математики НАН України, Київ, квітень, 1997 р.);

-на семінарі відділу В.Л. Рвачова (Інститут проблем машинобудування ім. А.М. Підгорного НАНУ, Харків, травень, 1997 р.):

-наукових конференціях професорсько-викладацького складу Української інженерно-педагогічної академії (секції "Вища математика" та "Прикладна математика") (Харків, 1994>1997рр.).

Публікації. За гемою дисертації опубліковано 11 робіт, в тому числі:

1 стаття в журналі “Доповіді “ НАН України, 3 статті у збірниках наукових праць інституту математики НАН України, 2 статті задепоновано в ДНТБ України, 1 матеріали конференції, 4 тез доповідей на конференціях. Структура та обсяг дисертації Дисертація включає вступ, чотири пави з висновками, список літературних джерел із 116 найменувань, 49 рисунків, 14 таблиць, усього 141 сторінка основного друкованого тексту.

ОСНОВНИЙ ЗМІСТ РОБОТИ.

РОЗДІЛ 1 “ Аналітичний огляд відомих методів відновлення функція з ізогсометрісю” присвячено огляду відомих методів ізогеометричної сплайн-ігггерпомції та апроксимації функцій однієї та двох змінних.

У розділу 2 “Інтерполяція функцій однієї змінної із збереженням ізогеометрВ* запропоновано методи .явної побудови сплайнів однієї змінної, основаних на використанні окремого випадку формули О.М. Литвина представлення залишку інтерполяційних формул Лагранжа та Ерміта. Зокрема, кош при інтерполюванні використовуються лише значення функції (без похідних), на кожному з відрізків [х,, дгм ] оператор сплайн-іягерполюваяня шукаємо у вигляді:

8„(х) = 8ы(Лх)=:

х-х

1+1

X,- -X

1+1

У і +

х-х,

*М-*і

Л+1+

; Лі<х <х(+],і = 1,#-1, (1)

У і ~ /Гхі)> і=ІМ, де деякі наближення /' (х), х ф^Хц.,].

а

Хай О > 0, <? еХ. Підставляючи в (1) ф(>н (£) = Дм+і,* ■ 4* >

СТаЛИХ сталі з умов

і = 1,М-1, будемо мати (Н-1)(0+1) довільних

і = \,М—1,к = 0,0. Вибираючи ці невідомі

$!и)(хі ~®) = ЗІ{)(хі + 0Л і= 2, А''- 1, ц- 1,0 (всього {М-2)<2 умов), отримаємо кусково-поліноміальну функцію степеня (0+2) , яка належатиме класові С(® [а,Ь] і буде мати г~ <2 довільних параметрів. Ці параметри пропонується знаходити із умови мінімуму деякого фунхціоналу. В роботі пропонуються такі критерії.

1- •Л(^)=}(^)2л->іииі

а

ДГ-1

2. ^2&г)= -о;]2

> тт

і=2

З деяких випадках інтерполяційних даних менше ніж точок, в яких відома лформація про наближувану функцію (наприклад, в деякій точці Хк може 5уги відомо, що функція зростає, спадає, опукла, вгнута, але самого гначешія ук серед експериментальних даних немає). В цьому випадку можна )озгпядагк такий критерій:

[{Бу)2<3х+Л\\у12 ->т'т, .

г У ■

гри умовах Аи >0('<0^) А2, > 0(< 0,), і.к е^/у, с^;

у = [yh >~>J(k f ;Уц, Л є vV=й,},

__ К

к = \, г;-невідомі ініерподвдііші дані; jjj*|2 = ^ УЇк >

k=\

,_Ум-Ук.

Ац =:Auy = wl- ■ — ; A* =xfc+1 -x*,* = l,iV-1; h

Аг* -&и(АцсУ);%-

Хай /fx) eKC2l-Ul]=:{f(x):f<M)(x) eCf-l;lJ,s= 0,1; /"(xj -кусково-неперервна на[-1,1], j/"fjcjj</Г}.

Зауваження 2.2. Якщо в формулі (1) q>/J+, (tj замінити деяким функціоналом ф U+1 (У = M,u+1 f/J = M,J+1 = const (у формулі (2) Q=r= 1, GH)), то

sNjjn (х) = ------ /fo+1; - ґ* - х,+1; • f(х,.;]+

" (2)

*«+і “*r

м,

U+1

(X-Xj-(X-X1+1,); X€[X,,XMJ.

Теорема 2.1. Хан Л: -непарне. Якщо в формулі (2) Мим знаходити з умов ЯігЬ-О) = $#(х,+ 0), і ~ 2,Л/ - 1,, де Л/;,.? знаходити за допомогою критерію 1, то М^у,, і = 1, ІУ - 1 , мають вигляд

N-2

N-1

^1,2 - . 2 f Аі/+1 ~ А и ) • й(>1» а( - X 7~’

М‘-'Ч!~/Г7

2Г-і/+ЇАи-Ди_,^Г-и

і-і h\

,=,V

*=2

■Л/и

,і = 2,^-1.

(3)

(4)

Для знаходження невідомих Ма+] у випадку парних або непарних функцій пропонуємо використати також наступник підхід.

Лема 2.1. Хай задана сітка Д: -1=х/<х2<...<х2£+і=хл/=1 і/(х)=/(-х) на [-1,1]. Якщо в формулі (2) знаходити з умови 8'К(х) еС[-\;\], тобто з умов 8'н(х1~а) = 8'и(хі + 0), і- 2,И -1, у вузлах та якщо

припустимо Мі,2 hi= Мц .і,ц Ам/, то ці значення Мц+и i~\,N-\> знаходяться за формулами

гг-г

МІЛ =

Ц.ІІС

Sf-l/fAv+i-ДиЛ

h,

Аналогічну лему сформульовано і дня непарних функцій.

В дисертації дна пар лях та непарних на [-1,1] функцій виведені достатні умови монотонності, опуклості, досліджено оцінку похибки отриманими лшайнгши. В цьому підрозділі знайдені точні оцінки для функцій

/(х) є \7І(І) = \г(х) €С2 (]),! = [0,і| ІГ"\\Л < 1).

8 У4+ІбЗі3 + 117іг -ьЗ& 4- 4І __________1______________

27 ] 2(іг+і+1/3?/г+і(і + 1)(2і+1) ~

=5зг=*»•*■ =т=8*-'№

оо

Георема 2.7. Введемо клас функцій \^Кпїїг^{і),

п=г

№

*Ж(/Ь \ї<х)\Ґ0(х) є С{1\ *=0,1,2,- г є іЛі);

’оді для залишку г([;х)=/(х)-з([;х) виконується нерівність

г(/;х)\^1)^Ей,\'Х-

І підрозділу 2.2 знайдено розв’язок такої задачі.

адача 1. Функція однієї змінної у = /(х), д: є/],/, = [а, і], задана воїми значеннями у, = / (х,), і ~ 1, п; а~х} <х2 <...<хп=Ь.

'рім того, про цю функцію відома також додаткова інформація такого игляду: в деяких точках х*к с /1( к~\,г, або на деяких підіїггервалах ак,рк} сІик = ї,г, відомо, що /(х) зростає (спадає) або Дх) опукла инута). Треба відновити Дх) з допомогою інтерполяційних сплайнів із рахуванням цій інформації.

дя роз’вязання задачі 1 використаємо інтерполяційні сплайни другого орядку, що запропоновано у підрозділу 2.1. Шукаємо наближення до ункції /(х) у вигляді Бп+Г(х) (2), де X - (дг1,х2,...,хл+г)- це впорядкований

зктор, що складено із векторів X - (хг, хг та X* = (г*, х* ).

евідомі Л/и+1, і — 1,п + г — \, знаходяться із умов:

1)5'+г^,.-0) = 5;і+г^,+0Л / = 2, я + г - 1; (б)

ІМІ

2) ./,&„)-* лш»; (7)

Щ,2

або

II. 1)Б'МГ (х, -0) = ^;+г (*, + ОЛ / = 2.Я + Г-1;

2)'7г(йп+г)-+тІП (8)

"у

при додаткових обмеженнях на невідомі значення функції /(хк). Ці обмеження можуть знаходитися з використанням початкових даних та задавшися дослідником в діалоговому режимі:

Ди > 0 (< Ч Л2>5 <0 (>0), ди = А^(АиГ). (9)

Серед х5,дгї+1 хоча б одне повинно збігатися з якимось (х*к), бо інакше така нерівність не буде містити додаткову інформацію про невідомі значення /(х*к). Пря такій постановці ми отримали задачу квадратичного програмування, що може бути розв’язана за допомогою будь-якого із збіжних глобальних методів квадратичного програмування, наприклад, методом комплексів. Враховуючи, що якісна інформація про наближувану функцію (інтервали зростання, опуклості тощо) задана наближено, то, в принципі, функціонали /2 треба замінити на функціонали

^ + Д]|Х|2, ^ + А|ї|2 відповідно, де І- параметр регуляргаації, що знаходиться за будь-яким відомим методом регуляргоації.

У підрозділі 2.3. розглядається загальний підхід до наближення функцій однієї змінної з допомогою сплайнів.

Хай на сітці А: а=хі<х2<...<Хи~Ь задано функцію у=/(х): ус=/(х^, і= І#. Побудуємо оператор Ь^Дх) із властивостями иЖх^/(хІ і=1,ії; Піч(х)=(Ін/(х))",хє(х„хм): ...,N-1,

<і>и+Лх)‘ Дезкі наближення/ (х), хє[хих1+]] з допомогою даних {у}.

Теорема 2.9. Оператор Іг/{уі}; {щ,і+і};х)~:8^х), що задається формулою (1) задовольняє властивості:

1 )Ых^М=у11 І=ЕЖ;

2)ІцДх)єС[а,Ь], \ґуІМєС[ХіЛ+)];

3)1ы/(х)еС1*[а,Ь], якщо <р(*и<М>;= м&+0), І=2,...,К-1; к=0,1,2,...;

при цьому <Ри+і(х)=( иЛх)) ~, хє[хьхі+]], /= І,ЛГ— 1; тобто

эр {Іціїх))~~щП Фі£+/Й), хфих1+!], і= 1,АГ -1; (10)

4) діш того, щоб зберігалася монотонність початкових даних на відрізку [*іД*+Л> треба щоб виконувалася така умова:

Наслідок 2.4. Замінюючи функції Фі,і+Кх) різними формулами наближення /’(х) отримаємо різні інтерполяційні оператори, які при властивостях (10) зберігатимуть інтервали, де$х) була опукла (вгнута).

В цьому підрозділі наведено приклади, в яких замінювали $^н(х) різними кусково-лінійними функціями, тобто отримували кубічні сплайни. Знайдено з ціпки похибки отриманими сплатами та проаналізовано результати наближення.

З розділу 3 побудовані формули поліноміальної та раціональної іятерлілації !щя областей складної форми, що необхідні для створення математичної «оделі місцевості. Вп. 3.1. розділу 3 “Інтерліпація функцій двох змінних” таведеяо формули іятердіїтції функції на трикутниках з криволінійною іпотепузою. На даний час автору дисертації відомі роботи, в яких сояструюються й досліджуються оператори поліноміальної іптерлінзції на грикутниках з криволінійною гіпогепузоіо. Але в цих роботах відсутні іагальні формули для залишкового члена, а також для його оцінки похибки

і різних нормах. Частковому розв'язанню цих задач і присвячено п.3.2. В рюму підрозділі вперше для деяких випадків знайдено інтегральне гредставлепня залишкового члена наближення /(х,у) іптерлінантамл /т(х,у), цо інтерлінують Лх,у) є С( Т) на д7, де Г - границя трикутника з ртволіншною гіпотенузою, а також досліджено ного оцінку у нормах деяких підпросторів.

лалогічні результати отримані для Н(і)=і, у =іі(х) - частина параболи. В .3.3 розглянуто п’ять перетинних прямих Гк (£=1,5). Побудовано

ДіД 2

2

з р'

2(р'+1)(р'+2)(р' + 3)(р'+4)

- 22

Д 1 А 2

•ч/яТ ‘

оператори лоліяоміальної иггсрліпаціі Ь /(х,у) на цих прямих для п'ятикутників спеціального вигляду з однією криволінійною стороною для всіх 4 випадків. В п. 3.4. побудовано оператор інтерлінації, що для відновленій: функції використовує лише інформацію на лініях-границях області. В п. 3.5 цей алгоритм узагальнено на випадок довільної кусково-опуклої функції. Нехай маємо багатокутну область О, що утворена перетином М ліній

Г;: УГ; , де Г;: ^(х,у)-^М=-0,

і=і Vі+#(*)

І г_ = 1, і = 1, М, (х)<0.хе [хрхм ],і = 1, М - 1.

В п. 3.5 побудовано оператор інтерлінації для цієї області П:

1и{{}і.(х’У)}'х<У) = Л,кк(х.У)/к (х,у), к=\

Де

а*(*-у)=П®»М /еП

т~ 1 і у=1 гк~\

гг&к / mїj

з властивостями

£и/(х> у)І ^=0= Л* (X, у)\ ^=0, к = ї,М. (11)

У випадку, якщо А(х,у)\Тк =/(х,у)\Тк • Л’|гк = /|гк. то

І'м{{/к(х>у)};х,у)= Іи/(х,у) і цей оператор матиме властивості

/|Гк = /)гк > к -\,М. В даному розділу пропонується алгоритм вибору

/к (х> У) (к=\, М), які мають властивості (11) і, крім того, використовують інформацію про сліди; функції/ тільки в точках границі ЗО.

В п. 3.6. описано кусково-іюліношальяу цггсрлшацію функцій двох змінних ддя областей складної форми. Розроблено алгоритм автоматичного розбиття області на підобласті, аиториш автоматичної типізації елементів та автоматичного визначення підобласті а = 1,2, в яку потрапила т.М(х,у). В результаті такого розбиття отримаємо прямокутні лунки

xk,xk+jx [yjyj+i] [k = l,Nx-\; j = \,Nz-l), де -кількість вертикальних іній області Єї, N 2 - кількість горизонтальних ліній області Q. Кожний із [их прямокутників, в свою чергу, містить один або два елемента 15 типів рьох видів (прямокутники, трикутники, п'ятикутники). Тим самим лгоріпм відновлення функції декількох змінних має локальні властивості, іо значно скорочує час обчислення та більш повно дозволяє икористовуваги початкову інформацію, що важливо при відновленні шерхонь із збереженням ізогеометрії.

Іп.4.1,4.2 розділу 4 “Згладжуюча інтерполяція функцій двох змінних з «користанням інтерліпації” запропоновано алгоритм відновлення функції pox змінних з допомогою бшшйних сішайнів з використанням інтерлінацп регупяргоацією. В п. 4.3. метод, викладений у п. 2.1., узагальнюється на ипадок двох змінних, тобто будується біквадрашчний інтерполяційний плайн Sp(!>(x,y). А в п.4.4. запропоновано метод побудови біквадратичного ітерпомцшного сплайна Sp(i)(x,y) за вказаними інгерпопйційними даними а допомогою іятерлінації функцій. В п. 4.5. запропоновано алгоритми обудови поверхонь із збереженням ізогеометрії з використанням ггерлінації з регуляргоацією за даними на лініях рівня.

[ижче наведемо один із алгоритмів, що запропоновано в цьому підрозділі, [ей алгоритм умовно можна розбити на такі кроки:

Крок 1. Розбиття області наближення на елементи (прямокутники, рямокупшки з однією криволінійною стороною, прямокутні трикутники з риволіншною гіпотенузою, п'ятикутники з однією криволінійною гороною) (див. підрозділ 3.6).

Крок 2. Побудова з допомогою інгершнації функції формул зближеного представлення функцій в кожному з елементів з ізогеометрією.

Крок 3. Формування обмежень, пов’язаних з монотонністю і пуклоспо поверхні на даній системі ліній (аналогічно (9)).

Крок 4. Знаходження невідомих значень функції на лйгіх іятерлінації з мови мінімуму функціонала Для знаходження z-F(x,y) гасористовуємо біквадратнчні сшіайни з інтерліпаїцєю функції у вигляді гякого оператора Q(F;х,у).

(z)-a0jjD2(x,y )dxdy + «і JJ (7П|2 dxdy + аг jj(v dxdy +

і2 i2 i2 ^

k= 1 (=1 /=1 j=1 p^ _

тіп

“р.

при обмеженнях

> 0(< О), А[у>0(<0), к =1,2, (13)

д0> _ р(хм,1> уі,]р(хі,і’Уи) д(1> _ лси /леи р).

- г _г > аг,у -Ац, »ли;Г ^

лЖ,у хі,}

А^, А% знаходяться аналогічно відносно змінної у, де а0 + а.і + а2 + а3 + а4 = 1, а, £ 0,/ = 0,4,

^ = х,+и -**. *==ЇЖ; - *,,>

і = ЩгЛ і=ЇЖ-

Л/(^|1,і' = 1,Лг1-1,Л = 1,Лг2; Л/^+17І=1,і^2"1 // = 1,^,знаходиться зумов

(б)-(7) або (6),(8). і- параметри регудяризації.

При знаходження мінімуму функціонала (12) при обмеженнях (13) за допомогою методів квадратичного програмування, ми знайдемо невідомі значення функції в вузлах прямокутної сітки.

Крок 5. Візуалізація отриманих результатів. Знаходження значення функції г=Р(х,у) в довільній точці області О за відповідними формулами ілтерлінаціі (наприклад, за методами, що запропоновані в підрозділах 4.3, 4.4) і побудова поверхні за отриманою таблицею даних. Таким чином, поставлена задача про знаходження наближення із збереженням ізогеометрії може бути сформульована у вигляді типової задачі квадратичного програмування.

Оскільки рівняння ліній рівня нам невідомі, то криволінійні сторони можна наближено описувати, наприклад, параболами, або параметричними сплайнами. Таким чином створюється математична модель поверхні, яка точно враховує всі дані ліній рівня, які є на карті.

Наприкінці кожної глави зроблено висновки; в таблицях, а також в додатку до дисертації, наведено результати обчислювального експерименту, які підтверджують теоретичні результати отримані в дисертації

ВИСНОВКИ

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

Створено і досліджено загальний алгоритм явної побудови сгаїайиів цгіа змінної із збереженням ізогеомстрії (детально розглянуто параболічні . кубічні сплайпи).

Створено загальний алгоритм побудови біквадрагичннх сплайнів з [користанням і без використання інтерлінації, який не вимагає введення >даткової системи вузлів і не використовує яких-небудь граничних умов. Розроблено та реалізовано алгоритм згладжуючої інтерполяції функції юх змінних.

Розроблено методи побудови цифрових карт на основі інформації про тії рівня фуїшш (включаючи побудову явних формул інтерлінації на аницях опуклих областей, які складаються із частин відомих кривих) із ереженням ізогеометрії. На базі цих методів створена математична модель льєфу місцевості. Досліджено похибки наближення формули інтерлінації границі трикутника з криволінійною гіпотенузою в різних нормах. фактичні результати :

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

Проведено порівняння з відомими методами відновлення кривих та верхонь із збереженням ізогеометрії.

Створено пакет програм на мові Turbo Pascal 7.0, що реалізують тропоновані методи та алгоритми.

Запропоновані методи можуть використовуватися під час створення фрових карт, при прокладанні траси польоту літаючого об’єкту, що птгь на малій висоті з великою швидкіспо, використовуватися як тематичне забезпечення для графічних пакетів типу Graphika, Surfer, ithcad, тобто всюди, де треба ефективно відновлювати криві та поверхні набором експериментальних даних із збереженням ізогеометрії.

ПРАЦІ, ЩО ОПУБЛІКОВАНО ЗА ТЕМОЮ ДИСЕРТАЦІЇ. Кракова І.В., Литвин О.М. Новий метод відновлення функції однієї змінної із збереженням ізогеометрії// Доповіді НАН УкрлЗни-Київ, № б, 1996 ,-С. 36-41.

Крылова И.В., Литвин О.М. Построение семейства параболических :плайнов// В сб. научных трудов "Нелинейные краевые задачи

математической физики и их приложения", Киев, институт математики НАН Украины, 1995,- С.137-139.

3. Крикам ив., Литвин О.М Про побудову сплайнів двох змінних 5 використанням інтерлінації// В сб. научных трудов "Нелинейные краевые задачи математической физики и их приложения", Киев, ил статут математики НАН Украины, 1996,- С. 151-153.

4. Крикова І.В., Литвин О.М Інтерлінація на границі п’ятикутника з криволінійною стороною//Волинський математичний вісник, 1996.- Вил.

З,- С. 56-60.

5. Кракова И.Б.,Литвин О.Н. Приближение кривых сплайнами с сохранением формы. Обзор//Деп. в ДНТБ України 02.03.95 К® 588-Ук 95,- 54 с.

6. Кракова І.В., Литвин О.М. Метод побудови сімейства операторів параболічного сішайн-інгерполювання. Достатні умови опуклості, монотонності//Деп. в ДНТБ України 02.10.95 № 2225-Ук95.- 27 с.

7. Кракова І.В. Метод явної побудови інтерполяційних сплайнів парного стелена// Матеріали XVIII науково-методичної конференції.- Харків, УША, 22-23 березня 1995 р.- С.231-235.

8. Литвин О.М., Крикова І.В. Новий метод побудови цифрових карт для управління літаючим об’єктом, який летять на малій висоті з великою швидкістю// Тез. доп. на III міжнародній науково-технічній конференції “Контроль и управление в технических системах ”, Винница, 18-21 сент. 1995 г., ч.І,.- С. 36-37.

9. Литвин О.М., Крикова І.В. Нелінійна інтерлінація на границі трикутника

з однією криволінійною стороною// Тези доповіді на V міжнародній конференції ім. академіка М. Кравчука, Київ, Научний технічний Університет України, 16-18 травня,1996 р.- С.246.

10. Литвин О.М, Крикова [.В. Побудова сплайнів хирного степеня із збереженням ізогеометрії // Тез. доп. на Всеукр. науковій конференції ‘Розробка та застосування математичних методів в науково-технічних дослідженнях” 5-7 жовтня 1995р.-Львів,- С. 111-113.

11. Крикова ІВ., Литяин О.М Метод побудови математичної моделі поверхні за даними ліній рівня із збереженням ізогеометрії // Тез. доп. на Всеукр. науковій конференції “Застосування обчислювальної техніки, математичного моделювання та математичних методів у наукових дослідженнях” вересень 1997 р.-Львів - С. 48-51.

Крикова І.В. Отшс поверхонь па основі експериментальних даних з допомогою Ііггерлііішаї функцій та ного застосузшпш.

Дисертацією є рукопис, що представлено на здобуття наукового ступеня кандидата фізико-математичлнх наук за спеціальністю 01.01.07-обчислюваяьна математика Інститут кібернетики НАН України імені В.М. Глушкова, Київ, 1998 р.

У дисертації запропоновані методи відновлення функцій однієї та двох змінних із збереженням ізогеометрії, а також методів відновлення функції двох змінних за допомогою формул ііггерлінації. Запропоновано загальний підхід до оцінки наближення одержаними сішгйн-штерполгнтами та сгоюйн-іктершінантами. Наведено результати чисельного розв’язання тестових прикладів.

Ключові слова: інтерлінація, могеометрія, відновлеппя функцій, спяайн-інгерполяція, ошайн-інтерлінашя, регуляргояціа, квадратичне програмування, математична модель поверхні Земні.

Крыкова И.В. Описание поверхностей на основе экспериментальных данных с помощью интерлинации функций и его применение.

Диссертация является рукописью, представленной на соискание ученой степени кандидата физико-математических наук по специальности 01.01.07- вычислительная математика Институт кибернетики НАН Украины имени В.Н. Глушкова, Киев, 1998 г,

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

Клюнете слова: иптерлинаши, язогеометриа, восстановление функций, сплайн-интерполяция, сплайя-интерлнпация, регуляризация, квадратичное программирование, математическая модель поверхности Земли.

Krikova I.V. Description of surface which is based on experimental data with interlinstion function and its applications.

The dissertation is a manuscript presented on competition for academic degree of physical-mathemalics sciences candidate by speciality 01.01.07-

computer mathematics. Institute for cybernetics of Ukrcnian Academy » Sciences named by B.N. Glyshkov, Kiev, 1998 .

In dissertation methods of reconstruction of function of one and tw< variables by interpolation data with shape-preserving (izogeometry) initial da and also methods reconstruciion function bivariste with formula interlinatic (the blending function interpolation) are proposed. The general approach f< estimate error approximation by bioperator of spline-interpolation and splirn interlinalion are suggested. Calculation results of tests are given.

Key words: interim ation (the blending-function interpolation

izogeometry, reconstruction functions, spline-interpolation, spline-ixiterlinatioi regularization, quadratic programming, mathematical model of the Earth.

Відповідальний за випуск к.т.н. Топоров В.Г. Підписано до друку 13.02.98г.

Формат 60 х 90 1/16.Папір офсет.№1.Ум. Друк. Арк.1. Тираж 100 эк. Зам. №97.

Надруковано в AT «КіПі» 310003 м. Харків, гш. Конституції, 26.