Ctrl+K

Линейная алгебра (напоминание)

Линейная алгебра (напоминание)#

Векторные нормы#

Обобщим длину вектора (расстояние между двумя точками). Такое обобщение называется нормой.

Норма - функционал \(\|\mathbf{x}\|\) заданный на векторном пространстве \(\mathbb{R}^n\), для которого выполняются утверждения:

  • \(\|\mathbf{x}\| = 0 \Leftrightarrow \mathbf{x} = \mathbf{0}\)

  • \(\|\alpha \mathbf{x}\| = |\alpha|\|\mathbf{x}\|\)

  • \(\|\mathbf{x} + \mathbf{y}\| \leq \|\mathbf{x}\| + \|\mathbf{y}\|\)

Рассмотрим семейство норм \(||\mathbf{x}||_p = (\sum\limits_{i = 1}^{n}|x_i|^p)^{\frac{1}{p}}\). Самые важные представители:

  • \(||\mathbf{x}||_1 =\sum\limits_{i = 1}^{n} |x_i| \) - манхэттенское расстояние, октаэдрическая, \(\ell_1\) норма.

  • \(||\mathbf{x}||_2 = (\sum\limits_{i = 1}^{n}x_i^2)^{\frac{1}{2}}\) - евклидова норма, \(\ell_2\) норма.

  • \(||\mathbf{x}||_{\infty} = \max\limits_{i}|x_i|\) - кубическая норма, \(\ell_\infty\).

Теорема (о константе эквивалентности конечномерных норм):

Рассмотрим векторное пространство \(\mathbb{R}^n\). Тогда:

\[\forall p,q \;\; \exists C_1, C_2 > 0 : \; \forall x \in \mathbb{R}^n \hookrightarrow C_1||\mathbf{x}||_p\leq||\mathbf{x}||_q\leq C_2||\mathbf{x}||_p\]

Визуализация векторных норм. Единичный диск.#

Пакет NumPy содержит всё необходимое для вычисления норм - функция np.linalg.norm:

import numpy as np
n = 100

a = np.ones(n) # вектор единиц размера n

b = a + 1e-3 * np.random.randn(n) # возмущённый вектор a

# Посмотрим, как возмущение вектора повлияло на относительную ошибку в вычислении нормы

print('Relative error in L1 norm:', np.linalg.norm(a - b, 1) / np.linalg.norm(b, 1))
print('Relative error in L2 norm:', np.linalg.norm(a - b) / np.linalg.norm(b))
print('Relative error in Chebyshev norm:', np.linalg.norm(a - b, np.inf) / np.linalg.norm(b, np.inf))

Relative error in L1 norm: 0.0007543854647883141
Relative error in L2 norm: 0.0009374816160543979
Relative error in Chebyshev norm: 0.002409222048420099

Единичный диск – это множество точек такое, что

\[\|\mathbf{x}\| <= 1 \]

Для евклидовой нормы единичный диск сопадает с обычным диском.

Для других норм единичный диск сильно отличается от привычного нам диска.

\(\ell_1\)-норма, \(||\mathbf{x}||_1 =\sum\limits_{i = 1}^{n} |x_i| \)#

Hide code cell source 
%matplotlib inline
import matplotlib.pyplot as plt
import numpy as np
p = 1 # Which norm do we use
M = 40000 # Number of sampling points
a = np.random.randn(M, 2)
b = []
for i in range(M):
    if np.linalg.norm(a[i, :], p) <= 1:
        b.append(a[i, :])
b = np.array(b)
plt.plot(b[:, 0], b[:, 1], '.')
plt.axis('equal')
_ = plt.title('Unit disk in the p-th norm, $p={0:}$'.format(p))
../../_images/9c9b25a04043d13f1f77c2bc3a735020f4835a3392a59e970510773c662b59be.png

\(\ell_2\)-норма, \(||\mathbf{x}||_2 = (\sum\limits_{i = 1}^{n}x_i^2)^{\frac{1}{2}}\)#

Hide code cell source 
%matplotlib inline
import matplotlib.pyplot as plt
import numpy as np
p = 2 # Which norm do we use
M = 40000 # Number of sampling points
a = np.random.randn(M, 2)
b = []
for i in range(M):
    if np.linalg.norm(a[i, :], p) <= 1:
        b.append(a[i, :])
b = np.array(b)
plt.plot(b[:, 0], b[:, 1], '.')
plt.axis('equal')
_ = plt.title('Unit disk in the p-th norm, $p={0:}$'.format(p))
../../_images/3be97c9d6755fa3555100af09623249debb5bda0cf11aa231c3cb6423162c1b2.png

\(\ell_\infty\)-норма, \(||\mathbf{x}||_{\infty} = \max\limits_{i}|x_i|\)#

Hide code cell source 
%matplotlib inline
import matplotlib.pyplot as plt
import numpy as np
p = 1000 # Which norm do we use
M = 40000 # Number of sampling points
a = np.random.randn(M, 2)
b = []
for i in range(M):
    if np.linalg.norm(a[i, :], p) <= 1:
        b.append(a[i, :])
b = np.array(b)
plt.plot(b[:, 0], b[:, 1], '.')
plt.axis('equal')
_ = plt.title('Unit disk in the p-th norm, $p={0:}$'.format(p))
../../_images/b01e2078efffab4cb9536143a1fb07c6ccc7e84309eb1f6346496e630186e9f6.png

Матричные нормы#

Норма матрицы должна удовлетворять стандартным аксиомам нормы:

  • \(\|\mathbf{A}\|=0 \quad \Leftrightarrow \quad \mathbf{A}=\mathbf{0}\)

  • \(\|\alpha \mathbf{A}\|=|\alpha|\|\mathbf{A}\|, \quad \forall \alpha \in \mathbb{R}\)

  • \(\|\mathbf{A}+\mathbf{B}\| \leqslant\|\mathbf{A}\|+\|\mathbf{B}\|\).

Определение. Матричная норма \(\|\mathbf{A}\|_{\text{matrix}}\) называется согласованной с векторной нормой \(\|\mathbf{x}\|_{\text{vector}}\), если выполняется соотношение

\[ \|\mathbf{A}\mathbf{x}\|_{\text{vector}} \leqslant\|\mathbf{A}\|_{\text{matrix}} \cdot\|\mathbf{x}\|_{\text{vector}} \]

В дальнейшем не будем отдельно подписывать matrix и vector нормы - если норма берётся от вектора подразумеваем векторную норму и т.д.

Определение. Матричная норма \(\|\mathbf{A}\|\) называется субмультипликативной, если

\[ \|\mathbf{A} \cdot \mathbf{B}\| \leqslant\|\mathbf{A}\| \cdot\|\mathbf{B}\| \]

Наконец введём ключевое определение, позволяющее естественным образом создавать матричную норму из векторной.

Определение. Матричная норма \(\|\mathbf{A}\|\) называется подчиненной векторной норме \(\|\mathrm{x}\|\), если

\[ \|\mathbf{A}\| \equiv \sup _{\mathbf{x} \neq \mathbf{0}} \frac{\|\mathbf{A} \mathbf{x}\|}{\|\mathbf{x}\|}=\sup _{\|\mathbf{x}\|=1}\|\mathbf{A} \mathbf{x}\| \]

Покажем, что определенные таким образом матричные нормы будут «хорошими» через следующую лемму.

Лемма (об индуцированной норме)

Если норма \(\|\mathbf{A}\|\) подчинена какой-то векторной норме \(\|\mathbf{x}\|\), то она субмультипликативна и согласована с ней.

\(\Delta\)

1) Субмультипликативность
\[ \|\mathbf{A} \cdot \mathbf{B}\|=\sup _{\mathbf{x} \neq 0} \frac{\|\mathbf{A B} \mathbf{x}\|}{\|\mathbf{x}\|}=\sup _{\mathbf{B x} \neq 0} \frac{\|\mathbf{A B} \mathbf{x}\|}{\|\mathbf{x}\|} \leqslant \sup _{\mathbf{B x} \neq 0} \frac{\|\mathbf{A B} \mathbf{x}\|}{\|\mathbf{B} \mathbf{x}\|} \sup _{\mathbf{B} \mathbf{x} \neq 0} \frac{\|\mathbf{B} \mathbf{x}\|}{\|\mathbf{x}\|} \leqslant \]

Последние два супремума взяты по части множества ненулевых векторов. От увеличения множества они не уменьшатся:

\[ \leqslant \sup _{\mathbf{y} \neq 0} \frac{\|\mathbf{A} \mathbf{y}\|}{\|\mathbf{y}\|} \sup _{\mathbf{z} \neq 0} \frac{\|\mathbf{B} \mathbf{z}\|}{\|\mathbf{z}\|}=\|\mathbf{A}\| \cdot\|\mathbf{B}\| \]
2) Согласованность
\[ \|\mathbf{A}\|=\sup _{\mathbf{x} \neq \mathbf{0}} \frac{\|\mathbf{A} \mathbf{x}\|}{\|\mathbf{x}\|} \Rightarrow\|\mathbf{A} \mathbf{x}\| \leqslant\|\mathbf{A}\| \cdot\|\mathbf{x}\| \]

Кроме этого, из-за компактности множества \(\left\{\mathrm{x} \in \mathbb{R}^n \mid\|\mathrm{x}\|=1\right\}\), точная верхняя грань достигается на некотором векторе \(\mathrm{x}_0 \neq \mathbf{0}\), то есть для него справедливо

\[ \left\|\mathbf{A} \mathbf{x}_0\right\|=\|\mathbf{A}\| \cdot\left\|\mathbf{x}_0\right\| \]
⬛

Прежде, чем мы перейдём к явному виду матричных норм для векторных норм, упомянутых ранее, введём ещё одно важное определение из линейной алгебры.

Сингулярное разложение#

Определение. Сингулярное разложение произвольной матрицы \(\mathbf{A}\) есть

original image

Элементы матрицы \(\Sigma\) называются сингулярными числами. Они всегда положительны. Звёздочка на картинке - транспонирование и комплексное сопряжение (эрмитово сопряжение).

Свойства сингулярного разложения (см. картинку сверху):

  • \(r=\operatorname{rank}(A)\)

  • \(U, V\) - унитарные (\(U^{*}U=E\))

  • \(\sigma_1 \geq \ldots \geq \sigma_r>0\) - ненулевые сингулярные числа. Для эрмитовых матриц равны модулям собственных чисел.

  • Столбцы \(U, V\) - сингулярные вектора.

  • Существует всегда для любой матрицы (даже неквадратной).

Модуль максимального сингулярного числа показывает, в какое максимальное число раз оператор может увеличить длину вектора своим действием.

Таким образом, сингулярное разложение - это естественное обобщение спектрального разложения.

Явный вид матричных норм#

Приведём явный вид матричных норм, подчинённых ранее определённым векторным нормам. Для док-ва этих явных видов см. лекцию B1 или прочитайте презентацию. Также в дополнительных материалах лежат несколько полезных методичек.

Максимальная векторная норма (\(\ell_\infty\))#

Индуцирована векторной нормой \(\|\mathbf{x}\|_{\infty}=\max _i\left|x_i\right|\), и имеет вид

\[ \|\mathbf{A}\|_{\infty}=\max _i \sum_j\left|a_{i j}\right|, \]

и достигается на векторе \(\mathrm{x}_0\), составленном из знаков строки матрицы А с максимальной суммой модулей элементов:

\[ \left\|\mathbf{A} \mathbf{x}_0\right\|_{\infty}=\|\mathbf{A}\|_{\infty} \cdot\left\|\mathbf{x}_0\right\|_{\infty} \]

Т.е. максимальная матричная норма есть максимальная сумма модулей элементов в строке.

Манхэттенская норма (\(\ell_1\))#

Индуцирована векторной нормой \(\|\mathrm{x}\|_1=\sum_i\left|x_i\right|\), и имеет вид

\[ \|\mathbf{A}\|_1=\max _j \sum_i\left|a_{i j}\right|=\left\|\mathbf{A}^{\top}\right\|_{\infty}, \]

и достигается на векторе \(\mathrm{x}_0-\mathrm{j}\)-м столбце единичной матрицы:

\[ \left\|\mathbf{A} \mathbf{x}_0\right\|_1=\|\mathbf{A}\|_1 \cdot\left\|\mathbf{x}_0\right\|_1 \]

Т.е. \(\ell_1\) матричная норма есть максимальная сумма модулей элементов в столбце.

Евклидова норма (\(\ell_2\))#

Индуцирована евклидовой нормой \(\|\mathrm{x}\|_2 = \|\mathrm{x}\|_e = \sqrt{\sum_i x_i^2}\).

Евклидова норма матрицы А равна ее максимальному сингулярному числу:

\[ \|\mathbf{A}\|_e=\sigma_{\max }(\mathbf{A})=\sqrt{\lambda_{\max }\left(\mathbf{A}^{\top} \mathbf{A}\right)}, \]

и достигается на соответствующем правом сингулярном векторе

\[ \mathbf{x}_0=\mathbf{V} \mathbf{z}_0=\mathbf{v}_{j_0}, \quad \mathbf{A}^{\top} \mathbf{A} \mathbf{v}_{j_0}=\lambda_{\max } \mathbf{v}_{j_0} \]

где \(j_0\) - номер максимального сингулярного числа, \(\mathbf{v}_{j_0}-j_0\)-й столбец матрицы V.

Сингулярные и собственные числа - разные вещи

Как видим, необязательно считать сингулярные числа для матрицы \(\mathbf{A}\), чтобы найти её евклидову норму. Достаточно посчитать собственные числа матрицы \(\mathbf{A}^{\top} \mathbf{A}\), и взять корень из максимального.

Норма Фробениуса#

Является неоператорной нормой, т.е. неподчинённой никакой векторной нормой.

\[ \|A\|_F=\sqrt{\sum_{i=1}^n \sum_{j=1}^n\left|a_{i j}\right|^2} \]

Норма Фробениуса легко вычисляется (по сравнению, например, со спектральной нормой). Обладает следующими свойствами:

  • Согласованность c \(\ell_2\)-нормой \(:\|\mathbf{A}\mathbf{x}\|_{2} \leq\|\mathbf{A}\|_{F}\|\mathbf{x}\|_{2}\), так как в силу неравенства Коши-Буняковского

\[ \|\mathbf{A}\mathbf{x}\|_{2}^{2}=\sum_{i=1}^{m}\left|\sum_{j=1}^{n} a_{i j} x_{j}\right|^{2} \leq \sum_{i=1}^{m}\left(\sum_{j=1}^{n}\left|a_{i j}\right|^{2} \sum_{j=1}^{n}\left|x_{j}\right|^{2}\right)=\sum_{j=1}^{n}\left|x_{j}\right|^{2} \|\mathbf{A}\|_{F}^{2}=\|\mathbf{A}\|_{F}^{2}\|\mathbf{x}\|_{2}^{2} \]

  • Субмультипликативность: \(\|\mathbf{A}\mathbf{B}\|_{F} \leq\|\mathbf{A}\|_{F}\|\mathbf{B}\|_{F}\), так как

\[ \|\mathbf{A}\mathbf{B}\|_{F}^{2}=\sum_{i, j}\left|\sum_{k} a_{i k} b_{k j}\right|^{2} \leq \sum_{i, j}\left(\sum_{k}\left|a_{i k}\right|\left|b_{k j}\right|\right)^{2} \leq \sum_{i, j}\left(\sum_{k}\left|a_{i k}\right|^{2} \sum_{k}\left|b_{k j}\right|^{2}\right)=\sum_{i, k}\left|a_{i k}\right|^{2} \sum_{k, j}\left|b_{k j}\right|^{2}=\|\mathbf{A}\|_{F}^{2}\|\mathbf{B}\|_{F}^{2} \]

  • \(\|\mathbf{A}\|_{F}^{2}=\operatorname{tr} \mathbf{A}^{*} \mathbf{A}=\operatorname{tr} \mathbf{A} \mathbf{A}^{*}\), где \(\operatorname{tr} \mathbf{A}-\) след матрицы \(\mathbf{A}, \mathbf{A}^{*}\) - эрмитово-сопряжённая матрица.


  • \(\|\mathbf{A}\|_{F}^{2}=\sigma_{1}^{2}+\sigma_{2}^{2}+\cdots+\sigma_{r}^{2}\), где \(\sigma_{1}, \sigma_{2}, \ldots, \sigma_{r}-\) сингулярные числа матрицы \(\mathbf{A} .\)


  • \(\|\mathbf{A}\|_{F} \geq\|\mathbf{A}\|_{2}\), где \(\|\cdot\|_{2}-\) спектральная норма.


  • \(\|\mathbf{A}\|_{F}\) не изменяется при умножении матрицы \(\mathbf{A}\) слева или справа на ортогональные (унитарные) матрицы.


Почему норма Фробениуса классная?

Норма Фробениуса часто используется, потому что невязка многих методов минимизируется по ней (например, метода главных компонент). Норму Фробениуса также часто называют сферической или евклидовой, потому что она имеет простой геометрический смысл - длина вектора, который является суммой векторов - строк или столбцов матрицы. Отсюда также понятно, почему умножение матрицы на ортогональную не меняет её нормы Фробениуса. Соотношения эквивалентности её со спектральной нормой:

\[\begin{split} \begin{aligned} &\|\mathbf{A}\|_{2} \leq\|\mathbf{A}\|_{F} \leq \sqrt{n}\|\mathbf{A}\|_{2} \\ &\frac{1}{\sqrt{n}}\|\mathbf{A}\|_{F} \leq\|\mathbf{A}\|_{2} \leq\|\mathbf{A}\|_{F} \end{aligned} \end{split}\]

Наконец, можем вернуться к оценке погрешности решения СЛАУ.

Содержание