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.

siehe auch:


  automatisch erstellt am 22.  6. 2016