Lineare Algebra : Gaußsches Eleminationsverfahren

Quellen

Wikipedia : Gaußsches Eliminationsverfahren

Übersicht

Für ein lineares Gleichungssystem mit $N, N \in \mathbb{N_2}$ Unbekannten $\vec x = (x_1, .., x_N)$
und $N \times (1 + N)$ bekannten Koeffizienten $a_{ij}$ wird der eben der Lösungsvektor $\vec x$ gesucht.

Gegeben

$N$ : Dimension des Lösungsvektors, $N \in \mathbb{N_2}$
$a_{ij}$ : $N \times (1 + N)$ bekannte Koeffizienten, $a_{ij} \in \mathbb{R}, i \in [1 .. N], j \in [1 .. (1+N)] $

Gesucht

$\vec x = (x_1, .., x_N)$ : Lösungsvektor

Herleitung

Das vorgestellte Problem schreibt sich unter diesen Vorgaben als ein
lineares Gleichungssystem LES:

$ \begin{pmatrix} a_{11} & a_{12} & .. & a_{1N} \\ a_{21} & a_{22} & .. & a_{2N} \\ .. & .. & .. & .. \\ a_{N1} & a_{N2} & .. & a_{NN} \\ \end{pmatrix} \cdot \begin{pmatrix} x_{1} \\ x_{2} \\ .. \\ x_{N} \\ \end{pmatrix}= \begin{pmatrix} a_{1(1+N)} \\ a_{2(1+N)} \\ .. \\ a_{N(1+N)} \\ \end{pmatrix}$    (LES)

Durch zeilenweise Multiplikation / Subtraktion der $a_{ij}$ von $a_{kj}$ :

$a_{ij} = a_{ij} - \dfrac{a_{kj} a_{ik}}{a_{kk}}$    (vgl. Listing unten)

und Hauptdiagonalen-Normierung der Matrix ergibt sich ein Gleichungssystem (SES),
aus dem der Lösungsvektor $\vec x = (s_1, s_2, .., s_N)$ direkt abgelesen werden kann:

$ \begin{pmatrix} 1 & 0 & .. & 0 \\ 0 & 1 & .. & 0 \\ .. & .. & .. & .. \\ 0 & 0 & .. & 1 \\ \end{pmatrix} \cdot \begin{pmatrix} x_{1} \\ x_{2} \\ .. \\ x_{N} \\ \end{pmatrix}= \begin{pmatrix} s_1 \\ s_2 \\ .. \\ s_N \\ \end{pmatrix}$    (SES)

Python-Programm: Gauss-Elemination

Im Folgenden findet sich der Python-Code für die Gauss-Elemination: 

 #
 #--------------------------------------------------------------------
 #   Include
 #--------------------------------------------------------------------
 import math as M
 #
 #--------------------------------------------------------------------
 #   Helper
 #--------------------------------------------------------------------
 def Error(text):
     print('Error: ' + text + '!')
     return
 #
 def PrintMatrix(title, name, m):
     if (None == m):
         Error('Zero Matrix')
         return
     NR = len(m)
     NC = len(m[0])
     print('{0}({1})[{2}|{3}]:'.format(title, name, NR, NC))
     for IR in range(0, NR):
         for IC in range(0, NC):
             print('%+7.2f' % (m[IR][IC]), end='')
         print('')
     return
 #
 def PrintSolution(title, name, m):
     if (None == m):
         Error('Zero Matrix')
         return
     NR = len(m)
     NC = len(m[0])
     if (NR != NC - 1):
         Error('Invalid Matrix-Dimension')
         return
     print('{0}[{1}|{2}]:'.format(title, NR, NC))
     for IR in range(0, NR):
         print('%s[%d]=%+6.2f' % (name, IR, m[IR][NC - 1]))
     return
 #
 #--------------------------------------------------------------------
 #   Solver
 #--------------------------------------------------------------------
 def SolverNormalizeMatrix(m):
     if (None == m):
         Error('Zero Matrix')
         return []
     NR = len(m)
     NC = len(m[0])
     for IR in range(0, NR):
         D = m[IR][IR]
         if (0 == D):
             Error('Division by zero')
             return []
         for IC in range(0, NC):
             m[IR][IC] = m[IR][IC] / D
     return m
 #
 def SolverLowerElemination(m):
     NR = len(m)
     NC = len(m[0])
     for IT in range(0, NR):
         for IR in range(1 + IT, NR):
             F = m[IR][IT] / m[IT][IT]
             for IC in range(0, NC):
                 m[IR][IC] = m[IR][IC] - F * m[IT][IC]             
     return m
 #
 def SolverGaussElemination(m):
     NR = len(m)
     NC = len(m[0])
     for IT in range(0, NR):
         for IR in range(0, IT):
             F = m[IR][IT] / m[IT][IT]
             for IC in range(0, NC):
                 m[IR][IC] = m[IR][IC] - F * m[IT][IC]
         for IR in range(1 + IT, NR):
             F = m[IR][IT] / m[IT][IT]
             for IC in range(0, NC):
                 m[IR][IC] = m[IR][IC] - F * m[IT][IC]
     return m
 #
 #--------------------------------------------------------------------
 #   Main
 #--------------------------------------------------------------------
 if ('__main__' == __name__):
     print('*** GaussElemination: begin')   
     #
     M = [[-1,  1,  1,  0],
          [ 1, -3, -2,  5],
          [ 5,  1,  4,  3]]
     PrintMatrix('Matrix', 'Source', M)
     M = SolverGaussElemination(M)
     PrintMatrix('Matrix', 'GaussEleminated', M)
     M = SolverNormalizeMatrix(M)
     PrintMatrix('Matrix', 'Normalized', M)
     PrintSolution('GaussSolution', 'X', M)
     #
     print('*** GaussElemination: end')

Download des Python-Programms: 2206211055_GaussElemination_01V01.zip

Ausgabe des Python-Programms "Gauss-Elemination": 

*** GaussElemination: begin
Matrix(Source)[3|4]:
  -1.00  +1.00  +1.00  +0.00
  +1.00  -3.00  -2.00  +5.00
  +5.00  +1.00  +4.00  +3.00
Matrix(GaussEleminated)[3|4]:
  -1.00  +0.00  +0.00  +1.00
  +0.00  -2.00  +0.00  +8.00
  +0.00  +0.00  +6.00 +18.00
Matrix(Normalized)[3|4]:
  +1.00  -0.00  -0.00  -1.00
  -0.00  +1.00  -0.00  -4.00
  +0.00  +0.00  +1.00  +3.00
GaussSolution[3|4]:
X[0]= -1.00
X[1]= -4.00
X[2]= +3.00
*** GaussElemination: end

WebSites    Module    Mathematik