Processing math: 100%

dersblog



Ders 21

Bu özdeğer/vektörler hakkındaki ilk dersimiz. Bu değerler özel büyüklüklerdir, özel sayılardır, ve onları niye istediğimizi, niye hesapladığımızı göreceğiz.

Özvektör nedir?

Elimde bir A matrisi var. Bir matris ne yapar? Vektörler üzerinde, mesela x vektörü, etkide bulunabilir, onları değiştirebilir. Sanki A'yi bir fonksiyon gibi de görebiliriz, x vektörü A'ya "giriyor" ve "dışarıya" bir Ax çıkıyor. Calculus'ta olduğu gibi f()'e bir tek sayı x veriliyor, f(x) geri dışarı çıkıyor [hakikaten de x ve Ax aynı boyutta yani giriş çıkış analojisi çok uygun]. Lineer Cebirde daha çok boyut var, giren ve çıkan vektörler.

Bu derste özellikle ilgilendiğim vektörler ise dışarı çıktığı zaman girdiği haliyle aynı yönü gösteren vektörler. Dikkat, "aynı" olan vektörler değil çıkınca aynı "yönü" gösteren vektörler. Bu tipik bir durum olmazdı değil mi? Çoğunlukla A'yi bir uyguladık mı dışarı çıkan vektör tamamen başka bir yönü gösterir. Bizim ilgilendiğimiz durumda öyle olmayacak, bu durumda Ax, x'e paralel olacak. İşte bu vektörler özvektörler olacak.

Paralel ne demektir? Formülle daha rahat belirtilir,

Ax=λx

λ, yani özdeğer, bir skalardır. İki tarafta x'in olması paralelliğe işaret ediyor, sadece büyüklük (λ üzerinden) değişik olabiliyor. Tabii büyüklük derken λ eksi değerde olabileceği için vektörün ters yönde olmasına da izin vermiş oluyoruz. λ sıfır da olabilir, hatta hayali sayı bile olabilir.

Özdeğer sıfır üzerinde biraz daha duralım. Bu durumda Ax=0x elde ederiz yani Ax=0. Bu ne demektir? x'lerin A'nin sıfır uzayında (nullspace) olması... Eğer A eşsiz (singular) ise, ki Ax=0 bu demek zaten demek ki öyle bir x olabiliyor ki Ax=0 olabiliyor, o zaman x sıfır olmayan bir vektördür, ve λ=0 bir özdeğer olmalıdır.

Bir yansıtma matrisine bakalım, mesela P. Elimizde bir düzlem (plane) var, ve bu sathın üzerinde yansıtma yapan bir P var.

b, P'nin bir özvektörü müdür? Değildir. Çünkü b ve Pb aynı yönü göstermiyorlar.

Peki, bu resme göre, yansıtma sonrası aynı yönde olacak bir vektör var mıdır? Varsa nerededir? Cevap, eğer x üstteki düzlemin tam üzerinde ise P yansıtması sonrası aynı yönde kalır. Tabii yansıtma tekrar kendisini verir, yani vektör hiç değişmemiş olur. Px=x, ki λ=1.

Başka bir özvektör var mı? Olmasını umuyorum çünkü 3 boyuttayım ve bu demektir ki 2 tane daha birbirinden bağımsız özvektör bulabilmeliyim, ki nihayetinde özvektörlerin ikisi düzlem üzerinde [düzlem iki boyutlu bir şey olduğuna göre], o zaman üçüncüsü düzlem dışında olacak. Düzlem dışında olan özvektör dik olan özvektör olmalı.

Bu durumda Px=0, ve λ=0, çünkü dikliğin bir diğer tanımı çarpım sonrası sonucun sıfır olması.

Bir diğer örnek. Şu permutasyon matrisine bakalım.

A=[0110]

Bu matrisi hangi vektör ile çarparsam aynı yönde bir vektör elde ederim? Permutasyon matrisi tanım itibariyle permutasyon yapar, yani öğelerin yerini değiştirir. İki boyut bağlamında bir vektörün iki öğesinin yerini değiştirecektir. Peki hangi vektörün öğeleri yer değiştirirse yine kendisi olur? Cevap basit, x=[11].

x=[11],Ax=[11],λ=1,Ax=x

Bir tane daha özdeğer/vektör lazım. Bu diğer özdeğer λ=1 olmalı. Peki nasıl bir vektör olmalı ki öğeleri yer değiştirince ters yönü göstersin?

x=[11],Ax=[11],λ=1,Ax=x

