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

Метод разложения матрицы

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

Заявление

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

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

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

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

Когда A — действительная матрица (следовательно, симметричная положительно определенная), факторизация может быть записана так, где L — действительная нижняя треугольная матрица с положительными диагональными элементами. ^{[4] [5] [6]} $${\displaystyle \mathbf {A} =\mathbf {LL} ^{\mathsf {T}},}$$

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

Если эрмитова матрица A является только положительно полуопределенной, а не положительно определенной, то она все равно имеет разложение вида A = LL * , где диагональные элементы L могут быть равны нулю. ^[7] Разложение не обязательно должно быть уникальным, например: для любого θ . Однако, если ранг A равен r , то существует уникальный нижний треугольный L с ровно r положительными диагональными элементами и n − r столбцами, содержащими все нули. ^[8] $${\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 является положительно полуопределенной матрицей n × n ранга r , то существует по крайней мере одна матрица перестановки P такая, что PAP ^T имеет уникальное разложение вида PAP ^T = LL ^* с , где L ₁ является нижней треугольной матрицей r × r с положительной диагональю. ^[9] ${\textstyle \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 может быть вычислено и использовано по сути с теми же алгоритмами, но избегает извлечения квадратных корней. ^[10]

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

Разложение LDL связано с классическим разложением Холецкого вида 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 можно разложить следующим образом (это изменяет масштаб каждого столбца, делая диагональные элементы равными 1), ${\textstyle \mathbf {A} =\mathbf {C} \mathbf {C} ^{*}}$ ${\textstyle \mathbf {C} }$ ${\textstyle \mathbf {L} \mathbf {D} \mathbf {L} ^{*}}$ $${\displaystyle \mathbf {L} =\mathbf {C} \mathbf {S} ^{-1}}$$ $${\displaystyle \mathbf {D} =\mathbf {S} ^{2}.}$$

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

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

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

Разложение Холецкого эквивалентно конкретному выбору сопряженных осей эллипсоида . ^[13] Подробно, пусть эллипсоид определен как , тогда по определению набор векторов является сопряженными осями эллипсоида тогда и только тогда . Тогда эллипсоид находится в точности там , где отображает базисный вектор , и является единичной сферой в n измерениях. То есть эллипсоид является линейным образом единичной сферы. ${\textstyle y^{T}Ay=1}$ ${\textstyle v_{1},...,v_{n}}$ ${\textstyle v_{i}^{T}Av_{j}=\delta _{ij}}$ $${\displaystyle \left\{\sum _{i}x_{i}v_{i}:x^{T}x=1\right\}=f(\mathbb {S} ^{n})}$$ ${\textstyle f}$ ${\textstyle e_{i}\mapsto v_{i}}$ ${\textstyle \mathbb {S} ^{n}}$

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

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

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

Приложения

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

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

Альтернативный способ исключить извлечение квадратных корней при разложении — вычислить разложение ЛПНП , затем найти решение относительно y и, наконец, решить . ${\textstyle \mathbf {LL} ^{\mathrm {*} }}$ ${\textstyle \mathbf {A} =\mathbf {LDL} ^{\mathrm {*} }}$ ${\textstyle \mathbf {Ly} =\mathbf {b} }$ ${\textstyle \mathbf {DL} ^{\mathrm {*} }\mathbf {x} =\mathbf {y} }$

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

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

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

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

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

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

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

Следующий упрощенный пример показывает экономию, которую можно получить от разложения Холецкого: предположим, что цель состоит в том, чтобы сгенерировать две коррелированные нормальные переменные и с заданным коэффициентом корреляции . Для этого необходимо сначала сгенерировать две некоррелированные гауссовские случайные величины и (например, с помощью преобразования Бокса–Мюллера ). При заданном коэффициенте корреляции коррелированные нормальные переменные могут быть получены с помощью преобразований и . ${\textstyle x_{1}}$ ${\textstyle x_{2}}$ ${\textstyle \rho }$ ${\textstyle z_{1}}$ ${\textstyle z_{2}}$ ${\textstyle \rho }$ ${\textstyle 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] Полное обращение может быть даже эффективно выполнено на месте. ${\textstyle n^{3}}$ ${\textstyle {\tfrac {1}{2}}n^{3}}$

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

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

Вычисление

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

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

Алгоритм Холецкого

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

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

А ⁽¹⁾  := А .

На шаге i матрица A ^{( i )} имеет следующий вид: где I _{i −1} обозначает единичную матрицу размерности i − 1 . $${\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}},}$$

