Die Mathe-Redaktion - 17.01.2018 18:59 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
ListenpunktSchwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktZur Award-Abstimmung
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden oder den Newsletter bestellen.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 830 Gäste und 31 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Numerik & Optimierung » Anzahl der Operationen des Gauß-Verfahrens
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Anzahl der Operationen des Gauß-Verfahrens
mathletic
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 11.11.2013
Mitteilungen: 1299
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2018-01-11 12:40

\(\begingroup\)
Hallo,

sei A eine reguläre (<math>n\times n</math>)-Matrix, für die das Gaußsche Eliminationsverfahren möglich ist.
Ich will zeigen dass zur Lösung von Ax = b erfordert das Gaußsche Eliminationsverfahren <math>\frac{n^3}{3}+O(n^2)</math> Operationen.


Ich habe folgendes gemacht, aber eine andere Anzahl der Operationen gefunden:

Die Schritte des Gaußsche Eliminationsverfahrens sind die folgende:
Schritt 1:
Wir definieren die erweiterte <math>n\times (n+1)</math>-Koeffizientenmatrix:
<math>A_\text{er}=(A\mid b)=\begin{pmatrix}
\left.\begin{matrix}
a_{11} & a_{12}  & \ldots & a_{1n} \\
a_{21} & a_{22}  & \ldots & a_{2n} \\
\vdots & \vdots  & \ddots & \vdots \\
a_{n1} & a_{n2}  & \ldots & a_{nn} \\
\end{matrix}\right| \begin{matrix}
b_1 \\ b_2 \\ \vdots \\ b_n
\end{matrix}
\end{pmatrix}</math>

Schritt 2:
Beginnend mit den erste Element der Hauptdiagonalen als Pivot, also das <math>a_{11}</math>, führen wir eine Operation durch zwischen der ersten Zeile und jede der folgenden Zeilen, sodass alle Einträge unter den Pivot gleich Null werden.    

Nach diesen Schritt hat die erweiterte Koeffizientenmatrix folgende Form:
<math>A_\text{er}(1)=\begin{pmatrix}
\left.\begin{matrix}
a_{11} & a_{12}  & \ldots & a_{1n} \\
0 & a_{22}^{(2)}  & \ldots & a_{2n}^{(2)} \\
\vdots & \vdots  & \ddots & \vdots \\
0 & a_{n2}^{(2)}  & \ldots & a_{nn}^{(2)} \\
\end{matrix}\right| \begin{matrix}
b_1 \\ b_2^{(2)} \\ \vdots \\ b_n^{(2)}
\end{matrix}
\end{pmatrix}</math>

Diese Matrix entsteht mit der Operation <math>(i=2, \ldots , n)</math>:
<math>\left (i\text{-te Zeile von } A_\text{er}(1)\right )=-\frac{a_{i1}}{a_{11}}\left (1\text{-te Zeile von } A_\text{er}\right )+\left (i\text{-te Zeile von } A_\text{er}\right )</math>

Schritt 3:
Wir setzen den Prozess fort, beginnend mit den zweiten Element der Hauptdiagonalen der Matrix <math>A_\text{er}(1)</math> als Pivot, also das <math>a_{22}^2</math>, führen wir eine Operation durch zwischen der zweiten Zeile und jede der folgenden Zeilen, sodass alle Einträge unter den Pivot gleich Null werden.    

Nach diesen Schritt hat die erweiterte Koeffizientenmatrix folgende Form:
<math>A_\text{er}(2)=\begin{pmatrix}
\left.\begin{matrix}
a_{11} & a_{12}  & a_{13} & \ldots & a_{1n} \\
0 & a_{22}^{(2)}  & a_{23}^{(2)} & \ldots & a_{2n}^{(2)} \\
0 & 0  & a_{33}^{(3)} & \ldots & a_{3n}^{(3)} \\
\vdots & \vdots  & \vdots & \ddots & \vdots \\
0 & 0 &  a_{n3}^{(3)}  & \ldots & a_{nn}^{(3)} \\
\end{matrix}\right| \begin{matrix}
b_1 \\ b_2^{(2)} \\ b_3^{(3)} \\ \vdots \\ b_n^{(3)}
\end{matrix}
\end{pmatrix}</math>

Diese Matrix entsteht mit der Operation <math>(i=3, \ldots , n)</math>:
<math>\left (i\text{-te Zeile von } A_\text{er}(2)\right )=-\frac{a_{i2}^{(2)}}{a_{22}^{(2)}}\left (2\text{-te Zeile von } A_\text{er}(1)\right )+\left (i\text{-te Zeile von } A_\text{er}(1)\right )</math>  

Wenn wir im gleichen Sinnen weitermachen, bekommen wir nach n Schritten die erweiterte Koeffizientenmatrix in Zeilenstufenform:
<math>A_\text{er}(n)=\begin{pmatrix}
\left.\begin{matrix}
a_{11} & a_{12}  & a_{13} & \ldots & a_{1n} \\
0 & a_{22}^{(2)}  & a_{23}^{(2)} & \ldots & a_{2n}^{(2)} \\
0 & 0  & a_{33}^{(3)} & \ldots & a_{3n}^{(3)} \\
\vdots & \vdots  & \vdots & \ddots & \vdots \\
0 & 0 &  0  & \ldots & a_{nn}^{(n)} \\
\end{matrix}\right| \begin{matrix}
b_1 \\ b_2^{(2)} \\ b_3^{(3)} \\ \vdots \\ b_n^{(n)}
\end{matrix}
\end{pmatrix}</math>
mit der wir die Lösung mit der Rückwärtssubstitutionen berechnen können.

Also von der Gleichung <math>a_{nn}^{(n)}x_n=b_n^{(n)}</math> berechnen wir das $x_n$, usw.  


Im Schritt 2 des Verfahrens um die Elemente <math>a_{ij}^{(2)}, \ i,j=2, \ldots , n</math> zu berechnen sind folgende Operationen erfordert:
- die Division <math>-\frac{a_{i1}}{a_{11}}</math> : <math>1</math> Operation
- das Produkt von jeden der <math>n-1</math> Elemente der ersten Zeile mit den Faktor <math>-\frac{a_{i1}}{a_{11}}</math> : <math>n-1</math> Operationen  
- die Summe von den jeweilgen <math>n-1</math> Elementen der ersten beiden Zeilen : <math>n-1</math> Operationen

 
Also für eine Zeile sind es dann <math>1+(n-1)+(n-1)</math> Operationen. Das machen wir für alle <math>n-1</math> Zeilen. Also insgesamt sind es dann <math>\left (n-1\right )\cdot \left [1+(n-1)+(n-1)\right ]=\left (n-1\right )\cdot \left [1+2(n-1)\right ]=(n-1)+2(n-1)^2</math>.

Um die Elemente <math>a_{ij}^{(i)}</math> zu berechnen, brauchen wir dann
<math>\displaystyle{\sum_{i=2}^n\left [(n-i)+2(n-i)^2\right ]=\sum_{i=2}^n(n-i)+2\sum_{i=2}^n(n-i)^2} \\ \displaystyle{=\frac{n^2-3n+2}{2}+\frac{2n^3-9n^2+13n-6}{3}}\\  \displaystyle{=\frac{3n^2-9n+6+4n^3-18n^2+26n-12}{6}}\\  \displaystyle{=\frac{4n^3-15n^2+15n-6}{6}}\\  \displaystyle{=\frac{2}{3}n^3-\frac{5}{2}n^2+\frac{5}{2}n-1}</math>  

Ausserdem sind
<math>\displaystyle{(n-1)+(n-2)+\ldots +1=\frac{n(n-1)}{2}}</math>
Operationen erforderlich um die <math>b_i^{(i)}</math>, <math>i=2, \ldots , n</math> zu berechnen.

Bei der Rückwärtssubstitutionen sind
<math>\displaystyle{1+2+\ldots +n=\frac{n(n+1)}{2}}</math>
erforderlich.


Insgesamt erfordert also das Gaußsche Eliminationsverfahren <math>\displaystyle{\frac{2}{3}n^3-\frac{5}{2}n^2+\frac{5}{2}n-1+\frac{n(n-1)}{2}+\frac{n(n+1)}{2}  =\frac{2}{3}n^3-\frac{3}{2}n^2+\frac{5}{2}n-1}</math>
Operationen.


Was mache ich falsch?
\(\endgroup\)


Wahlurne Für mathletic bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
Buri
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 02.08.2003
Mitteilungen: 45110
Aus: Dresden
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2018-01-11 20:34

\(\begingroup\)
Hi mathletic,
es ist alles richtig so.
Du hast Additionen, Multiplikationen und Divisionen gezählt.
Es ist üblich, als Maßeinheit der Rechenkomplexität eine Berechnung der Form a := b + c * d, die aus einer Addition und einer Multiplikation besteht, zu nehmen. Wenn man das tut, dann kommt wirklich \(\frac{n^3}3\) heraus, und wenn man Additionen und Multiplikationen als jeweils eine Operation zählt, sind es \(\frac{2n^3}3\) Operationen.
Leider findet man im Netz als Definition der Maßeinheit Flop lediglich die simple Erklärung "Gleitkommaoperationen (Additionen oder Multiplikationen) pro Sekunde".
Den meisten Mathematikern im Fachgebiet Numerische Mathematik ist jedoch klar, dass man unter Flop üblicherweise den Aufwand für eine Addition und Multiplikation nimmt, vielleicht kann einer der Numerik-Experten einen Link finden, wo das so erklärt wird. Ich habe das schon irgendwo gelesen, auch und gerade in der Zeit vor dem Internet, aber wo das war, weiß ich nicht mehr.
Gruß Buri
\(\endgroup\)


Wahlurne Für Buri bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
mathletic
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 11.11.2013
Mitteilungen: 1299
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2018-01-11 21:57


Ich verstehe! Vielen Dank für die Antwort!!

Ich habe noch eine Frage:
Wenn man als rechte Seite <math>b</math> nacheinander die Einheitsvektoren <math>e^{(1)}=(1, 0, \ldots , 0)^T, \ldots , e^{(n)}=(0, \ldots , 0, 1)^T</math> wählt, man mit den zugehörigen Lösungen <math>x^{(1)},\ldots ,x^{(n)}</math> die Inverse <math>A^{-1}=[x^{(1)}, \ldots , x^{(n)}]</math> erhält. Ich will zeigen dass die Inverse sich mit <math>n^3 +O(n^2)</math> Operationen berechnen lässt.

Berechnen wir hier das gleiche nur anders die Berechnung von den <math>b_i^{(i)}</math> ?  



Wahlurne Für mathletic bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 5100
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2018-01-12 10:35


Ich habe es so gelernt:
FLOPs = floating point operations = Additionen, Subtraktionen, Multiplikationen, Divisionen
Dabei sind Divisionen am aufwändigsten, gefolgt von Multiplikationen. Additionen und Subtraktionen kommen dahinter (der Aufwand einer "normalen" Multiplikation ist quadratisch in der Stellenzahl, bei einer Addition wächst der Aufwand nur linear). Daher zählen viele nur die Multiplikationen/Divisionen (zumindest so lange, wie die Zahl der Additionen in der gleichen Größenordnung liegt).

Die Definition von Buri für FLOPs greift diese Idee auf, man bekommt die Additionen quasi kostenlos dazu, so lange sie die Zahl der Multiplikationen nicht überschreiten.

Es gibt also verschiedene Konzepte, welche Operationen man wie zählt, die alle ihre Vor- und Nachteile haben. Man muss halt im Zweifelsfall wissen, was denn nun genau gezählt wurde.



Zur Frage:
Will man die Gleichung Ax=b für viele rechte Seiten lösen, so bietet sich ein etwas anderes Verfahren an, das sich LR- (oder LU-)Zerlegung nennt.
Die notwendigen Umformungsschritte, um A auf Diagonalform zu bringen werden in einer weiteren Matrix "gespeichert", so dass man für verschiedene rechte Seiten diese Schritte nicht immer wieder neu berechnen muss.

Siehe hier.



Wahlurne Für Kitaktus bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
mathletic
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 11.11.2013
Mitteilungen: 1299
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2018-01-12 11:35


2018-01-12 10:35 - Kitaktus in Beitrag No. 3 schreibt:
Ich habe es so gelernt:
FLOPs = floating point operations = Additionen, Subtraktionen, Multiplikationen, Divisionen
Dabei sind Divisionen am aufwändigsten, gefolgt von Multiplikationen. Additionen und Subtraktionen kommen dahinter (der Aufwand einer "normalen" Multiplikation ist quadratisch in der Stellenzahl, bei einer Addition wächst der Aufwand nur linear). Daher zählen viele nur die Multiplikationen/Divisionen (zumindest so lange, wie die Zahl der Additionen in der gleichen Größenordnung liegt).

Die Definition von Buri für FLOPs greift diese Idee auf, man bekommt die Additionen quasi kostenlos dazu, so lange sie die Zahl der Multiplikationen nicht überschreiten.

Es gibt also verschiedene Konzepte, welche Operationen man wie zählt, die alle ihre Vor- und Nachteile haben. Man muss halt im Zweifelsfall wissen, was denn nun genau gezählt wurde.


Ich verstehe!!



2018-01-12 10:35 - Kitaktus in Beitrag No. 3 schreibt:
Zur Frage:
Will man die Gleichung Ax=b für viele rechte Seiten lösen, so bietet sich ein etwas anderes Verfahren an, das sich LR- (oder LU-)Zerlegung nennt.
Die notwendigen Umformungsschritte, um A auf Diagonalform zu bringen werden in einer weiteren Matrix "gespeichert", so dass man für verschiedene rechte Seiten diese Schritte nicht immer wieder neu berechnen muss.

