Системи лінійних алгебраїчних рівнянь

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

(1)

яка може бути записана в матричному вигляді

де

–

прямокутна матриця розмірності , яка має m рядків і n стовпчиків,

– вектор-рядок n-го порядку, який отримують із матриці при m = 1;

– вектор-стовпчик m-го порядку, який також отримують із матриці при n = 1.

Матриця

яка отримана з матриці А додаванням стовбцю вільних членів, називається розширеною.

Розв’язанням системи (1) називається така упорядкована сукупність чисел , яка обертає всі рівняння системи в вірні рівності.

Система лінійних рівнянь називається сумісною, якщо вона має хоча б одне рішення, і несумісною (суперечливою), якщо вона не має рішень.

Сумісна система називається визначеною, якщо вона має єдине рішення, невизначеною, якщо існує більше одного рішення.

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

Система лінійних алгебраїчних з n невідомими, яка має неособливу матрицю А, сумісна і має єдине рішення.

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

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

Метод Гауса

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

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

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

(2)

Метод Гауса розв’язання системи (2) – це метод послідовного виключення невідомих. Суть його полягає в перетворенні системи (2) до еквівалентної системи, що має вигляд трикутної матриці (прямий хід), із якої потім послідовно (зворотним ходом) розраховують значення всіх невідомих.

Відмінність визначника системи від нуля є необхідною та достатньою умовою існування єдиного рішення системи (2). Якщо визначник системи дорівнює нулю, то система або не має рішення, або має безліч рішень.

Якщо визначник системи близький до нуля, кажуть, що система погано обумовлена. В подібному випадку знайти числове рішення системи важко, а його точність сумнівна.

Розглянемо загальну схему методу Гауса для систем, які мають єдине рішення.

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

(3)

де

Помножимо рівняння (3) на а₂₁ і віднімемо отримане рівняння із другого рівняння системи (2). Аналогічно перетворимо інші рівняння. В результаті цих операцій система рівнянь набуде вигляду:

(4)

де …,

У випадку, коли деякий з коефіцієнтів виявиться рівним нулю, то j-е рівняння системи (2) увійде до системи (4) без зміни, тобто .

Тепер, залишивши без зміни перше рівняння системи (4), можна взяти за основу друге рівняння і застосувати описану процедуру до системи з (n – 1) рівнянь, виключивши невідоме х₂ з третього та наступних рівнянь. Отримаємо систему наступного вигляду

(4)

де ,

Продовжуючи аналогічні перетворення, приводимо матицю (2) до еквівалентної системи

(5)

в якій матриця із коефіцієнтів має трикутний вигляд.

На цьому прямий хід розв’язання системи лінійних рівнянь методом Гауса закінчується.

При оберненому ході відбувається послідовне виключення невідомого x_n , починаючи з (n – 1)-го рівняння. Отримуємо

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

На початку першого кроку прямого ходу серед коефіцієнтів а_і₁ (і = 1, 2, …, n) при невідомому х₁ знаходять найбільший за модулем. Припустимо, що це а_j₁. Після цього в системі рівнянь (2) виконують перестановку: перше рівняння ставлять на місце j-го, а j-е на місце першого. Далі обчислення проводять в послідовності, описаній вище.

На початку другого кроку прямого ходу максимальний за модулем елемент вибирають серед коефіцієнтів а_і₂ (і = 2, 3, …, n) при невідомому х₂, знову можлива відповідна перестановка та виключення невідомого х₂, починаючи з третього рівняння, і аж до останнього кроку прямого ходу в методі Гауса.

Зауважимо, що процедура прямого ходу в методі Гауса може призвести не до трикутної матриці (5), а до двох випадків:

1) кількість перетворених рівнянь системи менше кількості невідомих (це відбувається, якщо в процесі перетворень отримується тотожність ) – тоді система має нескінченну множину рішень;

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

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

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

(6)

Якщо всі діагональні коефіцієнти (і = 1, 2, …, n), то систему (6) можна подати в так званому приведеному вигляді

(7)

де

Введемо позначення

и перепишемо систему (7) у вигляді єдиного матричного рівняння

(8)

де добуток матриці а на вектор х.

Послідовні наближення (ітерації) знаходимо наступним чином. Візьмемо за початкове наближення х⁽⁰⁾ вектор β і підставимо його в праву частину (8); отримуємо х⁽¹⁾. Продовжуючи аналогічні обчислення, приходимо до векторної послідовності наближень

– перше наближення,

– друге наближення,

……………… (9)

– (k + 1)-е наближення.

……………………………………………

Якщо існує границя ξ послідовності векторів , то переходячи до границі в рівності при , переконуємося, що ξ є рішенням рівняння (8), тобто

Достатньою умовою збіжності ітерацій до рішення є наступна теорема.

Теорема. Якщо будь-яка норма матриці менше одиниці , то рівняння (8) має єдине рішення ξ, до якого прагне послідовність ітерацій при будь-якому виборі початкового наближення х⁽⁰⁾.

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

Метод Зейделя є деякою модифікацією методу послідовних наближень. Знову розглянемо систему лінійних рівнянь (1) та еквіваленту їй приведену систему (7). При розв’язанні системи (7) методом простої ітерації кожний крок складається в переході від вже існуючого наближення значень невідомих до нового (чергового) наближення. В методі Зейделя при розрахунку (k + 1)-го наближення невідомого х_і враховуються вже знайдені раніше (k + 1)-е наближення невідомих х₁, х₂, …, х_n.

Для розв’язання системи (1) вибираємо довільне початкове наближення коренів і підставляємо в перше рівняння системи (1):