Descompunerea LU

Descompunerea LU ( LU-decomposition , LU-factorization ) este o reprezentare a unei matrice ca produs a două matrice, , unde este o matrice triunghiulară inferioară și este o matrice triunghiulară superioară. $A$ $A=LU$ $L$ $U$

Descompunerea LU este utilizată pentru a rezolva sisteme de ecuații liniare , a inversa matricele și pentru a calcula determinantul . O descompunere LU există numai dacă matricea este inversabilă și toate principalele minore principale (de colț) ale matricei sunt nedegenerate [1] . $A$ $A$

Această metodă este una dintre varietățile metodei Gauss .

Aplicații

Rezolvarea sistemelor de ecuații liniare

Descompunerea LU rezultată a matricei (matricea coeficienților sistemului) poate fi utilizată pentru a rezolva o familie de sisteme de ecuații liniare cu vectori diferiți pe partea dreaptă [2] : $A$ $b$

ax=b

Dacă descompunerea LU a matricei , , este cunoscută , sistemul original poate fi scris ca $A$ $A=LU$

LUx=b.

Acest sistem poate fi rezolvat în doi pași. Primul pas este rezolvarea sistemului

Ly=b.

Deoarece este o matrice triunghiulară inferioară, acest sistem se rezolvă direct prin substituție directă . $L$

La a doua etapă, sistemul este rezolvat

x=y.

Deoarece este o matrice triunghiulară superioară, acest sistem se rezolvă direct prin înlocuire inversă . $U$

Inversarea matricei

Inversarea matricei este echivalentă cu rezolvarea unui sistem liniar $A$

AX=I

unde este o matrice necunoscută, este matricea de identitate. Soluția acestui sistem este o matrice inversă . $X$ $eu$ $X$ $A^{{-1}}$

Sistemul poate fi rezolvat prin metoda de descompunere LU descrisă mai sus.

Calcularea determinantului unei matrice

Având în vedere descompunerea LU a matricei , $A$

A=LU

putem calcula direct determinantul acestuia ,

\det(A)=\det(LU)=\det(L)\det(U)=\left(\prod _{{i=1}}^{n}L_{{ii}}\right)\ stânga(\prod _{{i=1}}^{n}U_{{ii}}\dreapta)

unde este dimensiunea matricei și sunt elementele diagonale ale matricelor și . $n$ $A$ $L_{{ii}}$ $U_{{ii}}$ $L$ $U$

Derivarea formulei

Pe baza domeniului de aplicare, descompunerea LU poate fi aplicată numai unei matrice nesingulare, prin urmare, în cele ce urmează, vom presupune că matricea este nesingulară. $A$

Deoarece atât în primul rând al matricei, cât și în prima coloană a matricei , toate elementele, cu excepția eventualului primului, sunt egale cu zero, avem $L$ $U$

