Матрицаның өзіндік мәндерін есептеуге арналған сандық әдістер

Кіріспе

Матрицаның өзіндік мәнін есептеуге арналған сандық әдістер. Сандық талдаудағы маңызды мәселелердің бірі – матрицаның өзіндік мәндерін табу үшін тиімді және тұрақты алгоритмдерді жасау. Бұл өзіндік мәнді есептеу алгоритмдері өзіндік векторларды да анықтай алады.

Нормалды, Гермиттік және нақты симметриялық матрицалар

М комплекстік матрицаның M^(*) – M-нің түйіндес конъюгатының транспозыциясы: A квадраттық матрицасы, егер ол өзінің косымшасымен коммутацияласа, қалыпты деп аталады: 1=A^(*) A = AA^(*). Егер ол өзінің косымшасына тең болса, онда ол гермиттік деп аталады: 1=A^(*) = A. Барлық гермиттік матрицалар қалыпты. Егер А тек нақты элементтерден тұрса, онда косымша тек транспоза болып табылады, ал А гермиттік, егер және тек қана ол симметриялық болса. Бағандық векторларға қолданғанда, косымша 'C'^(n) бойынша канондық ішкі көбейтіндіні анықтау үшін қолданылуы мүмкін: 1='w' ⋅ 'v' = 'w'^(*) 'v'. Қалыпты, гермиттік және нақты симметриялық матрицалардың бірнеше пайдалы қасиеттері бар: Қалыпты матрицаның кез келген жалпыланған өзіндік векторы – қарапайым өзіндік вектор. Кез келген қалыпты матрица диагональды матрицаға ұқсас, өйткені оның Джордан қалыпты түрі диагональды. Қалыпты матрицаның әртүрлі өзіндік мәндерінің өзіндік векторлары ортогональды. Нөлдік кеңістік және қалыпты матрицаның бейнесі (немесе бағандық кеңістік) бір-біріне ортогональды. Кез келген қалыпты матрица үшін 'C'^(n) А-ның өзіндік векторларынан тұратын ортонормалдық базаға ие. Өзіндік векторлардың сәйкес матрицасы унитарлы болады. Гермиттік матрицаның өзіндік мәндері нақты, өйткені нөлдік емес өзіндік вектор 'v' үшін. Егер A нақты болса, онда A симметриялы болса ғана және тек қана A-ның өзіндік векторларынан тұратын 'R'^(n) ортонормалдық базасы бар. Нақты немесе күрделі матрицаның гермиттік болмай-ақ барлық нақты өзіндік мәндері болуы мүмкін. Мысалы, нақты үшбұрышты матрицаның өзіндік мәндері оның диагоналі бойынша орналасқан, бірақ жалпы жағдайда симметриялық емес.

Шарт нөмірі

