07.2 – Lösung eines überbestimmten Gleichungssystems

 

Es soll das überbestimmte Gleichungssystem Ax = b mit

A \in {\mathbb{R}^{m \times n}},\quad x \in {\mathbb{R}^n},\quad b \in {\mathbb{R}^m},\quad m > n

gelöst werden. Da es im Allgemeinen keine Lösung gibt, ist als sinnvoller Ausweg eine Ausgleichslösung \tilde x zu suchen, so dass

{\left\| {A\tilde x-b} \right\|_2} \leq {\left\| {Ax-b} \right\|_2}\quad \forall x \in {\mathbb{R}^n}

bzw.

F\left( {\tilde x} \right) \to \min mit F\left( x \right): = \frac{1} {2}\left\| {Ax-b} \right\|_2^2

  1. Geben sei eine notwendige Bedingung für ein Minimum von F an
  2. Zeigen Sie, dass diese Bedingung auch hinreichend ist
  3. Zeigen Sie, dass b-A\tilde x orthogonal auf dem Bild von A steht
  4. Zeigen Sie, dass für jede orthogonale Matrix Q \in {\mathbb{R}^{m \times m}} gilt: \tilde x ist Ausgleichslösung von Ax = b genau dann, wenn \tilde x Ausgleichslösung von QAx = Qb ist.
  5. Wir wählen nun Q so, dass

    QA = \left( {\begin{array}{*{20}{c}} R \\ 0 \\ \end{array} } \right)

    wobei R \in {\mathbb{R}^{n \times n}} eine reguläre obere Dreiecksmatrix ist. Zeigen Sie, dass \tilde x eine Lösung von Rx = {b_1} ist, wobei {b_1} \in {\mathbb{R}^n} und Qb = {\left( {\begin{array}{*{20}{c}}{{b_1}} & {{b_2}} \\ \end{array} } \right)^T}

Lösung

a )

F\left( x \right) = \frac{1}{2}{\left( {Ax-b} \right)^T}\left( {Ax-b} \right)

= \frac{1}{2}\left( {{x^T}{A^T}-{b^T}} \right)\left( {Ax-b} \right)

= \frac{1}{2}\left( {{x^T}{A^T}Ax-{x^T}{A^T}b-{b^T}Ax+{b^T}b} \right)

= \frac{1}{2}\left( {{x^T}{A^T}Ax-2{x^T}{A^T}b+{b^T}b} \right)

Notwendige Bedingung für Minimum: Ableitung verschwindet

0 = \nabla F\left( x \right) = {A^T}Ax-{A^T}b\quad \Rightarrow \quad {A^T}Ax = {A^T}b (Normalengleichung)

b )

Es sei

{A^T}A\tilde x = {A^T}b

Ax-b = A\tilde x-b+Ax-A\tilde x = A\tilde x-b+A\left( {x+\tilde x} \right)

2F\left( x \right) = {\left( {Ax-b} \right)^T}\left( {Ax-b} \right)

= {\left( {A\tilde x+b+A\left( {x-\tilde x} \right)} \right)^T}\left( {A\tilde x+b+A\left( {x-\tilde x} \right)} \right)

= F\left( {\tilde x} \right)+{\left( {x-\tilde x} \right)^T}{A^T}A\left( {x-\tilde x} \right) \geq F\left( {\tilde x} \right)

da {A^T}A positiv semidefinit ist. Dies ist der Fall, weil {x^T}{A^T}Ax = {y^T}y \geq 0 für y = Ax.
Gleichheit gilt genau dann, wenn y = 0.

c )

\left( {b-A\tilde x} \right)Ax = {b^T}Ax-{{\tilde x}^T}{A^T}Ax

= {x^T}{A^T}b-{x^T}{A^T}A\tilde x

= {x^T}\underbrace {\left( {{A^T}b-{A^T}A\tilde x} \right)}_{ = 0} = 0

d )

Für orthogonale Matrizen gilt

{\left\| x \right\|_2} = {\left\| {Qx} \right\|_2}

weil

{Q^T}Q = I

\left\| x \right\|_2^2 = {x^T}x

\left\| {Qx} \right\|_2^2 = {\left( {Qx} \right)^T}Qx = {x^T}\underbrace {{Q^T}Q}_{ = I}x = {x^T}x

Daraus folgt:

{\left\| {b-Ax} \right\|_2} = {\left\| {Q\left( {b-Ax} \right)} \right\|_2} = {\left\| {Qb-QAx} \right\|_2}

was die Behauptung bestätigt.

e )

Wähle Q so, dass

QA = \left( {\begin{array}{*{20}{c}} R \\ 0 \\ \end{array} } \right)

mit Q \in {\mathbb{R}^{m \times m}},\quad A \in {\mathbb{R}^{m \times n}},\quad R \in {\mathbb{R}^{n \times n}} (R sei obere reguläre Dreiecksmatrix)

Zeige:

\tilde x ist Lösung von Rx = {b_1}, wobei Qb = \left( {\begin{array}{*{20}{c}} {{b_1}} \\ {{b_2}} \\ \end{array} } \right),\quad {b_1} \in {\mathbb{R}^n},\quad {b_2} \in {\mathbb{R}^{m-n}}

Wir können unser lineares Ausgleichsproblem schreiben als

\frac{1}{2}\left\| {Qb-QAx} \right\|_2^2 \to \min

Also

\left\| {\left( {\begin{array}{*{20}{c}} {{b_1}} \\ {{b_2}} \\ \end{array} } \right)-\left( {\begin{array}{*{20}{c}} {Rx} \\ 0 \\ \end{array} } \right)} \right\|_2^2 = \left\| {{b_1}-Rx} \right\|_2^2+\underbrace {\left\| {{b_2}} \right\|_2^2}_{ = const}

Damit müssen wir

\left\| {{b_1}-Rx} \right\|_2^2

minimieren, also folgt:

R\tilde x = {b_1}