Özdeğer Algoritmaları
Özdeğer algoritmaları, bir matrisin özdeğerlerini ve özvektörlerini yinelemeli olarak hesaplar, çünkü dört çarpı dörtten büyük matrisler için sonlu bir formül mevcut değildir.
Tanım
Bir özdeğer algoritması, bir matrisin özdeğerlerini ve isteğe bağlı olarak özvektörlerini yaklaşık olarak belirlemek için kullanılan yinelemeli bir sayısal prosedürdür; zira özdeğerler karakteristik polinomun kökleridir ve genellikle sonlu sayıda aritmetik işlemle bulunamazlar.
Kapsam
Bu konu, kuvvet ve ters yinelemeleri, Hessenberg veya üç köşegen forma indirgemeyi, kaydırmalı QR algoritmasını ve simetrik özdeğer problemi için özelleşmiş yöntemleri, ayrıca hesaplanan özdeğerlerin hassasiyetini yöneten pertürbasyon kuramını kapsamaktadır.
Temel sorular
- Genel özdeğer hesaplaması neden doğrudan değil de yinelemeli olmak zorundadır?
- Kaydırmalı QR algoritması Schur formuna nasıl yakınsar ve verimlilik için Hessenberg formuna ön indirgeme neden esastır?
- Simetrik özdeğer problemini daha iyi koşullu ve özelleşmiş algoritmalara uygun kılan nedir?
- Özdeğerler pertürbasyonlara karşı ne kadar hassastır ve bu durum matrisin normal olmama (non-normality) özelliğine nasıl bağlıdır?
Temel kuramlar
- QR algoritması
- Bir matrisi tekrar tekrar QR olarak çarpanlara ayırmak ve RQ olarak birleştirmek, iyi seçilmiş kaydırmalar ve ön Hessenberg indirgemesi ile matrisi köşegeninde özdeğerleri barındıran üst üçgensel (Schur) forma doğru yönlendirir; bu, yoğun özdeğer problemi için standart yöntemdir.
- Kuvvet ve ters yineleme
- Matrisle tekrarlanan çarpma işlemi baskın özvektöre yakınsarken, bir kaydırmalı ters yineleme kaydırmaya en yakın özdeğeri hedefler; bunlar hem klasik yöntemlerin hem de modern özvektör iyileştirmesinin temelini oluşturur.
- Özdeğer pertürbasyon kuramı
- Bauer-Fike teoremi ve ilgili sonuçlar, özdeğerlerin pertürbasyonlar altında ne kadar hareket ettiğini sınırlar; simetrik (normal) matrisler için özdeğerler mükemmel koşulludur, oysa yüksek derecede normal olmayan matrisler için son derece hassas olabilirler.
Mekanizmalar
Yoğun bir matris, öncelikle ortogonal benzerlik dönüşümleriyle üst Hessenberg formuna (simetrik durumda üç köşegen) indirgenir; bu işlem özdeğerleri korurken her bir QR adımını daha uygun maliyetli hale getirir. Kaydırmalı QR yinelemesi daha sonra yakınsamış özdeğerleri matrisin altından birer veya ikişerli olarak indirger. Simetrik problemler için, böl ve yönet (divide-and-conquer) ve MRRR algoritmaları, özdeğerleri ve özvektörleri doğru ve paralel bir şekilde hesaplamak için yapıyı kullanır.
Klinik önem
Özdeğer hesaplamaları, yapısal ve makine mühendisliğinde titreşim modlarını ve doğal frekansları, dinamik sistemlerin ve kontrol döngülerinin kararlılığını, kuantum kimyası ve fiziğindeki enerji seviyelerini ve grafik bölümleme, PageRank ve temel bileşen analizi (principal component analysis) arkasındaki spektral yöntemleri belirlemektedir.
Tarihçe
QR algoritması, 1961 civarında John Francis ve Vera Kublanovskaya tarafından bağımsız olarak tanıtılmıştır ve kaydırmaların ve Hessenberg indirgemesinin eklenmesiyle yoğun özdeğer problemi için baskın yöntem haline gelmiştir; Wilkinson'ın analizi, algoritmanın güvenilirliğini ve doğruluğunu açıklayan pertürbasyon kuramını ortaya koymuştur.
Öne çıkan isimler
- James H. Wilkinson
- John G. F. Francis
- Vera Kublanovskaya
- Beresford Parlett
İlgili konular
Temel eserler
- trefethen1997
- golub2013
- wilkinson1965
Sıkça sorulan sorular
- Özdeğerler neden doğrusal bir çözüm gibi doğrudan bir formülle hesaplanamaz?
- Özdeğerler karakteristik polinomun kökleridir ve Abel teoremi uyarınca beş veya daha yüksek dereceli polinomların genel bir kök formülü yoktur, bu nedenle dört çarpı dörtten büyük matrisler için özdeğer hesaplaması yinelemeli olmak zorundadır.
- Özdeğerler her zaman iyi koşullu mudur?
- Simetrik ve diğer normal matrisler için özdeğerler mükemmel koşulludur, ancak güçlü bir şekilde normal olmayan matrisler için pertürbasyonlara karşı oldukça hassas olabilirler; bu nedenle spektrum tek başına bu tür matrislerin davranışını yakalayamayabilir.