Методи вирішення системи лінійних рівнянь

1. Правило Кpамеpа

_ _ _ _ ____

х_j = |(a₁ a₂... b... a_n)|, J = 1, n

| А |

де | А | - визначник матриці А;

_ _ _ _

|(а₁, а₂.. b...a_n)| - визначник матриці А, в якому j-й стовпець замінений на вектор вільних членів.

Цей метод через свою трудомісткість практично не використовується.

2. Метод Гауса (метод послідовного виключення).

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

a₁₁⁽⁰⁾ x₁ + a₁₂ ⁽⁰⁾ x₂ + a₁₃⁽⁰⁾ x₃ + a₁₄⁽⁰⁾ x₄ = b₁⁽⁰⁾ (1)

a₂₁⁽⁰⁾ x₁ + a₂₂⁽⁰⁾ x₂ + a₂₃⁽⁰⁾ x₃ + a₂₄⁽⁰⁾ x₄ = b₂ ⁽⁰⁾

a₃₁⁽⁰⁾ x₁ + a₃₂⁽⁰⁾ x₂ + a₃₃⁽⁰⁾ x₃ + a₃₄⁽⁰⁾ x₄ = b₃⁽⁰⁾

a₄₁⁽⁰⁾ x₁ + a₄₂⁽⁰⁾ x₂ + a₄₃⁽⁰⁾ x₃ + a₄₄⁽⁰⁾ x₄ = b₄⁽⁰⁾

Припустимо, що коефіцієнт а₁₁, званий провідним елементом першого рядка, не рівний нулю. Розділивши перше з рівнянь (1) на а₁₁, одержимо нове рівняння

x₁ + a₁₂⁽¹⁾ x₂ + a₁₃⁽¹⁾ x₃ + a₁₄⁽¹⁾ x₄ = b₁⁽¹⁾ (2)

де a_1j ⁽¹⁾ = a_1j ⁽⁰⁾/ a₁₁⁽⁰⁾, j = 2,3,4.

Виключимо невідому х₁ з кожного рівняння системи (1), починаючи з другим, шляхом віднімання рівняння (2), помноженого на коефіцієнт при х₁ у відповідному рівнянні. Перетворені рівняння мають вигляд:

a₂₂⁽¹⁾ x₂ + a₂₃⁽¹⁾ x₃ + a₂₄⁽¹⁾ x₄ = b₂⁽¹⁾ (3)

a₃₂⁽¹⁾ x₂ + a₃₃⁽¹⁾ x₃ + a₃₄⁽¹⁾ x₄ = b₃ ⁽¹⁾

a₄₂⁽¹⁾ x₂ + a₄₃⁽¹⁾ x₃ + a₄₄⁽¹⁾ x₄ = b₄⁽¹⁾

де a_ij ⁽¹⁾=a_ij ⁽⁰⁾ -a_1j⁽¹⁾* a_i1⁽⁰⁾, i = 2,3,4, j = 2,3,4.

Припустимо, що ведучий елемент другого рядка, тобто коефіцієнт а₂₂, теж відмінний від нуля. Тоді, розділивши на нього перше з рівнянь (3), одержимо:

x₂+ a₂₃⁽²⁾+ a₂₄⁽²⁾ x₄ = b₂⁽²⁾ (4)

де a_2j ⁽²⁾ = a_2j⁽¹⁾/a₂₂⁽¹⁾, j = 3,4.

Виключивши за допомогою рівняння (4) невідому х₂ з двох останніх рівнянь в (3), одержимо:

a₃₃⁽²⁾ x₃ + a₃₄⁽²⁾ x₄ = b₃⁽²⁾ (5)

a₄₃⁽²⁾ x₃ + a₄₄⁽²⁾ x₄ = b₄⁽²⁾

де a_ij⁽²⁾= a_ij⁽¹⁾ - a_2j⁽²⁾ a_i2⁽¹⁾ i = 3,4, j = 3,4

Якщо ведучий елемент третього рядка а₃₃⁽²⁾ не рівний нулю, то поділивши на нього перше з рівнянь (5) і віднявши знайдене рівняння, помножене на а₄₃⁽²⁾, з другого рівняння, одержимо:

x₃ + a₃₄⁽³⁾ x₄ = b₃⁽³⁾ (6)

a₄₄⁽³⁾ x₄ = b₄⁽³⁾ (7)

де a₃j⁽³⁾= a_3j⁽²⁾/ a₃₃⁽²⁾, a_4j⁽³⁾= a₄j⁽²⁾ - a₃j⁽³⁾ a₄₃⁽²⁾, j = 4

Нарешті, якщо a₄₄⁽³⁾ не рівно нулю, то, розділивши на нього рівняння (7) приведемо це рівняння до вигляду