Кез келген сандық есептеу мәселесін белгілі бір кіріс x үшін белгілі бір f функциясын бағалау ретінде қарастыруға болады. Мәселенің шарт саны κ(f, x) – функцияның нәтижесіндегігі салыстырмалы қателік пен кірістегігі салыстырмалы қателіктің қатынасы болып табылады және функцияға да, кіріске де байланысты өзгереді. Шарт саны есептеу барысында қате қалай өсетінін сипаттайды. Оның 10-дық логарифмі нәтижедегі дәлдік кірістегіден қанша тамыздықпен кем екенін көрсетеді. Шарт саны – ең жақсы жағдайды көрсетеді. Ол проблеманың ішкі тұрақсыздығын көрсетеді, оны қалай шешуге тырысқаныңызға қарамастан. Кездейсоқ оқиғаларды есептемегенде, ешбір алгоритм шарт саны көрсеткеннен дәл нәтиже бере алмайды. Дегенмен, дұрыс емес құрылған алгоритм одан да нашар нәтижелерді тудыруы мүмкін. Мысалы, төменде айтылғандай, нормальды матрицалар үшін өзіндік мәндерді табу мәселесі әрқашан жақсы шартталған. Бірақ, полиномның түбірлерін табу мәселесі өте нашар шартталған болуы мүмкін. Сондықтан, сипаттамалық полиномның түбірлерін тауып жұмыс істейтін өзіндік мән алгоритмдері, проблема нашар шартталмаған жағдайда да нашар шартталған болуы мүмкін. A кері айналдырылатын жағдайдағы сызықтық теңдеуді шешу мәселесі үшін 1=A'v' = 'b', матрицаның шарт саны 1=κ(A^(−1), 'b') келесідей беріледі, мұндағы оператор нормасы 'C'^(n) нормалық Евклид нормасына бағынышты. Бұл сан 'b'-ге тәуелді емес және A мен A^(−1) үшін бірдей болғандықтан, оны әдетте матрицаның шарт саны κ(A) деп атайды. Бұл κ(A) мәні сонымен қатар A матрицасының ең үлкен өзіндік мәнінің ең кіші өзіндік мәніне қатынасының абсолюттік мәні болып табылады. Егер A бірлік матрица болса, онда , сондықтан 1=κ(A) = 1. Жалпы матрицалар үшін оператор нормасын есептеу көбінесе қиынға соғады. Сондықтан, шарт санын бағалау үшін басқа матрицалық нормалар жиі қолданылады. Өзіндік мән мәселесі үшін Бауэр мен Файк, егер λ диагональдық n × n матрицасы A-ның өзіндік мәні болса және V – өзіндік векторлар матрицасы болса, онда λ-ны есептеудегі абсолютті қателік κ(V) пен A-дағы абсолютті қателіктің көбейтіндісімен шектеледі екенін дәлездеді. Нәтижесінде, λ-ны табудың шарт саны: Егер A нормальды болса, онда V бірлік матрица болады, ал 1=κ(λ, A) = 1. Осылайша, барлық нормальды матрицалар үшін өзіндік мән мәселесі жақсы шартталған. λ өзіндік мәніне сәйкес келетін нормальды матрица A-ның өзіндік кеңістігін табу мәселесінің шарт саны λ және A-ның басқа өзіндік мәндері арасындағы ең аз қашықтыққа кері пропорционалды екені көрсетілді. Атап айтқанда, нормальды матрицалар үшін өзіндік кеңістік мәселесі оқшауланған өзіндік мәндер үшін жақсы шартталған. Өзіндік мәндер оқшауланбаған жағдайда, ең жақсысы жақын маңдағы өзіндік мәндердің барлық өзіндік векторларының кеңеюін анықтау.

Any problem of numeric calculation can be viewed as the evaluation of some function f for some input x. The condition number κ(f, x) of the problem is the ratio of the relative error in the function's output to the relative error in the input, and varies with both the function and the input. The condition number describes how error grows during the calculation. Its base 10 logarithm tells how many fewer digits of accuracy exist in the result than existed in the input. The condition number is a best case scenario. It reflects the instability built into the problem, regardless of how it is solved. No algorithm can ever produce more accurate results than indicated by the condition number, except by chance. However, a poorly designed algorithm may produce significantly worse results. For example, as mentioned below, the problem of finding eigenvalues for normal matrices is always well conditioned. However, the problem of finding the roots of a polynomial can be very ill conditioned. Thus eigenvalue algorithms that work by finding the roots of the characteristic polynomial can be ill conditioned even when the problem is not. For the problem of solving the linear equation 1=A'v' = 'b' where A is invertible, the matrix condition number 1=κ(A^(−1), 'b') is given by , where is the operator norm subordinate to the normal Euclidean norm on 'C'^(n). Since this number is independent of 'b' and is the same for A and A^(−1), it is usually just called the condition number κ(A) of the matrix A. This value κ(A) is also the absolute value of the ratio of the largest eigenvalue of A to its smallest. If A is unitary, then , so 1=κ(A) = 1. For general matrices, the operator norm is often difficult to calculate. For this reason, other matrix norms are commonly used to estimate the condition number. For the eigenvalue problem, Bauer and Fike proved that if λ is an eigenvalue for a diagonalizable n × n matrix A with eigenvector matrix V, then the absolute error in calculating λ is bounded by the product of κ(V) and the absolute error in A. As a result, the condition number for finding λ is If A is normal, then V is unitary, and 1=κ(λ, A) = 1. Thus the eigenvalue problem for all normal matrices is well conditioned. The condition number for the problem of finding the eigenspace of a normal matrix A corresponding to an eigenvalue λ has been shown to be inversely proportional to the minimum distance between λ and the other distinct eigenvalues of A. In particular, the eigenspace problem for normal matrices is well conditioned for isolated eigenvalues. When eigenvalues are not isolated, the best that can be hoped for is to identify the span of all eigenvectors of nearby eigenvalues.

