2. Чисельні методи розв’язання систем лінійних рівнянь. Числа обумовленості слр.

Розглянемо чисельні методи розв’язання систем лінійних алгебраїчних рівнянь

Ax=f (1)

де A - матриця n*n, має обернену. x = ( , ... , ) - шуканий вектор,

f =( -заданий вектор.

Припускаємо, що визначник матриці А відмінний від нуля, так що існує єдиний розв’язок х. Розрізняють прямі та ітераційні методи роз-ня СЛР. У прямих (або точних) методах розв’язок x системи (1) відшукується за скінчену кількість арифметичних дій. Внаслідок похибок заокруглення прямі методи насправді не приводять до точного розв’язку системи (1) і назвати їх точними можливо лише залишаючи осторонь похибки заокруглення. Ітераційні методи (їх також називають методами послідовних наближень) полягають у тому, що розв’язок x системи (1) відшукується як границя при послідовних наближень де n- номер ітерації. Як правило, за скінчену кількість ітерацій ця границя не досягається. Як правило число (точність) задається і обчислення проводяться до тих пір, поки не виконується умова .

Прямі методи

перетворюється в , де A_i - матриці nn такі, що системи з такими матрицями розв’язуються легко. Позначимо . Тепер опишемо матриці, з якими легко працювати:

P - матриці, отримані перестановкою рядків чи стовпчиків в одиничній матриці E. P - ортогональні P^-1=P^T, PM - перестановка рядків, NP - перестановка стовпчиків. , p_i - на якому місці в i-му рядку стоїть 1

ортогональні матриці: Q^-1=Q^T, - розв’язок

діагональні матриці

блоково - діагональні матриці, на діагоналі Жорданові клітини розміру 1 чи 2

нижні діагональні матриці (вище діагоналі - 0)

верхні трикутні матриці

I. Метод Гауса та його модифікації.

Запишемо систему (1) у розгорнутому вигляді:

(2)

Метод Гаусса розв’язання системи (2) полягає у послідовному вилученні невідомих з цієї системи. Вважаємо, що a₁₁ 0, поділимо 1-ше р-ня на a₁₁:

(3)

Розглянемо тепер рівняння системи (2), що залишилися

; i= 2,n . (4)

Помножимо (3) на - та додамо одержане рівняння до і-го рівняння системи (4), i=2,n.

У результаті одержимо наступну систему рівнянь:

. Ми отримаємо трикутну матрицю, де на k-му кроці перетворення коефіцієнти визначаються формулою . Виконується, коли ведучий елемент 0. Якщо ведучий елемент =0, тоді у рядку нижче шукають ненульовий елемент і переставляють місцями рядки.

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

Не важко побачити, що одне перетворення методу Гауса еквівалентне множенню системи на L₁^-1: . Нехай у нас уже оброблено і-1 стовпчик початкової матриці. Тоді матриця L_і^-1 матиме вигляд:

Продовжуючи таким чином до останнього рівняння одержимо систему з трикутною верхньою матрицею, де U=A – верхня трикутна матриця. Тобто отримаємо: .

Метод Гауса вимагає n³/3+О(n²) операцій додавання і віднімання і стільки ж операцій множення і ділення.

Ітераційне уточнення одержаного розв’язку:

Уточнення не треба, якщо y має порядок похибки округлення.