Crout-algoritmus

A módszert Prescott Durand Crout alkotta meg. Lineáris egyenletrendszerek megoldásában játszik szerepet.

A Crout-algoritmus az LU felbontás egyik lehetséges kivitelezése, mivel az A mátrixot egy alsó háromszögmátrixra (L) és egy felső háromszögmátrixra (U) bontja fel.

Tehát abból indulunk ki, hogy:

${\displaystyle A=LU}$

Példa: Három egyenletes egyenletrendszer esetén a következőképp fog kinézni:

${\displaystyle A={\begin{pmatrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\\a_{31}&a_{32}&a_{33}\\\end{pmatrix}}={\begin{pmatrix}l_{11}&0&0\\l_{21}&l_{22}&0\\l_{31}&l_{32}&l_{33}\\\end{pmatrix}}{\begin{pmatrix}u_{11}&u_{12}&u_{13}\\0&u_{22}&u_{23}\\0&0&u_{33}\end{pmatrix}}=LU}$

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

1) Végrehajtjuk az ${\displaystyle 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) ${\displaystyle u_{ij}=a_{ij}-\sum _{k\mathop {=} 1}^{i-1}(l_{ik}*u_{kj})}$; ahol i ϵ [1..j]
  b) ${\displaystyle l_{ij}=1/u_{jj}*(a_{ij}-\sum _{k\mathop {=} 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 (${\displaystyle n^{3}/3+n^{2}}$), ami gyakorlatilag egy kiküszöbölést és két visszahelyettesítést jelent.

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

Lázár Zsolt, Lázár József, Járai-Szabó Ferenc: Numerikus módszerek