Richardson-Verfahren

Richardson-Verfahren

Das Richardson-Verfahren ist in der numerischen Mathematik ein Algorithmus zur näherungsweisen Lösung von linearen Gleichungssystemen. Es zählt wie das Gauß-Seidel-Verfahren zur Klasse der Splitting-Verfahren. Als iteratives Verfahren nähert es sich schrittweise einer Lösung des linearen Gleichungssystems Ax = b an.

Inhaltsverzeichnis

Richardson-Verfahren

Durch Wahl von B = I (Einheitsmatrix) erhält man aus der allgemeinen Fixpunktgleichung

x = Φ(x): = IxB − 1Ax + B − 1b

das Richardsonverfahren.

xk + 1 = (IA)xk + b

Dieses Verfahren konvergiert wie jede Fixpunktiteration dieser Art, falls der Spektralradius der Iterationsmatrix G: = IA echt kleiner eins ist.

Relaxiertes Richardsonverfahren

Die Iterationsformel des relaxierten Richardson-Verfahrens lautet

xk + 1 = (I − ωA)xk + ωb

Dabei wird in jedem Schritt das Residuum mit einem Faktor ω gewichtet. Falls A eine symmetrisch positiv definite Matrix ist so gilt für den optimalen Relaxionsparameter

\omega_{opt} = \frac{2}{\lambda_{max}(A) + \lambda_{min}(A)}.

Dabei bezeichnen λmax(A) und λmin(A) den maximalen und minimalen Eigenwert von A. Für den Konvergenzradius (gleichbedeutend zum Spektralradius) gilt

\rho(G_{w_{opt}}) = \frac{\kappa_2(A) - 1}{\kappa_2(A) + 1} < 1

dabei bezeichnet κ2(A) die Kondition der Matrix A. Das relaxierte Richardson-Verfahren konvergiert dann genauso "schnell" wie das Gradientenverfahren bei symmetrischen Matrizen, wofür man jedoch keinen Relaxionsparameter berechnen muss. Dafür kann man mit dem Richardsonverfahren auch bei unsymmetrischen Matrizen mit komplexen Eigenwerten noch Konvergenz erzwingen, solange deren Realteile alle positiv sind.

Das Verfahren ist als Glätter in Mehrgitterverfahren geeignet.

Zyklisches Richardsonverfahren

Die Konvergenz lässt sich erheblich verbessern, wenn man mehrere Schritte der Iteration mit unterschiedlichen Parametern ωk betrachtet. Man führt dazu jeweils m Schritte

 x_k = x_{k-1} + \omega_{k}(b-Ax_{k-1}),\quad  k=1,\ldots,m

zyklisch durch. Das Verfahren konvergiert, wenn der Spektralradius des Matrixpolynoms

 p_m(A) =(I-\omega_1 A)(I-\omega_2 A)\cdots (I-\omega_m A)

kleiner als eins ist, und umso besser je kleiner er ist. Für eine Matrix A mit reellen und positiven Eigenwerten kann der Spektralradius durch das Maximum des reellen Polynoms  p_m(t) =(1-\omega_1 t)(1-\omega_2 t)\cdots (1-\omega_m t) im Intervall minmax] abgeschätzt werden. Besonders klein wird dieses Maximum, wenn man die Relaxationsparameter so wählt, dass ihre Kehrwerte gerade die Nullstellen des geeignet verschobenen Tschebyschow-Polynoms sind,

\frac2{\omega_k}=\lambda_{min}+\lambda_{max}
 +\left(\lambda_{max}-\lambda_{min}\right)\cos\left(\frac{2k-1}{2m}\pi\right),\ k=1,\ldots,m.

Dann verbessert sich die Konvergenzaussage für symmetrische Matrizen und einen Zyklus der Länge m zu

\rho(p_m(A))\le 2\left(\frac{\sqrt{\kappa_2(A)}-1}{\sqrt{\kappa_2(A)}+1}\right)^m.

Für realistische Probleme mit \kappa_2(A)\gg1 stellt dies eine große Verbesserung gegenüber dem einfachen relaxierten Verfahren dar, da nur noch die Wurzel der Konditionszahl eingeht.

