Кіріспе
Сандық талдауда кері итерация (сондай-ақ кері қуат әдісі деп аталады) – итерациялық өзіндік мән алгоритмі. Бұл тиісті өзіндік мәнге жуықтамасы бұрыннан белгілі болған кезде, шамамен өзіндік векторды табуға мүмкіндік береді. Әдіс тұжырымдамалық тұрғыдан қуат әдісіне ұқсас. Ол бастапқыда құрылымдық механика саласындағы резонанстық жиіліктерді есептеу үшін жасалған болып көрінеді. Кері қуат итерациясы алгоритмі қалаған өзіндік векторға сәйкес келетін өзіндік мәнге жуықтамамен және вектормен басталады, ол кездейсоқ таңдалған вектор немесе өзіндік векторға жуықтама болуы мүмкін. Әдіс итерация арқылы сипатталады:
eigenvector when an approximation to a corresponding eigenvalue is already known. The method is conceptually similar to the power method. It appears to have originally been developed to compute resonance frequencies in the field of structural mechanics. The inverse power iteration algorithm starts with an approximation for the eigenvalue corresponding to the desired eigenvector and a vector , either a randomly selected vector or an approximation to the eigenvector. The method is described by the iteration
мұнда – әдетте таңдалатын тұрақтылар. Өзіндік векторлар тұрақтыға көбейтуге дейін анықталады, сондықтан теорияда -ның таңдауы кездейсоқ болуы мүмкін; -ның таңдауының практикалық аспектілері төменде талқыланады. Әрбір итерацияда вектор матрицаға көбейтіледі және нормаланады. Бұл формула қуат әдісіндегідей, тек матрицаны ауыстырудан басқа. Өзіндік мәнге жуықтама неғұрлым жақын болса, алгоритм соғұрлым жылдам конвергенцияланады; алайда, -ның дұрыс емес таңдауы баяу конвергенцияға немесе қажетті өзіндік вектордан басқа векторға конвергенцияға әкелуі мүмкін. Іс жүзінде, әдіс өзіндік мәнге жақсы жуықтама белгілі болған кезде қолданылады, сондықтан тек бірнеше (көбінесе бір ғана) итерация қажет.
The closer the approximation to the eigenvalue is chosen, the faster the algorithm converges; however, incorrect choice of can lead to slow convergence or to the convergence to an eigenvector other than the one desired. In practice, the method is used when a good approximation for the eigenvalue is known, and hence one needs only few (quite often just one) iterations.
Күрделілігі
Кері итерация алгоритмі сызықтық жүйені шешуді немесе кері матрицаны есептеуді қажет етеді. Құрылымдалмаған матрицалар үшін (сирект емес, Топлиц емес) бұл операциялар қажет болады.
Нормалдану тұрақтысын таңдау
Жалпы мақсаттағы процессорларда (мысалы, Intel өндіретін) қосу, көбейту және бөлу операцияларын орындау уақыты шамамен бірдей. Бірақ кіріктірілген және/немесе төмен энергия тұтынушы аппараттық құралдарда (цифрлық сигнал процессорлары, FPGA, ASIC) бөлу аппараттық деңгейде қолдау көрсетпеуі мүмкін, сондықтан одан аулақ болу керек. Дұрыс таңдау аппараттық қолдаусыз жылдам бөлуді қамтамасыз етеді, себебі 2-нің дәрежесіне бөлу тұрақты нүктелік арифметикада біт ығыстыру арқылы, ал қозғалмалы нүктелік арифметикада экспонентадан кешіру арқылы жүзеге асырылуы мүмкін. Тұрақты нүктелік арифметика қолданып алгоритмді іске асырғанда тұрақтының таңдалуы ерекше маңызды. Шағын мәндер норманың жылдам өсуіне және мән шығып кетуіне алып келеді, ал үлкен мәндер вектордың нөлге жақындауына себеп болады.
Қолданылуы
Әдістің негізгі қолданылуы – өзіндік мәнге жуықтама табылып, сәйкес өзіндік векторды табу қажет болған жағдайда. Мұндай жағдайда кері итерация – негізгі және, мүмкін, жалғыз қолданылатын әдіс.
Тақрибан өзіндік мәндерді табу әдістері
Көбінесе, бұл әдіс шамамен өзіндік мәндерді анықтайтын басқа әдіспен бірге қолданылады: классикалық мысал – екіге бөлу арқылы өзіндік мәндерді табу алгоритмі, тағы бір мысал – Рейлидің үлесі арқылы итерация, ол іс жүзінде алдыңғы итерация қадамында алынған векторға сәйкес Рейлидің үлесі ретінде таңдалған шамамен өзіндік мәнмен бірдей кері итерация болып табылады. Дегенмен, әдісті жеке-жеке қолдануға болатын жағдайлар да бар, бірақ олар өте сирек кездеседі.
Матрицаның нормасы басым өзіндік құнға жуықтама ретінде
Доминантты өзіндік мәнді кез келген матрица үшін оңай бағалауға болады. Кез келген шақырылған норма үшін, кез келген өзіндік мән үшін бұл рас. Сондықтан матрицаның нормасын шамамен өзіндік мән ретінде қарастырғанда, әдіс доминантты өзіндік векторға жақындасатынын көруге болады.
So taking the norm of the matrix as an approximate eigenvalue one can see that the method will converge to the dominant eigenvector.
Статистикаға негізделген бағалау
Кейбір нақты уақыт қолданбаларында секундына миллиондаған матрица жылдамдығымен матрицалар үшін өзіндік векторларды табу қажет болады. Мұндай қолданбаларда матрицалардың статистикасы көбінесе алдын ала белгілі болады, сондықтан үлкен матрицалар жинағы үшін орташа өзіндік мәнді шамамен өзіндік мән ретінде қабылдауға болады. Жақсырақ, матрицаның ізге немесе нормасына өзіндік мәндердің орташа қатынасын есептеп, орташа өзіндік мәнді іздің немесе норманың осы қатынастың орташа мәніне көбейтілген нәтижесі ретінде бағалауға болады. Әрине, мұндай әдіс тек сақтылықпен және жоғары дәлдік қажет болмаған жағдайларда ғана қолданылуы мүмкін. Орташа өзіндік мәнді бағалаудың бұл тәсілін басқа әдістермен біріктіре отырып, тым үлкен қателіктерге жол бермеуге болады.