Thumbnail Image

Iterative solution of discretized convection-diffusion problems

Echeverría Serur, Carlos

Inst. Mathematik

Certain approximation techniques for the numerical solution of partial differential equations result in linear algebraic systems where the coefficient matrix is nonsymmetric, nonnormal and ill-conditioned. This is the case for the finite difference discretization of the convection-diffusion equation posed on a Shishkin mesh treated in this work. We present a convergence analysis of the (algebraic) multiplicative Schwarz method when it is used to solve linear systems arising from both the upwind and central finite difference discretization approaches to such problems. For one and two dimensional problems, we show that the iteration matrix of the method has low-rank, which allows us to bound its infinity-norm. These bounds lead to quantitative error bounds for the iterates of the method that are valid from the first step of the iteration process. For problems in one-dimension, we prove rapid convergence of the method for all parameter choices of the problem when the upwind discretization approach is used, while convergence can only be proven for certain parameter choices for the central difference approach. Only the upwind discretization is considered in the case of two-dimensional problems. Furthermore, we consider the method as a preconditioner to GMRES and prove the convergence of the preconditioned method in a small number of steps when the local subdomain problems are solved exactly. Numerical experiments show that, for problems in two-dimensions, the number of iterations either stays the same or decreases for the case of inexact local solves, achieving a speed up in computational time. We continue by generalizing our convergence results to the case where the coefficient matrix of the linear system possess a special block structure that arises, for example, when a partial differential equation is posed and discretized on a domain that consists of two subdomains that overlap. Our analysis does not assume that the system matrices resulting from the discretization process are symmetric (positive definite) or posses the M- or H-matrix property. Instead, our results are obtained by generalizing the theory of diagonal dominant matrices from the scalar to the block case. Based on this generalization we present bounds on the norms of the inverses of general block tridiagonal matrices and derive a variant of the Gershgorin Circle Theorem that provides eigenvalue inclusion regions in the complex plane that are potentially tighter than the usual sets derived from the classical definition.
Bestimmte Approximationstechniken für die numerische Lösung partieller Differentialgleichungen führen zu linearen algebraischen Systemen, bei denen die Koeffizientenmatrix nicht symmetrisch, nicht normal und schlecht konditioniert ist. Dies ist der Fall zum Beispiel bei der Diskretisierung der Konvektions-Diffusions-Gleichung, die in dieser Arbeit auf einem Shishkin-gitter aufgestellt wurde. Wir stellen eine Konvergenzanalyse der (algebraischen) multiplikativen Schwarz-Methode vor, wenn sie zur Lösung linearer Systeme verwendet wird, die sich sowohl aus dem Upwind als auch aus dem zentralen Finite-Differenz-Diskretisierungsansatz für solche Probleme ergeben. Für ein- und zweidimensionale Probleme zeigen wir, dass die Iterationsmatrix der Methode einen niedrigen Rang hat, was uns erlaubt, ihre infinity-Norm abzuschätzen. Diese Schranken führen zu quantitativen Fehlerschranke für die Iterationen der Methode, die ab dem ersten Schritt des Iterationsprozesses gültig sind. Bei eindimensionalen Problemen beweisen wir eine schnelle Konvergenz der Methode für alle Parameterwahlen des Problems, wenn der Upwind-Diskretisierungsansatz verwendet wird, während die Konvergenz nur für bestimmte Parameterwahlen für den zentralen Differenzansatz nachgewiesen werden kann. Bei zweidimensionalen Problemen wird nur die Upwind-Diskretisierung berücksichtigt. Darüber hinaus betrachten wir die Methode als Vorkonditionierer von GMRES und weisen die Konvergenz der vorkonditionierten Methode in wenigen Schritten nach, wenn die lokalen Teilbereichsprobleme exakt gelöst werden. Numerische Experimente zeigen, dass bei zweidimensionalen Problemen die Anzahl der Iterationen entweder gleich bleibt oder bei ungenauen lokalen Lösungen abnimmt, wodurch eine Beschleunigung der Rechenzeit erreicht wird. Wir fahren fort, indem wir unsere Konvergenzergebnisse auf den Fall verallgemeinern, dass die Koeffizientenmatrix des linearen Systems eine spezielle Blockstruktur besitzt, die sich z.B. ergibt, wenn eine partielle Differentialgleichung auf einem Gebiet gestellt und diskretisiert wird, die aus zwei Untergebiete besteht, die sich überlappen. Unsere Analyse geht nicht davon aus, dass die aus dem Diskretisierungsprozess resultierenden Systemmatrizen symmetrisch (positiv definit) sind oder die Eigenschaft der M- oder H-Matrix besitzen. Stattdessen erhalten wir unsere Ergebnisse durch Verallgemeinerung der Theorie der diagonaldominanten Matrizen vom skalaren zum Blockfall. Basierend auf dieser Verallgemeinerung beschränken wir die Norm der Inversen von allgemeinen Blocktridiagonalmatrizen und leiten eine Variante des Satz von Gershgorin her. Die Eigenwert-Einschlussbereiche in der komplexen Ebene liefert, die potenziell kleiner sind als die klassischen Gershgorin-Kreise.