Розв'язування систем лінійних рівнянь методом Гауса
Вступ
Прості математичні задачі малої вимірності, що вивчаються в курсі вищої математики, допускають можливість отримання аналітичних рішень. Складні математичні моделі великої розмірності вимагають застосування чисельних методів.
Чисельні методи — це математичний інструментарій, за допомогою якого математична задача формулюється у вигляді, зручному для розв’язання на комп’ютері. У такому разі говорять про перетворення математичної задачі в обчислювальну задачу. При цьому послідовність виконання необхідних арифметичних і логічних операцій визначається алгоритмом її розв’язання. Алгоритм повинен бути рекурсивним і складатися з відносно невеликих блоків, які багаторазово виконуються для різних вхідних даних.
Слід зазначити, що з появою швидких та потужних цифрових комп’ютерів роль чисельних методів для розв’язання наукових та інженерних задач значно зросла. І хоча аналітичні методи розв’язання математичних задач, як і раніше, дуже важливі, чисельні методи суттєво розширюють можливості розв’язання наукових та інженерних задач, не дивлячись на те, що самі рівняння математичних моделей з ускладненням структури сучасних виробів стають погано обумовленими та жорсткими, що істотно ускладнює їх розв’язування. Узявши виконання рутинних обчислень на себе, комп’ютери звільняють час вченого або інженера для творчості: формулювання задач і генерування гіпотез, аналізу та інтерпретації результатів розрахунку тощо.
Чисельні методи забезпечують системний формалізований підхід до розв’язання математичних задач. Проте за умов їх ефективного використання окрім уміння присутня і деяка частка мистецтва, що залежить від здібностей користувача, оскільки для розв’язання кожної математичної задачі існує декілька можливих чисельних методів і їх програмних реалізацій для різних типів комп’ютерів. На жаль, для обрання ефективного способу розв’язання поставленої задачі лише інтуїції замало, потрібні глибокі знання і певні навички. Існує декілька переконливих причин, що мотивують необхідність глибокого вивчення чисельних методів майбутніми фахівцями у галузі комп’ютерно-системної інженерії та прикладної математики.
Чисельні методи є надзвичайно потужним інструментарієм для розв’язання проблемних задач, що описуються довільними нелінійними диференціально-алгебраїчними рівняннями великої розмірності, для яких в даний час не існує аналітичних рішень. Освоївши такі методи, майбутній фахівець набуває здібностей до системного аналізу через математичне моделювання найскладніших задач сучасної науки і техніки.
У своїй майбутній професійній діяльності такий фахівець у першу чергу орієнтуватиметься на використання пакетів сучасних обчислювальних програм, причому те, наскільки правильно він буде їх застосовувати, безпосередньо залежатиме від знання і розуміння ним особливостей і обмежень, властивих чисельним методам, що реалізовані в пакеті. Може трапитися, що одна й та сама математична задача за допомогою певного програмно-технічного комплексу буде одним фахівцем успішно розв’язана, а іншим — ні, оскільки в сучасних пакетах передбачено їх налагоджування під конкретну задачу.
Може з’ясуватися, що низку задач неможливо розв’язати з використанням наявних пакетів програм. Якщо майбутній фахівець знає чисельні методи і володіє навичками програмування, він буде в змозі самостійно провести розробку необхідного алгоритму і програмно його реалізувати, вбудувавши в обчислювальний комплекс.
Вивчення чисельних методів стимулює освоєння самих комп’ютерів, оскільки найкращим способом навчитися програмувати є написання комп’ютерних програм власноруч. Правильно застосувавши чисельні методи, майбутній фахівець зможе пересвідчитися у тому, що комп’ютери успішно розв’язують його професійні задачі. При цьому він сам відчує вплив похибок обчислень на результат і навчиться контролювати ці похибки.
Вивчення чисельних методів сприяє також переосмисленню і більш глибокому розумінню математики в цілому, оскільки однією із задач чисельних методів є зведення методів вищої математики до виконання простих арифметичних операцій.
Хоча існує безліч чисельних методів, усі вони (як і алгоритми, що їм відповідають) мають багато спільних властивостей і характеристик. Чисельні методи:
передбачають проведення великої кількості рутинних арифметичних обчислень за допомогою рекурсивних співвідношень, що використовуються для організації ітерацій, тобто повторюваних циклів обчислень зі зміненими початковими умовами для поліпшення результату;
направлені на локальне спрощення задачі, коли, наприклад, використовувані нелінійні залежності лінеаризуються за допомогою своїх обчислених похідних або похідні замінюються різницевими апроксимаціями;
значно залежать від близкості початкового наближення (або декількох наближень), необхідного для початку обчислень до розв’язку, від властивостей нелінійних функцій, які використовуються в математичних моделях, що накладає обмеження (для забезпечення єдиного розв’язку) на їх диференційованість, на швидкість зміни функцій та ін.;
Чисельні методи характеризуються:
різною швидкістю збіжності, тобто числом ітерацій, виконання яких необхідне для отримання заданої точності розв’язку;
різною стійкістю, тобто збереженням достовірності розв’язку під час подальших ітерацій;
різною точністю отримуваного розв’язку в разі виконання однакового числа ітерацій або циклів обчислень.
Чисельні методи розрізняються:
за широтою і легкістю застосування, тобто за ступенем своєї універсальності та інваріантності для розв’язання різних математичних задач;
за складністю їх програмування;
за можливостями використання у разі їх реалізації наявних бібліотек функцій і процедур, створених для підтримки різних алгоритмічних мов;
за ступенем чутливості до погано обумовлених (або некоректних) математичних задач, коли малим змінам вхідних даних можуть відповідати великі зміни розв’язку.
1. Теоретична частина
1.1 Метод Гауса
Метод Гауса (або метод послідовного виключення невідомих) застосовний для розв’язання систем лінійних рівнянь, в яких число невідомих може бути або рівно числу рівнянь, або відмінно від нього.
Система т лінійних рівнянь з п невідомими має вигляд:

x1, x2., xn – невідомі.
ai j - коефіцієнти при невідомих.
bi - вільні члени (або праві частини)
Система лінійних рівнянь називається сумісною, якщо вона має розв’язок, і несумісною, якщо вона не має розв’язків.
Сумісна система називається визначеною, якщо вона має єдине розв’язок і невизначеною, якщо вона має незліченну безліч розв’язків.
Дві сумісні системи називаються рівносильними, якщо вони мають одну і ту ж множину розв’язків.
До елементарних перетворень системи віднесемо наступні:
зміна місцями два будь-яких рівнянь;
множення обох частин будь-якого з рівнянь на довільне число, відмінне від нуля;
збільшення до обох частин одного з рівнянь системи відповідних частин іншого рівняння, помножених на будь-яке дійсне число.
Елементарні перетворення переводять систему рівнянь в рівносильну їй.
Для простоти розглянемо метод Гауса для системи трьох лінійних рівнянь з трьома невідомими у разі, коли існує єдиний розв’язок:
Дана система:
(1)
1-й крок методу Гауса.
На першому
кроці виключимо
невідоме х1
зі всіх рівнянь
системи (1), окрім
першого. Хай
коефіцієнт
.
Назвемо його
провідним
елементом.
Розділимо перше
рівняння системи
(1) на а11. Отримаємо
рівняння:
(2)
де

Виключимо х1 з другого і третього рівнянь системи (1). Для цього віднімемо з них рівняння (2), помножене на коефіцієнт при х1 (відповідно а21 і а31).
Система прийме вигляд:
(3)
Верхній індекс (1) указує, що мова йде про коефіцієнтах першої перетвореної системи.
2-ий крок методу Гауса. На другому кроці виключимо невідоме х2 з третього рівняння системи (3).
Хай коефіцієнт
.
Виберемо його
за провідний
елемент і розділимо
на нього друге
рівняння системи
(3), отримаємо
рівняння:
(4)
де

З третього
рівняння системи
(3) віднімемо
рівняння (4),
помножене на
Отримаємо
рівняння:
![]()
Припускаючи,
що
знаходимо:

В результаті перетворень система прийняла вигляд:
(5)
Система вигляду (5) називається трикутною.
Процес приведення системи (1) до трикутного вигляду (5) (кроки 1 і 2) називають прямим ходом методу Гауса.
Знаходження невідомих з трикутної системи називають зворотним ходом методу Гауса.
Для цього знайдене значення х3 підставляють в друге рівняння системи (5) і знаходять х2. Потім х2 і х3 підставляють в перше рівняння і знаходять х1.
У загальному випадку для системи т лінійних рівнянь з п невідомими проводяться аналогічні перетворення. На кожному кроці виключається одне з невідомих зі всіх рівнянь, розташованих нижче провідного рівняння.
Звідси інша назва методу Гауса – метод послідовного виключення невідомих.
Якщо в ході перетворень системи виходить суперечливе рівняння вигляду 0 = b, де b № 0, то це означає, що система несумісна і розв’язків не має.
У разі сумісної системи після перетворень по методу Гауса, складових прямий хід методу, система т лінійних рівнянь з п невідомими буде приведена або до трикутного або до ступінчастого вигляду.
Трикутна система має вигляд:

Така система має єдине рішення, яке знаходиться в результаті проведення зворотного ходу методу Гауса.
Ступінчаста система має вигляд:

Така система має незліченну множину розв’язків. Щоб знайти їх, у всіх рівняннях системи члени з невідомими хk+1., xk переносять в праву частину. Ці невідомі називаються вільними і надають їм довільні значення. З отриманої трикутної системи знаходимо х1., xk, які виражатимуться через вільних невідомих.
1.2 Компактна схема Гауса
Якщо обчислення по схемі єдиного ділення ведуться за допомогою обчислювальних машин, то багато часу затрачається на запис проміжних результатів. Компактна схема Гауса дає економний спосіб запису. Розглянемо порядок складення схеми для системи:

Всі результати обчислення будемо записувати в одну таблицю (Таблиця 1)

Компактна схема Гауса. Таблиця 1.
Порядок заповнення таблиці.
Прямий хід.
Записуємо коефіцієнти даної системи в чотирьох рядках і п’яти стовпцях розділу І таблиці 1.
Додаємо
всі коефіцієнти
по рядку і записуємо
суму в стовпчик
(стовпчик
контролю), наприклад
.
Ділимо
всі числа, які
стоять в першому
рядку, на
і результати
записуємо в
п’ятому рядку
розділу І.
Обчислюємо
і робимо перевірку.
Якщо обчислення
ведуться з
постійним
числом знаків
після коми, то
числа
і
не повинні
відрізнятися
не більше ніж
на одиницю
останнього
розряду. В іншому
випадку потрібно
перевірити
дії пункту 3).
По формулам (2.4) обчислюємо коефіцієнти:
![]()
Результати записуємо в перші три рядки розділу ІІ.
Робимо
перевірку.
Сума елементів
кожного рядка
не повинна
відрізнятися
від
більше чим на
одиницю останнього
розряду (якщо
всі обчислення
ведуться з
постійним
числом знаків
після коми).
Ділимо
всі елементи
першого рядка
розділу ІІ на
і результати
записуємо в
четвертому
рядку розділу
ІІ.
Робимо перевірку, як в пункті 4).
За формулами
(2.7) обчислюємо
Результати
записуємо в
перші два рядки
розділу ІІІ.
Робимо перевірку, як в пункті 6).
Ділимо
елементи першого
рядка розділу
ІІІ на
і знаходимо
числа
.
Всі результати
записуємо в
третьому рядку
розділу ІІІ.
Робимо перевірку.
Обчислюємо
.
Результати
записуємо в
розділі IV.
Обернений хід.
В розділі V записуємо одиниці, як це показано в таблиці 1.
Обчислюємо
![]()
Для обчислення
значення
використовуємо
лише рядки
розділів І,
ІІ, ІІІ, що містять
одиниці, починаючи
з останньої.
Так, для обчислення
помножимо
на
і результати
віднімаємо
з
.
При цьому одиниці,
розставлені
в розділі V,
допомагають
знаходити для
відповідні
коефіцієнти
в помічених
рядках.
Таким чином,
.
Обчислюємо
,
для чого використовуємо
елементи поміченого
рядка розділу
ІІ:
![]()
Обчислюємо
,
для чого використовуємо
елементи поміченого
рядка розділу
І:
![]()
Аналогічно
проводиться
обернений хід
в контрольній
системі. Розв’язок
цієї системи
повинен відрізнятися
від розв’язку
даної системи
на 1 (з точністю
до одиниці
останнього
розряду):
![]()
Цей контроль
здійснюється
за допомогою
стовпця
![]()
Таким же чином реалізується компактна схема Гауса для систем з іншим числом невідомих. Компактна схема Гауса особливо потрібна при одночасному розв’язанні декількох систем, які відрізняються лише стовпцями вільних членів, що має місце, наприклад, при обчисленні елементів оберненої матриці.

