TU Wien:AKNUM Computernumerik VO (Schranz-Kirlinger)/Verfahrenzusammenfassung SS2015

Numerische Lösung linear Gleichungssysteme

Gaußelimination

Die Grunidee der Gaußelimination ist ein allgemeines lineares Gleichungssystem vom Typ

$A{\vec {x}}={\vec {b}}\quad {\mbox{wobei }}A\in \mathbb {R} ^{n\times n}{\mbox{ und }}{\vec {b}},{\vec {x}}\in \mathbb {R} ^{n}$

in ein sogenanntes gestaffeltes System zu bringen um danach mittels Rückeinsetzung eine Lösung zu erhalten.

Ausgangspunkt ist das volle System:

${\begin{aligned}a_{11}x_{1}+a_{12}x_{2}+\cdots +a_{1n}x_{n}=&b_{1}\\a_{21}x_{2}+a_{22}x_{2}+\cdots +a_{2n}x_{n}=&b_{2}\\\vdots &\\a_{n1}x_{1}+a_{n2}x_{2}+\cdots +a_{nn}x_{n}=&b_{n}\end{aligned}}$

Um dieses System in das gestaffelte System zu bringen muss man die erste Gleichung mit ${\frac {a_{21}}{a_{11}}}$ multiplizieren und anschließend von der zweiten Gleichung subtrahieren. Dadurch fällt die erste Zeile der zweiten Gleichung weg:

$\left(a_{21}-{\frac {a_{21}}{a_{11}}}a_{11}\right)x_{1}=0$

Dann erhält man ein $(n-1)\times (n-1)$-Teilsystem auf das man den selben Schritt anwendet. Wiederholt man das $n-1$ mal, erhält man:

${\begin{aligned}a_{11}x_{1}+a_{12}x_{2}+a_{13}x_{3}+\cdots +a_{1n}x_{n}=&b_{1}\\a'_{22}x_{2}+a'_{23}x_{3}+\cdots +a_{2n}'x_{n}=&b'_{2}\\a'_{33}x_{3}+\cdots +a_{3n}'x_{n}=&b'_{3}\\\vdots &\\a_{nn}^{''}x_{n}=&b_{n}\end{aligned}}$

Dieses System ist dann äquivalent zum ursprünglichen System. Jetzt kann man die Lösung durch Rückeinsetzung berechen.

$x_{n}={\frac {b_{n}}{a_{nn}}},\quad x{n_{1}}={\frac {b_{n-1}-a_{n-1,n}{\frac {b_{n}}{a_{nn}}}}{a_{n-1,n-1}}},\quad \cdots$

Dies ist im allgemeinen schlecht Konditioniert durch Spaltenpivotsuche mit Zeilentausch kann man die Kondition bezüglich zu Rundungsfehler stark verbessern. Dabei tauscht man vor der Elimination die Zeile mit dem betragsgrößten Element aus der $i$-ten Spalte in die $j$-te Zeile

Lineares Ausgleichproblem

Wenn man weiß dass eine Funktion $f(x)$ eine bestimmte Gestalt hat. (z.B.: Polynom vom Grad 2 also $f(x)=c_{o}+c_{1}x+c_{2}x^{2}$ ) die Parameter/Koeffizienten jedoch unbekannt sind, können diese mit einem linearen Gleichungssystem berechnet werden.

${\begin{aligned}c_{0}+c_{1}x_{0}+c_{2}x_{0}^{2}=&f(x_{0})\\c_{0}+c_{1}x_{1}+c_{2}x_{1}^{2}=&f(x_{1})\\c_{0}+c_{1}x_{2}+c_{2}x_{2}^{2}=&f(x_{2})\end{aligned}}$

d.h. ein lineares Gleichungssystem der Form:

${\begin{pmatrix}1&x_{0}&x_{0}^{2}\\1&x_{1}&x_{1}^{2}\\1&x_{2}&x_{2}^{2}\\\end{pmatrix}}\cdot {\begin{pmatrix}c_{0}\\c_{1}\\c_{2}\\\end{pmatrix}}={\begin{pmatrix}f(x_{0})\\f(x_{1})\\f(x_{2})\\\end{pmatrix}}$

Meistens hat man aber mehr Messungen der zugrundeliegender Funktion also einen Datensatz : $((x_{0},f(x_{0})),(x_{1},f(x_{1})),\cdots ,(x_{m},f(x_{m})))$ und man möchte $f(x)$ optimal an diese Daten anpassen also den Abstand der Fehlerquadrate minimal werden lassen:

$E(c_{0},c_{1},c_{2}):=\sum _{i=0}^{m}(c_{0}+c_{1}x_{i}+c_{2}x_{i}^{2}-{\tilde {f}}(x_{i}))^{2}$

Das ist der Fall wenn die partiellen Ableitungen 0 werden. Aus den 3 Ableitungen kann man dann ein lineares Gleichungssystem aufstellen. Welches man auch so anschreiben kann:

$A={\begin{pmatrix}1&x_{0}&x_{0}^{2}\\1&x_{1}&x_{1}^{2}\\1&x_{2}&x_{2}^{2}\\&\vdots &\\1&x_{m}&x_{m}^{2}\\\end{pmatrix}}$

$A^{T}A\cdot {\begin{pmatrix}c_{0}\\c_{1}\\c_{2}\\\end{pmatrix}}=A^{T}{\begin{pmatrix}{\tilde {f}}(x_{0})\\{\tilde {f}}(x_{1})\\{\tilde {f}}(x_{2})\\\vdots \\{\tilde {f}}(x_{m})\\\end{pmatrix}}$

Nichtlineare Gleichungssysteme

Iterationsverfahren

Idee eines Iterationsverfahrens für das Auffinden von Lösungen mit dem Startwert ${\vec {x}}_{0}\in D$

${\vec {T}}({\vec {x}}_{0})=:{\vec {x}}_{i}{\vec {T}}({\vec {x}}_{1})=:\cdots =:{\vec {x}}_{k-1}{\vec {T}}({\vec {x}}_{k-1})=:{\vec {x}}_{k}$

Verfahren

• Bisektion: Ein sehr einfaches Verfahren zur Nullstellensuche, welches auf Halbierung eines Intervalls beruht. Konvergiert linear, der Fehler halbiert sich etwa in jedem Iterationsschritt.
• Regula Falsi, Sekantenverfahren: Einfache iterative Verfahren zur Nullstellenbestimmung eindimensionaler Funktionen.
• Fixpunktverfahren: Eine Klasse linear konvergenter Verfahren zum Auffinden von Fixpunkten von Funktionen, auch im Mehrdimensionalen.
• Newton-Verfahren: Ein quadratisch konvergentes Verfahren zum Auffinden von Nullstellen differenzierbarer Funktionen. Auch im Mehrdimensionalen anwendbar, dann ist in jedem Iterationsschritt ein lineares Gleichungssystem zu lösen.

Interpolation und Approximation

Dabei stellt man aus den Daten eine Koeffizientenmatrix, die sogenannte Vandermondematrix auf:

${\begin{pmatrix}1&x_{0}&x_{0}^{2}&\cdots &x_{0}^{n}\\1&x_{1}&x_{1}^{2}&\cdots &x_{1}^{n}\\1&x_{2}&x_{2}^{2}&\cdots &x_{2}^{n}\\&\vdots &&\ddots &\\1&x_{n}&x_{n}^{2}&\cdots &x_{n}^{n}\\\end{pmatrix}}$

Das Lagrange-Interpolationspolynom kann durch Lösen dieser Matrix erhalten werden. Dies ist jedoch im allgemeinen sehr aufwendig. Also werden andere Basen als die Einheitsbasen $e_{i}$ verwendet. Basen für den Raum der Polynome vom Grad $n$ sind z.B. die Lagrange-Polynome oder die Newton Polynome. Bei Hermiteinterpolation können auch hohe Ableitungswerte vorgegeben sein die das Interpolationspolynom anpassen.