4. Інтерполювання функцій
Нехай дана система лінійних рівнянь (1). Зведемо систему (1) до системи (2). Задамо деякі початкові наближення невідомихx1(0) = β1,x2 (0) = β2, :,xn(0) = βn. Підставимо їх у праві частини системи та обчислимо нові наближення, у своїй використовуватимемо наближення до рішень, знайдені і під час поточної ітерації, тобто.
Аналогічно проводимо другу ітерацію тощо. Процес уточнення кореня закінчується, коли виконується умоваk= 1, :,n, деE- допустима похибка обчислення.Зауваження:при вирішенні системи лінійних рівнянь методом Зейделя ітераційний процес буде схожим лише у випадку, якщо для кожного рівняння виконується умоваi= 1, :,n, однак у суму не входить доданокaij з рівнимиiіj. При цьому хоча б одна нерівність має виконуватися суворо. Ця умова є достатньою умовою збіжності методу Зейделя.
Метод виключення Гауса
(Розглядається рішення систем рівнянь даним методом і обчислень зворотної матриці за допомогою методу Гаусса).
Метод виключення Гауса відноситься до прямих методів розв'язання систем лінійних рівнянь. Ідея цього методу полягає в тому, щоб вихідну систему лінійних рівнянь (1) з довільною матрицеюАзвести деякими еквівалентними перетвореннями до системи виду (2), де - трикутна матриця. Потім з останнього рівняння системи (2) знаходитьсяxn, з попереднього -xn-1 і т.д.Обчислення зворотної матриці за допомогою методу Гауса:Нехайxi - i-ий стовпець шуканої зворотної матриці,ei - i-ий стовпець одиничної матриці. Т.к.A·A-1 = E, то приi= 1, 2, :,n. Завдання знаходження зворотногоматриці зводиться до завдання розв'язанняnсистемnлінійних рівнянь з однією і тією ж матрицеюA, але з різними правими частинами.
4. Інтерполювання функцій
Основні питання, що розглядаються на лекції:
Основні поняття інтерполяції, завдання, що призводить до наближення функції, геометричний зміст інтерполяції
Інтерполяційний багаточлен Лагранжа
Оцінка похибки інтерполяційної формули Лагранжа
Інтерполяційні формули Ньютона
Перша інтерполяційна формула Ньютона
Друга інтерполяційна формула Ньютона
Оцінка похибок першої та другої інтерполяційних формул Ньютона
Основні поняття інтерполяції, завдання, що веде до наближення функції
Інтерполяція (від латів. interpolation - зміна, переробка) - в математиці та статистиці, відшукання проміжних значень величини за деякими відомими її значенням [Рад. енциклопедичний словник]. Завдання, що веде до наближення функції, полягає в наступному. Відомі значення функціїf (x)у точкахx1,x2, :,xn; потрібно відновити її значення за іншихх. Інтерполяційний поліном, що передає властивості функціїf(x)будуватимемо у вигляді: Pn(x) = c1φ1(x) + c2φ2(x) + : + cnφn(x), де φ1(x), φ2 (x), :, φn(x) - клас лінійно-незалежних функцій, при цьому Pn(xi) = f(xi), i = 1, 2, :, n. Отже, Pn(x) f(x). Точки x1, x2, :, xn називаються вузлами інтерполяції.
Інтерполяційний багаточлен Лагранжа
Нехай відомі значення функції f (x) у (n+1) точці x0, x1, :, xn. Тоді багаточлен Лагранжа, що передає властивості функції f(x), можна записати так:
Схема Ейткена пропонує більш зручну формузнаходження полінома Лагранжа. Основна ідея цього методу полягає в наступному. На першому етапі обчислюються багаточлени L0,1(x), L1,2(x), : Ln-1,n(x), побудовані на кожній парі сусідніх вузлів 0,1; 1,2; :; n-1,n відповідно. При цьому , , :,. Таким чином, багаточлени, побудовані на парі сусідніх вузлів, обчислюються за формулами: . Потім основі цих многочленів обчислюються многочлены, побудовані на трійках сусідніх вузлів: . І т.д. доки вийде один многочлен, побудований усім вузлах інтерполяції: . Отриманий многочленL0, 1, . n(x)Ln(x).
Оцінка похибки інтерполяційної формули Лагранжа
Маємоyj= f (xj), Ln(x). БагаточленLn(x)побудований так, щоLn(xj) = f(xj). Обчислюючи похибкуRn(x)таким чином:Rn(x) = f (x) - Ln(x), можна отримати таку формулу для оцінки похибки інтерполяційної формули Лагранжа:
Інтерполяційні формули Ньютона
Ступінь полінома має перевищуватиn.
ФормулаPn(x)для першої інтерполяційної формули Ньютона має вигляд: , деq = ( x - x0)/h. Перша інтерполяційна формула Ньютона застосовується тоді, коли x знаходиться спочатку таблиці. Тоді якx0слід брати найближче зліва до заданогоxтабличного значення.
Друга інтерполяційна формула НьютонаКоли значення аргументу знаходиться ближче до кінця відрізкаінтерполяції, застосовувати першу інтерполяційну формулу стає невигідно. Для цього застосовується друга інтерполяційна формула Ньютона: деq = (x - xn) / h. Тут якxnслід брати найближче праворуч до заданогоxтабличного значення.
Оцінка похибок першої та другої інтерполяційних формул Ньютона
Використовуючи підстановкиq = (x - x0) / hіq = (x - xn) / hі замінюючи відповідним чином вираз для Пn+1(x)у формулі оцінки похибки інтерполяційної формули Лагранжа, отримаємо формули для оцінки похибки інтерполювання за першою і другий інтерполяційної формули Ньютона відповідно: , .
Завдання зворотного інтерполювання ось у чому. Якщо значення yi> у таблиці впорядковані за зростанням або спаданням, то функціяy = f(x)монотонна на [x0, xn], і цю таблицю можна інтерпретувати як завдання дискретного образу функціїx = φ(y), зворотної по відношенню до функціїy = f(x). Для цієї зворотної функції також може бути поставлена задача інтерполювання: знайти значенняx*за вказаним значеннямy*.
Нехай xi> рівновіддалені вузли, розташовані на відстаніhодин від одного і побудований один з поліномів Ньютона (для певності - перший): . При розв'язанні задачі зворотного інтерполювання за допомогою цього полінома в його лівій частині виникає відоме значенняy*, а сама формула стає рівнянням алгебри щодох. Якщо числа yi> упорядковані за зростанням або спаданням, то це рівняння має єдине рішення на [x0, xn]. Його рішення слід шукати будь-яким ізвивчених раніше методів на вирішення нелінійних рівнянь. У цьому випадку найбільш природним способом для вирішення рівняння є метод простої ітерації. Підставимоy = y*у вищенаведену формулу і перетворимо рівність, що вийшла, до виду: . Це рівняння має структуруx = ? (x), тобто. на вигляд придатне для застосування методу простої ітерації. Як початкове наближення можна взяти значенняx(0)= xi, найближче до шуканогох*. Маючи початкове наближенняx(0), будуємо ітераційний процес для вирішення отриманого рівняння доки не буде досягнуто заданої точності:
При велику кількість вузлів інтерполяції сильно зростає ступінь інтерполяційних багаточленів, що робить їх незручними для обчислень. У цьому випадку зручно користуватися особливим видом шматково-поліноміальної інтерполяції - інтерполяції сплайн. Суть цього підходу ось у чому.
Визначення. Нехай відрізок [a, b] розбитий крапками наnчасткових відрізків [xi, xi+1],i = 0, 1, :, n-1. Сплайном порядкуmназивається функціяSm(x), що має такі властивості: 1) ФункціяSm(x)безперервна на відрізку [a, b] разом зі своїми похідними до деякого порядкур. 2) На кожному відрізку [xi, xi+1] функція збігається з деяким алгебраїчним багаточленомPm,i(x)ступеняm.
Різницяm - pміж ступенем сплайну та найвищим порядком безперервної на відрізку [a, b] похідною називаютьдефектом сплайну. Розглянемо сплайни, дефект яких дорівнює 1.
Найбільшого поширення набули кубічні сплайниS3(x).
Отже, для здійснення інтерполяції необхідно побудувати такий сплайн, що S(xi) = yi, i = 0 1, :, n. Відповідно до визначення кубічний сплайн можна подати у вигляді:
