Алгебра · объяснение и практика

Как ортогонализовать векторы Грамом — Шмидтом и пропустить зависимые

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

Неизвестное x показывает найденное значение — пять.

Главная мысль

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

Что именно сохраняет вычитание проекций

Оболочка набора — все линейные комбинации его векторов. Задача состоит в замене набора на удобные взаимно перпендикулярные направления с той же оболочкой, а не в сохранении длин и координат каждого исходного вектора. Для ненулевого направления u проекция вектора v равна u·(v·u)/(u·u). В знаменателе стоит квадрат нормы, поэтому он положителен и не требует извлечения корня.

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

Пример с зависимым вектором внутри списка

Рассмотрим v₁=(1;1;0), v₂=(2;2;0), v₃=(1;0;1). Первым направлением берём u₁=v₁, его квадрат нормы равен двум. Для второго вектора коэффициент проекции равен четырём, делённым на два, то есть двум. После вычитания 2u₁ получается ноль. Это содержательный результат: v₂ уже находится на найденной прямой, поэтому не увеличивает размерность оболочки.

Продолжаем обработку третьего вектора, сохранив только ненулевое направление u₁. Коэффициент его проекции равен одному, делённому на два. Остаток u₂=v₃−u₁/2=(1/2;−1/2;1). Он ненулевой, поэтому добавляется в базис. Зависимый вектор в середине списка не останавливает весь метод. Если после него остались новые независимые направления, они по-прежнему должны быть рассмотрены.

Пример

Ортогональный базис оболочки: u₁=(1;1;0), u₂=(1/2;−1/2;1). Квадраты норм равны 2 и 3/2, скалярное произведение равно 1/2−1/2=0. Размерность оболочки — два.

Проверка полноты видна прямо: v₁=u₁, v₂=2u₁, v₃=u₁/2+u₂. Каждый исходный вектор восстановлен из нового базиса. Независимость следует из ненулевых норм и ортогональности; в трёхмерном пространстве не обязательно нужен базис из трёх векторов для заданной оболочки.

Ортогональный базис ещё не ортонормированный

Для ортонормированного базиса каждый полученный вектор дополнительно делят на его норму. В примере это деление на √2 и √(3/2). Нормировать необязательно, если задача требует только ортогональных направлений; точные ненормированные координаты нередко проще. Нельзя назвать базис единичным лишь потому, что попарные произведения нулевые: длины проверяются отдельно. Нулевой исходный вектор также пропускается и не создаёт нового направления.

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

От чтения к действию

А теперь — вы

Обрабатываются (1;0), (2;0), (0;1). Второй остаток нулевой. Как поступить?

Частые вопросы

Изменится ли конкретный базис при перестановке исходных векторов?

Может измениться порядок и сами ортогональные направления. При точных вычислениях оболочка и её размерность сохраняются, если обработан весь набор.

Что выдаёт набор из одних нулевых векторов?

Его оболочка содержит только ноль и имеет размерность ноль. Пустой базис корректен; создавать искусственное ненулевое направление не требуется.

Углублённый разбор

Отражение Хаусхолдера без изменения длины

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

Перед началом: Скалярное произведение; Ортогональная матрица.

Отражение определяется одной нормалью

Для ненулевого v положим H=I−2vvᵀ/(vᵀv). Вектор вдоль v меняет знак, а любой вектор из v⊥ остаётся прежним. Разложение x на эти две ортогональные части показывает геометрию отражения. Из той же формулы следует Hᵀ=H и H²=I, поэтому H ортогональна и сохраняет евклидову норму.

Чтобы получить Hx=αe₁ с |α|=‖x‖, можно выбрать v=x−αe₁, если этот вектор ненулевой. Тогда отражение меняет x в нужное направление. Два возможных знака α дают разные, но корректные отражения. В вычислениях знак выбирают так, чтобы избежать вычитания почти равных больших чисел в первой координате v.

Нормировать вектор отражения необязательно

В записи с единичной нормалью q=v/‖v‖ отражение выглядит как H=I−2qqᵀ. Обе формулы равносильны. Если используется ненормированный v, знаменатель vᵀv обязателен. Его потеря обычно нарушает и сохранение длины, и равенство H²=I. Масштабирование v на ненулевое число не меняет отражение.

Полную матрицу H можно не строить: действие на y вычисляется как y−v·(2vᵀy/(vᵀv)). Это один скалярный коэффициент и одна векторная поправка. Для блока столбцов отражение применяется к каждому из них, создавая нули ниже диагонали в текущем столбце, но сохраняя согласованное действие на остальные.

После первого столбца работают в меньшем подпространстве

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

Если хвост уже нулевой, дополнительное отражение может быть не нужно. Если сам исходный вектор нулевой, нормаль по формуле x−αe₁ тоже нулевая и деление недопустимо. Такие случаи обрабатывают явно. Проверка Hx и HᵀH=I отделяет цель обнуления от свойства сохранения длины.

Обнуление второй координаты

Условие. Для x=(3,4) постройте отражение H, переводящее x в (−5,0), используя v=(8,4).

  1. Норма x равна пяти. Разность x−(−5,0)=(8,4) совпадает с выбранным v.
  2. Квадрат нормы v равен 64+16=80, поэтому множитель перед vvᵀ равен 1/40.
  3. H=I−vvᵀ/40=[[-3/5,−4/5],[−4/5,3/5]].
  4. Умножение H(3,4)=((−9−16)/5,(−12+12)/5)=(−5,0) завершает обнуление.

Ответ. H=[[-3/5,−4/5],[−4/5,3/5]], Hx=(−5,0).

Проверка. Строки H имеют квадрат нормы один и нулевое скалярное произведение; H²=I. Определитель −1 подтверждает отражение, а не поворот.

Где легко ошибиться. Ненормированная нормаль допустима только со знаменателем vᵀv. Замена отражения обычной проекцией уничтожает длину и не даёт ортогонального преобразования.

Проверьте понимание

Каков det H для ненулевой нормали в двумерной задаче?

Вопросы к этой главе

Почему целевая координата выбрана отрицательной?

Для положительной первой координаты x это позволяет складывать её с нормой в v₁, избегая потери значащих цифр. Геометрически положительная цель тоже возможна при ненулевой нормали.

Отражение единственно?

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

Сверить определения и условия

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

  • Driscoll, Braun: Computing QR factorizations

    Вебом прочитаны определение отражения Хаусхолдера, его ортогональность и применение для QR; авторский учебник. Изложение и числовые данные данной главы подготовлены отдельно.

Модифицированный Грам — Шмидт и обновляемый остаток

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

Перед началом: Ортогональная проекция; Округление.

Коэффициент берут от текущего остатка

Пусть q₁,…,qₖ уже ортонормированы и обрабатывается новый столбец a. В модифицированном варианте сначала v=a. На шаге i вычисляют rᵢ=qᵢᵀv и сразу заменяют v←v−rᵢqᵢ. Следующий коэффициент получают из уже изменённого v. В классическом варианте коэффициенты всех проекций сначала вычисляют от исходного a.

В точной арифметике два способа совпадают, поскольку qⱼᵀqᵢ=0 при j≠i. Вычитание компоненты qᵢ не меняет точного коэффициента по qⱼ. Но после округления вычисленные направления лишь приближённо ортогональны. Поэтому замена исходного столбца текущим остатком становится реальным изменением вычислительного маршрута.

Остаток после каждого удаления компоненты
ШагКоэффициентОстаток
Исходный—(2,1,3)
q₁2(0,1,3)
q₂3(0,−4/5,3/5)

Норма остатка отвечает за новое направление

После всех вычитаний вычисляют rₖ₊₁=‖v‖. Если она ненулевая, новый q=v/rₖ₊₁ добавляет единичное направление. В точных данных нулевой остаток означает зависимость нового столбца от прежних. В численных данных малая норма требует порога, связанного с масштабом задачи, а не сравнения с произвольной постоянной без единиц.

Модифицированный вариант обычно лучше сохраняет ортогональность, но не даёт абсолютной гарантии для любого плохо обусловленного набора столбцов. Иногда полезен второй проход ортогонализации, в котором снова удаляют компоненты по уже найденным q. Он уменьшает накопленный остаточный наклон, но не создаёт информацию, потерянную в исходных округлённых данных.

Два вида контроля проверяют разные свойства

Равенство A≈QR проверяет восстановление исходных столбцов, а QᵀQ≈I проверяет ортогональность. Первое может выполняться очень точно при заметной потере второго. Поэтому одной невязки восстановления недостаточно, если дальнейшая задача использует Q как изометрию либо рассчитывает проекции обычным транспонированием.

При реализации важно хранить коэффициенты rᵢ в правильной строке R и не терять обновлённый остаток между шагами. Для точного небольшого примера можно показать инвариант: исходный a равен сумме уже извлечённых rᵢqᵢ и текущего v. Он объясняет каждое вычитание и одновременно проверяет сборку разложения.

Два известных направления

Условие. q₁=(1,0,0), q₂=(0,3/5,4/5), a=(2,1,3). Выполните два шага модифицированного Грама — Шмидта.

  1. Начальный остаток v=a. Первый коэффициент r₁=q₁ᵀv=2; новый v=(0,1,3).
  2. Второй коэффициент берётся от нового v: r₂=3/5+12/5=3.
  3. Вычитание 3q₂ даёт v=(0,−4/5,3/5); его норма равна единице.
  4. Поэтому q₃=v. Оба произведения q₁ᵀq₃ и q₂ᵀq₃ равны нулю.

Ответ. r₁=2, r₂=3, q₃=(0,−4/5,3/5).

Проверка. Восстановление 2q₁+3q₂+q₃ даёт (2,1,3); единичные нормы и ортогональность проверяются точными дробями.

Где легко ошибиться. Нельзя объявлять численную ортогональность только по малой ошибке A−QR. Для QᵀQ−I требуется отдельная проверка, особенно при почти зависимых столбцах.

Проверьте понимание

От какого вектора вычисляется второй коэффициент в модифицированном варианте задачи?

Вопросы к этой главе

Отличаются ли ответы двух вариантов для точных рациональных данных?

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

Что делать с почти нулевым остатком?

Сопоставить его норму с масштабом исходного столбца и точностью данных. Автоматическое деление на очень малую норму может усилить вычислительный шум.

Сверить определения и условия

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

  • Georgia Tech: Orthogonal Sets

    Вебом проверены ортонормальность, формула проекции и базовый процесс Грама — Шмидта. Отличие порядка обновления остатка и ограничения численной точности объяснены отдельно; источник не выдаётся за экспериментальную гарантию точности.

Треугольная задача наименьших квадратов после QR

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

Перед началом: Метод наименьших квадратов; Ортонормированные столбцы.

Разложите данные на достижимую часть и остаток

Пусть A=QR — тонкое QR-разложение матрицы m×n с независимыми столбцами. Здесь QᵀQ=Iₙ, R квадратная верхняя треугольная и обратимая. Любой b разлагается на QQᵀb и r⊥=(I−QQᵀ)b. Вторая часть ортогональна всем столбцам Q и не может быть воспроизведена никаким Ax.

По теореме Пифагора ‖Ax−b‖²=‖Rx−Qᵀb‖²+‖r⊥‖². Вторая величина не зависит от x. Поэтому минимум достигается, когда Rx=Qᵀb, и эта треугольная система имеет единственное решение. Здесь использована ортогональность, а не покомпонентное отбрасывание лишних уравнений.

Полное Q показывает минимальную ошибку в хвосте

Если Q дополнена до квадратной ортогональной матрицы Q_full, то Q_fullᵀA имеет блок R сверху и нули снизу. Тот же поворот b даёт верхнюю часть для подстановки и нижнюю часть, квадрат нормы которой равен минимальной сумме квадратов. Ортогональный поворот сохраняет длину, поэтому полученная ошибка относится к исходной задаче.

