3.8

Обратные суммы и чувствительность

[8/100%]
Показать
LaTeX
Задача 3.8.1

Вспомните формулу Шермана–Моррисона: если An×n\mathbf{A}_{n \times n} невырождена, а c→\overrightarrow {c}, d→\overrightarrow {d} — столбцы размера n×1n \times 1, такие что 1+d→TA−1c→≠01+\overrightarrow {d}^{T}\mathbf{A}^{-1}\overrightarrow {c} \neq 0, то сумма A+c→d→T\mathbf{A}+\overrightarrow {c}\overrightarrow {d}^{T} невырождена, и

(A+c→d→T)−1=A−1−A−1c→d→TA−11+d→TA−1c→. (\mathbf{A}+\overrightarrow {c}\overrightarrow {d}^{T})^{-1} = \mathbf{A}^{-1} - \frac{\mathbf{A}^{-1}\overrightarrow {c}\overrightarrow {d}^{T}\mathbf{A}^{-1}}{1+\overrightarrow {d}^{T}\mathbf{A}^{-1}\overrightarrow {c}}.

Предположим, вам даны

A=[20−1−111−101]иA−1=[10101−1102]. \mathbf{A} = \begin{bmatrix} 2 & 0 & -1 \\ -1 & 1 & 1 \\ -1 & 0 & 1 \end{bmatrix} \qquad \text{и} \qquad \mathbf{A}^{-1} = \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & -1 \\ 1 & 0 & 2 \end{bmatrix}.
?
(a)

Используя формулу Шермана--Моррисона, найдите обратную матрицу для B\mathbf{B}, полученной из A\mathbf{A} изменением элемента (3,2)(3,2) с 00 на 22.

(b)

Пусть C\mathbf{C} — матрица, совпадающая с A\mathbf{A} всюду, кроме того что c32=2c_{32}=2 и c33=2c_{33}=2. Используя формулу Шермана--Моррисона, найдите C−1\mathbf{C}^{-1}.

Задача 3.8.2

Предположим, что A\mathbf{A} и B\mathbf{B} — невырожденные матрицы, причём B\mathbf{B} получается из A\mathbf{A} заменой A∗j\mathbf{A}_{*j} на другой столбец b→\overrightarrow {b}. Используя формулу Шермана--Моррисона, выведите, что

B−1=A−1−(A−1b→−e→j)[A−1]j∗[A−1]j∗b→. \mathbf{B}^{-1} = \mathbf{A}^{-1} - \frac{(\mathbf{A}^{-1}\overrightarrow {b}-\overrightarrow {e}_{j})[\mathbf{A}^{-1}]_{j*}}{[\mathbf{A}^{-1}]_{j*}\overrightarrow {b}}.
?
Задача 3.8.3

Предположим, что матрица коэффициентов невырожденной системы Ax→=b→\mathbf{A}\overrightarrow {x} = \overrightarrow {b} обновляется, порождая другую невырожденную систему (A+c→d→T)z→=b→(\mathbf{A}+\overrightarrow {c}\overrightarrow {d}^{T})\overrightarrow {z} = \overrightarrow {b}, где b→,c→,d→∈Rn×1\overrightarrow {b}, \overrightarrow {c}, \overrightarrow {d} \in \mathbb {R}^{n \times 1}, и пусть y→\overrightarrow {y} — решение Ay→=c→\mathbf{A}\overrightarrow {y} = \overrightarrow {c}. Покажите, что

z→=x→−y→d→Tx→1+d→Ty→. \overrightarrow {z} = \overrightarrow {x} - \frac{\overrightarrow {y}\overrightarrow {d}^{T}\overrightarrow {x}}{1+\overrightarrow {d}^{T}\overrightarrow {y}}.
?
Задача 3.8.4
?
(a)

Используя формулу Шермана--Моррисона, докажите, что если A\mathbf{A} невырождена, то A+αe→ie→jT\mathbf{A}+\alpha \overrightarrow {e}_{i}\overrightarrow {e}_{j}^{T} невырождена при достаточно малом α\alpha.

(b)

Используя пункт (а), докажите, что I+E\mathbf{I}+\mathbf{E} невырождена, когда все ϵij\epsilon_{ij} достаточно малы по модулю. Это альтернатива использованию рассуждения с рядом Неймана.

Задача 3.8.5

Для заданных матриц A\mathbf{A} и B\mathbf{B}, где A\mathbf{A} невырождена, объясните, почему A+ϵB\mathbf{A}+\epsilon \mathbf{B} также невырождена, когда вещественное число ϵ\epsilon ограничено достаточно малым интервалом вокруг начала координат. Иными словами, докажите, что малые возмущения невырожденных матриц также невырождены.

?
Задача 3.8.6

Выведите формулу Шермана--Моррисона--Вудбери: если An×n\mathbf{A}_{n \times n} невырождена, а C\mathbf{C}, D\mathbf{D} имеют размер n×kn \times k, причём (I+DTA−1C)−1(\mathbf{I}+\mathbf{D}^{T}\mathbf{A}^{-1}\mathbf{C})^{-1} существует, то

(A+CDT)−1=A−1−A−1C(I+DTA−1C)−1DTA−1. (\mathbf{A}+\mathbf{C}\mathbf{D}^{T})^{-1} = \mathbf{A}^{-1} - \mathbf{A}^{-1}\mathbf{C}(\mathbf{I}+\mathbf{D}^{T}\mathbf{A}^{-1}\mathbf{C})^{-1}\mathbf{D}^{T}\mathbf{A}^{-1}.
?
Примечание.
?

Вспомните упражнение 3.7.11 (формулы блочного обращения через дополнения Шура) и рассмотрите произведение (IC0I)(ACDT−I)(I0DTI)\begin{pmatrix} \mathbf{I} & \mathbf{C} \\ \mathbf{0} & \mathbf{I} \end{pmatrix}\begin{pmatrix} \mathbf{A} & \mathbf{C} \\ \mathbf{D}^{T} & -\mathbf{I} \end{pmatrix}\begin{pmatrix} \mathbf{I} & \mathbf{0} \\ \mathbf{D}^{T} & \mathbf{I} \end{pmatrix}.

Задача 3.8.7

Вспомните норму ∥A∥=max⁡i∑j∣aij∣\left\| \mathbf{A}\right\| = \max_{i}\sum_{j}\left|a_{ij}\right| (максимальную сумму модулей элементов строки) и связанное с ней число обусловленности κ(A)=∥A∥∥A−1∥\kappa (\mathbf{A}) = \left\| \mathbf{A}\right\| \left\| \mathbf{A}^{-1}\right\| невырожденной матрицы A\mathbf{A}, которое показывает, насколько плохо обусловлена A\mathbf{A} (чем больше κ\kappa, тем хуже обусловленность).

Используя указанную выше норму, упорядочите следующие матрицы по степени плохой обусловленности:

A=[1000−1000100−100−100−100300],B=[18−1−9−711111718],C=[122−4201−45−45−9481]. \mathbf{A} = \begin{bmatrix} 100 & 0 & -100 \\ 0 & 100 & -100 \\ -100 & -100 & 300 \end{bmatrix}, \qquad \mathbf{B} = \begin{bmatrix} 1 & 8 & -1 \\ -9 & -71 & 11 \\ 1 & 17 & 18 \end{bmatrix}, \qquad \mathbf{C} = \begin{bmatrix} 1 & 22 & -42 \\ 0 & 1 & -45 \\ -45 & -948 & 1 \end{bmatrix}.
?
Задача 3.8.8

Предположим, что элементы A(t)\mathbf{A}(t), x→(t)\overrightarrow {x}(t) и b→(t)\overrightarrow {b}(t) являются дифференцируемыми функциями вещественной переменной tt, такими что A(t)x→(t)=b→(t)\mathbf{A}(t)\overrightarrow {x}(t) = \overrightarrow {b}(t).

?
(a)

Предполагая, что A(t)−1\mathbf{A}(t)^{-1} существует, объясните, почему

dA(t)−1dt=−A(t)−1A′(t)A(t)−1. \frac{d\mathbf{A}(t)^{-1}}{dt} = -\mathbf{A}(t)^{-1}\mathbf{A}'(t)\mathbf{A}(t)^{-1}.
(b)

Выведите уравнение

x→′(t)=A(t)−1b→′(t)−A(t)−1A′(t)x→(t). \overrightarrow {x}'(t) = \mathbf{A}(t)^{-1}\overrightarrow {b}'(t) - \mathbf{A}(t)^{-1}\mathbf{A}'(t)\overrightarrow {x}(t).

Это показывает, что A−1\mathbf{A}^{-1} усиливает как изменение A\mathbf{A}, так и изменение b→\overrightarrow {b}, и тем самым подтверждает наблюдение, сделанное в задаче (3.8.8), о том, что чувствительность невырожденной системы к малым возмущениям напрямую связана с величиной элементов A−1\mathbf{A}^{-1}.