Samarqand davlat universiteti raqamli texnologiyalar fakulteti amaliy matematika va informatika yo

Vizualizatsiya. Asosiy QR algoritmini A musbat-aniq simmetrik matritsa bo'lgan holatda tasavvur qilish mumkin . Bunday holda, A ni 2 o'lchamdagi ellips yoki undan yuqori o'lchamdagi ellipsoid sifatida tasvirlash mumkin . Algoritmga kiritilgan ma'lumotlar va bitta iteratsiya o'rtasidagi munosabatni 1-rasmdagi kabi tasvirlash mumkin (animatsiyani ko'rish uchun bosing). LR algoritmi QR algoritmi bilan birga tasvirlanganligini unutmang. Bitta iteratsiya ellipsning x o'qi tomon egilishiga yoki "tushilishiga" olib keladi. Agar ellipsning katta yarim o'qi x o'qiga parallel bo'lsa, QR ning bir iteratsiyasi hech narsa qilmaydi. Algoritm "hech narsa qilmaydi" yana bir holat - katta yarim o'q x o'qi o'rniga y o'qiga parallel bo'lganda. Bunday holda, ellipsni har ikki yo'nalishda ham yiqilib tushmasdan muvozanatni saqlaydigan deb hisoblash mumkin. Ikkala holatda ham matritsa diagonaldir. Algoritmning iteratsiyasi "hech narsa qilmaydi" vaziyat sobit nuqta deb ataladi . Algoritm tomonidan qo'llaniladigan strategiya - bu belgilangan nuqtaga iteratsiya. Bir sobit nuqta barqaror, ikkinchisi esa beqaror ekanligiga e'tibor bering. Agar ellips beqaror qo'zg'almas nuqtadan juda oz miqdorga egilgan bo'lsa, QR ning bir iteratsiyasi ellipsning sobit nuqtadan emas, balki sobit nuqtadan uzoqlashishiga olib keladi. Oxir-oqibat, algoritm boshqa belgilangan nuqtaga yaqinlashadi, lekin bu uzoq vaqt talab etadi.

1-rasm: QR yoki LR algoritmining bitta iteratsiyasining chiqishi uning kiritilishi bilan bir qatorda qanday o'zgaradi

3.2. QR va LR algoritmlari orqali matritsaning xos qiymatlarni topish va xos vektorlarni hisoblash

Shuni ta'kidlash kerakki, hatto nosimmetrik matritsaning bitta xos vektorini ham topish mumkin emas. Bu qiyinchilik har doim matritsaning xos qiymatlarining koʻpligi maʼlum boʻlmaganda yuzaga keladi. Boshqa tomondan, o'z qiymatlarini topish uchun bir xil muammo mavjud emas. Matritsaning o'ziga xos qiymatlari har doim hisoblash mumkin. Endi biz ushbu qiyinchiliklar asosiy QR algoritmida qanday namoyon bo'lishini muhokama qilamiz. Bu 2-rasmda ko'rsatilgan. (Eskizni bosishni unutmang). Eslatib o'tamiz, ellipslar musbat-aniq simmetrik matritsalarni ifodalaydi. Kirish matritsasining ikkita xos qiymati bir-biriga yaqinlashganda, kirish ellipsi aylanaga aylanadi. Doira identifikatsiya matritsasining ko'paytmasiga mos keladi. Yaqin doira o'z qiymatlari matritsaning diagonal yozuvlariga deyarli teng bo'lgan identifikatsiya matritsasining deyarli ko'p qismiga to'g'ri keladi. Shuning uchun o'z qiymatlarini taxminan topish muammosi bu holda oson ekanligi ko'rsatilgan. Ammo ellipslarning yarim o'qlari bilan nima sodir bo'lishiga e'tibor bering. QR (yoki LR) iteratsiyasi yarim o‘qlarni kamroq va kamroq egiladi, chunki kirish ellipsi aylana bo‘lishga yaqinlashadi. Yarim o'qlar x va y o'qlariga parallel bo'lgandagina xos vektorlarni bilish mumkin. Deyarli parallellikka erishish uchun kerak bo'lgan iteratsiyalar soni, kirish ellipsi aylana shaklida bo'lganda, chegaralanmagan holda ortadi.
Ixtiyoriy simmetrik matritsaning o'ziga xos tarkibini hisoblash imkonsiz bo'lsa-da , matritsani ixtiyoriy ravishda kichik miqdor bilan buzish va hosil bo'lgan matritsaning o'ziga xos tarkibiy qismini hisoblash har doim mumkin. Agar matritsa yaqin aylana sifatida tasvirlangan bo'lsa, matritsa tasviri mukammal doira bo'lgan bilan almashtirilishi mumkin. Bunday holda, matritsa identifikatsiya matritsasining ko'paytmasi bo'lib, uning o'ziga xos birikmasi darhol bo'ladi. Shuni yodda tutingki, hosil bo'lgan o'z asosi asl xossadan ancha uzoq bo'lishi mumkin.