Нельзя записывать QQᵀ=Iₘ для тонкой Q при m>n. Это проектор на пространство столбцов, а не единичное действие на всём пространстве наблюдений. Именно недостающая часть b и является причиной ненулевого минимального остатка. Равенство QᵀQ=Iₙ имеет другой размер и другой смысл.

Проверьте ранг до обратной подстановки

Если столбцы зависимы, R содержит вырожденный блок, и обычное решение всех коэффициентов единственным образом невозможно. Нужны перестановки столбцов, ранговый анализ или другой метод. Само наличие некоторого QR-разложения ещё не доказывает независимость исходных признаков.

Для независимых столбцов QR избегает явного возведения обусловленности в квадрат, которое возникает при переходе к AᵀA. Это аргумент в пользу вычислительного маршрута, а не обещание точности при любом входе. После решения проверяют остаток в исходных координатах и равенство Aᵀ(Ax−b)=0 как независимое условие оптимальности.

Треугольная задача после поворота

Условие. Даны Q со столбцами (1,0,0),(0,1,0), R=[[2,1],[0,3]], b=(5,6,4). Найдите МНК-решение и минимальную сумму квадратов.

  1. Тонкое Q ортонормировано. Проекция данных в координаты его столбцов равна Qᵀb=(5,6).
  2. Решаем R x=(5,6): из 3x₂=6 получаем x₂=2, затем 2x₁+2=5 и x₁=3/2.
  3. Матрица A=QR имеет строки (2,1),(0,3),(0,0). Прогноз Ax=(5,6,0).
  4. Остаток Ax−b=(0,0,−4), его квадрат нормы равен 16; третье наблюдение недостижимо моделью.

Ответ. x=(3/2,2); минимальная сумма квадратов 16.

Проверка. Aᵀ(Ax−b)=(0,0). Любое отклонение x на h добавляет ‖Rh‖²≥0, причём равенство возможно только при h=0.

Где легко ошибиться. Тонкая Q имеет ортонормированные столбцы, но обычно QQᵀ не равна единичной матрице наблюдений. Потеря этого различия ошибочно обнулит неизбежный остаток.

Проверьте понимание

Чему равна минимальная сумма квадратов в разобранной задаче?

Вопросы к этой главе

Можно ли восстановить остаток без полного Q?

Да. После решения вычисляют b−Ax в исходных координатах либо вычитают QQᵀb из b. Полная ортогональная матрица нужна только для удобного отображения хвостовых координат.

Почему коэффициенты единственны?

При независимых столбцах R обратима. Поэтому только один x обнуляет первую часть пифагорова разложения; остаток вне пространства столбцов уже фиксирован данными.

Сверить определения и условия

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

  • Driscoll, Braun: The QR factorization

    Вебом прочитан авторский раздел QR, ортогональности и применения к переопределённой системе. Пифагорово разложение и конкретный остаток в данной главе вычислены отдельно.

Полярное разложение отделяет вращение от растяжения

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

Перед началом: Ортогональная матрица; Положительный квадратный корень.

Правый положительный фактор определяется однозначно

Для вещественной квадратной матрицы A ищем A=UH, где U ортогональна, а H симметрична и положительно полуопределённа. Из AᵀA=HᵀUᵀUH=H² следует H=(AᵀA)^(1/2). Квадратный корень здесь означает положительный симметричный корень матрицы, а не извлечение корня из каждого элемента. Отрицательные элементы вне диагонали сами по себе не мешают положительности формы.

Когда A обратима, H положительно определена и U=AH⁻¹. Тогда UᵀU=H⁻¹AᵀAH⁻¹=I, что доказывает ортогональность. Формула также даёт единственность обоих факторов в этом случае. Геометрический порядок важен: сначала действует H, затем U. Перестановка множителей обычно изменяет матрицу, потому что ортогональный и положительный факторы не обязаны коммутировать.

Собственные направления растяжения не равны исходным осям

