Хабр·Russia·Tuesday, November 3, 2026 at 07:31 AM UTC

Удивительно простое доказательство сингулярного разложения матриц

Translate

master_program24 минуты назад

Начнём с общей схемы доказательства.

Ниже подробно разберём все обозначения, леммы и переходы.

Сингулярное разложение (Singular Value Decomposition, SVD) обычно выводят из спектральной теоремы для симметричной матрицы .

У этого классического пути есть педагогический недостаток: он уводит нас от исходного геометрического смысла отображения в алгебру квадратичных форм и характеристических многочленов. Между тем геометрическое утверждение SVD предельно наглядно и просто:

Для любого линейного отображения $A\colon\mathbb{R}^n\to\mathbb{R}^m$ существует ортонормированный базис во входном пространстве, образы векторов которого попарно ортогональны.

Возникает естественный вопрос: можно ли доказать существование такого базиса напрямую — без собственных значений, без определителей, без спектральной теоремы и без производных?

Оказывается, можно. Для этого достаточно школьной тригонометрии, понятия предела последовательности, матриц и теории про ортонормированные базисы в $\mathbb{R}^n$ .

Главным преимуществом такого подхода является возможность изложить теорию SVD-разложения матриц уже в середине первого семестра вуза, и дальше строить вузовский курс линейной алгебры вокруг нее. Кроме того, статья может помочь лучше разобраться в SVD тем, кто давно хотел это сделать, или открыть для себя какие-то новые геометрические смыслы.

1. Что именно мы ищем

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

Ортонормированный базис.

Базис — это набор векторов, через который любой вектор пространства единственным образом выражается как линейная комбинация.

Базис $q_1,\ldots,q_n$ в $\mathbb{R}^n$ называется ортонормированным, если все его векторы имеют единичную длину и попарно перпендикулярны:

$\langle q_i,q_j\rangle=\begin{cases}1,&i=j,\\0,&i\ne j.\end{cases}$

Слово «ортонормированный» объединяет два условия: «орто» отвечает за взаимную ортогональность, а «нормированный» — за единичные длины.

Любые векторов с этими свойствами в автоматически образуют базис.

Действительно, если их линейная комбинация равна нулю, скалярное умножение на выделяет её коэффициент при и показывает, что он равен нулю. Значит, векторы линейно независимы, а их число равно размерности пространства.

Ортогональная матрица.

Вещественная квадратная матрица размера $n\times n$ называется ортогональной, если

где — транспонированная матрица, а — единичная. Для квадратной матрицы это означает, что обратная матрица совпадает с транспонированной:

$Q^{-1}=Q^T,\qquad QQ^T=I_n.$

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

Почему эти определения связаны.

Запишем векторы в стандартных координатах и поставим их в столбцы матрицы:

$Q=\begin{pmatrix}q_1&q_2&\cdots&q_n\end{pmatrix}.$

По правилу умножения матриц элемент произведения на позиции равен скалярному произведению соответствующих столбцов:

$(Q^TQ)_{ij}=\langle q_i,q_j\rangle.$

Поэтому матрица ортогональна тогда и только тогда, когда её столбцы образуют ортонормированный базис.

Из равенства следует, что её строки тоже образуют ортонормированный базис.

Геометрический смысл.

Ортогональная матрица сохраняет скалярные произведения:

$\langle Qx,Qy\rangle=x^TQ^TQy=x^Ty=\langle x,y\rangle.$

Следовательно, она сохраняет длины и углы между ненулевыми векторами: пространство можно повернуть или отразить, но нельзя растянуть или перекосить. Например,

$Q=\frac{1}{\sqrt{2}}\begin{pmatrix}1&-1\\1&1\end{pmatrix}$

задаёт поворот плоскости на 45 градусов. Её столбцы — единичные взаимно перпендикулярные векторы нового базиса. Ортогональные преобразования могут включать и отражения, поэтому не всякая ортогональная матрица является чистым поворотом.

Связь со сменой координат.

Если — столбец координат вектора в базисе $(q_1,\ldots,q_n)$ , то его координаты равны

$z=Qx=x_1q_1+\cdots+x_nq_n,\qquad x=Q^Tz.$

Здесь геометрический вектор остаётся тем же: меняется способ записать его координаты. Таким образом, искать ортонормированный базис и искать ортогональную матрицу, составленную из его векторов, — две формы одной задачи.

Один и тот же вектор в двух ортонормированных базисах. Меняются координаты и проекции, сам вектор остаётся прежним.

Теперь применим эту связь между базисами и матрицами к самому линейному отображению.

Пусть — фиксированная вещественная матрица размера $m\times n$ , задающая отображение из в $\mathbb{R}^m$ . Здесь участвуют два пространства, и в каждом из них можно независимо выбрать ортонормированный базис.

Соберём векторы входного базиса в столбцы ортогональной матрицы размера , а выходного — в столбцы ортогональной матрицы размера $m\times m$ .

Проследим, как теперь записывается действие .

Если — координаты входного вектора в базисе , то его стандартные координаты равны . Применив отображение, получим .

Чтобы выразить результат в базисе , нужно умножить его на :

Значит, матрица того же отображения в новых базисах имеет вид

Само отображение осталось прежним: мы лишь выбрали, по каким осям измерять входные и выходные векторы. Но от выбора осей зависит, насколько сложной выглядит его матрица.

Самая удобная картина — когда координаты не смешиваются: каждая входная координата умножается на своё неотрицательное число и попадает в соответствующую выходную координату, а некоторые направления могут переходить в ноль. Такой картине соответствует прямоугольная диагональная матрица $\Sigma$ .

Утверждение SVD состоит в том, что подходящие ортонормированные базисы существуют для любой вещественной матрицы.

Именно это мы и будем доказывать. В выбранных базисах должно выполняться

$U^TAV=\Sigma.$

Геометрия SVD для отображения (x, y) ↦ (2x + y, y). Прямое действие A и путь Vᵀ → Σ → U дают одинаковый результат. Цветные стрелки отслеживают e₁ и e₂; σ₁ и σ₂ — длины полуосей эллипса. Матрицы округлены до трёх знаков.

Здесь имеет размер . Её ненулевые диагональные элементы можно расположить в порядке $\sigma_1\ge\sigma_2\ge\cdots\ge\sigma_r>0$ , где $r=\operatorname{rank}A$ ; все остальные элементы равны нулю. Если ранг равен нулю, то и $\Sigma=0$ , а базисы можно выбрать произвольно.

Наконец, умножим равенство слева на , а справа на . Благодаря ортогональности матриц получаем привычную запись сингулярного разложения:

$A = U \Sigma V^T.$

Если домножить это равенство справа на (помня, что для ортогональной матрицы ), условие переписывается в виде:

$A V = U \Sigma.$

Столбцы матрицы $V = (v_1, v_2, \dots, v_n)$ образуют ортонормированный базис в .

Столбцы матрицы $U = (u_1, u_2, \dots, u_m)$ образуют ортонормированный базис в . Равенство $A V = U \Sigma$ по столбцам означает:

$A v_i = \sigma_i u_i \quad (1 \le i \le r), \qquad A v_i = 0 \quad (r < i \le n).$

Столбцы AV — образы входного базиса. Ненулевые образы нормируем и дополняем до ортонормированного базиса выхода; нулевые соответствуют ядру A. Цвет связывает вектор с его образом, а длины полос условны.

Поскольку базис $u_1, \dots, u_m$ ортонормирован, векторы должны быть попарно ортогональны:

$\langle A v_i, A v_j \rangle = 0 \quad \text{при } i \ne j.$

Это сводит всю задачу к геометрически прозрачной и интуитивно понятной цели:

найти во входном пространстве такой ортонормированный базис $(v_1, \dots, v_n)$ , чтобы образы $(A v_1, \dots, A v_n)$ в оказались попарно взаимно перпендикулярны.

Один оператор и два ортонормированных входных базиса. В подходящем базисе V образы взаимно перпендикулярны; их длины дают сингулярные числа, а нормировка — векторы выходного базиса U.

Как только такой базис будет найден, нормировка ненулевых образов сразу даст сингулярные числа $\sigma_i = \|A v_i\|$ и первые столбцов матрицы .

Дополнив их до базиса всего , мы получим искомое разложение.

Окружность, эллипс и ортогональные образы базиса

Геометрия на примере $A=\begin{pmatrix}2&1\\0&1\end{pmatrix}$ .

Единичная окружность переходит в эллипс.

Подходящий ортонормированный базис входа даёт два ортогональных образа — главные полуоси этого эллипса. Их длины и есть сингулярные числа.

2. Двумерная лемма: ортогонализация одной пары вращением

Начнем с элементарного случая: у нас есть всего два ортонормированных вектора $v, w \in \mathbb{R}^n$ . Их образы $A v, A w \in \mathbb{R}^m$ в общем случае, вообще говоря не ортогональны: их скалярное произведение $\langle A v, A w \rangle$ может быть отлично от нуля.

Повернем пару в порождаемой ими плоскости на угол $\theta$ :

$\begin{aligned}v_\theta &= \cos\theta \cdot v + \sin\theta \cdot w, \\w_\theta &= -\sin\theta \cdot v + \cos\theta \cdot w.\end{aligned}$

Легко проверить, что пара $(v_\theta, w_\theta)$ остается ортонормированной и задает ту же плоскость при любом значении .

Вычислим скалярное произведение их образов как функцию угла :

$f(\theta) = \langle A v_\theta, A w_\theta \rangle = \langle \cos\theta \, A v + \sin\theta \, A w, \; -\sin\theta \, A v + \cos\theta \, A w \rangle.$

Раскрывая билинейное скалярное произведение, получаем:

$\begin{aligned}f(\theta) &= -\cos\theta \sin\theta \, \|Av\|^2 + \cos^2\theta \, \langle Av, Aw \rangle - \sin^2\theta \, \langle Av, Aw \rangle + \sin\theta \cos\theta \, \|Aw\|^2 \\&= (\cos^2\theta - \sin^2\theta) \langle Av, Aw \rangle + \sin\theta \cos\theta \left( \|Aw\|^2 - \|Av\|^2 \right).\end{aligned}$

Используя формулы двойного угла $\cos^2\theta - \sin^2\theta = \cos 2\theta$ и $2\sin\theta\cos\theta = \sin 2\theta$ , приходим к виду:

$f(\theta) = \alpha \cos 2\theta + \beta \sin 2\theta,$

где коэффициенты полностью определяются исходной геометрией:

$\alpha = \langle Av, Aw \rangle, \qquad \beta = \frac{\|Aw\|^2 - \|Av\|^2}{2}.$

Наша цель — найти угол , при котором $f(\theta) = 0$ .

Если $\alpha = 0$ и $\beta = 0$ , то $f(\theta) \equiv 0$ для всех . Образы уже ортогональны, и вращение не требуется: можно положить $\theta = 0$ .
Если хотя бы один из коэффициентов отличен от нуля, положим $R = \sqrt{\alpha^2 + \beta^2} > 0$ . Тогда вектор $(\beta/R, \alpha/R)$ лежит на единичной окружности: $(\alpha/R)^2 + (\beta/R)^2 = 1$ . Следовательно, существует вспомогательный угол $\varphi \in [0, 2\pi)$ , такой что:

$\sin\varphi = \frac{\alpha}{R}, \qquad \cos\varphi = \frac{\beta}{R}.$

Подставим это представление в формулу для $f(\theta)$ :

$f(\theta) = R \left( \sin\varphi \cos 2\theta + \cos\varphi \sin 2\theta \right) = R \sin(2\theta + \varphi).$

Теперь зануление функции становится тривиальным. Нам достаточно потребовать того, чтобы аргумент синуса обратился в ноль:

$2\theta_* + \varphi = 0 \implies \theta_* = -\frac{\varphi}{2}.$

При таком угле $\theta_*$ образы повернутых векторов строго ортогональны: $\langle A v_{\theta_*}, A w_{\theta_*} \rangle = 0$ .

Вспомогательный угол $\varphi$ дает универсальное точное решение для любых начальных векторов, включая случай нулевых образов.

Поворот входного базиса для той же матрицы .

В анимации используется угол $\theta_*\approx31{,}717^\circ$ : скалярное произведение образов становится нулевым. Корни уравнения отличаются на $\pi/2$ ; выбор другого корня меняет порядок и знаки векторов, но сохраняет ортогональность.

3. Препятствие в нескольких измерениях: эффект домино

Казалось бы, задача решена: если мы умеем ортогонализовать любую пару векторов, давайте просто перебирать пары по очереди. Возьмем пару , повернем её так, чтобы $\langle Av_1, Av_2 \rangle = 0$ . Затем возьмем и повернем её, добившись $\langle Av_2, Av_3 \rangle = 0$ .

Но здесь нас ждет классическая ловушка линейной алгебры.

Поворачивая пару , мы заменяем вектор на линейную комбинацию:

$v_2' = \cos\theta \, v_2 + \sin\theta \, v_3.$

Что произойдет с уже исправленным скалярным произведением первого и второго векторов?

$\langle A v_1, A v_2' \rangle = \cos\theta \, \underbrace{\langle Av_1, Av_2 \rangle}_{=0} + \sin\theta \, \langle Av_1, Av_3 \rangle = \sin\theta \, \langle Av_1, Av_3 \rangle.$

Если вектор не был ортогонален и $\sin\theta\ne0$ , то новое произведение $\langle Av_1, Av_2' \rangle$ снова станет ненулевым.

Исправляя одну связь, мы можем нарушить соседние. Наивный попарный перебор рискует превратиться в бесконечную погоню за ускользающей ортогональностью. Что же делать?

4. Мера неортогональности и тождество сохранения

Чтобы управлять всем базисом сразу, введем скалярный функционал, измеряющий суммарное отклонение системы от взаимной ортогональности. Для любого ортонормированного базиса $\mathcal{V} = (v_1, \dots, v_n)$ пространства определим:

$\Phi(\mathcal{V}) = \sum_{1 \le i < j \le n} \langle A v_i, A v_j \rangle^2.$

Свойства этой величины:

$\Phi(\mathcal{V}) \ge 0$ , так как это сумма квадратов вещественных чисел.
$\Phi(\mathcal{V}) = 0$ тогда и только тогда, когда $\langle A v_i, A v_j \rangle = 0$ для всех пар . Это именно то, что нам требуется для построения SVD.
Суммирование ведется по строго упорядоченным парам : каждая неупорядоченная пара учитывается ровно один раз.

Что произойдет со значением $\Phi(\mathcal{V})$ , если мы выберем какую-то конкретную пару индексов и повернем только эти два вектора на угол , оставив все остальные базисных вектора нетронутыми?

Разобьем слагаемые в сумме $\Phi$ на три непересекающиеся группы:

Пара : её вклад равен $\langle A v_i, A v_j \rangle^2$ .
Пары, не содержащие ни , ни : для любых $k, l \notin \{i, j\}$ векторы и вообще не менялись, поэтому произведения $\langle A v_k, A v_l \rangle^2$ остаются константами.
Пары, связывающие поворачиваемую пару с третьим вектором: для каждого фиксированного индекса $k \ne i, j$ в сумме присутствуют ровно два слагаемых:

$\langle A v_i, A v_k \rangle^2 + \langle A v_j, A v_k \rangle^2.$

Обозначим для краткости $a_k = \langle A v_i, A v_k \rangle$ и $b_k = \langle A v_j, A v_k \rangle$ , а также $c = \cos\theta$ , $s = \sin\theta$ . После поворота новые векторы имеют вид:

$v'_i = c \, v_i + s \, v_j, \qquad v'_j = -s \, v_i + c \, v_j.$

В силу линейности новые скалярные произведения с неизменным вектором равны:

$\langle A v'_i, A v_k \rangle = c \, a_k + s \, b_k, \qquad \langle A v'_j, A v_k \rangle = -s \, a_k + c \, b_k.$

Сохранение суммы квадратов скалярных произведений

Вспомогательная плоскость скалярных произведений: горизонтальная координата — $a_k=\langle Av_i,Av_k\rangle$ , вертикальная — $b_k=\langle Av_j,Av_k\rangle$ . После поворота входной пары точка остаётся на окружности $a_k^2+b_k^2=\mathrm{const}$ . Это не плоскость векторов в выходном пространстве.

Теперь посчитаем сумму их квадратов:

$\begin{aligned}(c a_k + s b_k)^2 + (-s a_k + c b_k)^2 &= (c^2 a_k^2 + 2cs \, a_k b_k + s^2 b_k^2) + (s^2 a_k^2 - 2cs \, a_k b_k + c^2 b_k^2) \\&= (c^2 + s^2) a_k^2 + (s^2 + c^2) b_k^2 \\&= a_k^2 + b_k^2.\end{aligned}$

Перекрестные члены взаимно уничтожились, а .

Это ключевой момент всего доказательства:

для любого $k\ne i,j$ сохраняется сумма квадратов двух скалярных произведений $\langle Av_i,Av_k\rangle^2+\langle Av_j,Av_k\rangle^2$ — при любом угле поворота.

Анимация инварианта во вспомогательной плоскости

Анимация того же инварианта: два квадрата могут увеличиваться и уменьшаться, а их сумма постоянна. Поэтому связи с третьим вектором перераспределяются, но не мешают уменьшить общий функционал за счёт выбранной пары.

5. Достижение минимума: предельный переход

Итак, мы имеем функционал $\Phi \ge 0$ .

Множество всех ортонормированных базисов в непусто (достаточно взять стандартный базис). Значит, у множества значений $\{\Phi(\mathcal{V})\}$ существует точная нижняя грань (инфимум):

$\mu = \inf_{\mathcal{V}} \Phi(\mathcal{V}) \ge 0.$

Мы хотим показать, что этот инфимум не просто существует как абстрактное число, а фактически достигается на некотором ортонормированном базисе $\mathcal{V}_*$ .

Обычно в курсах анализа здесь говорят: «ортогональная группа компактна, а функция непрерывна, следовательно, по теореме Вейерштрасса минимум достигается».

Чтобы не скрывать суть за топологическими терминами, раскроем этот шаг явно через деление отрезков пополам (как в теореме Больцано — Вейерштрасса).

Строгое доказательство достижения минимума

По определению точной нижней грани для каждого натурального $k = 1, 2, \dots$ мы можем выбрать ортонормированный базис $\mathcal{V}_k = (v_1^{(k)}, \dots, v_n^{(k)})$ , для которого:

$\mu \le \Phi(\mathcal{V}_k) < \mu + \frac{1}{k}.$

Каждый вектор $v_i^{(k)}$ имеет единичную длину в , поэтому каждая из его координат лежит в отрезке . Базис задается набором из $n \times n = n^2$ вещественных чисел.

Возьмем первую координату первого вектора: это числовая последовательность в отрезке . Разделим отрезок пополам. Хотя бы в одной из половин содержится бесконечно много членов последовательности.

Выберем эту половину и продолжим процесс деления. По принципу вложенных отрезков мы выделим подпоследовательность индексов, для которой первая координата сходится к некоторому числу.

Перейдем ко второй координате, просеивая уже выбранную подпоследовательность тем же методом. Поскольку общее число координат конечно (ровно ), мы повторим эту процедуру конечное число раз и получим одну общую подпоследовательность индексов $k_\ell$ , в которой сходятся координаты всех векторов:

$v_i^{(k_\ell)} \xrightarrow{\ell \to \infty} v_i^* \quad \text{для каждого } i = 1, \dots, n.$

Проверим, образуют ли предельные векторы $v_1^*, \dots, v_n^*$ ортонормированный базис. Скалярное произведение является конечной суммой произведений координат, поэтому предельный переход сохраняет скалярные произведения:

$\langle v_i^*, v_j^* \rangle = \lim_{\ell \to \infty} \langle v_i^{(k_\ell)}, v_j^{(k_\ell)} \rangle = \lim_{\ell \to \infty} \delta_{ij} = \delta_{ij},$

где $\delta_{ij} = 1$ при и $\delta_{ij} = 0$ при $i \ne j$ . Предельные векторы ортонормированы, а любой набор из ортонормированных векторов в автоматически является базисом.

Наконец, функционал — многочлен степени не выше четырёх от координат базисных векторов. Поэтому предельный переход совместим с вычислением :

$\Phi(\mathcal{V}_*) = \lim_{\ell \to \infty} \Phi(\mathcal{V}_{k_\ell}) = \mu.$

Минимум действительно достигается: существует конкретный ортонормированный базис $\mathcal{V}_* = (v_1, \dots, v_n)$ , на котором $\Phi(\mathcal{V}_*) = \mu$ .

Заметьте: мы пока не утверждаем, что $\mu = 0$ . Мы лишь доказали, что значение функционала ни на каком другом базисе не может быть строго меньше $\mu$ .

6. Решающий шаг: почему минимум не может быть положительным

Предположим, что абсолютный минимум положителен: $\mu > 0$ .

Раз $\Phi(\mathcal{V}_*) = \mu > 0$ , в сумме квадратов обязан найтись хотя бы один ненулевой член. Значит, существует пара индексов , для которой:

$\gamma = \langle A v_i, A v_j \rangle \ne 0.$

Применим к паре нашу двумерную лемму: найдем угол $\theta_* = -\varphi/2$ , при котором образы повернутых векторов становятся строго ортогональными:

$\langle A v'_i, A v'_j \rangle = 0.$

Сформируем новый базис $\mathcal{V}'$ , заменив в векторы на повернутые , а остальные вектора оставив без изменений. Базис остается ортонормированным.

Что произошло со значением $\Phi(\mathcal{V}')$ ?

Вклады всех пар, не содержащих и , не изменились.
Для каждого сумма вкладов двух пар сохранилась благодаря доказанному ранее тождеству:

$\langle A v'_i, A v_k \rangle^2 + \langle A v'_j, A v_k \rangle^2 = \langle A v_i, A v_k \rangle^2 + \langle A v_j, A v_k \rangle^2.$

Вклад самой пары уменьшился с $\gamma^2$ до 0.

Следовательно, суммарная неортогональность нового базиса равна точно:

$\Phi(\mathcal{V}') = \Phi(\mathcal{V}_*) - \gamma^2 = \mu - \gamma^2.$

Но так как $\gamma \ne 0$ , мы получаем:

$\Phi(\mathcal{V}') < \mu.$

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

Значит:

$\mu = 0.$

А раз минимум равен нулю и достигается на базисе , то:

$\Phi(\mathcal{V}_*) = \sum_{1 \le i < j \le n} \langle A v_i, A v_j \rangle^2 = 0.$

Поскольку все слагаемые неотрицательны, каждое из них обязано быть нулем:

$\langle A v_i, A v_j \rangle = 0 \quad \text{для всех } 1 \le i < j \le n.$

Образы векторов базиса попарно ортогональны.

7. Сборка прямоугольного SVD

Теперь аккуратно соберем итоговые матрицы для любого прямоугольного размера $m \times n$ .

Пусть — найденный ортонормированный базис в , образы которого попарно ортогональны. Некоторые из этих образов могут быть нулевыми (например, если матрица вырождена или ).

1. Упорядочение.

Перенумеруем векторы базиса так, чтобы длины их образов шли по невозрастанию:

$\|A v_1\| \ge \|A v_2\| \ge \dots \ge \|A v_r\| > 0 = \|A v_{r+1}\| = \dots = \|A v_n\|.$

Число ненулевых образов в точности совпадает с размерностью пространства образов $\operatorname{im} A$ , то есть $r = \operatorname{rank} A \le \min(m, n)$ . Если , то , и все образы нулевые. Если , сумма формально не содержит слагаемых и равна нулю сразу.

2. Сингулярные числа.

Положим для каждого $i = 1, \dots, r$ :

$\sigma_i = \|A v_i\| > 0.$

3. Базис выхода.

Определим первые векторов в простой нормировкой:

$u_i = \frac{A v_i}{\sigma_i} \quad (1 \le i \le r).$

Так как образы попарно ортогональны, набор $(u_1, \dots, u_r)$ является ортонормированным в . Дополним его любым стандартным способом (например, процессом Грама — Шмидта) до полного ортонормированного базиса $(u_1, \dots, u_m)$ пространства . Заметим: если , мы ни в коем случае не пытаемся строить векторы для индексов больше ; выходное пространство строго -мерно.

4. Матричная запись.

Составим матрицы:

$V = \begin{pmatrix} v_1 & v_2 & \dots & v_n \end{pmatrix} \in \mathbb{R}^{n \times n}, \qquad U = \begin{pmatrix} u_1 & u_2 & \dots & u_m \end{pmatrix} \in \mathbb{R}^{m \times m}.$

Обе матрицы составлены из ортонормированных базисов, поэтому они ортогональны: , . Обратите внимание: матрицы могут иметь определитель −1 (содержать отражение), требование быть «чистыми» вращениями на них не накладывается.

Определим матрицу размера : на позициях при $1 \le i \le r$ запишем числа $\sigma_i$ , а все остальные её элементы положим равными нулю.

Проверим произведение : его -й столбец равен . При $i \le r$ имеем $A v_i = \sigma_i u_i$ , а при имеем . Но именно такие столбцы дает произведение $U \Sigma$ . Следовательно:

Умножая справа на и учитывая, что , получаем:

Сингулярное разложение построено.

8. Исторический контекст и связь с вычислениями

Идея использовать функционал суммы квадратов неортогональности восходит к классическому методу вращений Якоби для диагонализации симметричных матриц.

В 1981 году математик Герберт Уилф (Herbert S. Wilf) опубликовал короткую двухстраничную заметку, в которой предложил доказывать спектральную теорему для симметричных матриц именно через глобальный минимум суммы квадратов внедиагональных элементов.

Связь этого доказательства с подходом Уилфа видна, если рассмотреть матрицу Грама системы векторов :

Ее элементы — в точности скалярные произведения $g_{ij} = \langle A v_i, A v_j \rangle$ . Внедиагональная сумма квадратов матрицы равна:

$\operatorname{Od}(G) = \sum_{i \ne j} g_{ij}^2 = 2 \sum_{1 \le i < j \le n} \langle A v_i, A v_j \rangle^2 = 2 \Phi(\mathcal{V}).$

Уилф минимизировал $\operatorname{Od}(G)$ для произвольной симметричной матрицы. Мы же применили эту логику непосредственно к исходному отображению , даже не формируя матрицу и не требуя предварительного знания спектральной теории.

С этим рассуждением связан практический численный алгоритм — односторонний метод Якоби для SVD (one-sided Jacobi SVD). В нём последовательно ортогонализуют пары столбцов матрицы , накапливая вращения в . На практике итерации останавливают, когда скалярные произведения столбцов становятся достаточно малы относительно их норм.

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

Например, документация LAPACK для DGESVJ отдельно оговаривает условия точности и критерий остановки [3].

Пример на Python

import numpy as np

A = np.array([[2.0, 1.0], [0.0, 1.0]])
x, y = A[:, 0], A[:, 1]
aa, bb = x @ x, y @ y
gamma = x @ y

# Выбираем один из корней уравнения <Av, Aw> = 0.
theta = 0.5 * np.arctan2(2.0 * gamma, aa - bb)
c, s = np.cos(theta), np.sin(theta)
V = np.array([[c, -s], [s, c]])
B = A @ V
sigma = np.linalg.norm(B, axis=0)
U = B / sigma  # В этом примере обе нормы ненулевые.

assert np.allclose(V.T @ V, np.eye(2), atol=1e-12)
assert np.isclose(B[:, 0] @ B[:, 1], 0.0, atol=1e-12)
assert np.isclose(np.linalg.norm(B, "fro"), np.linalg.norm(A, "fro"))
assert np.allclose(U.T @ U, np.eye(2), atol=1e-12)
assert np.allclose(A, U @ np.diag(sigma) @ V.T, atol=1e-12)

print(f"Угол: {np.degrees(theta):.6f} градусов")
print("Сингулярные числа:", np.round(sigma, 6))

Результат:

Угол: 31.717474 градусов
Сингулярные числа: [2.288246 0.874032]

Проверки подтверждают ортонормированность базисов, ортогональность образов, сохранение нормы Фробениуса и восстановление исходной матрицы.

Схема доказательства одним предложением

Существование минимизирующего базиса $\implies$ инвариантность суммы квадратов скалярных произведений с третьими векторами при повороте пары строгое уменьшение на при предположении попарная ортогональность образов нормировка и получение $A = U \Sigma V^T$ .

Источники

Herbert S. Wilf. An Algorithm-Inspired Proof of the Spectral Theorem in . The American Mathematical Monthly, Vol. 88, No. 1 (1981), pp. 49–50. (PDF на странице автора)
Robert van de Geijn, Margaret Myers. Advanced Linear Algebra: Foundations to Frontiers. §11.3.3, Jacobi’s method for computing the Singular Value Decomposition. (Материалы курса)
LAPACK. Документация DGESVJ: односторонний метод Якоби, условия относительной точности и критерий остановки. (Описание процедуры)

Если эта публикация вас вдохновила и вы хотите поддержать автора — не стесняйтесь нажать на кнопку

View the original on Хабр →

KioskNews shows a cleaned-up reading view extracted from the publisher’s page — the original always lives on their site, not ours.