Näherungslösung überbestimmtes Gleichungssystem

Question

Hallo liebe Wissende :)

Wir hatten heute in der Vorlesung folgenden Satz:

"Für eine Matrix $A\in R^{n\times m}$ mit n>m gelte m=rang(A). Dann erhält man die beste Näherungslösung (im Sinne der kleinsten Quadrate) des überbestimmten Gleichungssystems $Ax=b$  durch Lösen der Gleichung $A^TAx=A^Tb$."

Den Beweis des Profs kann ich nachvollziehen, habe aber nicht wirklich verstanden, warum das so ist. Kann mir vielleicht jemand erklären, warum das im Sinne der kleinsten Quadrate die beste Näherungslösung ist? Ich hätte gerne ein Bild im Kopf, damit ich das verstehe.

Vielen Dank vorab

Patty

Answer 1

Aloha :)

Ich versuche mal eine anschauliche Erklärung anhand eines einfachen Beispiels, das du aber auf beliebig komplizierte Anwendungen erweitern kannst. Wir betrachten folgende 3 Gleichungen mit 2 Variablen: $$2x-y=2\quad;\quad x+2y=1\quad;\quad x+y=4$$Du hast mehr Gleichungen als Variablen, solche Gleichungssysteme heißen "überbestimmt" und sind in der Regel nicht exakt lösbar. Du könntest $x$ und $y$ so bestimmen, dass 2 Gleichungen exakt gelöst werden, die dritte mit diesen $x$- und $y$-Werten aber völlig daneben liegt. Besser wäre es, eine Näherungslösung zu finden, die alle 3 Gleichungen "möglichst gut" erfüllt. Wenn z.B. $x_0=1,4$ und $y_0=0,5$ gewählt werden, erhalten wir folgende Abweichungen $r_i$:$$2x_0-y_0=2\,\underbrace{+\,0,3}_{r_1}\quad;\quad x_0+2y_0=1\,\underbrace{+\,1,4}_{=r_2}\quad;\quad x_0+y_0=4\,\underbrace{-2,1}_{=r_3}$$Um diese Abweichungen $r_i$ geschickt zu wählen, setzen wir das Problem nun auf eine geometrische Ebene. Dazu schreiben wir die 3 Gleichungen in Matrix-Schreibweise auf:$$\underbrace{\left(\begin{array}{c}2 & -1\\1 & 2\\1 & 1\end{array}\right)}_{=:A}\cdot\underbrace{\left(\begin{array}{c}x\\y\end{array}\right)}_{=:\vec x}=\underbrace{\left(\begin{array}{c}2\\1\\4\end{array}\right)}_{=:\vec b}\quad\text{nicht lösbar!}$$Nicht lösbar ist das System deswegen, weil sich der Vektor $b$ nicht als Linearkombination der Spaltenvektoren vom $A$ schreiben lässt. Mit dem Trick von oben addieren wir auf der rechten Seite einen "Rest-Vektor" $\vec r$, den wir so wählen können, dass sich die komplette rechte Seite $\vec b+\vec r$ als Linearkombination der Spaltenvektoren von $A$ schreiben lässt:$$\underbrace{\left(\begin{array}{c}2 & -1\\1 & 2\\1 & 1\end{array}\right)}_{=A}\cdot\underbrace{\left(\begin{array}{c}x\\y\end{array}\right)}_{=\vec x}=\underbrace{\left(\begin{array}{c}2\\1\\4\end{array}\right)}_{=\vec b}+\underbrace{\left(\begin{array}{c}r_1\\r_2\\r_3\end{array}\right)}_{=:\vec r}$$Geometrisch bedeutet dies Folgendes. Der Vektor $\vec b$ liegt außerhalb der (Hyper-)Ebene, die durch die Spaltenvektoren von $A$ aufgespannt wird. Durch Addition eines geeigneten Vektors $\vec r$ zu $\vec b$ können wir jedoch bewirken, dass der Summenvektor $\vec b+\vec r$ in dieser (Hyper-)Ebene liegt. Für $\vec r$ muss bisher nur$$\vec r=A\vec x-\vec b$$gelten, ansonsten können wir ihn noch frei wählen. Die Idee hinter dem Satz aus deiner Vorlesung ist nun, diesen Vektor $\vec r$ "möglichst kurz" zu wählen. Der Vektor $\vec r$ ist genau dann am kürzesten, wenn er senkrecht auf der (Hyper-)Ebene steht, die durch die Spaltenvektoren von $A$ aufgespannt wird. Aus Sicht des Endpunktes von $\vec b$ geht es dann nämlich direkt senkrecht in Richtung (Hyper-)Ebene. Wenn der Vektor $\vec r$ aber senkrecht auf dieser (Hyper-)Ebene steht, dann steht er auch senkrecht auf allen Spaltenvektoren von $A$, die diese (Hyper-)Ebene aufspannen. Das Skalarprodukt aus allen Spaltenvektoren von $A$ und $\vec r$ muss also $0$ sein. Bei der Matrix-Multiplikation heißt es "Zeile mal Spalte", daher können wir die Matrix $A$ zu $A^T$ transponieren und die gefundene Bedinung in der Form $A^T\cdot\vec r=\vec 0$ formulieren. Das bedeutet:$$A^T\vec r=\vec 0\quad\Leftrightarrow\quad A^T(A\vec x-\vec b)=\vec 0\quad\Leftrightarrow\quad A^TA\vec x=A^T\vec b$$Ich hoffe, diese Beschreibung hat dir beim Verständnis etwas geholfen. Falls nicht, frag bitte einfach noch, was dir unklar ist.

Comments

Boah Tschaka!!! Das ist eine super Erklärung, ich habe das alles sofort verstanden. Vielen Dank dafür... \o/

Answer 2

^{Wie haben einen Artikel dazu in der Datenbank}

^{https://www.mathelounge.de/529251/artikel-regression-berechnung-regr…}

^{vielleicht hilft der zue Erkenntnis?}

^{"Gegeben seien n Datenpaar.."}

^{nach diesem Text solltest Du im Kommentar weiterlesen....}

Comments

Danke dir für den Link. Er beschreibt einen speziellen Anwendungsfall des Satzes. Aber leider wird der Satz dort sofort angewendet. Es wird nicht erklärt, warum der Satz gilt.

---

Die Begründung ist enthalten (Kommentar) entsprechend dem Minimieren der Abstände über die part. Ableitungen - Gradient der Abweichungsquatrate...

---

Oops, die Kommentare hatte ich gar nicht richtig gesehen. Die Erklärung ist da besser als in meiner Vorlesung, der Beweis ist verständlicher. Aber ich bin irgendwie zu doof, ich habe das Gefühl es immer noch nicht wirklich verstanden zu haben. Aber vielen Dank für deinen Tipp :)

---

Zum Rumprobieren hilft vielleicht

https://www.geogebra.org/m/YjjE9nwR

und die Links auf dem Worksheet