Gfyuki

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

[a11a12⋯a1na21a22⋯a2n⋮⋮⋱⋮an1an2⋯ann]⋅[x1x2⋮xn]=[y1y2⋮yn]{displaystyle {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 A⋅x=y{displaystyle mathbf {A} cdot x=y}, kaj A{displaystyle mathbf {A} } - matrico de koeficientoj , x{displaystyle mathbf {x} } - vektoro de variabloj, y{displaystyle 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).

A=L⋅U{displaystyle mathbf {A} =mathbf {L} cdot mathbf {U} }
L=[l110⋯0l21l22⋯0⋮⋮⋱0ln1ln2⋯lnn]U=[u11u12⋯u1n0u22⋯u2n⋮⋮⋱⋮00⋯unn]{displaystyle 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:

L⋅U⋅x=y{displaystyle 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.

L⋅z=y{displaystyle mathbf {L} cdot mathbf {z} =mathbf {y} }
U⋅x=z{displaystyle mathbf {U} cdot mathbf {x} =mathbf {z} }

Ecoj de metodo |

• La metodo ebligas rapidan kalkuladon de matrico A{displaystyle mathbf {A} }.


• Kvanto de multiplikoj kiuj estas bezonata por solvi (kalkuli valorojn de vektoro x{displaystyle x}) estas n2{displaystyle n^{2}} kaj adicioj n2−n{displaystyle 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:

det(A⋅B)=det(A)⋅det(B){displaystyle mathbf {det(Acdot 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:

det(A)=det(U)=u11⋅u22⋅⋯⋅unn{displaystyle 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{displaystyle A=LU} estas sistemo de n2{displaystyle n^{2}} ekvacioj kun n2{displaystyle n^{2}} variabloj. La variabloj estas elementoj lij{displaystyle l_{ij}} por i<j{displaystyle i<j} (elementoj sube diagonalo) kaj uij{displaystyle u_{ij}} por i≥j{displaystyle igeq j} (elementoj de diagonalo kaj supere). Kun lemo ke elementoj de diagonalo de matrico L ekvacias 1.

[a11a12⋯a1na21a22⋯a2n⋮⋮⋱⋮an1an2⋯ann]=[10⋯0l211⋯0⋮⋮⋱0ln1ln2⋯1]⋅[u11u12⋯u1n0u22⋯u2n⋮⋮⋱⋮00⋯unn]{displaystyle {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 &1end{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{displaystyle L} kaj U{displaystyle 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,…,n{displaystyle i=1,2,ldots ,n}:

uij=aij−∑k=1i−1likukj{displaystyle u_{ij}=a_{ij}-sum _{k=1}^{i-1}l_{ik}u_{kj}} dla j=i,i+1…,n{displaystyle j=i,i+1ldots ,n}

lji=1uii(aji−∑k=1i−1ljkuki){displaystyle 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…,n{displaystyle j=i+1,i+2ldots ,n}

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

Kvanto de bezonataj operacioj:

• multiplikaj: 13n3−13n{displaystyle {frac {1}{3}}n^{3}-{frac {1}{3}}n},


• adiciaj: 13n3−12n2+16n{displaystyle {frac {1}{3}}n^{3}-{frac {1}{2}}n^{2}+{frac {1}{6}}n}.

Ekzemplo (matrico 3x3) |

[532120304]=[100l2110l31l321][u11u12u130u22u2300u33]{displaystyle {begin{bmatrix}5&3&2\1&2&0\3&0&4end{bmatrix}}={begin{bmatrix}1&0&0\l_{21}&1&0\l_{31}&l_{32}&1end{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⋅u11+0⋅0+0⋅0→u11=5{displaystyle 5=1cdot u_{11}+0cdot 0+0cdot 0rightarrow u_{11}=5}

3=1⋅u12+0⋅u22+0⋅0→u12=3{displaystyle 3=1cdot u_{12}+0cdot u_{22}+0cdot 0rightarrow u_{12}=3}

2=1⋅u13+0⋅u23+0⋅u33→u13=2{displaystyle 2=1cdot u_{13}+0cdot u_{23}+0cdot u_{33}rightarrow u_{13}=2}

[532120304]=[100l2110l31l321][5320u22u2300u33]{displaystyle {begin{bmatrix}5&3&2\1&2&0\3&0&4end{bmatrix}}={begin{bmatrix}1&0&0\l_{21}&1&0\l_{31}&l_{32}&1end{bmatrix}}{begin{bmatrix}5&3&2\0&u_{22}&u_{23}\0&0&u_{33}\end{bmatrix}}}

Unua kolumno de matrico L:

1=l21⋅5+1⋅0+0⋅0→l21=15{displaystyle 1=l_{21}cdot 5+1cdot 0+0cdot 0rightarrow l_{21}={frac {1}{5}}}

3=l31⋅5+l32⋅0+1⋅0→l31=35{displaystyle 3=l_{31}cdot 5+l_{32}cdot 0+1cdot 0rightarrow l_{31}={frac {3}{5}}}

[532120304]=[100151035l321][5320u22u2300u33]{displaystyle {begin{bmatrix}5&3&2\1&2&0\3&0&4end{bmatrix}}={begin{bmatrix}1&0&0\{frac {1}{5}}&1&0\{frac {3}{5}}&l_{32}&1end{bmatrix}}{begin{bmatrix}5&3&2\0&u_{22}&u_{23}\0&0&u_{33}\end{bmatrix}}}

Dua verso de matrico U:

2=15⋅3+1⋅u22+0⋅0→u22=75{displaystyle 2={frac {1}{5}}cdot 3+1cdot u_{22}+0cdot 0rightarrow u_{22}={frac {7}{5}}}

0=15⋅2+1⋅u23+0⋅u33→u23=−25{displaystyle 0={frac {1}{5}}cdot 2+1cdot u_{23}+0cdot u_{33}rightarrow u_{23}=-{frac {2}{5}}}

[532120304]=[100151035l321][532075−2500u33]{displaystyle {begin{bmatrix}5&3&2\1&2&0\3&0&4end{bmatrix}}={begin{bmatrix}1&0&0\{frac {1}{5}}&1&0\{frac {3}{5}}&l_{32}&1end{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=35⋅3+l32⋅75+1⋅0→l32=−97{displaystyle 0={frac {3}{5}}cdot 3+l_{32}cdot {frac {7}{5}}+1cdot 0rightarrow l_{32}=-{frac {9}{7}}}

[532120304]=[100151035−971][532075−2500u33]{displaystyle {begin{bmatrix}5&3&2\1&2&0\3&0&4end{bmatrix}}={begin{bmatrix}1&0&0\{frac {1}{5}}&1&0\{frac {3}{5}}&-{frac {9}{7}}&1end{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=35⋅2+97⋅25+1⋅u33→u33=167{displaystyle 4={frac {3}{5}}cdot 2+{frac {9}{7}}cdot {frac {2}{5}}+1cdot u_{33}rightarrow u_{33}={frac {16}{7}}}

[532120304]=[100151035−971][532075−2500167]{displaystyle {begin{bmatrix}5&3&2\1&2&0\3&0&4end{bmatrix}}={begin{bmatrix}1&0&0\{frac {1}{5}}&1&0\{frac {3}{5}}&-{frac {9}{7}}&1end{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