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

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

Зазначимо, що такі нижня і верхня трикутні матриці існують лише в тому вмпадку, якщо всі кутові мінори (також називають головними мінорами) квадратної матриці A відмінні від нуля. Якщо елементи діагоналі однієї з трикутних матриць фіксовані (ненульові), то таке розкладання єдине.

Нагадаємо, що кутовими мінорами матриці A порядку n називаються визначники наступного вигляду:

Кутові мінори матриці A розмірності nxn

Зауваження: довільна невироджена матриця A перестановкою рядків (стовпців) може бути приведена до матриці з відмінними від нуля кутовими мінорами.

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

Система лінійних рівнянь

де A квадратна матриця порядку n і x та b – вектори стовпці.

Згідно з сказаним вище, матрицю коефіцієнтів A представимо у вигляді добутку нижньотрикутної матриці L і верхньотрикутної матриці U з одиничною діагоналлю, тобто lu розкладання матриці, де

Матриці l та u

Тоді, рівняння (1) можна записати у наступному вигляді:

Метод lu-розкладу формула

Ввівши у розгляд змінну y = U * x, рівність (3) перепишемо наступним чином: L * y = b.

Звідси, шуканий вектор x може бути знайдений із ланцюга рівнянь L * y = b; U * x = y, які виходячи з того, що матриці L та U – трикутні, легко розв’язуються за наступними формулами:

Метод lu-розкладу формули

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

Отже, врахувавши рівність (2), послідовно перемножимо рядки матриці L на стовпці матриці U. В результаті отримаємо систему, яка складається з n ^ 2 рівнянь та n ^ 2 невідомих lij і uij:

Метод lu-розкладу формули

Розв’язавши дану систему, отримаємо розрахункові формули для знаходження елементів матриць L та U:

Метод lu-розкладу формули

Приклад 1: використовуючи метод-LU факторизації, розв’язати систему рівнянь наступного вигляду:

Система 2 лінійних рівнянь з 2 невідомими

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

Коефіцієнти матриць lu розкладання

Таким чином, рівність (2), у даному випадку, виглядає так:

lu розкладання матриці

На наступному кроці, використовуючи формули (5), знаходимо розв’язок системи рівнянь виду L * y = b:

y1 = 1; y2 = 2;

Далі, за формулами (6), знайдемо розв’язок системи рівнянь U * x = y, який і приймаємо в якості рішення заданої системи:

x2 = 2; x1 = 5;

Скориставшись онлайн калькулятором, перевіримо правельність отриманих результатів:

Метод lu розкладу онлайн

Розв’язок системи рівнянь використовуючи метод LU-розкладу онлайн

Приклад 2: розв’язати ситему рівнянь:

Система 3 лінійних рівнянь з 3 невідомими

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

lu розкладання матриці коефіцієнтів

Далі, використовуючи формули (5), знайдемо розв’язок системи рівнянь L * y = b, після чого, розв’язавши систему U * x = y (розрахункові формули (6)), отримаємо шуканий вектор x:

y1 = -0.4; y2 = 0.538; y3 = -1.784; x3 = -1.784; x2 = 2.459; x1 = 1.432;

Приклад 3: розв’язати систему рівнянь наступного вигляду:

Система 4 лінійних рівнянь з 4 невідомими

Отже, скориставшись формулами (8), отримаємо LU розкладання матриці коефіцієнтів:

lu розкладання матриці коефіцієнтів

Далі, використовуючи формули (5), знаходимо розв’язок системи лінійних рівнянь виду L * y = b:

y1 = 20; y2 = 3.6; y3 = 0.7; y4 = -1;

Після цього, за формулами (6), отримаємо розв’язок системи рівнянь U * x = y, а відповідно, і рішення заданої системи:

x4 = -1; x3 = 1; x2 = 2; x1 = 3;

  1. На які дві групи діляться чисельні методи розв’язання систем лінійних рівнянь?
  2. До якої групи відноситься метод розв’язку систем рівнянь, що базується на LU-розкладанні матриці системи?
  3. У чому полягає метод LU-розкладу?
  4. Чи для будь-якої матриці існує LU-розкладання?
  5. Скільки різноманітних LU-розкладів існує для матриці?
  6. Якщо знайдено LU-розкладання матриці A, то за якою схемою здійснюється подальше рішення системи A * x = b з довільною правою частиною b?

Блок-схема алгоритму знаходження розв’язку системи лінійних рівнянь методом LU-розкладу

Метод lu факторизації блок-схема

Залишити коментар

Your email address will not be published. Required fields are marked *

*