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 . Például egy háromegyenletes egyenletrendszer esetén az LU felbontás a következőképp fog kinézni:
Az algoritmus célja az egyes -k és -k meghatározása.
Lépései Az algoritmus során a következő lépéseket követjük:
1) Végrehajtjuk az , 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) ; ahol i ϵ [1..j] b) ; 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 (), 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)
Kategória:Lineáris algebra Kategória:Algoritmusok