Одним із найпоширеніших методів розв'язання систем лінійних рівнянь є метод Гауса. Цей метод також називають методом послідовного виключення невідомих. В загальному вигляді його вперше запропонував німецький математик Карл Фрідріх Гаус (1777-1855)

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

2.1.1 Схема єдиного ділення

Прямий хід складається з n 1 кроків виключення.

1-й крок. Метою цього кроку є виключення невідомого x₁ із рівнянь з номерами i= 2, 3, …, n. будемо вважати, що коефіцієнт a₁₁ 0, будемо називати його головним елементом 1-го кроку.

Знайдемо величини

q_i1 = a_i1/a₁₁ (i = 2, 3, …, n),

що називаються множниками 1-го кроку. Віднімемо послідовно від другого, третього, …, рівнянь системи перше рівняння, помножене відповідно на q₂₁, q₃₁, …, q_n1. Це дозволить перетворити в нуль коефіцієнти при x₁ у всіх рівняннях, крім першого. В результаті отримаємо еквівалентну систему

a₁₁x₁ + a₁₂x₂ + a₁₃x₃ + … + a_1nx_n = b_1,

a₂₂⁽¹⁾x₂ + a₂₃⁽¹⁾x₃ + … + a_2n⁽¹⁾x_n = b₂^(1),

a₃₂⁽¹⁾x₂ + a₃₃⁽¹⁾x₃ + … + a_3n⁽¹⁾x_n = b₃⁽¹⁾,

……………

a_n2⁽¹⁾x₂ + a_n3⁽¹⁾x₃ + … + a_nn⁽¹⁾x_n = b_n⁽¹⁾.

в якій a_ij⁽¹⁾ и b_ij⁽¹⁾ обчислюються за формулами

a_ij⁽¹⁾ = a_ij ? q_i1a_1j, b_i⁽¹⁾ = b_i ? q_i1b₁.

2-ий крок. Метою цього кроку є виключення невідомого x₂ з рівнянь з номерами i = 3, 4, …, n. Нехай a₂₂⁽¹⁾ ? 0, де a₂₂⁽¹⁾ - коефіцієнт. Що називають головним (або ведучим) елементом 2-го кроку. Обчислимо множники другого кроку

q_i2 = a_i2⁽¹⁾ / a₂₂⁽¹⁾ (i = 3, 4, …, n)

і віднімемо послідовно із третього, четвертого, …, n-го рівняння системи друге рівняння, помножене відповідно на q₃₂, q₄₂, …, q_m2. В результаті отримаємо систему

a₁₁x₁ + a₁₂x₂ + a₁₃x₃ +… + a_1nx_n =b₁ ,

a₂₂⁽¹⁾x₂ + a₂₃⁽¹⁾x₃ +… + a_2n⁽¹⁾ =b₂⁽¹⁾ ,

a₃₃⁽²⁾x₃ +… + a_3n⁽²⁾x_n = b₃⁽²⁾ ,

……………….

a_n3⁽²⁾x₃ +… + a_nn⁽²⁾x_n = b_n⁽²⁾ .

Тут коефіцієнти a_ij⁽²⁾ і b_ij⁽²⁾ обчислюються за формулами

a_ij⁽²⁾ = a_ij⁽¹⁾ - q_i2a_2j⁽¹⁾, b_i⁽²⁾ = b_i⁽¹⁾ - q_i2b₂⁽¹⁾.

Аналогічно проводяться інші кроки. Опишемо черговий крок.

k-й крок. В припущенні, що головний елемент k-го кроку a_kk^(k-1) відмінний від нуля, обчислимо множники k-го кроку

q_ik = a_ik^(k-1) / a_kk^(k-1) (i = k + 1, …, n)

і віднімемо послідовно із (k + 1) - го, …, n-го рівняння отриманих на попередньому кроці системи k-e рівняння, помножене відповідно на q_k+1,k, q_k+2,k, …, q_nk.

Після кроку виключенням отримаємо систему рівнянь

a₂₂⁽¹⁾x₂ +a₂₃⁽¹⁾x₃ + … + a_2n⁽¹⁾x_n = b₂⁽¹⁾ ,

a₃₃⁽²⁾x₃ + … + a_3n⁽²⁾x_n = b₃⁽²⁾ ,

……………….

a_nn^(n-1)x_n = b_n^(n-1) .

матриця A^(n-1) якої є трикутною. На цьому розрахунки прямого ходу закінчуються.

Зворотній хід. Із останнього рівняння системи знаходимо x_n. Підставляючи знайдене значення x_n в передостаннє рівняння, отримаємо x_n-1. Здійснюючи зворотну підстановку, далі послідовно знаходимо x_n-1, x_n-2, …, x₁. Обчислення невідомих тут проводиться за формулами

x_n = b_n^(n-1) / a_nn^(n-1),

x_k = (b_n^(k-1) - a_k,k+1^(k-1)x_k+1 - … - a_kn^(k-1)x_n) / a_kk^(k-1), (k = n - 1, …, 1).

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