Если матрица L _i определяется как (обратите внимание, что a _i,i > 0 , поскольку A ^{( i )} положительно определена), то A ^{( i )} можно записать как, где Обратите внимание, что b _i b * _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}},}$$ $${\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}}.}$$

Это повторяется для 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.}$$

Для комплексных и действительных матриц допускаются несущественные произвольные изменения знаков диагональных и связанных недиагональных элементов. Выражение под квадратным корнем всегда положительно, если 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_{j,k}^{*}L_{i,k}\right)\quad {\text{for }}i>j.}$$

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

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

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

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

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

где conjgотносится к комплексному сопряжению элементов.

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

  для ( j = 0 ; j < dimensionSize ; j ++ ) { float sum = 0 ; для ( k = 0 ; k < j ; k ++ ) { sum += L [ j ][ k ] * L [ j ][ k ]; } L [ j ][ j ] = sqrt ( A [ j ][ j ] - sum );                                 для ( i = j + 1 ; i < dimensionSize ; i ++ ) { сумма = 0 ; для ( k = 0 ; k < j ; k ++ ) { сумма += L [ i ][ k ] * L [ j ][ k ]; } L [ i ][ j ] = ( 1,0 / L [ j ][ j ] * ( A [ i ][ j ] - сумма )); } }                                      

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

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

где conjgотносится к комплексному сопряжению элементов.

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

Устойчивость вычислений

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

Теперь предположим, что применимо разложение Холецкого. Как упоминалось выше, алгоритм будет в два раза быстрее. Более того, не требуется поворот , и ошибка всегда будет небольшой. В частности, если Ax = b , а y обозначает вычисленное решение, то y решает возмущенную систему ( A + E ) y = b , где Здесь ||·|| ₂ — матричная 2-норма , c _n — малая константа, зависящая от n , а ε обозначает округление до единицы . $${\displaystyle \|\mathbf {E} \|_{2}\leq c_{n}\varepsilon \|\mathbf {A} \|_{2}.}$$

Одной из проблем, связанных с разложением Холецкого, о которой следует знать, является использование квадратных корней. Если факторизуемая матрица является положительно определенной, как и требуется, числа под квадратными корнями всегда положительны в точной арифметике . К сожалению, числа могут стать отрицательными из-за ошибок округления , в этом случае алгоритм не может продолжать работу. Однако это может произойти только в том случае, если матрица очень плохо обусловлена. Одним из способов решения этой проблемы является добавление диагональной матрицы коррекции к разлагаемой матрице в попытке повысить положительную определенность. ^[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}.}$$

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

Обновление разложения

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

Обновление рейтинга один

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

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

функция  [L] = cholupdate ( L, x ) n = длина ( 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 ( k , k ) = r ; если k < n L (( k + 1 ): n , k ) = ( L (( k + 1 ): n , k ) + s * x (( k + 1 ): n )) / c ; x (( k + 1 ): n ) = c * x (( k + 1 ): n ) - s * L (( k + 1 ): n , k ); конец конец конец                                                          

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

Понижение рейтинга на один

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

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

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

Если симметричная и положительно определенная матрица представлена ​​в блочной форме как ${\textstyle \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}},}$$

затем для новой матрицы , которая является такой же, но со вставкой новых строк и столбцов, ${\textstyle {\tilde {\mathbf {A} }}}$ ${\textstyle \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}}}$$

Теперь возникает интерес к нахождению факторизации Холецкого , которую можно назвать , без непосредственного вычисления всего разложения. ${\textstyle {\tilde {\mathbf {A} }}}$ ${\textstyle {\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}}}$$

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

матрицы с удаленными строками и столбцами, ${\textstyle \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] ${\textstyle {\tilde {\mathbf {A} }}=\mathbf {A} \pm \mathbf {x} \mathbf {x} ^{*}}$

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

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

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

