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

де

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

Означення 1. Матрицею перестановок Р називається квадратна матриця, у якої в кожному рядку і в кожному стовпці тільки один елемент відмінний від нуля і рівний одиниці.

Означення 2. Елементарною матрицею перестановок

називається матриця, отримана з одиничної матриці перестановкою к-го і l-го рядків.

Наприклад, елементарними матрицями перестановок третього порядку є матриці:

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

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

2) Для будь-якої квадратної матриці А матриця відрізняється від А перестановкою к-го і l-го стовпців.

3) Для будь-якої квадратної матриці А матриця відрізняється від А перестановкою к-го і l-го стовпців.

Застосування елементарних матриць перестановок для опису методу Гауса з вибором головного елементу по стовпцю можна пояснити на наступному прикладі системи третього порядку:

(4)

Система має вигляд (1), де

(5)

Максимальний елемент першого стовпця матриці А знаходиться в другому рядку. Тому треба поміняти місцями другий і перший рядки і перейти до еквівалентної системи

(6)

Систему (6) можна записати у вигляді

(7)

тобто вона виходить з системи (4) шляхом множення на матрицю перестановок

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

В результаті від системи (7) перейдемо до еквівалентної

(8)

або в розгорненому вигляді:

(9)

З останніх двох рівнянь системи (9) треба тепер виключити змінне

. Оскільки максимальним елементом першого стовпця укороченої системи

(10)

є елемент другого рядка, робимо в (10) перестановку рядків і тим самим від системи (9) переходимо до еквівалентної системи, яку можна записати в матричному вигляді як:

. (12)

Таким чином система (12) отримана з (8) застосуванням элементарної матриці перестановок:

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

В результаті отримаємо систему

(13)

або

(14)

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

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

Таким чином, для розглянутого прикладу процес виключення Гауса з вибором головного елементу по стовпцю записується так

(15)

По побудові матриця

(16)

є верхньою трикутною матрицею з одиничною головною діагоналлю.

Відмінність від звичайного методу Гауса полягає в тому, що як співмножники в (16) разом з елементарними трикутними матрицями

можуть бути присутніми елементарні матриці перестановок .

Покажемо ще, що з (16) слідує розкладання

PA=LU (17)

L -нижняя трикутна матриця, що має обернену, P - матриця перестановок.

Для цього знайдемо матрицю:

(18)

Матриця отримується з матриці

перестановкою другого і третього рядків:

Матриця отримується з

перестановкою другого і третього стовпців

тобто

-нижняя трикутна матриця, що має зворотну.т.е.

З (18), враховуючи рівність

, отримаємо

(19)

Звідси і з (16) видно, що

де позначено

. Оскільки Р-матрица перестановок і L-нижняя трикутна матриця, властивість (17) доведена. Воно означає, що метод Гауса з вибором головного елементу по стовпцю еквівалентний звичайному методу Гауса, застосованому до матриці РА, тобто до системи, отриманої з початкової системи перестановкою деяких рівнянь.

3. Загальний висновок. Результат, отриманий раніше для дуже приватного прикладу, справедливий і у разі загальної системи рівнянь (1).

А саме, метод Гауса з вибором головного елементу по стовпцю можна записати у вигляді:

(20)

де

- елементарні матриці перестановок такі, що і - елементарні нижні трикутні матриці.

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

PAx=Pf (21)

де Р - деяка матриця перестановок.

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

ТЕОРЕМА 1. Якщо

то існує матриця перестановок Р така, що матриця РА має відмінні від нуля кутові мінори.

Наслідок. Якщо

то існує матриця престанавок Р така, що справедливе розкладання

РА=LU, (22)

де L- нижня трикутна матриця з відмінними від нуля діагональними елементами і U- верхня трикутна матриця з одиничною головною діагоналлю. В цьому випадку для розв’язання системи (1) можна застосовувати метод Гауса з вибором головного елементу.

1.4 Алгоритм знаходження рангу матриці

Нехай потрібно обчислити ранг матриці

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

Перший рядок залишаємо без змін. До другого рядка додаємо перший, помножений на число

. У результаті другий рядок приймає вигляд:

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

. У результаті третій рядок приймає вигляд:

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