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

Метод матричного разложения

В линейной алгебре разложение Холецкого или факторизация Холецкого (произносится / ʃ ə ˈ l ɛ s k i / shə- LES -kee ) — это разложение эрмитовой положительно определенной матрицы в произведение нижней треугольной матрицы и ее сопряженной transpose , что полезно для эффективных численных решений, например, моделирования Монте-Карло . Оно было открыто Андре-Луи Холеским для вещественных матриц и посмертно опубликовано в 1924 году. ^[1] Когда оно применимо, разложение Холецкого примерно в два раза эффективнее, чем LU-разложение для решения систем линейных уравнений . ^[2]

Заявление

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

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

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

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

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

${\displaystyle \mathbf {A} =\mathbf {LL} ^{\mathsf {T}},}$

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

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

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

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

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

Альтернативно, декомпозиция может быть сделана уникальной, если фиксирован поворотный выбор. Формально, если A — положительно-полуопределенная матрица размера n × n ранга r , то существует хотя бы одна матрица перестановок P такая, что PAP ^T имеет уникальное разложение вида PAP ^T = LL ^* с , где L ₁ — матрица r × r нижняя треугольная матрица с положительной диагональю. ^[9] ${\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 в разложение. Основное преимущество заключается в том, что разложение ЛПНП можно вычислить и использовать по существу с помощью тех же алгоритмов, но без извлечения квадратных корней. ^[10]

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

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

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

И наоборот, учитывая классическое разложение Холецкого положительно определенной матрицы, если 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 положительны. Для положительно полуопределенного A существует разложение , в котором количество ненулевых элементов на диагонали D в точности равно рангу A. ^[11] Некоторые неопределенные матрицы, для которых не существует разложения Холецкого, имеют разложение LDL с отрицательными элементами в D : достаточно, чтобы первые n -1 главных миноров матрицы A были неособыми. ^[12] ${\displaystyle \mathbf {L} \mathbf {D} \mathbf {L} ^{*}}$

Пример

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

${\displaystyle {\begin{aligned}{\begin{pmatrix}4&12&-16\\12&37&-43\\-16&-43&98\\\end{pmatrix}}={\begin{pmatrix}2&0&0\\6&1&0\\-8&5&3\\\end{pmatrix}}{\begin{pmatrix}2&6&-8\\0&1&5\\0&0&3\\\end{pmatrix}}.\end{aligned}}}$

А вот его разложение ^Т -ЛПНП :

${\displaystyle {\begin{aligned}{\begin{pmatrix}4&12&-16\\12&37&-43\\-16&-43&98\\\end{pmatrix}}&={\begin{pmatrix}1&0&0\\3&1&0\\-4&5&1\\\end{pmatrix}}{\begin{pmatrix}4&0&0\\0&1&0\\0&0&9\\\end{pmatrix}}{\begin{pmatrix}1&3&-4\\0&1&5\\0&0&1\\\end{pmatrix}}.\end{aligned}}}$

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

Эллипс — это линейное изображение единичного круга. Два вектора являются сопряженными осями эллипса, выбранными так, чтобы они были параллельны первой оси и находились внутри плоскости, охватываемой первыми двумя осями. ${\displaystyle v_{1},v_{2}}$ ${\displaystyle v_{1}}$ ${\displaystyle v_{2}}$

Разложение Холецкого эквивалентно определенному выбору сопряженных осей эллипсоида . ^[13] Подробно, пусть эллипсоид определен как , тогда по определению набор векторов является сопряженными осями эллипсоида тогда и только тогда . Тогда эллипсоид в точности ${\displaystyle y^{T}Ay=1}$ ${\displaystyle v_{1},...,v_{n}}$ ${\displaystyle v_{i}^{T}Av_{j}=\delta _{ij}}$

$${\displaystyle \left\{\sum _{i}x_{i}v_{i}:x^{T}x=1\right\}=f(\mathbb {S} ^{n})}$$

${\displaystyle f}$ ${\displaystyle e_{i}\mapsto v_{i}}$ ${\displaystyle \mathbb {S} ^{n}}$

Определите матрицу , тогда эквивалентно . Разный выбор сопряженных осей соответствует разным разложениям. ${\displaystyle V:=[v_{1}|v_{2}|\cdots |v_{n}]}$ ${\displaystyle v_{i}^{T}Av_{j}=\delta _{ij}}$ ${\displaystyle V^{T}AV=I}$

Разложение Холецкого соответствует выбору быть параллельным первой оси, находиться внутри плоскости, охватываемой первыми двумя осями, и так далее. Получается верхнетреугольная матрица. Тогда существует , где – нижнетреугольный. ${\displaystyle v_{1}}$ ${\displaystyle v_{2}}$ ${\displaystyle V}$ ${\displaystyle A=LL^{T}}$ ${\displaystyle L=(V^{-1})^{T}}$

Точно так же анализ главных компонент соответствует выбору перпендикулярности. Тогда пусть и , и где – ортогональная матрица. Тогда это дает . ${\displaystyle v_{1},...,v_{n}}$ ${\displaystyle \lambda =1/\|v_{i}\|^{2}}$ ${\displaystyle \Sigma =\mathrm {diag} (\lambda _{1},...,\lambda _{n})}$ ${\displaystyle V=U\Sigma ^{-1/2}}$ ${\displaystyle U}$ ${\displaystyle A=U\Sigma U^{T}}$

Приложения

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

Разложение Холецкого в основном используется для численного решения линейных уравнений . Если 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} }$

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

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

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

Нелинейная оптимизация

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

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

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

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

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

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

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

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

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

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

Вычисление

Существуют различные методы расчета разложения Холецкого. Вычислительная сложность обычно используемых алгоритмов в целом равна ^O ( n3 ) . ^{[ нужна цитация ]} Все алгоритмы, описанные ниже, включают около (1/3) n ³ FLOP ( n ^3/6 умножений и такое же количество сложений) для реальных вариантов и (4/3) n ³ FLOP для сложных вариантов, ^{[16 ]} где n — размер матрицы A. Следовательно, они имеют половину стоимости LU-разложения , которое использует 2 n ^3/3 FLOP (см. Trefethen and 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,i > 0, поскольку A ^{( i )} положительно определена), то 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 . После n шагов получается A ^{( n +1)} = I , и, следовательно, искомая нижняя треугольная матрица L вычисляется как

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

Алгоритмы Холески-Банакевича и Холески-Краута.

Шаблон доступа (белый) и шаблон записи (желтый) для локального алгоритма Холецкого-Банакевича на матрице 5×5.

Если уравнение

${\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.}$

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

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

${\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_{j,k}^{*}L_{i,k}\right)\quad {\text{for }}i>j.}$

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

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

for ( я = 0 ; я < sizeSize ; я ++ ) { for ( j = 0 ; j <= i ; j ++ ) { float sum = 0 ; для ( k знак равно 0 ; k < j ; k ++ ) сумма += L [ i ] [ k ] * L [ j ] [ k ];                                   если ( я == j ) L [ я ][ j ] = sqrt ( A [ я ][ я ] - сумма ); иначе L [ i ][ j ] = ( 1,0 / L [ j ][ j ] * ( A [ i ][ j ] - сумма )); } }                   

Приведенный выше алгоритм можно кратко выразить как объединение скалярного произведения и умножения матриц в векторизованных языках программирования, таких как Фортран , следующим образом:

do я знак равно 1 , размер ( A , 1 ) L ( я , я ) = sqrt ( A ( я , я ) - скалярное произведение ( L ( я , 1 : я - 1 ), L ( я , 1 : я - 1 ) )) L ( i + 1 :, i ) = ( A ( i + 1 :, i ) - matmul ( conjg ( L ( i , 1 : i - 1 )), L ( i + 1 :, 1 : i - 1 ))) / L ( я , я ) конец делаю                 

