Kurs:Numerik I/Lineare Ausgleichsrechnung

Einleitung

Diese Seite kann als Wiki2Reveal Folien angezeigt werden. Einzelne Abschnitte werden als Folien betrachtet und Änderungen an den Folien wirken sich sofort auf den Inhalt der Folien aus.

Notation

Um die $0 \in 𝕂$ aus dem verwendeten Körper von dem Nullvektor $0_{V} \in V$ aus dem Vektorraum $V$ zu unterscheiden, wird bei der Verwendung des Nullvektors $0_{V}$ mit $V$ indiziert.

Problemstellung

In der Praxis hat man häufig auch ein überbestimmtes lineares Gleichungssystem $A x = b$ für eine Matrix $A \in ℝ^{n \times k}$ mit $n > k$ und eine rechte Seite $b \in ℝ^{n}$ zu „lösen“. Da ein solches System mehr Gleichungen als Unbekannte hat, ist im Allgemeinen $A x - b \neq 0$ für alle $x \in ℝ^{k}$ und besitzt es somit keine exakte Lösung.

Vorgehen - Minimierung des Fehlers

Es macht also Sinn, ein $x^{*}$ als „Lösung“ zu akzeptieren, für welches der Defekt $A x - b$ hinsichtlich einer gewählten $l_{p}$ -Norm $‖ \cdot ‖_{p}$ auf dem $ℝ^{k}$ minimal wird, also eine Lösung $x^{*}$ des Problems

\inf_{x \in ℝ^{k}} ‖ b - A x ‖_{p} .

Euklidische Norm - Minimierung des Fehlers 1

Im Fall der Verwendung der $l_{2}$ - bzw. Euklidischen Norm lautet dieses Problem

\inf_{x \in ℝ^{k}} ‖ b - A x ‖_{2},

Im Hinblick auf eine Lösung kann man auch ein äquivalentes Problem bearbeiten, indem man den zu minimierende Ausdruck quadriert:

\inf_{x \in ℝ^{k}} ‖ b - A x ‖_{2}^{2}

Euklidische Norm - Minimierung des Fehlers 2

Die Äquivalenz ergibt sich aus der strengen Monotonie von $f (x) = x^{2}$ für $x \geq 0$ und der Eigenschaft der Norm, die einen nicht-negativen Wert liefert. Die Funktionen $E_{2} (x) : = ‖ b - A x ‖_{2}$ und $E (x) : = ‖ b - A x ‖_{2}^{2}$ haben offenbar dieselben Minimalpunkte $x$ , sofern solche existieren.

Euklidische Norm - Differenzierbarkeit 3

Ferner ist die minimierende Funktion $E (x) : = ‖ b - A x ‖_{2}^{2}$ für alle $x \in ℝ^{k}$ differenzierbar.

Euklidische Norm - Fehlerquadratmethode 4

Bei Wahl der $l_{2}$ -Norm minimiert man also die Summe der Fehlerquadrate, und man spricht daher auch von Fehlerquadratmethode oder von diskreter $l_{2}$ -Approximation.

Nicht-differenzierbare Fehlerfunktionen 5

