diff options
Diffstat (limited to 'math')
| -rw-r--r-- | math/gauss.cpp | 38 | ||||
| -rw-r--r-- | math/math.tex | 3 |
2 files changed, 41 insertions, 0 deletions
diff --git a/math/gauss.cpp b/math/gauss.cpp new file mode 100644 index 0000000..5faaa90 --- /dev/null +++ b/math/gauss.cpp @@ -0,0 +1,38 @@ +// Laufzeit: O(n^3) +void swapLines(int n, int l1, int l2) { + for (int i = 0; i <= n; i++) swap(mat[l1][i], mat[l2][i]); +} + +void normalLine(int n, int line) { + double factor = mat[line][line]; + for (int i = 0; i <= n; i++) { + mat[line][i] /= factor; +}} + +void takeAll(int n, int line) { + for (int i = 0; i < n; i++) { + if (i == line) continue; + double diff = mat[i][line]; + for (int j = 0; j <= n; j++) { + mat[i][j] -= diff * mat[line][j]; +}}} + +int gauss(int n) { // Gibt zurück, ob das System (eindeutig) lösbar ist. + for (int i = 0; i < n; i++) { + int swappee = i; // Sucht Pivotzeile für bessere Stabilität. + for (int j = i + 1; j < n; j++) + if (abs(mat[j][i]) > abs(mat[i][i])) swappee = j; + swapLines(n, i, swappee); + if (abs(mat[i][i]) > EPSILON) { + normalLine(n, i); + takeAll(n, i); + }} // Ab jetzt nur noch checks bzgl. Eindeutigkeit/Existenz der Lösung. + for (int i = 0; i < n; i++) { + bool allZero = true; + for (int j = i; j < n; j++) + if (abs(mat[i][j]) > EPSILON) allZero = false; + if (allZero && abs(mat[i][n]) > EPSILON) return INCONSISTENT; + if (allZero && abs(mat[i][n]) < EPSILON) return MULTIPLE; + } + return UNIQUE; +} diff --git a/math/math.tex b/math/math.tex index 7d36c00..c06bd34 100644 --- a/math/math.tex +++ b/math/math.tex @@ -22,6 +22,9 @@ Sei $0 \leq x < n$. Definiere $d := \gcd(x, n)$.\newline \subsection{LGS über $\mathbb{F}_p$} \lstinputlisting{math/lgsFp.cpp} +\subsection{LGS über $\mathbb{R}$} +\lstinputlisting{math/gauss.cpp} + \subsection{Chinesischer Restsatz} \begin{itemize} \item Extrem anfällig gegen Overflows. Evtl. häufig 128-Bit Integer verwenden. |