Özvektör/değerler hakkında ufak bir şey daha söylemek istiyorum. N×N matrisinin N tane özdeğeri vardır. Bu değerleri bulmak kolay değildir. 1., 2., hatta N'inci seviye bir denklemden çıkar bu değerler. Fakat bize yardım eden bir numara vardır, tüm özdeğerlerin toplamı matrisin köşegen değerlerinin toplamına eşittir, ki bu toplama "iz" (trace) ismi verilir.

Bu numarayı üstteki örnekte kullanırsak, λ=1 bulduğum anda diğer özdeğerin -1 olduğunu hemen bilirim, çünkü ana matrisin izi sıfır, 01=1.

Artık özdeğer/vektör hesabına gelelim. Ax=λx denklemi var, bu denklemde iki bilinmeyen var. Bu denklemi nasıl çözerim? Bir numara, her şeyi tek tarafa gönderirim,

(AλI)x=0

Şimdi bu denklem bana bir şeyler söylüyor. Eğer bir x "var" ise, bu varlık, AλI'nin eşsiz olduğu anlamına gelir. Peki eşsiz matrisler hakkında ne biliyorum? Determinantlarının sıfır olduğunu biliyorum. Yani,

det(AλI)=0

Bu denklem özdeğer denklemi, ya da karakteristik denklem (characteristic equation) olarak bilinir.

İlk önce λ bulmakla işe başlarım. Tabii N tane λ olacaktır, bunların hepsini bulmakla işe başlarım. Not: N λ olması demek N değişik λ olması anlamına gelmiyor, bazı λ değerleri kendini tekrar edebilir. Tabii tekrarlanan λ bizim dersteki her türlü derdin kaynağıdır [biraz şaka biraz gerçek havasıyla söylüyor hoca].

λ'yi bulunca ne yaparım? Matrisin sıfır uzayını hesaplarım, ki artık bu işlemde usta olduk, eliminasyona başlarım, pivot bulurum, vs.

Örnek

A=[3113]

Bu matris simetrik. Bu tür özel şartlar matrisin özdeğerlerinin de özel olması anlamına gelir. Mesela simetrik matrislerin tüm özdeğerlerinin reel sayı olduğunu hemen bilirim. Peki özvektörler? Birbirlerine dik olurlar. Bir önceki örneği hatırlarsak, [11] ve [11].

det(AλI)=[3λ113λ]=(3λ)21=0

λ26λ+8=0

Bu formüldeki 6 nedir? Matris izinin eksi hali. Peki 8? O da determinant. Yani 2x2 durumunda sayılar çok basit şekilde ortaya çıkıyorlar. Neyse, üstteki formülü faktorize edelim, (λ4)(λ2), yani λ1=4,λ2=2.

Şimdi özvektörler: Bu vektörler köşegenden 2 ya da 4 çıkartıldığı zaman ortaya çıkan matrislerin sıfır uzayıdır.

[341134]=[1111]

Bu matris eşsiz mi? Öyle. Bu matrisi x1=[11] ile çarparsam sıfır elde ederim. Diğeri?

[321132]=[1111]

x2=[1 1]. Bu da ikinci özvektör.

İlginç bir durum, bu sonuç permutasyon matrisinden gelen sonuca çok benziyor. Fark nerede? Ana matrisin köşegenine 3 eklenmiş, ya da A+3I yapılmış. Bunu yapınca özdeğerlere 3 eklemiş oldum. Ama özvektörler hiç değişmeden kaldı.

Daha çetrefil bir örnek görelim. Diyelim ki iki matris A,B'nin özdeğerlerini biliyorum. A+B'nin özdeğerleri λ,α nedir? İlk akla gelen cevap "özdeğerleri toplanır" doğru değil. Çünkü

(A+B)x=(λ+α)x

demiş oluruz, ama bunu derken özvektörler aynı demiş oluruz. Bu doğru değildir. AB aynı şekilde. Bunlar kötü örnekler.

Bir örnek daha yapalım, bu sefer döndürme / rotasyon (rotation) matrisi. 90 derece döndürme matrisi olsun.

Örnek

Q=[cos90sin90sin90cos90]=[0110]

Bu bir dik, dikgen (orthogonal) bir matris. Özdeğerlerin toplamı sıfır olacak, çünkü iz öyle. Determinant özdeğerlerin çarpımına eşit, yani bu çarpım 1 olacak.

