06.1 – Minimum mit dem Gradientenverfahren finden

 

Mit Hilfe des Gradientenverfahrens soll das Minimum der Funktion

f\left( {{x_1},{x_2}} \right) = \frac{1}{2}\left( {x_1^2+\lambda x_2^2} \right)

bestimmt werden.

  1. Schreiben Sie f in der Form f\left( x \right) = \frac{1}{2} x^T Ax-b^Tx, wobei x = {\left( {{x_1},{x_2}} \right)^T}.
  2. Um das Minimum von f zu bestimmen, kann auch ein Gleichungssystem gelöst werden. Geben Sie dieses an.
  3. Bestimmen Sie die Konditionszahl von A bezüglich der 2-Norm.
  4. Aus der Vorlesung kennen Sie die Abschätzung

    {\left\| {{x_{k+1}}-{x^*}} \right\|_A} \leq {q^{k+1}}{\left\| {{x_0}-{x^*}} \right\|_A},\quad q = \frac{{\kappa -1}}{{\kappa +1}}

    Dabei ist \kappa die Konditionszahl von {B^{-1}}A mit Vorkonditionierungsmatrix B. Zeigen Sie, dass diese Abschätzung hier für B = I und {x_0} = \left( {1,\frac{1}{\lambda }} \right) scharf ist.

Lösung

a )

f\left( x \right) = \frac{1}{2}{x^T}Ax-{b^T}x,\quad x = {\left( {{x_1},{x_2}} \right)^T}

Mit

A = \left( {\begin{array}{*{20}{c}} 1 & 0 \\ 0 & \lambda \\ \end{array} } \right),\quad b = \left( {\begin{array}{*{20}{c}} 0 \\ 0 \\ \end{array} } \right),\quad \lambda \geq 1 (Interessant vor allem für sehr große Eigenwerte)

b )

\nabla f\left( {{x^*}} \right) = 0\quad \Rightarrow \quad A{x^*}-b = 0\quad \Rightarrow \quad A{x^*} = 0

\left( {\begin{array}{*{20}{c}} 1 & 0 \\ 0 & \lambda \\ \end{array} } \right){x^*} = \vec 0\quad \Rightarrow \quad {x^*} = \left( {\begin{array}{*{20}{c}} 0 \\ 0 \\ \end{array} } \right)

c )

Die Konditionszahl bezüglich der 2-Norm berechnet man mit:

{\kappa _2} = \frac{\lambda _{\max} \left( A \right)}{\lambda _{\min }\left( A \right)}

d )

Aus der Vorlesung:

{\left\| {{x_{k+1}}-{x^*}} \right\|_A} \leq {q^{k+1}}{\left\| {{x_0}-{x^*}} \right\|_A},\quad q = \frac{{\kappa -1}} {{\kappa +1}}

Die verwendete Norm ist dabei:

\left\| x \right\|_A^2 = {x^T}Ax

Zu zeigen:

{\left\| {{x_{k+1}}-{x^*}} \right\|_A} = {q^{k+1}}{\left\| {{x_0}-{x^*}} \right\|_A}

Für ein instationäres Iterationsverfahren gilt allgemein:

{x_{k+1}} = {x_k}+\alpha {s_k}

Gradientenverfahren:

{s_k} = b-A{x_k} (wir wollen zum Minimum, also gehen wir immer den steilsten Weg runter)

Hier:

{s_k} = -A{x_k} = \left( {\begin{array}{*{20}{c}} {-x_k^{\left( 1 \right)}} \\ {-\lambda x_k^{\left( 2 \right)}} \\ \end{array} } \right)\quad \Rightarrow \quad {x_{k+1}} = {x_k}+{\alpha _k}{s_k} = \left( {\begin{array}{*{20}{c}} {\left( {1-{\alpha _k}} \right)x_k^{\left( 1 \right)}} \\ {\left( {1-\lambda {\alpha _k}} \right)x_k^{\left( 2 \right)}} \\ \end{array} } \right)

zu beweisen:

{\alpha _k} = \frac{2}{{1+\lambda }}

Aus der Vorlesung wissen wir:

{\alpha _k} = \frac{{{r^T}s}}{{{v^T}s}}

Wobei

s = {B^{-1}}r = r

r = b-A{x_k} = -A{x_k}

v = Ar

mit dem Residuum r. Daraus folgt durch Einsetzen in die bekannte Formel:

\quad \Rightarrow \quad {\alpha _k} = \frac{{{{\left( {A{x_k}} \right)}^T}\left( {-A{x_k}} \right)}}{{{{\left( {Ar} \right)}^T}r}} = \frac{{x_k^T{A^2}{x_k}}}{{x_k^T{A^3}{x_k}}} = \frac{{{{\left( {x_k^{\left( 1 \right)}} \right)}^2}+{\lambda ^2}{{\left( {x_k^{\left( 2 \right)}} \right)}^2}}}{{{{\left( {x_k^{\left( 1 \right)}} \right)}^2}+{\lambda ^3}{{\left( {x_k^{\left( 2 \right)}} \right)}^2}}}

