Бінарна алгебраїчна операція
Химия

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


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

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

Основна ідея методу. Може виявитися, що система

Ax=f (1)

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

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

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

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

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

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

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

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

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

Застосовується також метод Гауса з вибором головного елемента стовпця. Припустимо, що
Метод Гаусса з вибором головного елемента. Перепишемо систему (2) у вигляді

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

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

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

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

Матриці перестановок. Раніше було показано, що звичайний метод Гауса можна записати як

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

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

ВИЗНАЧЕННЯ 1. Матрицею перестановок Р називається квадратна матриця, яка у кожному рядку й у кожному стовпці лише один елемент відрізняється від нуля і дорівнює одиниці.

ВИЗНАЧЕННЯ 2. Елементарною матрицею перестановок
Метод Гаусса з вибором головного елементаназивається матриця, отримана з одиничної матриці перестановкою к-й та l-й рядків.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

перестановок

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

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

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

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

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

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

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

З останніх двох рівнянь системи (9) треба тепер виключити змінне
Метод Гаусса з вибором головного елемента. Оскільки максимальним елементом першого стовпця укороченої системи

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

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

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

яку можна записати в матричному вигляді

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

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

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

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

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

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

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

або

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

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

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

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

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

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

вигляді

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

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

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

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

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

Покажемо ще, що з (16) випливає розкладання

PA = LU, (17)

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

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

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

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

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

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

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

тобто.
Метод Гаусса з вибором головного елемента-нижня трикутна матриця, що має обернену.

З (18), враховуючи рівність
Метод Гаусса з вибором головного елемента, отримаємо

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

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

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

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

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

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

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

де
Метод Гаусса з вибором головного елемента— елементарні матриці перестановок такі, що

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

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

PAx = Pf, (21)

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

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

ТЕОРЕМА 1. Якщо
Метод Гаусса з вибором головного елементато існує матриця перестано-

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

нори.

Доказ у п.4.

СЛІДСТВО. Якщо
Метод Гаусса з вибором головного елементато існує матриця преста-

вок Р така, що справедливе розкладання

РА = LU, (22)

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

4. Доказ теореми 1. Доведемо теорему індукцією за кількістю m-порядку матриці А.

Нехай m = 2, тобто.

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

Якщо
Метод Гаусса з вибором головного елемента то твердження теореми виконується за Р=Е, де Е — одинична матриця другого порядку. Якщо
Метод Гаусса з вибором головного елемента, то
Метод Гаусса з вибором головного елемента, т.к.
Метод Гаусса з вибором головного елементаПри цьому у матриці

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

всі кутові мінори відмінні від нуля.

Нехай затвердження теореми правильне будь-яких квадратних матриць порядку m-1. Покажемо, що воно правильне і для матриць порядку m. Розіб’ємо матрицю А порядку m на блоки

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

де

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

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

Достатньо розглянути два випадки:Метод Гаусса з вибором головного елемента і
Метод Гаусса з вибором головного елемента. У першому випадку, за припущенням індукції, існує матриця перестановок.
Метод Гаусса з вибором головного елементапорядку m-1 така, що
Метод Гаусса з вибором головного елементамає відмінні від нуля кутові мінори. Тоді для матриці перестановок

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

маємо

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

причому
Метод Гаусса з вибором головного елемента. Тим самим усі кутові мінори матриці РА відмінні від нуля.

Розглянемо другий випадок, колиМетод Гаусса з вибором головного елемента . Т.к.Метод Гаусса з вибором головного елемента , знайдеться хоча б один відмінний від нуля мінор порядку m-1 матриці А, отриманий викреслюванням останнього стовпця і рядка. Нехай, наприклад,

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

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

Переставляючи у матриці А рядки з номерами l та m, отримаємо матрицю
Метод Гаусса з вибором головного елемента, у якої кутовий мінор порядку m-1 має вигляд

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

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

Теорему доведено.

© Реферат плюс



Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *