Метод Гаусса з вибором головного елемента

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

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

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

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

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

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

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

Метод виключення Гаусса з вибором головного елемента – опис алгоритму.

Нехай дана система лінійних рівнянь виду (1), для якої потрібно знайти чисельний розв’язок:

Розглянемо розширену прямокутну матрицю, що складається з коєфіціентов системи (1) та її вільних членів:

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

Нехай це буде елемент  (даний елемент, як уже зазначалося вище, називають головним елементом).

Далі, для кожного рядка матриці (2), крім рядка під номером , обчислюємо множники:

На наступному кроці виконуємо насутпні дії: до кожного неголовного рядка розширеної матриці (2) додамо головний рядок (-й рядок матриці ) помножений на відповідний для нього множник :

В результаті отримаємо нову матрицю, -й стовпець якої складається з нульових елементів.

Викреслюючи даний стовпець і-й (головний) рядок, отримаємо матрицю , яка складається з меншого на одиницю числа рядків та стовпців.

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

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

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

Схема з вибором головного елемента – приклади.

Приклад 1: використовуючи метод Гаусса з вибором головного елемента, розв’язати систему рівнянь наступного виду:

Отже, запишемо задану систему у вигляді прямокутної матриці (2):

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

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

На наступному кроці, до кожного неголовного рядка (рядки номером один, два та чотири) матриці  додаємо третій помножений на відповідний для нього множник . Даний процес описується формулою (4):

Далі, викреслюючи четвертий стовпець і третій (головний) рядок, отримаємо матрицю :

Після цього переходимо до етапу номер два, і над отриманою матрицею  повторюємо тіж операції, а саме:

1. вибираємо головний елемент: .
2. для першого та другого рядків матриці обчислюємо множники :

   

1. до кожного неголовного рядка (в даному випадку це будуть рядки під номером один та два) матриці  додаємо головний рядок помножений на відповідний для нього множник . Результатом виконання даного кроку буде матриця виду:

   

1. викреслюючи третій стовпець і третій рядок, отримаємо матрицю :

   

Етап номер три:

1. вибираємо головний елемент: .
2. для другого рядка матриці обчислюємо множник :

   

1. до кожного неголовного рядка матриці  додаємо головний рядок помножений на відповідний множник . Результатом виконання даного кроку буде матриця виду:

   

1. викреслюючи далі другий стовпець і перший рядок з розляду, отримаємо матрицю :

   

На цьому процес приведення матриці до «ступінчастого» вигляду завершується.

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

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

1. Що називається рішенням системи лінійних алгебраїчних рівнянь?
2. Метод Гаусса з вибором головного елемента є точним чи наближеним методом?
3. В чому полягає сенс вибору головного елемен.
4. Чи будь-яку систему лінійних рівнянь можна розв’язати за схемою вибору головного елемента?
5. Чим метод виключення Гаусса з вибором головного елемента відрізняється від методу Гаусса?
6. До якого виду може бути приведена система лінійних алгебраїчних рівнянь в результаті її розв’язку за схемою з вибором головного елемента?
7. Що потрібно виконати для перевірки знайденого рішення?

Блок-схема алгоритму знаходження розв’язку системи лінійних рівнянь методом Гаусса з вибором головного елемента.