Если — положительно полуопределенная матрица , то последовательность состоит из положительно определенных матриц . (Это является непосредственным следствием, например, теоремы о спектральном отображении для полиномиального функционального исчисления.) Также в операторной норме . Из положительно определенного случая каждая имеет разложение Холецкого . По свойству операторной нормы, ${\textstyle \mathbf {A} }$ ${\textstyle 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 }$$ ${\textstyle \mathbf {A} _{k}}$ ${\textstyle \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*. Так же является ограниченным множеством в банаховом пространстве операторов, поэтому относительно компактным (потому что лежащее в основе векторное пространство конечномерно). Следовательно, у него есть сходящаяся подпоследовательность, также обозначаемая как , с пределом . Можно легко проверить, что это имеет требуемые свойства, т. е . , и является нижнетреугольным с неотрицательными диагональными элементами: для всех и , ${\textstyle \leq }$ ${\textstyle M_{n}(\mathbb {C} )}$ ${\textstyle \left(\mathbf {L} _{k}\right)_{k}}$ ${\textstyle \left(\mathbf {L} _{k}\right)_{k}}$ ${\textstyle \mathbf {L} }$ ${\textstyle \mathbf {L} }$ ${\textstyle \mathbf {A} =\mathbf {L} \mathbf {L} ^{*}}$ ${\textstyle \mathbf {L} }$ ${\textstyle x}$ ${\textstyle 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 \,.}$$

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

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

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

Обобщение

Факторизация Холецкого может быть обобщена ^{[ требуется ссылка ]} на (не обязательно конечные) матрицы с операторными записями. Пусть будет последовательностью гильбертовых пространств . Рассмотрим операторную матрицу ${\textstyle \{{\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 положительными. ${\textstyle \langle h,\mathbf {A} h\rangle \geq 0}$

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

• Язык программирования C : научная библиотека GNU предоставляет несколько реализаций разложения Холецкого.
• Система компьютерной алгебры Maximacholesky : функция вычисляет разложение Холецкого.
• Система численных вычислений GNU Octave предоставляет несколько функций для расчета, обновления и применения разложения Холецкого.
• Библиотека LAPACK обеспечивает высокопроизводительную реализацию разложения Холецкого, доступ к которой можно получить из Fortran , C и большинства языков.
• В Python функция choleskyиз numpy.linalgмодуля выполняет разложение Холецкого.
• В Matlab функция cholдает разложение Холецкого. Обратите внимание, что cholпо умолчанию используется верхний треугольный фактор входной матрицы, т.е. она вычисляет , где является верхним треугольным. Можно передать флаг, чтобы вместо этого использовать нижний треугольный фактор. ${\textstyle A=R^{*}R}$ ${\textstyle R}$
• В R функция cholдает разложение Холецкого.
• В Julia функция choleskyиз LinearAlgebraстандартной библиотеки дает разложение Холецкого.
• В системе Mathematica функцию « CholeskyDecomposition» можно применить к матрице.
• В C++ несколько библиотек линейной алгебры поддерживают такую ​​декомпозицию:
  • Armadillo (библиотека C++) предоставляет команду cholдля выполнения разложения Холецкого.
  • Библиотека Eigen предоставляет разложения Холецкого как для разреженных, так и для плотных матриц.
  • В пакете ROOTTDecompChol класс доступен.

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

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

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

Примечания

1. Бенуа (1924). «Примечание к методу разрешения нормальных уравнений, происшедшему с применением метода moindres carrés à un système d'équations linéaires en nombre inférieur à celui des inconnues (Procédé du Commandant Cholesky)». Бюллетень Géodesique (на французском языке). 2 : 66–67. дои : 10.1007/BF03031308.
2. Press, William H.; Saul A. Teukolsky; William T. Vetterling; Brian P. Flannery (1992). Numerical Recipes in C: The Art of Scientific Computing (второе изд.). Cambridge University England EPress. стр. 994. ISBN 0-521-43108-5. Получено 28.01.2009 .
3. Голуб и Ван Лоан (1996, стр. 143), Хорн и Джонсон (1985, стр. 407), Трефетен и Бау (1997, стр. 174).
4. Хорн и Джонсон (1985, стр. 407).
5. "матрицы - Диагонализация комплексной симметричной матрицы". MathOverflow . Получено 2020-01-25 .
6. Шабауэр, Ханнес; Пахер, Кристоф; Сандерленд, Эндрю Г.; Ганстерер, Вильфрид Н. (2010-05-01). «К параллельному решателю для обобщенных комплексных симметричных задач на собственные значения». Procedia Computer Science . ICCS 2010. 1 (1): 437–445. doi : 10.1016/j.procs.2010.04.047 . ISSN  1877-0509.
7. Голуб и Ван Лоан (1996, стр. 147).
8. Джентл, Джеймс Э. (1998). Численная линейная алгебра для приложений в статистике . Springer. стр. 94. ISBN 978-1-4612-0623-1.
9. Хайэм, Николас Дж. (1990). «Анализ разложения Холецкого полуопределенной матрицы». В Коксе, МГ; Хаммарлинге, СДж (ред.). Надежные численные вычисления . Оксфорд, Великобритания: Oxford University Press. стр. 161–185. ISBN 978-0-19-853564-5.
10. Krishnamoorthy, Aravindh; Menon, Deepak (2011). «Обращение матрицы с использованием разложения Холецкого». 1111 : 4144. arXiv : 1111.4144 . Bibcode :2011arXiv1111.4144K. {{cite journal}}: Цитировать журнал требует |journal=( помощь )
11. Так, Энтони Ман-Чо (2007). Подход полуопределенного программирования к проблеме реализации графа: теория, приложения и расширения (PDF) (PhD). Теорема 2.2.6.
12. Голуб и Ван Лоан (1996, Теорема 4.1.3)
13. Поуп, Стивен Б. «Алгоритмы для эллипсоидов». Отчет Корнелльского университета № FDA (2008): 08-01.
14. Арора, Джасбир Сингх (2004-06-02). Введение в оптимальное проектирование. Elsevier. ISBN 978-0-08-047025-2.
15. Документация Matlab randn. mathworks.com.
16. ?potrf Библиотека Intel® Math Kernel [1]
17. Фанг, Хоу-рен; О'Лири, Дайан П. (8 августа 2006 г.). «Модифицированные алгоритмы Холецкого: каталог с новыми подходами» (PDF) . {{cite journal}}: Цитировать журнал требует |journal=( помощь )
18. Уоткинс, Д. (1991). Основы матричных вычислений . Нью-Йорк: Wiley. стр. 84. ISBN 0-471-61414-9.
19. Нокедаль, Хорхе (2000). Численная оптимизация . Springer.
20. Фанг, Хоу-рен (24 августа 2007 г.). «Анализ блочных факторизаций LDLT для симметричных неопределенных матриц». {{cite journal}}: Цитировать журнал требует |journal=( помощь )
21. На основе: Stewart, GW (1998). Базовые разложения . Филадельфия: Soc. for Industrial and Applied Mathematics. ISBN 0-89871-414-1.
22. Осборн, М. (2010), Приложение B.

Ссылки

• Dereniowski, Dariusz; Kubale, Marek (2004). "Cholesky Factorization of Matrices in Parallel and Ranking of Graphs". 5-я Международная конференция по параллельной обработке и прикладной математике (PDF) . Lecture Notes on Computer Science. Vol. 3019. Springer-Verlag. pp. 985–992. doi :10.1007/978-3-540-24669-5_127. ISBN 978-3-540-21946-0. Архивировано из оригинала (PDF) 2011-07-16.
• Голуб, Джин Х.; Ван Лоан, Чарльз Ф. (1996). Матричные вычисления (3-е изд.). Балтимор: Университет Джонса Хопкинса. ISBN 978-0-8018-5414-9.
• Хорн, Роджер А.; Джонсон, Чарльз Р. (1985). Матричный анализ . Cambridge University Press. ISBN 0-521-38632-2.
• SJ Julier и JK Uhlmann. «Общий метод аппроксимации нелинейных преобразований распределений вероятностей».
• SJ Julier и JK Uhlmann, «Новое расширение фильтра Калмана для нелинейных систем», в Proc. AeroSense: 11th Int. Symp. Aerospace/Defence Sensing, Simulation and Controls, 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
• Разложение Холецкого стало проще на Science Meanderthal

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

• 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

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

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

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

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