Bu dizi ne zaman, nereye, hangi hizla yakinsar ?

Question

Su bir matriks dizisi olsun.

$x_0 = x_b$

$x_{n+1} = x_n + c(A x_n - I)$

Burada $A$ tersinebilir kare bir matriks, $I$ ise birim matriks.

hangi $c \in \mathbb{R}$ icin bu dizi yakinsar? Peki neye yakinsar ve ne kadar hizli yakinsar?

Comments

Reel sayılar (1x1 matrisler) için olan benzer bir soruya bakalım önce:

$c$ ve $d \in \mathbb{R}$ olmak üzere $x_{n+1} = (c a + 1) x_{n} - d$.

Bu dizi her $x_0 \in \mathbb{R}$ için yalnızca $| ca+1 | < 1$ ise bir limite yakınsar, sebebini okuyucuya bırakıyorum şimdilik.

$N$ boyutta diyagonal bir $A$ matrisi ve sabit bir $\vec{d}$ vektörü için benzeri bir $\vec{x}_n$ dizisi: $\vec{x}_{n+1} = (c A + I) \vec{x}_{n} - \vec{d}$.

Bu dizi de aynı sebepten her $\vec{x}_0 \in \mathbb{R}^N$ için ancak $A$'nın diyagonal elemenleri olan $a_k$'lar $| c a_k + 1| < 1$ şartını sağlarsa yakınsar. Yani yakınsama için: (I) $A$ matrisi "positive definite" veya "negatif definite" olmalı (II) $c$ sayısı $a_k$'ların tam tersi tersi işaretli ve $0 < |c| < 2/\text{max}(a_k)$ olmalı. Sorudaki matrisi bir vektörler grubu olarak düşünerek $X_0 = \begin{bmatrix} \vec{x}^{(1)}_0 & \vec{x}^{(2)}_0 & \dots & \vec{x}^{(N)}_0 \end{bmatrix}$ bu sonucu orada da kullanmaya devam edebiliriz.

Fakat cevapta hala eksik bir şey var: $A$'nın diyagonal olduğunu (veya diyagonalleştirebileceğimizi) varsaydım ama tersinir her $A$ için bir şey diyemedim.

---

Hemen size bir iki itirazimdan bahsetmek istiyorum.

$\begin{pmatrix} 2 &-1 \\ 1 &2 \end{pmatrix}$

Matrisi simetrik ne pozitif ne definit olmasina ragmen $c = -0.6$ degeri icin verilen matrisin terine yakinsiyor

---

Örneğindeki matrisi özdeğerleri $2-i$ ve $2+i$ olacak şekilde diyagonal yapabiliyoruz. Bu durumda yakınsama koşulunu karmaşık sayılarda incelemek istersek 1x1'lik durum için yaptığımız hesabı tekrarlayıp şöyle bir kapalı formül yazabiliriz: $c \in \mathbb{R}$ ve $z_n, \alpha \in \mathbb{C}$ ve $\rho = c \alpha + 1$ için

$$z_{n+1} = \rho z_n + d = \rho^{n+1} z_0 + d \sum^n_{i=0}\rho^n = \rho^{n+1} z_0 + d \, \frac{1 - \rho^{n+1}}{1 - \rho}$$

Bu ifadenin birinci ve ikinci terimi $n \xrightarrow{} \infty$ limitinde ancak $|\rho| < 1$ için yakınsaklar. Yani bulduğumuz koşulu karmaşık özdeğerli matrisleri de kapsayacak şekilde genelleştirebiliriz. Elimizdeki matris için $c=-0.6$ durumunda $\rho_1$ ve $\rho_2$ değerleri karmaşık düzlemdeki birim çemberin içinde kaldığından bu yakınsamaya güzel bir örnek oluyor.

Bu aydınlatıcı örnekten anladığım kadarıyla "positive/negative definite" matrisler demek ki bütün durumları kapsamıyormuş. Ama dikkat ederseniz özdeğerlerin ikisinin de reel kısmının $2>0$ olması yakınsama için belirleyici oldu. Buna dayanarak diyagonal bir $A$ matrisi için, özdeğerlerin sadece reel kısmına sahip olan $\frac{1}{2}(A + A^\dagger)$ matrisi pozitif mi negatif mi diye bakmak hala geçerli bir kriter olacaktır tahminim.

---

Ben de benzer sonuclar elde ettim paylasmak isterim.

 

$x_{n+1} = x_n + c(A x_n - I)$ dizisinin $A^{-1}$ e yakinsadigini varsayalim.

$\epsilon_n = A^{-1}-x_n $ olsun. $x$ dizisinin in gercekten yakinsamasi icin $\epsilon$ dizisinin limitinin $0$ olmasi gerekiyor. Bu diziyi inceleyelim. Orjinal iterasyonun icine yerlestirelim $\epsilon$ u

$ A^{-1} - \epsilon_{n+1} = A^{-1} - \epsilon_{n} + c(A (A^{-1} - \epsilon_{n}) - I)$

$\epsilon_{n+1} =  \epsilon_{n} + c A \epsilon_{n}$

$\epsilon_{n+1} =  (I + c A )\epsilon_{n}$

buradan sanirim diyebiliriz ki

$\epsilon_{m} =  (I + c A )^m \epsilon_{0}$
 

sanirim burada $ \| I+cA \| < 1$ diyip durabiliriz,

peki bu $\|\cdot\|$ ne ?

galiba burada matriks normundan cok butun matriks normlarinin infimumuna bakmak gerekiyor. Spektral yaricap aradigimiz cevap olabilir.

 

Buraradan asagisi ikinci duzenleme oncesinde yazildi .

ben spektral normu sectim. sanirim sonlu vektor uzayinda calistigimiz icin hangi normu sectigimin pek bir onemi olmamali ama emin degilim.

Bu norm bir operator normu. Yani$ \| A\|_{2,2} = sup_{x \neq 0}\frac{\|Ax\|_2}{\|x\|_2}$. Pek onemli degil sanirim yapacagimiz is icin ama gene de bahsedeyim dedim.

Spektral normu soyle hesaplayabiliriz.

$\|A\|_2 = \sigma_1(A) = \sqrt{\lambda_{max}(A^*A)}$
burada $\sigma_1$ asagida bahsettigim singular value decompositiondaki diagonal $\Sigma$ matrisinin en buyuk degeri.

 

Duzenleme sonrasi: burayi onceden yazmistim dogru sanirim ama gereksiz

ama soyle fikirler geldi aklima

$D = I + cA$ matrisinin Singular Value Decompositionini alalim.

Hatirlatma adina her $D \in \mathbb{C}^{n \times m}$ yi, su matrisleri kullanarak

$\Sigma \in \mathbb{C}^{n \times m} , U \in \mathbb{C}^{n \times n}, V \in \mathbb{C}^{m \times m} $ ,

su sekilde  ifade edebiliyoruz

$D = U\Sigma V^*$

$U$ ile $V$ burada komplex unitary matrixler.

burada hatirlatmak isterim ki unitary matriksler normu degistirmez. yani

$\|D\| = \| \Sigma \| $
yani diyebiliriz ki $I+cA$ nin singular degerlerinin normu 1 den kucuk oldugu surece yakinsar daha guzellestirmedi sanki durumu ama gene de paylasmak istedim.

 

peki $c \in \mathbb{R}$ yi birakip daha genel bir $c$ icin sorsak soruyu serinin yakinsayabilecegi matrisler degisir mi ?