Mo Logo [Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen] Englische Flagge
Mathematik-Online-Lexikon:

Steilster Abstieg bei quadratischer Funktion

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Übersicht

Für eine quadratische Funktion

$\displaystyle f(x) = \frac{1}{2} x^{\text{t}} A x - b^{\text{t}} x $

mit einer symmetrischen positiv definiten Matrix $ A$ hat ein Iterationsschritt $ x\to y$ der Methode des steilsten Abstiegs die Form

$\displaystyle y = x + t d,\ d = -$grad$\displaystyle f(x) = b - Ax \,. $

Das Minimum von

\begin{displaymath} \begin{array}{rcl} f(x+td) &=& \frac{1}{2} (x+td)^{\text{t... ...,t^2 + (x^{\text{t}}Ad - b^{\text{t}}d)\,t + c \end{array} \end{displaymath}

lässt sich in diesem Fall explizit angeben. Durch Nullsetzen der Ableitung nach $ t$ erhält man

$\displaystyle 0=d^{\text{t}}Ad\, t - (\underbrace{b-Ax}_{d})^{\text{t}}d $

und somit die Formel

$\displaystyle t = \frac{d^{\text{t}} d}{d^{\text{t}}Ad} $

für den Halbgeradenparameter.

Wie die Abbildung zeigt, kann es zu unerwünschten Oszillationen kommen, wenn $ A$ Eigenwerte stark unterschiedlicher Größenordnung besitzt. Ein extremes Beispiel erhält man für

$\displaystyle A = \left(\begin{array}{cc} 1&0 \\ 0&100 \end{array}\right),\quad b = \left(\begin{array}{c} 0 \\ 0 \end{array}\right) \,. $

Für $ x=(\begin{array}{cc} c & 1 \end{array})^{\text{t}}$ ist

$\displaystyle d = -\,\left(\begin{array}{c} c \\ 100 \end{array}\right),\quad Ad = -\, \left(\begin{array}{c} c \\ 10^4 \end{array}\right) $

und

$\displaystyle d^{\text{t}}d = c^2 + 10^4,\quad d^{\text{t}}Ad = c^2 + 10^6,\quad t = \frac{c^2 + 10^4}{c^2 + 10^6} \,. $

Damit folgt

$\displaystyle y= \left(\begin{array}{c} c \\ 1 \end{array}\right) - \frac{... ...}{c^2 + 10^6} \left(\begin{array}{c} 10^4/c \\ -1 \end{array}\right) \,. $

Konkret erhält man für $ c=100$

$\displaystyle y = \frac{99}{101} \left(\begin{array}{c} x_1 \\ -x_2 \end{array}\right) \,. $

Man erkennt, dass in jedem Iterationsschritt der Abstand zum Minimum im Ursprung nur um weniger als $ 1\%$ verringert wird.

[Verweise]
  automatisch erstellt am 22.  6. 2016