16.10.2026 - Woche 5

Mit linearen Gleichungssystemen begonnen. Als Erstes die Definition sowie die Standardform eines solchen Systems.

Definition 3.1

Ein lineares Gleichungssystem mit $m$ Gleichungen und $n$ Variablen $x_1,x_2\dots x_n$ von der Form

$$\begin{gathered} a_{11}{x}_1+a_{12}{x}_2+\dots +a_{1n}{x}_n=b_1 \\ {a}_{21}{x}_1+a_{22}{x}_2+\dots +a_{2n}{x}_n=b_2 \\ ⋮⋮ \\ {a}_{m1}{x}_1+a_{m2}{x}_2+\dots +a_{mn}{x}_n=b_m \end{gathered}$$

Wobei die Einträge $a_{ij},b_i$ bekannte reelle Zahlen sind und die $x_j$ als Platzhalter für die unbekannten reelle Zahlen stehen, welche berechnet werden müssen. Kann auch folgendermassen in Vektor Matrix Form geschrieben werden:

$$\underset{A\in {\mathbb{R}}^{mxn}}{\underbrace{\left[\begin{array}{cccc}{a}_{11}& a_{12}& \dots & a_{1n}\\ a_{21}& a_{22}& \dots & a_{2n}\\ a_{m1}& a_{m2}& \dots & a_{mn}\end{array}\right]}}\cdot \underset{x\in {\mathbb{R}}^n}{\underbrace{\left(\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_n\end{array}\right)}}=\underset{b\in {\mathbb{R}}^n}{\underbrace{\left(\begin{array}{c}{b}_1\\ b_2\\ ⋮\\ b_n\end{array}\right)}}$$

$A$: Koeffizientenmatrix
$x$ : Variablenvektor
$b$ : rechte Seite

Link to original

Lösen des Systems:

Finde $x\in {\mathbb{R}}^m$ mit $Ax=b$ oder berichte, dass es keinen Vektor gibt, welcher diese Gleichung erfüllt.

Bei $A$ in Zeilennotation:

$$\left[\begin{array}{ccc}-& {\mathbf{u}}_1^{\top }& -\\ -& {\mathbf{u}}_2^{\top }& -\\ & ⋮& \\ -& {\mathbf{u}}_m^{\top }& -\end{array}\right]$$

müssen alle Gleichungen $u_i^{\top }x=b$ für $i=1\dots m$ erfüllt werden

Bei $A$ in Spaltennotation:

$$A=\left[\begin{array}{cccc}|& |& & |\\ {\mathbf{v}}_1& {\mathbf{v}}_2& \cdots & {\mathbf{v}}_n\\ |& |& & |\end{array}\right]$$

muss der Vektor $b$ als Linearkombination von $v_1,v_2,\dots v_n$ geschrieben werden:

$$b=\sum _{j=1}^n{x}_j\cdot v_j$$

Page-Rank-Algorithmus

Der Page-Rank Algorithmus arbeitet auf Link-Graphen(Gerichteter Graph).
Als Beispiel für einen solchen Link-Graphen dient das Internet. Anhand des Beispiels Internet wird der Algorithmus auch im kurzen aufgezeigt.

Beispiel Page-Rank Algorithmus und das Internet

Für das Beispiel wird der oben gezeigte Link-Graph betrachtet. Jeder Knoten ist eine Seite und jede Kante eine Verlinkung von einer Seite auf eine andere.

Es stellt sich nun die Frage, welche Seite die relevanteste ist und z.B. in der Suche als Erstes angezeigt wird.

Traditionelles Mass:

Das traditionelle Mass für die Relevanz einer Seite ist identisch zur Variante, mit welcher man die Relevanz eines wissenschaftlichen Papers gemessen hat. Man zählt die Anzahl der Zitate (also die Links) auf eine Seite. Die Seite, die so die Meisten Zitate bzw. Links erhält wird als die relevanteste angesehen. Nach traditionellem Mass ist also Seite 2 die relevanteste, da es die Seite ist, auf welche die meisten Links zeigen.

So kann allerdings die Relevanz einer einzelnen Seite selbst manipuliert werden, indem gezielt neue Seiten erstellt werden, welche auf die gewünschte Seite verlinken. Während dieses künstliche Erstellen von Seiten bei wissenschaftlichen Papern noch einigermassen schwer und unpraktisch war, konnten im Internet sehr einfach viele Seiten erstellt werden und auf eine einzige Seite verlinken, um die Relevanz dieser Seite in die Höhe zu treiben.

