В задаче QR разложения докажи что вектор b_i (полч...

Ниже приведена стандартная идея доказательства того, что на каждом шаге ортогонализации Грама–Шмидта очередной вектор $b_i$ (до нормировки) не вырождается в ноль и, следовательно, имеет строго положительную норму.

---

Постановка задачи

Пусть дан набор линейно независимых векторов

$$a_1,\; a_2,\; \dots,\; a_n \in \mathbb{R}^m$$

(или из любого другого векторного пространства над полем $\mathbb{R}$, где определено скалярное произведение).

Последовательность векторов $\{b_i\}$ в классическом методе Грама–Шмидта строится по формулам:

1. Начинаем с

   $$b_1 \;=\; a_1.$$

2. На $k$-м шаге (при $k \ge 2$) «вычитаем проекции» $a_k$ на уже построенные векторы $b_1,\dots,b_{k-1}$:

   $$b_k \;=\; a_k \;-\; \sum_{j=1}^{k-1} \frac{\langle b_j,\;a_k\rangle}{\langle b_j,\;b_j\rangle}\;b_j.$$

   Здесь $\langle \cdot,\cdot\rangle$ — скалярное произведение (евклидово в $\mathbb{R}^m$).

Затем в классической QR-факторизации вектор $q_k$ получается нормировкой $b_k$:

$$q_k \;=\; \frac{b_k}{\|b_k\|}.$$

Для того чтобы $\|q_k\|$ было определено, необходимо $\|b_k\|\neq 0$. Поэтому важно показать, что $b_k \neq 0$, то есть $\|b_k\|>0$ на каждом шаге.

---

Идея доказательства

1. Линейная независимость исходных векторов.

   По условию задачи векторы $a_1,\dots,a_n$ — линейно независимы. Это означает, что если

   $$\alpha_1 a_1 + \cdots + \alpha_n a_n = 0$$

   (нулевой вектор), то все $\alpha_i = 0$.

2. Если $b_k = 0$, тогда $a_k$ выражается через предыдущие векторы $a_1,\dots,a_{k-1}$.

   Предположим, что на $k$-м шаге (где $1 < k \leq n$) получилось $b_k = 0$. Из определения:

   $$b_k \;=\; a_k - \sum_{j=1}^{k-1} \frac{\langle b_j,\;a_k\rangle}{\langle b_j,\;b_j\rangle}\;b_j \;=\; 0.$$

   Это означает

   $$a_k \;=\; \sum_{j=1}^{k-1} \frac{\langle b_j,\;a_k\rangle}{\langle b_j,\;b_j\rangle}\;b_j.$$

   Но каждый $b_j$ сам является линейной комбинацией $a_1,\dots,a_j$ (по построению на предыдущих шагах). Следовательно, $a_k$ оказался линейной комбинацией $a_1, a_2, \dots, a_{k-1}$.

   Однако по условию $a_1,\dots,a_k$ — линейно независимы. Прийти к тому, что $a_k$ выражается через предыдущие $a_1,\dots,a_{k-1}$, значит противоречить этой независимости.

3. Вывод: $b_k \neq 0$.

   Поскольку предположение $b_k = 0$ привело к противоречию, заключаем, что на самом деле $b_k \neq 0$. А значит, $\|b_k\|>0$ (его норма строго положительна).

4. Нормировка и $q_k$.

   Таким образом, вектор $q_k = \tfrac{b_k}{\|b_k\|}$ корректно определён, и метод Грама–Шмидта завершается без вырождения на каждом шаге.

---

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

Если бы на $k$-м шаге алгоритма Грама–Шмидта возник нулевой вектор $b_k$, это означало бы, что $a_k$ является линейной комбинацией предыдущих векторов $a_1,\dots,a_{k-1}$, что противоречит линейной независимости исходного набора.

---

Итог: Поскольку $b_k \neq 0$ для всех $k$, векторы $b_i$ имеют строго положительную норму и, следовательно, в методе Грама–Шмидта всегда можно корректно перейти к ортонормированным векторам $q_i = \tfrac{b_i}{\|b_i\|}$.

Ниже кратко изложено, в каких обстоятельствах при построении преобразования Хаусхолдера может получиться вектор $u^* = 0$ и что это означает с геометрической точки зрения.

---

Что такое $u^*$ в преобразовании Хаусхолдера

Пусть мы хотим «отразить» (преобразовать) вектор $x \in \mathbb{R}^n$ так, чтобы он стал параллелен базисному вектору $e_1 = (1,0,\dots,0)^T$. Обычно выбирают

$$u^* \;=\; x \;\pm\; \|x\|_2 \, e_1.$$

Затем задают

$$u \;=\; \frac{u^*}{\|u^*\|_2},$$

после чего строят матрицу Хаусхолдера

$$P = I \;-\; 2\,u\,u^T.$$

Это отражение в гиперплоскости, задаваемой ортогонально вектору $u$, и оно переводит $x$ в $\pm \|x\|_2\, e_1$.

---

Как может получиться $u^* = 0$

1. Рассмотрим формулу

   $$u^* = x \;\pm\; \|x\|_2 \, e_1.$$

2. Случай $x = \mp\,\|x\|_2 \, e_1$.
   Предположим, что $x$ уже совпадает по направлению (но не обязательно по знаку) с базисным вектором $e_1$. Тогда:

   $$x = \alpha e_1, \quad \text{где } \alpha = \pm\,\|x\|_2.$$
   • Если мы выберем знак в формуле для $u^*$ так, что $\alpha = \mp\|x\|_2$, то есть «минус» там, где уже стоит «плюс», или наоборот, — то в скобках может возникнуть взаимная компенсация.
   • Конкретнее, если $x = -\|x\|_2\, e_1$ и мы поставим «$+$» в формуле $x + \|x\|_2 e_1$, то получим: $$u^* \;=\; \bigl(-\|x\|_2\, e_1\bigr) \;+\; \|x\|_2\, e_1 \;=\; 0.$$

   Аналогично, если $x = +\|x\|_2\, e_1$ и мы выберем «$-$» в формуле.

Таким образом, главная причина, почему $u^* = 0$ может получиться, — это когда исходный вектор $x$ уже «лежит» на прямой, заданной $e_1$, и мы берём неподходящий знак в $\pm$.

---

Геометрический смысл $u^* = 0$

1. Отсутствие необходимости «отражать».
   Если $x$ уже параллелен $e_1$ и мы выбираем именно тот знак, который полностью компенсирует $x$ добавлением/вычитанием $\|x\|_2\, e_1$, это означает, что мы «пытались» построить отражение, которое… не нужно.
   Геометрически это означает, что преобразование Хаусхолдера, предназначенное «сдвинуть» $x$ на ось, фактически вырождается в тождественное отображение (или не определено через данную формулу, так как нормировать нулевой вектор невозможно).

2. Отражение, которое превращается в тождественную матрицу.
   Если $u^* = 0$, мы не сможем построить нужный $u = u^*/\|u^*\|$. Формально «матрица Хаусхолдера» $P = I - 2 \frac{u^* (u^*)^T}{\|u^*\|^2}$ перестаёт иметь смысл, так как знаменатель равен нулю. Но в таком случае нам вообще и не нужно никакое отражение: вектор $x$ уже там, где мы хотели его получить (на оси, задаваемой $e_1$). Говоря проще, отражение «не нужно», и естественным преобразованием для «уже нужного» вектора является просто тождественное.

---

Коротко

• Когда $x$ направлен вдоль $e_1$, аккуратный выбор знака «$+$» или «$-$» способен привести к тому, что $x \pm \|x\|_2\, e_1$ окажется нулевым.
• Геометрически это значит, что «строим» отражение там, где отражать нечего, поэтому конструкция вырождается: $u^* = 0$ и матрица Хаусхолдера сводится к тождеству (или, точнее, в общем виде не определяется через указанную формулу).

Таким образом, $u^*=0$ указывает на то, что вектор $x$ уже лежит по направлению (или строго противоположен направлению) выбранного эталонного вектора $e_1$, и никакого «реального» отражения в данном шаге фактически не требуется.

Ниже изложена стандартная схема (и идея её доказательства) того, что, если матрица $A$ имеет размер $5\times 4$ и мы последовательно строим четыре преобразования Хаусхолдера $P_1,\dots,P_4$ (каждое из них размера $5\times 5$), то в конечном итоге получается разложение вида

$$A \;=\; \underbrace{P_1^T\,P_2^T\,P_3^T\,P_4^T}_{Q^*}\;\underbrace{R^*}_{5\times 4},$$

где:

1. Матрица $R^*$ является «почти верхнетреугольной» $5\times 4$-матрицей (точнее, её верхние $4\times 4$ элементы образуют верхнетреугольную матрицу, а пятая строка может содержать нули или какие-то элементы в последнем столбце — зависит от шага построения).
2. Матрица $P_i$ — это отражение Хаусхолдера (ортогональная матрица, причём $P_i^T = P_i$).

Обычно для получения «стандартного» $QR$-разложения размером $5\times 4$ (то есть где $Q$ имеет размер $5\times 4$, а $R$ — $4\times 4$), делают так:

• Берут первые четыре столбца из произведения $P_1^T\,P_2^T\,P_3^T\,P_4^T$ (которые сами по себе дают матрицу размера $5\times 4$) и называют её $Q$.
• Берут первые четыре строки из $R^*$ (это будет $\underbrace{4\times 4}_{R}$-подматрица сверху) и называют её $R$.

Нужно показать, что тогда

$$P_1^T\,P_2^T\,P_3^T\,P_4^T\;R^* \;=\; Q\,R.$$

Именно это равенство означает, что если мы «урежем» справа произведение $P_1^T P_2^T P_3^T P_4^T$ до первых четырёх столбцов (т. е. возьмём $Q$) и «урежем» сверху $R^*$ до первых четырёх строк (т. е. возьмём $R$), то их произведение даёт тот же результат, что и умножение полноразмерных $Q^*\cdot R^*$. Ниже — основной контур этого доказательства.

---

Шаг 1. Итоговое произведение после четырёх отражений

1. На каждом шаге отражения Хаусхолдера (скажем, $P_1$, затем $P_2$, и т. д.) умножаются слева на текущую матрицу:

   $$P_1 A = A^{(1)}, \quad P_2 A^{(1)} = A^{(2)}, \quad P_3 A^{(2)} = A^{(3)}, \quad P_4 A^{(3)} = A^{(4)},$$

   причём $A^{(4)}$ и есть та самая «почти верхнетреугольная» матрица, которую мы обозначаем за $R^*$.
   Тогда ясно, что

   $$A^{(4)} \;=\; P_4\,P_3\,P_2\,P_1\,A \;=\; R^*.$$

   Отсюда перепишем $A$ «справа»:

   $$A \;=\; (P_1^T\,P_2^T\,P_3^T\,P_4^T)\;R^*.$$

   Обозначим для удобства

   $$Q^* \;=\; P_1^T\,P_2^T\,P_3^T\,P_4^T.$$

   Тогда $A = Q^*\;R^*$.

2. Каждая матрица $P_i$ ортогональна (так как это отражение Хаусхолдера), следовательно $P_i^T = P_i^{-1} = P_i$. Поэтому и $Q^*$ ортогональна, но полная размерность её — $5\times 5$.

---

Шаг 2. Как выделяются нужные блоки $Q$ и $R$

• Матрица $Q$. Берём первые четыре столбца из $Q^*$ (то есть выбрасываем последний, 5-й столбец). Поскольку $Q^*$ — $5\times 5$-матрица, результат будет $5\times 4$-матрица, что и нужно для искомого $Q$.

• Матрица $R$. Берём первые четыре строки из $R^*$. Так как $R^*$ — $5\times 4$-матрица, её верхние четыре строки образуют матрицу $4\times 4$, что и есть искомое $R$.

То есть:

$$Q \;=\; Q^*\Big|_{\text{(взять первые 4 столбца)}}, \quad R \;=\; R^*\Big|_{\text{(взять первые 4 строки)}}.$$

Говоря формально,

$$Q^* \;=\; \bigl[ \,Q\;\;\bigl|\bigr.\;\;q_5 \bigr], \quad R^* \;=\; \begin{bmatrix} R \\[6pt] r_5^T \end{bmatrix},$$

где $q_5$ — 5-й столбец $Q^*$, а $r_5^T$ — 5-я строка $R^*$.

---

Шаг 3. Доказательство равенства $Q^*\,R^* = Q\,R$

Рассмотрим покомпонентно произведение

$$Q^*\,R^* \;=\; \bigl[ \,Q\;\;\bigl|\bigr.\;\;q_5 \bigr] \; \begin{bmatrix} R \\[3pt] r_5^T \end{bmatrix} .$$

Умножение блоков здесь даёт:

$$Q^*\,R^* \;=\; Q \cdot R \;+\; q_5 \cdot r_5^T.$$

Нужно показать, что второй блок $q_5 \cdot r_5^T$ на самом деле даёт вклад, который «зануляется» именно в тех местах, где могла бы быть разница (по сути, нижние строки и/или правые столбцы).

В классическом пошаговом построении $R^*$ (четырьмя отражениями) к моменту применения четвёртого отражения у нас уже обнулены нужные «поддиагональные» элементы, поэтому вектор $r_5$ либо является нулевым (если мы реально получили строго верхнетреугольную матрицу 5×4), либо таков, что при умножении $q_5 \cdot r_5^T$ эти «лишние» элементы не влияют на первые 4 строки и 4 столбца результирующего произведения.

Другими словами, в стандартном алгоритме Хаусхолдера после последнего шага «хвостовые» элементы (в пятой строке и за пределами первых 4 столбцов) уже не затрагивают блок $1\ldots4,1\ldots4$, и в итоге

$$Q^*\,R^* \;=\; Q\,R \quad \text{(если смотреть на первые 4 строки и 4 столбца)}.$$

С учётом же полной размерности получается именно равенство матриц $5\times 4$ (правая часть есть произведение $5\times 4$).

Коротко: при умножении «лишний» пятый столбец $q_5$ и пятая строка $r_5^T$ даёт нулевой вклад там, где формируется «блок» размера $5\times 4$. Именно поэтому можно свободно заменить $Q^*\to Q$ (урезая один столбец) и $R^*\to R$ (урезая одну строку), сохранив то же произведение.

---

Итог: $P_1^T P_2^T P_3^T P_4^T R^* = Q\,R$

Таким образом, мы получили, что

1. $Q$ есть первые 4 столбца ортогональной матрицы $Q^* = P_1^T P_2^T P_3^T P_4^T$, т. е. $\dim(Q)=5\times 4$.
2. $R$ есть первые 4 строки $R^*$, т. е. $\dim(R)=4\times 4$.
3. Произведение $(P_1^T P_2^T P_3^T P_4^T)\;R^*$ в точности совпадает с $Q\,R$.

Фактически это и говорит, что

$$A \;=\; Q^* R^* \;=\; Q\,R$$

и есть искомое $QR$-разложение размера $5\times 4$.

Ниже сформулировано и доказано классическое утверждение о том, что QR-разложение матрицы $A$ (при некоторых стандартных соглашениях, например, о знаках диагональных элементов $R$) однозначно. Для упрощения будем рассматривать случай, когда $A$ имеет полный столбцовый ранг и размер $m\times n$ ($m\ge n$).

---

Утверждение (единственность QR-разложения)

Пусть матрица $A\in \mathbb{R}^{m\times n}$ имеет полный столбцовый ранг, то есть $\text{rank}(A)=n$. Предположим, что существуют два разложения:

$$A \;=\; Q R \quad\text{и}\quad A \;=\; \widetilde{Q}\,\widetilde{R},$$

где

• $Q, \widetilde{Q}\in \mathbb{R}^{m\times n}$ — матрицы с ортонормированными столбцами (то есть $Q^T Q = \widetilde{Q}^T \widetilde{Q} = I_n$),
• $R, \widetilde{R}\in \mathbb{R}^{n\times n}$ — верхнетреугольные матрицы (при классической формулировке QR-разложения).

Тогда, если мы дополнительно наложим требование, что диагональные элементы $R$ и $\widetilde{R}$ положительны (или, по крайней мере, неотрицательны) по диагонали, получаем, что

$$Q = \widetilde{Q} \quad\text{и}\quad R = \widetilde{R}.$$

В частности, это показывает единственность разложения (при фиксированном выборе знаков или неотрицательности на диагонали $R$).

Без условия о знаках (или неотрицательности) диагональных элементов в $R$ возникает двусмысленность в виде диагональных матриц $\pm 1$ (см. ниже).

---

Ключевая идея доказательства

Пусть мы имеем два разложения одной и той же матрицы $A$:

$$A = Q\,R \quad\text{и}\quad A = \widetilde{Q}\,\widetilde{R}.$$

Тогда

$$Q\,R = \widetilde{Q}\,\widetilde{R}.$$

Шаг 1. Домножим слева или справа

1. Домножаем слева на $Q^T$.
   Получим

   $$Q^T \bigl(Q\,R\bigr) \;=\; Q^T \bigl(\widetilde{Q}\,\widetilde{R}\bigr).$$

   Так как $Q^T Q = I_n$, то левая часть упрощается:

   $$I_n \, R = Q^T \,\widetilde{Q}\,\widetilde{R}.$$

   Итак,

   $$R = Q^T\,\widetilde{Q}\,\widetilde{R}. \tag{1}$$

2. Аналогично, можно домножить справа на $\widetilde{R}^{-1}$ (эта матрица обратима, поскольку $\widetilde{R}$ верхнетреугольна с ненулевой диагональю — полный столбцовый ранг $A$ исключает нулевые диагональные элементы). Тогда

   $$Q\,R\,\widetilde{R}^{-1} \;=\; \widetilde{Q}.$$

   Итак,

   $$\widetilde{Q} \;=\; Q\; \bigl(R\,\widetilde{R}^{-1}\bigr). \tag{2}$$

Шаг 2. Рассмотрим матрицу $Q^T \widetilde{Q}$

Из (2) видно, что

$$\widetilde{Q} \;=\; Q\,M, \quad \text{где } M = R\,\widetilde{R}^{-1}.$$

Тогда

$$Q^T \widetilde{Q} \;=\; Q^T (Q\,M) \;=\; (Q^T Q)\;M \;=\; I_n\,M \;=\; M.$$

Отсюда:

$$Q^T \widetilde{Q} = M \quad\text{и}\quad M = R \,\widetilde{R}^{-1}.$$

Но $Q^T \widetilde{Q}$ — это $\;n\times n$-матрица, являющаяся ортогональной, так как $Q$ и $\widetilde{Q}$ имеют ортонормированные столбцы. Значит,

$$M = Q^T \widetilde{Q} \quad \text{есть ортогональная} \quad (M^T M = I_n).$$

Шаг 3. $M = R\,\widetilde{R}^{-1}$ и «верхняя треугольность»

Одновременно из (1) имеем:

$$R \;=\; \bigl(Q^T\widetilde{Q}\bigr)\,\widetilde{R} \;=\; M\,\widetilde{R}.$$

Но $R$ и $\widetilde{R}$ — обе верхние треугольные. Тогда и $M = R\,\widetilde{R}^{-1}$ (или $\widetilde{R}^{-1} R$) автоматически должна быть верхнетреугольной и ортогональной.

Ортогональная верхнетреугольная матрица

Матрица $M$, будучи одновременно верхней треугольной и ортогональной, непременно должна быть диагональной. Действительно, рассмотрим любую нетривиальную верхнетреугольную матрицу $M$. Если она ещё ортогональна, то все внедиагональные элементы должны обращаться в ноль. Иначе не соблюдалась бы норма столбцов/строк.

Значит,

$$M \;=\; \begin{bmatrix} d_1 & 0 & \cdots & 0 \\ 0 & d_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & d_n \end{bmatrix},$$

и каждая $d_i = \pm 1$, так как для ортогональной диагональной матрицы длина каждого столбца должна быть 1, следовательно $|d_i|=1$.

Шаг 4. Связь со знаками на диагонали $R$

Таким образом, мы находим

$$R \;=\; M \,\widetilde{R} \;=\; D \,\widetilde{R}, \quad \text{где } D=\mathrm{diag}(\pm 1,\dots,\pm 1).$$

Аналогично, из $\widetilde{Q} = Q\,M$ получаем

$$\widetilde{Q} \;=\; Q\,D.$$

Отсюда и следует, что без дополнительного условия (например, «диагональные элементы $R$ неотрицательны») QR-разложение определено с точностью до знаков $\pm 1$ на диагонали. То есть:

$$Q\,R = (Q\,D)\,(D^{-1}R).$$

Но если мы оговариваем (как это принято в большинстве реализаций), что диагональные элементы матрицы $R$ строго положительны (или неотрицательны), то матрица $D$ вынужденно становится единичной (так как переключение знака на диагонали противоречило бы условию на $R$). В этом случае

$$D = I_n, \quad \text{откуда} \quad \widetilde{Q} = Q,\;\;\widetilde{R} = R.$$

Итак, при выбранном соглашении о знаке диагонали факторизация $QR$ единственна.

---

Итог

1. В общем случае (без соглашений о знаке диагонали $R$) QR-разложение определяется с точностью до умножения $Q$ справа на диагональную матрицу $D=\mathrm{diag}(\pm1,\dots,\pm1)$ и, соответственно, умножения $R$ слева на $D^{-1}$.
2. Если дополнительно потребовать (как обычно делают), чтобы диагональные элементы $R$ были положительны (или неотрицательны), то такая двусмысленность исчезает — матрица $D$ должна быть единичной, и тем самым $QR$-разложение становится единственным.