Если H имеет недиагональные элементы, она растягивает вдоль собственных ортогональных направлений. Длины этих растяжений — сингулярные величины A. Столбцовая нормировка A по отдельности не восстанавливает U: даже нормированные столбцы могут оставаться неортогональными. В H хранится и информация об их взаимной геометрии.

При вырожденной A положительный фактор H по-прежнему единственен, но полный ортогональный U может быть неединственным: действие на ядре не наблюдается в произведении UH. Например у diag(1,0) оба варианта diag(1,1) и diag(1,−1) дают тот же A после умножения на H. Это точная граница утверждения о единственности, а не ошибка вычисления.

Полярная и треугольная задачи дают разные сертификаты

В QR положительный по диагонали верхнетреугольный R зависит от последовательного выбора столбцов. В полярном разложении H симметрична и определяется общей матрицей AᵀA. Поэтому простая замена R на H без пересчёта ортогонального множителя неверна. Для проверки полярной пары достаточно установить UH=A, UᵀU=I, H²=AᵀA и положительность H. Последняя нужна обязательно: произвольный симметричный квадратный корень тоже может воспроизвести квадрат, но иметь неверные знаки растяжений.

Недиагональное растяжение

Условие. Для A=[[−1,−2],[2,1]] найдите правое полярное разложение A=UH и определите собственные растяжения H.

  1. Получаем AᵀA=[[5,4],[4,5]]. Направления (1,1) и (1,−1) имеют собственные значения9 и1.
  2. Положительный квадратный корень равен H=[[2,1],[1,2]]: его квадрат [[5,4],[4,5]], а собственные значения3 и1 положительны.
  3. Матрица H⁻¹=(1/3)[[2,−1],[−1,2]]. Умножение AH⁻¹ даёт U=[[0,−1],[1,0]], поворот на прямой угол.
  4. Проверяем UH=[[−1,−2],[2,1]] и UᵀU=I. Следовательно, растяжения равны3 и1, затем выполняется ортогональный поворот.

Ответ. H=[[2,1],[1,2]], U=[[0,−1],[1,0]]; растяжения3 и1.

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

Где легко ошибиться. Не извлекайте квадратный корень поэлементно из AᵀA. Нужна матрица H, квадрат которой в смысле матричного умножения равен AᵀA и чьи собственные значения неотрицательны.

Проверьте понимание

Чему равен элемент H₁₁ найденного положительного фактора?

Вопросы к этой главе

У ортогонального фактора всегда определитель1?

Нет. Для обратимой A знак det U совпадает со знаком det A, поскольку det H положителен. Отрицательный знак означает ортогональное преобразование с отражением, а не чистый поворот.

Почему важен именно правый полярный фактор?

Запись A=UH отделяет растяжение во входных координатах. Можно строить и левую форму A=KU, где K=(AAᵀ)^(1/2) описывает растяжение в выходных координатах. Эти положительные матрицы обычно различаются.

Сверить определения и условия

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

  • Nicholas Higham: What Is the Polar Decomposition?

    Прочитаны определение A=UH, формула H=(A* A)^(1/2), единственность при полном ранге и потеря единственности U при дефекте. Собственная матрица содержит недиагональный положительный фактор.

Минимакс Рэлея на подпространствах

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

Перед началом: Самосопряжённая матрица; Размерность пересечения подпространств.

Два игрока выбирают пространство и направление

Пусть A симметрична и её собственные значения записаны по возрастанию λ₁≤…≤λₙ. Для ненулевого x отношение Рэлея равно R(x)=xᵀAx/(xᵀx). Минимаксная формула утверждает λₖ=min_dimE=k max_x∈E R(x). Сначала для каждого k-мерного пространства берут самый большой коэффициент формы, затем выбирают пространство с наименьшим таким максимумом. Перестановка этих действий задаёт другую задачу.

Двойственная запись имеет вид λₖ=max_dimE=n−k+1 min_x∈E R(x). Она выбирает пространство, у которого самое слабое направление как можно сильнее. В обоих случаях нулевой вектор исключён, а однородность позволяет ограничиться единичной сферой. Симметричность обеспечивает ортонормированный собственный базис и вещественный порядок значений.

