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

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

a₂₁x₁ + a₂₂x₂ + …+ a_2nx_n = b₂

.

. Þ a_ijx_j= b_i (i = 1,n)

.

a_n1x₁ + a_n2x₂ + …+ a_nnx_n = b_n

Число елементарних операцій при розв’язуванні лінійних систем з n-змінними пропорційно ~ n³.

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

Прямі методи дозволяють отримати розв’язок системи у вигляді точних формул після виконання скінченого числа арифметичних операцій над коефіцієнтами системи і вільними членами. Це метод Гауса і правило Крамера.

Ітераційні методи дозволяють отримати розв’язок системи з заданою точністю шляхом нескінченно збіжних процесів. Із наближених методів розглянемо метод ітерацій.

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

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

1. Вимагають збереження в ОП всіх елементів матриці А, навіть, якщо серед них є багато нульових.
2. При розрахунках відбувається накопичення похибок, так як результат наступного кроку обчислень використовує результат попереднього.
3. При застосуванні прямих методів доцільно розв’язувати системи з густо заповненою матрицею. Тому широко використовують ітераційні методи. В них задається початкове значення невідомих: x₁⁽⁰⁾, x₂⁽⁰⁾,…,x_n⁽⁰⁾ і врезультаті ітераційних циклів отримуються наступні наближення. Вважається, що розв’язок знайдений з точністю e, якщо виконується умова êx_i⁽ⁿ⁾-x_i^(n-1) |< e (i=1,2,…,n).

Переваги:

1. Ітераційні методи не завжди вимагають збереження всієї матриці. Потрібні коефіцієнти можна знаходити в процесі розрахунку.
2. Вони не накопичують похибок так як результат на n-ітерації не залежить від попередніх разів.
3. Вони годяться для широкого класу систем і погано обумовлених систем.

Вибір методу розв’язку систем лінійних рівнянь залежить від кількох факторів:

1.Від особливостей матриці А

2.Від розмірності А

3.Від характеристик комп’ютера: його швидкодії, ОП,
зовнішніх носіїв.

A×X=B

Матриця коефіцієнтів називається неособливою або не виродженою, якщо існує обернена до неї матриця А^-1×А= А×А^-1= І.

a₁₁ a₁₂... a_1n

.

A =.

.

a_n1 a_n2 ... a_nn

X = B =

a₁₁ 0 0 0

0 a₂₂ 0 0

0 0 a₃₃ 0 - діагональна квадратна

0 0 0 a_nn

1 0 0 0

0 1 0 0 - одинична, нульова

0 0 1 0

0 0 0 1

Якщо застосовувати до систем лінійних рівнянь елементарні перетворення, то отримаємо рівносильні системи, тобто системи, що мають такий же розв’язок. Елементарні перетворення:

1. множення всіх елементів рядка на одне і те ж число, яке ¹ 0.

2. додавання до елементів одного рядка відповідних елементів іншого рядка, помножених на загальне для всіх число.

3. перестановка рядків або стовпців.

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

Він оснований якраз на елементарних перетвореннях. Схема – квадратна матриця перетворюється в трикутну. Розберем схему єдиного ділення.

a₁₁х₁ + а₁₂х₂ + а₁₃х₃ = b₁

a₂₁х₁ + а₂₂х₂ + а₂₃х₃ = b₂

a₃₁х₁ + а₃₂х₂ + а₃₃х₃ = b₃

Нехай а₁₁¹ 0

Розділимо коефіцієнти першого рівняння і вільний член на а₁₁. Отримаємо а = і b = (1)

x₁ + a x₂ + a x₃ = b (2)

Тепер виключимо змінну х₂ з другого і третього рівнянь. Для цього від другого рівняння віднімемо перше, помножене на а₂₁, а від третього - помножене на а₃₁. Отримаємо

a x₂ + a x₃ = b (3)

a x₂ + a x₃ = b , де (4)

a = а_ij - a a_i1 (i = 2,3; j = 2,3)

b = b_i - a b

Далі (3) ділимо на а Þ

x₂ + a x₃ = b і виключимо х₂ із (4).

Отримаємо х₃ =

Якщо х₁, х₂, х₃ підставити в початкову систему, то повинні отримати тотожність, але в зв’язку з тим, що проводились заокруглення чисел, то в результаті підстановки отримаємо деякі числа, відмінні від нуля. Ці числа називають нев’язками. Якщо нев’язки малі, то рішення є вірним.

Алгоритм

А×Х = В

Введемо розширену матрицю

a₁₁ a₁₂... a_1n b₁

a₂₁ a₂₂... a_2n b₂

.

(А|B) =.

a_n1 a_n2... a_nn b_n

A(N,N); B (N)

Розв’язок X(N) розмістимо в В.

1) Ділимо перший рядок (А|B) на а₁₁, потім множимо його послідовно на а_к1 (k =2...n) і віднімаємо його від k-ого рядка. Після цього отримаємо наступну матрицю:

2) 1 a ... a b
0 a ... a b
.
.
.
0 a ... a b

3) Елементи другого рядка ділимо на а , потім множимо на а (k = 3…n) і віднімаємо від k-ого рядка.

4) Продовжуємо цей процес до тих пір, поки ця процедура не повториться (n-1) раз. Тоді отримаємо:
1 a ... a b
0 1 a ... a b
0 0 1... a b
.
.
.
0 0 0... 1 a b
0 0 0 … 0 1 b
На цьому прямий хід методу Гауса закінчується.

5) Виконуємо обернений хід метода Гауса. В (n-1) рядок підставляємо значення х_n і знаходимо х_n-1 і т.д. за формулами

Правилом Крамера вже для n=4 не користуються, бо число операцій:

N (n) = (n²-1) n! +n, а для Гауса

N (n) = (n²+3n - 1)

Тобто при:   n = 5   n=10

По Крамеру   N = 2885   N = 360∙10^6

По Гаусу   N = 65   N = 430

Метод Гауса – в теорії числових методів показується, що при виконанні прямого ходу методу Гауса треба виконати n³/2 – додавань, ~ n³/3 – множень, ~ n²/2 – ділень. На оберненому ході методу Гауса ~n²/2 – додавань, ~ n²/2 – множень, ~ n – ділень. Отже, приведення матриці до трикутного вигляду на порядок складніше ніж знаходження невідомих.

При розробці алгоритму обов’язково треба перевірити а₁₁≠0. Якщо а₁₁=0, тоді серед коефіцієнтів а_і1 (і=2,3,...,n) шукають відмінний від нуля коефіцієнт а_і1. Міняють це рівняння з першим. Такий коефіцієнт обов’язково знайдеться, інакше матриця вироджена, тобто detA=0.

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

При обчисленні визначника, треба виконати (n-1)×n! Операцій множення і (n!-1) – операцій додавання. Отже всіх операцій N=n!-1+(n-1)×n!=n×n!-1»n×n!

n
N		3.6×10^7	5×10^19
час		6 хв.	1.4×10^11год~5×10^9діб

Якщо швидкодія 100000 оп/сек. Тому звичайні методи для обчислення визначника малоефективні. Тому стараються використовувати більш економні методи. Зручно використовувати прямий хід Гауса, тобто приводити матрицю до трикутного вигляду. Визначник при цьому не міняється, може змінитися тільки його знак і detA= ± а_кк, де а_{кк –} діагональні елементи приведеної до ∆-вигляду матриці. Добуток береться зі знаком,,+’’, якщо кількість переставлених рядків парна, і,,-’’, якщо непарна (при приведенні до ∆-вигляду).

Обчислення оберненої матриці

1 k=j

a_ik× z_kj = d_ij 0 i¹j

Для отримання оберненої матриці треба n-раз розв’язати початкову систему. Після кожного розв’язку системи знаходиться один стовпчик оберненої матриці. Наприклад, для знаходження стовпчика оберненої матриці номер j, тобто z_1j,…,z_nj треба розв’язати систему таких лінійних рівнянь:

a₁₁z_1j + a₁₂z_2j +…+ a_1nz_nj = 0

.

.

.

a_j1z1j + a_j2z_2j +…+ a_jnz_nj = 1 (2)

.

.

.

