Numerik, Permutationsmatrix, Matrixnorm

Question

Numerik, Permutationsmatrix, Matrixnorm

Aufgabe:

a) Zeigen Sie, dass für eine Permutationsmatrix $ P \in \mathbb{R}^{n \times n} $ und eine beliebige Matrix $ A \in \mathbb{R}^{n \times n} $ gilt
$ \|P A\|_{1}=\|A\|_{1}=\|A P\|_{1} $
mit der Spaltenbetragssumme $ \|\cdot\|_{1} $ als Matrixnorm.

b) Beweisen Sie unter Verwendung von Aufgabenteil (a), dass für jede Permutationsmatrix $ P \in \mathbb{R}^{n \times n} $ und jede regulärc Matrix $ A \in \mathbb{R}^{n \times n} $ gilt
$ \kappa_{1}(P A)=\kappa_{1}(A) \text {. } $
wobei $\kappa_{1}(.)$ die Konditionszah! bezzüglich der Vorm $ \|\cdot\|_{1} $ bezeichnet.

c) Beweisen Sie für beliebige Matrizen $ A \in \mathbb{R}^{n \times n} $, dass
$ |\lambda| \leq\|A\| $
gilt für jeden Eigenwert $ \lambda $ von $ A $ und jede Matrixnorm $ \|\cdot\| $, die von einer Vektornorm erzeugt wird.

d) Eine Matrix $ A \in \mathbb{R}^{4 \times 4} $ besitze die Eigenwerte $ \frac{1}{20},-\frac{3}{4}, 3,-100 $. Leiten Sie mit der Eigenschaft aus Aufgabenteil (b) eine möglichst hohe untere Schranke (Zahlenwert anzugeben) für die Konditionszahl $ \kappa(A) $ bezüglich aller Matrixnormen, die von einer Vektornorm erzeugt werden, her.

e) Sei $ A \in \mathbb{R}^{n \times n} $ eine Matrix mit $ \operatorname{det}(A) \neq 0 $ und $ x, \tilde{x} \in \mathbb{R}^{n} $ Vektoren mit $ x \neq 0 $. Die Ergebnisse der Matrix-Vektor-Multiplikation lauten $ y=A x $ und $ \tilde{y}=A \tilde{x} $. Es wird eine beliebige Vektornorm $ \|\cdot\| $ und die zugehörige Matrixnorm verwendet.
i) Leiten Sie eine Abschätzung für die Abweichung $ \|\tilde{y}-y\| $ in Abhängigkeit der Abweichung $ \|\tilde{x}-x\| $ her.

ii) Leiten Sie eine Abschätzung für die relative Abweichung $ \frac{\|\bar{y}-y\|}{\|y\|} $ in Abhängigkeit der relativen Abweichung $ \frac{\|\bar{x}-x\|}{\|x\|} $ her. Bringen Sie die obere Schranke in Beziehung zur Konditionszahl der Matrix $ A $.

Problem/Ansatz:

Hallo Zusammen, könnte mir jemand bitte dabei helfen? Ich habe was gemacht aber bin mir nicht sicher, ob es richtig ist...

Zu a) Um zu zeigen, dass für eine Permutationsmatrix $P \in \mathbb{R}^{n \times n}$ und eine beliebige Matrix $A \in \mathbb{R}^{n \times n}$ gilt $\|PA\|_{1} = \|A\|_{1} = \|AP\|_{1}$ mit der Spaltenbetragssumme $\|\cdot\|_{1}$ als Matrixnorm, betrachten wir die Definition der Matrixnorm $\|\cdot\|_{1}$:

$\|A\|_{1} = \max_{1 \leq j \leq n} \sum_{i=1}^{n} |a_{ij}|$

Sei $P$ eine Permutationsmatrix und $A$ eine beliebige Matrix. Dann gilt:

$\|PA\|_{1} = \max_{1 \leq j \leq n} \sum_{i=1}^{n} |(PA)_{ij}|$

Da $P$ eine Permutationsmatrix ist, sind in jeder Spalte von $PA$ und $AP$ genau ein Eintrag ungleich null. Daher gilt:

