LU-розклад матриці — представлення матриці у вигляді добутку нижньої трикутної матриці та верхньої трикутної матриці.
Квадратна матриця A розміру n може бути представлена у вигляді
де L та U — нижня та верхня трикутна матриця того ж розміру відповідно.
LDU-розклад матриці — це представлення у вигляді
де D — діагональна матриця, а L та U є одиничними трикутними матрицями, тобто, всі їх діагональні елементи рівні одиниці.
LUP-розклад матриці — це представлення в формі
де L та U — нижня та верхня трикутна матриця того ж розміру, а P — матриця перестановки.
Опис
Матриця називається доповненням Шура для щодо
Метод не працює якщо один з тому що відбувається ділення на нуль. Елементи, на які ми ділимо впродовж -розкладу, називаються опорними і перебувають на головній діагоналі матриці Ми використовуємо матрицю перестановки у -розкладі задля уникнення ділення на нуль. Оскільки представлення чисел з рухомою комою на цифровій машині має обмеження, ми також не хочемо ділити на надто маленьке число. Використовують два підходи для вибору опорного елементу на -му кроці -розкладу. Перший — вибрати найбільший елемент в -му рядку, що дає значний виграш у числовій стійкості. Другий — вибрати найбільший елемент у доповненні Щура на отриманому -му кроці. Цей підхід дає дуже маленький приріст числової стабільності порівняно з попереднім підходом, натомість вимагає значних затрат часу.
Алгоритм Є модифікованим методом Гауса і потребує 2n3 / 3 арифметичних операцій.
Позначимо як lij, uij, aij елементи матриць L,U та A відповідно. З означення LU-розбиття lij=0 (j>i), uij=0 (j<i), uii=1. Очевидно, що
,
(тут n — розмір матриці А)
Звідки легко в явній формі отримати вирази для елементів матриць L та U:
Застосування Розв'язок СЛАР Якщо в рівнянні
задано A та b. Тоді розв'язок отримується в два кроки: Розв'язуємо рівняння і знаходимо y Розв'язуємо рівняння і знаходимо x.
Обернена матриця Матриці L та U можуть використовуватись для обчислення оберненої матриці:
Обчислення детермінанта Після застосування LU-розкладу детермінант може бути обчислений через добуток детермінантів матриць L та U. А детермінанти цих матриць рівні добутку діагональних елементів: det(A)=det(LU)=det(L)det(U)=
Дивись також Теорія матриць
Примітки
Джерела