Fakat bu örnekte bazı şeyler yanlış gidecek. Niye? Düşünelim, hangi vektör bu matrise verilince, döndürüldükten sonra dışarı aynı yönde olarak çıkar? Özellikle 90 derece döndürüldükten sonra. Gördüğünüz gibi problem çıkabilir. Özdeğerler ile de problem var, toplamı 0 olan ama çarpımı 1 olan nasıl sayılar bulabileceğiz ki?

Fakat bir çare var. Hesaplayalım,

det(QλI)=[λ11λ]=λ2+1=0

Özdeğerler nedir? λ1=i,λ2=i. Bu sayılar kompleks / hayali sayılardır, reel değillerdir. Bu olabilir. Bir matris, üstte olduğu gibi, tamamen reel sayılardan oluşabilir, ama özdeğerleri hayali olabilir.

Bu iki hayali sayı birbirinin kopmleks eşleniği (complex conjugate). Kompleks eşleniğin ne olduğunu hatırlıyoruz herhalde, bir sayının hayali kısmının işaretini değiştirince onun kompleks eşleniğini elde etmiş olurum. Üstteki sayılar zaten tamamen hayali bölümden oluşuyor, hiç reel kısımları yok, o tek kısmın da işaretini değiştirince eşleniği elde ediyorum.

Eğer matrisim simetrik, ya da "simetriğe yakın" olsaydı, üstteki durum kesinlikle ortaya çıkmazdı. Çünkü kural odur ki, simetrik matrislerin özdeğerleri reeldir.

Bol bol örnek veriyorum ki tüm olasılıkları görebilelim.

Bir kötü ihtimal daha.

A=[3103]

Bu matris üçgensel (triangular). Bu tür matrislerde özdeğerler köşegenin üzerindedir! Bunu bilmek oldukça faydalıdır. Ama kontrol edelim,

det(QλI)=[3λ103λ]=(3λ)(3λ)=0,λ1=3,λ2=3

Problem nerede? Problem özvektörlerde. Hatırlayalım,

(AλI)x=0

denklemini çözüyoruz, yani

(AλI)x=[0100]x=[00]

Burada x sonucunu arıyorum, bir vektör. Kafadan hemen birinci özvektörü bulabilirim,

x1=[10]

Peki ikinci özvektör nedir? Bu vektörün birinciden bağımsız olması gerekir, unutmayalım. Böyle bir vektör bulabilir miyiz? Bulamayız. Mümkün değil. Bu sebeple bu örneğe dejenere durum (değenerate case) denir. İkinci bir bağımsız özvektör yoktur.

Ekler

Alttaki anlatım alternatif bir kaynaktan alınmıştır

Özvektörler, Özdeğerleri Elle Hesaplamak (Eigenvectors, Eigenvalues)

Özdeğerler ve özvektörler her matrise göre özel vektörlerdir, ki matris bu özel vektörleri transform ettiğinde / işlediğinde sonuç yine özvektörün kendisidir, daha doğrusu onun bir sabit (özdeğer) ile çarpılmış halidir. Yani

Ax=λx

Tek tarafa geçirelim

Axλx=0

Bu noktada x'leri dışarı çekmek isterdik, fakat bunu yapamayız, çünkü o zaman içeride Aλ kalır ve bu olmaz, çünkü A bir matris, λ bir tek sayı. Ama Ix=x'ten hareketle

AxλIx=0

diyebiliriz. Şimdi dışarı çekersek

(AλI)x=0

Bu ifadenin doğru olması için parantez içindeki ifade / matris eşsiz (singular) olmalıdır. Bunun için ise parantez içinin determinantı sıfır olmalıdır. Yani

|AλI|=0

Örnek

A=[1435]

AλI=[1435]λ[1001]

=[1λ435λ]

det(AλI)=(1λ)(5λ)43

Üstteki denkleme karakteristik denklem (characteristic equation) denir.

=76λ+λ2

Kökleri λ1=7, λ2=1.

Her özdeğere tekabül eden özvektörü bulmak istiyorsak, çıkartma işlemini yapalım

AλI=[174357]=[6432]

Şu formüle dönersek

(AλI)x=0

Çıkartma sonrası elimize geçen matrisi çarpacak öyle bir x vektörü arıyoruz ki bu vektörle çarpınca elimize sıfır (vektörü) geçsin. Yani bu aradığımız x vektörü (AλI)'nin sıfır uzayında (nullspace).