Page-Rank Algorithmus:

In ihrem Paper “The anatomy of a large-scale hypertextual Web search engine” von 1998 widmen sich Sergey Brin und Lawrance Page diesem Problem und stellen eine Suchmaschine (Google) vor, welche einen anderen Page-Rank Algorithmus verwendet.

Ihr Algorithmus basiert auf den folgenden Prinzipen:

• Zitate von relevanten Seiten zählen mehr
• Zitate von Seiten, welche viele andere Seiten zitieren zählen weniger

Die Relevanz einer einzigen Seite ist:

$$\frac{\text{Summe der Relvanzen der zitierenden Seiten}}{\text{Anzahl der zitierten Seiten}}$$

Beispiel mit dem obigen Link-Graph

Die Relevanz der Seite zwei ist:
$x_2=\frac{x_1}{2}+x_4+x_5\frac{x_6}{4}$
Diese Gleichung kann man nun noch für die anderen 5 Seiten aufstellen.
So erhält man dann ein lineares Gleichungssystem mit 6 Gleichungen und 6 unbekannten.

Das Problem ist aber noch nicht vollständig gelöst, denn $0$ löst immer jedes dieser Gleichungssysteme. Dann hat aber jede Seite einfach eine Relevanz von $0$, was auch nicht hilfreich ist. Es muss also noch ein Faktor in die Gleichungssysteme eingebaut werden, damit $0$ nicht für alle $x$ eine Lösung sein kann.

Dafür wurde der sogenannte Dämpfungsfaktor $d$ eingeführt. Damit der Dämpfungsfaktor das eigentliche Resultat nicht verfälscht sondern nur dafür sorgt, dass $0$ nicht für alle $x$ eine Lösung ist soll dieser möglichst nahe an 1 liegen. Es bietet sich z.B. $d=\frac{7}{8}$ an. Es gibt natürlich noch viele Werte, welche näher an 1 liegen als $\frac{7}{8}$ aber es gilt auch abzuwägen, wie gross der Rechenaufwand wird. So hat sich $\frac{7}{8}$ als geeigneter Wert herausgestellt. Mit Dämfungsfaktor sieht die Berechnung der Relevanz für eine Seite dann folgendermassen aus:
$x_2=(1-d)+d(\frac{x_1}{2}+x_4+x_5\frac{x_6}{4})$
Das Gleichungssystem kann nun für den obigen Link-Graphen gelöst werden. Daraus ergeben sich dann die folgenden Werte:

Die Seite mit der grössten Relevanz ist hier also Seite 3. Seite 2 hat zwar viele andere Seiten, welche auf die Seite verweisen, leidet aber darunter, dass es einen Link von Seite 6 zu Seite 2 gibt, da von der Seite 6 so viele Links auf andere Seiten gehen und somit Seite 6 eine nicht so relevante Seite ist. Seite 3 hingegen hat zwar nur wenige Links, diese Links sind dafür aber von relevanten Seiten.

Link to original

Invertieren einer Matrix

Eine $m\times m$ Matrix $A$ ist genau dann invertierbar, wenn es eine $m\times m$ Matrix $B$ gibt, sodass $AB=I$ (Definition 2.56)

$$B=\left[\begin{array}{cccc}|& |& & |\\ {\mathbf{x}}_1& {\mathbf{x}}_2& \cdots & {\mathbf{x}}_m\\ |& |& & |\end{array}\right]:\underset{AB}{\underbrace{\left[\begin{array}{cccc}|& |& & |\\ \mathbf{A}{\mathbf{x}}_1& \mathbf{A}{\mathbf{x}}_2& \cdots & \mathbf{A}{\mathbf{x}}_{\mathbf{m}}\\ |& |& & |\end{array}\right]}}=\underset{I}{\underbrace{\left[\begin{array}{cccc}|& |& & |\\ {\mathbf{e}}_1& {\mathbf{e}}_2& \cdots & {\mathbf{e}}_{\mathbf{j}}\\ |& |& & |\end{array}\right]}}$$

Um den Vektor $x_j$ zu finden kann die Gleichung $A{x}_j=e_j$ gelöst werden.
Um die gesamte Matrix $B$ zu finden müssen $m$ lineare Gleichungssysteme gelöst werden.

Das Lösen dieser Gleichungssysteme kann z.B. mittels der Gauss-Elimination durchgeführt werden.

Gauss-Elimination

Die Gauss-Elimination ist ein Algorithmus zum Lösen von $Ax=b$ mit quadratischen Matrizen $A\in {\mathbb{R}}^{m\times m}$

1. In einem ersten Schritt wird das Gleichungssystem $Ax=b$ in ein System $Ux=c$ umgewandelt. Dieses neue Gleichungssystem hat die gleichen Lösungen wie das alte, hat aber ein “hübsches” $U$ in Form einer oberen Dreiecksmatrix.
2. Das Gleichungssystem $Ux=c$ kann leicht durch Rückwärtseinsetzen gelöst werden

$$\underset{U}{\underbrace{\left[\begin{array}{ccc}2& 3& 4\\ 0& 5& 6\\ 0& 0& 7\end{array}\right]}}\cdot \underset{x}{\underbrace{\left(\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right)}}=\underset{c}{\underbrace{\left(\begin{array}{c}19\\ 17\\ 14\end{array}\right)}}$$

Die obige Matrix-Vektor Gleichung kann auch als das folgende Gleichungssystem geschrieben werden:

$$\begin{array}{rlrlrlrl}1.& 2x_1& +& 3x_2& +& 4x_3& =& 19\\ 2.& & & 5x_2& +& 6x_3& =& 17\\ 3.& & & & & 7x_3& =& 14\end{array}$$

Das dritte Gleichungssystem besteht noch aus einer unbekannten und lässt sich daher einfach mit dem Ergebnis $x_3=2$ lösen. Dieses Ergebnis kann dann in die zweite Gleichung eingesetzt werden.

$$\begin{array}{rlrlrlrl}1.& 2x_1& +& 3x_2& +& 8& =& 19\\ 2.& & & 5x_2& +& 12& =& 17\end{array}$$

Nun gibt es auch im zweiten Gleichungssystem noch eine unbekannte und auch dieses Gleichungssystem kann gelöst werden: $x_2=1$. Wenn dieser Wert nun noch in die erste Gleichung eingesetzt wird, kommt man auf die folgende Gleichung:

$$\begin{array}{rlrlrl}1.& 2x_1& +& 11& =& 19\end{array}$$

Löst man diese Gleichung auf erhält man $x_1=4$. Somit hat man das Gleichungssystem gelöst und die folgenden Lösungen erhalten:
$x_1=4x_2=1x_3=2$
Im Fall einer $m\times m$ Gleichung $i=m,m-1,\dots 1$ :
${\sum }_{j=i}^m{u}_{ij}\cdot x_j=c_i$
oder

$$x_i=\frac{c_i-{\sum }_{j=i+1}^m{u}_{ij}\cdot x_j}{u_{ii}}$$

Hier wird sich zunutze gemacht, dass die bisherigen $x_m$, $x_{m-1}$ bis hin zu $x_{i+1}$ schon bekannt sind und verwendet werden können, um das aktuell gesuchte $x_i$ zu berechnen.
Wichtig ist hier noch, dass $u_{ii}\ne 0$ sein muss, da ansonsten eine Division mit $0$ stattfinden würde. Diese Einsicht ist gleichbedeutend mit der Aussage, dass es in der Diagonalen der Matrix keinen Eintrag mit Wert $0$ geben darf.

Elimination

Wenn $A$ keine obere Dreiecksmatrix kann das obige Verfahren noch nicht angewendet werden. $A$ muss also zuerst in die Form einer oberen Dreiecksmatrix gebracht werden. Somit wird also die Transformation von $Ax=b\to Ux=c$ durchgeführt.

$$\underset{A}{\underbrace{\left[\begin{array}{ccc}2& 3& 4\\ 4& 11& 14\\ 2& 8& 17\end{array}\right]}}\cdot \underset{x}{\underbrace{\left(\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right)}}=\underset{b}{\underbrace{\left(\begin{array}{c}19\\ 55\\ 50\end{array}\right)}}$$

Als erstes soll die $4$ eliminiert werden. Um das zu erreichen muss die erste Gleichung zwei Mal von der zweiten abgezogen werden.

\begin{array}{r@{\quad}rcrcrcr} (\text{Gleichung 2}): & 4x_1 &+& 11x_2 &+& 14x_3 &=& 55\\ -2(\text{Gleichung 1}): & 4x_1 &+& 6x_2 &+& 8x_3 &=& 38\\ \hline & & & 5x_2 &+& 6x_3 &=& 17 \end{array}