x₄ = b₄⁽⁴⁾ (8)

де b₄⁽⁴⁾= b₄⁽³⁾/ a₄₄⁽³⁾

Отже, якщо ведучі елементи a₁₁⁽⁰⁾, a₂₂⁽¹⁾, a₃₃⁽²⁾, a₄₄⁽³⁾ відмінні від нуля, то система (1) еквівалентна наступній системі з трикутною матрицею:

x₁ + a₁₂⁽¹⁾ x + a₁₃⁽¹⁾ x3 + a₁₄⁽¹⁾ x₄ = b₁⁽¹⁾ (9)

x₂ + a₂₃⁽²⁾ x3 + a₂₄⁽²⁾ x₄ = b₂⁽²⁾

x₃ + a₃₄⁽³⁾ x₄ = b₃⁽³⁾

x₄ = b₄⁽⁴⁾

яка одержана об'єднанням рівнянь (2),(4),(6),(8).

З системи (9) невідомі x₁, x₂, x₃, x₄ знаходять явно в зворотному порядку по формулах

x₄ = b₄⁽⁴⁾

x₃ = b₃⁽³⁾ - a₃₄⁽³⁾ x₄ (10)

x₂ = b₂⁽²⁾ - a2₃⁽²⁾ x₃ - a₂₄⁽²⁾ x₄

x₁ = b₁⁽¹⁾ - a₁₂⁽¹⁾ x₂ - a₁₃⁽¹⁾ x₃ - a₁₄⁽¹⁾ x₄

Процес приведення системи (1) до трикутного вигляду (9) називається прямим ходом, а знаходження невідомих по формулах (10) - зворотним ходом методом Гауса.

Алгоритм методу Гауса можна записати таким чином: ___ ___

1. За допомогою двох циклів з управляючими змінними i = 1,n та j = 1,n організовуємо введення коефіцієнтів a_ij і b_j, створюючи масиви А і В.

2. Проводимо прямий хід виключення невідомих шляхом перетворення коефіцієнтів по формулах:

a_ji = - a_ji/a_ji

a_jk = a_jk + aj_i * a_jk

b_i = b_i + a_ji * b_i

_____ _____ _____

де i = 1,n-1; j = i+1,n; до = i+1,n

Наприкінці перетворень одержуємо:

x_n = b_n/a_nn

3. Організовуємо зворотний хід (послідовне знаходження x_n-1, x_n-2...x₁) проводячи обчислення по формулах:

h = b_i і h = h - x_ja_ij

_____ _____

де i = n-1,1; j = i+1,n, тоді x_i = h/a_ij

В результаті формується масив невідомих X={ x₁,x₂...x_n}

Блок-схема представлена на Рис. 1.

Розглянутий вище найпростіший варіант методу Гауса, званий схемою єдиного розподілу, має наступні недоліки. Якщо ведучий елемент якого-небудь рядка, наприклад коефіцієнт а₁₁⁽⁰⁾ при х₁ в першому ж рівнянні виявиться рівним нулю, то ця схема формально непридатна, хоча задана система рівнянь може мати єдине рішення. Крім того, якщо визначник не рівний нулю, але в процесі обчислень зустрічаються ведучі елементи які достатньо малі в порівнянні з іншими елементами відповідних стрічок, то ця обставина сприяє посиленню негативного впливу погрішностей округлення на точність результату.

Розглянемо схеми з вибором головного елемента.

1. Метод Гауса з вибором головного елемента в стовпці.

На кожному i-м кроці спочатку вибираємо елемент, рівний max _i<j<n | a_ij^(i-1) |. Хай це буде елемент (A_li^(i-1)). Міняємо місцями L-е і i-е рівняння і проводимо i-й крок методу Гауса.

Блок-схема алгоритму приведена на Рис. 2.

2. Метод Гауса з вибором головного елемента в рядку.

На кожному i-м кроці вибирається елемент, рівний max | a_ij |. Хай це буде елемент a_iL. Перезначимо невідомі: x_L = x_i, а х_i = x_L, тобто переставляємо L та i стовпці матриці, а далі проводимо i-й крок методу Гауса.

Блок-схема алгоритму приведена на Рис. 3.

М - масив індексів невідомих; К - номер стовпця, що містить max елемент; R - робоча змінна, що використовується для перестановки елементів стовпців матриці коефіцієнтів, а також для пере означення індексів невідомих (елементи масиву М міняються місцями).

Рис.2

Рис.3

Приклад 1. Знаходження рішення системи лінійних рівнянь:

в MathCAD

а) вирішення системи лінійних рівнянь методом Крамера.

детермінант не дорівнює 0, система має едине рішення

б) вирішення системи лінійних рівнянь матричним методом

в) вирішення системи лінійних рівнянь методом Гауса - Жордано