Итерациялық алгоритмдер

Итеративті алгоритмдер өзіндік мәндер мәселесін өзіндік мәндерге жақындасатын тізбектерді құру арқылы шешеді. Кейбір алгоритмдер векторлардың өзіндік векторларға жақындасатын тізбектерін де құрайды. Көбінесе, өзіндік мәндер тізбектері үшбұрышты немесе диагональды түрге жақындасатын ұқсас матрицалар тізбектері түрінде беріледі, бұл өзіндік мәндерді оңай оқуға мүмкіндік береді. Өзіндік векторлар тізбегі сәйкес ұқсастық матрицалары түрінде беріледі. Әдіс Қолданылатын объектілер Бір қадамға кететін шығын Жақындасу Сипаттамасы Ланчос алгоритмі Гермиттік m ең үлкен/ең кіші өзіндік жұптар Күш итерациясы ең үлкен мәні бар өзіндік жұп O(n^(2)) сызықтық Матрицаны кездейсоқ бастапқы векторға қайта-қайта қолданып, нормалайды. Кері итерация μ-ге ең жақын мәні бар өзіндік жұп сызықтық (A − μI)^(−1) үшін күш итерациясы Рейлидің коэффициенті итерациясы Гермиттік кез келген өзіндік жұп кубикалық (A − μiI)^(−1) үшін күш итерациясы, мұнда μi әр итерация үшін алдыңғы итерацияның Рейлидің коэффициенті болып табылады. Алдын ала шартталған кері итерация немесе LOBPCG алгоритмі μ-ге ең жақын мәні бар оң, нақты симметриялық өзіндік жұп A-ға жуық кері шартты кері итерация. Бисекция әдісі нақты симметриялық тридиагональды кез келген өзіндік мән сызықтық Штурм тізбегімен қолдау көрсетілетін сипаттамалық полиномның түбірлерін табу үшін бисекция әдісін қолданады. Лагерр итерациясы нақты симметриялық тридиагональды кез келген өзіндік мән кубикалық Лагерр әдісін қолданады. QR алгоритмі Гессенберг барлық өзіндік мәндер O(n^(2)) кубикалық A = QR түрінде жіктейді, мұнда Q ортогональды және R үшбұрышты, содан кейін RQ-ға келесі итерацияны қолданады. барлық өзіндік жұптар 6n^(3) + O(n^(2)) Якоби өзіндік мән алгоритмі нақты симметриялық барлық өзіндік мәндер O(n^(3)) квадратық Диагональдық емес элементтерді жоюға тырысу үшін Гивенс айналымдарын қолданады. Бұл сәтсіз аяқталады, бірақ диагональды нығайтады. Бөліп жеңу Гермиттік тридиагональды барлық өзіндік мәндер O(n^(2)) Матрицаны диагональдандырылып, содан кейін қайта құрастырылатын кіші матрицаларға бөледі. барлық өзіндік жұптар Гомотопия әдісі нақты симметриялық тридиагональды барлық өзіндік жұптар O(n^(2)) Диагональдық өзіндік мәндер мәселесінен есептелетін гомотопия жолын құрастырады. Жалғанды спектр әдісі нақты симметриялық μ-ге ең жақын мәні бар өзіндік жұп (A − μI)^(2) үшін алдын ала шартталған кері итерация қолданылады. MRRR алгоритмі нақты симметриялық тридиагональды кейбір немесе барлық өзіндік жұптар O(n^(2)) "Көптеген салыстырмалы берік өкілдіктер" – ауыстырылған матрицаның LDLT жіктелуінде кері итерацияны орындайды. Грамм итерациясы жалпы ең үлкен өзіндік мәні бар өзіндік жұп суперсызықтық Грамм көбейтіндісін есептеп, қайта масштабтайды.