a_{{11}}=l_{{11}}u_{{{11}}

Dacă , atunci sau . În primul caz, primul rând al matricei este format în întregime din zerouri , în al doilea, prima coloană a matricei . Prin urmare, sau este degenerat și, prin urmare, este degenerat , ceea ce duce la o contradicție. Astfel, dacă , atunci matricea nesingulară nu are o descompunere LU. $a_{{11}}=0$ $l_{{11}}=0$ $u_{{11}}=0$ $L$ $U$ $L$ $U$ $A$ $a_{{11}}=0$ $A$

Să , atunci și . Deoarece L și U sunt definite până la înmulțirea lui U cu o constantă și împărțirea lui L la aceeași constantă, putem cere ca . In acelasi timp . $a_{{11}}\neq 0$ $l_{{11}}\neq 0$ $u_{{11}}\neq 0$ $l_{{11}}=1$ $u_{{11}}=a_{{11}}$

Împărțiți matricea A în celule:

A={\begin{pmatrix}a_{{11}}&w^{T}\\v&A'\\\end{pmatrix}}

unde au dimensiuni respectiv , , . $v,w^{T},A'$ $(N-1)\times 1$ $1\times (N-1)$ $(N-1)\times (N-1)$

În mod similar, împărțim în celule ale matricei și : $L$ $U$

L={\begin{pmatrix}1&0\\v_{l}&L'\\\end{pmatrix}),\ U={\begin{pmatrix}a_{11}&w_{u}^{T} \\0&U'\\\end{pmatrix}}.

Ecuația ia forma $A=LU$

w^{T}=w_{u}^{T},

v=a_{11}v_{l},

A'=v_{l}w_{u}^{T}+L'U'.

Rezolvând sistemul de ecuații pentru , , , , obținem: $v_{l)$ $w_{u)$ $L'$ $U'$

w_{u}=w,

v_{l}=v/a_{11},

L'U'=A'-vw^{T}/a_{11}.

În sfârșit avem:

L={\begin{pmatrix}1&0\\v/a_{11}&L'\\\end{pmatrix)),

U={\begin{pmatrix}a_{11}&w^{T}\\0&U'\\\end{pmatrix)),

L'U'=A'-vw^{T}/a_{11}.

Deci, am redus descompunerea LU a matricei de mărime la descompunerea LU a matricei de mărime . $N\time N$ $(N-1)\times (N-1)$

Expresia se numește complement Schur al elementului din matricea A [1] . $A'-vw^{T}/a_{{11}}$ $a_{11}$

Algoritm

Unul dintre algoritmii de calcul al descompunerii LU este dat mai jos. [3]

Vom folosi următoarea notație pentru elementele matricei: , , , ; iar elementele diagonale ale matricei : , . $A=(a_{{ij}})$ $L=(l_{{ij}})$ $U=(u_{{ij}})$ $i,j=1\dots n$ $L$ $l_{{ii}}=1$ $i=1\dots n$

Puteți găsi matricele și după cum urmează (pașii trebuie efectuati strict în ordine, deoarece următoarele elemente se găsesc folosind cele anterioare): $L$ $U$

Bucla i de la 1 la n
1. Bucla j de la 1 la n
  1. uij =0, lij = 0
  2. l ii =1
Bucla i de la 1 la n
1. Bucla j de la 1 la n
  1. Dacă i<=j: $u_{ij}=a_{ij}-\sum _{k=1}^{i-1}l_{ik}*u_{kj)$
  2. Dacă i>j: ${\displaystyle l_{ij}=(a_{ij}-\sum _{k=1}^{j-1}l_{ik}*u_{kj})/u_{jj))$

Ca rezultat, obținem matrici - și . $L$ $U$

Vezi și

Note

↑ 1 2 E. E. Tyrtyshnikov. Analiza matriceală și algebră liniară. — 2004-2005.
↑ Levitin, 2006 .
↑ Verzhbitsky V.M. Fundamentele metodelor numerice. Manual pentru licee. - Liceul, 2002. - S. 63-64. — ISBN 5-06-004020-8 .

Literatură

Ortega J. Introducere în metodele paralele și vectoriale pentru rezolvarea sistemelor liniare. — M .: Mir, 1991. — 376 p. — ISBN 5-03-001941-3 .
Levitin A. V. Algoritmi. Introducere în dezvoltare și analiză - M . : Williams , 2006. - 576 p. — ISBN 978-5-8459-0987-9

Vectori și matrici

Vectori

Noțiuni de bază	Vector în geometrie Bază Baza ortogonala Coordonatele vectoriale Coliniaritate Ortogonalitatea Dependență liniară Spațiu coloane
Tipuri de vectori	Vector unitar Vector axial vector izotrop Normal Coliniaritate Vector zero Vector rază Vector propriu
Operații pe vectori	Produs scalar produs vectorial produs mixt Produs pseudoscalar Produs dublu cruce
Tipuri de spațiu	spațiu vectorial spatiu afin Spațiul euclidian Spațiul pseudo-euclidian Spațiu normat Spațiul Minkowski

matrici

Noțiuni de bază	Înmulțirea matricei Matrice transpusă Matricea conjugată hermitiană Matricea simetrică matrice inversă Valoare proprie Polinom caracteristic al unei matrice
Matrici speciale	Matrice de identitate Matrice zero Matricea diagonală matricea lambda
Descompuneri de matrice	descompunerea LU Descompunerea Cholesky Descompunerea QR Descompunerea LUP descompunerea unei valori singulare Descompunerea spectrală a unei matrice

Alte