ЧИСЕЛЬНІ МЕТОДИ РОЗВ’ЯЗУВАННЯ СИСТЕМ ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ (СЛАР).
СЛАР (системи лінійних алгебраїчних рівнянь) найбільш прості, але в той же час до них зводиться багато задач чисельного аналізу.
Є багато різних способів розв’язку СЛАР.
Методи розв’язування СЛАР, які використовуються на практиці, можна розділити на дві великі групи:
Точні методи характеризуються тим, що з їх допомогою можливо, провівши скінчене число операцій, одержати точні значення невідомих.
При цьому припускається, що коефіцієнти і праві частини системи відомі точно, а всі обчислення здійснюються без заокруглень.
Частіше вони здійснюються в два етапи:
-
на першому етапі перетворюють систему до того чи іншого простого виду;
-
на другому – розв’язують спрощену систему і отримують значення невідомих.
Методи послідовних наближень характеризуються тим, що з самого початку задаються деякими наближеними значеннями невідомих.
Із цих наближених значень тим чи іншим способом отримують нові покращені наближені значення.
З новими наближеними значеннями поступають аналогічно.
При виконанні певних умов можна прийти, після великої кількості кроків, до точного розв’язку.
Метод виключення Гаусса
Найпростішим з точних методів являється метод виключення.
З цим методом ми вже зустрічалися в звичайному шкільному курсі алгебри.
Комбінуючи яким-небудь способом рівняння системи, домагаються того, що у всіх рівняннях, крім одного, буде виключено одне з невідомих. Потім виключають друге невідоме, третє і так далі.
В результаті отримуємо систему з трикутною чи діагональною матрицею, розв’язання якої не викликає труднощів.
Але точність результату і час, затрачений на його отримання, залежать від організації обчислень.
Нехай дана довільна СЛАР (1):
Нехай a11≠0.
Перетворимо систему (1), виключаючи невідоме х1 із всіх рівнянь, крім першого. Для цього обидві частини першого рівняння помножимо на число a21/a11 і від другого рівняння віднімемо це рівняння (від усіх його відповідних частин). Потім обидві частини першого рівняння, помножені на число a31/a11, віднімаються від відповідних частини третього рівняння і так далі.
Ми дійдемо цим шляхом до нової системи з s лінійних рівнянь з n невідомими: (2)
Система (2) еквівалентна системі (1).
Будемо перетворювати систему (2).
Перше рівняння залишаємо без змін. Будемо перетворювати всю систему, крім першого рівняння.
При цьому вважаємо, що серед цих рівнянь немає таких, всі коефіцієнти лівих частин яких дорівнюють нулю. Такі рівняння ми би відкинули, якби їх вільні члени дорівнювали нулю. В протилежному випадку ми би вже довели несумісність нашої системи.
Таким чином, серед коефіцієнтів a'ij є відмінні від нуля, нехай a'22≠0.
Перетворимо тепер систему (2), віднімаючи від обох частин третього і кожного з наступних рівнянь обидві частини другого рівняння, попередньо помноживши відповідно на числа:
Таким чином, буде виключено невідоме х2 із всіх рівнянь, крім першого і другого. Одержимо наступну систему:
Наша система містить тепер t рівнянь, t<=s, бо деякі могли бути відкинуті.
Тепер будемо перетворювати частину системи, яка містить всі рівняння, крім перших двох. Аналогічними діями послідовно виключаємо невідомі.
Якщо ми прийдемо до такої системи, одне з рівнянь якої має відмінний від нуля вільний член, а всі коефіцієнти лівої частини дорівнюють нулю, то наша вихідна система буде несумісною.
В противному випадку ми отримаємо наступну систему рівнянь, еквівалентну системі (1).
Тут
В цьому випадку система (1) сумісна. Вона є визначеною при k = n і невизначеною при k < n. Дійсно, якщо k = n, то система (3) має вид:
З останнього рівняння одержимо цілком певне значення для невідомого хn.
Підставляючи його в передостаннє рівняння, ми знайдемо однозначно визначене хп-1. Продовжуючи аналогічно, знайдемо, що система (4), а отже, і система (1), мають єдиний розв’язок, тобто сумісні і визначені.
Якщо k < n, то для вільних невідомих хk+1…., хn візьмемо довільні числові значення, після чого, рухаючись по системі (3) знизу вверх, знайдемо для невідомих хk, хk-1,…., х2, х1 цілком певні значення.
Так як значення для вільних невідомих можна вибрати нескінченним числом способів, то наша система (3), а, отже, і система (1) будуть сумісними, але невизначеними.
Даним методом (при різноманітних виборах значень для вільних невідомих) будуть знайдені всі розв’язки системи (1).
«Трикутна» форма системи рівнянь (4) або «трапецієдальна» форма системи рівнянь (3) (при k < n), була одержана з припущення, що коефіцієнти а11, а’22,… відмінні від нуля.
В загальному випадку та система рівнянь, до якої прийдемо після доведення до кінця процесу виключення невідомих, буде мати трикутну або трапецієдальну форму лише після необхідної зміни нумерації.
Таким чином, метод Гаусса застосовний до будь-якої системи лінійних рівнянь. При цьому система буде несумісна, якщо в процесі перетворень ми отримаємо рівняння, в якому коефіцієнти при всіх невідомих рівні нулю, а вільний член відмінний від нуля; якщо ж такого рівняння не існує, то система буде сумісною. Сумісна система рівнянь буде визначеною, якщо вона зводиться до трикутного виду (4), і невизначеною, якщо зводиться до трапецієдального виду (3) при k < n.
Цей метод застосовний і до СЛОР, тобто рівнянь, вільні члени яких рівні нулю. Така система завжди сумісна, бо має нульовий розв’язок (0,0,…,0).
Нехай в розглядуваній системі число рівнянь менше числа невідомих. Тоді наша система не може зводитися до трикутного виду, бо в процесі перетворень по методу Гаусса число рівнянь може зменшуватися, але не може збільшуватися; отже, вона зводиться до трапецієдального вигляду, тобто невизначена.
Якщо в СЛОР число рівнянь менше числа невідомих, то ця система має, крім нульового розв’язку, також і ненульові розв’язки, тобто розв’язки, в яких значення деяких (або навіть всіх) невідомих відмінні від нуля; таких розв’язків буде нескінченно багато.
Будемо виписувати матрицю з коефіцієнтів системи, приєднавши до неї стовпчик із вільних членів, відділених вертикальною рискою, і всі перетворення здійснювати над рядками цієї розширеної матриці.
Приклад. Розв’язати систему:
Переходимо до системи:
Отже, наша система має єдиний розв’язок:
х1=2, х2=-3, х3=-1, і значить є сумісною.
Але іноді в чисельних методах використовують модифікований метод Гаусса. Суть його полягає в тому, щоб аналогічними перетвореннями перетворити всі діагональні елементи на одиниці.
Цей спосіб є зручним при складанні алгоритмів та написанні програм для обчислень СЛАР.
Продемонструємо його на цьому ж прикладі:
Одержимо розв’язок: х1=2, х2=-3, х3=-1.
Метод Крамера
Якщо визначник системи
то вона має єдиний розв’язок. Цей розв’язок можна обчислити за формулами Крамера
xk =det Ak / det A, (k=1,2,…,n), де матрицю Ak одержують з матриці А, замінивши її k-вий стовпець стовпцем вільних членів.