Samarqand davlat universiteti raqamli texnologiyalar fakulteti amaliy matematika va informatika yo

III BOB. XOS SON VA XOS VEKTORLARNI QR VA LR ALGORITMLARI ORQALI HISOBLASH

3.1. QR (yoki LR) algoritmi

Raqamli chiziqli algebrada QR algoritmi yoki QR iteratsiyasi o'ziga xos qiymat algoritmidir : ya'ni matritsaning xos qiymatlari va xos vektorlarini hisoblash tartibi . QR algoritmi 1950-yillarning oxirida Jon GF Frensis va Vera N. Kublanovskaya tomonidan mustaqil ravishda ishlab chiqilgan. Asosiy gʻoya QR dekompozitsiyasini amalga oshirish, matritsani ortogonal matritsa va yuqori uchburchak matritsaning mahsuloti sifatida yozish , omillarni teskari tartibda koʻpaytirish va takrorlashdan iborat.

Amaliy QR algoritmi. Rasmiy ravishda, biz xos qiymatlarini hisoblamoqchi bo'lgan A haqiqiy matritsa bo'lsin va A ₀ := A bo'lsin . K --bosqichda ( k = 0 dan boshlab) QR parchalanishini hisoblaymiz A _k = Q _k R _k bunda Q _k ortogonal matritsa ( ya’ni Q ^T = Q ⁻¹ ) va R _k yuqori uchburchakdir. matritsa. Keyin A _k +1 = R _k Q _k hosil qilamiz.

shuning uchun barcha A _k o'xshash va shuning uchun ular bir xil xos qiymatlarga ega . Algoritm son jihatdan barqaror , chunki u ortogonal o'xshashlik o'zgarishlari bilan davom etadi.
Muayyan sharoitlarda  A _k matritsalari uchburchak matritsaga, A ning Schur shakliga yaqinlashadi . Uchburchak matritsaning o'ziga xos qiymatlari diagonalda keltirilgan va xususiy qiymat masalasi hal qilinadi. Konvergentsiyani sinab ko'rishda aniq nollarni talab qilish mantiqiy emas , lekin Gershgorin doira teoremasi xato chegarasini beradi.
Ushbu xom shaklda iteratsiyalar nisbatan qimmat. Buni birinchi navbatda A matritsasini Gessenberg shaklining yuqori shakliga (bu uy egalarini kamaytirishga asoslangan texnikadan foydalangan holda arifmetik operatsiyalarga xarajat qiladi) ortogonal o'xshashlik o'zgarishlarining chekli ketma-ketligi bilan ikki tomonlama QR parchalanishiga o'tkazish orqali yumshatish mumkin. (QR dekompozitsiyasi uchun uy egasi reflektorlari faqat chapga ko'paytiriladi, lekin Hessenberg ishi uchun ular chap va o'ngga ko'paytiriladi.) Yuqori Hessenberg matritsasining QR parchalanishini aniqlash xarajatlari arifmetik amallar. Bundan tashqari, Hessenberg shakli deyarli yuqori uchburchak bo'lganligi sababli (u har bir diagonal ostida faqat bitta nolga teng bo'lmagan yozuvga ega), uni boshlang'ich nuqtasi sifatida ishlatish QR algoritmining yaqinlashishi uchun zarur bo'lgan qadamlar sonini kamaytiradi.
Agar asl matritsa simmetrik bo'lsa, u holda yuqori Hessenberg matritsasi ham simmetrik va shuning uchun tridiagonal bo'lib, barcha A _k . Ushbu protsedura uy egalarini kamaytirishga asoslangan texnikadan foydalangan holda arifmetik operatsiyalarga sarflanadi.  Simmetrik tridiagonal matritsaning QR dekompozitsiyasini aniqlash operatsiyalarga sarflanadi.
Konvergentsiya tezligi o'z qiymatlari orasidagi bo'linishga bog'liq, shuning uchun amaliy algoritm ajratishni oshirish va yaqinlashuvni tezlashtirish uchun aniq yoki yashirin siljishlardan foydalanadi. Oddiy nosimmetrik QR algoritmi har bir xos qiymatni faqat bir yoki ikkita takrorlash bilan izolyatsiya qiladi (keyin matritsa hajmini kamaytiradi), bu uni samarali va mustahkam qiladi.