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

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

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

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

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

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

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

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

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

Система n лінійних рівнянь з n невідомими

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

Розширена матриця системи

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

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

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

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

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

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

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

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

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

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

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

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

Система 4 лінійних рівнянь з 4 невідомими

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

Розширена матриця системи

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

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

m1 = 0.4; m2 = 0; m3 = 0;

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

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

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

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

    m1 = 0.6; m2 = -0.4;

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

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

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

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

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

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

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

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

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

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

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

Ми в соціальних мережах

Залишити коментар

Your email address will not be published. Required fields are marked *

*