Разложение Холецкого
Разложе́ние Холе́цкого — представление симметричной положительно-определённой матрицы <math>A</math> в виде <math>A = LL^T</math>, где <math>L</math> — нижняя треугольная матрица со строго положительными элементами на диагонали. Иногда разложение записывается в эквивалентной форме: <math>A = U^TU</math>, где <math>U = L^T</math> — верхняя треугольная матрица. Разложение Холецкого всегда существует и единственно для любой симметричной положительно-определённой матрицы.
Существует также обобщение этого разложения на случай комплекснозначных матриц. Если <math>A</math> — положительно-определённая эрмитова матрица, то существует разложение <math>A = LL^*</math>, где <math>L</math> — нижняя треугольная матрица с положительными действительными элементами на диагонали, а <math>L^*</math> — эрмитово-сопряжённая к ней матрица.
Разложение названо в честь французского математика Андре-Луи Холецкого (1875-1918).
Алгоритм
Элементы матрицы <math>L</math> можно вычислить, начиная с верхнего левого угла матрицы, по формулам:
- <math>L_{ii} = \sqrt{A_{ii} - \sum_{k=1}^{i-1} L_{ik}^2}</math>
- <math>L_{ij} = \frac{1}{L_{jj}} \left(A_{ij} - \sum_{k=1}^{j-1} L_{ik} L_{jk} \right)</math>, если <math>j < i</math>.
Выражение под корнем всегда положительно, если <math>A</math> — действительная положительно-определённая матрица.
Вычисление происходит сверху вниз, слева направо, т.е. сперва <math>L_{ii}</math>, а затем <math>L_{ij}</math>.
Для комплекснозначных эрмитовых матриц используются формулы:
- <math>L_{ii} = \sqrt{ A_{ii} - \sum_{k=1}^{i-1} L_{ik}L_{ik}^* }</math>
- <math>L_{ij} = \frac{1}{L_{jj}} \left( A_{ij} - \sum_{k=1}^{j-1} L_{ik} L_{jk}^* \right)</math>, если <math>j < i</math>.
Приложения
Это разложение может применяться для решения системы линейных уравнений <math>Ax = b</math>, если матрица <math>A</math> симметрична и положительно-определена. Такие матрицы часто возникают, например, при использовании метода наименьших квадратов и численном решении дифференциальных уравнений.
Выполнив разложение <math>A = LL^T</math>, решение <math>x</math> получается последовательным решением двух треугольных систем уравнений: <math>Ly = b</math> и <math>L^T x = y</math>. Такой способ решения иногда называется методом квадратных корней.[1] По сравнению с более общими методами, такими как метод Гаусса или LU-разложение, он устойчивее численно и требует примерно вдвое меньше арифметических операций. [2]
Разложение Холецкого также применяется в методах Монте-Карло для генерации коррелированных случайных величин. Пусть <math>X</math> — вектор из независимых стандартных нормальных случайных величин, а <math>\Sigma = LL^T</math> — желаемая ковариационная матрица. Тогда вектор <math>Y = LX</math> будет иметь многомерное нормальное распределение с нулевым математическим ожиданием и ковариационной матрицей <math>\Sigma</math>. [3]
Реализация в математических пакетах программ
- В SAS используется функция ROOT( matrix ), входящая в пакет SAS IML.
- В системах MATLAB, Octave, R разложение выполняется командой U = chol(A).
- В Maple и NumPy существует процедура cholesky в модуле linalg.
- В Mathematica используется процедура CholeskyDecomposition[A].
- В MathCAD для разложения используется функция cholesky(A)
- В GSL используется функция gsl_linalg_cholesky_decomp.
- В библиотеке от Google [code.google.com/p/ceres-solver/ ceres-solver]</tt>.
Напишите отзыв о статье "Разложение Холецкого"
Примечания
- ↑ Вержбицкий В. М. Основы численных методов. — М.: Высшая школа, 2009. — 840 с. — ISBN 9785060061239.
- ↑ William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. [www.haoli.org/nr/bookcpdf/c2-9.pdf 2.9 Cholesky Decomposition] // Numerical Recipes in C. — 2nd edition. — Cambridge: Cambridge University Press. — ISBN 0-521-43108-5.
- ↑ Martin Haugh. [www.columbia.edu/~mh2078/MCS04/MCS_framework_FEegs.pdf Generating Correlated Random Variables].
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||
Отрывок, характеризующий Разложение Холецкого
Наташа подала ему руку и вышла. Княжна Марья, напротив, вместо того чтобы уйти, опустилась в кресло и своим лучистым, глубоким взглядом строго и внимательно посмотрела на Пьера. Усталость, которую она очевидно выказывала перед этим, теперь совсем прошла. Она тяжело и продолжительно вздохнула, как будто приготавливаясь к длинному разговору.Все смущение и неловкость Пьера, при удалении Наташи, мгновенно исчезли и заменились взволнованным оживлением. Он быстро придвинул кресло совсем близко к княжне Марье.
– Да, я и хотел сказать вам, – сказал он, отвечая, как на слова, на ее взгляд. – Княжна, помогите мне. Что мне делать? Могу я надеяться? Княжна, друг мой, выслушайте меня. Я все знаю. Я знаю, что я не стою ее; я знаю, что теперь невозможно говорить об этом. Но я хочу быть братом ей. Нет, я не хочу.. я не могу…
Он остановился и потер себе лицо и глаза руками.
– Ну, вот, – продолжал он, видимо сделав усилие над собой, чтобы говорить связно. – Я не знаю, с каких пор я люблю ее. Но я одну только ее, одну любил во всю мою жизнь и люблю так, что без нее не могу себе представить жизни. Просить руки ее теперь я не решаюсь; но мысль о том, что, может быть, она могла бы быть моею и что я упущу эту возможность… возможность… ужасна. Скажите, могу я надеяться? Скажите, что мне делать? Милая княжна, – сказал он, помолчав немного и тронув ее за руку, так как она не отвечала.
– Я думаю о том, что вы мне сказали, – отвечала княжна Марья. – Вот что я скажу вам. Вы правы, что теперь говорить ей об любви… – Княжна остановилась. Она хотела сказать: говорить ей о любви теперь невозможно; но она остановилась, потому что она третий день видела по вдруг переменившейся Наташе, что не только Наташа не оскорбилась бы, если б ей Пьер высказал свою любовь, но что она одного только этого и желала.
– Говорить ей теперь… нельзя, – все таки сказала княжна Марья.
– Но что же мне делать?
– Поручите это мне, – сказала княжна Марья. – Я знаю…
Пьер смотрел в глаза княжне Марье.
– Ну, ну… – говорил он.
– Я знаю, что она любит… полюбит вас, – поправилась княжна Марья.
Не успела она сказать эти слова, как Пьер вскочил и с испуганным лицом схватил за руку княжну Марью.
– Отчего вы думаете? Вы думаете, что я могу надеяться? Вы думаете?!
– Да, думаю, – улыбаясь, сказала княжна Марья. – Напишите родителям. И поручите мне. Я скажу ей, когда будет можно. Я желаю этого. И сердце мое чувствует, что это будет.
– Нет, это не может быть! Как я счастлив! Но это не может быть… Как я счастлив! Нет, не может быть! – говорил Пьер, целуя руки княжны Марьи.
– Вы поезжайте в Петербург; это лучше. А я напишу вам, – сказала она.
– В Петербург? Ехать? Хорошо, да, ехать. Но завтра я могу приехать к вам?
На другой день Пьер приехал проститься. Наташа была менее оживлена, чем в прежние дни; но в этот день, иногда взглянув ей в глаза, Пьер чувствовал, что он исчезает, что ни его, ни ее нет больше, а есть одно чувство счастья. «Неужели? Нет, не может быть», – говорил он себе при каждом ее взгляде, жесте, слове, наполнявших его душу радостью.
Когда он, прощаясь с нею, взял ее тонкую, худую руку, он невольно несколько дольше удержал ее в своей.
«Неужели эта рука, это лицо, эти глаза, все это чуждое мне сокровище женской прелести, неужели это все будет вечно мое, привычное, такое же, каким я сам для себя? Нет, это невозможно!..»
– Прощайте, граф, – сказала она ему громко. – Я очень буду ждать вас, – прибавила она шепотом.
И эти простые слова, взгляд и выражение лица, сопровождавшие их, в продолжение двух месяцев составляли предмет неистощимых воспоминаний, объяснений и счастливых мечтаний Пьера. «Я очень буду ждать вас… Да, да, как она сказала? Да, я очень буду ждать вас. Ах, как я счастлив! Что ж это такое, как я счастлив!» – говорил себе Пьер.
В душе Пьера теперь не происходило ничего подобного тому, что происходило в ней в подобных же обстоятельствах во время его сватовства с Элен.
