O'zaro qiymat algoritmini ajratib oling - Divide-and-conquer eigenvalue algorithm - Wikipedia

O'zaro qiymat algoritmlarini ajratib oling sinfidir shaxsiy qiymat algoritmlari uchun Hermitiyalik yoki haqiqiy nosimmetrik matritsalar yaqinda (taxminan 1990-yillar) raqobatbardosh bo'lib qoldi barqarorlik va samaradorlik kabi an'anaviy algoritmlar bilan QR algoritmi. Ushbu algoritmlarning asosiy tushunchasi bo'ling va zabt eting yaqinlashish Kompyuter fanlari. An o'ziga xos qiymat muammo taxminan yarim o'lchamdagi ikkita muammoga bo'linadi, ularning har biri hal qilinadi rekursiv, va asl muammoning o'ziga xos qiymatlari ushbu kichik muammolarning natijalari bo'yicha hisoblanadi.

Bu erda dastlab 1981 yilda Cuppen tomonidan taklif qilingan o'xshashlik va g'alaba qozonish algoritmining eng oddiy versiyasini taqdim etamiz. Ushbu maqola doirasidan tashqarida bo'lgan ko'plab tafsilotlar chiqarib tashlanadi; ammo, ushbu tafsilotlarni hisobga olmasdan, algoritm to'liq barqaror emas.

Fon

Hermit matritsalarining ko'pgina o'ziga xos algoritmlarida bo'lgani kabi, bo'linish va zabt etishning kamayishi bilan boshlanadi uchburchak shakl. Uchun matritsa, buning uchun standart usul Uy egalarining aks etishi, oladi floplar, yoki agar xususiy vektorlar ham kerak. Kabi boshqa algoritmlar mavjud Arnoldi takrorlanishi, bu matritsalarning ayrim sinflari uchun yaxshiroq bo'lishi mumkin; biz buni bu erda ko'rib chiqmaymiz.

Ba'zi hollarda, mumkin tushirish shaxsiy qiymat muammosi kichikroq muammolarga aylanadi. A ni ko'rib chiqing blokli diagonali matritsa

Ning xos qiymatlari va xususiy vektorlari shunchaki va , va deyarli har doim bu ikkita kichik masalani echish asl muammoni birdaniga hal qilishdan ko'ra tezroq bo'ladi. Ushbu uslub ko'plab o'ziga xos algoritmlarning samaradorligini oshirish uchun ishlatilishi mumkin, ammo uni ajratish va yutish uchun alohida ahamiyatga ega.

Ushbu maqolaning qolgan qismida biz bo'linish va zabt etish algoritmiga kirishni qabul qilamiz haqiqiy nosimmetrik tridiagonal matritsa . Algoritmni Hermit matritsalari uchun o'zgartirish mumkin bo'lsa ham, biz bu erda batafsil ma'lumot bermaymiz.

Bo'lmoq

The bo'lmoq ajratish va yutish algoritmining bir qismi tridiyagonal matritsa "deyarli" blok diagonali ekanligini anglashdan kelib chiqadi.

Deyarli blok diagonal.png

Submatrix hajmi biz qo'ng'iroq qilamiz , undan keyin bu . Haqida eslatma ekanligini unutmang deyarli blok diagonali bo'lish, qanday bo'lishidan qat'iy nazar to'g'ri tanlangan (ya'ni, matritsani bu kabi parchalashning ko'plab usullari mavjud). Biroq, samaradorlik nuqtai nazaridan tanlov qilish mantiqan .

Biz yozamiz blok diagonali matritsa sifatida, ortiqcha a 1-daraja tuzatish:

Blok diagonal plus correction.png

Orasidagi yagona farq va bu pastki o'ng kirish yilda bilan almashtirildi va shunga o'xshash, ichida yuqori chap kirish bilan almashtirildi .

Bo'linish bosqichining qolgan qismi o'z qiymatlarini (va zarur bo'lsa, o'z vektorlarini) echishdir. va , bu topish uchun diagonalizatsiya va . Buni ajratish va yutib yuborish algoritmiga rekursiv chaqiriqlar bilan amalga oshirish mumkin, ammo amaliy dasturlar ko'pincha kichik submatrikalar uchun QR algoritmiga o'tadi.

Fath qiling

The zabt etish algoritmning bir qismi tushunarsiz qismdir. Yuqorida hisoblangan submatrikalarning diagonalizatsiyasini hisobga olsak, asl matritsaning diagonalizatsiyasini qanday topamiz?

Birinchidan, aniqlang , qayerda ning oxirgi qatori va ning birinchi qatori . Endi buni ko'rsatish oddiy

Qolgan vazifa diagonali matritsaning o'ziga xos qiymatlarini topishga va bitta darajadagi tuzatishga qisqartirildi. Buni qanday qilishni ko'rsatmasdan oldin, yozuvni soddalashtiramiz. Biz matritsaning o'ziga xos qiymatlarini qidiramiz , qayerda aniq yozuvlar bilan diagonal va nolga teng bo'lmagan yozuvlar bilan har qanday vektor.