где conjgотносится к комплексно-сопряженным элементам.

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

  for ( j = 0 ; j < sizeSize ; j ++ ) { float sum = 0 ; для ( k знак равно 0 ; k < j ; k ++ ) { сумма += L [ j ] [ k ] * L [ j ] [ k ]; } L [ j ][ j ] = sqrt ( A [ j ] [ j ] - сумма );                                 для ( я знак равно j + 1 ; я < размерразмера ; я ++ ) { сумма = 0 ; для ( k знак равно 0 ; k < j ; k ++ ) { сумма += L [ я ] [ k ] * L [ j ] [ k ]; } L [ i ][ j ] = ( 1,0 / L [ j ] [ j ] * ( A [ i ] [ j ] - сумма )); } }                                      

Приведенный выше алгоритм можно кратко выразить как объединение скалярного произведения и умножения матриц в векторизованных языках программирования, таких как Фортран , следующим образом:

do i = 1 , размер ( A , 1 ) L ( я , я ) = sqrt ( A ( я , я ) - скалярное произведение ( L ( 1 : я - 1 , я ), L ( 1 : я - 1 , я ) )) L ( i , i + 1 :) = ( A ( i , i + 1 :) - matmul ( conjg ( L ( 1 : i - 1 , i ))), L ( 1 : i - 1 , i + 1 :))) / L ( i , i ) end do                 

где conjgотносится к комплексно-сопряженным элементам.

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

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

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

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

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

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

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

Разложение ЛПНП

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

${\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 * при использовании с неопределенными матрицами без тщательного поворота нестабильна; ^{В [19]} , в частности, элементы факторизации могут расти произвольно. Возможным улучшением является выполнение факторизации блочных подматриц, обычно 2 × 2: ^[20]

${\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} ^{*}}$

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

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

Обновление ранга n — это обновление матрицы, при котором разложение обновляется так, что . Этого можно достичь путем последовательного выполнения обновлений первого ранга для каждого из столбцов . ${\displaystyle \mathbf {M} }$ ${\displaystyle {\tilde {\mathbf {A} }}=\mathbf {A} +\mathbf {M} \mathbf {M} ^{*}}$ ${\displaystyle \mathbf {M} }$

Понижение первого ранга

Понижение первого ранга аналогично обновлению первого ранга, за исключением того, что добавление заменяется вычитанием: . Это работает только в том случае, если новая матрица все еще положительно определена. ${\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}&=\mathrm {chol} \left(\mathbf {A} _{22}-\mathbf {S} _{12}^{\mathrm {T} }\mathbf {S} _{12}\right),\\\mathbf {S} _{23}&=\mathbf {S} _{22}^{\mathrm {T} }\setminus \left(\mathbf {A} _{23}-\mathbf {S} _{12}^{\mathrm {T} }\mathbf {S} _{13}\right),\\\mathbf {S} _{33}&=\mathrm {chol} \left(\mathbf {L} _{33}^{\mathrm {T} }\mathbf {L} _{33}-\mathbf {S} _{23}^{\mathrm {T} }\mathbf {S} _{23}\right).\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}&=\mathrm {chol} \left(\mathbf {S} _{33}^{\mathrm {T} }\mathbf {S} _{33}+\mathbf {S} _{23}^{\mathrm {T} }\mathbf {S} _{23}\right).\end{aligned}}}$

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

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

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

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

Если – положительно определенная матрица , то последовательность состоит из положительно определенных матриц . (Это непосредственное следствие, например, теоремы о спектральном отображении для полиномиального функционального исчисления.) Кроме того, ${\displaystyle \mathbf {A} }$ ${\displaystyle n\times n}$ ${\textstyle \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}\leq \|\mathbf {L} _{k}\mathbf {L} _{k}^{*}\|=\|\mathbf {A} _{k}\|\,.}$

