Steins Methode - Stone's method

In der numerischen Analyse ist die Methode von Stone , auch als stark implizites Verfahren oder SIP bekannt , ein Algorithmus zum Lösen eines spärlichen linearen Gleichungssystems . Das Verfahren verwendet eine unvollständige LU-Zerlegung , die sich der exakten LU-Zerlegung annähert , um eine iterative Lösung des Problems zu erhalten. Die Methode ist nach Harold S. Stone benannt , der sie 1968 vorschlug.

Die LU-Zerlegung ist ein ausgezeichneter linearer Allzweckgleichungslöser. Der größte Nachteil besteht darin, dass die Koeffizientenmatrix nicht als spärliche Matrix ausgenutzt wird. Die LU-Zerlegung einer dünn besetzten Matrix ist normalerweise nicht dünn, daher kann für ein großes Gleichungssystem die LU-Zerlegung eine unerschwingliche Menge an Speicher und eine unzulässige Anzahl von arithmetischen Operationen erfordern .

Wenn bei den vorkonditionierten iterativen Verfahren die Vorkonditionierungsmatrix M eine gute Annäherung an die Koeffizientenmatrix A ist, ist die Konvergenz schneller. Dies bringt einen auf die Idee, die ungefähre Faktorisierung LU von A als Iterationsmatrix M zu verwenden .

Eine Version der unvollständigen unteren-oberen Zerlegungsmethode wurde 1968 von Stone vorgeschlagen. Diese Methode wurde für das Gleichungssystem entwickelt, das sich aus der Diskretisierung partieller Differentialgleichungen ergibt, und wurde zunächst für ein pentadiagonales Gleichungssystem verwendet, das beim Lösen einer elliptischen partiellen Differentialgleichung in a erhalten wurde zweidimensionaler Raum durch eine Finite-Differenzen- Methode. Die ungefähre LU-Zerlegung wurde in derselben pentadiagonalen Form wie die ursprüngliche Matrix (drei Diagonalen für L und drei Diagonalen für U ) als die beste Übereinstimmung der sieben möglichen Gleichungen für die fünf Unbekannten für jede Zeile der Matrix angesehen.

Algorithmus

method stone is
    For the linear system Ax = b
    calculate incomplete LU factorization of matrix A
       Ax = (M-N)x = (LU-N)x = b
       Mx(k+1) = Nx(k)+b , with ||M|| >> ||N||
       Mx(k+1) = LUx(k+1) = c(k)
       LUx(k) = L(Ux(k+1)) = Ly(k) = c(k)
    set a guess
       k = 0, x(k)
       r(k)=b - Ax(k)
    while ( ||r(k)||2 ≥ ε ) do
       evaluate new right hand side
          c(k) = Nx(k) + b
       solve Ly(k) = c(k) by forward substitution
          y(k) = L−1c(k)
       solve Ux(k+1) = y(k) by back substitution
          x(k+1) = U−1y(k)
    end while

Fußnoten

Verweise

• Stone, HL (1968). "Iterative Lösung impliziter Approximationen mehrdimensionaler partieller Differentialgleichungen". SIAM Journal on Numerical Analysis . 5 (3): 530–538. doi : 10.1137 / 0705044 . hdl : 10338.dmlcz / 104038 . - der Originalartikel
• Ferziger, JH und Peric, M. (2001). Berechnungsmethoden für die Fluiddynamik . Springer-Verlag, Berlin. ISBN   3-540-42074-6 . CS1-Wartung: mehrere Namen: Autorenliste ( Link )
• Acosta, JM (2001). Numerische Algorithmen für dreidimensionale rechnergestützte fluiddynamische Probleme. Doktorarbeit . Polytechnische Universität von Katalonien.
• Dieser Artikel enthält Text aus dem Artikel Stone's_method im CFD-Wiki , der unter der GFDL- Lizenz steht.