Разложение Холецкого

В линейной алгебре , то разложение Холецкого или Холецкая факторизация (выраженный / ʃ ə . Л ɛ с . K я / ) представляю собой разложение из эрмитово , положительно определенной матрицы в произведение нижней треугольной матрицы и ее сопряженное транспонирование , который полезен для эффективных численных решений, например, моделирования Монте-Карло . Его открыл Андре-Луи Холецкий.для реальных матриц. Когда это применимо, разложение Холецкого примерно в два раза эффективнее, чем разложение LU для решения систем линейных уравнений . ^[1]

Заявление [ править ]

Разложение Холецкого эрмитовой положительно определенной матрицы A является разложением вида

${\ Displaystyle \ mathbf {A} = \ mathbf {LL} ^ {*},}$

где L является нижней треугольной матрицей с действительными и положительными диагональными элементами, а L * обозначает сопряженное транспонирование из L . Каждая эрмитова положительно определенная матрица (а значит, и каждая вещественнозначная симметричная положительно определенная матрица) имеет уникальное разложение Холецкого. ^[2]

Обратное верно тривиально: если A можно записать как LL * для некоторого обратимого L , нижнетреугольного или иного другого, то A эрмитово и положительно определено.

Когда A - вещественная матрица (следовательно, симметричная положительно определенная), факторизация может быть записана

${\ Displaystyle \ mathbf {A} = \ mathbf {LL} ^ {T},}$

где L - вещественная нижнетреугольная матрица с положительными диагональными элементами. ^{[3] [4] [5]}

Положительные полуопределенные матрицы [ править ]

Если эрмитова матрица A является только положительно полуопределенной, а не положительно определенной, то она все еще имеет разложение формы A = LL *, где диагональные элементы матрицы L могут быть равны нулю. ^[6] Разложение не обязательно должно быть уникальным, например:

${\ displaystyle {\ begin {pmatrix} 0 & 0 \\ 0 & 1 \ end {pmatrix}} = \ mathbf {L} \ mathbf {L} ^ {*}, \ quad \ quad \ mathbf {L} = {\ begin {pmatrix } 0 & 0 \\\ cos \ theta & \ sin \ theta \ end {pmatrix}}.}$

Однако если ранг A равен r , то существует единственный нижний треугольник L с ровно r положительными диагональными элементами и nr столбцами, содержащими все нули. ^[7]

В качестве альтернативы декомпозиция может быть сделана уникальной, если фиксирован выбор поворота. Формально, если A является положительной полуопределенной матрицей размера n × n ранга r , то существует по крайней мере одна матрица перестановок P такая, что PAP ^T имеет единственное разложение вида PAP ^T = LL ^* с , где L ₁ - матрица размера r × r нижнетреугольная матрица с положительной диагональю. ^[8]${\ displaystyle \ mathbf {L} = {\ begin {bmatrix} \ mathbf {L} _ {1} & 0 \\\ mathbf {L} _ {2} & 0 \ end {bmatrix}}}$

Разложение ЛПНП [ править ]

Близким вариантом классического разложения Холецкого является разложение ЛПНП,

${\ Displaystyle \ mathbf {A} = \ mathbf {LDL} ^ {*},}$

где L - нижняя единичная треугольная (унитреугольная) матрица, а D - диагональная матрица. То есть требуется, чтобы диагональные элементы L были равны 1 за счет введения дополнительной диагональной матрицы D в разложение. Основное преимущество состоит в том, что разложение LDL можно вычислить и использовать по существу с теми же алгоритмами, но избегает извлечения квадратных корней. ^[9]

