Реферати українською » Математика » Сплайни, фінітних функції


Реферат Сплайни, фінітних функції


>Реферат:

«>Сплайни.Финитние функції. Основні поняття, призначення. Усплайни Шенберга»


Запровадження

Функції, як ті, що тепер називаютьсплайнами були відомі математикам давно, починаючи як ізЭйлера, та їх інтенсивне вивчення почалося, фактично, лише у середині ХХ століття. У 1946 року ІсаакШенберг запустив у вжиток цей термін як позначення класуполиномиальнихсплайнов. До 1960 роківсплайни були переважно інструментом теоретичних досліджень, часто з'являлися у ролі рішень різних екстремальних і варіаційних завдань, особливо у теорії наближень.

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


1.Сплайни

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

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

>Сплайни мають численні застосування як і математичної теорії, і у різноманітних обчислювальних додатках. Зокрема,сплайни двох змінних інтенсивно йдуть на завдання поверхонь у різних системах комп'ютерного моделювання.

 

1.1 Криві Безьє

КривіБезье чи КривіБернштейна-Безье розробив 60-ті роки ХХ століття незалежно друг від друга П'єром Безьє і Полем деКастельжо.

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

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

Визначення

Крива Безьє –параметрическая крива, що задається вираженням:

                                      (1.1)

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

                                                   (1.2)

,                                                                 (1.3)

де n – ступіньполинома, і – порядковий номер опорною вершини

1.2 Види кривих Безьє:

1. Лінійні криві

При n = 1 крива є відрізок прямий лінії, опорні точкиP0 іP1 визначають його початок і поклала край. Крива ставиться рівнянням:

                                     (1.4)

2.Квадратичние криві

>Квадратичная крива Безьє (n = 2) ставиться3-мя опорними точками:P0,P1 іP2:

        (1.5)

>Квадратичние криві Безьє у складісплайнов йдуть на описи форми символів в шрифтахTrueType й уSWF файлах.

3.Кубические криві

У параметричної формі кубічна крива Безьє (n = 3) описується наступним рівнянням:

 (1.6)

Чотири опорні точкиP0,P1,P2 іP3, задані в2-х чи3-мерном просторі визначають форму кривою.

Лінія бере початок з точкиP0 прямуючи доP1 і закінчується точціP3 підходячи до неї з бокуP2. Тобто крива не проходить через точкиP1 іP2, їх використовують для вказівки її напрями. Довжина відрізка міжP0 іP1 визначає, як швидко криваповернет доP3.

Малюнок 1Кубическая крива Безьє

У матричної формі кубічна крива Безьє записується так:


,                                          (1.7)

де називається базисної матрицею Безьє:

                                                   (1.8)

У середовищі сучасних графічних системах, як-отPostScript,Metafont іGIMP до поданнякриволинейних форм використовуютьсясплайни Безьє, що складаються з кубічних кривих.

1.3 Побудова кривих Безьє

1. Лінійні криві

>Параметрt до функцій, яка описує лінійний випадок кривою Безьє, визначає саме з відривом відP0 доP1 перебуваєB(t). Наприклад, приt = 0,25 значення функціїB(t) відповідає чверті відстані між точкамиP0 іP1.Параметрt змінюється від 0 до 1, аB(t) описує відрізок прямий між точкамиP0 іP1.

Малюнок 2 Побудова лінійної кривою Безьє


2.Квадратичние криві

Для побудовиквадратичних кривих Безьє потрібно виділення двох проміжних точокQ0 іQ1 з умови щоб параметрt змінювався від 0 до 1:

КрапкаQ0 змінюється відP0 доP1 і описує лінійну криву Безьє.

КрапкаQ1 змінюється відP1 доP2 і описує лінійну криву Безьє.

Крапка B змінюється відQ0 доQ1 і описуєквадратичную криву Безьє.

Малюнок 3 Побудоваквадратичной кривою Безьє

3. Криві вищих ступенів

Для побудови кривих вищих порядків відповідно потрібне і більше проміжних точок. Для кубічної кривою це проміжні точкиQ0,Q1 іQ2, описують лінійні криві, і навіть точкиR0 іR1, які описуютьквадратичние криві: простіше рівнянняp0q0/p0q1=q1p1/p1p2=bq0/q1q0

Малюнок 4 Побудова кубічної кривою Безьє


Для кривих четвертої мірою цей будуть точкиQ0,Q1,Q2 іQ3, описують лінійні криві,R0,R1 іR2, які описуютьквадратичние криві, і навіть точкиS0 іS1, описують кубічні криві Безьє:

Малюнок 5 Побудова кривою Безьє4-ой ступеня

1.4 Застосування у комп'ютерній графіці

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

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

1.5 Перетворенняквадратичних кривих Безьє в кубічні

>Квадратичная крива Безьє з координатами перетворюється на кубічну криву Безьє з координатами:

 


2.Финитние функції

>Финитной називається функція , певна всім , але яка від нуля тільки деякою кінцевої області , званої кінцевим носієм:

                                                                   (2.1)

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

                            (2.2)

Бажано, аби тільки для , суміжних з .

>Подобласти дістали назву кінцеві елементи.

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

Зазначимо переваги такого вибору базису:

а) зважаючи на те, що вибираються значно меншими і навіть скалярні твори

   (2.3)


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

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

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

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

.                                                                   (2.4)

На всі ці запитання частково відповідає теоріяСтренга-Фикса.

2.2 Теорія апроксимаціїфинитними функціямиСтренга-Фикса

Викладемо основні ідеї цієї теорії для функцій однієї перемінної до регулярних кінцевими елементами.

Область покриваємо рівномірної сіткою


, [>p] – ціла частинаp.

Кінцеві елементи виберемо як відтинки довжиною з центром у точці : . Якщо , суміжні елементи не перетинаються та його довжина дорівнює : якщо , то довжина перетину дорівнює , довжина дорівнює ; при – довжина перетину , довжина дорівнює . Зауважимо, що таке покриття повністю задовольняє умовам (2.2). Усі базисніфинитние функції носіями виберемо однаковою форми як зрушення однієї «стандартної»финитной функції :

;                   (2.5)

Якщо «стандартна» функція нормована до одиниці, що його зрушення записуються як

                 (2.6)

ТеоремуСтренга-Фикса (одне із варіантів)

Припустимо, що . І тут для існує перетворення Фур'є:

пряме зворотне

Припустимо, що з перетворення Фур'є стандартноїфинитной функції виконано умова


 і за (2.7)

(тобто. в точках має нулі і кратності).

Тоді є такі , що з

.

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

Наявність такої центральної теореми, і навіть ще низки доведенихСтренгом-Фиксом теорем, зокрема й існуванні функцій, які відповідають умовам (2.7), дає алгоритм для побудови базисних фінітних функцій, які мають необхіднимиаппроксимационними властивостями.


3.B-сплайни Шенберга

У обчислювальної математиціB-сплайном називаютьсплайн-функцию, має найменший носій для заданої ступеня, порядку гладкості і розбивки області визначення. Фундаментальна теорема встановлює, будь-якасплайн-функция для заданої ступеня, гладкості й області визначення то, можливо представлена як лінійна комбінаціяB-сплайнов тієї мірі і гладкості тій самій області визначення. [1] ТермінB-сплайн був введений І.Шенбергом і є скороченням від словосполучення «базиснийсплайн». [2]B-сплайни може бути враховано з допомогою алгоритму де Бору, який володіє сталістю.

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

Коли вузли рівновіддалені друг від друга, кажуть, щоB-сплайн є однорідним, інакше її називають неоднорідним.

Коли кількість вузлів збігається з ступенемсплайна,B-сплайн вироджується в криву Безьє. Форма базисної функції визначається розташуванням вузлів.Масштабирование чи паралельний перенесення базисного вектора важить на базисну функцію.

>Сплайн міститься у опуклої оболонці його опорних точок.

>Базиснийсплайн ступеня n: .

не звертається до нуль лише з проміжку [>ti,ti+n+1], тобто:

.                                   (3.1)

Інакше кажучи, зміна одній опорній точки впливає лише з локальне поведінка кривою, а чи не на глобальне, як у кривих Безьє.

>Базисная функція може бути отримана зполинома Бернштейна

>В-сплайн і пояснюються деякі найчастіше використовувані базиси

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

Шенберг запропонував один цікавий клас функцій, які відповідають умові (2.7). Функцію називаютьВ-сплайном (Шенберга) ступеня , коли його перетворення Фур'є має вигляд

.                                                            (3.2)

Як кажуть, функція (6.8) задовольняє всім умовам (6.7).

>Базис з сходинок

Досить просто показати, що з

 


                                                                     (3.3)

І тут базис є набір зрушень (2.5) стандартної сходинки (3.3), а функція є розривну ступінчасту функцію ().Аппроксимация за нормою має порядок . Такий базис може бути обраний як друге базису під час використання методуГалеркина-Петрова.

>Базис з кришок

РозглянемоВ-сплайн ступеня : . На цьому співвідношення слід, що як згортка функцій =

Після нескладних перетворень отримуємо:

 


                                                               (3.4)

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

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

>В-сплайн ступеня  єкусочно-полиноминальний кубічнийсплайн, якийсверткой:

.

                    (3.5)

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


Література

1. Роджерс Д., Адамс Дж. Математичні основи машинної графіки. – М.: Світ, 2001.

2. Корнійчук, Н.П., Бабенко, В.Ф.,Лигун, А.А. Екстремальні властивостіполиномов ісплайнов / відп. ред. А.І. Степанець; ред. С.Д.Кошис,О.Д. Мельник, НАН України,Ин-тматематики.–К.:Наукова думка, 1992.–304 з.

3. Роджерс Д., Адамс Дж. Математичні основи машинної графіки. – М.: Світ, 2001.

4. Лівшиць Євген Давидович. БезперервніE-виборки задля наближенняполиномиальними і раціональнимисплайнами: Діс. …канд.физ.-мат. наук: 01.01.01 Москва, 2005 90 з.

5.Алберг Дж.,Нильсон Еге., Волш Дж. – Теоріясплайнов і його докладання

6. ВинниченкоЛ.Ф.Экспоненциальниегистосплайни: передумови запровадження //Publishing houseEducation and Sciences.r.o., конференція «Європейська наука ХХІ сторіччя», 2009

7. Корнійчук, Н.П., Бабенко, В.Ф.,Лигун, А.А. Екстремальні властивостіполиномов ісплайнов / відп. ред. А.І. Степанець; ред. С.Д.Кошис,О.Д. Мельник, НАН України,Ин-т математики. – До.:Наукова думка, 1992.–304 з.


Схожі реферати:

Навігація