Hauptseite: Unterschied zwischen den Versionen

Aus MWiki
Wechseln zu: Navigation, Suche
(EW-Verfahren)
K (EW-Verfahren)
Zeile 6: Zeile 6:
  
 
=== Beweis und Algorithmus ===
 
=== Beweis und Algorithmus ===
Seien <math>R_1 := (r_{1jk}) = (r_{1kj}) = R_1^T \in {}^{\nu}\mathbb{C}^{n \times n}, n \in {}^{\nu}2\mathbb{N}^*, r_{11k} := 1</math> und für <math>j &gt; 1</math> sowie <math>n_{jk} := j + k - 3</math> sowohl <math>r_{1jk} := \hat{n}e^{i\tau n_{jk}/n}</math> mit  <math>n_{jk} &lt; n</math> als auch <math>r_{1jk} := \hat{n}e^{i\tau(n_{jk} - \acute{n})/n}</math> mit <math>n_{jk} \ge n</math>. Durch Vertauschung der ersten Zeile bzw. Spalte mit der <math>j</math>-ten und entsprechender Vertauschung der übrigen Zeilen und Spalten entstehen die Matrizen <math>R_j = R_j^T</math> mit <math>j &gt; 1</math>. Sei <math>\delta_{jk}</math> das Kronecker-Delta.
+
Seien <math>R_1 := (r_{1jk}) = (r_{1kj}) = R_1^T \in {}^{\nu}\mathbb{C}^{n \times n}, n \in {}^{\nu}2\mathbb{N}^*, r_{11k} := 1</math> und für <math>j &gt; 1</math> sowie <math>n_{jk} := j + k - 3</math> sowohl <math>r_{1jk} := \hat{n}e^{i\tau n_{jk}/n}</math> mit  <math>n_{jk} &lt; n</math> als auch <math>r_{1jk} := \hat{n}e^{i\tau(n_{jk} - \acute{n})/n}</math> mit <math>n_{jk} \ge n</math>. Durch Vertauschung der ersten Zeile bzw. Spalte mit der <math>j</math>-ten und entsprechender Vertauschung der übrigen Zeilen und Spalten entstehen die Matrizen <math>R_j = R_j^T</math> mit <math>j &gt; 1</math>. Sei <math>\delta_{jk}</math> das Kronecker-Delta und <math>A := (a_{jk})</math>.
  
Folgt <math>a_{jk} \le 0</math> für mindestens ein Paar <math>(j, k)</math> aus <math>A := (a_{jk})</math>, so werden die Summe <math>s_0 := \sum\limits_{j=1}^m{b_j\varepsilon^j}</math> mit einer beliebigen transzendenten Zahl <math>\varepsilon</math> und <math>s_k := \sum\limits_{j=1}^m{a_{jk}\varepsilon^j} \ne 0</math> für alle <math>k</math> gebildet. Für <math>s_k &lt; 0</math> wird <math>x_k</math> durch <math>-x_k</math> ersetzt. Dann wird ein Vielfaches von <math>s^Tx</math> bzw. <math>s_0</math> zu <math>Ax = b</math> addiert, sodass nunmehr <math>a_{jk} > 0</math> für alle <math>(j, k)</math> gilt. O. B. d. A. sei <math>b_j = 1</math> für alle <math>j</math>. Für <math>D_j := (d_{jk}), d_{jk} = \delta_{jk}⁄a_{jk}, C_j := D_j R_j</math> und <math>x_k^{(\prime(0))} := C_j^{-1} \hat{n}/ \max_j a_{jk}</math> sei <math>x^{\prime(\grave{m})} = x^{\prime(m)} + \hat{n}C_j^{-1}(D_j^{-1}b - Ax^{\prime(m)}).\square</math>
+
Folgt <math>a_{jk} \le 0</math> für mindestens ein Paar <math>(j, k)</math>, so werden die Summe <math>s_0 := \sum\limits_{j=1}^m{b_j\varepsilon^j}</math> mit einer beliebigen transzendenten Zahl <math>\varepsilon</math> und <math>s_k := \sum\limits_{j=1}^m{a_{jk}\varepsilon^j} \ne 0</math> für alle <math>k</math> gebildet. Für <math>s_k &lt; 0</math> wird <math>x_k</math> durch <math>-x_k</math> ersetzt. Ein Vielfaches von <math>s^Tx</math> bzw. <math>s_0</math> wird so zu <math>Ax = b</math> addiert, dass <math>a_{jk} > 0</math> für alle <math>(j, k)</math> gilt. O. B. d. A. sei <math>b_j = 1</math> für alle <math>j</math>. Für <math>D_j := (d_{jk}), d_{jk} = \delta_{jk}⁄a_{jk}, C_j := D_j R_j</math> und <math>x_k^{(0)} := \hat{n}/ \max_j a_{jk}</math> sei <math>x^{(\grave{m})} = x^{(m)} + C_j^{-1}(b - Ax^{\prime(m)}).\square</math>
  
 
=== Korollar ===
 
