Розв'язування систем лінійних рівнянь методом Гауса

Вступ

Прості математичні задачі малої вимірності, що вивчаються в курсі вищої математики, допускають можливість отримання аналітичних рішень. Складні математичні моделі великої розмірності вимагають застосування чисельних методів.

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

Слід зазначити, що з появою швидких та потужних цифрових комп’ютерів роль чисельних методів для розв’язання наукових та інженерних задач значно зросла. І хоча аналітичні методи розв’язання математичних задач, як і раніше, дуже важливі, чисельні методи суттєво розширюють можливості розв’язання наукових та інженерних задач, не дивлячись на те, що самі рівняння математичних моделей з ускладненням структури сучасних виробів стають погано обумовленими та жорсткими, що істотно ускладнює їх розв’язування. Узявши виконання рутинних обчислень на себе, комп’ютери звільняють час вченого або інженера для творчості: формулювання задач і генерування гіпотез, аналізу та інтерпретації результатів розрахунку тощо.

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

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

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

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

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

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

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

 передбачають проведення великої кількості рутинних арифметичних обчислень за допомогою рекурсивних співвідношень, що використовуються для організації ітерацій, тобто повторюваних циклів обчислень зі зміненими початковими умовами для поліпшення результату;

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

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

Чисельні методи характеризуються:

 різною швидкістю збіжності, тобто числом ітерацій, виконання яких необхідне для отримання заданої точності розв’язку;

 різною стійкістю, тобто збереженням достовірності розв’язку під час подальших ітерацій;

 різною точністю отримуваного розв’язку в разі виконання однакового числа ітерацій або циклів обчислень.

Чисельні методи розрізняються:

 за широтою і легкістю застосування, тобто за ступенем своєї універсальності та інваріантності для розв’язання різних математичних задач;

 за складністю їх програмування;

 за можливостями використання у разі їх реалізації наявних бібліотек функцій і процедур, створених для підтримки різних алгоритмічних мов;

 за ступенем чутливості до погано обумовлених (або некоректних) математичних задач, коли малим змінам вхідних даних можуть відповідати великі зміни розв’язку.

1. Теоретична частина

1.1 Метод Гауса

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

Система т лінійних рівнянь з п невідомими має вигляд:

x1, x2., xn – невідомі.

ai _j - коефіцієнти при невідомих.

bi - вільні члени (або праві частини)

Система лінійних рівнянь називається сумісною, якщо вона має розв’язок, і несумісною, якщо вона не має розв’язків.

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

Дві сумісні системи називаються рівносильними, якщо вони мають одну і ту ж множину розв’язків.

До елементарних перетворень системи віднесемо наступні:

1.   зміна місцями два будь-яких рівнянь;

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

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

Елементарні перетворення переводять систему рівнянь в рівносильну їй.

Для простоти розглянемо метод Гауса для системи трьох лінійних рівнянь з трьома невідомими у разі, коли існує єдиний розв’язок:

Дана система:

(1)

1-й крок методу Гауса.

На першому кроці виключимо невідоме х₁ зі всіх рівнянь системи (1), окрім першого. Хай коефіцієнт . Назвемо його провідним елементом. Розділимо перше рівняння системи (1) на а11. Отримаємо рівняння:

(2)

де

Виключимо х₁ з другого і третього рівнянь системи (1). Для цього віднімемо з них рівняння (2), помножене на коефіцієнт при х₁ (відповідно а₂₁ і а₃₁).

Система прийме вигляд:

 (3)

Верхній індекс (1) указує, що мова йде про коефіцієнтах першої перетвореної системи.

2-ий крок методу Гауса. На другому кроці виключимо невідоме х₂ з третього рівняння системи (3).

Хай коефіцієнт . Виберемо його за провідний елемент і розділимо на нього друге рівняння системи (3), отримаємо рівняння:

(4)

де

З третього рівняння системи (3) віднімемо рівняння (4), помножене на Отримаємо рівняння:

Припускаючи, що  знаходимо:

В результаті перетворень система прийняла вигляд:

(5)

Система вигляду (5) називається трикутною.

Процес приведення системи (1) до трикутного вигляду (5) (кроки 1 і 2) називають прямим ходом методу Гауса.

Знаходження невідомих з трикутної системи називають зворотним ходом методу Гауса.

Для цього знайдене значення х₃ підставляють в друге рівняння системи (5) і знаходять х_2. Потім х₂ і х₃ підставляють в перше рівняння і знаходять х_1.

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

Звідси інша назва методу Гауса – метод послідовного виключення невідомих.

Якщо в ході перетворень системи виходить суперечливе рівняння вигляду 0 = b, де b ¹ 0, то це означає, що система несумісна і розв’язків не має.

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

Трикутна система має вигляд:

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

Ступінчаста система має вигляд:

Така система має незліченну множину розв’язків. Щоб знайти їх, у всіх рівняннях системи члени з невідомими х_k+1., x_k переносять в праву частину. Ці невідомі називаються вільними і надають їм довільні значення. З отриманої трикутної системи знаходимо х₁., x_k, які виражатимуться через вільних невідомих.