Й - Стор 7
Чисельні методи аналізу
Мал. 2.7. Інтерполяція поліномом 10-го ступеня на прикладі Рунге
Але в загальному випадку при інтерполюванні алгебри навіть нескінченно гладких функцій похибка все-таки може не сходитися до нуля. Очевидно, найбільш відомий приклад такого роду навів німецький математик К. Рунге. У прикладі Рунґе функція
інтерполюється алгебраїчними поліномами на інтервалі [-1, 1] з рівномірним розташуванням вузлів інтерполяції x i = -1 + 2i/n, i = 0, 1, 2, . . . , n. Виявляється, що тоді
P n (x) інтерполяційний поліном n-ого ступеня. При цьому зі зростанням n поблизу кінці інтервалу інтерполування [−1, 1] у поліномів P n (x)
виникають сильні осциляції, розмах яких прагне нескінченності (див. рис. 2.7). Виходить, що хоча у вузлах інтерполяції значення функції Υ(x) збігаються зі значеннями інтерполяційного полінома, між цими вузлами P n(x) і Υ(x) можуть відрізнятися.
завгодно сильно, навіть попри плавний (нескінченно гладкий) характер зміни функції Υ(x).
Цікаво, що на інтервалі [−κ, κ] , де κ ≈ 0.726 розглядається інтерполяційний процес рівномірно сходить до Υ (x) (див. [49]).
2.1. Інтерполяція функцій
Крім того, корисно відзначити, що функція Υ (x) має похідні всіх порядків для будь-якого речового аргументу x , але в кінці інтервалу інтерполування [−1, 1] ці похідні вже не задовольняють
няють умові (2.32). Таким чином, незважаючи на простий вигляд, функція Υ(x) з прикладу Рунґе своєю поведінкою надто несхожа на
поліноми, похідні від яких ростуть помірно і, починаючи з деякого порядку,зникають. Ці цікаві питання ставляться до теорії функцій.
На закінчення теми наведемо два важливі теоретичні результати
про збіжність інтерполяційних процесів для безперервних функцій.
Теорема Фабер. Не існує нескінченної трикутної мат-
рици вузлів із заданого інтервалу, такий, що відповідний їй алгебраїчний інтерполяційний процес сходився б рівномірно для будь-якої безперервної функції на цьому інтервалі.
Зокрема, навіть для інтерполяційного процесу по вузлах поліномів Чебишева, розглянутим у §2.1е і в певному сенсі найкращим для алгебраїчної інтерполяції, існують приклади безперервних функцій, для яких цей процес алгебри розповсюджується. Подробиці можна знайти у [29].
З іншого боку, справедлива
Теорема Марцінкевича. Для будь-якої безперервної на заданому інтервалі функції f знайдеться така нескінченна трикутна матри-
ця вузлів цього інтервалу, що відповідний їй алгебраїчний інтерполяційний процес для функції f сходиться рівномірно.
Підтвердження цих теорем зацікавлений читач може визначити, наприклад, в [9, 10, 45].
Наведені вище результати здавалося б здаються взаємовиключними, але де вони перебувають у прямому суперечності друг до друга. Висновок з них полягає, перш за все, у тому, що безліч безперервних функцій є занадто широким, щоб для нього існував один (або навіть кілька) інтерполяційних процесів, що забезпечують рівномірну збіжність для всіх можливих ситуацій. З іншого боку, алгебраїчні поліноми, незважаючи на певні зручності роботи з ними, виявляються надто примхливим інструментом інтерполювання досить загальних безперервних функцій,
2. Чисельні методианалізу
так що нам потрібно перейматися розвитком більш гнучких інструментів інтерполяції. Цьому будуть присвячені наступні параграфи.
2.2а Елементи теорії
Нехай заданий інтервал [a, b] розбитий на підінтервали [x i -1, x i], i = 1, 2, . . . , n , отже a = x 0 і x n = b . Сплайн на [a, b] називається
функція, яка разом зі своїми похідними аж до деякого порядку безперервна на всьому інтервалі [a, b] і на кожному подинтервалі [x i −1 , x i ] є деяким поліномом. Максимальний на всьому інтервалі [a, b] ступінь поліномів, що задають сплайн, називається
ступенем сплайну. Різниця між ступенем сплайну і найвищим порядком його похідної, яка безперервна на [a, b] називається дефектом сплайну. Нарешті точки x i , i = 0, 1, . . . , n називають вузлами
Чому саме кускові поліноми? До ідеї запровадження можна дійти, наприклад, з допомогою наступних неформальних мотивацій. Для похідних високих порядків необхідні потрібні значення можна призначити, наприклад, за допомогою кусково-постійної інтерполяції, а потім добиться потрібної гладкості за допомогою послідовного застосування декількох операцій інтегрування.
Мал. 2.8. Шматково-постійна інтерполяція функції.
Сплайни знаходять широкі застосування в математиці та можуть використовуватись для різних цілей. Якщо сплайн застосовується для ре-
ня задачі інтерполяції, то він називається інтерполяційним. Інакше кажучи, интерполяционный сплайн це сплайн, який у заданих точках x˜ i , i = 0, 1 , . . . , m , вузли інтерполяції необхідні значення y i , і ці вузли інтерполяції, взагалі кажучи, можуть не збігатися з вузлами сплайну x i , i = 0, 1, . . . , n.
Термін «сплайн» є вдалим запозиченням з англійської мови 4 ,де слово ?spline¿ означає гнучку (зазвичай сталеву) чи-
нейку, яку, згинаючи, використовували креслення для проведення гладкої лінії між фіксованими даними точками. У середині XX століття цей термін увійшов до математики і перекочував на багато мов світу.
Таким чином, сплайни дефекту нуль це функції, що задаються на всьому інтервалі [a, b] однією поліноміальною формулою, а термін
«дефект» дуже точно висловлює те, скільки сплайну «не вистачає» до повноцінного полінома. З іншого боку, саме наявність дефекту забезпечує сплайну більшу гнучкість у порівнянні з поліномами і робить сплайни в деяких ситуаціях зручнішим інструментом наближення та інтерполювання функцій. Чим більший дефект сплайну, тим більше він відрізняється від полінома і тим специфічніші його властивості. Але дуже великий недолік призводить до значного зниження загальної гладкості сплайну. У значній кількості програм сплайнів цілком достатнім виявляються сплайни з мінімально можливим дефектом 1, і тільки такі сплайни ми розглядатимемо далі в нашій книзі.
Найпростіший "справжній" сплайн має дефект 1 і ступінь 1, будучи просто безперервно склеєним у вузлах x i, i = 1, 2, . . . , n-1. Іншими
словами, це шматково-лінійна функція, що має незважаючи на свою простоту багаті програми в математиці. 5 Сплайни другого ступеня
часто називають параболічними сплайнами.
Нехай є інтерполяційний сплайн ступеня d, вузли якого x 0 x 1 . . . , x n збігаються з вузлами інтерполювання. Цей сплайн повністю визначається n(d + 1) значеннями коефіцієнтів поліномів, що задають його на n підінтервалах [x i -1, x i], i = 1, 2,. . . , n. У те
ж час, у разі дефекту 1 є
4 Приклад невдалого запозичення термін¾вейвлет¿ для позначення
функцій-сплесків, що суперечить фонетичному ладу української мови. 5 Пригадаємо, наприклад, «ламані Ейлера», які застосовуються для доказу-
ності існування розв'язання задачі Коші для звичайних диференціальних рівнянь.