Ортогональные проекции и QR-разложение: Грам—Шмидт на пальцах

Задача: точка $(3,4)$ и прямая $y=\frac{1}{2}x$. Какая точка прямой ближе всего к нашей? Ответить «опустить перпендикуляр» легко, а вот посчитать координаты — уже техника. Та же задача в трёх измерениях и с плоскостью, в шести и с подпространством данных — вопрос прогноза в машинном обучении или позиционирования по сигналам спутников. Инструмент один: ортогональная проекция, а её массовое производство — процесс Грама—Шмидта и QR-разложение. Здесь разберём всё по порядку, с числами, которые можно проверить в уме.

Проекция на вектор: формула и смысл#

Начнём с одного направления. Пусть вектор $\vec{b}\ne \vec{0}$ задаёт прямую, и мы хотим «тень» вектора $\vec{a}$ на неё. Тень — это часть $\vec{a}$, сонаправленная с $\vec{b}$, а её длина достаётся из скалярного произведения: числовой коэффициент подбирается так, чтобы остаток стал перпендикулярен $\vec{b}$.

Внимание к типу: дробь $\frac{(\vec{a},\vec{b})}{(\vec{b},\vec{b})}$ — число, и умножается оно на $\vec{b}$. Разность $\vec{a}-{\text{пр}}_{\vec{b}}\vec{a}$ называют ортогональной составляющей: она падает на $\vec{b}$ с нулевым скалярным произведением. Вместе пара раскладывает вектор на два перпендикулярных слагаемых — теорема Пифагора превращает это в тождество $|\vec{a}{|}^2=|\text{пр}{|}^2+|\text{перп}{|}^2$.

Считаем на нашей задаче: $\vec{a}=(3,4)$, направление прямой — $\vec{b}=(2,1)$. Скалярные произведения: $(\vec{a},\vec{b})=6+4=10$, $(\vec{b},\vec{b})=5$, коэффициент $2$. Проекция: $2\vec{b}=(4,2)$. Ортогональная составляющая: $(3,4)-(4,2)=(-1,2)$, и проверка мгновенная: $(-1,2)\cdot (2,1)=-2+2=0$ — перпендикуляр. Пифагор тоже сходится: $|\vec{a}{|}^2=25$, при этом $|(4,2){|}^2=20$ и $|(-1,2){|}^2=5$.

Проекция на подпространство#

Прямая — частный случай. Общая постановка: дано подпространство $U$ (прямая, плоскость, столбцы матрицы) и вектор $\vec{a}$ снаружи. Проекцией на $U$ называется вектор $\vec{p}\in U$, для которого невязка $\vec{a}-\vec{p}$ ортогональна всем векторам из $U$. Геометрия тут железная: кратчайшее расстояние до плоскости достигается по перпендикуляру, поэтому $\vec{p}$ — одновременно и ближайшая точка $U$.

Считать проекцию легко, когда у $U$ есть ортонормированный базис ${\vec{e}}_1,\dots ,{\vec{e}}_k$ — тогда она распадается на сумму независимых теней:

Пример в ${\mathbb{R}}^3$: плоскость $U$ натянута на ${\vec{u}}_1=\frac{1}{\sqrt{2}}(1,1,0)$ и ${\vec{u}}_2=\frac{1}{\sqrt{2}}(1,-1,0)$ — базис ортонормированный, в чём убеждает пара проверок скалярных произведений. Для $\vec{a}=(2,0,1)$: $(\vec{a},{\vec{u}}_1)=\sqrt{2}$, $(\vec{a},{\vec{u}}_2)=\sqrt{2}$. Проекция $\sqrt{2}{\vec{u}}_1+\sqrt{2}{\vec{u}}_2=(1,1,0)+(1,-1,0)=(2,0,0)$. Невязка $(0,0,1)$ — третьи компоненты базисных векторов нулевые, перпендикулярность видна сразу. Расстояние от $\vec{a}$ до плоскости — длина невязки, ровно $1$.

Осталась проблема: базис подпространства приходит из задач косым. Процесс Грама—Шмидта превращает его в ортонормированный за один проход: каждый следующий вектор очищается от проекций на уже готовые направления, затем нормируется.

Ловушка процесса в формулировке: вычитать проекции нужно на готовые ортонормированные ${\vec{e}}_j$, а не на исходные ${\vec{a}}_j$. Классическая ошибка на контрольной — вычесть тень на сырой вектор и получить направление с перекосом. Свойства ортогональных наборов и полнота системы разобраны в уроке про евклидовы пространства; там же — неравенство Коши—Буняковского, на котором стоит минимальность проекции.

Кстати, что делать, если ортонормированного базиса подпространства под рукой нет, а проекцию считать надо? Два пути. Первый — прогнать Грама—Шмидта по столбцам матрицы и вернуться к формуле с суммой скалярных произведений. Второй — составить систему из условий перпендикулярности невязки каждому столбцу: она даёт уравнения ровно на столько коэффициентов, сколько столбцов, и решается знакомым Гауссом. Оба пути приводят к одному и тому же вектору; второй способ встретится нам ещё раз в следующем уроке под именем нормальных уравнений.

QR-разложение: что это и зачем#

Кстати, что делать, если ортонормированного базиса под рукой нет, а проекцию считать надо? Два пути. Первый — прогнать Грама—Шмидта по столбцам матрицы и вернуться к формуле с суммой скалярных произведений. Второй — составить систему A^{ op}ec{c} = A^{ op}ec{a} на коэффициенты разложения ec{p} = ec{a}_1 c_1 + ec{a}_2 c_2: условия перпендикулярности невязки обоим столбцам дают ровно столько уравнений, сколько нужно. Оба пути ведут к одному вектору; второй нам ещё встретится в нормальных уравнениях МНК — это буквально они, только другими словами.

Упакуем Грама—Шмидта в матричную форму. Пусть столбцы матрицы $A$ — линейно независимые векторы ${\vec{a}}_1,\dots ,{\vec{a}}_n$. Грам—Шмидт выдаёт ортонормированные ${\vec{e}}_1,\dots ,{\vec{e}}_n$, и если записать их столбцами в матрицу $Q$, то каждый исходный вектор разлагается по ним с коэффициентами, которые собираются в верхнетреугольную матрицу $R$:

Диагональ $R$ — ненулевая: это длины промежуточных векторов $|{\vec{b}}_k|$, и нулей там быть не может при независимых столбцах. Разложение единственно (при положительной диагонали $R$), а вычисляется оно одной строкой: $R=Q^{\top }A$, потому что $Q^{\top }=Q^{-1}$ для ортогональной матрицы. Проверим всё на числах: возьмём ${\vec{a}}_1=(2,1)$, ${\vec{a}}_2=(1,2)$.

Зачем это всё численщикам — три причины, каждая стоит целой главы в учебниках по вычислительной линейной алгебре. Первая: ортогональные матрицы не растягивают векторы, $|Q\vec{x}|=|\vec{x}|$, поэтому ошибки округления не раздувается при проходе алгоритма — решение систем через $QR$ устойчивее «лобового» Гаусса на плохих матрицах. Вторая: система $A\vec{x}=\vec{b}$ распадается на $R\vec{x}=Q^{\top }\vec{b}$, а треугольная система решается обратным ходом без единого преобразования строк. Третья: итерации $A\to RQ$ — это QR-алгоритм, промышленный способ добывать собственные значения: сохраняя собственные значения, он сам собой приводит матрицу к треугольному виду, где они лежат на диагонали.

Ошибки, которые дорого стоят#

• Вычесть в Граме—Шмидте проекцию на исходный ${\vec{a}}_1$ вместо нормированного ${\vec{e}}_1$: коэффициент окажется не тем, базис выйдет косым, QR не сойдётся.
• Забыть нормировку и записать в $Q$ просто ${\vec{b}}_j$: столбцы ортогональны, но не единичной длины, $Q^{\top }Q\ne E$, и формула $R=Q^{\top }A$ ломается.
• Перепутать тип результата: проекция — вектор, а $\frac{(\vec{a},\vec{b})}{|\vec{b}|}$ — число (длина тени в единицах $\vec{b}$). В ответе задач про расстояние нужен вектор или длина невязки, а не коэффициент.
• Делить на $(\vec{b},\vec{b})$, когда требуется $|\vec{b}|$: у формул проекции и «числового» проектирования знаменатели разные — сверяйте размерность.

Техническая база урока: умножение матриц и транспонирование для работы с $Q^{\top }$, определители для контроля независимости столбцов. Пересчёт между базисами, в том числе ортонормированным, — в уроке о матрице перехода; сводка формул — в шпаргалке по векторной алгебре.

Дальше по курсу: ортогональность немедленно превращается в метод — МНК и нормальные уравнения решают задачу подгонки прямой именно проекцией на пространство столбцов. Назад, к алгебре смены базиса, ведёт урок о матрице перехода.