Agar wmen nolga teng, (, dmen) ning o'ziga xos juftligi beri.

Agar bu o'zgacha qiymat, bizda:

qayerda mos keladigan xususiy vektor. Endi

Shuni yodda tuting nolga teng bo'lmagan skalar. Ham na nolga teng. Agar nol bo'lishi kerak edi, ning o'ziga xos vektori bo'ladi tomonidan . Agar shunday bo'lgan bo'lsa, beri bitta nolga teng bo'lmagan pozitsiyani o'z ichiga oladi aniq diagonali va shu bilan ichki mahsulotdir Axir nol bo'lishi mumkin emas. Shuning uchun bizda:

yoki skaler tenglama sifatida yozilgan,

Ushbu tenglama dunyoviy tenglama. Shuning uchun muammo ildizlarning ildizlarini topishga qisqartirildi ratsional funktsiya ushbu tenglamaning chap tomoni bilan belgilanadi.

Barcha shaxsiy qiymat algoritmlari iterativ bo'lishi kerak va bo'linish va yutish algoritmi ham farq qilmaydi. Hal qilish chiziqli emas dunyoviy tenglama iterativ texnikani talab qiladi, masalan Nyuton-Raphson usuli. Biroq, har bir ildizni topish mumkin O (1) takrorlash, ularning har biri talab qiladi floplar (masalan - daraja ratsional funktsiyasi), ushbu algoritmning takrorlanadigan qismining narxini tashkil qiladi .

Tahlil

Algoritmlarni ajratish va yutish uchun odatiy bo'lganidek, biz Bo'lish va yutish takrorlanishlari uchun master teoremasi ish vaqtini tahlil qilish. Yuqorida biz tanlaganimizni aytganimizni eslang . Biz yozishimiz mumkin takrorlanish munosabati:

Asosiy teorema yozuvida, va shunday qilib . Shubhasiz, , shuning uchun bizda bor

Yodingizda tutingki, biz Ermit matritsasini tridiyagonal shaklga kamaytirish zarurligini ta'kidladik floplar. Bu bo'linish va zabt etish qismining ishlash vaqtini mitti qiladi va shu vaqtda bo'linish va yutish algoritmi QR algoritmidan qanday ustunlikni taklif qilishi aniq emas (bu ham oladi) tridiagonal matritsalar uchun floplar).

Ajratish va zabt etishning afzalligi o'ziga xos vektorlar zarur bo'lganda paydo bo'ladi. Agar shunday bo'lsa, tridiagonal shaklga o'tish kerak , lekin algoritmning ikkinchi qismi oladi shuningdek. Maqsadli aniqlik bilan QR algoritmi uchun bu shunday , bo'linish va zabt etish uchun bu . Ushbu yaxshilanishning sababi shundaki, bo'linish va yutib chiqishda algoritmning bir qismi (ko'paytirish matritsalar) takrorlanishdan ajralib turadi, QR-da esa bu har bir takrorlanish bosqichida bo'lishi kerak. Qo'shilishi qisqartirish uchun floplar, umumiy yaxshilanish ga floplar.

Ajratish va zabt etish algoritmidan amaliy foydalanish shuni ko'rsatdiki, aksariyat haqiqiy qiymat muammolarida algoritm aslida bundan ham yaxshiroq ishlaydi. Sababi shundaki, ko'pincha matritsalar va vektorlar bo'lishga moyil son jihatdan siyrak, ya'ni ular qiymatlaridan kichik bo'lgan ko'plab yozuvlarga ega ekanligini anglatadi suzuvchi nuqta aniqlik, imkon beradi raqamli deflyatsiya, ya'ni muammoni birlashtirilmagan pastki muammolarga ajratish.

Variantlar va amalga oshirish

Bu erda taqdim etilgan algoritm eng sodda versiya. Ko'pgina amaliy dasturlarda barqarorlikni kafolatlash uchun 1-darajali murakkab tuzatishlardan foydalaniladi; ba'zi bir variantlarda hatto 2-darajali tuzatishlar qo'llaniladi.[iqtibos kerak ]

Ratsional funktsiyalar uchun Nyuton-Raphson usulidan ko'ra ishlashi va barqarorligi jihatidan yaxshiroq ishlashi mumkin bo'lgan maxsus ildiz qidirish texnikasi mavjud. Bular ajratish va yutib yuborish algoritmining takrorlanadigan qismini takomillashtirish uchun ishlatilishi mumkin.

Ajratish va zabt etish algoritmi osonlikcha parallel va chiziqli algebra kabi hisoblash paketlari LAPACK yuqori sifatli parallel dasturlarni o'z ichiga oladi.

Adabiyotlar

  • Demmel, Jeyms V. (1997), Amaliy sonli chiziqli algebra, Filadelfiya, Pensilvaniya: Sanoat va amaliy matematika jamiyati, ISBN  0-89871-389-7, JANOB  1463942.
  • Kuppen, JJM (1981). "Simmetrik tridiyagonal xususiy muammo uchun bo'linish va g'alaba qozonish usuli". Numerische Mathematik. 36: 177–195.