Dies wird nun als die Gleichung $A^{\prime }x=b^{\prime }$ geschrieben. Als Matrix-Vektor Gleichung sieht das folgendermassen aus:

$$\left[\begin{array}{ccc}2& 3& 4\\ 0& 5& 6\\ 2& 8& 17\end{array}\right]\cdot \left(\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right)=\left(\begin{array}{c}19\\ 17\\ 50\end{array}\right)$$

Das Verfahren, welches angewendet wurde, um die $4$ zu entfernen nennt sich Zeilensubtraktion. Eine Zeilensubtraktion ist eigentlich nichts anderes, als eine Matrixtransformation, welche auf alle Spalten von $A$ sowie auf den Vektor $b$ angewandt wird:

$$T_{E_{21}}\left(\left(\begin{array}{c}{v}_1\\ v_2\\ v_3\end{array}\right)\right)=\left(\begin{array}{c}{v}_1\\ v_2-2v_1\\ v_3\end{array}\right)=\underset{E_{21}}{\underbrace{\left[\begin{array}{ccc}1& 0& 0\\ -2& 1& 0\\ 0& 0& 1\end{array}\right]}}\left(\begin{array}{c}{v}_1\\ v_2\\ v_3\end{array}\right)$$

Wobei $E_{21}$ die Eliminationsmatrix ist, welche dafür sorgt, dass die $4$ verschwindet.
Jetzt gilt es noch zu zeigen, dass durch diese Umformungen die Lösungen auch erhalten bleiben.
Dazu lohnt es sich anzusehen, wie die Gleichung $A^{\prime }x=b^{\prime }$ definiert ist:

$A^{\prime }x=b^{\prime }:$ $A^{\prime }=E_{21}A$, $b^{\prime }=E_{21}b$
Wobei $E_{21}$ heisst: Ziehe Gleichung 1 zwei Mal von Gleichung 2 ab.

Da es sich hier um die Multiplikation mit einer Matrix handelt kann die Operation auch umgekehrt werden:
$A=E_{21}^{-1}{A}^{\prime }$ , $b=E_{21}^{-1}{b}^{\prime }$

Wobei $E_{21}^{-1}$ durch die Matrix $E_{21}^{-1}=\left[\begin{array}{ccc}1& 0& 0\\ 2& 1& 0\\ 0& 0& 1\end{array}\right]$
dargestellt wird. Man kann $E_{21}^{-1}$ also als addiere Gleichung 1 zwei Mal zu Gleichung 2 interpretieren.

Aber wieso haben $Ax=b$ und $A^{\prime }x=b^{\prime }$ jetzt die gleichen Lösungen?

• Wenn $Ax=b$ gilt, dann gilt auch: $A^{\prime }x=E_{21}Ax=E_{21}b=b^{\prime }$
• Wenn $A^{\prime }x=b^{\prime }$ gilt, dann gilt auch $Ax=E_{21}^{-1}{A}^{\prime }x=E_{21}^{-1}{b}^{\prime }=b$
  Daraus folgt nun also, dass $Ax=b$ und $A^{\prime }x=b^{\prime }$ die gleichen Lösungen haben.

Um das System in eine schöne obere Dreiecksmatrix zu verwandeln muss man nun also alle Zahlen, welche in der obigen Matrix rot markiert sind eliminieren.
Dabei geht man so vor, dass man zuerst die erste Gleichung verwendet, um in jeder Zeile die Zahl der ersten Spalte zu entfernen, dann geht man weiter und verwendet die zweite Gleichung, um von der dritten Zeile an jede Zahl in der zweiten Spalte zu eliminieren. Diesen Prozess führt man solange durch, bis man den Zustand der oberen Dreiecksmatrix hergestellt hat.

Da die Schritte der Elimination $E_{21}$, $E_{31}$ und $E_{32}$ eigentlich nur Matrixmultiplikationen sind, welche nach und nach auf $A$ angewendet werden können, kann der gesamte Eliminationsprozess auch als eine einzige Eliminationsmatrix geschrieben werden, welcher dann das Produkt der einzelnen Eliminationsmatrizen ist:

$$E_{32}{E}_{31}{E}_{21}=E_{gesamt}$$ $$E_{gesamt}A=U$$

Somit kommt man dann auf das schöne $U$ von weiter oben, welches verwendet wird, um ganz einfach auf die Resultate des linearen Gleichungssystems zu kommen.

Link to original