Розв'язування систем лінійних рівнянь методом Гауса
Таким чином система (12) отримана з (8) застосуванням элементарної матриці перестановок:

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

В результаті отримаємо систему
(13)
або
(14)
Завершальний крок прямого ходу методу Гауса полягає в заміні останнього рівняння системи (14)

що еквівалентно множенню (13) на елементарну нижню трикутну матрицю

Таким чином, для розглянутого прикладу процес виключення Гауса з вибором головного елементу по стовпцю записується так
(15)
По побудові матриця
(16)
є верхньою трикутною матрицею з одиничною головною діагоналлю.
Відмінність
від звичайного
методу Гауса
полягає в тому,
що як співмножники
в (16) разом з
елементарними
трикутними
матрицями
можуть бути
присутніми
елементарні
матриці перестановок
.
Покажемо ще, що з (16) слідує розкладання
PA=LU (17)
L -нижняя трикутна матриця, що має обернену, P - матриця перестановок.
Для цього знайдемо матрицю:
(18)
Матриця
отримується
з матриці
перестановкою
другого і третього
рядків:

Матриця
отримується
з
перестановкою
другого і третього
стовпців

тобто
-нижняя
трикутна матриця,
що має зворотну.т.е.
З (18), враховуючи
рівність
,
отримаємо
(19)
Звідси і з (16) видно, що
![]()
де позначено
.
Оскільки Р-матрица
перестановок
і L-нижняя трикутна
матриця, властивість
(17) доведена. Воно
означає, що
метод Гауса
з вибором головного
елементу по
стовпцю еквівалентний
звичайному
методу Гауса,
застосованому
до матриці РА,
тобто до системи,
отриманої з
початкової
системи перестановкою
деяких рівнянь.
Загальний висновок. Результат, отриманий раніше для дуже приватного прикладу, справедливий і у разі загальної системи рівнянь (1).
А саме, метод Гауса з вибором головного елементу по стовпцю можна записати у вигляді:
(20)
де
- елементарні
матриці перестановок
такі, що
і
-
елементарні
нижні трикутні
матриці.
Звідси, використовуючи співвідношення перестановленості, аналогічні (19), можна показати, що метод Гауса з вибором головного елементу еквівалентний звичайному методу Гауса, застосованому до системи
PAx=Pf (21)
де Р - деяка матриця перестановок.
Теоретичне обгрунтування методу Гауса з вибором головного елементу міститься в наступній теоремі.
ТЕОРЕМА
1. Якщо
то існує матриця
перестановок
Р така, що матриця
РА має відмінні
від нуля кутові
мінори.
Наслідок.
Якщо
то існує матриця
престанавок
Р така, що справедливе
розкладання
РА=LU, (22)
де L- нижня трикутна матриця з відмінними від нуля діагональними елементами і U- верхня трикутна матриця з одиничною головною діагоналлю. В цьому випадку для розв’язання системи (1) можна застосовувати метод Гауса з вибором головного елементу.
1.4 Алгоритм знаходження рангу матриці
Нехай
потрібно обчислити
ранг матриці
розмірів
.
Якщо матриця
нульова, то за
означенням
маємо
.
В іншому випадку
за допомогою
перестановки
рядків і стовпців
матриці добиваємося
того, щоб у лівому
верхньому куті
матриці стояв
ненульовий
елемент. Отже,
вважаємо, що
.
Перший
рядок залишаємо
без змін. До
другого рядка
додаємо перший,
помножений
на число
.
У результаті
другий рядок
приймає вигляд:

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

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

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

Якщо
всі рядки, починаючи
з третього,
нульові, то
,
так як мінор:

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

Сформуємо розширену матрицю:

Прямий хід методу Гауса:
Крок 1.
Розділимо
перший рядок
матриці на
![]()
Отримаємо матрицю наступного вигляду:

Крок 2.
Віднімаємо
від другого
рядка перший
рядок, помножений
на
![]()
Віднімаємо
від третього
рядка перший
рядок, помножений
на
![]()
Отримана модифікована матриця:

Крок 3.
Розділимо
другий рядок
на
:

Крок 4.
Віднімаємо
від третього
рядка другий
рядок, помножений
на
![]()

Крок 5.
Розділимо
третій рядок
матриці на
:

Прямий хід метода Гауса закінчено. Обернений хід метода Гауса. Утворюємо нулі вище головної діагоналі.
Крок 6.
Віднімаємо
від другого
рядка третій,
помножений
на
Віднімаємо
від першого
рядка третій,
помножений
на
:

Крок 7.
Віднімаємо
від першого
рядка другий,
помножений
на
:

Запишемо систему рівнянь по останній розширеній матриці:

Змінні x1, x2, x3 залишемо в лівій частині рівняння, а х4 перенесимо вправо. Остаточний вигляд системи буде такий:

де х4 – вільна змінна.
Дана система рівнянь має безліч розв’язків.
Приклад 2. Розв’яжемо СЛАР методом Гауса в MS Excel:

Цей метод розв'язання систем лінійних рівнянь придатний для розв'язання систем з будь-яким числом рівнянь і невідомих.
Запишемо нашу СЛАР в матричній формі:
![]()

Отже маємо:

Помічений
елемент матриці
,
оскільки він
не дорівнює
нулю отже виключаємо
змінну
і утворюємо
нулі нижче
,
отримуємо
наступну матрицю:

Якщо
ж
,
то потрібно
переставляти
рядки. Вибираємо
перший ненульовий
елемент в стовпчику,
що знаходиться
нижче від
розв’язувального
елемента і
переставляємо
цей рядок на
рядок з нульовим
елементом
![]()
Аналогічно продовжуємо до отримання розв’язку СЛАР. В результаті отримаємо наступну табличку:


Отже в результаті отримали:
,
де
- небазисні
змінні.
Загальний розв’язок системи буде мати наступний вигляд:
,
де
- довільні.
Приклад 3. Розв’язання СЛАР з вибором головного елемента в MS Excel:

Суть даного методу полягає в тому, що на кожному кроці обирається напрямний рядок з максимальним абсолютним значенням розв’язувального елемента. Його перевагами у порівнянні з методом Гауса є те, що в результаті отримаємо меншу накопичену похибку за рахунок ділення напрямних рядків на більші елементи, але для погано обумовлених СЛАР похибка як і в методі Гауса може бути суттєвою.
Знаходження розв’язку за допомогою методу головного елемента описується наступним чином:



Загальний розв’язок системи має вигляд:
,
де
- довільні.
Відповіді отриманні при розв’язуванні ідентичні, але кількість кроків виконаних, при реалізації метода головного елемента, дещо більша ніж в методі Гауса.
2.2 Обчислення рангу матриці
Приклад 4. Знайти ранг матриці:

Розв’язання. Перший рядок залишаємо без змін. Щоб уникнути появи дробів, помножимо другу, третю та четверту рядки на 2:

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

Другу
рядок залишаємо
без змін. На
третьому рядку
додаємо другий,
помножений
на 2. Отримаємо
рядок
.
До
четвертого
рядка додаємо
другий. Отримаємо
нульовий рядок.
Перетворена
матриця має
вигляд:

Поміняємо місцями третій і четвертий стовпчики:

Базисний
мінор матриці