II Метод віддзеркалення.

Цей метод базується на розкладі матриці СЛАР (сис-ми лін. алгебраїчних рівнянь) на добуток ортогональної і верхньої трикутної матриці. A=QR , де Q – ортогональна матриця, яка є добутком елементарних ортогональних матриць, так званих матриць віддзеркалення або перетворень Хаусхолдера. Цей метод вимагає вдвічі більше операцій, ніж метод Гауса.

III Для специфічних матриць:

1) Якщо матриця симетрична, то метод квадратного кореня використовує в 2 рази менше часу, ніж метод Гауса. A - симетрична, A=LL^T, L - нижня, L^T- верхня трикутна матриця.

Звідси , і взагалі, , . Цей метод має недоліки, якщо в системі присутні дійсні коефіцієнти (при розрахунках на ПЕОМ).

2) Матриця A (система рівнянь з цією матрицею) має тридіагональний вигляд:

В цьому випадку для роз-ку задачі використовується метод прогонки, який вимагає порядку 8 n операцій. Якщо здійснити розщеплення, то можна очікувати, що вони дводіагональні, отже існує зв’язок , тоді . Цей вираз підставимо в і-те рівняння. Для визначення покрокових  і  ми маємо перше рівняння . Метод визначення  і  називається прямим ходом прогонки. Якщо відоме останнє x_n, то зворотнім ходом можна визначити всі x_n-1,..,x₁. А x_n ми оберемо з останнього рівняння . Метод прогонки потребує O(n).

Ітераційні методи

Багато практично важливих задач зводяться до роз-ня СЛАР дуже великої розмірності, матриці яких не є щільно заповненими (містять багато нульових елементів). У цьому випадку вигідно застосовувати ітераційні методи. Розглянемо систему . Ітераційні методи складаються з перетворень цієї системи до еквівалентної: та організації обчислювального процесу при заданому початковому наближенні . За таких умов процес буде збігатися до дійсного розв’язку системи. Розглянемо послідовність , і т.д., де ,..., та зрозуміло У нас для оптимального розв’язку послідовність повинна бути скінченою. Для цього необхідно , а тоді приймає вигляд . Існує декілька підходів для отримання цього з . Розглянемо ці підходи:

1. Метод Якобі. Вважаємо, що a₁₁0, тоді , ..., . (*)

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

3. Методи інтерполювання. Множники Лагранжа та Ерміта. Сплайни.

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

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

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

( наближеного) функції у довільній точці .

Іноді відомо, що наближену функцію доцільно шукати у вигляді

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

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

Серед способів інтерполяції найбільш поширеним є випадок лінійної інтерполяції .

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

(1)

тобто з системи n +1 лінійних рівнянь з n+1 невідомими

Достатня умова існування єдиного роз-ку сис-ми для довільного набору вузлів є вимоги, щоб ф-ція була ф-цією Чебешова: . Тоді отримаємо (2)

тобто інтерполяція здійснюється многочленом, який називається інтерполяційним.

Теорема. Якщо вузли интерполяції різні, то існує єдиний інтерполяційний многочлен n-го ступеню.

В загальному вигляді , (3)

(4)

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

Завжди можна записати рівність , де - залишковий член, тобто похибка інтерполювання. шукають у вигляді , де , а r_n(x) - деяка функція, значення якої у вузлах інтерполяції x_i можна задавати які завгодно, оскільки . Оцінка похибки інтерполяції в поточній точці x [a,b] має вигляд , де const M дорівнює .

Лінійна інтерполяція.

Інтерполяція за формулою при n=1, тобто за допомогою лінійної функції , називається лінійною. Якщо ввести позначення , то формула лінійної інтерполяції запишеться у вигляді , де q називається фазою інтерполяції, яка змінюється від 0 до 1, коли x пробігає значення від x₀ до x₁.

Многочлени Чебишева.

Для того, щоб максимальна похибка інтерполяції функції f на відрізку [a,b] () була мінімальною, в якості вузлів інтерполяції беруть корені многочлена Чебишева T_n+1(x): . Ці точки є оптимальними вузлами оцінки похибки інтерполяції на відрізку [a,b]. Оцінка похибки має вигляд , де .

Інтерполяція з рівновіддаленими вузлами.

Якщо відрізок [a,b] великий і необхідна висока точність апроксимації функції, то часто користуються таблицею значень функції у вузлах, що розбивають відрізок з постійним кроком, число їх може бути достатньо великим. Нехай - вузли інтерполяції, h>0 - крок, причому . Позначимо , тоді інтерполяційний многочлен буде мати вигляд , де . Залишковий член (похибка інтерполяції) має вигляд , де - n+1 похідна по x, - деяка проміжна точка, .

Інтерполювання з кратними вузлами.

Побудувати многочлен степеня m такий, що . Многочлен називається інтерполяційним многочленом Ерміта.

Нехай при таких умовах ; – многочлен Ерміта.