LU-розклад матриці

(Перенаправлено з LU-розклад)

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

Квадратна матриця A розміру n може бути представлена у вигляді

де L та U — нижня та верхня трикутна матриця того ж розміру відповідно.

LDU-розклад матриці — це представлення у вигляді

де Dдіагональна матриця, а L та U є одиничними трикутними матрицями, тобто, всі їх діагональні елементи рівні одиниці.

LUP-розклад матриці — це представлення в формі

де L та U — нижня та верхня трикутна матриця того ж розміру, а Pматриця перестановки.

Опис ред.

 

Матриця   називається доповненням Шура для   щодо  

Метод не працює якщо один з   тому що відбувається ділення на нуль. Елементи, на які ми ділимо впродовж  -розкладу, називаються опорними і перебувають на головній діагоналі матриці   Ми використовуємо матрицю перестановки   у  -розкладі задля уникнення ділення на нуль. Оскільки представлення чисел з рухомою комою на цифровій машині має обмеження[1], ми також не хочемо ділити на надто маленьке число. Використовують два підходи для вибору опорного елементу на  -му кроці  -розкладу. Перший — вибрати найбільший елемент в  -му рядку, що дає значний виграш у числовій стійкості. Другий — вибрати найбільший елемент у доповненні Щура на отриманому  -му кроці. Цей підхід дає дуже маленький приріст числової стабільності порівняно з попереднім підходом, натомість вимагає значних затрат часу.[2]

Алгоритм ред.

Є модифікованим методом Гауса і потребує 2n3 / 3 арифметичних операцій.

Позначимо як lij, uij, aij елементи матриць L,U та A відповідно. З означення LU-розбиття lij=0 (j>i), uij=0 (j<i), uii=1. Очевидно, що

 

 ,

(тут n — розмір матриці А)

Звідки легко в явній формі отримати вирази для елементів матриць L та U:

 

 

Застосування ред.

Розв'язок СЛАР ред.

Якщо в рівнянні

 

задано A та b. Тоді розв'язок отримується в два кроки:

  1. Розв'язуємо рівняння   і знаходимо y
  2. Розв'язуємо рівняння   і знаходимо x.

Обернена матриця ред.

Матриці L та U можуть використовуватись для обчислення оберненої матриці:

 

Обчислення детермінанта ред.

Після застосування LU-розкладу детермінант може бути обчислений через добуток детермінантів матриць L та U. А детермінанти цих матриць рівні добутку діагональних елементів:

det(A)=det(LU)=det(L)det(U)=  

Дивись також ред.

Примітки ред.

  1. Арифметика рухомої коми. Архів оригіналу за 23 грудня 2014. Процитовано 8 грудня 2014. 
  2. Lloyd N. Trefethen; David Bau, III. 21. Pivoting. Numerical Linear Algebra. SIAM. с. 160-161. ISBN 978-0-898713-61-9. 

Джерела ред.