=== Korollar ===

Version vom 17. November 2020, 20:48 Uhr

Willkommen bei MWiki

Satz des Monats

EW-Verfahren

Satz: Ist [math]\displaystyle{ A \in {}^{\nu}\mathbb{Q}^{n \times n} }[/math] in dem linearen Gleichungssystem (LGS) [math]\displaystyle{ Ax = b \in {}^{\nu}\mathbb{Q}^{n} }[/math] mit [math]\displaystyle{ n \in {}^{\nu}\mathbb{N}^* }[/math] regulär, berechnet das Einheitswurzelverfahren ([math]\displaystyle{ EW }[/math]-Verfahren) [math]\displaystyle{ x \in {}^{\nu}\mathbb{Q}^{n} }[/math] in [math]\displaystyle{ \mathcal{O}(n^2) }[/math]..

Beweis und Algorithmus

Seien [math]\displaystyle{ R_1 := (r_{1jk}) = (r_{1kj}) = R_1^T \in {}^{\nu}\mathbb{C}^{n \times n}, n \in {}^{\nu}2\mathbb{N}^*, r_{11k} := 1 }[/math] und für [math]\displaystyle{ j > 1 }[/math] sowie [math]\displaystyle{ n_{jk} := j + k - 3 }[/math] sowohl [math]\displaystyle{ r_{1jk} := \hat{n}e^{i\tau n_{jk}/n} }[/math] mit [math]\displaystyle{ n_{jk} < n }[/math] als auch [math]\displaystyle{ r_{1jk} := \hat{n}e^{i\tau(n_{jk} - \acute{n})/n} }[/math] mit [math]\displaystyle{ n_{jk} \ge n }[/math]. Durch Vertauschung der ersten Zeile bzw. Spalte mit der [math]\displaystyle{ j }[/math]-ten und entsprechender Vertauschung der übrigen Zeilen und Spalten entstehen die Matrizen [math]\displaystyle{ R_j = R_j^T }[/math] mit [math]\displaystyle{ j > 1 }[/math]. Sei [math]\displaystyle{ \delta_{jk} }[/math] das Kronecker-Delta und [math]\displaystyle{ A := (a_{jk}) }[/math].

Folgt [math]\displaystyle{ a_{jk} \le 0 }[/math] für mindestens ein Paar [math]\displaystyle{ (j, k) }[/math], so werden die Summe [math]\displaystyle{ s_0 := \sum\limits_{j=1}^m{b_j\varepsilon^j} }[/math] mit einer beliebigen transzendenten Zahl [math]\displaystyle{ \varepsilon }[/math] und [math]\displaystyle{ s_k := \sum\limits_{j=1}^m{a_{jk}\varepsilon^j} \ne 0 }[/math] für alle [math]\displaystyle{ k }[/math] gebildet. Für [math]\displaystyle{ s_k < 0 }[/math] wird [math]\displaystyle{ x_k }[/math] durch [math]\displaystyle{ -x_k }[/math] ersetzt. Ein Vielfaches von [math]\displaystyle{ s^Tx }[/math] bzw. [math]\displaystyle{ s_0 }[/math] wird so zu [math]\displaystyle{ Ax = b }[/math] addiert, dass [math]\displaystyle{ a_{jk} \gt 0 }[/math] für alle [math]\displaystyle{ (j, k) }[/math] gilt. O. B. d. A. sei [math]\displaystyle{ b_j = 1 }[/math] für alle [math]\displaystyle{ j }[/math]. Für [math]\displaystyle{ D_j := (d_{jk}), d_{jk} = \delta_{jk}⁄a_{jk}, C_j := D_j R_j }[/math] und [math]\displaystyle{ x_k^{(0)} := \hat{n}/ \max_j a_{jk} }[/math] sei [math]\displaystyle{ x^{(\grave{m})} = x^{(m)} + C_j^{-1}(b - Ax^{\prime(m)}).\square }[/math]

Korollar

Das EW-Verfahren kann die Eigenwerte und -vektoren von [math]\displaystyle{ Ax = \lambda x \in {}^{\nu}\mathbb{Q}^{n} + {}^{\nu}\mathbb{Q}^{n} }[/math] für [math]\displaystyle{ n \in {}^{\nu}2\mathbb{N}^*, \lambda \in {}^{\nu}\mathbb{Q}+ {i}^{\nu}\mathbb{Q} }[/math] und [math]\displaystyle{ A \in {}^{\nu}\mathbb{Q}^{n \times n} }[/math] mit dem Ansatz [math]\displaystyle{ x^{\prime(\grave{m})} = C_j^{-1}AC_j x^{\prime(m)} }[/math] in [math]\displaystyle{ \mathcal{O}(n^2) }[/math] bestimmen.[math]\displaystyle{ \square }[/math]

Bemerkung: Die Erweiterung auf komplexe [math]\displaystyle{ A }[/math] und [math]\displaystyle{ b }[/math] ist einfach.

Leseempfehlung

Nichtstandardmathematik