\quad \Rightarrow \quad {\alpha _0} = \frac{{1+{\lambda ^2} \cdot \frac{1}{{{\lambda ^2}}}}}{{1+{\lambda ^3} \cdot \frac{1}{{{\lambda ^2}}}}} = \frac{2}{{1+\lambda }},\quad {x_0} = {\left( {\begin{array}{*{20}{c}} 1 & {\frac{1}{\lambda }} \\ \end{array} } \right)^T}

Wir wollen nun den Beweis mit vollständiger Induktion durchführen.

Induktionsannahme: {\alpha _k} = \frac{2}{{1+\lambda }}

Induktionsanfang: siehe oben

Induktionsschritt: k \to k+1

{\alpha _{k+1}} = \frac{{{{\left( {x_{k+1}^{\left( 1 \right)}} \right)}^2}+{\lambda ^2}{{\left( {x_{k+1}^{\left( 2 \right)}} \right)}^2}}}{{{{\left( {x_{k+1}^{\left( 1 \right)}} \right)}^2}+{\lambda ^3}{{\left( {x_{k+1}^{\left( 2 \right)}} \right)}^2}}} = \frac{{{{\left( {1-{\alpha _k}} \right)}^2}\left( {x_k^{\left( 1 \right)}} \right)+{\lambda ^2}{{\left( {1-\lambda {\alpha _k}} \right)}^2}\left( {x_k^{\left( 2 \right)}} \right)}}{{{{\left( {1-{\alpha _k}} \right)}^2}\left( {x_k^{\left( 1 \right)}} \right)+{\lambda ^3}{{\left( {1-\lambda {\alpha _k}} \right)}^2}\left( {x_k^{\left( 2 \right)}} \right)}}

Einsetzen der Induktionsannahme:

{\alpha _{k+1}} = \frac{{{{\left( {\frac{{-1+\lambda }}{{1+\lambda }}} \right)}^2}{{\left( {x_k^{\left( 1 \right)}} \right)}^2}+{\lambda ^2}{{\left( {\frac{{1-\lambda }}{{1+\lambda }}} \right)}^2}{{\left( {x_k^{\left( 2 \right)}} \right)}^2}}}{{{{\left( {\frac{{-1+\lambda }}{{1+\lambda }}} \right)}^2}{{\left( {x_k^{\left( 1 \right)}} \right)}^2}+{\lambda ^3}{{\left( {\frac{{1-\lambda }}{{1+\lambda }}} \right)}^2}{{\left( {x_k^{\left( 2 \right)}} \right)}^2}}} = \frac{{{{\left( {x_k^{\left( 1 \right)}} \right)}^2}+{\lambda ^2}{{\left( {x_k^{\left( 2 \right)}} \right)}^2}}}{{{{\left( {x_k^{\left( 1 \right)}} \right)}^2}+{\lambda ^3}{{\left( {x_k^{\left( 2 \right)}} \right)}^2}}} = {\alpha _k} = \frac{2}{{1+\lambda }}

Die Schrittweite ist also für alle k gleich.

x_{k+1}^TA{x_{k+1}} = {\left( {x_{k+1}^{\left( 1 \right)}} \right)^2}+\lambda {\left( {x_{k+1}^{\left( 2 \right)}} \right)^2}

= {\left( {1-{\alpha _k}} \right)^2}{\left( {x_k^{\left( 1 \right)}} \right)^2}+\lambda {\left( {1-\lambda {\alpha _k}} \right)^2}{\left( {x_k^{\left( 2 \right)}} \right)^2}

= {\left( {\frac{{\lambda -1}}{{\lambda +1}}} \right)^2}\left( {{{\left( {x_k^{\left( 1 \right)}} \right)}^2}+\lambda {{\left( {x_k^{\left( 2 \right)}} \right)}^2}} \right)

= {\left( {\frac{{\lambda -1}}{{\lambda +1}}} \right)^2}x_k^TA{x_k}

Daraus folgt:

\quad \Rightarrow \quad {\left\| {{x_{k+1}}} \right\|_A} = \frac{{\kappa -1}}{{\kappa +1}}{\left\| {{x_k}} \right\|_A}

\quad \Rightarrow \quad {\left\| {{x_{k+1}}} \right\|_A} = {\left( {\frac{{\kappa -1}}{{\kappa +1}}} \right)^{k+1}}{\left\| {{x_0}} \right\|_A}

Da \kappa = \lambda gilt, haben wir für große \lambda eine schlechte Konvergenz! Wenn wir ungünstig starten, wird die Norm des Vektors x in jedem Schritt nur unwesentlich kleiner.