2.1.2 Метод Гауса з вибором головного елемента по стовпчику (схема часткового вибору)

Описання методу. На k-ому кроці прямого ходу коефіцієнти рівнянь системи з номерами i = k + 1, …, n перетворюються за формулами

a_ij^(k) = a_ij^(k-1) ? q_ika_kj, b_i^(k) = b_i^(k-1) ? q_ikb_k^(k-1)_, i = k + 1, …, n.

Інтуїтивно зрозуміло, що для запобігання сильного росту коефіцієнтів системи і пов'язаних з цим помилок не можна допускати великих множників q_ik.

В методі Гауса з вибором головного елементу по стовпчику гарантується, що |q_ik| ? 1 для всіх k = 1, 2, …, n - 1 та i = k + 1, …, n. Відмінність цього варіанту метода Гауса від схеми єдиного ділення полягають в тому, що на k-ому кроці виключення в якості головного елементу вибирають максимальний за модулем коефіцієнт a_ikk при невідомому x_k в рівняннях номерами i = k + 1, …, n. Потім відповідне вибраному елементу рівняння з номером i_k міняють місцями з k-им рівнянням системи для того, щоб головний елемент зайняв місце коефіцієнта a_kk^(k-1). Після цієї перестановки виключення невідомого проводять, як в схемі єдиного ділення.

2.1.3 Метод Гауса з вибором головного елементу по всій матриці (схема повного вибору)

На 1-ому кроці методу серед елементів a_ij визначають максимальний за модулем елемент a_i1j1. Перше рівняння системи і рівняння з номером i₁ міняють місцями. Далі стандартним образом проводять виключення невідомого x_i1 із всіх рівнянь, окрім першого.

На k-ому кроці методу серед коефіцієнтів a_ij^(k-1) при невідомих в рівняннях системи з номерами i = k, …, n вибирають максимальний за модулем коефіцієнт a_ikjk^(k-1). Потім k-е рівняння і рівняння, що містить даний коефіцієнт, міняють місцями і виключають невідоме x_jk з рівнянь з номерами i = k + 1, …, n.

На етапі зворотного ходу невідомі обчислюють в такому порядку: x_jn, x_jn-1, …, x_j1.

Наведемо модифікований метод вилучення невідомих - так званий метод Жордана-Гауса.

Розглянемо схему Жордана-Гауса на прикладі розв'язування конкретної системи ,

яку у матричному вигляді записують так: .

Початкова таблиця має такий вигляд:

.

Числа -2 та -3 - це елементи другого та третього рядка (взяті з протилежним знаком), які розташовані в тому стовпці, де в першому рядку є число 1.

Множимо перший рядок на числа -2 та -3 й отримуємо, відповідно, вектори (-2; -4; 6; 12) та (-3; -6; 9; 18). Додаємо ці вектори до другого і третього рядків:

.

Ділимо всі елементи другого рядка на -5, роблячи діагональний елемент таблиці одиничним:

.

Розпочинаємо наступний етап методу. Множимо другий рядок на -2 та на 4 й отримуємо вектори (0; -2; 14/5; 22/5) і (0; 4; - 28/5; - 44/5). Додаємо ці вектори до першого та третього рядків:

,

і робимо ще один діагональний елемент одиницею (ділимо на 22/5):

.

На останньому кроці множимо третій рядок на 1/5 та 1/7 і додаємо утворені вектори (0; 0; 1/5; 3/5) і (0; 0; 7/5; 21/5) до першого та другого рядка:

, тобто отримуємо систему рівнянь

, розв'язками якої є числа x₁= -1; x₂=2; x₃=3.

Якщо під час обчислень у схемі Жордана-Гауса деякий рядок повністю стає нульовим (0 0 0 | 0), то це є ознакою того факту, що система має безліч розв'язків.

Якщо ж цей рядок стає нульовим за винятком вільного члена (0 0 0 | b_i0), то система розв'язків не має.

2.2 Метод Крамера

(Матриця А є симетричною, якщо її елементи, розташовані симетрично щодо головної діагоналі, рівні між собою, тобто a_ij=a_ji. при всіх i, j. Матриця В є транспонованою до матриці А, якщо її стовпці збігаються з відповідними рядками А).

Метод квадратного кореня скорочує обчислення приблизно в 2 рази за рахунок симетрії.

При виконанні умов невиродженості і симетричності матриці системи метод квадратного кореня вже можна застосовувати, але в процесі обчислень по формулах методу при цьому можуть виникати комплексні числа. Для того, щоб уникнути роботи з комплексними числами, ми будемо вимагати від матриці А виконання ще однієї додаткової умови: додатньої визначеності, тобто всі головні мінори А мають бути додатні. (Нагадаємо, що головним мінором порядку К квадратної матриці А називається мінор, що складається з елементів, що знаходяться на перетині перших К рядків і перших К стовпців матриці А).

2.4.2 Матричний опис методу квадратного кореня

Підставою для цього методу служить наступна теорема:

Хай дана система АХ=В задовольняє умові застосовності методу квадратного кореня. Тоді існує така верхньотрикутна матриця S, що: S^tS=A

В цьому випадку початкову систему можна записати у вигляді (S^tS) X=B або S^t(SX)=B. Якщо позначити SX=Y, то весь процес знаходження рішення Х можна розбити на три етапи:

Знайти матрицю S: S^tS=A;

Знайти Y: S^tY=B;

Знайти X: SX=Y.

Найбільш трудомістким тут є перший етап, оскільки на другому і третьому етапі треба лише розв'язувати системи лінійних рівнянь з нижньотрикутною і верхньотрикутною матрицями відповідно.

Знаходження матриці S («квадратного кореня» з А)

Покажемо процес знаходження коефіцієнтів матриці S в разі матриці А розмірами 4х4, а потім вже випишемо спільні формули.

Позначимо елементи матриці S:

Тоді має бути виконане співвідношення A=S^tS, або

По правилах множення матриць отримуємо систему:

s₁₁*s₁₁ = a₁₁

s₁₁*s₁₂ = a₁₂

s₁₁*s₁₃ = a₁₃

s₁₁*s₁₄ = a₁₄

s₁₂*s₁₂ + s₂₂*s₂₂ = a₂₂

s₁₂*s₁₃ + s₂₂*s₂₃ = a₂₃

s₁₂*s₁₄ + s₂₂*s₂₄ = a₂₄

s₁₃*s₁₃ + s₂₃*s₂₃ + s₃₃*s₃₃ = a₃₃

s₁₃*s₁₄ + s₂₃*s₂₄ + s₃₃*s₃₄ = a₃₄

s₁₄*s₁₄ + s₂₄*s₂₄ + s₃₄*s₃₄ + s₄₄*s₄₄ = a₄₄

з 10 рівнянь. На перший погляд, ми сильно ускладнили завдання - замість лінійної системи з 4-х рівнянь з 4-мя невідомими ми повинні вирішувати систему з 10 нелінійних рівнянь з 10 невідомими. Проте, і в разі 4х4, і в разі N невідомих наша система вирішується дуже просто: ми по черзі знаходимо всі елементи матриці S. З 1-го рівняння знайдемо s₁₁, потім з 2-го рівняння - s₁₂ і так далі Таким чином ми порядково визначимо всі елементи шуканої матриці.

Спільні формули для знаходження елементів матриці S мають вигляд:

, де i=1,2…n

де j=i+1…, n

Для знаходження вектора Y ми вирішуємо систему S^tY=B, і отримуємо:

, де j=1,2…, n

Для знаходження вектора Х ми розв'язуємо систему SХ=Y, і отримуємо:

, де i=n, n-1…, 1.

3. Наближені методи розв'язання систем лінійних рівнянь

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

Коефіцієнти лінійних систем, які виникають під час обробки результатів експерименту, містять помилки спостережень. Якщо коефіцієнти системи задано формулами, то обчислення їх призводить до похибок округлення. Якщо систему рівнянь у пам'ять машини записати навіть точно, то в процесі її розв'язування ЕОМ обов'язково виникнуть похибки округлень, які не можуть не вплинути на точність розв'язку. Проте, якщо матриця системи майже вироджена, то можна сподіватись, що малі зміни в коефіцієнтах і (або) вільних членах також призведуть до значних змін у її розв'язку.

Якщо малі збурення коефіцієнтів і (або) вільних членів системи дуже збурюють її розв'язок, то таку систему рівнянь називають погано обумовленою. Навпаки, якщо малі збурення коефіцієнтів і (або) вільних членів системи мало збурюють її розв'язок, то таку систему називають добре обумовленою. Прикладом погано обумовленої є, наприклад, система вигляду

6,1x₁ + 3,4x₂ = 6,12,

14,7 x₁ + 8,2х₂ = 14,7,

розв'язком якої є пара (1; 0). Якщо число 6,1 у правій частині першого рівняння системи змінити на 0,02, то система

6,1x₁ + 3,4x₂ = 6,1,

14,7 x₁ + 8,2х₂ = 14,7,

матиме розв'язком пару (5,1; -7,35). Отже, мале збурення (менше 0,33%) одного з вільних членів системи зовсім змінило розв'язок системи.

Якщо коефіцієнт 6,1 у лівій частині першого рівняння системи змінити на 0,01, то розв'язком системи

6,11x₁ + 3,4x₂ = 6,1,

14,7 x₁ + 8,2х₂ = 14,7,

буде пара (0,36730972; 1,204918). І в цьому випадку мале збурення (менше 0,17%) одного коефіцієнта системи значно змінило її розв'язок.

Ознакою поганої обумовленості системи лінійних рівнянь є її майже виродженість. Іншими словами, якщо значення визначника системи досить мале порівняно з її коефіцієнтами, то така система близька до виродженої (особливої). Так, визначник системи і становить близько 0,27% значення найбільшого з коефіцієнтів системи (а₂₁ = 14,7).

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

3.1 Метод Гауса. Схема з вибором головного елемента