Crout-algoritmus

A Crout-algoritmus lineáris egyenletrendszerek megoldásában játszik szerepet. A módszert Prescott Durand Crout amerikai matematikus alkotta meg.

A Crout-algoritmus az LU felbontás egyik lehetséges kivitelezése, mivel egy A mátrixot egy alsó háromszögmátrixra (L) és egy felső háromszögmátrixra (U) bont fel, ahol $A=LU$. Például egy háromegyenletes egyenletrendszer esetén az LU felbontás a következőképp fog kinézni:

$A=\left(\begin{array}{ccc}{a}_{11}& a_{12}& a_{13}\\ a_{21}& a_{22}& a_{23}\\ a_{31}& a_{32}& a_{33}\end{array}\right)=\left(\begin{array}{ccc}{l}_{11}& 0& 0\\ l_{21}& l_{22}& 0\\ l_{31}& l_{32}& l_{33}\end{array}\right)\left(\begin{array}{ccc}{u}_{11}& u_{12}& u_{13}\\ 0& u_{22}& u_{23}\\ 0& 0& u_{33}\end{array}\right)=LU.$

Az algoritmus célja az egyes $l_{ij}$-k és $u_{ij}$-k meghatározása.

Lépései

Az algoritmus során a következő lépéseket követjük:

1) Végrehajtjuk az $l_{ii}=1$, i ϵ [1..n] értékadásokat.

2) Minden egyes j ϵ [1..n] indexre a következő két lépést hajtjuk végre:

  a) $u_{ij}=a_{ij}-\sum _{k=1}^{i-1}(l_{ik}*u_{kj})$; ahol i ϵ [1..j]
  b) $l_{ij}=1/u_{jj}*(a_{ij}-\sum _{k=1}^{j-1}(l_{ik}*u_{kj})$; ahol i ϵ [j+1..n]

Az algoritmus biztosítja, hogy az egyenletek jobb oldalán szereplő, éppen felhasználásra kerülő l és u változók előzőleg már kiszámításra kerültek.

A módszer műveletigénye ($n^3/3+n^2$), ami gyakorlatilag egy kiküszöbölést és két visszahelyettesítést jelent.

A Crout-algoritmus Python programozási nyelvben

def Crout(a,l,u):
    for i in range(n):
        l[i][i]=1
    for j in range(n):
        for i in range(j+1):
            u[i][j]=a[i][j]
            for k in range(i):            
                u[i][j]=u[i][j]-l[i][k]*u[k][j]

        for i in range(j+1,n):
            l[i][j]=a[i][j]
            for k in range(j):
                l[i][j]=l[i][j]-l[i][k]*u[k][j]
            l[i][j]=l[i][j]/u[j][j]
    return l, u

Források

• Lázár Zsolt – Lázár József – Járai-Szabó Ferenc: Numerikus módszerek (Kolozsvári Egyetemi Kiadó, Kolozsvár, 2008) Sablon:ISBN