Пересечение даёт универсальную нижнюю границу

Любое k-мерное E пересекается ненулевым образом с пространством собственных векторов от k-го до n-го: сумма размерностей равна n+1. На найденном направлении R не меньше λₖ, значит максимум на E тоже не меньше λₖ. Это граница для всех возможных E, а не только для координатных плоскостей.

Достижение показывается другим пространством: берём первые k собственных направлений. На нём R является взвешенным средним чисел λ₁,…,λₖ и не превосходит λₖ; на k-м направлении равенство достигается. Так доказательство разделяется на универсальное препятствие и конкретное достигающее пространство. Пример одной удачной плоскости без первого аргумента ещё не доказывал бы минимум.

Ограничение на произвольную плоскость даёт лишь оценку

Выбранное вручную пространство может содержать слишком сильное направление, поэтому его максимум окажется выше λₖ. Метод Рэлея — Ритца использует это как контролируемую верхнюю оценку при расчёте на пробном подпространстве. Геометрия метрики при этом должна сохраняться: если базис плоскости не ортонормирован, в знаменателе появляется его матрица Грама. Простая подстановка координат как ортонормированных способна изменить отношение и испортить оценку.

Средний спектральный уровень

Условие. Пусть A=diag(1,4,9). Найдите min по всем двумерным E величины max R(x) на E. Отдельно найдите максимум на пробной плоскости x₃=x₁.

  1. Любая двумерная E пересекается с span(e₂,e₃) по ненулевому направлению. На нём R≥4, поэтому максимум на E не меньше4.
  2. При E₀=span(e₁,e₂) отношение равно (x₁²+4x₂²)/(x₁²+x₂²) и его максимум равен4. Значит универсальная нижняя граница достигается.
  3. На плоскости x₃=x₁ положим x=(a,b,a). Тогда R=(10a²+4b²)/(2a²+b²). Это взвешенное среднее5 и4.
  4. Пробная плоскость имеет максимум5 при b=0. Она даёт верную верхнюю оценку4≤5, но не минимизирует худшее направление.

Ответ. Искомый минимакс равен4; максимум на плоскости x₃=x₁ равен5.

Проверка. Два рациональных неравенства следуют из неотрицательности квадратов: на E₀ имеем R≤4, на пробной плоскости4≤R≤5. Пересечение размерностей независимо исключает любой результат меньше4 для всей задачи.

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

Проверьте понимание

Чему равен минимакс по всем двумерным подпространствам?

Вопросы к этой главе

Что изменится при кратном собственном значении?

Значение минимакса останется тем же по формуле, но достигающее пространство может быть неединственным. Внутри кратного собственного подпространства можно менять направления, не меняя соответствующие отношения Рэлея.

Почему здесь недостаточно искать стационарные точки R?

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

Сверить определения и условия

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

  • Sergei Treil: Linear Algebra Done Wrong

    Прочитаны глава7§4.2: минимакс собственных значений, и §5: положительные формы как скалярные произведения. Обобщённое отношение Рэлея приводится к обычному собственной заменой метрики; матрицы и дополнительные плоскости наши.

Главные углы между двумя подпространствами

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

Перед началом: Ортонормированный базис; Сингулярные числа матрицы.

Сначала устранить произвол исходных базисов

Рассмотрим два действительных подпространства U,V одинаковой размерности r в евклидовом пространстве. Пусть столбцы Q и R образуют их ортонормированные базисы. Любые единичные u∈U и v∈V записываются как u=Qa, v=Rb при |a|=|b|=1. Их скалярное произведение равно aᵀCb, где C=QᵀR. Буквы a,b обозначают коэффициенты в базисах, а u,v — векторы исходного пространства.

Наибольшее возможное значение aᵀCb есть старшее сингулярное число C. После выбора соответствующей пары направлений ищут максимум на ортогональных дополнениях к уже выбранным направлениям в каждом пространстве. Получается r чисел 1≥σ₁≥…≥σ_r≥0. Главные углы определим в порядке 0≤θ₁≤…≤θ_r≤π/2 по равенствам cosθ_i=σ_i.

