vollständige Induktion < Lin. Gleich.-systeme < Numerik < Hochschule < Mathe < Vorhilfe
|
Hallo Zusammen,
Ich sitze hier gerade vor folgender Aufgabe:
| Aufgabe |
Betrachte eine Tridiagonalmatrix [m]A \in M\left( {n \times n,\mathbb{R}} \right)[/m] der Form
[mm]A = \operatorname{tridiag}\left(b_i,a_i,c_i\right) :=
\begin{pmatrix}
a_1&c_1&{}&{}&{}\\
b_2&\ddots&\ddots&{}&0\\
{}&\ddots&\ddots&\ddots&{}\\
{}&0&\ddots&\ddots&c_{n-1}\\
{}&{}&{}&b_n&a_n
\end{pmatrix}.[/mm]
Die Elemente der Matrix A erfüllen die Ungleichungen:
[mm]\begin{gathered}
\left( 1 \right)\quad \left| {a_1 } \right| > \left| {c_1 } \right| > 0, \hfill \\
\left( 2 \right)\quad \left| {a_i } \right| \geqslant \left| {b_i } \right| + \left| {c_i } \right|,\,b_i \ne 0,\,c_i \ne 0,\,2 \leqslant i \leqslant n - 1 \hfill \\
\left( 3 \right)\quad \left| {a_n } \right| \geqslant \left| {b_n } \right| > 0. \hfill \\
\end{gathered}.[/mm]
Zeige, es gilt:
[mm]\begin{gathered}
\left( {\text{i}} \right)\quad {\text{Die durch }}\alpha _1 : = a_1 ,\gamma _1 : = c_1 \alpha _1^{ - 1} {\text{ und durch }}\alpha _i : = a_i - b_i \gamma _{i - 1} {\text{ für}} \hfill \\
2 \leqslant i \leqslant n,\,\gamma _i : = c_i \alpha _i^{ - 1} {\text{ für }}2 \leqslant i \leqslant n - 1{\text{ definierten Zahlen genügen den}} \hfill \\
{\text{Ungleichungen:}} \hfill \\
\left| {\gamma _i } \right| < 1,\,1 \leqslant i \leqslant n - 1; \hfill \\
0 < \left| {a_i } \right| - \left| {b_i } \right| < \left| {\alpha _i } \right| < \left| {a_i } \right| + \left| {b_i } \right|,\,2 \leqslant i \leqslant n. \hfill \\
\end{gathered}[/mm]
Hinweis: Die Ungleichung [mm]\left| {\gamma _i } \right| < 1,\,1 \leqslant i \leqslant n - 1[/mm] kann durch vollständige Induktion gezeigt werden.
Benutze: [mm]\textstyle\left| {\gamma _m } \right| = \left| {\frac{{c_m }}
{{a_m - b_m \gamma _{m - 1} }}} \right| \leqslant \frac{{\left| {c_m } \right|}}
{{\left| {\left| {a_m } \right| - \left| {b_m } \right|\left| {\gamma _{m - 1} } \right|} \right|}}[/mm]
[mm]\begin{gathered}
\left( {{\text{ii}}} \right)\quad {\text{A besitzt die Dreieckszerlegung }}A = LR{\text{ mit }}L: = {\text{ tridiag}}\left( {b_i ,\alpha _i ,0} \right), \hfill \\
R: = {\text{ tridiag}}\left( {0,1,\gamma _i } \right). \hfill \\
{\text{Hinweis: Ausmultiplizieren}} \hfill \\
\end{gathered}[/mm]
(iii) A ist regulär. Was bedeutet dieser Begriff?
|
Jedenfalls habe ich schonmal mit der Aufgabe angefangen:
zu (i).1
Induktionsanfang (i = 2):
[m]\begin{gathered}
\left| {\gamma _2 } \right| = \left| {\frac{{c_2 }}
{{a_2 - b_2 \gamma _1 }}} \right| \leqslant \frac{{\left| {c_2 } \right|}}
{{\left| {\left| {a_2 } \right| - \left| {b_2 } \right|\left| {\gamma _1 } \right|} \right|}} = \frac{{\left| {c_2 } \right|}}
{{\left| {\left| {a_2 } \right| - \left| {b_2 } \right|\left| {c_1 \alpha _1^{ - 1} } \right|} \right|}} = \frac{{\left| {c_2 } \right|}}
{{\left| {\left| {a_2 } \right| - \left| {b_2 } \right|\left| {c_1 *\tfrac{1}
{{a_1 }}} \right|} \right|}} = \hfill \\
\frac{{\left| {c_2 } \right|}}
{{\left| {\tfrac{{\left| {a_2 } \right|\left| {a_1 } \right|}}
{{a_1 }} - \tfrac{{\left| {b_2 } \right|c_1 }}
{{a_1 }}} \right|}} = \frac{{\left| {a_1 } \right|\left| {c_2 } \right|}}
{{\left| {a_2 } \right|\left| {a_1 } \right| - \left| {b_2 } \right|c_1 }} \hfill \\
\end{gathered}[/m].
Wegen [m]
\left| {a_2 } \right| \geqslant \left| {b_2 } \right| + \left| {c_2 } \right| \Rightarrow \frac{{\left| {a_1 } \right|\left| {c_2 } \right|}}
{{\left| {a_2 } \right|\left| {a_1 } \right| - \left| {b_2 } \right|c_1 }} \geqslant \frac{{\left| {a_1 } \right|\left| {c_2 } \right|}}
{{\left( {\left| {b_2 } \right| + \left| {c_2 } \right|} \right)\left| {a_1 } \right| - \left| {b_2 } \right|c_1 }} > \frac{{\left| {c_1 } \right|\left| {c_2 } \right|}}
{{\left| {c_1 } \right|\left| {b_2 } \right| + \left| {c_1 } \right|\left| {c_2 } \right| - \left| {b_2 } \right|c_1 }} = 1[/m].
Ist mein Induktionsanfang richtig?
Jedenfalls versuche ich die Aufgabe jetzt weiter zu lösen. Mal sehen wie weit ich heute komme. Die Aufgabe ist ziemlich schwierig.
Viele Grüße
Karl
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 18:38 Sa 31.12.2005 | | Autor: | Karl_Pech |
Liebe Mitglieder!
Ich habe hier eine Aufgabenstellung vor mir, bei der ich mir nicht ganz sicher bin, ob sie nicht mit der Aufgabenstellung aus diesem Diskussionsstrang identisch ist:
| Aufgabe | | Das Gauss'sche Verfahren ist für Tridiagonalmatrizen ohne Pivotsuche durchführbar, wenn [mm]A[/mm] erfüllt [mm]\left|\alpha_1\right| > \left|\beta_1\right| > 0[/mm] und [mm]\left|\alpha_i\right| \leqslant \left|\beta_i\right| + \left|\gamma_{i-1}\right|[/mm] für [mm]i = 2,\dotsc,n-1[/mm]. Insbesondere ist [mm]A[/mm] diagonaldominant für [mm]k=1,\dotsc,n-1[/mm], d.h. [mm]\text{\fbox{$\left|\lambda_k\right| < 1$}}[/mm] und [mm]\text{\fbox{$\left|\mu_k\right| > \left|\alpha_k\right| - \left|\gamma_{k-1}\right| > 0$}}[/mm] für [mm]k=2,\dotsc,n[/mm]. |
Was denkt ihr? Und falls die Aufgabenstellungen nicht identisch sind, wäre mir ein Tipp schon sehr willkommen. 
Grüße
Karl
|
|
|
| |
|
Hallo Karl,
Die Bedeutung der vorkommenden Variablen ist (zumindest mir) unklar.
Aber genau gleich siehts irgendwie nicht aus 
viele Grüße
mathemaduenn
|
|
|
| |
|
Hallo Karl,
Bei deiner Ungleichungskette steht da.
[mm] |\gamma_2|\le [/mm] X>1 innerhalb sind auch kleine Fehler aber Du machst Dir's auch unnötig schwer wieso fängst Du nicht bei n=1 an.
Regulär bedeutet invertierbar.
Ja das wars erstmal stehn ja auch nicht mehr Fragen da
gruß
mathemaduenn
|
|
|
| |
|
Hallo mathemaduenn,
Nochmals danke für deine Antwort. Hier ist, was ich daraus gemacht habe:
Induktionsanfang (i = 1):
[m]\left| {\gamma _1 } \right| = \left| {c_1 \alpha _1^{ - 1} } \right| = \left| {c_1 \frac{1}
{{\alpha _1 }}} \right| = \left| {\frac{{c_1 }}
{{a_1 }}} \right|\mathop < \limits^{{\text{wegen (1)}}} 1[/m]
Induktionsannahme:
Die Aussage ist wahr!
[m]\begin{array}{*{20}c}
{{\text{Induktionsschritt }}\left( {i \to i + 1} \right):} \\
\hline
\end{array}[/m]
[m]\left| {\gamma _{i + 1} } \right| = \left| {c_{i + 1} \alpha _{i + 1}^{ - 1} } \right| = \left| {\frac{{c_{i + 1} }}
{{\underbrace {a_{i + 1} }_{ \geqslant \left| {b_{i + 1} } \right| + \left| {c_{i + 1} } \right|} - b_{i + 1} * \underbrace {\gamma _i }_{ < \,1,{\text{ wegen I}}{\text{. - Ann}}{\text{.}}}}}} \right| =\;?[/m]
Und was jetzt? Wär' Klasse, wenn Du mir einen Tip geben könntest.
Viele Grüße
Karl
|
|
|
| |
|
Hallo Karl,
Du hast:
[mm]|c_i|\le|a_i|-|b_i|[/mm]
Was muß denn erfüllt sein damit ein Bruch kleiner 1 ist?
Reicht das schon?
gruß
mathemaduenn
|
|
|
| |
|
Hallo mathemaduenn,
Sorry, für die späte Antwort, aber ich war die ganze Zeit damit beschäftigt noch eine andere Frage ins Forum zu stellen!
> Du hast:
> [mm]|c_i|\le|a_i|-|b_i|[/mm]
> Was muß denn erfüllt sein damit ein Bruch kleiner 1 ist?
> Reicht das schon?
Ich denke ja: [m]\frac{{\left| {c_{i + 1} } \right|}}
{{\left| {a_{i + 1} } \right| - \left| {b_{i + 1} } \right|\left| {\gamma _i } \right|}}\mathop \leqslant \limits^{\begin{gathered}
{\text{wegen }}\left( {\text{2}} \right),{\text{ denn}} \hfill \\
{\text{unser Z\"ahler wird}} \hfill \\
{\text{gr\"o{\ss}er und somit}} \hfill \\
{\text{der Bruch insgesamt}} \hfill \\
\end{gathered}} \frac{{\left| {a_{i + 1} } \right| - \left| {b_{i + 1} } \right|}}
{{\left| {a_{i + 1} } \right| - \left| {b_{i + 1} } \right|\left| {\gamma _i } \right|}}[/m]. Wegen [m]\left| {\gamma _i } \right|\mathop < \limits^{{\text{I}}{\text{.A}}{\text{.}}} 1 \Rightarrow \left| {b_{i + 1} } \right|\left| {\gamma _i } \right| < \left| {b_{i + 1} } \right|\;\left( \star \right)[/m]. Und damit: [m]\frac{{\left| {a_{i + 1} } \right| - \left| {b_{i + 1} } \right|}}
{{\left| {a_{i + 1} } \right| - \left| {b_{i + 1} } \right|\left| {\gamma _i } \right|}}\mathop < \limits^{\left| {a_{i + 1} } \right| - \left| {b_{i + 1} } \right|\mathop < \limits^{\left( \star \right)} \left| {a_{i + 1} } \right| - \left| {b_{i + 1} } \right|\left| {\gamma _i } \right|} 1[/m]. Daraus folgt die Behauptung. [mm] $\square$
[/mm]
Ist das richtig? Wenn ja, so versuche ich mal gleich die andere Ungleichung.
Grüße
Karl
|
|
|
| |
|
Hallo Karl,
Gibt's nichts zu ergänzen.
gruß
mathemaduenn
|
|
|
| |
|
Hi,
Irgendwie komme ich bei der 2ten Ungleichung nicht weiter. Hier ist das, was ich da bisher hingeschrieben habe:
Induktionsanfang (i = 1):
[m]\begin{gathered}
\left| {a_1 } \right| - \left| {b_1 } \right|\mathop \geqslant \limits^{\left( 2 \right)} \left| {c_1 } \right|\mathop > \limits^{\left( 1 \right)} 0 \hfill \\
\Rightarrow 0 < \left| {a_1 } \right| - \left| {b_1 } \right| \hfill \\
\left| {\alpha _1 } \right| = \left| {a_1 } \right|\mathop > \limits^{\left( 1 \right)} \left| {c_1 } \right|\mathop \geqslant \limits^{\left( 2 \right)} \left| {a_1 } \right| - \left| {b_1 } \right| \Rightarrow \left| {a_1 } \right| - \left| {b_1 } \right| < \left| {\alpha _1 } \right| \hfill \\
\Rightarrow ? \hfill \\
\end{gathered}[/m]
Ich weiß, das ist ziemlich wenig. Hoffe auf einen Tip.
Grüße
Karl
|
|
|
| |
|
Hallo Karl,
Du kannst ja das bereits Bewiesene ausnutzen. dann funktionierts auch ohne Induktion. als Tipp:
Dreiecksungleichung:
[mm]|a-b|\le |a|+|b|[/mm]
aber auch
[mm]|b+(a-b)|\le |b|+|a-b|\Rightarrow |a|-|b| \le |a-b|[/mm]
gruß
mathemaduenn
|
|
|
| |
|
Hallo mathemaduenn,
> Du kannst ja das bereits Bewiesene ausnutzen.
Ups, das sollte ich wohl tatsächlich tun. Wozu habe ich's sonst bewiesen.
[m]\begin{gathered}
\left| {\gamma _i } \right|: = \left| {c_i \alpha _i^{ - 1} } \right| = \frac{{\overbrace {\left| {c_i } \right|}^{\left| {a_i } \right| - \left| {b_i } \right|\mathop \geqslant \limits^{\left( 2 \right)} }}}
{{\left| {a_i } \right| - \left| {b_i } \right|\left| {\gamma _{i - 1} } \right|}} \geqslant \frac{{\left| {a_i } \right| - \left| {b_i } \right|}}
{{\left| {a_i } \right| - \left| {b_i } \right|\left| {\gamma _{i - 1} } \right|}} \Rightarrow \frac{{\left| {a_i } \right| - \left| {b_i } \right|}}
{{\left| {a_i } \right| - \left| {b_i } \right|\left| {\gamma _{i - 1} } \right|}} \leqslant \left| {\gamma _i } \right| < 1 \hfill \\
\Rightarrow \left| {a_i } \right| - \left| {b_i } \right| < \left| {a_i } \right| - \left| {b_i } \right|\left| {\gamma _{i - 1} } \right| = :\left| {\alpha _i } \right| \hfill \\
\end{gathered}[/m]
Ok, jetzt müßte ich nur noch [m]0 < \left| {a_i } \right| - \left| {b_i } \right|[/m] und [m]\left| {\alpha _i } \right| < \left| {a_i } \right| + \left| {b_i } \right|[/m] beweisen. Und vermutlich müßte ich gerade hier die Dreiecksungleichung benutzen, die Du mir angegeben hast, aber ich weiß noch nicht wie.
Vielen Dank!
Grüße
Karl
|
|
|
| |
|
Hallo Karl,
[mm]|a_i| \le |b_i|+|c_i|[/mm]
Da stand dan noch [mm] c_i [/mm] wäre nicht null also
[mm]|a_i|>|b_i|[/mm]
Das war schon die erste.
Jetzt Start fürs nächste.
[mm] |\alpha_i|=|a_i-\gamma_{i-1}*b_i|
[/mm]
Die Dreiecksungleichung verwenden
[mm]|a_i|-|\gamma_{i-1}||b_i| \le |a_i-\gamma_{i-1}*b_i| \le |a_i|+|\gamma_{i-1}||b_i|[/mm]
Da die [mm] gamma_i [/mm] kleiner 1 waren und [mm] b_i [/mm] ungleich null macht ein weglassen von [mm] \gamma_{i-1} [/mm] die linke Seite echt kleiner und die rechte Seite echt größer.
Dein Beweis ist leider falsch mit der Vergrößerung des Zählers vergrößert sich auch der Bruch.
Alles klar?
![[gutenacht]](/images/smileys/gutenacht.gif "[gutenacht]")
mathemaduenn
|
|
|
|
