Кіріспе

Өзіндік мәндерді есептеу алгоритмі. Сандық сызықтық алгебрада QR алгоритмі немесе QR итерациясы – матрицаның өзіндік мәндері мен өзіндік векторларын есептеуге арналған алгоритм. QR алгоритмі 1950-ші жылдардың соңында Джон Г. Ф. Френсис және Вера Н. Кублановская тәуелсіз түрде әзірледі. Алгоритмнің негізгі идеясы – матрицаны ортогональды матрица мен жоғарғы үшбұрышты матрицаның көбейтіндісі түрінде жазып, осы көбейткіштерді кері ретпен көбейту және осы амалды қайталап орындау болып табылады.

QR-алгоритмінің практикалық

Формальды түрде, A-ны өзіндік мәндерін есептегіміз келетін нақты матрица деп алайық, және 1=A0 := A. k-шы қадамда (1=k = 0-дан бастап) біз QR-ыдырауын есептейміз 1=Ak = Qk Rk, мұнда Qk – ортогональды матрица (яғни, 1=Q^(T) = Q^(−1)), ал Rk – жоғарғы үшбұрышты матрица. Содан кейін 1=Ak+1 = Rk Qk құраймыз. Атап өтейік,

барлық Ak матрицалары ұқсас, демек олардың өзіндік мәндері бірдей. Алгоритм сандық тұрғыдан тұрақты, себебі ол ортогональды ұқсастық түрлендірулер арқылы жүзеге асырылады. Белгілі бір шарттарда Ak матрицалары үшбұрышты матрицаға, A-ның Schur түріне жақындайды. Үшбұрышты матрицаның өзіндік мәндері диагональ бойынша тізімделеді, және өзіндік мәндерді табу мәселесі шешіледі. Жақындасуды тексеруде нақты нөлдерді талап етудің қажеті жоқ, бірақ Гершгорин шеңбер теоремасы қатеге шек қояды. Бұл қарапайым түрінде итерациялар салыстырмалы түрде қымбат. Бұл мәселені A матрицасын ең алдымен жоғарғы Гессенберг формасына келтіру арқылы шешуге болады (бұл үй иесінің азайтуына негізделген әдіспен арифметикалық операцияларды қажет етеді), ортогональды ұқсастық түрлендірулердің шекті тізбегімен, QR-ыдырау сияқты. (QR-ыдырау үшін үй иесінің шағылыстырғыштары тек сол жақтан көбейтіледі, бірақ Гессенберг жағдайында олар сол және оң жақтан көбейтіледі.) Жоғарғы Гессенберг матрицасының QR-ыдырауын анықтау арифметикалық операцияларды қажет етеді. Сонымен қатар, Гессенберг формасы бұрыннан үшбұрышты формаға жақын болғандықтан (әр қисақтың астында тек бір ғана нөлден өзге жазу бар), оны бастапқы нүкте ретінде пайдалану QR алгоритмінің жақындасуы үшін қажетті қадамдар санын азайтады. Егер бастапқы матрица симметриялық болса, онда жоғарғы Гессенберг матрицасы да симметриялық, демек үшбұрышты болады, сондай-ақ барлық Ak матрицалары да сондай болады. Бұл процедура үй иесінің азайтуына негізделген әдіспен арифметикалық операцияларды қажет етеді. Жақындасу жылдамдығы өзіндік мәндер арасындағы айырмаға байланысты, сондықтан практикалық алгоритм айырманы арттыру және жақындасуды үдету үшін нақты немесе жасырын жылжуларды қолданады. Типтік симметриялық QR алгоритмі әрбір өзіндік мәнді бір немесе екі итерациямен оқшаулайды (содан кейін матрицаның өлшемін азайтады), осылайша ол тиімді де, сенімді де болады.

Көрнекілендіру

Негізгі QR алгоритмін A оң белгілі симметриялық матрица болған жағдайда визуализациялауға болады. Бұл жағдайда А екі өлшемді эллипс немесе жоғары өлшемді эллипсоид ретінде бейнеленуі мүмкін. Алгоритмге берілген мәліметтер мен бір итерация арасындағы қатынасты 1-суретте көрсетілгендей бейнелеуге болады (анимацияны көру үшін басыңыз). LR алгоритмі QR алгоритмімен бірге көрсетілгенін ескеріңіз. Бір итерация эллипстің x осіне қарай еңкеюіне немесе "құлауына" себеп болады. Егер эллипстің үлкен жартылай осі x осіне параллель болса, QR итерациясының бірі ештеңе жасамайды. Алгоритм "ешнәрсе жасамайтын" тағы бір жағдай – үлкен жартылай осі x осі орнына y осіне параллель болған кезде. Мұндай жағдайда эллипс екі бағытта да құлай алмай, осал тепе-теңдікте тұрғандай болады. Екі жағдайда да матрица диагональды болады. Алгоритм итерациясының "ешнәрсе жасамайтын" жағдайы тұрақты нүкте деп аталады. Алгоритмнің стратегиясы – тұрақты нүктеге қарай итерация жасау. Бір тұрақты нүкте тұрақты, ал екіншісі тұрақсыз екенін байқаңыз. Егер эллипс тұрақсыз тұрақты нүктеден өте аз бұрышпен бұрылса, QR итерациясының бірі эллипсті тұрақты нүктеге қарай емес, одан алшақтатуы мүмкін. Бірақ, соңында алгоритм басқа тұрақты нүктеге жақындасады, бірақ бұл көп уақыт алады.

Өзіндік мәндерді табу мен өзіндік векторларды табу

Симметриялық матрицаның тіпті бір ғана өзіндік векторын табу есептеу арқылы іске аспайтынын атап өткен жөн (есептеу анализінің анықтамаларына сәйкес, нақты арифметикада). Бұл қиындық матрицаның өзіндік мәндерінің көптігі белгілі болмағанда туындайды. Ал, өзіндік мәндерді табуда мұндай мәселе жоқ. Матрицаның өзіндік мәндері әрқашан есептелуге болады. Енді біз осы қиындықтардың негізгі QR алгоритмінде қалай көрінетінін қарастырамыз. Бұл 2-суретте көрсетілген. Эллипстер оң белгілі симметриялық матрицаларды көрсетеді екенін еске түсірейік. Егер кіріс матрицасының екі өзіндік мәні бір-біріне жақындаса, кіріс эллипсі шеңберге айналады. Шеңбер – сәйкестік матрицаның есесіне тең. Шеңберге жақын эллипс – сәйкестік матрицаның шамамен есесіне тең, оның өзіндік мәндері матрицаның диагональдық элементтеріне жуық. Сондықтан, өзіндік мәндерді шамамен табу мәселесі бұл жағдайда оңай екені көрінеді. Бірақ эллипстің жартылай осьтеріне не болатынын қараңыз. QR (немесе LR) алгоритмінің әрбір итерациясы кіріс эллипсі шеңберге жақындаған сайын жартылай осьтерді көбірек еңкейтіп отырады. Өзіндік векторларды жартылай осьтер x және y осьтеріне параллель болғанда ғана анықтауға болады. Эллипс шеңберге жақындаған сайын, жартылай параллельдікке жету үшін қажетті итерациялар саны шексіз өседі. Кез келген симметриялық матрицаның өзіндік ыдырауын есептеу мүмкін болмаса да, матрицаны кез келген кішкентай шамамен өзгертіп, алынған матрицаның өзіндік ыдырауын есептеу әрқашан мүмкін. Матрица шеңберге жақын болған жағдайда, оны суреті кемелді шеңбер болатын матрицамен алмастыруға болады. Бұл жағдайда матрица сәйкестік матрицасының есесі болып табылады және оның өзіндік ыдырауы бірден анықталады. Дегенмен, алынған өзіндік база бастапқы өзіндік базадан қашықтау болуы мүмкін екенін есте сақтаңыз.

Жылдамдату: ауысу және дефляция

Эллипстің пішіні шеңберге жақындағанда баяулау байқалады, ал керісінше, эллипс созылғанда, яғни шеңберден алшақтағанда, оның айналуы жылдамдайды. Мұндай созу эллипсті бейнелейтін матрицаны мен алмастырғанда туындайды, мұнда – матрицасының ең кіші өзіндік мәніне жуық. Бұл жағдайда эллипстің екі жарты осьтерінің қатынасы шамасына жақындайды. Жоғары өлшемдерде мұндай ауысу эллипсоидтың ең кіші жарты осьінің ұзындығын басқа жарты осьтерге қарағанда кішірейтіп, ең кіші өзіндік мәнге жуықтауды жылдамдатады, бірақ басқа өзіндік мәндерге жуықтауды жылдамдатпайды. Ең кіші өзіндік мән толық анықталғанда бұл әдіс тиімсіз болады, сондықтан матрицаны дефляциялау қажет, яғни оның соңғы қатары мен бағаны жойылуы керек. Сондай-ақ, тұрақсыз бекітілген нүкте мәселесі де шешілуі керек. Ауысу эвристикасы көбінесе осы мәселені шешуге бағытталған: іс жүзіндегі ауысулар көбінесе үзілісті және кездейсоқ болады. Симметриялық матрицаларға, атап айтқанда біз қарап отырған матрицаларға өте қолайлы Уилкинсон ауысуы, әсіресе үзілісті болып келеді.

Жасырын QR алгоритмі

Қазіргі заманғы есептеу практикасында QR алгоритмі бірнеше ауысымдарды енгізуді жеңілдететін жасырын нұсқада орындалады. Оның атын Франсис алгоритмі деп атау ұсынылды. Голуб және Ван Лоан "Франсис QR қадамы" терминін қолданады.

Түсіндіру және конвергенция

QR алгоритмін негізгі "қуат" өзіндік мән алгоритмінің күрделірек түрі деп қарастыруға болады. Естеріңізге сала кетейік, қуат алгоритмі A матрицасын бір векторға қайта-қайта көбейтіп, әрбір итерациядан кейін нормалайды. Вектор ең үлкен өзіндік мәннің өзіндік векторына жақындайды. QR алгоритмі керісінше, толық векторлар жиынымен жұмыс істейді, нормалау (және ортогоналдау) үшін QR-ы ыдыратуды қолданады. А егер симметриялық матрица болса, жақындасқанда AQ = QΛ теңдігі орындалады, мұнда Λ – A матрицасы жақындасқан өзіндік мәндердің диагональдық матрицасы, ал Q – осы нәтижеге жету үшін қажетті барлық ортогоналды ұқсастық түрлендірулерінің жиынтығы. Демек, Q матрицасының бағаналары – өзіндік векторлар.

Тарих

QR алгоритміне дейін LR алгоритмі пайда болды, ол QR ыдырауының орнына LU ыдырауын қолданады. QR алгоритмі көбірек тұрақты, сондықтан LR алгоритмі қазіргі кезде сирек қолданылады. Дегенмен, ол QR алгоритмін дамытудағы маңызды қадам болып табылады. LR алгоритмін 1950 жылдардың басында Хайнц Рутихаузер әзірледі, ол сол кезде Эдуард Стифельдің Цюрихтегі ЭТХ-да ғылыми көмекшісі болып жұмыс істеді. Стифель Рутихаузерге A матрицасының өзіндік мәндерін табу үшін y0T Ak x0, k = 0, 1 (мұнда x0 және y0 кездейсоқ векторлар) сәттер тізбегін қолдануды ұсынды. Рутихаузер осы міндет үшін Александр Айткеннің алгоритмін қабылдап, оны quotient-difference алгоритміне немесе qd алгоритміне дамытты. Есептеуді қолайлы түрде орналастырғаннан кейін, ол qd алгоритмінің іс жүзінде тридиагональды матрицаға қолданылатын Ak = LkUk (LU ыдырау), Ak+1 = UkLk итерациясы екенін анықтады, содан LR алгоритмі туындайды.

Басқа нұсқалар

QR алгоритмінің бір түрі, Голуб-Кахан-Рейнш алгоритмі, ең жалпы матрицаны екідиагональды түрге келтіруден басталады. Бұл QR алгоритмінің жеке мәндерді есептеуге арналған нұсқасы алғаш рет LAPACK кіші бағдарламасы DBDSQR-де сипатталған. Бұл итеративтік әдіс жеке мәндер өте кішкентай болған жағдайларды қамту үшін кейбір өзгерістермен іске асырылады. Хаусхолдердің көрістірілімдерін және қажет болған жағдайда QR жіктелуін қолданатын алғашқы қадаммен бірге, бұл жеке мәнді жіктеуді есептеу үшін DGESVD процедурасын құрайды. QR алгоритмі шексіз өлшемдерде де, тиісті жинақталу нәтижелерімен бірге іске асырылуы мүмкін.