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:

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

Примітки[ред.ред. код]

  1. Арифметика рухомої коми
  2. Lloyd N. Trefethen; David Bau, III. 21. Pivoting. Numerical Linear Algebra. SIAM. с. 160–161. ISBN 978-0-898713-61-9. 

Джерела[ред.ред. код]


Сигма Це незавершена стаття з математики.
Ви можете допомогти проекту, виправивши або дописавши її.