Введение

Метод разложения матриц
В линейной алгебре разложение Чолеского, или факторизация Чолеского (произносится /ʃ//ə/'/l//ɛ//s//k//i/ shəLESkee) — это представление эрмитовой, положительно определенной матрицы в виде произведения нижнетреугольной матрицы и её сопряжённой транспонированной матрицы, что полезно для эффективных численных решений, например, в методах Монте-Карло. Оно было открыто Андре Луи Чолески для вещественных матриц и опубликовано посмертно в 1924 году. Применительно к задачам, где оно возможно, разложение Чолеского примерно в два раза эффективнее разложения LU для решения систем линейных уравнений.

Геометрическая интерпретация

Разложение Холецкого эквивалентно определенному выбору сопряженных осей эллипсоида. В частности, пусть эллипсоид задан как , тогда по определению, множество векторов являются сопряженными осями эллипсоида, если выполняется условие . Тогда эллипсоид можно представить как , где отображает базисный вектор , а является единичной сферой в n-мерном пространстве. Иными словами, эллипсоид является линейным преобразованием единичной сферы. Определим матрицу , тогда условие эквивалентно . Различные выборы сопряженных осей соответствуют различным разложениям. Разложение Холецкого соответствует выбору , параллельного первой оси, , лежащего в плоскости, натянутой на первые две оси, и так далее. Это приводит к тому, что является верхнетреугольной матрицей. Тогда существует , где является нижнетреугольной матрицей. Аналогично, анализ главных компонент соответствует выбору сопряженных осей, взаимно перпендикулярных. Пусть и , и тогда существует , где является ортогональной матрицей. Это приводит к следующему результату: .

Числовое решение системы линейных уравнений

Разложение Чоллески в основном используется для численного решения систем линейных уравнений. Если матрица A симметрична и положительно определена, то систему можно решить, сначала вычислив разложение Чоллески , затем решив уравнение для y методом прямой подстановки, и, наконец, решив уравнение для x методом обратной подстановки. Альтернативный способ избежать вычисления квадратных корней при разложении – вычислить LDL-разложение , затем решить уравнение для y, и, наконец, решить уравнение . Для линейных систем, которые можно привести к симметричному виду, разложение Чоллески (или его вариант LDL) является предпочтительным методом благодаря более высокой эффективности и численной устойчивости. По сравнению с LU-разложением, оно примерно в два раза эффективнее.

Моделирование Монте-Карло

Расщепление Чолески обычно используется в методе Монте-Карло для моделирования систем с множеством взаимосвязанных переменных. Матрица ковариаций раскладывается на нижнетреугольную матрицу L. Применение этого к вектору некоррелированных случайных величин u дает вектор выборок Lu с ковариационными свойствами моделируемой системы. Следующий упрощенный пример демонстрирует эффективность, которую обеспечивает разложение Чолески: предположим, что необходимо сгенерировать две коррелированные нормальные случайные величины x и y с заданным коэффициентом корреляции ρ. Для этого сначала необходимо сгенерировать две некоррелированные гауссовские случайные величины u и v, что можно сделать, например, с помощью преобразования Бокса-Мюллера. Зная требуемый коэффициент корреляции ρ, коррелированные нормальные случайные величины можно получить с помощью преобразований x = u + ρv и y = v - ρu.

Фильтры Калмана

Непахнущие фильтры Калмана обычно используют разложение Чолеского для выбора набора так называемых сигма-точек. Фильтр Калмана отслеживает среднее состояние системы в виде вектора x длины N и ковариацию в виде матрицы P размера N × N. Матрица P всегда положительно полуопределённая и может быть разложена на LLᵀ. К среднему значению x можно прибавлять и вычитать столбцы матрицы L, чтобы сформировать набор из 2N векторов, называемых сигма-точками. Эти сигма-точки полностью описывают среднее значение и ковариацию состояния системы.

Инверсия матрицы

Явную обратную матрицу эрмитова типа можно вычислить с помощью разложения Холецкого, аналогично решению систем линейных уравнений, используя операций (умножений), где n – размер матрицы A. Следовательно, вычислительная сложность этого метода вдвое меньше, чем у LU-разложения, требующего 2n³/3 FLOPs (см. Trefethen и Bau, 1997). То, какой из алгоритмов будет быстрее, зависит от особенностей реализации. Как правило, первый алгоритм будет немного медленнее из-за менее упорядоченного доступа к данным.

Стабильность вычислений

Предположим, есть желание решить хорошо обусловленную систему линейных уравнений. Если используется LU-разложение, то алгоритм неустойчив, если не применяется какая-либо стратегия выбора главного элемента. В этом случае ошибка зависит от так называемого фактора роста матрицы, который обычно (но не всегда) мал. Теперь предположим, что применимо разложение Холецкого. Как уже упоминалось выше, алгоритм будет в два раза быстрее. Более того, выбор главного элемента не требуется, и ошибка всегда будет небольшой. В частности, если Ax = b, и y обозначает вычисленное решение, то y является решением возмущенной системы (A + E)y = b, где

||·||₂ – матричная 2-норма, cn – малая константа, зависящая от n, а ε обозначает единицу округления. Одной из особенностей разложения Холецкого, о которой следует помнить, является использование квадратных корней. Если разлагаемая матрица положительно определена, как того требует условие, числа под квадратными корнями всегда положительны при точной арифметике. К сожалению, из-за ошибок округления эти числа могут стать отрицательными, в этом случае алгоритм не сможет продолжаться. Однако это может произойти только в том случае, если матрица очень плохо обусловлена. Один из способов решения этой проблемы – добавить к разлагаемой матрице диагональную корректирующую матрицу, чтобы повысить ее положительную определенность. Хотя это может снизить точность разложения, это может быть очень выгодно по другим причинам; например, при использовании метода Ньютона в оптимизации добавление диагональной матрицы может улучшить устойчивость, когда решение далеко от оптимума.

Вариант блока

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

где каждый элемент в указанных матрицах является квадратной подматрицей. Из этого следуют аналогичные рекуррентные соотношения:

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

Обновление декомпозиции

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

Первый в рейтинге

Дата понижения ранга один аналогична обновлению ранга один, за исключением того, что сложение заменяется вычитанием: это работает только если новая матрица остаётся положительно определённой. Код для обновления ранга один, представленный выше, можно легко адаптировать для выполнения понижения ранга один: достаточно заменить два сложения в присваивании переменным r и L((k+1):n, k) на вычитания.

Доказательство ограничивающим аргументом

Вышеуказанные алгоритмы показывают, что каждая положительно определенная матрица имеет разложение Чолски. Этот результат можно расширить на случай положительной полуопределенности, используя предельный аргумент. Этот аргумент не является полностью конструктивным, то есть не предоставляет явных численных алгоритмов для вычисления факторов Чолски. Если A – положительно полуопределенная матрица, то последовательность A_n состоит из положительно определенных матриц. (Это непосредственное следствие, например, теоремы спектрального отображения для полиномиального функционального исчисления.) Также, ||A_n - A|| → 0 в операторной норме. Из положительно определенного случая следует, что каждая матрица A_n имеет разложение Чолски. По свойству операторной нормы, множество {A_n} ограничено, поскольку пространство операторов, оснащенное операторной нормой, является C*-алгеброй. Следовательно, это ограниченное множество в банаховом пространстве операторов, а значит, относительно компактно (поскольку базовое векторное пространство конечномерно). Следовательно, в нем существует сходящаяся подпоследовательность, также обозначаемая A_{n_k}, с пределом A*. Легко проверить, что эта матрица A* обладает необходимыми свойствами, то есть A* = A и A* является нижнетреугольной матрицей с неотрицательными диагональными элементами: для всех i и j.

Следовательно, A_{n_k} → A*. Поскольку базовое векторное пространство конечномерно, все топологии на пространстве операторов эквивалентны. Таким образом, сходимость A_{n_k} к A* в норме означает, что A_{n_k} сходится к A* поточечно. Это, в свою очередь, подразумевает, что поскольку каждая матрица A_{n_k} является нижнетреугольной с неотрицательными диагональными элементами, то и A* также является нижнетреугольной с неотрицательными диагональными элементами.

Доказательство по QR-разложению

Пусть A – положительно полуопределённая эрмитова матрица. Тогда её можно представить в виде произведения её квадратного корня, то есть A = √A√A. Теперь к матрице √A можно применить QR-разложение, в результате чего получится √A = QR, где Q – унитарная матрица, а R – верхнетреугольная. Подставляя разложение в исходное равенство, получаем A = QRQR = QR². Обозначив Q² = Q', завершаем доказательство.

Онлайн калькуляторы

Онлайн-калькулятор матриц выполняет разложение матриц на множители Холецкого в режиме онлайн.