По этой причине разложение ЛПНП часто называют разложением Холецкого без квадратного корня . Для реальных матриц факторизация имеет вид A = LDL ^T и часто называется разложением LDLT (или разложением LDL ^T , или LDL '). Она тесно связана с eigendecomposition вещественных симметричных матриц , A = QΛQ ^T .

Разложение LDL связано с классическим разложением Холецкого формы LL * следующим образом:

${\ Displaystyle \ mathbf {A} = \ mathbf {LDL} ^ {*} = \ mathbf {L} \ mathbf {D} ^ {1/2} (\ mathbf {D} ^ {1/2}) ^ { *} \ mathbf {L} ^ {*} = \ mathbf {L} \ mathbf {D} ^ {1/2} (\ mathbf {L} \ mathbf {D} ^ {1/2}) ^ {*} .}$

И наоборот, учитывая классическое разложение Холецкого положительно определенной матрицы, если S - диагональная матрица, содержащая главную диагональ матрицы , то A может быть разложено как где${\displaystyle \mathbf {A} =\mathbf {C} \mathbf {C} ^{*}}$${\displaystyle \mathbf {C} }$${\displaystyle \mathbf {L} \mathbf {D} \mathbf {L} ^{*}}$

${\displaystyle \mathbf {L} =\mathbf {C} \mathbf {S} ^{-1}}$ (это изменяет масштаб каждого столбца, чтобы сделать диагональные элементы равными 1),

${\displaystyle \mathbf {D} =\mathbf {S} ^{2}.}$

Если A положительно определена, то все диагональные элементы D положительны. Для получения положительных полуопределенных А , разложение существует там , где количество ненулевых элементов по диагонали D точно ранг A . ^[10] Некоторые неопределенные матрицы , для которых не существует разложение Холецкого имеет разложение LDL с записями в отрицательными D : достаточно, чтобы первые п-1 ведущие главные миноров из A неособов. ^[11]${\displaystyle \mathbf {L} \mathbf {D} \mathbf {L} ^{*}}$

Пример [ править ]

Вот разложение Холецкого симметричной вещественной матрицы:

${\displaystyle {\begin{aligned}\left({\begin{array}{*{3}{r}}4&12&-16\\12&37&-43\\-16&-43&98\\\end{array}}\right)=\left({\begin{array}{*{3}{r}}2&0&0\\6&1&0\\-8&5&3\\\end{array}}\right)\left({\begin{array}{*{3}{r}}2&6&-8\\0&1&5\\0&0&3\\\end{array}}\right).\end{aligned}}}$

А вот его разложение LDL ^T :

${\displaystyle {\begin{aligned}\left({\begin{array}{*{3}{r}}4&12&-16\\12&37&-43\\-16&-43&98\\\end{array}}\right)&=\left({\begin{array}{*{3}{r}}1&0&0\\3&1&0\\-4&5&1\\\end{array}}\right)\left({\begin{array}{*{3}{r}}4&0&0\\0&1&0\\0&0&9\\\end{array}}\right)\left({\begin{array}{*{3}{r}}1&3&-4\\0&1&5\\0&0&1\\\end{array}}\right).\end{aligned}}}$

Приложения [ править ]

Разложение Холецкого в основном используется для численного решения линейных уравнений . Если A является симметричным и положительно определенным, то мы можем решить , сначала вычислив разложение Холецкого , затем решив для y путем прямой подстановки и, наконец, решив для x путем обратной подстановки .${\displaystyle \mathbf {Ax} =\mathbf {b} }$${\displaystyle \mathbf {Ax} =\mathbf {b} }$${\displaystyle \mathbf {A} =\mathbf {LL} ^{\mathrm {*} }}$${\displaystyle \mathbf {Ly} =\mathbf {b} }$${\displaystyle \mathbf {L^{*}x} =\mathbf {y} }$

Альтернативный способ избавиться от извлечения квадратного корня в разложении - это вычислить разложение Холецкого , затем решить для y и, наконец, решить .${\displaystyle \mathbf {LL} ^{\mathrm {*} }}$${\displaystyle \mathbf {A} =\mathbf {LDL} ^{\mathrm {*} }}$${\displaystyle \mathbf {Ly} =\mathbf {b} }$${\displaystyle \mathbf {DL} ^{\mathrm {*} }\mathbf {x} =\mathbf {y} }$

Для линейных систем, которые могут быть представлены в симметричной форме, разложение Холецкого (или его вариант LDL) является методом выбора, обеспечивающим превосходную эффективность и численную стабильность. По сравнению с LU-разложением он примерно в два раза эффективнее. ^[1]

Линейный метод наименьших квадратов [ править ]

Системы вида Ax = b с симметричной и положительно определенной A возникают в приложениях довольно часто. Например, нормальные уравнения в линейных задачах наименьших квадратов имеют такую ​​форму. Также может случиться, что матрица A исходит из функционала энергии, который должен быть положительным по физическим соображениям; это часто случается при численном решении уравнений в частных производных .

Нелинейная оптимизация [ править ]

Нелинейные многомерные функции могут быть минимизированы по их параметрам, используя варианты метода Ньютона, называемые квазиньютоновскими методами. На итерации k поиск идет в направлении, определяемом решением = для , где - направление шага, является градиентом и является приближением к матрице Гессе, сформированной путем повторения обновлений ранга-1 на каждой итерации. Две хорошо известные формулы обновления называются Дэвидон – Флетчер – Пауэлл (DFP) и Бройден – Флетчер – Гольдфарб – Шанно.${\displaystyle p_{k}}$${\displaystyle B_{k}p_{k}}$${\displaystyle -g_{k}}$${\displaystyle p_{k}}$${\displaystyle p_{k}}$${\displaystyle g_{k}}$${\displaystyle B_{k}}$(BFGS). Потери положительно-определенного условия из-за ошибки округления можно избежать, если вместо обновления приближения к обратному к гессиану обновлять разложение Холецкого аппроксимации самой матрицы Гессе. ^[12]

Моделирование Монте-Карло [ править ]

Разложение Холецкого обычно используется в методе Монте-Карло для моделирования систем с множеством коррелированных переменных. Ковариационная матрица разлагаетс с получением низшего треугольную L . Применяя это к вектору некоррелированных выборок u, вы получаете вектор выборки Lu с ковариационными свойствами моделируемой системы. ^[13]

Следующий упрощенный пример показывает экономию, которую можно получить из разложения Холецкого: предположим, цель состоит в том, чтобы сгенерировать две коррелированные нормальные переменные и с заданным коэффициентом корреляции . Для этого необходимо сначала сгенерировать две некоррелированные гауссовские случайные величины и , что можно сделать с помощью преобразования Бокса – Маллера . При заданном коэффициенте корреляции коррелированные нормальные переменные могут быть получены с помощью преобразований и .${\displaystyle x_{1}}$${\displaystyle x_{2}}$${\displaystyle \rho }$${\displaystyle z_{1}}$${\displaystyle z_{2}}$${\displaystyle \rho }$${\displaystyle x_{1}=z_{1}}$${\displaystyle x_{2}=\rho z_{1}+{\sqrt {1-\rho ^{2}}}z_{2}}$

Фильтры Калмана [ править ]

Фильтры Калмана без запаха обычно используют разложение Холецкого для выбора набора так называемых сигма-точек. Фильтр Калмана отслеживает среднее состояние системы как вектор х длины N и ковариации в качестве N × N матрицы P . Матрица Р всегда положителен полуопределенный и может быть разложен на LL ^T . Столбцы L можно складывать и вычитать из среднего x, чтобы сформировать набор из 2 N векторов, называемых сигма-точками . Эти сигма-точки полностью отражают среднее значение и ковариацию состояния системы.

Инверсия матрицы [ править ]

Явная обратная эрмитова матрица может быть вычислена с помощью разложения Холецкого аналогично решению линейных систем с использованием операций ( умножений). ^[9] Вся инверсия может быть эффективно выполнена даже на месте.${\displaystyle n^{3}}$${\displaystyle {\tfrac {1}{2}}n^{3}}$

Неэрмитова матрица B также может быть обращена с использованием следующего тождества, где BB * всегда будет эрмитовой:

${\displaystyle \mathbf {B} ^{-1}=\mathbf {B} ^{*}(\mathbf {BB} ^{*})^{-1}.}$

Вычисление [ править ]

Существуют различные методы вычисления разложения Холецкого. Вычислительная сложность обычно используемых алгоритмов в целом составляет O ( n ³ ). ^{[ Править ]} Алгоритмы описаны ниже всего включают около п ³ /3 FLOPs ( п ³ /6 умножений и одинаковое количество добавок), где п является размер матрицы A . Следовательно, они имеют половину стоимости разложения LU , который использует 2 н ³ /3 FLOPs (см Trefethen и Bau 1997).

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

Алгоритм Холецкого [ править ]

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

Рекурсивный алгоритм начинается с i  : = 1 и

⁽¹⁾  : = .

На шаге i матрица A ^{( i )} имеет следующий вид:

${\displaystyle \mathbf {A} ^{(i)}={\begin{pmatrix}\mathbf {I} _{i-1}&0&0\\0&a_{i,i}&\mathbf {b} _{i}^{*}\\0&\mathbf {b} _{i}&\mathbf {B} ^{(i)}\end{pmatrix}},}$

где I _{i −1} обозначает единичную матрицу размерности i - 1.

Если теперь мы определим матрицу L _i как

${\displaystyle \mathbf {L} _{i}:={\begin{pmatrix}\mathbf {I} _{i-1}&0&0\\0&{\sqrt {a_{i,i}}}&0\\0&{\frac {1}{\sqrt {a_{i,i}}}}\mathbf {b} _{i}&\mathbf {I} _{n-i}\end{pmatrix}},}$

тогда мы можем записать A ^{( i )} как

${\displaystyle \mathbf {A} ^{(i)}=\mathbf {L} _{i}\mathbf {A} ^{(i+1)}\mathbf {L} _{i}^{*}}$

куда

${\displaystyle \mathbf {A} ^{(i+1)}={\begin{pmatrix}\mathbf {I} _{i-1}&0&0\\0&1&0\\0&0&\mathbf {B} ^{(i)}-{\frac {1}{a_{i,i}}}\mathbf {b} _{i}\mathbf {b} _{i}^{*}\end{pmatrix}}.}$

Обратите внимание, что b _i b * _i является внешним продуктом , поэтому этот алгоритм называется версией внешнего продукта в (Golub & Van Loan).

Мы повторяем это для i от 1 до n . После п шагов, мы получаем ^{( п +1)} = I . Следовательно, нижнетреугольная матрица L, которую мы ищем, вычисляется как

${\displaystyle \mathbf {L} :=\mathbf {L} _{1}\mathbf {L} _{2}\dots \mathbf {L} _{n}.}$

Алгоритмы Холецкого – Банахевича и Холецкого – Краута [ править ]

Если мы выпишем уравнение

${\displaystyle {\begin{aligned}\mathbf {A} =\mathbf {LL} ^{T}&={\begin{pmatrix}L_{11}&0&0\\L_{21}&L_{22}&0\\L_{31}&L_{32}&L_{33}\\\end{pmatrix}}{\begin{pmatrix}L_{11}&L_{21}&L_{31}\\0&L_{22}&L_{32}\\0&0&L_{33}\end{pmatrix}}\\[8pt]&={\begin{pmatrix}L_{11}^{2}&&({\text{symmetric}})\\L_{21}L_{11}&L_{21}^{2}+L_{22}^{2}&\\L_{31}L_{11}&L_{31}L_{21}+L_{32}L_{22}&L_{31}^{2}+L_{32}^{2}+L_{33}^{2}\end{pmatrix}},\end{aligned}}}$

получаем следующее:

${\displaystyle {\begin{aligned}\mathbf {L} ={\begin{pmatrix}{\sqrt {A_{11}}}&0&0\\A_{21}/L_{11}&{\sqrt {A_{22}-L_{21}^{2}}}&0\\A_{31}/L_{11}&\left(A_{32}-L_{31}L_{21}\right)/L_{22}&{\sqrt {A_{33}-L_{31}^{2}-L_{32}^{2}}}\end{pmatrix}}\end{aligned}}}$

и, следовательно, следующие формулы для элементов L :

${\displaystyle L_{j,j}=(\pm ){\sqrt {A_{j,j}-\sum _{k=1}^{j-1}L_{j,k}^{2}}},}$

${\displaystyle L_{i,j}={\frac {1}{L_{j,j}}}\left(A_{i,j}-\sum _{k=1}^{j-1}L_{i,k}L_{j,k}\right)\quad {\text{for }}i>j.}$

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

Для комплексной эрмитовой матрицы применяется следующая формула:

${\displaystyle L_{j,j}={\sqrt {A_{j,j}-\sum _{k=1}^{j-1}L_{j,k}L_{j,k}^{*}}},}$

${\displaystyle L_{i,j}={\frac {1}{L_{j,j}}}\left(A_{i,j}-\sum _{k=1}^{j-1}L_{i,k}L_{j,k}^{*}\right)\quad {\text{for }}i>j.}$

Таким образом, мы можем вычислить запись ( i , j ), если мы знаем записи слева и выше. Вычисления обычно располагаются в одном из следующих порядков:

• Алгоритм Холецкого-Banachiewicz начинается с верхнего левого угла матрицы L и продолжается для вычисления матрицы по строкам.
• Алгоритм Холецкого-Crout начинается с верхнего левого угла матрицы L и продолжается для вычисления столбца матрицы по столбцам.

Любой из вариантов доступа позволяет при желании выполнять все вычисления на месте.

Стабильность расчета [ править ]

Предположим, что мы хотим решить хорошо обусловленную систему линейных уравнений. Если используется разложение LU, алгоритм будет нестабильным, если мы не используем какую-то стратегию поворота. В последнем случае ошибка зависит от так называемого фактора роста матрицы, который обычно (но не всегда) невелик.

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

${\displaystyle \|\mathbf {E} \|_{2}\leq c_{n}\varepsilon \|\mathbf {A} \|_{2}.}$

Здесь || · || ₂ - матричная 2-норма , c _n - малая константа, зависящая от n , а ε обозначает единичное округление .

Одна из проблем разложения Холецкого, о которой следует помнить, - это использование квадратных корней. Если факторизуемая матрица положительно определена, как требуется, числа под квадратными корнями всегда положительны в точной арифметике . К сожалению, числа могут стать отрицательными из -за ошибок округления , и в этом случае алгоритм не может продолжить работу. Однако это может произойти только в том случае, если матрица очень плохо подготовлена. Один из способов решить эту проблему - добавить матрицу диагональной коррекции к разлагаемой матрице, чтобы попытаться обеспечить положительную определенность. ^[14] Хотя это может снизить точность разложения, это может быть очень благоприятным по другим причинам; например, при выполнении метода Ньютона в оптимизациидобавление диагональной матрицы может улучшить стабильность, когда она далека от оптимальной.

Разложение ЛПНП [ править ]

Альтернативной формой, устраняющей необходимость извлекать квадратные корни, когда A является симметричным, является симметричная неопределенная факторизация ^[15]

${\displaystyle {\begin{aligned}\mathbf {A} =\mathbf {LDL} ^{\mathrm {T} }&={\begin{pmatrix}1&0&0\\L_{21}&1&0\\L_{31}&L_{32}&1\\\end{pmatrix}}{\begin{pmatrix}D_{1}&0&0\\0&D_{2}&0\\0&0&D_{3}\\\end{pmatrix}}{\begin{pmatrix}1&L_{21}&L_{31}\\0&1&L_{32}\\0&0&1\\\end{pmatrix}}\\[8pt]&={\begin{pmatrix}D_{1}&&(\mathrm {symmetric} )\\L_{21}D_{1}&L_{21}^{2}D_{1}+D_{2}&\\L_{31}D_{1}&L_{31}L_{21}D_{1}+L_{32}D_{2}&L_{31}^{2}D_{1}+L_{32}^{2}D_{2}+D_{3}.\end{pmatrix}}.\end{aligned}}}$

Для записей D и L применяются следующие рекурсивные отношения :

${\displaystyle D_{j}=A_{jj}-\sum _{k=1}^{j-1}L_{jk}^{2}D_{k},}$

${\displaystyle L_{ij}={\frac {1}{D_{j}}}\left(A_{ij}-\sum _{k=1}^{j-1}L_{ik}L_{jk}D_{k}\right)\quad {\text{for }}i>j.}$

Это работает до тех пор, пока сгенерированные диагональные элементы в D остаются ненулевыми. Тогда разложение единственное. D и L реальны, если A реально.

Для комплексной эрмитовой матрицы A применяется следующая формула:

${\displaystyle D_{j}=A_{jj}-\sum _{k=1}^{j-1}L_{jk}L_{jk}^{*}D_{k},}$

${\displaystyle L_{ij}={\frac {1}{D_{j}}}\left(A_{ij}-\sum _{k=1}^{j-1}L_{ik}L_{jk}^{*}D_{k}\right)\quad {\text{for }}i>j.}$

Опять же, шаблон доступа позволяет при желании выполнять все вычисления на месте.

Вариант блокировки [ править ]

Известно, что при использовании с неопределенными матрицами факторизация LDL * нестабильна без тщательного поворота; ^{[16] в} частности, элементы факторизации могут расти произвольно. Возможным улучшением является выполнение факторизации блочных подматриц, обычно 2 × 2: ^[17]

${\displaystyle {\begin{aligned}\mathbf {A} =\mathbf {LDL} ^{\mathrm {T} }&={\begin{pmatrix}\mathbf {I} &0&0\\\mathbf {L} _{21}&\mathbf {I} &0\\\mathbf {L} _{31}&\mathbf {L} _{32}&\mathbf {I} \\\end{pmatrix}}{\begin{pmatrix}\mathbf {D} _{1}&0&0\\0&\mathbf {D} _{2}&0\\0&0&\mathbf {D} _{3}\\\end{pmatrix}}{\begin{pmatrix}\mathbf {I} &\mathbf {L} _{21}^{\mathrm {T} }&\mathbf {L} _{31}^{\mathrm {T} }\\0&\mathbf {I} &\mathbf {L} _{32}^{\mathrm {T} }\\0&0&\mathbf {I} \\\end{pmatrix}}\\[8pt]&={\begin{pmatrix}\mathbf {D} _{1}&&(\mathrm {symmetric} )\\\mathbf {L} _{21}\mathbf {D} _{1}&\mathbf {L} _{21}\mathbf {D} _{1}\mathbf {L} _{21}^{\mathrm {T} }+\mathbf {D} _{2}&\\\mathbf {L} _{31}\mathbf {D} _{1}&\mathbf {L} _{31}\mathbf {D} _{1}\mathbf {L} _{21}^{\mathrm {T} }+\mathbf {L} _{32}\mathbf {D} _{2}&\mathbf {L} _{31}\mathbf {D} _{1}\mathbf {L} _{31}^{\mathrm {T} }+\mathbf {L} _{32}\mathbf {D} _{2}\mathbf {L} _{32}^{\mathrm {T} }+\mathbf {D} _{3}\end{pmatrix}},\end{aligned}}}$

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

${\displaystyle \mathbf {D} _{j}=\mathbf {A} _{jj}-\sum _{k=1}^{j-1}\mathbf {L} _{jk}\mathbf {D} _{k}\mathbf {L} _{jk}^{\mathrm {T} },}$

${\displaystyle \mathbf {L} _{ij}=\left(\mathbf {A} _{ij}-\sum _{k=1}^{j-1}\mathbf {L} _{ik}\mathbf {D} _{k}\mathbf {L} _{jk}^{\mathrm {T} }\right)\mathbf {D} _{j}^{-1}.}$

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

Обновление декомпозиции [ править ]

На практике часто возникает задача обновить разложение Холецкого. Более подробно, один уже вычислил разложение Холецкого некоторой матрицы , то один меняет матрицу в некотором роде в другую матрицу, скажем , и один хочет вычислить разложение Холецкого обновленной матрицы: . Теперь возникает вопрос, можно ли использовать разложение Холецкого, которое было вычислено ранее, для вычисления разложения Холецкого .${\displaystyle \mathbf {A} =\mathbf {L} \mathbf {L} ^{*}}$${\displaystyle \mathbf {A} }$${\displaystyle \mathbf {A} }$${\displaystyle {\tilde {\mathbf {A} }}}$${\displaystyle {\tilde {\mathbf {A} }}={\tilde {\mathbf {L} }}{\tilde {\mathbf {L} }}^{*}}$${\displaystyle \mathbf {A} }$${\displaystyle {\tilde {\mathbf {A} }}}$

Обновление первого ранга [ править ]

Конкретный случай, когда обновленная матрица связана с матрицей посредством , известен как обновление ранга один .${\displaystyle {\tilde {\mathbf {A} }}}$${\displaystyle \mathbf {A} }$${\displaystyle {\tilde {\mathbf {A} }}=\mathbf {A} +\mathbf {x} \mathbf {x} ^{*}}$

Вот небольшая функция ^[18], написанная на синтаксисе Matlab, которая реализует обновление первого ранга:

функция  [L] = cholupdate ( L, x )  п  =  длина ( х );  для  k  =  1 : n  r  =  sqrt ( L ( k ,  k ) ^ 2  +  x ( k ) ^ 2 );  c  =  r  /  L ( k ,  k );  s  =  x ( k )  /  L ( k ,  k );  L ( к ,  к)  =  r ;  если  k  <  n  L (( k + 1 ): n ,  k )  =  ( L (( k + 1 ): n ,  k )  +  s  *  x (( k + 1 ): n ))  /  c ;  х (( к + 1 ): п )  =  с  *  х (( к + 1): n )  -  s  *  L (( k + 1 ): n ,  k );  конец  конец конец

Понижение первого ранга [ править ]

Ранга один downdate похож на ранговой одно обновление, за исключением того, что добавление заменяется вычитанием: . Это работает, только если новая матрица все еще является положительно определенной.${\displaystyle {\tilde {\mathbf {A} }}=\mathbf {A} -\mathbf {x} \mathbf {x} ^{*}}$${\displaystyle {\tilde {\mathbf {A} }}}$

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

Добавление и удаление строк и столбцов [ править ]

Если у нас есть симметричная и положительно определенная матрица, представленная в блочной форме как${\displaystyle \mathbf {A} }$

${\displaystyle \mathbf {A} ={\begin{pmatrix}\mathbf {A} _{11}&\mathbf {A} _{13}\\\mathbf {A} _{13}^{\mathrm {T} }&\mathbf {A} _{33}\\\end{pmatrix}}}$

и его верхний фактор Холецкого

${\displaystyle \mathbf {L} ={\begin{pmatrix}\mathbf {L} _{11}&\mathbf {L} _{13}\\0&\mathbf {L} _{33}\\\end{pmatrix}},}$

затем для новой матрицы , которая такая же, как и с добавлением новых строк и столбцов,${\displaystyle {\tilde {\mathbf {A} }}}$${\displaystyle \mathbf {A} }$

${\displaystyle {\begin{aligned}{\tilde {\mathbf {A} }}&={\begin{pmatrix}\mathbf {A} _{11}&\mathbf {A} _{12}&\mathbf {A} _{13}\\\mathbf {A} _{12}^{\mathrm {T} }&\mathbf {A} _{22}&\mathbf {A} _{23}\\\mathbf {A} _{13}^{\mathrm {T} }&\mathbf {A} _{23}^{\mathrm {T} }&\mathbf {A} _{33}\\\end{pmatrix}}\end{aligned}}}$

нас интересует факторизация Холецкого , которую мы называем , без прямого вычисления всего разложения. ${\displaystyle {\tilde {\mathbf {A} }}}$${\displaystyle {\tilde {\mathbf {S} }}}$

${\displaystyle {\begin{aligned}{\tilde {\mathbf {S} }}&={\begin{pmatrix}\mathbf {S} _{11}&\mathbf {S} _{12}&\mathbf {S} _{13}\\0&\mathbf {S} _{22}&\mathbf {S} _{23}\\0&0&\mathbf {S} _{33}\\\end{pmatrix}}.\end{aligned}}}$

Записывая решение , которое легко найти для треугольных матриц, и разложение Холецкого , можно найти следующие соотношения:${\displaystyle \mathbf {A} \setminus \mathbf {b} }$${\displaystyle \mathbf {A} \mathbf {x} =\mathbf {b} }$${\displaystyle {\text{chol}}(\mathbf {M} )}$${\displaystyle \mathbf {M} }$

${\displaystyle {\begin{aligned}\mathbf {S} _{11}&=\mathbf {L} _{11},\\\mathbf {S} _{12}&=\mathbf {L} _{11}^{\mathrm {T} }\setminus \mathbf {A} _{12},\\\mathbf {S} _{13}&=\mathbf {L} _{13},\\\mathbf {S} _{22}&={\text{chol}}(\mathbf {A} _{22}-\mathbf {S} _{12}^{\mathrm {T} }\mathbf {S} _{12}),\\\mathbf {S} _{23}&=\mathbf {S} _{22}^{\mathrm {T} }\setminus (\mathbf {A} _{23}-\mathbf {S} _{12}^{\mathrm {T} }\mathbf {S} _{13}),\\\mathbf {S} _{33}&={\text{chol}}(\mathbf {L} _{33}^{\mathrm {T} }\mathbf {L} _{33}-\mathbf {S} _{23}^{\mathrm {T} }\mathbf {S} _{23}).\\\end{aligned}}}$

Эти формулы могут использоваться для определения фактора Холецкого после вставки строк или столбцов в любую позицию, если мы соответствующим образом установим размеры строки и столбца (в том числе равными нулю). Обратная задача, когда мы имеем

${\displaystyle {\begin{aligned}{\tilde {\mathbf {A} }}&={\begin{pmatrix}\mathbf {A} _{11}&\mathbf {A} _{12}&\mathbf {A} _{13}\\\mathbf {A} _{12}^{\mathrm {T} }&\mathbf {A} _{22}&\mathbf {A} _{23}\\\mathbf {A} _{13}^{\mathrm {T} }&\mathbf {A} _{23}^{\mathrm {T} }&\mathbf {A} _{33}\\\end{pmatrix}}\end{aligned}}}$

с известным разложением Холецкого

${\displaystyle {\begin{aligned}{\tilde {\mathbf {S} }}&={\begin{pmatrix}\mathbf {S} _{11}&\mathbf {S} _{12}&\mathbf {S} _{13}\\0&\mathbf {S} _{22}&\mathbf {S} _{23}\\0&0&\mathbf {S} _{33}\\\end{pmatrix}}\end{aligned}}}$

и желаете определить фактор Холецкого

${\displaystyle {\begin{aligned}\mathbf {L} &={\begin{pmatrix}\mathbf {L} _{11}&\mathbf {L} _{13}\\0&\mathbf {L} _{33}\\\end{pmatrix}}\end{aligned}}}$

матрицы с удаленными строками и столбцами,${\displaystyle \mathbf {A} }$

${\displaystyle {\begin{aligned}\mathbf {A} &={\begin{pmatrix}\mathbf {A} _{11}&\mathbf {A} _{13}\\\mathbf {A} _{13}^{\mathrm {T} }&\mathbf {A} _{33}\\\end{pmatrix}},\end{aligned}}}$

дает следующие правила:

${\displaystyle {\begin{aligned}\mathbf {L} _{11}&=\mathbf {S} _{11},\\\mathbf {L} _{13}&=\mathbf {S} _{13},\\\mathbf {L} _{33}&={\text{chol}}(\mathbf {S} _{33}^{\mathrm {T} }\mathbf {S} _{33}+\mathbf {S} _{23}^{\mathrm {T} }\mathbf {S} _{23}).\end{aligned}}}$

Обратите внимание, что приведенные выше уравнения, которые включают поиск разложения Холецкого новой матрицы, имеют форму , которая позволяет их эффективно вычислять с помощью процедур обновления и понижения, подробно описанных в предыдущем разделе. ^[19]${\displaystyle {\tilde {\mathbf {A} }}=\mathbf {A} \pm \mathbf {x} \mathbf {x} ^{*}}$

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

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

Приведенные выше алгоритмы показывают, что каждая положительно определенная матрица имеет разложение Холецкого. Этот результат можно распространить на положительный полуопределенный случай ограничивающим аргументом. Аргумент не является полностью конструктивным, т.е. он не дает явных численных алгоритмов для вычисления факторов Холецкого.${\displaystyle \mathbf {A} }$

Если - положительно полуопределенная матрица , то последовательность состоит из положительно определенных матриц . (Это является непосредственным следствием, например, теоремы о спектральном отображении для полиномиального функционального исчисления.) Кроме того,${\displaystyle \mathbf {A} }$${\displaystyle n\times n}$ ${\displaystyle \left(\mathbf {A} _{k}\right)_{k}:=\left(\mathbf {A} +{\frac {1}{k}}\mathbf {I} _{n}\right)_{k}}$

${\displaystyle \mathbf {A} _{k}\rightarrow \mathbf {A} \quad {\text{for}}\quad k\rightarrow \infty }$

в операторной норме . В положительно определенном случае каждый из них имеет разложение Холецкого . По свойству операторной нормы${\displaystyle \mathbf {A} _{k}}$${\displaystyle \mathbf {A} _{k}=\mathbf {L} _{k}\mathbf {L} _{k}^{*}}$

${\displaystyle \|\mathbf {L} _{k}\|^{2}\geq \|\mathbf {L} _{k}\mathbf {L} _{k}^{*}\|=\|\mathbf {A} _{k}\|\,.}$

Таким образом, ограниченное множество в банаховом пространстве операторов является относительно компактным (поскольку лежащее в основе векторное пространство конечномерно). Следовательно, у него есть сходящаяся подпоследовательность, также обозначаемая с пределом . Это можно легко проверить , что это имеет желаемые свойства, то есть , и является нижней треугольной с неотрицательными диагональными элементами: для всех и ,${\displaystyle \left(\mathbf {L} _{k}\right)_{k}}$${\displaystyle \left(\mathbf {L} _{k}\right)_{k}}$${\displaystyle \mathbf {L} }$${\displaystyle \mathbf {L} }$${\displaystyle \mathbf {A} =\mathbf {L} \mathbf {L} ^{*}}$${\displaystyle \mathbf {L} }$${\displaystyle x}$${\displaystyle y}$

${\displaystyle \langle \mathbf {A} x,y\rangle =\left\langle \lim \mathbf {A} _{k}x,y\right\rangle =\langle \lim \mathbf {L} _{k}\mathbf {L} _{k}^{*}x,y\rangle =\langle \mathbf {L} \mathbf {L} ^{*}x,y\rangle \,.}$

Поэтому . Поскольку основное векторное пространство конечномерно, все топологии в пространстве операторов эквивалентны. Так что в норме значит имеет тенденцию к входу. Это, в свою очередь, означает, что, поскольку каждый из них является нижним треугольником с неотрицательными диагональными элементами, тоже.${\displaystyle \mathbf {A} =\mathbf {L} \mathbf {L} ^{*}}$${\displaystyle \left(\mathbf {L} _{k}\right)_{k}}$${\displaystyle \mathbf {L} }$${\displaystyle \left(\mathbf {L} _{k}\right)_{k}}$${\displaystyle \mathbf {L} }$${\displaystyle \mathbf {L} _{k}}$${\displaystyle \mathbf {L} }$

Доказательство с помощью QR-разложения [ править ]

Пусть - положительная полуопределенная эрмитова матрица. Тогда можно записать в виде произведения его квадратного корня матрицы , . Теперь можно применить QR-разложение к , в результате чего , где является унитарным и верхнетреугольным. Подставляя разложение в исходное равенство, получаем . Установка завершает доказательство.${\displaystyle \mathbf {A} }$${\displaystyle \mathbf {A} =\mathbf {B} \mathbf {B} ^{*}}$${\displaystyle \mathbf {B} ^{*}}$${\displaystyle \mathbf {B} ^{*}=\mathbf {Q} \mathbf {R} }$${\displaystyle \mathbf {Q} }$${\displaystyle \mathbf {R} }$${\displaystyle A=\mathbf {B} \mathbf {B} ^{*}=(\mathbf {QR} )^{*}\mathbf {QR} =\mathbf {R} ^{*}\mathbf {Q} ^{*}\mathbf {QR} =\mathbf {R} ^{*}\mathbf {R} }$${\displaystyle \mathbf {L} =\mathbf {R} ^{*}}$

Обобщение [ править ]

Факторизация Холецкого может быть обобщена ^{[ ссылка ]} на (не обязательно конечные) матрицы с операторными записями. Позвольте быть последовательность гильбертовых пространств . Рассмотрим операторную матрицу${\displaystyle \{{\mathcal {H}}_{n}\}}$

${\displaystyle \mathbf {A} ={\begin{bmatrix}\mathbf {A} _{11}&\mathbf {A} _{12}&\mathbf {A} _{13}&\;\\\mathbf {A} _{12}^{*}&\mathbf {A} _{22}&\mathbf {A} _{23}&\;\\\mathbf {A} _{13}^{*}&\mathbf {A} _{23}^{*}&\mathbf {A} _{33}&\;\\\;&\;&\;&\ddots \end{bmatrix}}}$

действуя на прямую сумму

${\displaystyle {\mathcal {H}}=\bigoplus _{n}{\mathcal {H}}_{n},}$

где каждый

${\displaystyle \mathbf {A} _{ij}:{\mathcal {H}}_{j}\rightarrow {\mathcal {H}}_{i}}$

- ограниченный оператор . Если A положительно (полуопределено) в том смысле, что для всех конечных k и любого

${\displaystyle h\in \bigoplus _{n=1}^{k}{\mathcal {H}}_{k},}$

мы , то существует нижняя треугольная матрица оператора L , такие , что A = LL *. Можно также считать диагональные элементы L положительными.${\displaystyle \langle h,\mathbf {A} h\rangle \geq 0}$

Реализации в библиотеках программирования [ править ]

• Язык программирования C : Научная библиотека GNU предоставляет несколько реализаций разложения Холецкого.
• Система компьютерной алгебры Maxima : функция cholesky вычисляет разложение Холецкого.
• Система численных вычислений GNU Octave предоставляет несколько функций для вычисления, обновления и применения разложения Холецкого.
• Библиотека LAPACK обеспечивает высокопроизводительную реализацию декомпозиции Холецкого, к которой можно получить доступ из Fortran, C и большинства языков.
• В Python функция cholesky из модуля numpy.linalg выполняет разложение Холецкого.
• В Matlab и R функция "chol" дает разложение Холецкого.
• В Julia "cholesky" функция из стандартной библиотеки LinearAlgebra дает разложение Холецкого.
• В системе Mathematica функцию "CholeskyDecomposition" можно применить к матрице.
• В C ++ команда "chol" из библиотеки armadillo выполняет разложение Холецкого. Библиотека Eigen предоставляет факторизации Холецкого как для разреженных, так и для плотных матриц.
• В пакете ROOT доступен класс TDecompChol.
• В Analytica функция Decompose дает разложение Холецкого.
• Библиотека Apache Commons Math имеет реализацию, которая может использоваться на Java, Scala и любом другом языке JVM.

См. Также [ править ]

• Ранг цикла
• Неполная факторизация Холецкого
• Разложение матрицы
• Алгоритм минимальной степени
• Квадратный корень из матрицы
• Закон инерции Сильвестра
• Символическое разложение Холецкого

Примечания [ править ]

Ссылки [ править ]

• Дерениовский, Дариуш; Кубале, Марек (2004). "Факторизация Холецкого параллельных матриц и ранжирование графов". 5-я Международная конференция по параллельной обработке и прикладной математике (PDF) . Конспект лекций по информатике. 3019 . Springer-Verlag. С. 985–992. DOI : 10.1007 / 978-3-540-24669-5_127 . ISBN 978-3-540-21946-0. Архивировано из оригинального (PDF) 16 июля 2011 года.
• Голуб, Джин Х .; Ван Лоан, Чарльз Ф. (1996). Матричные вычисления (3-е изд.). Балтимор: Джонс Хопкинс. ISBN 978-0-8018-5414-9.
• Хорн, Роджер А .; Джонсон, Чарльз Р. (1985). Матричный анализ . Издательство Кембриджского университета. ISBN 0-521-38632-2.
• SJ Julier и JK Uhlmann. « Общий метод аппроксимации нелинейных преобразований вероятностных распределений ».
• SJ Julier и JK Uhlmann, " Новое расширение фильтра Калмана для нелинейных систем ", в Proc. AeroSense: 11 Int. Symp. Аэрокосмическая / оборонная зондирование, моделирование и управление, 1997, стр. 182–193.
• Trefethen, Lloyd N .; Бау, Дэвид (1997). Численная линейная алгебра . Филадельфия: Общество промышленной и прикладной математики. ISBN 978-0-89871-361-9.
• Осборн, Майкл (2010). Байесовские гауссовские процессы для последовательного прогнозирования, оптимизации и квадратуры (PDF) (диссертация). Оксфордский университет.

Внешние ссылки [ править ]

История науки [ править ]

• Sur la résolution numérique des systèmes d'équations linéaires , рукопись Холецкого 1910 г., онлайн и проанализирована в BibNum (на французском и английском языках) [для английского нажмите «Зарядное устройство»]

Информация [ править ]

• "Факторизация Холецкого" , Математическая энциклопедия , EMS Press , 2001 [1994]
• Разложение Холецкого , Краткое руководство по анализу данных
• Разложение Холецкого на www.math-linux.com
• Разложение Холецкого стало проще на науке Меандерталец

Компьютерный код [ править ]

• LAPACK - это набор подпрограмм FORTRAN для решения задач плотной линейной алгебры.
• ALGLIB включает частичный перенос LAPACK на C ++, C #, Delphi, Visual Basic и т. Д.
• libflame - это библиотека C с функциональностью LAPACK.
• Заметки и видео о высокопроизводительной реализации факторизации Холецкого в Техасском университете в Остине.
• Холецкий: TBB + Threads + SSE - это книга, в которой объясняется реализация CF с TBB, потоками и SSE (на испанском языке).
• библиотека "Ceres Solver" от Google.
• Процедуры разложения LDL в Matlab.
• Armadillo - это пакет линейной алгебры C ++

Использование матрицы в моделировании [ править ]

• Генерация коррелированных случайных величин и случайных процессов , Мартин Хо, Колумбийский университет

Онлайн калькуляторы [ править ]

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