Кіріспе
Матрицаның ыдырау әдісі
Сызықтық алгебрада Чолески ыдырауы немесе Чолески факторлауы (/ʃ//ə/'/l//ɛ//s//k//i/ shəLESkee) — Эрмиттік, оң анықталған матрицаны төменгі үшбұрышты матрица мен оның түйіндес транспозының көбейтіндісіне жіктеу. Бұл тиімді сандық есептеулер үшін пайдалы, мысалы, Монте-Карло симуляцияларында. Оны Андре Луи Чолески нақты матрицалар үшін ашқан, ал 1924 жылы оның өлімінен кейін жарияланған. Қолданылатын жағдайларда Чолески ыдырауы сызықтық теңдеулер жүйесін шешу үшін ЛУ ыдырауынан шамамен екі есе тиімді.
In linear algebra, the Cholesky decomposition or Cholesky factorization (pronounced /ʃ//ə/'/l//ɛ//s//k//i/ shəLESkee) is a decomposition of a Hermitian, positive definite matrix into the product of a lower triangular matrix and its conjugate transpose, which is useful for efficient numerical solutions, e. g., Monte Carlo simulations. It was discovered by André Louis Cholesky for real matrices, and posthumously published in 1924. When it is applicable, the Cholesky decomposition is roughly twice as efficient as the LU decomposition for solving systems of linear equations.
Геометриялық түсіндіру
Чолски ыдырауы эллипсоидтың конъюгат осьтерінің нақты бір таңдауымен эквивалентті. Еліпсоидты анықтасақ, , онда анықтама бойынша векторлар жиыны эллипсоидтың конъюгат осьтері болады, егер . Содан кейін, эллипсоид дәл осы жерде беріледі, мұнда негізгі векторді -ға бейнелейді, ал - n өлшемдегі бірлік сфера. Яғни, эллипсоид – бірлік сфераның сызықтық бейнесі. Матрицаны анықтасақ , онда эквивалентті болады. Конъюгат осьтердің әртүрлі таңдаулары әртүрлі ыдырауларға сәйкес келеді. Чолски ыдырауы бірінші оське параллель, екінші оське қатысты жазықтықта және т.б. таңдауларға сәйкес келеді. Бұл оны жоғарғы үшбұрышты матрицаға айналдырады. Онда , ал төменгі үшбұрышты матрица. Сол сияқты, бас компоненттерді талдау конъюгат осьтерді перпендикуляр таңдауға сәйкес келеді. Содан кейін, және , болсын, және ортогоналды матрица. Осыдан шығады.
Сызықтық теңдеулер жүйесінің сандық шешімі
Чолски ыдырауы негізінен сызықтық теңдеулерді сандық түрде шешу үшін қолданылады. Егер A матрицасы симметриялық және оң анықталған болса, онда ол алдымен Чолски ыдырауын есептеу арқылы, содан кейін y-ді тікелей қою арқылы, және соңында x-ті кері қою арқылы шешіледі. Чолски ыдырауындағы квадрат түбірді алудан бас тартудың балама жолы – LDL ыдырауын есептеу, содан кейін y-ді шешу және ақырында x-ті табу болып табылады. Симметриялық түрге келтірілген сызықтық жүйелер үшін Чолски ыдырауы (немесе оның LDL түрі) жоғары тиімділік және сандық тұрақтылықты қамтамасыз ететіндіктен, басымдыққа ие әдіс болып табылады. LU ыдырауымен салыстырғанда, ол шамамен екі есе тиімді.
For linear systems that can be put into symmetric form, the Cholesky decomposition (or its LDL variant) is the method of choice, for superior efficiency and numerical stability. Compared to the LU decomposition, it is roughly twice as efficient.
Монте-Карло симуляциясы
Чолески ыдырауы көбінесе Монте-Карло әдісінде көптеген өзара байланысты айнымалылары бар жүйелерді модельдеу үшін қолданылады. Ковариациялық матрица төменгі үшбұрышты L матрицасын алу үшін ыдырайды. Бұл матрицаны корреляцияланбаған үлгілер векторына қолданғанда, модельделетін жүйенің ковариациялық қасиеттеріне ие Lu үлгі векторы пайда болады. Келесі қарапайым мысал Чолески ыдырауының тиімділігін көрсетеді: егер мақсат екі корреляцияланған қалыпты айнымалыны және берілген корреляциялық коэффициентін жасау болса, онда алдымен екі корреляцияланбаған Гаусс кездейсоқ айнымалысын жасау қажет, мысалы және , бұл Box-Muller түрлендіруін қолдану арқылы жасалуы мүмкін. Қажетті корреляциялық коэффициент берілген жағдайда, корреляцияланған қалыпты айнымалыларды мына түрлендірулер арқылы алуға болады: және .
Калман сүзгілері
Иіссіз Калман сүзгілері әдетте «сигма нүктелері» деп аталатын жиынды таңдау үшін Чолески ыдырауын қолданады. Калман сүзгісі жүйенің орташа күйін N ұзындығындағы x векторы және N × N матрицасы P түріндегі ковариациясы ретінде бақылайды. P матрицасы әрқашан оң жартылай анықталған және LLT түрінде ыдыратылуы мүмкін. L матрицасының бағаналарын орташа x-ке қосу және алу арқылы «сигма нүктелері» деп аталатын 2N вектордан тұратын жиынтық құралады. Бұл сигма нүктелері жүйе күйінің орташа мәні мен ковариациясын толыққанды қамтиды.
Матрицалық инверсия
Гермиттік матрицаның нақты керісін Чолески ыдырауы арқылы, сызықтық жүйелерді шешуге ұқсас әдіспен есептеуге болады, бұл операциялар (көбейтулер) қажет етеді, мұндағы n – A матрицасының өлшемі. Осылайша, олар 2n³/3 FLOP қолданатын LU ыдырауынан екі есе арзанға түседі (Trefethen және Bau, 1997 қараңыз). Төмендегі алгоритмдердің қайсысы жылдамырақ болатыны – іске асылу ерекшеліктеріне байланысты. Әдетте, бірінші алгоритм деректерге нашар реттелген тәртіппен қол жеткізгендіктен, сәл баяу болады.
Есептеудің тұрақтылығы
Сызықтық теңдеулердің жақсы шартталған жүйесін шешуге ниеттілік болсын делік. Егер LU ыдырауы қолданылса, онда айналдыру стратегиясы қолданылмаса, алгоритм тұрақсыз болады. Соңғы жағдайда қате матрицаның өсу факторы деп аталатын, әдетте (бірақ әрдайым емес) кішкентай болатын шамаға байланысты. Енді, Чолски ыдырауы қолданыла алады делік. Жоғарыда айтылғандай, алгоритм екі есе жылдам болады. Сонымен қатар, айналдыру қажет емес және қате әрқашан кіші болады. Атап айтқанда, егер Ax = b, ал y есептелген шешімді білдірсе, онда y (A + E)y = b теңдеуін шешеді, мұндағы ||·||2 – матрицаның 2-ші нормасы, cn – n-ге тәуелді кішкентай тұрақты, ал ε – бірлікті дөңгелектеу қатесін білдіреді. Чолски ыдырауын қолдану кезінде ескеру керек бір мәселе – квадрат түбірлерді қолдану. Егер ыдыратылатын матрица талап етілгендей оң анықталған болса, квадрат түбірлер астындағы сандар нақты арифметикада әрқашан оң болады. Өкінішке орай, дөңгелектеу қателерінің салдарынан сандар теріс болуы мүмкін, бұл жағдайда алгоритм жалғаса алмайды. Алайда, бұл тек матрицаның өте нашар шартталған жағдайда ғана болуы мүмкін. Мұны шешудің бір жолы – ыдыратылатын матрицаға диагональдық түзету матрицасын қосу арқылы оң анықтығын арттыру. Бұл ыдыраудың дәлдігін төмендетуі мүмкін, бірақ басқа себептермен де тиімді болуы мүмкін; мысалы, оңтайландыруда Нютон әдісін қолданғанда, диагональдық матрицаны қосу оптимал нүктеден алыс болғанда тұрақтылықты жақсарта алады.
Here ||·||2 is the matrix 2 norm, cn is a small constant depending on n, and ε denotes the unit round off. One concern with the Cholesky decomposition to be aware of is the use of square roots. If the matrix being factorized is positive definite as required, the numbers under the square roots are always positive in exact arithmetic. Unfortunately, the numbers can become negative because of round off errors, in which case the algorithm cannot continue. However, this can only happen if the matrix is very ill conditioned. One way to address this is to add a diagonal correction matrix to the matrix being decomposed in an attempt to promote the positive definiteness. While this might lessen the accuracy of the decomposition, it can be very favorable for other reasons; for example, when performing Newton's method in optimization, adding a diagonal matrix can improve stability when far from the optimum.
Блоктық нұсқа
Белгісіз матрицаларда қолданылғанда, LDL* факторлануы мұқият айналмаса тұрақсыз екені мәлім; атап айтқанда, факторлану элементтері шексіз өсе алуы мүмкін. Мүмкін болатын жақсарту – блок субматрицаларда, көбінесе 2 × 2 өлшемді блоктарда факторлауды жүргізу:
мұнда жоғарыда көрсетілген матрицалардың әрқайсысы квадрат субматрица болып табылады. Осыдан келесідей ұқсас рекурсивті байланыстар туындайды:
Бұл матрица көбейтулерді және тікелей инверсияны қамтиды, соның салдарынан практикалық блок өлшемі шектеледі.
Орындылықтарды жаңарту
Практикада жиі кездесетін мәселе – Чолески ыдырауын жаңарту қажеттігі. Нақтырақ айтқанда, егер сіз қандайда бір матрицаның Чолески ыдырауын есептеген болсаңыз, содан кейін матрицаны бір жолмен өзге матрицаға өзгертіп, жаңартылған матрицаның Чолески ыдырауын есептегіңіз келсе, бұрын есептелген матрицаның Чолески ыдырауын пайдаланып, жаңа матрицаның Чолески ыдырауын есептеуге бола ма деген сұрақ туындайды.
Бірінші орынға ие
Бірінші рангілі төмендету, бірінші рангілі жаңартуға ұқсас, бірақ қосу операциясы шегерілумен алмастырылады: Бұл жаңа матрица оң анықталған болса ғана жұмыс істейді. Жоғарыда көрсетілген бірінші рангілі жаңарту кодын бірінші рангілі төмендетуге оңай бейімдеуге болады: r және L((k+1):n, k) мәніне берілетін екі қосуды шегерілумен ауыстыру жеткілікті.
Шектеу аргументі арқылы дәлелдеу
Жоғарыда келтірілген алгоритмдер әрбір оң белгілі матрицаның Чолески ыдырауын көрсетеді. Бұл нәтиже шектеу аргументі арқылы оң жартылай белгілі жағдайға кеңейтілуі мүмкін. Бұл аргумент толыққанды конструктивті емес, яғни ол Чолески факторларын есептеу үшін нақты сандық алгоритмдерді ұсынбайды. Егер оң жартылай белгілі матрица болса, онда тізбегі оң белгілі матрицалардан тұрады. (Бұл, мысалы, полиномдық функционалдық есептеу үшін спектралды бейнелеу теоремасының тікелей салдары.) Сондай-ақ, операторлық нормада. Оң белгілі жағдайда, әрбір Чолески ыдырауына ие. Операторлық норманың қасиеттеріне сәйкес, операторлық нормамен жабдықталған C* алгебра болып табылады. Сондықтан, операторлардың Банах кеңістігіндегі шектелген жиын, демек, салыстырмалы түрде тығыз (негізгі векторлық кеңістік шекті өлшемді болғандықтан). Осының салдарынан, ол шегімен конвергентті кіші тізбекке ие, сонымен қатар . Бұл қажетті қасиеттерге ие екенін оңай тексеруге болады, яғни , және оң жартылай белгілі диагональдық элементтерімен төменгі үшбұрышты: барлық және үшін.
in operator norm. From the positive definite case, each has Cholesky decomposition By property of the operator norm,
The holds because equipped with the operator norm is a C* algebra. So is a bounded set in the Banach space of operators, therefore relatively compact (because the underlying vector space is finite dimensional). Consequently, it has a convergent subsequence, also denoted by , with limit
It can be easily checked that this has the desired properties, i. e. , and is lower triangular with non negative diagonal entries: for all and ,
Therefore,
Because the underlying vector space is finite dimensional, all topologies on the space of operators are equivalent. So tends to in norm means tends to entrywise. This in turn implies that, since each is lower triangular with non negative diagonal entries, is also.
Осыдан келіп, . Негізгі векторлық кеңістік шекті өлшемді болғандықтан, операторлар кеңістігіндегі барлық топологиялар эквивалентті. Сондықтан, норма бойынша -қа жақындасады дегеніміз, элемент бойынша -ға жақындасады дегенді білдіреді. Бұл өз кезегінде, әрбір оң жартылай белгілі диагональдық элементтерімен төменгі үшбұрышты болғандықтан, де солай болады дегенді білдіреді.
in operator norm. From the positive definite case, each has Cholesky decomposition By property of the operator norm,
The holds because equipped with the operator norm is a C* algebra. So is a bounded set in the Banach space of operators, therefore relatively compact (because the underlying vector space is finite dimensional). Consequently, it has a convergent subsequence, also denoted by , with limit
It can be easily checked that this has the desired properties, i. e. , and is lower triangular with non negative diagonal entries: for all and ,
Therefore,
Because the underlying vector space is finite dimensional, all topologies on the space of operators are equivalent. So tends to in norm means tends to entrywise. This in turn implies that, since each is lower triangular with non negative diagonal entries, is also.
QR ыдырау арқылы дәлелдеу
Оң жартылай анықталған Эрмиттік матрица болсын. Онда оны оның түбір матрицасының көбейтіндісі ретінде жазуға болады. Енді QR жіктелуін қолдануға болады, нәтижесінде , мұнда – унитарлық, ал – жоғарғы үшбұрышты матрица. Бұл жіктелуді бастапқы теңдікке енгізу келесіні береді. деп белгілесек, дәлелдеме аяқталады.
, where is unitary and is upper triangular. Inserting the decomposition into the original equality yields Setting completes the proof.
Онлайн калькуляторлар
Онлайн матрицалық калькулятор матрицалардың Холецкий жіктелуін онлайн режимінде жүзеге асырады.