LU-malkomponaĵo

LU malkomponaĵo estas metodo de solvado de sistemo de linearaj ekvacioj, kiu havas formon:

${\begin{bmatrix}a_{11}&a_{12}&\cdots &a_{1n}\\a_{21}&a_{22}&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\cdots &a_{nn}\end{bmatrix}}\cdot {\begin{bmatrix}x_{1}\\x_{2}\\\vdots \\x_{n}\end{bmatrix}}={\begin{bmatrix}y_{1}\\y_{2}\\\vdots \\y_{n}\end{bmatrix}}$

Laŭ matrica maniero de skribado $\mathbf {A} \cdot x=y$, kaj $\mathbf {A}$ - matrico de koeficientoj , $\mathbf {x}$ - vektoro de variabloj, $\mathbf {y}$ - vektoro de datumoj.

Priskribo de metodo

Laŭ metodo LU matrico de koeficientoj estas malkomponata en multiplikado de du triangulaj matricoj: suba (angle: Lower) kaj supera (angle: Upper).

$\mathbf {A} =\mathbf {L} \cdot \mathbf {U}$

$\mathbf {L} ={\begin{bmatrix}l_{11}&0&\cdots &0\\l_{21}&l_{22}&\cdots &0\\\vdots &\vdots &\ddots &0\\l_{n1}&l_{n2}&\cdots &l_{nn}\end{bmatrix}}\mathbf {U} ={\begin{bmatrix}u_{11}&u_{12}&\cdots &u_{1n}\\0&u_{22}&\cdots &u_{2n}\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &u_{nn}\end{bmatrix}}$

Sistemo de ekvacioj tiam havas formon:

$\mathbf {L} \cdot \mathbf {U} \cdot \mathbf {x} =\mathbf {y}$

kaj ĝia solvo povas esti esprimita per du sistemoj de ekvacioj kun triangulaj ekvacioj, kiuj solvas tre facile.

$\mathbf {L} \cdot \mathbf {z} =\mathbf {y}$

$\mathbf {U} \cdot \mathbf {x} =\mathbf {z}$

Ecoj de metodo

• La metodo ebligas rapidan kalkuladon de matrico $\mathbf {A}$.
• Kvanto de multiplikoj kiuj estas bezonata por solvi (kalkuli valorojn de vektoro $x$) estas $n^{2}$ kaj adicioj $n^{2}-n$.
• por komputila kalkulado metodo ŝparas memoron, ĉar ĉiujn valorojn oni povas havi en unu matrico kaj unu vektoro (samaj kiuj enhavas komencajn valorojn).
• Ĝi bezonas malmultajn operacioj ol aliaj metodoj (krom specialaj metodoj)
• Kalkulado de determinanto de matrico A povas kalkuli uzante teoremon de Cauchy:

$\mathbf {det(A\cdot \mathbf {B} )} =\mathbf {det(A)} \cdot \mathbf {det(B)}$

kaj uzante de fakto, ke determino de triangula matrico estas multipliko de diagonalaj elementoj de matrico. Alinome:

$\mathbf {det(A)} =\mathbf {det(U)} =u_{11}\cdot u_{22}\cdot \cdots \cdot u_{nn}$

LU malkomponaĵo

Ĉefa problemo de ĉi tiu metodo estas malkomponaĵo. Por ke la malkomponaĵo estus unusignifa, decidas ke iu el du matricoj havas diagonalaj elementoj egalaj al unu.

Ekzistas du ĉefaj metodoj por fari tiun:

1. Metodo elimina de Gauss
2. Metodo de Doolittle (priskribo sube)

Metodo de Doolittle

Laŭ ĉi tiu metodo egaleco $A=LU$ estas sistemo de $n^{2}$ ekvacioj kun $n^{2}$ variabloj. La variabloj estas elementoj $l_{ij}$ por $i<j$ (elementoj sube diagonalo) kaj $u_{ij}$ por $i\geq j$ (elementoj de diagonalo kaj supere). Kun lemo ke elementoj de diagonalo de matrico L ekvacias 1.

${\begin{bmatrix}a_{11}&a_{12}&\cdots &a_{1n}\\a_{21}&a_{22}&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\cdots &a_{nn}\end{bmatrix}}={\begin{bmatrix}1&0&\cdots &0\\l_{21}&1&\cdots &0\\\vdots &\vdots &\ddots &0\\l_{n1}&l_{n2}&\cdots &1\end{bmatrix}}\cdot {\begin{bmatrix}u_{11}&u_{12}&\cdots &u_{1n}\\0&u_{22}&\cdots &u_{2n}\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &u_{nn}\end{bmatrix}}$

Kalkulado sekvaj elementoj de matricoj $L$ kaj $U$ faras alterne. te. post kalkulado de verso de matrico U kalkulas kolumnon de matrico L kaj denove sekvan verson U.

Ĝeneralaj formuloj por apartaj elementoj de matricoj estas:

por ĉiu $i=1,2,\ldots ,n$:

$u_{ij}=a_{ij}-\sum _{k=1}^{i-1}l_{ik}u_{kj}$ dla $j=i,i+1\ldots ,n$

$l_{ji}={\frac {1}{u_{ii}}}\left(a_{ji}-\sum _{k=1}^{i-1}l_{jk}u_{ki}\right)$ dla $j=i+1,i+2\ldots ,n$

Laŭ lasta ekvacio metodo ne funkcios, se $u_{ii}=0$.

Kvanto de bezonataj operacioj:

• multiplikaj: ${\frac {1}{3}}n^{3}-{\frac {1}{3}}n$,
• adiciaj: ${\frac {1}{3}}n^{3}-{\frac {1}{2}}n^{2}+{\frac {1}{6}}n$.

Ekzemplo (matrico 3x3)

${\begin{bmatrix}5&3&2\\1&2&0\\3&0&4\end{bmatrix}}={\begin{bmatrix}1&0&0\\l_{21}&1&0\\l_{31}&l_{32}&1\end{bmatrix}}{\begin{bmatrix}u_{11}&u_{12}&u_{13}\\0&u_{22}&u_{23}\\0&0&u_{33}\\\end{bmatrix}}$

Unua verso de matrico U:

$5=1\cdot u_{11}+0\cdot 0+0\cdot 0\rightarrow u_{11}=5$

$3=1\cdot u_{12}+0\cdot u_{22}+0\cdot 0\rightarrow u_{12}=3$

$2=1\cdot u_{13}+0\cdot u_{23}+0\cdot u_{33}\rightarrow u_{13}=2$

${\begin{bmatrix}5&3&2\\1&2&0\\3&0&4\end{bmatrix}}={\begin{bmatrix}1&0&0\\l_{21}&1&0\\l_{31}&l_{32}&1\end{bmatrix}}{\begin{bmatrix}5&3&2\\0&u_{22}&u_{23}\\0&0&u_{33}\\\end{bmatrix}}$

Unua kolumno de matrico L:

$1=l_{21}\cdot 5+1\cdot 0+0\cdot 0\rightarrow l_{21}={\frac {1}{5}}$

$3=l_{31}\cdot 5+l_{32}\cdot 0+1\cdot 0\rightarrow l_{31}={\frac {3}{5}}$

${\begin{bmatrix}5&3&2\\1&2&0\\3&0&4\end{bmatrix}}={\begin{bmatrix}1&0&0\\{\frac {1}{5}}&1&0\\{\frac {3}{5}}&l_{32}&1\end{bmatrix}}{\begin{bmatrix}5&3&2\\0&u_{22}&u_{23}\\0&0&u_{33}\\\end{bmatrix}}$

Dua verso de matrico U:

$2={\frac {1}{5}}\cdot 3+1\cdot u_{22}+0\cdot 0\rightarrow u_{22}={\frac {7}{5}}$

$0={\frac {1}{5}}\cdot 2+1\cdot u_{23}+0\cdot u_{33}\rightarrow u_{23}=-{\frac {2}{5}}$

${\begin{bmatrix}5&3&2\\1&2&0\\3&0&4\end{bmatrix}}={\begin{bmatrix}1&0&0\\{\frac {1}{5}}&1&0\\{\frac {3}{5}}&l_{32}&1\end{bmatrix}}{\begin{bmatrix}5&3&2\\0&{\frac {7}{5}}&-{\frac {2}{5}}\\0&0&u_{33}\\\end{bmatrix}}$

Dua kolumno de matrico L:

$0={\frac {3}{5}}\cdot 3+l_{32}\cdot {\frac {7}{5}}+1\cdot 0\rightarrow l_{32}=-{\frac {9}{7}}$

${\begin{bmatrix}5&3&2\\1&2&0\\3&0&4\end{bmatrix}}={\begin{bmatrix}1&0&0\\{\frac {1}{5}}&1&0\\{\frac {3}{5}}&-{\frac {9}{7}}&1\end{bmatrix}}{\begin{bmatrix}5&3&2\\0&{\frac {7}{5}}&-{\frac {2}{5}}\\0&0&u_{33}\\\end{bmatrix}}$

Tria verso de matrico U:

$4={\frac {3}{5}}\cdot 2+{\frac {9}{7}}\cdot {\frac {2}{5}}+1\cdot u_{33}\rightarrow u_{33}={\frac {16}{7}}$

${\begin{bmatrix}5&3&2\\1&2&0\\3&0&4\end{bmatrix}}={\begin{bmatrix}1&0&0\\{\frac {1}{5}}&1&0\\{\frac {3}{5}}&-{\frac {9}{7}}&1\end{bmatrix}}{\begin{bmatrix}5&3&2\\0&{\frac {7}{5}}&-{\frac {2}{5}}\\0&0&{\frac {16}{7}}\\\end{bmatrix}}$

Vidu ankaŭ

• Malkomponaĵo de Choleski