LR-Zerlegung, Crout < Lin. Gleich.-systeme < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:38 Di 30.03.2010 | | Autor: | moerni |
Hallo. Folgendes steht bei mir im Skript:
"Existenz der Zerlegung: Ist A regulär, dann kann man durch vorherige Zeilenvertauschungen bei A stets erreichen, dass eine LR-Zerlegung existiert."
Meine Frage: Wie kann ich der Matrix A ansehen, ob Zeilenvertauschungen nötig sind? Meine Überlegungen: da [mm] a_{1k}=r_{1k} [/mm] muss folgen, dass [mm] a_{11} \neq [/mm] 0 ist, da bei der R-Matrix [mm] r_{1k} \neq [/mm] 0 ist. Weiter ist [mm] r_{ii} \neq [/mm] 0, also 0 [mm] \neq a_{ii} [/mm] - [mm] l_{i1}r_{1i} [/mm] - ... - [mm] l_{i,i-1}r_{i-1,i}, [/mm] also [mm] a_{ii} \neq \sum_{j=1}^{i-1} l_{ij}r_{ji}. [/mm] Bringt das was? Also: welche Bedingungen an A müssen gelten, damit LR-Zerlegung ohne Zeilenvertauschungen existiert?
Eine Aufgabe war folgende: "Bestimmen Sie die Anzahl der Punkt- und Strichoperationen (jeweils getrennt) der LR-Zerlegung (Verfahren von Crout) bei einer Matrix der Größe n x n (ohne Berücksichtigung von Zeilenvertauschungen)."
Die Lösung ist: [mm] \frac{1}{3} n^3 [/mm] - [mm] \frac{1}{3}n [/mm] Punktoperationen und [mm] \frac{1}{3} n^3 [/mm] - [mm] \frac{1}{2} n^2 [/mm] + [mm] \frac{1}{6} [/mm] n Strichoperationen. Dieses Ergebnis kann ich leider nicht nachvollziehen. Ich habe angefangen, eine Liste zu erstellen:
1.Restzeile: 0 punkt, 0 strich, 1. Restspalte: 1 punkt, 0 strich; 2. Restzeile: 1 punkt, 1 strich, 2.Restspalte 2 punkt, 1 strich; 3. Restzeile 2 punkt, 2 strich, 3.Restspalte 3 punkt, 2 strich usw. daraus leite ich her (mit Gauß-Summenformel): Anzahl Punktoperationen: [mm] \frac{n(n+1)}{2} [/mm] + [mm] \frac{(n-1)n}{2} [/mm] = [mm] n^2 [/mm] und Anzahl Strichoperationen: [mm] \frac{2n(n-1)}{2} [/mm] = [mm] n^2-n.
[/mm]
Vergesse ich da etwas? Was mache ich falsch?
Über eine Antwort wäre ich sehr dankbar.
moerni
|
|
| |
|
Hallo!
> Hallo. Folgendes steht bei mir im Skript:
>
> "Existenz der Zerlegung: Ist A regulär, dann kann man
> durch vorherige Zeilenvertauschungen bei A stets erreichen,
> dass eine LR-Zerlegung existiert."
>
> Meine Frage: Wie kann ich der Matrix A ansehen, ob
> Zeilenvertauschungen nötig sind? Meine Überlegungen: da
> [mm]a_{1k}=r_{1k}[/mm] muss folgen, dass [mm]a_{11} \neq[/mm] 0 ist, da bei
> der R-Matrix [mm]r_{1k} \neq[/mm] 0 ist. Weiter ist [mm]r_{ii} \neq[/mm] 0,
> also 0 [mm]\neq a_{ii}[/mm] - [mm]l_{i1}r_{1i}[/mm] - ... -
> [mm]l_{i,i-1}r_{i-1,i},[/mm] also [mm]a_{ii} \neq \sum_{j=1}^{i-1} l_{ij}r_{ji}.[/mm]
> Bringt das was? Also: welche Bedingungen an A müssen
> gelten, damit LR-Zerlegung ohne Zeilenvertauschungen
> existiert?
Zunächst ist eher wichtig, dass du dir merkst: Jede reguläre Matrix hat eine LR-Zerlegung, wobei eventuell Zeilen vertauscht werden müssen.
Man muss einer Matrix nicht "ansehen", ob Zeilenvertauschungen nötig sind. Hilfreiche Sätze findest du aber ![[]](/images/popup.gif) hier, und vielleicht hier.
> Eine Aufgabe war folgende: "Bestimmen Sie die Anzahl der
> Punkt- und Strichoperationen (jeweils getrennt) der
> LR-Zerlegung (Verfahren von Crout) bei einer Matrix der
> Größe n x n (ohne Berücksichtigung von
> Zeilenvertauschungen)."
> Die Lösung ist: [mm]\frac{1}{3} n^3[/mm] - [mm]\frac{1}{3}n[/mm]
> Punktoperationen und [mm]\frac{1}{3} n^3[/mm] - [mm]\frac{1}{2} n^2[/mm] +
> [mm]\frac{1}{6}[/mm] n Strichoperationen. Dieses Ergebnis kann ich
> leider nicht nachvollziehen. Ich habe angefangen, eine
> Liste zu erstellen:
> 1.Restzeile: 0 punkt, 0 strich, 1. Restspalte: 1 punkt, 0
> strich; 2. Restzeile: 1 punkt, 1 strich, 2.Restspalte 2
> punkt, 1 strich; 3. Restzeile 2 punkt, 2 strich,
> 3.Restspalte 3 punkt, 2 strich usw. daraus leite ich her
> (mit Gauß-Summenformel): Anzahl Punktoperationen:
> [mm]\frac{n(n+1)}{2}[/mm] + [mm]\frac{(n-1)n}{2}[/mm] = [mm]n^2[/mm] und Anzahl
> Strichoperationen: [mm]\frac{2n(n-1)}{2}[/mm] = [mm]n^2-n.[/mm]
> Vergesse ich da etwas? Was mache ich falsch?
Du vergisst auf jeden Fall etwas, sonst kämst du auch auf kubischen Aufwand.
Um dir genauer helfen zu können, wäre es gut, wenn du einen Link postest, bei dem das von dir verwendete Verfahren genauso auftaucht, damit wir deine Liste besser nachvollziehen können. Eventuell ist es genau das, was sich oben im zweiten Link findet?
Grüße,
Stefan
|
|
|
| |
|
Hallo Moerni,
Bei deinen Überlegungen zum Aufwand scheint die Berechnung der "Restmatrix" zu fehlen. Als Anregung kann vllt. dieser Artikel dienen. Neben den in Stefans Links angegebenen Methoden zur Bestimmung, ob eine LR Zerlegung ohne Zeilenvertauschungen möglich ist, wollte ich noch anmerken, dass die LR-Zerlegung durchzuführen selbst die rechenaufwandsmäßig beste Methode dafür ist.
viele Grüße
mathemaduenn
|
|
|
|