Iterative algorithms solve the eigenvalue problem by producing sequences that converge to the eigenvalues. Some algorithms also produce sequences of vectors that converge to the eigenvectors. Most commonly, the eigenvalue sequences are expressed as sequences of similar matrices which converge to a triangular or diagonal form, allowing the eigenvalues to be read easily. The eigenvector sequences are expressed as the corresponding similarity matrices. Method Applies to Produces Cost per step Convergence Description Lanczos algorithm Hermitian m largest/smallest eigenpairs Power iteration general eigenpair with largest value O(n^(2)) linear Repeatedly applies the matrix to an arbitrary starting vector and renormalizes. Inverse iteration general eigenpair with value closest to μ linear Power iteration for (A − μI)^(−1) Rayleigh quotient iteration Hermitian any eigenpair cubic Power iteration for (A − μiI)^(−1), where μi for each iteration is the Rayleigh quotient of the previous iteration. Preconditioned inverse iteration or LOBPCG algorithm positive definite real symmetric eigenpair with value closest to μ Inverse iteration using a preconditioner (an approximate inverse to A). Bisection method real symmetric tridiagonal any eigenvalue linear Uses the bisection method to find roots of the characteristic polynomial, supported by the Sturm sequence. Laguerre iteration real symmetric tridiagonal any eigenvalue cubic Uses Laguerre's method to find roots of the characteristic polynomial, supported by the Sturm sequence. QR algorithm Hessenberg all eigenvalues O(n^(2)) cubic Factors A = QR, where Q is orthogonal and R is triangular, then applies the next iteration to RQ. all eigenpairs 6n^(3) + O(n^(2)) Jacobi eigenvalue algorithm real symmetric all eigenvalues O(n^(3)) quadratic Uses Givens rotations to attempt clearing all off diagonal entries. This fails, but strengthens the diagonal. Divide and conquer Hermitian tridiagonal all eigenvalues O(n^(2)) Divides the matrix into submatrices that are diagonalized then recombined. all eigenpairs Homotopy method real symmetric tridiagonal all eigenpairs O(n^(2)) Constructs a computable homotopy path from a diagonal eigenvalue problem. Folded spectrum method real symmetric eigenpair with value closest to μ Preconditioned inverse iteration applied to (A − μI)^(2) MRRR algorithm real symmetric tridiagonal some or all eigenpairs O(n^(2)) "Multiple relatively robust representations" – performs inverse iteration on a LDLT decomposition of the shifted matrix. Gram iteration general Eigenpair with largest eigenvalue super linear Repeatedly computes the Gram product and rescales, deterministically.

Тікелей есептеу

Жалпы матрицалар үшін өзіндік мәндерді тікелей есептеуге арналған қарапайым алгоритм жоқ болса да, өзіндік мәндерді тікелей есептеуге болатын көптеген арнайы матрицалар кластары бар. Оларға мыналар кіреді:

Үшбұрышты матрицалар

Үшбұрышты матрицаның детерминанты оның диагональдық элементтерінің көбейтіндісі болғандықтан, егер T үшбұрышты матрица болса, онда T матрицасының өзіндік мәндері оның диагональдық элементтерімен тең болады.

Қалыпты 3×3 матрицалардың өз векторлары

Егер 3×3 матрицасы қалыпты болса, онда векторларды табу үшін векторлық көбейтінді қолданылуы мүмкін. Егер λ матрицаның өзіндік мәні болса, онда матрицаның нөлдік кеңістігі оның баған кеңістігіне перпендикуляр болады. Матрицаның екі тәуелсіз бағанының векторлық көбейтіндісі нөлдік кеңістікте жатады. Яғни, ол λ өзіндік мәніне сәйкес келетін өз векторы болады. Бұл жағдайда баған кеңістігі екі өлшемді болғандықтан, өзіндік кеңістік бір өлшемді болуы керек, сондықтан кез келген басқа өз векторы оған параллель болады. Егер матрицада екі тәуелсіз баған болмаса, бірақ ол нөлдік матрица болмаса, векторлық көбейтіндіні қолдануға болады. Бұл жағдайда λ өзіндік мәнінің көптігі 2-ге тең, сондықтан баған кеңістігіне перпендикуляр кез келген вектор өз векторы болады. Матрицаның нөлдік емес бағаны деп есептейік. Одан параллель емес кез келген векторды таңдаңыз. Онда және векторлары бағанға перпендикуляр болады, демек, олар матрицаның өз векторлары болады. Бұл матрица қалыпты болмаған жағдайда жұмыс істемейді, себебі мұндай матрицалар үшін нөлдік кеңістік пен баған кеңістігінің перпендикуляр болуы міндетті емес.