a_n1z_1j + a_n2z_2j +…+ a_nnz_nj = 0

Щоб уникнути цього використовують модифікацію метода Гауса. Одну з таких модифікацій називають методом Гауса з вибором головного елемента в стовпці. Його відмінність від розглянутого метода Гауса в тому, що на кожному кроці шукається максимальний елемент в стовпці. Нехай на кожному кроці отримується діагональний елемент а_кк^(к-1). Серед всіх елементів, які лежать вище шукаємо max: max a_к^(к-1).

Нехай цей елемент в рівнянні а_рк^(к-1). Міняємо місцями р і k-е рівняння. Цю операцію повторюють на кожному кроці.

В ролі невідомих виступає стовпчик z_ij. В правій частині один стоїть тільки в z=j. Таких систем треба записати n-штук. Тут зручно проводити обчислення так як матриця a_ij – не міняється. Тому до трикутного вигляду систему приводять один раз. Для знаходження відповідного стовпчика використовують обернений хід методу Гауса. Цей метод ефективніший ніж метод:

(a_ij)^-1 = _, де A_ji – алгебраїчне доповнення до a_ij в початковій матриці. Таким методом для знаходження оберненої матриці треба виконати ~ n²n! операцій. А описаний метод з розв'язком систем лінійних рівнянь вимагає тільки ~ в 3 рази більше арифметичних операцій ніж приведення системи до трикутного вигляду.

Важливим є питання точності отриманих розв’язків. Її характеризують двома величинами:

Похибка, яка рівна різниці між отриманим розв’язком і точним. При практичному розв’язуванні систем лінійних рівнянь за характеристику точності беруть нев’язку (величина, що дорівнює різниці між правою і лівою частиною рівняння, в яке підставляються розв’язки). Похибка e і нев’язка r взаємозв’язані. Якщо e = 0, то r = 0. Але обернене твердження не завжди справедливе. Нев’язка в практичних розрахунках повинна бути ~ 10^-4 ¸ 10^-6.

Метод ітерацій

Цей метод дозволяє отримати збіжну послідовність наближених значень. Не потрібно контролювати проміжні обчислення, тому що окремі помилки на будь-якому кроці ітерацій не деформують кінцевий результат, хоч можуть процес обчислення зробити довшим, тобто це метод – самовиправляючий.

a_ijx_j = b_i, a_ii ≠ 0, визначник системи ≠ 0

Виразимо з першого рівняння x₁, з другого x₂ і т.д. Поділивши рівняння на а_іі отримаємо еквівалентну систему:

x₁ = β₁+α₁₂x₂+α₁₃x₃+…+α_1nx_ni

x₂ = β₂+α₂₁x₂+α₂₃x₃+…+α_2nx_n

…

x_n = β_n+α_n1x₂+α_n2x₃+…+α _n,n-1x_n-1, де

- a_ij /a_ii, при i ≠ j

β_i = b_i/ a_ii; α_i =

0, при i = j

або x_i = β_i + α_ijx_j (*)

назвемо її системою нормального виду.

Будемо розв'язувати її методом послідовних наближень. За нульове наближення візьмемо:

x₁⁽⁰⁾ = β₁

x₂⁽⁰⁾ = β₂

…

x_n⁽⁰⁾ = β_n

і підставимо в праву частину (*). Отримаємо:

x_i⁽¹⁾ = β_i + α_ijx_j⁽⁰⁾, потім аналогічно

x_i⁽²⁾ = β_i + α_ijx_j⁽¹⁾

Робочі формули методу ітерацій

x_i⁽⁰⁾ = β_i

x_i^(k+1) = β_i + α_ijx_j^(k)

α_ii = 0; i= 1,n; k=0,1,2,…

Збіжність?! Якщо ‌|α_ij| < 1 (i=1,n) або |а_ij| > ‌|а_ij| (i=1,n), то метод ітерацій для всіх рядків буде збіжним.

При обчисленні на машині процес ітерації закінчують, якщо

|x - x | ≤ •ε (i=1, n)

q= ‌|α_ij| < 1

Доводять, що тоді |x - x | ≤ ε

Дата добавления: 2015-05-23