Für symmetrisch-definite Matrizen bietet dieses Verfahren kaum Vorteile gegenüber dem Verfahren der konjugierten Gradienten, da es die Schätzung der Eigenwerte λminmax erfordert. Im unsymmetrischen Fall können aber die Parameter auch für komplexe Eigenwerte gut angepasst werden, vgl. Literatur. In den meisten Fällen ist aber die Tschebyschow-Iteration vorzuziehen, da sie die gleiche Fehlerschranke für jeden Iterationsschritt und nicht nur für Vielfache der Zykluslänge k = m, 2m, 3m, \ldots erreicht.

Literatur

  • Andreas Meister: Numerik linearer Gleichungssysteme. 2. Auflage. Vieweg 2005, ISBN 3-528-13135-7
  • Bernd Fischer, Lothar Reichel: A stable Richardson iteration method for complex linear systems. Numer. Math. 54 (1988), 225-242.

Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Richardson — ist ein Familienname, siehe Richardson (Familienname) ein britisches Cyclecar (1919 1922), siehe C. E. Richardson Co. eine britische Automarke, siehe J. R. Richardson Co. eine ehemalige britische Schiffswerft, siehe Richardson, Duck Company… …   Deutsch Wikipedia

  • Richardson-Iteration — Das Richardson Verfahren ist in der numerischen Mathematik ein Algorithmus zur näherungsweisen Lösung von linearen Gleichungssystemen. Es zählt wie das Gauß Seidel Verfahren zur Klasse der Splitting Verfahren. Als iteratives Verfahren nähert es… …   Deutsch Wikipedia

  • Richardson-Extrapolation — Das Verfahren der Richardson Extrapolation wurde von Lewis Fry Richardson (1881–1953) entwickelt. Es kann angewendet werden, wenn man bei der numerischen Lösung eines Problems aufgrund zweier verschiedener Diskretisierungen (mit den Schrittweiten …   Deutsch Wikipedia

  • Numerische Verfahren — Die Liste numerischer Verfahren führt Verfahren der numerischen Mathematik nach Anwendungsgebieten auf. Inhaltsverzeichnis 1 Lineare Gleichungssysteme 2 Nichtlineare Gleichungssysteme 3 Numerische Integration 4 Approximation und Interpolation …   Deutsch Wikipedia

  • Splitting Verfahren — In der numerischen Mathematik sind Splitting Verfahren iterative Verfahren zum Lösen linearer Gleichungssysteme Ax = b mit einer Matrix und rechter Seite Im Unterschied zu direkten Verfahren nähert man sich dabei ausgehend von einer Startnäherung …   Deutsch Wikipedia

  • Liste numerischer Verfahren — Die Liste numerischer Verfahren führt Verfahren der numerischen Mathematik nach Anwendungsgebieten auf. Inhaltsverzeichnis 1 Lineare Gleichungssysteme 2 Nichtlineare Gleichungssysteme 3 Numerische Integration …   Deutsch Wikipedia

  • Splitting-Verfahren — In der numerischen Mathematik sind Splitting Verfahren iterative Verfahren zum Lösen linearer Gleichungssysteme Ax = b mit einer Matrix und rechter Seite Im Unterschied zu direkten Verfahren nähert man sich dabei ausgehend von einer Startnäherung …   Deutsch Wikipedia

  • Krylov-Unterraum-Verfahren — Krylow Unterraum Verfahren sind iterative Verfahren zum Lösen großer, dünnbesetzter linearer Gleichungssysteme, wie sie bei der Diskretisierung von partiellen Differentialgleichungen entstehen oder von Eigenwertproblemen. Sie sind benannt nach… …   Deutsch Wikipedia

  • Lewis Fry Richardson — (* 11. Oktober 1881 in Newcastle upon Tyne; † 30. September 1953 in Kilmun, Argyll) war ein britischer Meteorologe und Friedensforscher. Er berechnete die erste Wettervorhersage, und auch wen …   Deutsch Wikipedia

  • Bill Richardson — (2008) William Blaine („Bill“) Richardson (* 15. November 1947 in Pasadena, Kalifornien) ist ein US amerikanischer Politiker und ehemaliger Gouverneur des Bundesstaates New Mexico. Er ist Mitglied der Demokraten und war Bew …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”