2 x 2 boyutundaki böyle ufak bir örnek için x'i aslında tahmin edebiliriz. Öyle iki sayı bulalım ki, 1. ve 2. kolonu onlarla ayrı ayrı çarpıp topladığımızda sonuç sıfır olsun. Her iki kolonun tepesinde -6 ve 4 görüyorum, sadece bu iki sayının sıfıra toplanması için acaba -6'yı 2 ile 4'ü 3 ile çarpıp toplasam olur mu? Kolondaki diğer sayılara bakıyoruz, 3 ve -2 için de bu işe yarıyor. Demek ki özvektörlerden biri

x1=[23]

Diğeri ise, aynı tekniği kullanarak,

x2=[21]

Ekler

Özdeğer/Vektör Hesabında Üst Metot (Power Method)

Diyelim ki bir A matrisinin, ki ARn×n, özdeğerleri λ1,...,λn ve özvektörleri v1,..,vn olarak verilmiş. Bu demektir ki her i=1,..,n için Avi=λivi. Farzedelim ki bu matrisin tüm özvektörleri bir "özbaz (eigenbasis)" oluşturuyor ve bu baz ile Rn'deki herhangi bir vektörü temsil edebiliyoruz. Hatırlayalım eğer tekrar eden özdeğer yok ise (hepsi değişik), normalize edilmiş vi vektörleri birimdik (orthonormal) bir set oluştururlar, ||v||=1,vTivi=1,vTjvi=0 demektir.

Diyelim ki |λ1|>|λ2|>..>|λn|, bu yazıda λ1'e baskın (dominant) özdeğer diyeceğiz. Şimdi Herhangi bir v0Rn'i alalım. Üsttekiler ışığında μ1,..,μn olarak öyle katsayılar olmalıdır ki

vo=μ1v1+..+μnvn

çünkü özvektörler bir baz oluşturuyorlar. Şimdi her iki tarafı soldan A ile çarpalım, ayrıca Avi=λivi eşitliğinden hareketle üstteki eşitliğin sağ tarafını alıp üçüncü bir eşitlik olarak en sağda yazalım,

Avo=μ1Av1+..+μnAvn=μ1λ1v1+...+μnλnvn

Şimdi üstteki ifadeyi A ile bir daha, hatta birkaç defa çarpalım, diyelim toplam m kere çarpmış olalım,

Amvo=μ1Amv1+..+μnAmvn=μ1λm1v1+...+μnλmnvn(1)

En sağda niye λmi ifadeleri elde ettik? Mesela μ1λ1v1 ifadesi, A ile bir kere çarpılınca,

μ1λ1Av1λ1v1=μ1λ1λ1v1=μ1λ21v1

olacaktır. Bunu m kere yapınca (1)'in en sağındaki sonucu elde ederiz.

Şimdi (1)'in en sağındaki eşitliğin içinden λm1'i çıkartalım (1)'ın en solundaki eşitlik ile yanyana getirelim,

Amvo=λm1(μ1v1+μn(λ2λ1)mv2+...+μn(λnλ1)mvn)

İspatın başında baskın özdeğerin λ1 olduğunu söylemiştik. O zaman

|λ2λ1|<1,...,|λnλ1|<1

Bu demektir ki limit koşulu m durumunda

Amvo=λm1(μ1v1+μn(λ2λ1)mv2+...+μn(λnλ1)mvn0)

Yani,

Amvo=λm1μ1v1

çünkü 1'den küçük olan tüm bölümler, katları alındıkça ve o kat (m) çok büyüdüğünde sıfıra giderler. Bu bölümleri içeren tüm terimler yokolur ve geriye üstteki ifade kalır.

Böylece üst metodunu türetmiş olduk. En son ifade şunu söylüyor, herhangi bir vektör v0'i alalım, ve onu A ile m kere çarpalım, ve bu durumda elimize gerçek özvektör v1'e paralel bir vektör λm1μ1v1 geçecektir (paralel çünkü v1 değeri tek sayı / skalar λmμ1 ile çarpılmakta). Bu vektörü normalize ederek bir özvektör sonucu elde edebiliriz. Unutmayalım, özvektörlerin sadece yönü ile ilgileniyoruz, büyüklükleri ile ilgilenmiyoruz, eğer v1 bir özvektör ise, herhangi bir skalar k için kv1 de bir özvektördür. Ders başında özvektörlerin "A ile çarpılıp yönünün değişmemesi" bağlamında tanımlandığını aklımızda tutalım [2].

Örnek olarak alttaki A'yi alalım, başlangıç olarak v0=[11]

v0 = np.array([1.,1.])
A = np.array([[13., 5.], [2., 4.]])
for i in range(20): 
    v0 = np.dot(A,v0)