Компактна схема Гауса для системи (2.12). Таблиця 2.
1.3 Метод Гауса з вибором головного елемента
Основна ідея методу. Може трапитись, що система
Ax=f (1)
де A - матриця m*m, x = (x1, x2...,xm) - шуканий вектор
f =(f1, f2..., fm) -заданий вектор.
має єдиний розв’язок, хоча який-небудь з кутового мінору матриці А рівний нулю. В цьому випадку звичайний метод Гауса виявляється непридатним, але може бути застосований метод Гауса з вибором головного елементу.
Основна
ідея методу
полягає в тому,
щоб на черговому
кроці виключати
не наступне
по номеру невідоме,
а те невідоме,
коефіцієнт
при якому є
найбільшим
по модулю. Таким
чином, як провідний
елемент тут
вибирається
головний, тобто
найбільший
по модулю елемент.
Тим самим, якщо
,
то в процесі
обчислень не
відбуватиметься
ділення на
нуль.
Різні варіанти методу Гауса з вибором головного елементу проілюструємо на прикладі системи з двох рівнянь:
(2)
![]()
Припустимо,
що
.
Тоді на першому
кроці виключатимемо
змінне
.
Такий прийом
еквівалентний
тому, що система
(2) переписується
у вигляді:
(3)
![]()
і до (3) застосовується перший крок звичайного методу Гауса. Вказаний спосіб виключення називається методом Гауса з вибором головного елементу по рядку. Він еквівалентний застосуванню звичайного методу Гауса до системи, в якій на кожному кроці виключення проводиться відповідна перенумерация змінних.
Застосовується
також метод
Гауса з вибором
головного
елементу по
стовпцю. Припустимо,
що
.
Перепишемо
систему (2) у
вигляді:
![]()
![]()
і до нової системи застосуємо на першому кроці звичайний метод Гауса. Таким чином, метод Гауса з вибором головного елементу по стовпцю еквівалентний застосуванню звичайного методу Гауса до системи, в якій на кожному кроці виключення проводиться відповідна перенумерация рівнянь.
Іноді застосовується і метод Гауса з вибором головного елементу по всій матриці, коли як ведучий вибирається максимальний по модулю елемент серед всіх елементів матриці системи.
Матриці перестановок. Раніше було показано, що звичайний метод Гауса можна записати у вигляді:
![]()
де
-- елементарні
нижні трикутні
матриці. Щоб
отримати аналогічний
запис методу
Гауса з вибором
головного
елементу, необхідно
розглянути
матриці перестановок.
Означення 1. Матрицею перестановок Р називається квадратна матриця, у якої в кожному рядку і в кожному стовпці тільки один елемент відмінний від нуля і рівний одиниці.
Означення
2. Елементарною
матрицею перестановок
називається
матриця, отримана
з одиничної
матриці перестановкою
к-го і l-го рядків.
Наприклад, елементарними матрицями перестановок третього порядку є матриці:

Можна відзначити наступні властивості елементарних матриць перестановок, витікаючі безпосередньо з їх визначення.
Добуток двох (а отже, і будь-якого числа) елементарних матриць перестановок є матриця перестановок (не обов'язково елементарною).
Для будь-якої квадратної матриці А матриця відрізняється від А перестановкою к-го і l-го стовпців.
Для будь-якої квадратної матриці А матриця відрізняється від А перестановкою к-го і l-го стовпців.
Застосування елементарних матриць перестановок для опису методу Гауса з вибором головного елементу по стовпцю можна пояснити на наступному прикладі системи третього порядку:
(4)
Система має вигляд (1), де
(5)
Максимальний елемент першого стовпця матриці А знаходиться в другому рядку. Тому треба поміняти місцями другий і перший рядки і перейти до еквівалентної системи
(6)
Систему (6) можна записати у вигляді
(7)
тобто вона виходить з системи (4) шляхом множення на матрицю перестановок

Далі, до системи (6) треба застосувати перший крок звичайного методу виключення Гауса. Цей крок еквівалентний множенню системи (7) на елементарну нижню трикутну

В результаті від системи (7) перейдемо до еквівалентної
(8)
або в розгорненому вигляді:
(9)
З останніх
двох рівнянь
системи (9) треба
тепер виключити
змінне
.
Оскільки максимальним
елементом
першого стовпця
укороченої
системи
(10)
є елемент другого рядка, робимо в (10) перестановку рядків і тим самим від системи (9) переходимо до еквівалентної системи, яку можна записати в матричному вигляді як: