Розв'язування систем лінійних рівнянь методом Гауса
Курсовой проект - Математика и статистика
Другие курсовые по предмету Математика и статистика
?ього порядку:
(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) доведена. Воно означає, що метод Гауса з вибором головного елементу по стовпцю еквівалентний звичайному методу Гауса, застосованому до матриці РА, тобто до системи, отриманої з початкової системи перестановкою деяких рівнянь.
- Загальний висновок. Результат, отриманий раніше для дуже приватного прикладу, справедливий і у разі загальної системи рівнянь (1).
А саме, метод Гауса з вибором головного елементу по стовпцю можна записати у вигляді:
(20)
де - елементарні матриці перестановок такі, що і - елементарні нижні трикутні матриці.
Звідси, використовуючи співвідношення перестановленості, аналогічні (19), можна показати, що метод Гауса з вибором головного елементу еквівалентний звичайному методу Гауса, застосованому до системи
PAx=Pf (21)
де Р - деяка матриця перестановок.
Теоретичне обгрунтування методу Гауса з вибором головного елементу міститься в наступній теоремі.
ТЕОРЕМА 1. Якщо то існує матриця перестановок Р така, що матриця РА має відмінні від нуля кутові мінори.
Наслідок. Якщо то існує матриця престанавок Р така, що справедливе розкладання
РА=LU, (22)
де L- нижня трикутна матриця з відмінними від нуля діагональними елементами і U- верхня трикутна матриця з одиничною головною діагоналлю. В цьому випадку для розвязання системи (1) можна застосовувати метод Гауса з вибором головного елементу.
1.4 Алгоритм знаходження рангу матриці
Нехай потрібно обчислити ранг матриці розмірів . Якщо матриця нульова, то за означенням маємо . В іншому випадку за допомогою перестановки рядків і стовпців матриці добиваємося того, щоб у лівому верхньому куті матриці стояв ненульовий елемент. Отже, вважаємо, що .
Перший рядок залишаємо без змін. До другого рядка додаємо перший, помножений на число . У результаті другий рядок приймає вигляд:
Потім до третього рядку додаємо перший рядок, помножений на число . У результаті третій рядок приймає вигляд:
Процес продовжуємо до тих пір, поки не отримаємо нуль на першому місці в останньому рядку. Перетворена матриця має вигляд:
Якщо всі рядки, починаючи з другої, в отриманій матриці нульові, то її ранг дорівнює 1, тому що є мінор першого порядку, відмінний від нуля . В іншому випадку перестановкою рядків і стовпців матриці з номерами більше одиниці, домагаємося, щоб другий елемент другого рядка був відмінний від нуля. Отже, вважаємо, що .
Перший і другий рядки залишаємо без змін. До третього рядка додаємо другий, помножений на число . В результаті отримаємо, що другий елемент третього рядка дорівнює нулю. Потім до четвертого рядка додаємо другий, помножений н