print 'v0 =',v0
v0 = [  1.14093076e+23   2.28186151e+22]

Sonsuzluk norm'u (infinity norm) ile normalize edersek (sonsuzluk normu bir vektör içindeki en büyük öğenin alınıp bölümde kullanılmasıyla yapılan normalizasyondur),

v1 = v0 / np.max(v0)
v1 = v1.reshape((2,1))
print 'v1 ='
print v1
v1 =
[[ 1. ]
 [ 0.2]]

Kontrol edelim,

import numpy.linalg as lin
U,D = lin.eig(A)
print U
print D
[ 14.   3.]
[[ 0.98058068 -0.4472136 ]
 [ 0.19611614  0.89442719]]

Birinci kolona oldukça yakın bir değer elde ettik, ki en büyük özdeğere tekabül eden özvektör orada.

Peki özdeğerin kendisini nasıl buluruz? Rayleigh Bölümü (Rayleigh Quotient) formülünü kullanabiliriz. Bu formül, eğer x bir özvektör ise

λ=xTAxxTx

Türetelim,

Ax=λx

xTAx=xTλx

λ bir tek sayı olduğuna göre sağ taraftan xTx'i alıp, solda bölüm yapabiliriz, ve Rayleigh formülüne erişiriz.

xTAx/xTx=λ

  1. özdeğeri hesaplayalım o zaman,
print np.dot(np.dot(v1.T,A),v1) / np.dot(v1.T,v1)
[[ 14.]]

Tüm Özvektörler

En büyük özdeğeri bulmanın yolunu gördük. Diğer özvektörleri nasıl buluruz? Bunun yöntemlerinden birisi en büyük özdeğer λ1'i bulduktan sonra onu bir işlem sonrası en küçük haline getirmek, ve Üst Metotu tekrar kullanarak (artık en büyük olan) λ2'yi bulmak. λ1'i en küçük haline getirmek, özdeğer/vektörü ana matris A'dan çıkartmak, onu "deflasyon işlemine tabi tutmak" (deflation) olarak biliniyor. Çıkartacağımız değer λ1u1uT1 olacak. İspatı şöyle gösterelim (normalize edilmiş vi özvektörleri şimdi ui olarak gösteriyoruz),

(Aλ1u1uT1)uj=Aujλ1u1uT1u1uj=λjujλ1u1(uT1uj)

Eğer j=1 ise

(Aλ1u1uT1)u1=λ1u1λ1u1(uT1u1)=0uj

Eğer j1 ise

(Aλ1u1uT1)uj=λjujλ1u1(uT1uj)=λjuj

Yani (Aλ1u1uT1)'nin özvektörleri A ile aynıdır, tek farkı en büyük olanı 0 haline gelmiştir, ama j1 için, yani diğer tüm özvektörleri aynıdır. O zaman deflasyon işleminden sonra ele geçen yeni matris üzerinde Üst Metotu tekrar kullanırsak artık en büyük olan u2'yi buluruz, sonra deflasyonu tekrarlarız, bir daha Üst Metot işletiriz, bu böyle devam eder.

lam1 = 14.
v0 = np.array([1.,1.])
B = A - np.dot(v1,v1.T)*lam1
print 'B'
print B
for i in range(20): 
    v0 = np.dot(B,v0)
v2 = v0 / np.max(v0)
v2 = v2.reshape((2,1))
print 'v2'
print v2
B
[[-1.    2.2 ]
 [-0.8   3.44]]
v2
[[ 0.55]
 [ 1.  ]]

Rayleigh Bölümü ile ikinci özdeğeri bulalım,

print np.dot(np.dot(v2.T,B),v2) / np.dot(v2.T,v2)
[[ 3.]]

Kaynaklar

[1] Feys, MATH317 EIGHTEENTH TUTORIAL, http://www.math.mcgill.ca/feys/documents/tutnotesR18.pdf

[2] Woolgar, Lab 15-Power Method and Dominant Eigenvalues, http://www.math.ualberta.ca/~ewoolgar/labs/linalg/Lab15.pdf

[3] Roberts, Computation of matrix eigenvalues and eigenvectors , http://www.robots.ox.ac.uk/~sjrob/Teaching/EngComp/ecl4.pdf

[4] Murphy, K., CS340: Machine Learning Lecture Notes, www.ugrad.cs.ubc.ca/~cs340

[6] Zaki, Maira, Fundamentals of Data Mining Algorithms


Yukarı