$\sum_{i=1}^{n} |(PA)_{ij}| = \sum_{i=1}^{n} |(AP)_{ij}| = \sum_{i=1}^{n} |a_{ij}|$

Für jede Spalte $j$ von $A$ sind die Beträge der Einträge in $PA$ und $AP$ genau gleich. Daher ist die maximale Spaltenbetragssumme in beiden Fällen gleich:

$\|PA\|_{1} = \|A\|_{1} = \|AP\|_{1}$

Zu b) Um zu beweisen, dass für jede Permutationsmatrix $P \in \mathbb{R}^{n \times n}$ und jede reguläre Matrix $A \in \mathbb{R}^{n \times n}$ gilt $\kappa_{1}(PA) = \kappa_{1}(A)$ mit $\kappa_{1}(\cdot)$ als Konditionszahl bezüglich der $\|\cdot\|_{1}$-Norm, nutzen wir die Ergebnisse aus Aufgabenteil (b).

Die Konditionszahl bezüglich der $\|\cdot\|_{1}$-Norm ist definiert als:

$\kappa_{1}(A) = \|A\|_{1} \|A^{-1}\|_{1}$

Sei $P$ eine Permutationsmatrix. Dann gilt nach Aufgabenteil (b):

$\|PA\|_{1} = \|A\|_{1} = \|AP\|_{1}$

Da $A$ regulär ist, ist auch $A^{-1}$ regulär. Daher gilt:

$\kappa_{1}(PA) = \|PA\|_{1} \|(PA)^{-1}\|_{1} = \|A\|_{1} \|A^{-1}\|_{1} = \kappa_{1}(A)$

Daraus folgt $\kappa_{1}(PA) = \kappa_{1}(A)$ für jede Permutationsmatrix $P$ und jede reguläre Matrix $A$.

Zu c) Um zu beweisen, dass $|\lambda| \leq \|A\|$ für jeden Eigenwert $\lambda$ von $A$ und jede Matrixnorm $\|\cdot\|$ gilt, die von einer Vektornorm erzeugt wird, verwenden wir die Definition der Matrixnorm und den Zusammenhang zwischen Matrixnormen und Vektornormen.

Sei $\lambda$ ein Eigenwert von $A$ und $v$ der zugehörige Eigenvektor, d.h. $Av = \lambda v$ mit $\|v\| \neq 0$. Dann gilt:

$$ |\lambda| = \left|\frac{Av}{v}\right| $$

Nun betrachten wir die Matrixnorm $\|A\|$ und deren Definition:

$$ \|A\| = \sup_{\|x\| \neq 0} \frac{\|Ax\|}{\|x\|} $$

Wir setzen $x = v$ und erhalten:

$$ \|A\| = \sup_{\|v\| \neq 0} \frac{\|Av\|}{\|v\|} $$

Da $Av = \lambda v$ für den Eigenvektor $v$ gilt, können wir dies einsetzen:

$$ \|A\| = \sup_{\|v\| \neq 0} \frac{\|\lambda v\|}{\|v\|} = \sup_{\|v\| \neq 0} \frac{|\lambda|\|v\|}{\|v\|} = \sup_{\|v\| \neq 0} |\lambda| = |\lambda| $$

Daraus folgt $|\lambda| \leq \|A\|$ für jeden Eigenwert $\lambda$ von $A$ und jede Matrixnorm $\|\cdot\|$, die von einer Vektornorm erzeugt wird.

Gefragt 15 Jul 2023 von elena_12

📘 Siehe "Matrix" im Wiki

1 Antwort

Ein anderes Problem?

Stell deine Frage

nudger · Answer 1 · 2023-07-15T20:52:00+0000

Zu a)

Da $P$ eine Permutationsmatrix ist, sind in jeder Spalte von $PA$ und $AP$ genau ein Eintrag ungleich null.

Das stimmt nicht und die Rechnung danach auch nicht. Ich würde auch nicht mit dem Summenzeichen rechnen, sondern lieber damit argumentieren, dass Multiplikation von links mit $P$ eine Zeilenvertauschung bewirkt (dann Nachweis für $PA$ führen) und Multiplikation von rechts mit $P$ eine Spaltenvertauschung bewirkt (nochmal, getrennten, Nachweis für $AP$ führen).

Beachte, es werden Spaltensummen gebildet und darüber das Maximum.

zu b) Weitgehend richtig, aber sooo leicht darf man nicht $\|(PA)^{-1}\|=\|A^{-1}\|$ folgern. Da braucht es noch eine genauere Erklärimg-

zu c) Idee richtig, aber man kann nicht (niemals!) durch Vektoren dividieren. Musst Du also noch umschreiben.

Beantwortet 15 Jul 2023 von nudger

Zu c)

||A|| = sup ||λv v^-1|| = sup |λ| ||v v^-1|| = sup |λ| = |λ|

Richtig oder?

Zu b)

$ \kappa(\mathrm{PA})=\frac{\sigma_{\max }(\mathrm{PA})}{\sigma_{\min }(\mathrm{PA})}=\sqrt{\frac{\lambda_{\max }\left(\mathrm{A}^{T} \mathrm{P}^{T} \mathrm{PA}\right)}{\lambda_{\min }\left(\mathrm{A}^{T} \mathrm{P}^{T} \mathrm{PA}\right)}}=\sqrt{\frac{\lambda_{\max }\left(\mathrm{A}^{T} \mathrm{~A}\right)}{\lambda_{\min }\left(\mathrm{A}^{T} \mathrm{~A}\right)}}=\frac{\sigma_{\max }(\mathrm{A})}{\sigma_{\min }(\mathrm{A})}=\kappa(\mathrm{A}) $

Da bin ich mir aber nicht sicher da in der Aufgabenstellung das steht “Beweisen Sie unter Verwendung von Aufgabenteil (a)”

Zu a)

$ \|A\|=\frac{\|A\|\|x\|}{\|X\|} \geq \frac{\|A x\|}{\|x\|}=\frac{\|P\|\|A x\|}{\|x\|} \geq \frac{\|\rho A x\|}{\|x\|}=\|P A\| $

Kommentiert 16 Jul 2023 von elena_12

i) Um eine Abschätzung für die Abweichung $\|\tilde{y} - y\|$ in Abhängigkeit von $\|\tilde{x} - x\|$ herzuleiten, nutzen wir die Beziehung $y = Ax$ und $\tilde{y} = A\tilde{x}$:

$$ \tilde{y} - y = A\tilde{x} - Ax = A(\tilde{x} - x) $$

Nun betrachten wir die Normen beider Seiten der Gleichung und nutzen die Dreiecksungleichung:

$$ \|\tilde{y} - y\| = \|A(\tilde{x} - x)\| \leq \|A\| \|\tilde{x} - x\| $$

Die Abschätzung lautet somit $\|\tilde{y} - y\| \leq \|A\| \|\tilde{x} - x\|$.

ii) Um eine Abschätzung für die relative Abweichung $\frac{\|\bar{y} - y\|}{\|y\|}$ in Abhängigkeit von $\frac{\|\bar{x} - x\|}{\|x\|}$ herzuleiten, nutzen wir erneut die Beziehung $y = Ax$ und $\bar{y} = A\bar{x}$:

$$ \frac{\|\bar{y} - y\|}{\|y\|} = \frac{\|A\bar{x} - Ax\|}{\|Ax\|} $$

Aus der Submultiplikativität der Norm erhalten wir:

$$ \frac{\|\bar{y} - y\|}{\|y\|} = \frac{\|A(\bar{x} - x)\|}{\|Ax\|} \leq \frac{\|A\| \|\bar{x} - x\|}{\|A\|\|x\|} $$

Da $\frac{\|Ax\|}{\|x\|}$ die Konditionszahl von $A$ bezüglich der gewählten Norm darstellt, erhalten wir die Abschätzung:

$$ \frac{\|\bar{y} - y\|}{\|y\|} \leq \kappa(A) \frac{\|\bar{x} - x\|}{\|x\|} $$

Die obere Schranke steht somit in Beziehung zur Konditionszahl der Matrix $A$.

Kommentiert 17 Jul 2023 von elena_12

Numerik, Permutationsmatrix, Matrixnorm

1 Antwort

Ähnliche Fragen

Eingabetools:

Beliebte Fragen:

Heiße Lounge-Fragen: