5.6: Вправи

Last updated
Save as PDF

Page ID: 33338

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$

Вправа 5.1

Припустимо,$A$ комплексна$m \times n$ матриця збурена до матриці$A + E$.

(а) Покажіть, що

\[\left|\sigma_{\max }(A+E)-\sigma_{\max }(A)\right| \leq \sigma_{\max }\tag{E}\]

Також знайдіть,$E$ що призводить до того, що нерівність досягається рівністю.

(Підказка: Щоб показати нерівність, напишіть$(A + E) = A + E$ і$A = (A + E) - E$, візьміть 2-норму з обох сторін кожного рівняння, і використовуйте нерівність трикутника.)

Виходить, що результат в (а) насправді застосовується до всіх сингулярних значень$A$ і$A + E$, а не тільки найбільшого. Частина (b) нижче - одна з версій результату для найменшого значення однини.

(b) Припустимо, що A має менше, ніж повний ранг стовпця, тобто має ранг$< n$, але$A + E$ має повний ранг стовпця. Показати (слідуючи процедурі, подібній до частини (а) - але дивлячись,$min \|(A+E)x\|_{2}$ а не на норму і т.д.)$A + E$, що

\[\sigma_{\min }(A+E) \leq \sigma_{\max }\tag{E}\]

Знову знайдіть$E$, що призводить до того, що нерівність досягається рівністю.

[Результат у (b) та деякі його розширення породжують наступну звукову (і широко використовувану) процедуру оцінки рангу якоїсь базової матриці$A$, враховуючи лише матрицю$A + E$ та знання$\|E\|_{2}$: Обчислити SVD$A + E$, а потім оголосити «числовий ранг» $A$бути кількістю сингулярних значень$A + E$, які більші за поріг$\|E\|_{2}$. Дана інформація узгоджується з наявністю$A$ такого рангу.]

(c) Перевірте наведені вище результати, використовуючи власні приклади в MATLAB. Можливо, вам також буде цікаво перевірити чисельно, що для великих$m, n$, норма матриці$E = s * randn(m, n)$ - яка є матрицею, записи якої є незалежними, нульовим середнім, гаусовим, зі стандартним відхиленням$s$ - близька до$s *(\sqrt{m}+\sqrt{n})$. Так$A$ що якщо збурено такою матрицею, то розумним значенням для використання в якості порогу при визначенні числового рангу$A$ є це число.

Вправа 5.2

$A$$E$Дозволяти і бути$m \times n$ матрицями. Покажіть, що

\[\min _{\operatorname{rank} E \leq r}\|A-E\|_{2}=\sigma_{r+1}\tag{A}\]

Щоб довести це, зверніть увагу, що обмеження рангу на$E$ можна інтерпретувати так: Якщо$v_{1},. . . v_{r+1}$ є лінійно незалежними векторами, то існує ненульовий вектор$z$, виражений у вигляді лінійної комбінації таких векторів, що належить до нульового простору$E$. Дійте наступним чином:

Виберіть$v_{i}$ їх з SVD A.
Виберіть елемент кандидата за$z$ допомогою$\|z\|_{2} = 1$.
Покажіть, що$\|(A - E)z\|_{2} \geq \sigma_{r+1}$. Це означає, що$\|(A - E)\|_{2} \geq \sigma_{r+1}$.
Побудуйте та$E$, яка досягає вищезазначеної межі.

Вправа 5.3

Розглянемо дійсну, квадратну систему рівнянь$Ax = (U \Sigma V^{T})x = y$, де$U$ і$V$ є ортогональними матрицями, з

\ [\ Sigma =\ лівий (\ begin {масив} {cc}
1 & 0\
0 & 10^ {-6}
\ кінець {масив}\ праворуч),\ quad y=U\ лівий (\ begin {масив} {c}
1\\
10^ {-6}
\ кінець {масив}\ праворуч)\ nonumber\]

Всі норми в цій проблемі приймаються за 2-норми.

(а) Яка норма точного рішення$x$?

(b) Припустимо,$y$ що збурено$y + \delta y$, і що відповідно рішення змінюється від$x$ in (a) до$x + \delta x$. Знайти збурень$\delta y$, з, таке$\|\delta y\|= 10^{-6}$, що

\[\frac{\|\delta x\|}{\|x\|} \approx \kappa(A) \frac{\|\delta y\|}{\|y\|}\nonumber\]

де$\kappa (A)$ - умова номер$A$.

(c) Припустимо, замість того, щоб збурити$A$,$y$ ми обурюємо$A + \delta A$, змінюючи його на, при цьому рішення відповідно змінюється від$x$ до$x + \delta x$ (для деяких$\delta x$, що відрізняється від частини (b)). Знайти збурень$\delta A$, з, таке$\|\delta A\|= 10^{-7}$, що

\[\frac{\|\delta x\|}{\|x\|} \approx \kappa(A) \frac{\|\delta A\|}{\|A\|}\nonumber\]

Вправа 5.4 Позитивні певні матриці

$A$Матриця позитивна напіввизначена якщо$x^{\prime}Ax \geq 0$ для всіх$x \neq 0$. Ми говоримо$Y$, що це квадратний корінь Ермітієвої позитивної напіввизначеної матриці, якщо$Y^{\prime}Y = A$. Показати, що$Y$ завжди існує і може бути побудовано з SVD$A$.

Вправа 5.5

Нехай$A$ і$B$ мають сумісні розміри. Покажіть, що якщо

\ [$\ |A x\ |_ {2}\ leq\ |B x\ |_ {2} $
для всіх $x$\ nonumber\]

то існує матриця$Y$ з$\|Y\|_{2} \leq 1$ такою, що

\[A=YB\nonumber\]

Припустимо$B$, має повний ранг до простоти.

Вправа 5.6

(а) Припустимо

\ [\ лівий\ |\ лівий (\ begin {масив} {cc}
X\\
A
\ end {масив}\ праворуч)\ право\ |\ leq\ гамма\ nonumber\]

Показати, що існує матриця$Y$ з$\|Y\|_{2} \leq 1$ такою, що

\[X=Y\left(\gamma^{2} I-A^{\prime} A\right)^{\frac{1}{2}}\nonumber\]

(б) Припустимо

\ [\ лівий\ |\ лівий (\ begin {масив} {cc}
X & A\\ end {масив}\ праворуч)\ право\ |\ leq\ гамма\ nonumber\]

Показати, що існує матриця$Z$ з$\|Z\| \leq 1$ такою, що$X = (\gamma^{2}I - AA^{*})^{\frac{1}{2}}Z$

Вправа 5.7 Розбудова матриці

Вищеописані проблеми можуть допомогти нам довести наступний важливий результат:

\ [\ gamma_ {0} :=\ min _ {X}\ ліворуч\ |\ ліворуч (\ почати {масив} {
cc}
X & B\ A
\ кінець {масив}\ праворуч)\ праворуч\ |=\ max\ ліворуч\ {\ |\ left (\ begin {масив} {
cc} C &\ left.a)\ |\ left (\ begin {масив}}
B\\
A
\ end {масив}\ праворуч)\ |\ право\}
\ кінець {масив}\ право. \ праворуч. \ номер\]

Це відоме як теорема розширення матриці. Зверніть увагу, що ліва сторона завжди більше або дорівнює правій стороні незалежно від вибору$X$. Нижче ми окреслимо кроки, необхідні для того, щоб довести, що ця нижня межа жорстка. Матричні розширення відіграють важливу роль в теорії систем, особливо в задачах модельного скорочення.

1. $\gamma_{1}$Дозволяти визначатися як

\ [\ gamma_ {1} =\ max\ лівий\ {\ лівий\ |\ лівий (\ begin {масив} {ll}
C & A
\ end {масив}\ праворуч)\ праворуч\ |,\ лівий\ |\ лівий (\ begin {масив} {l}
B
\
A\ end {масив}\ праворуч\ |\ праворуч\}\ nonumber\]

Покажіть, що:

\[\gamma_{0} \geq \gamma_{1}\nonumber\]

2. Використовуйте попередню вправу, щоб показати, що існує дві матриці$Y$ і$Z$ з нормами, меншими або рівними одній, такі, що

\[B=Y\left(\gamma_{1}^{2} I-A^{*} A\right)^{\frac{1}{2}}, \quad C=\left(\gamma_{1}^{2} I-A A^{*}\right)^{\frac{1}{2}} Z\nonumber\]

3. Визначте рішення кандидата, яке буде$\tilde{X}=-Y A^{*} Z$. Покажіть прямою заміною, що

\ [\ почати {вирівняний}
\ ліворуч.\ |\ begin {масив} {cc}
\ тильда {X} & B\\
C & A
\ кінець {масив}\ праворуч)\ | &=\ лівий\ |\ лівий (\ begin {масив} {cc}
-Y A^ {*} Z & Y\ лівий (\ gamma_ {1} ^ {2} I-A^ {*} A\ правий) ^ {\ гідророзриву {1} {2}}\
C=\ ліворуч (\ гамма_ { 1} ^ {2} I-A A^ {*}\ праворуч) ^ {\ frac {1} {2}} Z & A
\ кінець {масив}\ праворуч\ |\\
&=\ лівий\ |\ лівий (\ begin {масив} {cc} {cc}
Y & 0\\
0 & I
\ end {масив}\ праворуч)\ лівий (\ початок {масив} {cc}
-A^ {*} &\ ліворуч (\ гамма_ {1} ^ {2} I-A^ {*} A\ праворуч) ^ {\ frac {1} {2}}\\
C=\ ліворуч (\ gamma_ {1} ^ {2} I-A ^ {*}\ праворуч) ^ {\ frac {1} {2}} & A
\ end {масив}\ праворуч)\ лівий (\ початок {масив} {cc}
Z &
0 & I
\\ end {масив}\ праворуч)\ праворуч\ |
\ кінець {вирівняний}\ nonumber\]

4. Покажіть, що

\ [\ лівий\ |\ лівий (\ begin {масив} {cc}
\ тильда {X} & B\\
C & A
\ end {масив}\ праворуч)\ праворуч\ |\ leq\ gamma_ {1}\ nonumber\]

Це означає те,$\gamma_{0} \leq \gamma_{1}$ що доводить твердження.

Вправа 5.8

Довести або спростувати (через зустрічний приклад) наступні сингулярні значення нерівності.

$\sigma_{\min }(A+B) \leq \sigma_{\min }(A)+\sigma_{\min }(B)$для будь-яких$A$ і$B$.
$\sigma_{\min }(A+E) \leq \sigma_{\max }(E)$всякий раз, коли$A$ не має стовпця рангу, і$E$ є будь-якою матрицею.
$\sigma_{\max }(A) <1$, потім\[\sigma_{m a x}(I-A)^{-1} \leq \frac{1}{1-\sigma_{\max }(A)}\nonumber\]
$\sigma_{i }(I + A) \leq \sigma_{i}(A)+1$.