Это справедливо, поскольку алгебра C* снабжена операторной нормой. So — ограниченное множество в банаховом пространстве операторов, поэтому относительно компактное (поскольку базовое векторное пространство конечномерно). Следовательно, она имеет сходящуюся подпоследовательность, также обозначаемую , с пределом . Легко проверить, что он обладает желаемыми свойствами, т. е . является нижнетреугольным с неотрицательными диагональными элементами: для всех и , ${\displaystyle \leq }$ ${\displaystyle M_{n}(\mathbb {C} )}$ ${\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 предоставляет несколько реализаций разложения Холецкого.
• Система компьютерной алгебры Maximacholesky : функция вычисляет разложение Холецкого.
• Система численных вычислений GNU Octave предоставляет несколько функций для расчета, обновления и применения разложения Холецкого.
• Библиотека LAPACK обеспечивает высокопроизводительную реализацию разложения Холецкого, доступ к которой возможен из Fortran , C и большинства языков.
• В Python функция choleskyиз numpy.linalgмодуля выполняет разложение Холецкого.
• В Matlab функция cholдает разложение Холецкого. Обратите внимание, что cholпо умолчанию используется верхний треугольный коэффициент входной матрицы, т.е. он вычисляет, где находится верхний треугольный коэффициент. Вместо этого можно передать флаг, чтобы использовать нижний треугольный коэффициент. ${\displaystyle A=R^{*}R}$ ${\displaystyle R}$
• В R функция cholдает разложение Холецкого.
• В Julia функция choleskyиз LinearAlgebraстандартной библиотеки дает разложение Холецкого.
• В Mathematica функцию « CholeskyDecomposition» можно применить к матрице.
• В C++ несколько библиотек линейной алгебры поддерживают это разложение:
  • Armadillo (библиотека C++) предоставляет команду cholдля выполнения разложения Холецкого.
  • Библиотека Эйгена предоставляет факторизации Холецкого как для разреженных, так и для плотных матриц.
  • В ROOT пакете TDecompCholкласс доступен.

• В Analytica функция Decomposeдает разложение Холецкого.
• Библиотека Apache Commons Math имеет реализацию, которую можно использовать в Java, Scala и любом другом языке JVM.

Смотрите также

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

Примечания

1. Бенуа (1924). «Примечание к методу разрешения нормальных уравнений, происшедшему с применением метода moindres carrés в системе линейных уравнений под нижним номером в celui des inconnues (Procédé du Commandant Cholesky)». Бюллетень Géodésique (на французском языке). 2 : 66–67. дои : 10.1007/BF03031308.
2. Press, Уильям Х.; Саул Алексеевич Теукольский; Уильям Т. Веттерлинг; Брайан П. Фланнери (1992). Численные рецепты в C: Искусство научных вычислений (второе изд.). Кембриджский университет, Англия, Epress. п. 994. ИСБН 0-521-43108-5. Проверено 28 января 2009 г.
3. Голуб и Ван Лоан (1996, стр. 143), Хорн и Джонсон (1985, стр. 407), Трефетен и Бау (1997, стр. 174).
4. Хорн и Джонсон (1985, стр. 407).
5. «Матрицы - Диагонализация сложной симметричной матрицы» . MathOverflow . Проверено 25 января 2020 г.
6. Шабауэр, Ханнес; Пэчер, Кристоф; Сандерленд, Эндрю Г.; Ганстерер, Уилфрид Н. (1 мая 2010 г.). «На пути к параллельному решателю обобщенных сложных симметричных задач на собственные значения». Procedia Информатика . ICCS 2010. 1 (1): 437–445. дои : 10.1016/j.procs.2010.04.047 . ISSN  1877-0509.
7. Голуб и Ван Лоан (1996, стр. 147).
8. Нежный, Джеймс Э. (1998). Численная линейная алгебра для приложений в статистике . Спрингер. п. 94. ИСБН 978-1-4612-0623-1.
9. Хайэм, Николас Дж. (1990). «Анализ разложения Холецкого полуопределенной матрицы». В Коксе, Миннесота; Хаммарлинг, С.Дж. (ред.). Надежные численные вычисления . Оксфорд, Великобритания: Издательство Оксфордского университета. стр. 161–185. ISBN 978-0-19-853564-5.
10. Кришнамурти, Аравинд; Менон, Дипак (2011). «Обращение матрицы с использованием разложения Холецкого». 1111 : 4144. arXiv : 1111.4144 . Бибкод : 2011arXiv1111.4144K. {{cite journal}}: Требуется цитировать журнал |journal=( помощь )
11. Итак, Энтони Ман-Чо (2007). Подход полуопределенного программирования к проблеме реализации графов: теория, приложения и расширения (PDF) (доктор философии). Теорема 2.2.6.
12. Голуб и Ван Лоан (1996, теорема 4.1.3)
13. Поуп, Стивен Б. «Алгоритмы для эллипсоидов». Отчет Корнелльского университета № FDA (2008): 08-01.
14. Арора, Джасбир Сингх (2 июня 2004 г.). Введение в оптимальный дизайн. Эльзевир. ISBN 978-0-08-047025-2.
15. Документация Matlab randn. mathworks.com.
16. ?potrf Библиотека ядра Intel® Math [1]
17. Фанг, Хоурен; О'Лири, Дайан П. (8 августа 2006 г.). «Модифицированные алгоритмы Холецкого: каталог новых подходов» (PDF) . {{cite journal}}: Требуется цитировать журнал |journal=( помощь )
18. Уоткинс, Д. (1991). Основы матричных вычислений . Нью-Йорк: Уайли. п. 84. ИСБН 0-471-61414-9.
19. Носедал, Хорхе (2000). Численная оптимизация . Спрингер.
20. Фанг, Хорен (24 августа 2007 г.). «Анализ блочных факторизаций LDLT для симметричных неопределенных матриц». {{cite journal}}: Требуется цитировать журнал |journal=( помощь )
21. На основе: Стюарт, GW (1998). Основные разложения . Филадельфия: Сок. по промышленной и прикладной математике. ISBN 0-89871-414-1.
22. Осборн, М. (2010), Приложение B.

Рекомендации

• Деренёвский, Дариуш; Кубале, Марек (2004). «Параллельная факторизация матриц Холецкого и ранжирование графов». 5-я Международная конференция по параллельной обработке и прикладной математике (PDF) . Конспекты лекций по информатике. Том. 3019. Шпрингер-Верлаг. стр. 985–992. дои : 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.
• С. Дж. Жюльер и Дж. К. Ульман. «Общий метод аппроксимации нелинейных преобразований вероятностных распределений».
• С. Дж. Жюльер и Дж. К. Ульманн, «Новое расширение фильтра Калмана для нелинейных систем», в Proc. AeroSense: 11-й Международный. Симп. Аэрокосмическое/оборонное зондирование, моделирование и управление, 1997, стр. 182–193.
• Трефетен, Ллойд Н .; Бау, Дэвид (1997). Численная линейная алгебра . Филадельфия: Общество промышленной и прикладной математики. ISBN 978-0-89871-361-9.
• Осборн, Майкл (2010). Байесовские гауссовские процессы для последовательного прогнозирования, оптимизации и квадратуры (PDF) (диссертация). Оксфордский университет.
• Рушель, Жоау Паулу Тараскони, степень бакалавра «Параллельные реализации разложения Холецкого на процессорах и графических процессорах», Федеральный университет Риу-Гранди-ду-Сул, Институт информатики, 2016, стр. 29–30.

Внешние ссылки

История науки

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

Информация

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

Компьютерный код

• LAPACK — это набор подпрограмм FORTRAN для решения задач плотной линейной алгебры (DPOTRF, DPOTRF2, детализация производительности).
• ALGLIB включает частичный порт LAPACK на C++, C#, Delphi, Visual Basic и т. д. (spdmatrixcholesky, hpdmatrixcholesky).
• libflame — это библиотека C с функциональностью LAPACK.
• Заметки и видео о высокопроизводительной реализации факторизации Холецкого в Техасском университете в Остине.
• Cholesky: TBB + Threads + SSE — книга, объясняющая реализацию CF с TBB, потоками и SSE (на испанском языке).
• библиотека «Ceres Solver» от Google.
• Процедуры разложения ЛПНП в Matlab.
• Armadillo — пакет линейной алгебры C++.
• Rosetta Code — сайт по программированию хрестоматии. по теме страницы.
• AlgoWiki — открытая энциклопедия свойств алгоритмов и особенностей их реализации по теме страницы.
• Intel® oneAPI Math Kernel Library Оптимизированная Intel математическая библиотека для числовых вычислений ?potrf, ?potrs

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

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

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

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