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)=
Дивись також
Примітки
- . Архів оригіналу за 23 грудня 2014. Процитовано 8 грудня 2014.
- Lloyd N. Trefethen; David Bau, III. 21. Pivoting. Numerical Linear Algebra. SIAM. с. 160-161. ISBN .
Джерела
- Гантмахер Ф. Р. Теория матриц. — 5-е. — М: : Физматлит, 2010. — 559 с. — .(рос.)
Це незавершена стаття з математики. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
LU rozklad matrici predstavlennya matrici u viglyadi dobutku nizhnoyi trikutnoyi matrici ta verhnoyi trikutnoyi matrici Kvadratna matricya A rozmiru n mozhe buti predstavlena u viglyadi A L U displaystyle A LU de L ta U nizhnya ta verhnya trikutna matricya togo zh rozmiru vidpovidno LDU rozklad matrici ce predstavlennya u viglyadi A L D U displaystyle A LDU de D diagonalna matricya a L ta U ye odinichnimi trikutnimi matricyami tobto vsi yih diagonalni elementi rivni odinici LUP rozklad matrici ce predstavlennya v formi A L U P displaystyle A LUP de L ta U nizhnya ta verhnya trikutna matricya togo zh rozmiru a P matricya perestanovki OpisA a 11 a 12 a 1 n a 21 a 22 a 2 n a n 1 a n 2 a n n a 11 w t v A 1 0 v a 11 I n 1 a 11 w T 0 A v w t a 11 1 0 v a 11 I n 1 a 11 w T 0 L U 1 0 v a 11 L a 11 w T 0 U L U displaystyle A begin pmatrix a 11 amp a 12 amp dots amp a 1n amp a 21 amp a 22 amp dots amp a 2n amp vdots amp vdots amp ddots amp vdots amp a n1 amp a n2 amp dots amp a nn amp end pmatrix begin pmatrix a 11 amp w t amp v amp A amp end pmatrix begin pmatrix 1 amp 0 amp v a 11 amp I n 1 amp end pmatrix begin pmatrix a 11 amp w T amp 0 amp A frac v times w t a 11 amp end pmatrix begin pmatrix 1 amp 0 amp v a 11 amp I n 1 amp end pmatrix begin pmatrix a 11 amp w T amp 0 amp L U amp end pmatrix begin pmatrix 1 amp 0 amp v a 11 amp L amp end pmatrix begin pmatrix a 11 amp w T amp 0 amp U amp end pmatrix LU Matricya A v w t a 11 displaystyle A v times w t a 11 nazivayetsya dopovnennyam Shura dlya A displaystyle A shodo a 11 displaystyle a 11 Metod ne pracyuye yaksho odin z a i i 0 displaystyle a ii 0 tomu sho vidbuvayetsya dilennya na nul Elementi na yaki mi dilimo vprodovzh L U displaystyle LU rozkladu nazivayutsya opornimi i perebuvayut na golovnij diagonali matrici U displaystyle U Mi vikoristovuyemo matricyu perestanovki P displaystyle P u L U P displaystyle LUP rozkladi zadlya uniknennya dilennya na nul Oskilki predstavlennya chisel z ruhomoyu komoyu na cifrovij mashini maye obmezhennya mi takozh ne hochemo diliti na nadto malenke chislo Vikoristovuyut dva pidhodi dlya viboru opornogo elementu na i displaystyle i mu kroci L U P displaystyle LUP rozkladu Pershij vibrati najbilshij element v i displaystyle i mu ryadku sho daye znachnij vigrash u chislovij stijkosti Drugij vibrati najbilshij element u dopovnenni Shura na otrimanomu i displaystyle i mu kroci Cej pidhid daye duzhe malenkij pririst chislovoyi stabilnosti porivnyano z poperednim pidhodom natomist vimagaye znachnih zatrat chasu AlgoritmYe modifikovanim metodom Gausa i potrebuye 2n3 3 arifmetichnih operacij Poznachimo yak lij uij aij elementi matric L U ta A vidpovidno Z oznachennya LU rozbittya lij 0 j gt i uij 0 j lt i uii 1 Ochevidno sho a i j k 0 n 1 l i k u k j k 0 i 1 l i k u k j l i i u i j k i 1 n 1 l i k u k j k 0 i 1 l i k u k j l i i u i j displaystyle a ij sum k 0 n 1 l ik u kj sum k 0 i 1 l ik u kj l ii u ij sum k i 1 n 1 l ik u kj sum k 0 i 1 l ik u kj l ii u ij a i j k 0 n 1 l i k u k j k 0 j 1 l i k u k j l i j u j j k j 1 n 1 l i k u k j k 0 j 1 l i k u k j l i j u j j displaystyle a ij sum k 0 n 1 l ik u kj sum k 0 j 1 l ik u kj l ij u jj sum k j 1 n 1 l ik u kj sum k 0 j 1 l ik u kj l ij u jj tut n rozmir matrici A Zvidki legko v yavnij formi otrimati virazi dlya elementiv matric L ta U l i j a i j k 0 j 1 l i k u k j i j displaystyle l ij a ij sum k 0 j 1 l ik u kj i geq j u i j 1 l i i a i j k 0 i 1 l i k u k j i lt j displaystyle u ij 1 over l ii left a ij sum k 0 i 1 l ik u kj right i lt j ZastosuvannyaRozv yazok SLAR Yaksho v rivnyanni A x L U x b displaystyle Ax LUx b zadano A ta b Todi rozv yazok otrimuyetsya v dva kroki Rozv yazuyemo rivnyannya L y b displaystyle Ly b i znahodimo y Rozv yazuyemo rivnyannya U x y displaystyle Ux y i znahodimo x Obernena matricya Matrici L ta U mozhut vikoristovuvatis dlya obchislennya obernenoyi matrici A 1 U 1 L 1 displaystyle A 1 U 1 L 1 Obchislennya determinanta Pislya zastosuvannya LU rozkladu determinant mozhe buti obchislenij cherez dobutok determinantiv matric L ta U A determinanti cih matric rivni dobutku diagonalnih elementiv det A det LU det L det U L i i displaystyle prod L i i U i i displaystyle prod U i i Divis takozhTeoriya matricPrimitki Arhiv originalu za 23 grudnya 2014 Procitovano 8 grudnya 2014 Lloyd N Trefethen David Bau III 21 Pivoting Numerical Linear Algebra SIAM s 160 161 ISBN 978 0 898713 61 9 DzherelaGantmaher F R Teoriya matric 5 e M Fizmatlit 2010 559 s ISBN 5 9221 0524 8 ros Ce nezavershena stattya z matematiki Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi