{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"<link rel=\"stylesheet\" href=\"https://maxcdn.bootstrapcdn.com/bootstrap/4.0.0/css/bootstrap.min.css\" integrity=\"sha384-Gn5384xqQ1aoWXA+058RXPxPg6fy4IWvTNh0E263XmFcJlSAwiGgFAW/dAiS6JXm\" crossorigin=\"anonymous\">\n",
"<div class=\"text-center\">\n",
" <h1>Wissenschaftliches Rechnen WiSe 2020/21</h1>\n",
" <h2>Tutorium: Lineare Ausgleichsrechnung</h2>\n",
"</div>"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"<h2>Lineare Ausgleichsrechnung</h2>\n",
"\n",
"Gegeben:\n",
"<ul>\n",
" <li>Matrix $A \\in \\mathbb{R}^{n \\times m}$ mit $n > m$</li>\n",
" <li>$b \\in \\mathbb{R}^n$</li>\n",
"</ul>\n",
"\n",
"Was tun, wenn das LGS $Ax = b$ keine Lösung hat?"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Einen Vektor $x$ wählen, sodass Residuum $r = Ax - b$ bezüglich einer Norm $||\\cdot||$ minimiert wird."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "notes"
}
},
"source": [
"Vektor $b$ liegt nicht im Bild von $A$. Wir suchen stattdessen einen Vektor $\\hat{b}$ im Bild von $A$, welcher möglichst nah an $b$ liegt."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"<h3>Herleitung der Normalengleichung</h3>\n",
"<img src=\"imgs/norm.png\" width=\"100%\">"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"<b>Frage: Wie kann man Orthogonalität ausdrücken?</b>\n",
"\n",
"Durch das Skalarprodukt!"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Vektoren $u$ und $v$ sind orthogonal, falls $u^\\mathsf{T} v = 0$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Residuum muss orthogonal zu allen Spaltenvektoren von A sein:\n",
"\n",
"$$\n",
" A^\\mathsf{T} r = 0\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"$$\n",
" \\begin{bmatrix}\n",
" a_1^\\mathsf{T}\\\\\n",
" a_2^\\mathsf{T}\\\\\n",
" \\vdots\\\\\n",
" a_m^\\mathsf{T}\\\\\n",
" \\end{bmatrix}\n",
" r = \n",
" \\begin{bmatrix}\n",
" a_1^\\mathsf{T} r\\\\\n",
" a_2^\\mathsf{T} r\\\\\n",
" \\vdots\\\\\n",
" a_m^\\mathsf{T} r\n",
" \\end{bmatrix}\n",
" = \n",
" \\begin{bmatrix}\n",
" 0\\\\\n",
" 0\\\\\n",
" \\vdots\\\\\n",
" 0\n",
" \\end{bmatrix}\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"$$\n",
" \\Leftrightarrow A^\\mathsf{T} (Ax - b) = 0\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"$$\n",
" \\Leftrightarrow A^\\mathsf{T}Ax - A^\\mathsf{T}b = 0\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Normalengleichung:\n",
"\n",
"$$\n",
" \\Leftrightarrow A^\\mathsf{T}Ax = A^\\mathsf{T}b\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Falls $A^\\mathsf{T}A$ regulär ist:\n",
"\n",
"$$\n",
" x = (A^\\mathsf{T} A)^{-1} A^\\mathsf{T} b\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Der zu $b$ nächste Punkt im Bild von $A$ ist:\n",
"\n",
"$$ Ax = A (A^\\mathsf{T} A)^{-1} A^\\mathsf{T} b $$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"<h2>Abstand windschiefer Geraden</h2>"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"$$\n",
" g(s) = \\begin{bmatrix} -7\\\\2\\\\-3 \\end{bmatrix} + s \\begin{bmatrix} 0\\\\1\\\\2 \\end{bmatrix}\\\\\n",
" h(t) = \\begin{bmatrix} -3\\\\-3\\\\3 \\end{bmatrix} + t \\begin{bmatrix} 1\\\\2\\\\1 \\end{bmatrix}\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Ansatz:\n",
"\n",
"Finde $s, t \\in \\mathbb{R}$, sodass\n",
"\n",
"$$\n",
" g(s) = h(t)\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"$$\n",
"\\begin{bmatrix} -7\\\\2\\\\-3 \\end{bmatrix} + s \\begin{bmatrix} 0\\\\1\\\\2 \\end{bmatrix} = \\begin{bmatrix} -3\\\\-3\\\\3 \\end{bmatrix} + t \\begin{bmatrix} 1\\\\2\\\\1 \\end{bmatrix}\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"$$\n",
"s \\begin{bmatrix} 0\\\\1\\\\2 \\end{bmatrix} - t \\begin{bmatrix} 1\\\\2\\\\1 \\end{bmatrix} = \\begin{bmatrix} -3\\\\-3\\\\3 \\end{bmatrix} - \\begin{bmatrix} -7\\\\2\\\\-3 \\end{bmatrix}\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"$$\n",
"s \\begin{bmatrix} 0\\\\1\\\\2 \\end{bmatrix} + t \\begin{bmatrix} -1\\\\-2\\\\-1 \\end{bmatrix} \n",
"= \\begin{bmatrix} 4\\\\-5\\\\6 \\end{bmatrix}\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"$$\n",
"\\begin{bmatrix} 0 & -1\\\\1 & -2 \\\\2& -1 \\end{bmatrix} \\begin{bmatrix} s\\\\t\\end{bmatrix}\n",
"= \\begin{bmatrix} 4\\\\-5\\\\6 \\end{bmatrix}\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Normalengleichung:\n",
" \n",
"$$\n",
"\\begin{bmatrix} 0 & 1 & 2\\\\ -1 & -2 & -1 \\end{bmatrix} \\begin{bmatrix} 0 & -1\\\\1 & -2 \\\\2& -1 \\end{bmatrix} \\begin{bmatrix} s\\\\t\\end{bmatrix} = \\begin{bmatrix} 0 & 1 & 2\\\\ -1 & -2 & -1 \\end{bmatrix} \\begin{bmatrix} 4\\\\-5\\\\6 \\end{bmatrix}\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"$$\n",
"\\begin{bmatrix} 5 & -4\\\\ -4 & 6 \\end{bmatrix} \\begin{bmatrix} s\\\\t\\end{bmatrix} = \\begin{bmatrix} 7\\\\ 0\\end{bmatrix}\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"$$\n",
"\\begin{bmatrix} s\\\\t\\end{bmatrix} = \\begin{bmatrix} 3\\\\2\\end{bmatrix}\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Punkte, zwischen denen Abstand minimal ist:\n",
"\n",
"$$\n",
" g(3) = \\begin{bmatrix} -7\\\\2\\\\-3 \\end{bmatrix} + 3 \\begin{bmatrix} 0\\\\1\\\\2 \\end{bmatrix} = \\begin{bmatrix} -7\\\\5\\\\3\\end{bmatrix}\\\\\n",
" h(2) = \\begin{bmatrix} -3\\\\-3\\\\3 \\end{bmatrix} + 2 \\begin{bmatrix} 1\\\\2\\\\1 \\end{bmatrix} = \\begin{bmatrix} -1\\\\1\\\\5 \\end{bmatrix}\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Abstand:\n",
"\n",
"$$\n",
" \\left|\\left| \\; \\begin{bmatrix} -7\\\\5\\\\3\\end{bmatrix} - \\begin{bmatrix} -1\\\\1\\\\5 \\end{bmatrix} \\; \\right|\\right| = \\left|\\left| \\; \\begin{bmatrix} 6\\\\-4\\\\2 \\end{bmatrix} \\; \\right|\\right| \\approx 7.48\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"<div class=\"text-center\">\n",
" <h1>Lineare Regression</h1>\n",
"</div>"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"<h2>Lineare Regression</h2>\n",
"\n",
"Gegeben:\n",
"\n",
"<ul>\n",
" <li>$x_1, ..., x_n \\in \\mathbb{R}^d$</li>\n",
" <li>$y_1, ..., y_n \\in \\mathbb{R}$</li>\n",
"</ul>\n",
"\n",
"Gesucht: Funktion $f: \\mathbb{R}^d \\rightarrow \\mathbb{R}$, welche den quadratischen Fehler minimiert."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"<img src=\"imgs/lr1.png\" style=\"margin-left:auto;margin-right:auto;width:40%\">"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"<img src=\"imgs/lr2.png\" style=\"margin-left:auto;margin-right:auto;width:40%\">"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"<h4>Quadratischer Fehler (Sum of squares)</h4>\n",
"$$\n",
" \\mathcal{E} = \\underset{i = 1}{\\overset{n}{\\sum}} (y_i - f(x_i))^2\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"<h3>Quadratischer Fehler</h3>\n",
"\n",
"Warum nicht die Summe der Beträge minimieren?\n",
"\n",
"$$\n",
" \\mathcal{E} = \\underset{i = 1}{\\overset{n}{\\sum}} |y_i - f(x_i)|\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"<div style=\"display:flex\">\n",
" <div class=\"text-center\">\n",
" <img src=\"imgs/sq_vs_abs2.png\" width=\"100%\">\n",
" Betragsfehler: 8<br>\n",
" Quadratischer Fehler: 32\n",
" </div>\n",
" <div class=\"text-center\">\n",
" <img src=\"imgs/sq_vs_abs.png\" width=\"100%\">\n",
" Betragsfehler: 8<br>\n",
" Quadratischer Fehler: 16\n",
" </div>\n",
" <div class=\"text-center\">\n",
" <img src=\"imgs/sq_vs_abs3.png\" width=\"100%\">\n",
" Betragsfehler: 8<br>\n",
" Quadratischer Fehler: 32\n",
" </div>\n",
"</div>"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"<ul>\n",
" <li>Die Lösung ist eindeutig und einfach zu berechnen</li>\n",
" <li>Der Fehler wird möglichst gleichmäßig auf die Punkte verteilt</li>\n",
" <li>Der Betragsfehler wird auch minimiert</li>\n",
" <li>Nachteil: Ausreißer haben starken Effekt auf das Ergebnis</li>\n",
"</ul>"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Die Normalengleichung minimiert den quadratischen Fehler!"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"<h2>Lineare Regression mit Polynomen</h2>"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"<h4>Gegeben:</h4>\n",
"<ul>\n",
" <li><b>n</b> Punktpaare $(x_1, y_1), (x_2, y_2), ..., (x_n,y_n)$</li>\n",
"</ul>"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"<h4>Gesucht:</h4>\n",
"<ul>\n",
" <li>Polynom $f: \\mathbb{R} \\rightarrow \\mathbb{R}$ mit $f(x)= \\beta_0 + \\beta_1 x + ... + \\beta_d x^d$ vom Grad $d$</li>\n",
"</ul>"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Ansatz:\n",
"\n",
"$$\n",
" f(x_1) = y_1\\\\\n",
" f(x_2) = y_2\\\\\n",
" \\vdots\\\\\n",
" f(x_n) = y_n\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"$$\n",
" \\beta_0 + \\beta_1 x_1 + ... + \\beta_d x_1^d = y_1\\\\\n",
" \\beta_0 + \\beta_1 x_2 + ... + \\beta_d x_2^d = y_2\\\\\n",
" \\vdots\\\\\n",
" \\beta_0 + \\beta_1 x_n + ... + \\beta_d x_n^d = y_n\\\\\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Gesucht:\n",
"\n",
"$$\n",
" \\color{red}{\\beta_0} + \\color{red}{\\beta_1} x_1 + ... + \\color{red}{\\beta_d} x_1^d = y_1\\\\\n",
" \\color{red}{\\beta_0} + \\color{red}{\\beta_1} x_2 + ... + \\color{red}{\\beta_d} x_2^d = y_2\\\\\n",
" \\vdots\\\\\n",
" \\color{red}{\\beta_0} + \\color{red}{\\beta_1} x_n + ... + \\color{red}{\\beta_d} x_n^d = y_n\\\\\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Dieses LGS hat selten eine Lösung:\n",
"\n",
"$$\n",
" \\beta_0 + \\beta_1 x_1 + ... + \\beta_d x_1^d \\approx y_1\\\\\n",
" \\beta_0 + \\beta_1 x_2 + ... + \\beta_d x_2^d \\approx y_2\\\\\n",
" \\vdots\\\\\n",
" \\beta_0 + \\beta_1 x_n + ... + \\beta_d x_n^d \\approx y_n\\\\\n",
"$$\n",
"\n",
"Wir wollen auch keine exakte Lösung!"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"<div style=\"display:flex\">\n",
" <div style=\"width:100%\" class=\"text-center\">\n",
" <h3>Approximation</h3>\n",
" <img src=\"imgs/lr.png\" />\n",
" </div>\n",
" <div style=\"width:100%\" class=\"text-center\">\n",
" <h3>Interpolation</h3>\n",
" <img src=\"imgs/int.png\" />\n",
" </div>\n",
"</div>"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"LGS in Matrixform:\n",
" \n",
"$$\n",
" \\begin{bmatrix}\n",
" 1 & x_1 & ... & x_1^d\\\\\n",
" 1 & x_2 & ... & x_2^d\\\\\n",
" \\vdots & \\vdots & \\ddots & \\vdots\\\\\n",
" 1 & x_n & ... & x_n^d\\\\\n",
" \\end{bmatrix}\n",
" \\;\n",
" \\begin{bmatrix}\n",
" \\beta_0 \\\\ \\beta_1 \\\\ \\vdots \\\\ \\beta_d\n",
" \\end{bmatrix}\n",
" = \\begin{bmatrix}\n",
" y_1 \\\\ y_2 \\\\ \\vdots \\\\ y_n\n",
" \\end{bmatrix}\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"$$\n",
" X \\beta = Y\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Und dann: LGS näherungsweise mit Normalengleichung lösen"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"<h4>Beispiel</h4>\n",
"\n",
"Gegeben: Messpunkte $(x_i,y_i)$ mit den Werten (1,1), (2,2), (3,2), (4,3)<br>\n",
"\n",
"Gesucht: Gerade $f(x)$, die die Punkte approximiert"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Das heißt:\n",
"$$\n",
" f(x) = \\beta_0 + \\beta_1x\\\\\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"$$\n",
" X = \\begin{bmatrix} 1 & 1\\\\ 1 & 2\\\\ 1 & 3\\\\ 1 & 4\\end{bmatrix},\\;\\;\\;\\;\n",
" Y = \\begin{bmatrix} 1 \\\\ 2 \\\\ 2 \\\\ 3\\end{bmatrix}\\\\\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Lösungsvektor: \n",
" \n",
"$$\n",
" \\begin{bmatrix} \\beta_0 \\\\ \\beta_1 \\end{bmatrix}\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Normalengleichung:\n",
"\n",
"$$\n",
" \\begin{bmatrix} 1 & 1 & 1 & 1\\\\ 1 & 2 & 3 &4\\end{bmatrix} \\; \\begin{bmatrix} 1 & 1\\\\ 1 & 2\\\\ 1 & 3\\\\ 1 & 4\\end{bmatrix} \\cdot \\beta = \\begin{bmatrix} 1 & 1 & 1 & 1\\\\ 1 & 2 & 3 &4\\end{bmatrix} \\; \\begin{bmatrix} 1 \\\\ 2 \\\\ 2 \\\\ 3\\end{bmatrix}\\\\\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"$$\n",
"\\begin{bmatrix} 4 & 10\\\\ 10 & 30\\end{bmatrix} \\cdot \\beta = \\begin{bmatrix} 8 \\\\ 23 \\end{bmatrix}\\\\\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"$$\n",
"\\Longrightarrow \\beta = \\begin{bmatrix} 0.5\\\\ 0.6 \\end{bmatrix}\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"$$\n",
" f(x) = 0.6x + 0.5\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"<img src=\"imgs/lr_solution.png\" width=\"40%\" style=\"margin-left:auto;margin-right:auto\">"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"<h2>Ordinary Least Squares vs. Total Least Squares</h2>"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"<h3>Welcher Fehler wird minimiert?</h3>\n",
"\n",
"<div style=\"display:flex;margin-top:25px\">\n",
" <img src=\"imgs/ols.png\" width=\"50%\"/>\n",
" <img src=\"imgs/tls.png\" width=\"50%\"/>\n",
"</div>"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"<div class=\"text-center\">\n",
" <h1>Lösen der Normalengleichung</h1>\n",
"</div>"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"<h2>Definitheit von Matrizen</h2>\n",
"\n",
"Sei $A \\in \\mathbb{R}^{n \\times n}$ eine <b>symmetrische Matrix</b>. Wir nennen A\n",
"\n",
"$$\n",
"\\left.\n",
"\\begin{aligned}\n",
" &\\text{positiv definit}, & \\text{falls } x^\\mathsf{T}Ax > 0\\\\\n",
" &\\text{positiv semidefinit}, & \\text{falls } x^\\mathsf{T}Ax \\geq 0\\\\\n",
" &\\text{negativ definit}, & \\text{falls } x^\\mathsf{T}Ax < 0\\\\\n",
" &\\text{negativ semidefinit}, & \\text{falls } x^\\mathsf{T}Ax \\leq 0\\\\\n",
"\\end{aligned}\n",
"\\;\n",
"\\right\\} \\text { für alle } x \\in \\mathbb{R}^n \\setminus \\{0\\}.\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"$$\n",
" \\begin{bmatrix} x_1 & x_2 \\end{bmatrix}\n",
" \\begin{bmatrix}1 & 0\\\\ 0 & 3 \\end{bmatrix} \n",
" \\begin{bmatrix} x_1 \\\\ x_2 \\end{bmatrix} = x_1^2 + 3x_2^2\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"$$\n",
" \\begin{bmatrix}\n",
" 1 & 1 & 2\\\\\n",
" 1 & 3 & 4\\\\\n",
" 2 & 4 & 7\\\\\n",
" \\end{bmatrix}\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Sei $A \\in \\mathbb{R}^{n \\times n}$ eine <b>symmetrische</b> Matrix. A ist\n",
"\n",
"$$\n",
"\\begin{array}{l l}\n",
" \\text{positiv definit}, & \\text{falls alle Eigenwerte größer als 0 sind.} \\\\\n",
" \\text{positiv semidefinit}, &\\text{falls alle Eigenwerte größer gleich 0 sind.} \\\\\n",
" \\text{negativ definit}, &\\text{falls alle Eigenwerte kleiner als 0 sind.} \\\\\n",
" \\text{negativ semidefinit}, &\\text{falls alle Eigenwerte kleiner gleich 0 sind.}\\\\\n",
"\\end{array}\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"<h3>Hauptminorenkriterium</h3>\n",
"\n",
"\\begin{bmatrix}\n",
" 1 & 1 & 2\\\\\n",
" 1 & 3 & 4\\\\\n",
" 2 & 4 & 7\\\\\n",
" \\end{bmatrix}"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"$$\n",
" \\det 1 = 1\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"$$\n",
" \\det \\begin{bmatrix} 1 & 1 \\\\ 1 & 3 \\end{bmatrix} = 1 \\cdot 3 - 1 \\cdot 1 = 2\\\\\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"$$\n",
"\\det \\begin{bmatrix}\n",
" 1 & 1 & 2\\\\\n",
" 1 & 3 & 4\\\\\n",
" 2 & 4 & 7\\\\\n",
" \\end{bmatrix} = 1 \\cdot 3 \\cdot 7 + 1 \\cdot 4 \\cdot 2 + 2 \\cdot 1 \\cdot 4 - 2 \\cdot 3 \\cdot 2 - 4 \\cdot 4 \\cdot 1 - 7 \\cdot 1 \\cdot 1 = 2\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Falls alle Hauptminoren positiv, dann ist $A$ positiv definit.<br>\n",
"Falls alle Hauptminoren abwechselnd negativ und positiv sind, ist $A$ negativ definit."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "notes"
}
},
"source": [
"Für <b>symmetrische</b> Matrizen!"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"<h2>Cholesky-Zerlegung</h2>\n",
"\n",
"<h4>Definition (Cholesky-Zerlegung)</h4>\n",
"\n",
"Sei $A \\in \\mathbb{R}^{n \\times n}$ <b>symmetrisch</b> und <b>positiv definit</b>. Eine Cholesky-Zerlegung für $A$ ist eine Faktorisierung der Matrix in\n",
"\n",
"$$\n",
" A = L L^\\mathsf{T},\n",
"$$ \n",
"wobei $L$ eine untere Dreiecksmatrix ist."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"<h3>Cholesky-Zerlegung berechnen</h3>"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"$$\n",
" \\begin{bmatrix}\n",
" a_{1,1} & a_{1,2} & a_{1,3} & ...\\\\\n",
" a_{2,1} & a_{2,2} & a_{2,3} & ...\\\\\n",
" a_{3,1} & a_{3,2} & a_{3,3} & ...\\\\\n",
" \\vdots & \\vdots & \\vdots & \\ddots\\\\\n",
" \\end{bmatrix}\n",
" \\\n",
" = \n",
" \\\n",
" \\begin{bmatrix}\n",
" l_{1,1} & 0 & 0 & ...\\\\\n",
" l_{2,1} & l_{2,2} & 0 & ...\\\\\n",
" l_{3,1} & l_{3,2} & l_{3,3} & ...\\\\\n",
" \\vdots & \\vdots & \\vdots & \\ddots\\\\\n",
" \\end{bmatrix}\n",
" \\\n",
" \\begin{bmatrix}\n",
" l_{1,1} & l_{2,1} & l_{3,1} & ...\\\\\n",
" 0 & l_{2,2} & l_{3,2} & ...\\\\\n",
" 0 & 0 & l_{3,3} & ...\\\\\n",
" \\vdots & \\vdots & \\vdots & \\ddots\\\\\n",
" \\end{bmatrix}\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"$$\n",
" \\begin{bmatrix}\n",
" a_{1,1} & a_{1,2} & a_{1,3} & ...\\\\\n",
" a_{2,1} & a_{2,2} & a_{2,3} & ...\\\\\n",
" a_{3,1} & a_{3,2} & a_{3,3} & ...\\\\\n",
" \\vdots & \\vdots & \\vdots & \\ddots\\\\\n",
" \\end{bmatrix}\n",
" \\\n",
" = \n",
" \\\n",
" \\begin{bmatrix}\n",
" l_{1,1}^2 & l_{2,1} l_{1,1} & l_{3,1} l_{1,1} & ...\\\\\n",
" l_{2,1} l_{1,1} & l_{2,2}^2 + l_{2,1}^2 & l_{2,1} l_{3,1} + l_{2,2} l_{3,2} & ...\\\\\n",
" l_{3,1} l_{1,1} & l_{3,1} l_{2,1} + l_{3,2} l_{2,2} & l_{3,1}^2 + l_{3,2}^2 + l_{3,3}^2 & ...\\\\\n",
" \\vdots & \\vdots & \\vdots & \\ddots\\\\\n",
" \\end{bmatrix}\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Reihenfolge:\n",
" \n",
"$$\n",
"\\begin{bmatrix}\n",
" l_{1,1} \\color{blue}{(1)} & 0 & 0 & ...\\\\\n",
" l_{2,1} \\color{blue}{(2)} & l_{2,2} \\color{blue}{(3)} & 0 & ...\\\\\n",
" l_{3,1} \\color{blue}{(4)} & l_{3,2} \\color{blue}{(5)} & l_{3,3} \\color{blue}{(6)} & ...\\\\\n",
" \\vdots & \\vdots & \\vdots & \\ddots\\\\\n",
" \\end{bmatrix}\n",
"$$\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Formel:\n",
" \n",
"$$\n",
" l_{i,i} = \\sqrt{a_{i,i} - \\underset{k=1}{\\overset{i - 1}{\\sum}} l_{i,k}^2}\\\\\n",
" \\\\\n",
" l_{i,j} = \\frac{1}{l_{j,j}} \\left( a_{i,j} - \\underset{k=1}{\\overset{j - 1}{\\sum}} l_{i,k} l_{j,k} \\right)\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Beispiel:\n",
"\n",
"$$\n",
"A = \\begin{bmatrix}\n",
" 4 & 6 & 2\\\\\n",
" 6 & 10 & 5\\\\\n",
" 2 & 5 & 21\n",
"\\end{bmatrix}\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"$$\n",
"l_{1,1} = \\sqrt{\\color{red}4} = \\color{blue}2 \\\\\n",
"$$\n",
"\n",
"$$\n",
"A = \\begin{bmatrix}\n",
" \\color{red}4 & 6 & 2\\\\\n",
" 6 & 10 & 5\\\\\n",
" 2 & 5 & 21\n",
"\\end{bmatrix} \\quad\n",
"L = \\begin{bmatrix}\n",
" \\color{blue}{2} & 0 & 0\\\\\n",
" ? & ? & 0\\\\\n",
" ? & ? & ?\n",
"\\end{bmatrix}\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"$$\n",
" l_{2,1} = \\frac{1}{\\color{green}2} \\color{red}6 = \\color{blue}3\n",
"$$\n",
"\n",
"$$\n",
"A = \\begin{bmatrix}\n",
" 4 & 6 & 2\\\\\n",
" \\color{red}6 & 10 & 5\\\\\n",
" 2 & 5 & 21\n",
"\\end{bmatrix}\n",
"\\quad\n",
"L = \\begin{bmatrix}\n",
" \\color{green}2 & 0 & 0\\\\\n",
" \\color{blue}{3} & ? & 0\\\\\n",
" ? & ? & ?\n",
"\\end{bmatrix}\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"$$\n",
" l_{2,2} = \\sqrt{\\color{red}{10} - \\color{green}3^2} = \\color{blue}1\n",
"$$\n",
"\n",
"$$\n",
"A = \\begin{bmatrix}\n",
" 4 & 6 & 2\\\\\n",
" 6 & \\color{red}{10} & 5\\\\\n",
" 2 & 5 & 21\n",
"\\end{bmatrix}\n",
"\\quad\n",
"L = \\begin{bmatrix}\n",
" 2 & 0 & 0\\\\\n",
" \\color{green}3 & \\color{blue}{1} & 0\\\\\n",
" ? & ? & ?\n",
"\\end{bmatrix}\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"$$\n",
" l_{3,1} = \\frac{1}{\\color{green}2} \\color{red}2 = \\color{blue}1\n",
"$$\n",
"\n",
"$$\n",
"A = \\begin{bmatrix}\n",
" 4 & 6 & 2\\\\\n",
" 6 & 10 & 5\\\\\n",
" \\color{red}2 & 5 & 21\n",
"\\end{bmatrix}\n",
"\\quad\n",
"L = \\begin{bmatrix}\n",
" \\color{green}2 & 0 & 0\\\\\n",
" 3 & 1 & 0\\\\\n",
" \\color{blue}{1} & ? & ?\n",
"\\end{bmatrix}\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"$$\n",
" l_{3,2} = \\frac{1}{\\color{green}1} (\\color{red}5 - \\color{orange}1 \\cdot \\color{orange}3) = \\color{blue}2\n",
"$$\n",
"\n",
"$$\n",
"A = \\begin{bmatrix}\n",
" 4 & 6 & 2\\\\\n",
" 6 & 10 & 5\\\\\n",
" 2 & \\color{red}5 & 21\n",
"\\end{bmatrix}\n",
"L = \\begin{bmatrix}\n",
" 2 & 0 & 0\\\\\n",
" \\color{orange}3 & \\color{green}1 & 0\\\\\n",
" \\color{orange}1 & \\color{blue}{2} & ?\n",
"\\end{bmatrix}\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"$$\n",
" l_{3,3} = \\sqrt{\\color{red}{21} - \\color{green}1^2 - \\color{green}2^2} = \\color{blue}4\n",
"$$\n",
"\n",
"$$\n",
"A = \\begin{bmatrix}\n",
" 4 & 6 & 2\\\\\n",
" 6 & 10 & 5\\\\\n",
" 2 & 5 & \\color{red}{21}\n",
"\\end{bmatrix}\n",
"\\quad\n",
"L = \\begin{bmatrix}\n",
" 2 & 0 & 0\\\\\n",
" 3 & 1 & 0\\\\\n",
" \\color{green}1 & \\color{green}2 & \\color{blue}{4}\n",
"\\end{bmatrix}\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Mit numpy:\n",
"\n",
"<code>L = np.linalg.cholesky(A)</code>"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Laufzeit: $O(n^3)$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Asymptotisch! In der Praxis nur halber Aufwand im Vergleich zu Gauß."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Numerisch stabiler als Gauß!"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"<h2>LGS lösen mit Cholesky</h2>\n",
"\n",
"Wir haben $A \\in \\mathbb{R}^{n \\times n}$ mit Cholesky-Zerlegung $A = L L^\\mathsf{T}$.\n",
"\n",
"Wie kann man mithilfe von $L$ das LGS $A x = b$ lösen?"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"<ol>\n",
" <li>Löse das LGS $Ly = b$ für $y$ (Vorwärtseinsetzen)</li>\n",
" <li>Löse das LGS $L^\\mathsf{T} x = y$ für $x$ (Rückwärtseinsetzen)</li>\n",
"</ol>"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Schaffen wir es, dass $A^\\mathsf{T} A$ positiv definit wird?"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"<h2>Günstige Eigenschaften von $A^\\mathsf{T}A$</h2>\n",
"\n",
"Symmetrisch:\n",
"$$\n",
"(A^\\mathsf{T} A)^\\mathsf{T} = A^\\mathsf{T} A^{\\mathsf{T}^\\mathsf{T}} = A^\\mathsf{T} A\n",
"$$\n",
"\n",
"Positiv semidefinit:\n",
"$$\n",
"x^\\mathsf{T} A^\\mathsf{T} A x = (A x)^\\mathsf{T} (A x) = y^\\mathsf{T} y \\geq 0\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"Ja, durch viele Gleichungen!\n",
"\n",
"Ist $A$ überbestimmt und hat vollen Rang, so hat $A^\\mathsf{T}A$ vollen Rang!"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"source": [
"<h3>Computertomographie mit linearer Ausgleichsrechnung</h3>\n",
"\n",
"<ol>\n",
" <li>Stell das LGS $A x = b$ auf</li>\n",
" <li>Berechne $A^\\mathsf{T} A$ und $A^\\mathsf{T} b$</li>\n",
" <li>Berechne die Cholesky Zerlegung ($L$) für $A^\\mathsf{T} A$</li>\n",
" <li>Löse das LGS $L y = A^\\mathsf{T}b$ für $y$ durch Vorwärtseinsetzen</li>\n",
" <li>Löse das LGS $L^\\mathsf{T} x = y$ für $x$ durch Rückwärtseinsetzen</li>\n",
"</ol>"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.9.1"
}
},
"nbformat": 4,
"nbformat_minor": 4
}