Die Lösung des entsprechenden Problems für die $l_{1}$ - und die $l_{\infty}$ - bzw. Tschebyscheff-Norm ist ebenfalls von großem praktischen Interesse, führt aber auf nichtdifferenzierbare Funktionen $E_{1} (x) : = ‖ b - A x ‖_{1}$ bzw. $E_{\infty} (x) : = ‖ b - A x ‖_{\infty}$ , so dass diese Probleme schwieriger zu lösen sind. (Man kann letztere Probleme als lineare Optimierungsprobleme formulieren und beispielsweise mit dem sog. Simplexalgorithmus lösen.

Bemerkung - Euklidische Norm - Fehlerquadratmethode 6

Bevor wir nun das Problem für $E (x) : = ‖ b - A x ‖_{2}^{2}$ weiter untersuchen, wollen wir zunächst zwei Aufgabenstellungen beschreiben und analysieren, die auf ein derartiges über-bestimmtes Gleichungssystem führen.

Anwendung in Naturwissenschaft und Technik

In Naturwissenschaft und Technik hat man oft das Problem, mit einer großen Zahl von Messwerten umgehen zu müssen. Ein anderes, sich häufig stellendes Problem ist es, eine in endlich vielen Punkten gegebene Funktion, welche durch eine rechenaufwändige Vorschrift bestimmt ist, durch eine einfacher zu berechnende zu ersetzen. Beide Probleme kann man gemeinsam angehen und als $l_{2}$ -Approximationsprobleme beschreiben.

Daten und Messwerte

Wir gehen dazu von $n$ Zahlenpaaren

(t_{j}, y_{j}), j = 1, \dots, n

mit $t_{r} \neq t_{s}$ für $r \neq s$ aus, wobei üblicherweise $n$ groß ist. Beispielsweise können die $y_{j} \in ℝ$ irgendwelche zu unterschiedlichen Zeitpunkten $t_{j} \in ℝ$ gemessene Werte oder, im Hinblick auf die Approximation einer gegebenen Funktion $f$ , die Funktionswerte $y_{j} : = f (t_{j})$ zu gewissen Zeitpunkten $t_{j}$ des Definitionsbereichs von $f$ sein.

Ziel der Ausgleichsrechnung 1

Das Ziel der Ausgleichsrechnung ist es nun, durch geeignete Wahl eines Parametervektors $x : = (x_{1}, \dots, x_{k})^{T} \in ℝ^{k}$ eine Funktion der Gestalt

z (x, t) : = x_{1} v_{1} (t) + x_{2} v_{2} (t) + \dots + x_{k} v_{k} (t), t \in ℝ

mit $k$ gegebenen stetigen Ansatzfunktionen $v_{i}$ zu finden, so dass die Fehlerquadrate

(y_{j} - z (x, t_{j}))^{2}, j = 1, \dots, n

möglichst klein ausfallen.

Ziel der Ausgleichsrechnung 2

Dabei sollte sinnvollerweise $k \leq n$ sein und ist zumeist $k ≪ n$ . Hat man einen solchen Parametervektor $x$ bzw. eine solche Funktion $z (x, \cdot)$ gefunden und sind die Approximationsfehler in (4.5) nicht zu groß, so kann man statt mit den Daten (4.3) nur mit dieser Funktion arbeiten, für die im Fall $k ≪ n$ erheblich weniger Information, nämlich nur der Vektor $x$ , abgespeichert werden muss. Weil $z (x, \cdot)$ eine stetige Funktion ist, erlaubt ein solches Vorgehen außerdem, Werte $y$ zu Werten bzw. „Zeiten“ $t$ zu berechnen, für die keine Messung vorliegt.

Polynomapproximation mit Monomen

Die Ansatzfunktionen hat man so zu wählen, dass sie den gemessenen Prozess möglichst gut beschreiben. Häufig, insbesondere dann, wenn man wenig über den gegebenen Prozess weiß, verwendet man die Monome

v_{i} (t) : = t^{i - 1} (i = 1, \dots, k)

so dass

z (x, t) : = x_{1} + x_{2} t + \dots + x_{k} t^{k - 1}, t \in ℝ

ein Polynom vom Grad $\leq k - 1$ ist (Polynomapproximation).

Approximation periodische Prozesse

Wenn es sich um einen periodischen Prozess handelt, ist es aber beispielsweise günstiger, die $k : = 2 p + 1$ Funktionen

\begin{matrix} v_{1} (t) & = & 1 \\ v_{2} (t) & = & \sin (t), v_{3} (t) = \cos (t) \\ v_{4} (t) & = & \sin (2 t), v_{5} (t) = \cos (2 t) \\ \dots & = & \dots \\ v_{k} (t) & = & \sin (p t), v_{k + 1} (t) = c o s (p t) \end{matrix}

als Ansatzfunktionen zu wählen (trigonometrische Approximation), weil man dann im Allgemeinen bei gleicher Anzahl von Funktionen kleinere Fehler erhält.

Bemerkung - weitere Approximationen

Andere Systeme von Ansatzfunktionen können ebenfalls vernünftig sein. Die Wahl der Ansatzfunktionen hängt von dem Wissen über das modellierte System ab.

Summation von Fehlern bei der Approximation

Nun ist es nicht sinnvoll, $x$ so zu wählen, dass die Summe aller Fehler

y_{j} - z (x, t_{j}), j = 1, \dots, n

möglichst klein wird, da diese Summe auch bei großen Einzelfehlern sehr klein werden kann, nämlich dann, wenn sich die positiven und negativen Fehler (nahezu) aufheben.

Beispiel Summation von Fehlern bei der Approximation

Nehmen wir als Beispiel $y_{1} = 100$ , $y_{2} = - 97$ und $z (x, t_{1}) = 3$ , $z (x, t_{2}) = 1$ . Berechnet man die Fehlersumme, ergibt sich:

\underset{= 2 - 100 = - 98}{\underset{⏟}{(y_{1} - z (x, t_{1}))}} + \underset{= 1 - (- 97) = 98}{\underset{⏟}{(y_{2} - z (x, t_{2}))}} = 0

Der aggregierte Fehler "suggeriert", dass es keine Abweichung von den gemessenen Werten zu den approximierten Werten gibt, obwohl die Einzelfehler in den beide Messdaten betragsmäßig jeweils um 98 abweichen.

Summation von Fehlerquadraten bei der Approximation

Die Größe des Fehlervektors $(y_{j} - z (x, t_{j}))_{j = 1, \dots, n}$ misst man daher mit einer $l_{p}$ -Norm im $ℝ^{n}$ . Insbesondere führt dann die Verwendung der quadrierten $l_{2}$ - bzw. Euklidischen Norm (siehe den Kommentar auf die für alle $x \in ℝ^{k}$ differenzierbare Funktion

\tilde{F} (x) : = \sum_{j = 1}^{n} (y_{j} - z (x, t_{j}))^{2} .

Von den Ansatzfunktionen zur Matrix

Mit folgenden Setzungen erhält man ein lineare Gleichungssystem $A x = b$ .

b : = (\begin{matrix} y_{1} \\ ⋮ \\ y_{j} \\ ⋮ \\ y_{n} \end{matrix}), A : = (\begin{matrix} v_{1} (t_{1}) & \dots & v_{k} (t_{1}) \\ ⋮ & ⋮ \\ v_{1} (t_{j}) & \dots & v_{k} (t_{j}) \\ ⋮ & ⋮ \\ v_{1} (t_{n}) & \dots & v_{k} (t_{n}) \end{matrix}) .

Dabei sucht man geeignete $x \in ℝ^{n}$ , die den Fehler minimieren.

Summe der Fehlerquadrate und Normen

Damit kann eine Fehlerfunktion wie folgt geschrieben werden:

\tilde{F} (x) : = \sum_{j = 1}^{n} (y_{j} - z (x, t_{j}))^{2} = \sum_{j = 1}^{n} (b_{j} - (A x)_{j})^{2} = ‖ b - A x ‖_{2}^{2} .

Das beschriebene Problem der Ausgleichsrechnung ist also von der Form

\inf_{x \in ℝ^{n}} ‖ b - A x ‖_{2}^{2}

,

wobei $A$ und $b$ durch Messdaten $(t_{j}, y_{j}) \in ℝ^{2}$ gegeben sind.

Problem der Ausgleichsrechnung

Wir betrachten nun allgemein das Problem einer zu minimierende (Fehler-)Funktion

F (x) : = ‖ b - A x ‖_{2}^{2} = ⟨ b - A x, b - A x ⟩ = (b - A x)^{T} (b - A x) .

Bemerkung: Euklidische Skalarprodukt und Matrixmultiplikation

Für $x, y \in ℝ^{n}$ kann man das Euklische Skalarprodukt auch als Matrizenprodukt darstellen, indem man $x, y \in ℝ^{n}$ als Spaltenvektoren auffasst:

⟨ x, y ⟩ = x^{T} \cdot y = \sum_{i = 1}^{n} x_{i} \cdot y_{i}

Anwendung auf die Fehlerfunktion - Matrixrechenregeln

Über Matrixrechenregeln erhält man:

F (x) = (b - A x)^{T} (b - A x) = b^{T} b - (A x)^{T} b - b^{T} A x + \underset{= x^{T} A^{T} A x}{\underset{⏟}{(A x)^{T} A x}}

als quadratische Funktion in $k$ Veränderlichen $x = (x_{1}, \dots, x_{k})^{T}$

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

schreiben. Für die darin vorkommende Matrix $A^{T} A$ kann man aussagen:

Anwendung auf die Fehlerfunktion - Skalarprodukt

Über die Verwendung, dass das Skalarprodukt eine symmetrische Bilinearform ist, erhält man:

\begin{matrix} F (x) & = & ⟨ b - A x, b - A x ⟩ \\ = & ‖ b ‖_{2}^{2} - \underset{= ⟨ b, A x ⟩}{\underset{⏟}{⟨ A x, b ⟩}} - ⟨ b, A x ⟩ + \underset{= ⟨ x, A^{T} A x ⟩}{\underset{⏟}{‖ A x ‖_{2}^{2}}} \\ = & ‖ b ‖_{2}^{2} - 2 \cdot ⟨ b, A x ⟩ + \underset{= \frac{1}{2} ⟨ x, 2 A^{T} A x ⟩}{\underset{⏟}{‖ A x ‖_{2}^{2}}} \end{matrix}

als quadratische Funktion in $k$ Veränderlichen $x = (x_{1}, \dots, x_{k})^{T}$

F (x) = \frac{1}{2} ⟨ x, (2 A^{T} A) x ⟩ - ⟨ 2 A^{T} b, x ⟩ + ‖ b ‖_{2}^{2}

schreiben. Für die darin vorkommende Matrix $A^{T} A$ kann man aussagen:

Lemma - Positiv Definitheit - Rang - symmetrische Matrizen

Sei $A \in ℝ^{n \times k}$ mit $n \geq k$ und $Rang (A) = k$ . Dann ist die Matrix $A^{T} A \in ℝ^{k \times k}$ positiv definit.

Beweis

Die Matrix $A^{T} A$ ist wegen $(A^{T} A)^{T} = A^{T} A$ symmetrisch. Weiter ist sie positiv semidefinit, d. h. es gilt

h^{T} (A^{T} A) h = (A h)^{T} (A h) = ‖ A h ‖_{2}^{2} \geq 0, h \in ℝ^{k} .

Wegen $Rang (A) = k$ sind die $k$ Spalten $a^{1}, \dots, a^{k}$ von $A$ linear unabhängig (Zeilenrang = Spaltenrang) und daher hat man

h^{T} (A^{T} A) h = 0 \Leftrightarrow ‖ A h ‖_{2} = 0 \Leftrightarrow A h = 0 \Leftrightarrow h = 0 .

q.e.d.

Bemerkung - Rangbedingung

Im Fall der Ausgleichsrechnung mit den polynomialen oder trigonometrischen Ansatzfunktionen ist die Rangbedingung in dem Lemma zur positiv Definitheit von symmetrische Matrizen unter unserer Voraussetzung $n \geq k$ immer erfüllt. Dies besagt das folgenden das folgende Lemma.

Lemma - Rangbedingungen polynomiale/trigonometrische Ansatzfunktionen

Für polynomiale oder trigonometrische Ansatzfunktionen besitzt die gebildete Matrix $A \in ℝ^{n \times k}$ mit

A : = (\begin{matrix} v_{1} (t_{1}) & \dots & v_{k} (t_{1}) \\ ⋮ & ⋮ \\ v_{1} (t_{j}) & \dots & v_{k} (t_{j}) \\ ⋮ & ⋮ \\ v_{1} (t_{n}) & \dots & v_{k} (t_{n}) \end{matrix}) .

und $n \geq k$ den $Rang (A) = k$ .

Beweis - Rangbedingungen polynomiale/trigonometrische Ansatzfunktionen

Für das oben angegebene $A$ und $h : = (h_{1}, \dots, h_{k})^{T} \in ℝ^{k}$ gilt:

A h = 0 \Leftrightarrow \sum_{i = 1}^{k} h_{i} v_{i} (t_{j}) = 0 (j = 1, \dots, n) .

Beweis 1 - polynomial Ansatzfunktionen

Wird $A$ insbesondere durch polynomiale Ansatzfunktionen spezifiziert, so implizieren wegen $n \geq k$ die Gleichungen $\sum_{i = 1}^{k} h_{i} v_{i} (t_{j}) = 0$ , dass ein von Null verschiedenes Polynom vom Grad $\leq k - 1$ dann $k$ verschiedene Nullstellen.

Beweis 2 - Fundamentalsatz der Algebra

Nach dem Fundamentalsatz der Algebra kann ein solches Polynom aber höchstens $k - 1$ Nullstellen besitzen.

Beweis 3 - trigonometrische Ansatzfunktionen

Für trigonometrische Ansatzfunktionen schließt man analog mittels komplexer Darstellungen des Sinus und Kosinus (siehe z. B. Collatz/Krabs: Approximationstheorie, Teubner, Stuttgart, 1973^[1]).