Смена базисов не меняет найденный набор

Если заменить Q на QO и R на RP с ортогональными O,P, перекрёстная матрица станет OᵀCP. Её сингулярные числа сохраняются, хотя отдельные элементы могут совершенно измениться. Поэтому сравнение только угла между первыми входными столбцами не является сравнением подпространств.

Значение σ_i=1 соответствует общему направлению, то есть нулевому главному углу. Нуль среди σ_i означает прямой угол в соответствующей паре главных направлений. При этом наличие одного прямого угла не заставляет каждое направление U быть ортогональным каждому направлению V. Например, две плоскости в трёхмерном пространстве могут иметь общую прямую и ещё одну перпендикулярную пару.

Наибольший угол измеряет худшее расхождение

Для равных размерностей операторная норма разности ортопроекторов равна sinθ_r. Это связывает угловое описание с максимальной ошибкой при замене одного подпространства другим. В маленьком примере эту величину можно проверить непосредственно, рассматривая расстояние единичного вектора V до U, без повторного вычисления SVD.

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

Общая прямая и наклонённое второе направление

Условие. Пусть U=span{(1,0,0),(0,1,0)}, V=span{(1,0,0),(0,3/5,4/5)}. Найдите главные углы и максимальное расстояние единичного вектора V до U.

  1. Оба выписанных набора уже ортонормированы: второй вектор V имеет квадрат нормы 9/25+16/25=1 и ортогонален первому. Дополнительная ортогонализация не нужна.
  2. Матрица QᵀR диагональна с элементами 1 и3/5. Следовательно, её сингулярные числа также 1 и3/5; главные углы равны 0 иarccos(3/5).
  3. Нулевой угол соответствует общей оси первого координатного направления. Для второго угла синус равен 4/5. Это и есть худшее расстояние от единичного направления V до U.
  4. Непосредственно любой единичный v∈V имеет вид(a,3b/5,4b/5) сa²+b²=1. После ортопроекции на U остаток равен(0,0,4b/5); максимум его нормы 4/5 достигается при a=0,b=±1.

Ответ. Углы 0 иarccos(3/5); максимальное единичное расстояние 4/5.

Проверка. Самостоятельное вычисление матриц проекторов и квадрата их разности даёт ненулевые собственные значения 16/25,16/25. Поэтому норма разности проекторов 4/5 совпадает с прямой геометрической проверкой.

Где легко ошибиться. Не берите сингулярные числа произведения произвольных неортонормированных базисов. Перед QᵀR нужно убрать масштабы и зависимые направления, иначе числа могут даже выйти за единицу.

Проверьте понимание

Чему равно максимальное расстояние единичного вектора V до U?

Вопросы к этой главе

Почему один главный угол обязательно нулевой в этом примере?

Обе плоскости содержат ось(1,0,0). Можно выбрать одинаковый единичный вектор с обеих сторон и получить скалярное произведение 1, больше которого быть не может.

Чему равен угол между произвольно выбранными вторыми столбцами после их поворота?

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

Сверить определения и условия

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

  • Eckhard Hitzer: Angles between subspaces, §3–4

    Разделы 3–4: главные направления и связь косинусов главных углов с сингулярными числами после ортонормирования базисов. Рациональные базисы и проекторная проверка в главе рассчитаны отдельно.

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

Покомпонентное умножение обычно не описывает композицию операторов. Однако для положительно полуопределённых матриц оно сохраняет знак всей квадратичной формы. Теорема Шура объясняется новым набором векторов: каждую пару исходных признаков заменяют всеми попарными произведениями их координат.

Перед началом: Матрица Грама и линейная независимость; Положительная определённость квадратичной формы.

Сертификат через пары координат

Вещественные симметричные матрицы одного порядка; положительность означает знак квадратичной формы, а не знак каждого элемента.

