Розв'язок системи лінійних рівнянь використовуючи метод обертань

Метод Гаусса являється не єдиним методом який для розв'язку системи лінійних рівнянь використовує ідею зведення матриці коефіцієнтів до трикутного вигляду. Існує ще два методи, які можна віднести до категорії методів виключення невідомих, а саме метод обертань та метод відображень. Обидва цих методи базуються на представленні матриці qr_rozklad_matruci51 у вигляді добутку ортогональної матриці qr_rozklad_matruci52 та верхньої трикутної матриці qr_rozklad_matruci45. Нагадаємо, що матриця qr_rozklad_matruci52 називається ортогональною, якщо для неї виконується наступна умова: QR розклад матриці або qr_rozklad_matruci2.

Розглянемо спочатку метод обертань з допомогою якого будемо відшукувати розв'язок системи лінійних рівнянь наступного виду:

qr_rozklad_matruci3

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

Прямий хід методу обуртання.

На першому етапі прямого ходу здійснюємо виключення невідомої qr_rozklad_matruci4 з усіх рівнянь системи (1) крім першого. Для виключення qr_rozklad_matruci4 з другого рівняння обчислюють наступні коефіцієнти:

qr_rozklad_matruci5

для яких обов'язковою вимогою є виконання наступних умов qr_rozklad_matruci6. Після цього, перше рівняння системи (1) замінюють лінійною комбінацією першого і другого рівняння з коефіцієнтами qr_rozklad_matruci7 та qr_rozklad_matruci8, а друге рівняння — аналогічною лінійною комбінацією з коефіцієнтами qr_rozklad_matruci9 та qr_rozklad_matruci7. В результаті виконання даних дій система (1) набуде наступного вигляду:

qr_rozklad_matruci10

де qr_rozklad_matruci11.

Неважко переконатися, що перетворення системи (1) до виду (4) еквівалентно множенню зліва матриціqr_rozklad_matruci51 і вектора qr_rozklad_matruci53 на матрицю qr_rozklad_matruci15, де

qr_rozklad_matruci16

Виходячи з того, що коефіцієнти qr_rozklad_matruci7 і qr_rozklad_matruci8 матриці qr_rozklad_matruci15 підібрані таким чином, що qr_rozklad_matruci56, то їх можна представити наступним чином: qr_rozklad_matruci57. Тоді матриця qr_rozklad_matruci15 являтиме собою матрицю обертання на кут qr_rozklad_matruci58 в площині qr_rozklad_matruci59. Неважко догадатися, що саме з таких міркувань появилась назва даного методу.

Відмітимо, що у випадку коли коефіцієнт qr_rozklad_matruci12 здійснювати виключення невідомої qr_rozklad_matruci4 з другого рівняння системи немає необхідності. В цьому випадку покладають, що qr_rozklad_matruci13 і qr_rozklad_matruci14.

Далі переходимо до виключення невідомої qr_rozklad_matruci4 з третього рівняння. Для цього, як і на попередньому кроці, обчислюємо коефіцієнти виду:

qr_rozklad_matruci17

для яких також повинні виконуватись наступні умови qr_rozklad_matruci18. Після цього, перше рівняння системи (4) замінюємо лінійною комбінацією першого і третього рівняння з коефіцієнтами qr_rozklad_matruci19 та qr_rozklad_matruci20 і третє рівняння — аналогічною лінійною комбінацією з коефіцієнтами qr_rozklad_matruci21 та qr_rozklad_matruci19. Таким чином ми отримали систему, значення коефіцієнтів при невіломій qr_rozklad_matruci4 у другому і третьому рівнянні рівні нулю. Дане перетворення системи еквівалентне множенню зліва її матриці коефіцієнтів на наступну матрицю обертання:

qr_rozklad_matruci22

Аналогічним чином проводимо виключення невідомої qr_rozklad_matruci4 з решти рівнянь системи. В результаті виконання першого етапу, який складається з qr_rozklad_matruci23-го кроку система (1) зводиться до наступного вигляду:

qr_rozklad_matruci24

або у матрично-векторній формі qr_rozklad_matruci25, де qr_rozklad_matruci26.

Далі переходимо до другого етапу (складається  з qr_rozklad_matruci36-х кроків) з допомогою якого з рівнянь під номерами qr_rozklad_matruci38 системи (7)  здійснюємо виключення невідомої qr_rozklad_matruci37. Для цього, кожне qr_rozklad_matruci55-те рівняння замінюють лінійною комбінацією qr_rozklad_matruci55-го рівняння з другим. В результаті виконання даного етапу система (7) прийме наступний вигляд:

qr_rozklad_matruci39

або qr_rozklad_matruci40, де qr_rozklad_matruci41.

І так далі продовжуючи даний процес, після виконання qr_rozklad_matruci23-го етапу система лінійних рівнянь прийме наступний вигляд:

qr_rozklad_matruci42

або у матрично-векторній формі qr_rozklad_matruci43, де qr_rozklad_matruci44.

Позначивши через qr_rozklad_matruci45 верхню трикутну матрицю, отриману з допомогою прямого ходу методу обертань qr_rozklad_matruci46 (qr_rozklad_matruci47), де qr_rozklad_matruci48 — матриця результуючого обертання, являється ортогональною, як добуток ортогональних матриць. Отримуємо qr_rozklad_matruci50 — розклад матриці qr_rozklad_matruci511, де qr_rozklad_matruci49.

Обернений хід метоту обертань.

Обернений хід метоту обертань здійснюється аналогічно як і у методі Гаусса. Тобто з останнього рівняння системи (9) знаходимо значення невідомої qr_rozklad_matruci60. Після чого решта значень qr_rozklad_matruci62 обчислюють за наступною формулою:

qr_rozklad_matruci63

Розв'язок системи лінійних рівнянь методом обертань — приклад:

Використовуючи метод обертань, знайти розв'язок наступну систему лінійний алгебраїчних рівнянь:

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

Для виключення невідомої qr_rozklad_matruci4 з другого рівняння, скористаємось формулами (2) та обчислемо коефіцієнти qr_rozklad_matruci7 та qr_rozklad_matruci8:

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

Для виключення невідомої qr_rozklad_matruci4 з третього рівняння, за формулами (6), обчислимо коефіцієнти  qr_rozklad_matruci19 та qr_rozklad_matruci20, після чого, перше рівняння системи замінюємо лінійною комбінацією першого і третього рівняння з коефіцієнтами qr_rozklad_matruci19 та qr_rozklad_matruci20 і третє рівняння — аналогічною лінійною комбінацією з коефіцієнтами qr_rozklad_matruci21 та qr_rozklad_matruci19:

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

Для виключення qr_rozklad_matruci37 з третього рівняння системи обчислюємо коефіцієнти , та замінюючи друге і третє рівняння системи їх лінійними комбінаціями з коефіцієнтами  та відповідно, приходимо до системи:

Для виключення qr_rozklad_matruci37 з четвертого рівняння системи, обчислюємо коефіцієнти , , після чого, аналогічним чином, замінюємо друге та четверте рівняння отриманої на попередньому кроці системи, їх лінійними комбінаціями з коефіцієнтами  та відповідно. В результаті отримаємо:

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

Після цього, скориставшись оберненим ходом (формула (10)), послідовно знаходимо:

Блок-схема програмної реалізації методу обертання для розв'язку СЛАР:

qr_rozklad_matruci54

Матеріал був корисним, поділись в соціальних мережах:

Якщо тобі сподобалась дана тема, залиш свій коментар