Розв’язування систем лінійних алгебраїчних рівнянь. Абсолютна величина і норма матриці, страница 8

Поєднуючи ці рівності з (5) (l= N-1), одержимо остаточні формули для знаходження невідомих

у_i=a_i+1 у_i+1+b_i+1, i=N-1, N-2, ..., 0,

у_N=b_N+1, (6)

де коефіцієнти знаходяться за рекурентними формулами:

a_i+1= , i=1, 2, …, N-1, a₁= (7)

b_i+1= , i=1, 2, ..., N-1; b₁= (8)

Отже, формули (6)-(8) описують метод Гаусса, що у застосуванні до системи (1) одержав спеціальну назву - метод прогонки. Коефіцієнти a_iіb_iназиваються прогонковими коефіцієнтами, формули (7), (8) описують прямий хід прогонки, а (6) - зворотний хід. Оскільки значення у_iзнаходяться тут послідовно при переходу від i+1 до i, то формули (6)-(8) називають іноді правою прогонкою.

Метод зустрічних прогонок. Вище були отримані формули правої прогонки для розв’язку системи (1). Аналогічно виводяться формули лівої прогонки:

x_i =, i=N-1, N-2, ..., 1; , (9)

h_i=, i=N-1, N-2, ..., 0; , (10)

y_i+1=x_i+1 у_i+h_i+1, i=0, 1, ..., N-1; . (11)

Тут значення у_iзнаходяться послідовно при зростанні індексу i (зліва направо).

Іноді виявляється зручним комбінувати праву і ліву прогонки, одержуючи так званий метод зустрічних прогонок. Цей метод доцільно застосовувати, якщо треба знайти тільки одну невідоме, наприклад y_m (0£m£N), або групу невідомих. Одержимо формули методу зустрічних прогонок. Нехай 1£ m£N і за формулами (7)-(10) знайдені a₁, a₂, ..., a_m, b₁, b₂, ..., b_m, і x_N, x_N-1, ..., x_m, h_N, h_N-1, ..., h_m. Випишемо формули (6), (11) для зворотного ходу правої і лівої прогонок для i=m-1. Будемо мати систему, з якої знайдемо y_m:

y_m= .

Використовуючи знайдене y_m, за формулами (6) для i=m-1, m-2, ..., 0 знайдемо послідовно y_m-1, y_m-1, ..., y₀, а за формулами (11) для i=m, m+1, ..., N обчислимо інші y_m+1, y_m+2, ...,y_N.

Отже, формули методу зустрічних прогонок мають вигляд:

a_i+1=, i=1, 2, ..., m-1, a₁=,

b_i+1=, i=1, 2, ..., m-1, b₁=,

x_i =, i=N-1, N-2, ..., m, , (12)

h_i=, i=N-1, N-2, ..., m, ,

для обчислення прогонкових коефіцієнтів і

у_i=a_i+1 у_i+1+b_i+1, i=m-1, m-2, ..., 0;

у_i+1=x_i+1 у_i+h_i+1, i=m ,m+1, ..., N-1; (13)

y_m=

для визначення розв’язків.

3.1 Метод простої ітерації

Розглянемо СЛАР у матричному вигляді (3.2) (діагональні коефіцієнти a_ii відмінні від нуля для всіх i). Зведемо її до вигляду X=CX+D, де C=[c_ij] - квадратна матриця порядку n:

При цьому СЛАР (3.1) набуде вигляду

(3.4)

Взявши довільне початкове наближення , будуємо ітераційний процес за формулою (k=1,2,…).

3.2 Метод Зейделя

Ітераційний процес Зейделя відрізняється від методу простої ітерації тим, що при розв’язуванні систем вигляду X=CX+D обчислення наступного наближення значення x_iпри 1<i<n використовує обчислені раніше наближення невідомих x₁,x₂,…,x_i-1… .

У цьому випадку ітераційний процес методу Зейделя має вигляд:

(3.5)

Часто в практичних обчисленнях ітераційний процес припиняють, якщо два послідовних наближення відрізняються менше від наперед заданого числа ∆ у змісті обраної норми:

тобто коли наближені розв’язки і стануть

досить близькими і Величина ∆ пов'язана з точністю ε розв’язання системи співвідношенням , де - будь-яка канонічна норма матриці з коефіцієнтів при невідомих у правих частинах рівнянь перетвореної системи: X=BX+D.