Also um die Matrix R zu bekommen formen wir die Matrix in Zeilenstufenform, dazu brauchen wir <math>\sum_{i=1}^n\left [\left (n-i\right )\cdot \left (1+(n-i)\right )\right ]=\frac{n^3}{3}+2n^2+\frac{n}{3}</math> (wie wir beim Gauss-Verfahren gesehen haben, wenn wir als Operation die Multiplikation und die Division betrachten).

Die Einträge des Matrix L sind die Faktoren, mit dene multipliziert wurde, um in der Matrix R an der jeweiligen Stelle die 0 zu erzeugen. Allerdings mit umgekehrtem Vorzeichen. Diese haben wir also bereits berechnet, also für die Matrix L sind weitere Operationen nicht erforderlich, oder?

Mit dieser Zerlegung kann die Lösung Ax = b auf zwei einfachere Probleme aufgeteilt werden. Zuerst löst man das System für eine Hilfsvariable z: Lz = b und dann löst man Rx = z.

Das erste Gleichungssystem kann durch einfache Vorwärtssubstitution gelöst werden, das zweite durch Rückwärtssubstitution.

Bei der Vorwärtssubstitution und bei der Rückwärtssubstitution sind jeweils <math>1+2+\ldots +n=\frac{n(n+1)}{2}</math> Operationen erforderlich.

Da wir n verschiedene b-Vektoren haben, wenden wir die Vorwärts- und  Rückwärtssubstitution n-mal an.

Insegesamt brauchen wir also <math>\left (\frac{n^3}{3}+2n^2+\frac{n}{3}\right )+n\cdot 2\cdot \frac{n(n+1)}{2}=\frac{n^3}{3}+2n^2+\frac{n}{3}+n^3+n^2=\frac{4n^3}{3}+3n^2+\frac{n}{3}</math>.


Wo liegt mein Fehler? Der Koeffizient von <math>n^3</math> müsste 1 sein statt <math>\frac{4}{3}</math>  confused



Wahlurne Für mathletic bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 5100
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2018-01-12 16:23


Schau Dir mal diesen Faden an.
Hier werden sowohl Algorithmen mit Aufwand 4/3n3+... als auch solche mit n3+... thematisiert.



Wahlurne Für Kitaktus bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
mathletic
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 11.11.2013
Mitteilungen: 1299
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2018-01-13 02:02


Ich habe noch nicht verstanden wir man das <math>n^3</math> bekommt. Macht man hier vielleicht etwas anders bei der Berechnung von den Matrizen L,R als bei dem Gauss-Verfahren?



Wahlurne Für mathletic bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
Buri
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 02.08.2003
Mitteilungen: 45110
Aus: Dresden
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2018-01-13 10:54


Hi mathletic,
ja. Beim Gauss-Verfahren werden Dreiecksmatrizen berechnet.
Beim Austauschverfahren dagegen wird mit voll besetzten n x n-Matrizen gearbeitet.
Gruß Buri



Wahlurne Für Buri bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
mathletic
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 11.11.2013
Mitteilungen: 1299
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2018-01-13 16:17


2018-01-13 10:54 - Buri in Beitrag No. 7 schreibt:
Nur beim Gauss-Verfahren werden Dreiecksmatrizen berechnet.
Beim Gauss-Jordan-Verfahren und beim Austauschverfahren dagegen wird mit voll besetzten n x n-Matrizen gearbeitet.

Bei der LR-Zerlegung formen wir doch die Matrix in Zeilenstufenform und dann ist diese die Matrix R und die Matrix L entsteht aus Einsen in der Hauptdiagonale und darunter sind die Faktoren mit dene multipliziert wurde, um in der Matrix R an der jeweiligen Stelle die 0 zu erzeugen, allerdings mit umgekehrtem Vorzeichen.

Die L und R sind doch Dreiecksmatrizen. Oder habe ich etwas falsch verstanden?


Muss man hier vielleicht ein anderes Verfahren betrachten statt die LR-Zerlegung?



Wahlurne Für mathletic bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
Buri
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 02.08.2003
Mitteilungen: 45110
Aus: Dresden
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2018-01-13 16:22


2018-01-13 16:17 - mathletic in Beitrag No. 8 schreibt:
1. Die L und R sind doch Dreiecksmatrizen.
2. Muss man hier vielleicht ein anderes Verfahren betrachten statt die LR-Zerlegung?
1. ja.
2. ja, das Austauschverfahren zur Inversenberechnung.
Gruß Buri



Wahlurne Für Buri bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
mathletic hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2017 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]