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

Джерела

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.