Пусть Aᵢⱼ=uᵢ·uⱼ и Bᵢⱼ=vᵢ·vⱼ. Для каждого индекса i составим вектор wᵢ из чисел uᵢᵣvᵢₛ по всем парам r,s в одном фиксированном порядке. Тогда wᵢ·wⱼ=(uᵢ·uⱼ)(vᵢ·vⱼ). Следовательно, C=A∘B, где Cᵢⱼ=AᵢⱼBᵢⱼ, является матрицей Грама векторов wᵢ. Для любого z получаем zᵀCz=||Σᵢzᵢwᵢ||²≥0.

Это доказательство не требует положительности отдельных Aᵢⱼ. Скалярные произведения разных векторов могут быть отрицательными. Существенны грамово представление обеих матриц и одинаковый набор индексов. В комплексном случае берут эрмитовы произведения с сопряжением, а координатное построение сохраняется. Обычное AB вычисляет суммы по внутреннему индексу и является другой операцией.

Строгость определяется новым набором, а не прежними рангами

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

Полезное достаточное условие строже: если A положительно определена, а B полуопределена и все Bᵢᵢ>0, то A∘B положительно определена. Выберите λ>0 так, чтобы A−λI оставалась полуопределённой. Уже доказанная теорема даёт (A−λI)∘B≥0, значит C≥λ diag(Bᵢᵢ)>0. Здесь порядок означает сравнение квадратичных форм; он не является покомпонентным сравнением.

Нулевая диагональ и допустимые маски

Если Bⱼⱼ=0 у полуопределённой B, соответствующий грамов вектор нулевой. Поэтому вся строка и столбец j нулевые, а C не может быть строго положительной. Эта проверка быстро выявляет невозможную строгую оценку без вычисления определителя. Условие положительной диагонали в достаточном утверждении нельзя просто выбросить.

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

Два набора ранга два дают три независимых произведения

Условие. Возьмите u₁=(1,0),u₂=(0,1),u₃=(1,1) и v₁=(1,0),v₂=(1,1),v₃=(0,1). Найдите A,B,C=A∘B и решите, вырожден ли C.

  1. Попарные произведения дают A=((1,0,1),(0,1,1),(1,1,2)) и B=((1,1,0),(1,2,1),(0,1,1)). Оба набора живут в двумерном пространстве и имеют ранг два.
  2. В порядке координат (11,12,21,22) новые векторы равны w₁=(1,0,0,0), w₂=(0,0,1,1), w₃=(0,1,0,1). Их скалярные произведения образуют C=((1,0,0),(0,2,1),(0,1,2)).
  3. Координата11 выделяет коэффициент первого вектора, координата21 — второго, координата12 — третьего. Поэтому нулевая линейная комбинация всех w требует трёх нулевых коэффициентов: C строго положительна.
  4. Независимый контроль формы даёт zᵀCz=z₁²+z₂²+z₃²+(z₂+z₃)². Она положительна при любом ненулевом z, а det C=3. Ранги исходных матриц не запрещают этот результат.

Ответ. C=((1,0,0),(0,2,1),(0,1,2)) имеет ранг три и строго положительна, хотя A и B вырождены.

Проверка. Собственные значения C равны 1,1,3: первый координатный вектор отделён, а блок((2,1),(1,2)) имеет симметричное и антисимметричное направления. Их произведение равно найденному определителю.

Где легко ошибиться. Слово «положительная» не означает, что все элементы положительны. И не подменяйте A∘B матричным AB: у этих операций разные элементы и смысл.

Проверьте понимание

Каков ранг C=A∘B именно в разобранном примере двух трёхэлементных наборов?

Вопросы к этой главе

Почему ранг произведения оказался больше каждого исходного ранга?

Векторы w находятся в пространстве пар координат. Зависимость между u не обязана сохраняться после умножения каждого u на свой различный v.

Сохраняется ли строгая положительность при любой симметричной маске?

Нет. Например, маска((1,2),(2,1)) сама имеет отрицательное собственное значение. Для сохранения теорема требует полуопределённости маски; симметричности недостаточно.

Сверить определения и условия

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

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться