13 Özdeğer ve Tekil Değerleri Hesaplamak

QR iterasyonu, shift, Hessenberg ve bidiagonal

Bölüm bilgisi

Video: Computing Eigenvalues and Singular Values · OCW: MIT 18.065 Lecture 12 · Okuma süresi: ~36 dk · Eğitmen: Gilbert Strang · Önkoşul: Ders 11 (QR faktorizasyonu, Gram-Schmidt ve ortonormal tabanlar).

13.1 Bu Derste Ne Var?

eig ve svd perde arkasında ne yapar? Ders 11’in QR’ı beklenmedik bir yere uygulanır: özdeğer hesabı. Strang QR iterasyonunu, shift’i ve Hessenberg/tridiagonal ön-işlemeyi anlatır.

Üç temel fikir:

QR iterasyonu — $A = QR \to A_1 = RQ \to$ tekrarla; $A_1 = Q^{-1}AQ$ benzerdir (özdeğer korunur), köşegen-altı söner, özdeğerler köşegende belirir.
Ön-işleme — önce Hessenberg (simetrikte tridiagonal) forma indir; QR’ı çok hızlandırır. İteratif olmak zorunda (Abel: 5. derece denklemin formülü çözümü yok).
Tekil değerler — $A^{T}A$ KURMA (kondisyon karelenir), determinant KULLANMA; iki-yönlü ortogonal ($Q_1 A Q_2$) $\sigma$’ları korur → bidiagonal forma indir.

Bütün bu fikirlerin tek bir merkezden nasıl dallandığını Şekil 13.1 özetliyor: özdeğer/tekil değer hesabının kalbinde QR iterasyonu, çevresinde benzerlik, shift, Abel sınırı ve ön-işleme vardır.

flowchart TD
    M["Özdeğer / tekil değer hesabı"] --> QR["QR iterasyonu: A = QR → A₁ = RQ → tekrarla"]
    M --> SIM["benzerlik A₁ = Q⁻¹AQ → özdeğer korunur"]
    M --> DEC["köşegen-altı söner (kübik) → özdeğerler köşegende"]
    M --> SHIFT["shift A − sI → hızlandırır"]
    M --> ABEL["Abel: 5. derece+ formül yok → iteratif"]
    M --> PRE["ön-işleme: Hessenberg / simetrik → tridiagonal"]
    M --> SVD["SVD: AᵀA KURMA → bidiagonal"]

    LAP["LAPACK eig / svd"]

    style M fill:#1f4e79,color:#fff,stroke:#13243a,stroke-width:2px
    style LAP fill:#1f4e79,color:#fff,stroke:#13243a,stroke-width:2px
    style QR fill:#2e75b6,color:#fff,stroke:#13243a,stroke-width:2px
    style SIM fill:#2e75b6,color:#fff,stroke:#13243a,stroke-width:2px
    style DEC fill:#2e75b6,color:#fff,stroke:#13243a,stroke-width:2px
    style SHIFT fill:#6fa8dc,color:#13243a,stroke:#1f4e79,stroke-width:2px
    style ABEL fill:#6fa8dc,color:#13243a,stroke:#1f4e79,stroke-width:2px
    style PRE fill:#6fa8dc,color:#13243a,stroke:#1f4e79,stroke-width:2px
    style SVD fill:#6fa8dc,color:#13243a,stroke:#1f4e79,stroke-width:2px

Şekil 13.1: Ders 12 kavram haritası: özdeğer / tekil değer hesabı merkezinden ana fikirlere dallar — QR iterasyonu (A = QR → A₁ = RQ → tekrarla), benzerlik (A₁ = Q⁻¹AQ özdeğeri korur), köşegen-altının kübik sönmesi (özdeğerler köşegende), shift (A − sI yakınsamayı hızlandırır), Abel sınırı (5. derece+ kapalı formül yok → iteratif), ön-işleme (Hessenberg, simetrikte tridiagonal) ve SVD (AᵀA KURMA → bidiagonal); ayrıca her şeyi çalıştıran LAPACK eig/svd düğümü.

“It’s called the QR method because you start by factoring your matrix into QR.” — Strang, 2:12

Builder Notu — eig’in Motoru

QR iterasyonu = eig’in motoru: numpy.linalg.eig/eigh arka planda Hessenberg/tridiagonal + shift’li QR (LAPACK) çalıştırır; doğrudan çağırırsın, kütüphane optimize eder.
Benzerlik = özdeğer korur — her QR adımı $A_1 = Q^{-1}AQ$; spektral yöntemlerin (PCA, GCN) hesap temeli.
AᵀA’dan kaçın — tekil değer için $A^{T}A$ kurmak kondisyonu kareler (Ders 6); SVD doğrudan $A$ üzerinde bidiagonalleştirme + QR ile bulunur.
Abel sınırı — özdeğer/tekil değer kesin formülü yok (5. derece+); sadece iteratif yaklaşım, $\varepsilon$-yakın cevap.

Tek cümle: özdeğer/tekil değer hesabının motoru QR iterasyonudur — benzerlik dönüşümleriyle köşegen-altını söndürür; Hessenberg/tridiagonal/bidiagonal ön-işleme ve shift onu pratik kılar.

13.2 1. QR Yöntemi: A = QR → RQ

Özdeğerleri hesaplamak için QR faktorizasyonu (Ders 11) beklenmedik biçimde anahtar olur. Matrisi QR’a ayır, sonra çarpanları ters sırada çarp — yeni matris bu:

\[A_0 = Q_0 R_0, \qquad A_1 = R_0 Q_0\]

“It’s called the QR method because you start by factoring your matrix into QR.” — Strang, 2:12

Sonra $A_1$’i tekrar QR’a ayır, ters sırada çarp, $A_2$ üret — tekrar tekrar. Umut: özdeğerler değişmesin ve matris köşegene yakınsasın.

QR iterasyonunun bir simetrik matriste köşegeni adım adım özdeğerlere nasıl taşıdığını Şekil 13.2 gösteriyor: köşegen-altı sönerken köşegen değerleri kesik çizgilerle işaretli gerçek özdeğerlere oturuyor.

Kod

A = np.array([[4., 1., 0.], [1., 3., 1.], [0., 1., 2.]])
Af, dh, sh = qr_iteration(A, 25)

fig, ax = plt.subplots(figsize=(6.4, 4.4))
apply_style(ax)
renkler = [COL_PRIMARY, COL_ACCENT, COL_TEAL]
for i in range(3):
    ax.plot(range(len(dh)), dh[:, i], color=renkler[i], marker="o", ms=3, label="köşegen " + str(i + 1))
ev = np.sort(np.linalg.eigvalsh(A))[::-1]
for e in ev:
    ax.axhline(e, ls=":", color=COL_STEEL_300, lw=1)
ax.set_xlabel("QR iterasyon adımı")
ax.set_ylabel("köşegen değerleri")
ax.set_title("QR iterasyonu: köşegen değerleri özdeğerlere yakınsar (A=QR → RQ tekrarla)",
             color=COL_TEXT, fontsize=10, fontweight="bold")
ax.legend()

plt.show()

Şekil 13.2: QR iterasyonu ($A=QR \to A_1=RQ$ tekrarla): bir simetrik $A$’nın köşegen girdileri adım adım özdeğerlere (kesik çizgiler) yakınsar — köşegen-altı sıfıra sönerken köşegende özdeğerler beliriyor.

Builder Notu — Ters Sırada Çarp

QR iterasyonu, numpy.linalg.eig/eigh’in (LAPACK) motorudur. “A = QR sonra RQ” döngüsü, 1960’larda özdeğer hesabını kökten değiştirdi — önceki tüm yöntemleri silip süpürdü. Sen eig çağırırsın, arka planda bu döner.

13.3 2. Neden Özdeğerler Korunur (Benzerlik)

$A_1$’in özdeğerleri $A_0$’la aynı mı? İki matrisin aynı özdeğere sahip olduğunu göstermenin en iyi yolu: benzer olduklarını göstermek (Ders 4).

“They’re similar, that’s right.” — Strang, 4:29

$A_1 = R_0 Q_0$. $Q_0 R_0 = A_0$ olduğundan $R_0 = Q_0^{-1}A_0$; yerine koy:

\[A_1 = R_0 Q_0 = Q_0^{-1}(Q_0 R_0)Q_0 = Q_0^{-1} A_0 Q_0\]

Bu tam bir benzerlik dönüşümüdür → $A_1$ ve $A_0$ aynı özdeğerlere sahiptir. Her QR adımı özdeğerleri korur; yalnızca temsili değiştirir.

Builder Notu — Benzerlik Güvencesi

“Her adım $Q^{-1}AQ$ benzerliği” güvencesi, iterasyonun özdeğerleri bozmadan matrisi sadeleştirmesini sağlar. Aynı benzerlik fikri (taban değişimi özdeğeri korur) PCA, spektral kümeleme ve ağ reparametrizasyonunun ortak ilkesidir.

13.4 3. Köşegen-altı Söner → Özdeğerler

Mucize: çoğu matriste QR adımları köşegen-altı girdileri giderek küçültür. $A_0 \to A_1 \to A_2 \ldots$ köşegen-altı epsilonlara iner ve köşegende özdeğerler belirir.

“…the eigenvalues pop up on the diagonal.” — Strang, 17:36

2×2 örnekte köşegen-dışı girdi her adımda küpü alınır ($\sin\theta \to \sin^3\theta \to \sin^9\theta \to \ldots$), yani çok hızlı 0’a gider:

“…cubic convergence…” — Strang, 9:29

Köşegen-altı küçük epsilonlar özdeğerleri pek değiştirmez (benzerlik korur), o yüzden köşegen değerleri özdeğerlere yakınsar — en alttaki önce.

Köşegen-altı girdinin log eksende ne kadar dik düştüğünü Şekil 13.3 gösteriyor: birkaç adımda sıfıra çöken bu eğri, kübik yakınsamanın imzasıdır.

Kod

A = np.array([[4., 1., 0.], [1., 3., 1.], [0., 1., 2.]])
_, _, sh = qr_iteration(A, 12)

fig, ax = plt.subplots(figsize=(7, 4.2))
apply_style(ax)
ax.semilogy(range(len(sh)), np.maximum(sh, 1e-16), color=COL_PRIMARY, marker="o", ms=5, label="alt-köşegen |girdi|")
ax.set_xlabel("QR iterasyon adımı")
ax.set_ylabel("alt-köşegen |girdi| (log)")
ax.set_title("Köşegen-altı girdi her adımda hızla söner (→ 0): özdeğerler köşegende beliriyor", fontsize=10, fontweight="bold")
ax.legend()

plt.show()

Şekil 13.3: Köşegen-altı girdi her QR adımında hızla söner (→ 0): A=QR → RQ tekrarlandıkça özdeğerler köşegende beliriyor. Log eksende dik düşüş, kübik yakınsamanın imzasıdır.

Builder Notu — Kübik Hız

Kübik yakınsama, QR iterasyonunu pratik kılan şeydir: birkaç adımda makine hassasiyetine ulaşır. Bu hız, eig’in milisaniyelerde çalışmasının sebebi; büyük matrislerde ise yalnız baskın özdeğerleri arayan yöntemler (Lanczos, Ders 11) devreye girer.

13.5 4. Shift (Kaydırma) ile Hızlandırma

Numerik analistler daha hızlısını istedi ve shift (kaydırma) bulundu. Birim matrisin bir katını çıkar, QR yap, ters sırada çarp, kaydırmayı geri ekle:

\[A_0 - sI = QR, \qquad A_1 = RQ + sI\]

“…the idea of introducing a shift…” — Strang, 10:27

$sI$ ile kaydırmak özvektörleri değiştirmez, özdeğerleri $s$ kadar kaydırır ($\lambda \to \lambda - s$). İyi seçilmiş bir shift yakınsamayı çok hızlandırır. Ve benzerlik korunur: $R(Q)$ hesabında $R_0$ ile $R_0^{-1}$ sadeleşir, çıkarılan $sI$ ile eklenen $sI$ birbirini götürür → $A_1$ hâlâ $A_0$’a benzerdir.

Shift’in yakınsamayı ne kadar dramatik hızlandırdığını Şekil 13.4 gösteriyor: saf QR sekiz adımda ancak ilerlerken Wilkinson shift’li QR tek adımda makine hassasiyetine çöker.

Kod

# Aynı simetrik A: saf QR vs Wilkinson shift'li QR (alt-köşegen sönmesi)
Ash = np.array([[3., 1.], [1., 2.]])
_, _, sh_plain = qr_iteration(Ash, 8)        # shift yok
_, sh_shift = qr_iteration_shift(Ash, 8)     # Wilkinson shift

fig, ax = plt.subplots(figsize=(7, 4.2))
apply_style(ax)
ax.semilogy(range(len(sh_plain)), np.maximum(sh_plain, 1e-16),
            color=COL_VEC3, marker="s", ms=5, label="shift yok")
ax.semilogy(range(len(sh_shift)), np.maximum(sh_shift, 1e-16),
            color=COL_PRIMARY, marker="o", ms=5, label="Wilkinson shift")
ax.set_xlabel("adım")
ax.set_ylabel("alt-köşegen |girdi| (log)")
ax.legend()
ax.set_title("Shift (A-sI) yakınsamayı uçurur: Wilkinson shift birkaç adımda makine hassasiyeti",
             fontsize=10, fontweight="bold", color=COL_TEXT)

plt.show()

Şekil 13.4: Shift (A − sI) yakınsamayı uçurur. Aynı 2×2 simetrik A için alt-köşegen girdisinin büyüklüğü (log ölçek): turuncu kareler saf QR iterasyonu (shift yok) — her adımda yalnızca geometrik olarak küçülür ve 8 adımda hâlâ 10⁻³ düzeyinde. Navy daireler Wilkinson shift’li QR — tek adımda makine hassasiyetine (≈10⁻¹⁶) çöker. Shift, özdeğeri köşegene fırlatarak yakınsamayı dramatik biçimde hızlandırır.

Builder Notu — Akıllı Kaydırma

Shift, QR iterasyonunu pratikte kullanılabilir kılan hızlandırmadır (özellikle son özdeğere yakın shift seçmek). Aynı “kaydır-çöz-geri kaydır” fikri ters iterasyon (inverse iteration) ve önkoşullamada da görülür; bilinen bir özdeğer tahminine yakınsamayı hızlandırır.

13.6 5. Tam Çözüm İmkânsız (Abel)

Neden tam çözüm yok, neden iterasyon? Eliminasyonda $Ax = b$’yi sonlu adımda tam çözeriz. Ama özdeğerler $n.$ dereceden bir denklemin kökleridir ve Abel bir asır önce kanıtladı: 5. derece ve üstü denklemin kökleri için kapalı formül yoktur.

“5th degree, yeah.” — Strang, 21:36

Yani özdeğerleri (ve tekil değerleri) sonlu, kesin adımlarla bulmak matematiksel olarak imkânsızdır — yalnızca QR iterasyonuyla istediğimiz kadar ($\varepsilon$) yaklaşabiliriz. Özdeğer problemi, $Ax = b$’den bir zorluk seviyesi yukarıdadır.

Builder Notu — Abel’in Duvarı

Abel sınırı, neden eig’in “kesin” değil “$\varepsilon$-yakın” olduğunu açıklar: ~$n^3$ adımda makine hassasiyetine ulaşır ama prensipte sonsuz adım gerekir. Bu, sayısal lineer cebir ile cebirin temel ayrımı — ML’de özdeğer/SVD hep yaklaşık (ama pratikte yeterince kesin).

13.7 6. Hessenberg Formu (Ön-İşleme)

İş nerede? QR faktorizasyonunda. Onu hızlandırmak için matrisi önce çok sıfırlı bir forma indir. Tam üçgensel yapamayız (özdeğerleri bulmuş olurduk, Abel yasak), ama köşegenin bir altına kadar sıfırlayabiliriz — Hessenberg formu.

“Upper Hessenberg.” — Strang, 22:56

Hessenberg matris = üst üçgensel + bir alt köşegen, gerisi sıfır (≈yarı $n^2$ sıfır). Bu sıfırlar QR adımlarında sıfır kalır, böylece her QR çok daha ucuz. Tam yöntem: (1) A’yı benzerlikle Hessenberg’e indir, (2) shift’li QR uygula.

Dolu bir simetrik matrisin ön-işlemeyle nasıl tridiagonal yapıya indiğini Şekil 13.5 gösteriyor: 16 dolu girdi yalnız ana köşegen + bir alt/üst köşegene (~2n sayı) iniyor.

Kod

S = np.array([[4., 1., 2., 0.5],
              [1., 3., 0.7, 1.],
              [2., 0.7, 5., 1.2],
              [0.5, 1., 1.2, 2.]])

fig, axs = plt.subplots(1, 2, figsize=(7, 3.6))
spy_structure(axs[0], S, "simetrik A (dolu)")
spy_structure(axs[1], hessenberg_form(S), "tridiagonal (~2n sayı)")
fig.suptitle("Ön-işleme: simetrik A → tridiagonal (benzerlik, özdeğer korunur); QR adımları O(n) çok hızlı",
             color=COL_TEXT, fontsize=10, fontweight="bold")
plt.show()

Şekil 13.5: Ön-işleme: simetrik bir matris A, benzerlik dönüşümleriyle tridiagonal forma indirilir. Sol panelde dolu simetrik A’nın 16 girdisi, sağ panelde tridiagonal yapının yalnızca ana köşegen ile bir alt/üst köşegeni (~2n sayı) doludur. Özdeğerler korunur, sonraki QR adımları O(n) çok hızlı çalışır.

Builder Notu — Yarı Yol Sıfır

Hessenberg ön-işleme, eig’in iki aşamalı yapısının ilk yarısıdır (LAPACK). Benzerlik dönüşümüyle (Householder) yapıldığından özdeğerleri korur ve sonraki QR adımlarının maliyetini $O(n^2)$’den çok aşağı çeker — pratik özdeğer hesabının sırrı.

13.8 7. Simetrik → Tridiagonal

Matris simetrikse daha da iyi. QR adımları simetriyi korur ($A_0$ simetrik → $A_1$ simetrik). Simetrik + Hessenberg = tridiagonal: yalnız ana köşegen + bir üst + bir alt köşegen.

“…tridiagonal matrix.” — Strang, 27:09

Tridiagonal matriste yalnızca ~2n sayı vardır (üst ve alt köşegen simetriden eşit). QR adımları tridiagonalliği korur, böylece her adım $O(n^2)$ yerine $O(n)$ — “bomba gibi” hızlı. Simetrik eigh bu yüzden çok hızlıdır.

Builder Notu — İki Köşegen Yeter

Simetrik → tridiagonal indirgeme, kovaryans/Gram/Hessian gibi ML matrislerinin özdeğerlerini hesaplamanın hızlı yoludur (numpy.linalg.eigh). PCA, kernel yöntemleri ve spektral kümeleme bu rutinin hızına dayanır.

13.9 8. eig(A): Hessenberg + Shift’li QR

Tam algoritma iki adımdır: (1) A’yı Hessenberg (simetrikse tridiagonal) forma indir, (2) shift’li QR uygula. eig(A) perde arkasında bunu yapar — ama Matlab/NumPy kendi kodunu değil, profesyonel LAPACK rutinlerini çağırır.

LAPACK, on yazarlı, onyıllarca emek verilmiş sayısal lineer cebir “İncili”dir; özdeğer kodları indirilebilir ve her ciddi sistem ona dayanır. Yani sen eig/eigh/svd çağırırsın, dünyanın en iyi sayısal analistlerinin kodu çalışır.

Builder Notu — LAPACK’i Çağır

“Kendin yazma, LAPACK çağır” — sayısal ML’nin altın kuralı. Özdeğer/SVD rutinleri (geev, syev, gesdd) onlarca yıllık kararlılık çalışmasının ürünü; elle QR yazmak hem yavaş hem riskli. NumPy/PyTorch/SciPy hepsi LAPACK’e köprüdür.

13.10 9. Tekil Değerler: AᵀA ve Determinant’tan KAÇIN

Tekil değerler $A^{T}A$’nın özdeğerlerinin karekökleridir — ama bu yolla hesaplanmaz.

“…You would never form A transpose A.” — Strang, 28:43

$A^{T}A$ kurmak kondisyon sayısını kareler (Ders 6): küçük tekil değerlerin bilgisi yuvarlama hatasında kaybolur. İki “asla yapma”: (1) $A^{T}A$ kurma; (2) özdeğerleri determinant denkleminden ($\det(A - \lambda I) = 0$) bulma — hem çok yavaş hem umutsuzca kötü-koşullu ($n^2$ bilgi $n$ katsayıya sıkışır). Bunun yerine SVD doğrudan $A$ üzerinde çalışır.

Kondisyon sayısının $A^{T}A$ kurmakla nasıl karelendiğini Şekil 13.6 gösteriyor: $\kappa(A^{T}A) = \kappa(A)^2$ eğrisi $\kappa(A)$’nın çok üstüne fırlar, küçük tekil değerleri yutar.

Kod

kvals = [2., 4., 8., 16., 32., 64.]
kA = []; kAtA = []
for k in kvals:
    M = np.diag([k, 1.])
    a, b = ata_condition(M)
    kA.append(a); kAtA.append(b)
kA = np.array(kA); kAtA = np.array(kAtA)

fig, ax = plt.subplots(figsize=(6.2, 4.2))
apply_style(ax)
ax.loglog(kA, kAtA, color=COL_PRIMARY, marker="o", ms=5, label=r"$\kappa(A^T A)$")
ax.loglog(kA, kA**2, color=COL_VEC3, ls=":", label=r"$\kappa(A)^2$")
ax.loglog(kA, kA, color=COL_STEEL_300, ls="--", label=r"$\kappa(A)$ (y=x)")
ax.set_xlabel(r"$\kappa(A)$")
ax.set_ylabel("kondisyon")
ax.legend()
ax.set_title(r"$A^T A$ kondisyonu KARELER: küçük tekil değerler kaybolur"
             "\n"
             r"$\rightarrow$ SVD $A^T A$ kurmadan çalışır",
             color=COL_TEXT, fontsize=11, fontweight="bold")

plt.show()

Şekil 13.6: AᵀA kondisyonu KARELER: κ(AᵀA) = κ(A)² (navy noktalar turuncu κ(A)² eğrisiyle çakışır), oysa κ(A) (steel kesikli, y=x) yarı eğimde kalır. Küçük tekil değerler AᵀA’da kaybolur — bu yüzden SVD, AᵀA’yı kurmadan A üzerinden bidiagonal yolla çalışır.

Builder Notu — AᵀA’yı Asla Kurma

“AᵀA kurma, determinant kullanma” — iki yaygın hatayı yasaklar. np.linalg.svd doğrudan $A$’yı bidiagonalleştirir ($A^{T}A$’sız); en küçük tekil değerlerin doğruluğunu korur. Ters problemler, düşük-rank yaklaşım ve PCA bu kararlılığa bağlıdır.

13.11 10. Değişmezlik: Benzerlik vs İki-Yönlü Ortogonal

Özdeğer ve tekil değer için “neyi serbestçe değiştirebilirim” soruları farklı cevap verir. Özdeğer, benzerlik altında değişmez (her iki yan aynı matris ve tersi):

\[Q^{-1} A Q \;\Rightarrow\; \text{same eigenvalues}\]

Tekil değer ise iki ayrı ortogonal matris altında değişmez (SVD’de $A = U \Sigma V^{T}$; her iki yana farklı ortogonal çarpabilirim):

\[Q_1 A Q_2 \;\Rightarrow\; \text{same singular values}\]

Çünkü $Q_1 U$ ve $V^{T}Q_2$ yine ortogonaldir, ortadaki $\Sigma$ değişmez. Eigenvalue’da tek bir $Q$ ile sınırlıyken (tridiagonal’a iner), singular value’da iki serbestlik var — daha çok sadeleştirme.

İki ortogonal serbestliğin neye yol açtığını ve $B^{T}B$’nin tridiagonal çıkışını Şekil 13.7 gösteriyor: $Q_1 A Q_2$ tekil değeri koruduğundan $A$ bidiagonal’e iner, $B^{T}B$ ise eigenvalue dünyasının tridiagonal’ıdır.

Kod

B = make_bidiagonal([3., 4., 2.5], [1.2, 0.9])
BtB = B.T @ B

fig, axs = plt.subplots(1, 2, figsize=(7, 3.6))
spy_structure(axs[0], B, "A -> bidiagonal (SVD ön-işleme)")
spy_structure(axs[1], BtB, "B^T B = tridiagonal (özdeğer dünyası)")
fig.suptitle("Değişmezlik: Q1 A Q2 tekil değeri korur -> A bidiagonal'e iner; B^T B tridiagonal (A^T A kurmadan)", fontsize=9)
fig.tight_layout()
plt.show()

Şekil 13.7: Değişmezlik ve bidiagonal indirgeme: ortogonal $Q_1 A Q_2$ tekil değerleri korur, böylece $A$ üst-bidiagonal forma iner (SVD ön-işleme). $B^{\mathsf T}B$ ise tridiagonaldir — özdeğer dünyasına $A^{\mathsf T}A$’yı hiç kurmadan geçilir.

Builder Notu — Hangi Dönüşüm Neyi Korur

“Hangi dönüşüm neyi korur” ayrımı temeldir: benzerlik (taban değişimi) özdeğeri, iki-yönlü ortogonal tekil değeri korur. Bu, PCA’nın (kovaryans benzerliği) ve SVD-tabanlı sıkıştırmanın (ortogonal değişmezlik) neden taban seçiminden bağımsız olduğunu açıklar.

13.12 11. Bidiagonal Form (SVD İçin)

İki ortogonal serbestlik sayesinde SVD ön-işlemesi tridiagonal’dan daha ileri gider: bidiagonal form (ana köşegen + bir üst köşegen, gerisi sıfır).

“…reduce it even further from tridiagonal to bidiagonal.” — Strang, 38:11

Algoritma yine iki aşamalı: (1) A’yı iki-yönlü ortogonal ile bidiagonal’e indir ($\sigma$’lar korunur), (2) QR-tipi yöntemle $\sigma$’ları bul. Bidiagonal $A$ için $A^{T}A$ tridiagonaldir — eigenvalue dünyasıyla tam örtüşür. Böylece SVD, $A^{T}A$’yı hiç açıkça kurmadan hesaplanır.

Builder Notu — Bidiagonal’e İn

Bidiagonalleştirme + örtük QR, np.linalg.svd’nin (LAPACK gesdd/gesvd) yaptığıdır: $A^{T}A$’sız, sayısal kararlı SVD. Düşük-rank yaklaşım, PCA, pseudoinverse ve gürültü gidermenin güvenilir temeli.

13.13 Bu Dersin Özeti

QR iterasyonu — $A = QR \to A_1 = RQ \to$ tekrarla; özdeğerler köşegende belirir.
Benzerlik — $A_1 = Q^{-1}AQ$; özdeğerler korunur.
Köşegen-altı söner — kübik yakınsama; köşegen → özdeğerler.
Shift — $A - sI$ ile hızlandır; benzerlik korunur, $\lambda \to \lambda - s$.
Abel sınırı — 5. derece+ kapalı formülü yok; iterasyon zorunlu ($\varepsilon$-yakın).
Hessenberg — bir alt köşegen + sıfırlar; ön-işleme QR’ı hızlandırır.
Simetrik → tridiagonal — ~2n sayı; $O(n)$ adım, çok hızlı.
eig(A) — Hessenberg + shift’li QR; LAPACK.
AᵀA ve determinant’tan KAÇIN — kondisyon karelenir / kötü-koşullu.
Değişmezlik — $Q^{-1}AQ$ özdeğeri, $Q_1 A Q_2$ tekil değeri korur; SVD → bidiagonal.

Tek Bir Cümle

Özdeğer/tekil değer hesabının motoru QR iterasyonudur: $A = QR \to RQ$ döngüsü her adımda $Q^{-1}AQ$ benzerliğiyle özdeğerleri korur ve köşegen-altını söndürür; Hessenberg/tridiagonal/bidiagonal ön-işleme ve shift bunu pratik kılar — ama Abel yüzünden hep iteratif ($\varepsilon$-yakın), asla kesin.

13.14 Kontrol Soruları

Soru 1: QR iterasyonunda A₁ = RQ’nun A₀ = QR ile aynı özdeğerlere sahip olduğunu göster.

Cevap: $A_0 = QR$ olduğundan $R = Q^{-1}A_0$. Yerine koy: \[A_1 = RQ = Q^{-1}A_0 Q\] Bu bir benzerlik dönüşümü ($M = Q$ ile $M^{-1}A_0 M$). Benzer matrisler aynı özdeğerlere sahiptir (Ders 4). $Q$ ortogonal olduğundan $Q^{-1} = Q^{T}$, hesap kararlı. Demek ki tüm $A_0, A_1, A_2, \ldots$ aynı özdeğerlere sahiptir; köşegende beliren değerler gerçek özdeğerlerdir.

Soru 2: A − sI kaydırması özdeğerleri ve özvektörleri nasıl etkiler? Neden yakınsamayı hızlandırır?

Cevap: $A_0 v = \lambda v$ ise $(A_0 - sI)v = (\lambda - s)v$: özvektörler aynı, özdeğerler $s$ kadar kayar ($\lambda \to \lambda - s$). Eğer $s$ bir özdeğere (örneğin en küçüğüne) yakınsa, o özdeğer 0’a yaklaşır ve QR adımında köşegen-altı o satırda çok hızlı söner. İyi shift seçimi kübik yakınsamayı daha da hızlandırır. Kaydırma geri eklenince ($A_1 = RQ + sI$) benzerlik korunur.

Soru 3: Neden A’yı basit adımlarla tam üst üçgensel (özdeğerler köşegende) yapamayız, sadece Hessenberg’e indirebiliriz?

Cevap: Tam üçgensel yapabilseydik özdeğerleri köşegende kesin okurduk — sonlu adımda. Ama özdeğerler $n.$ dereceden bir denklemin kökleridir ve Abel kanıtladı: 5. derece+ için kapalı formül yoktur. Sonlu kesin adımlarla çözmek bu teoremi çiğnerdi. Bu yüzden en fazla Hessenberg’e (bir alt köşegen kalır) inebiliriz; gerisi iteratif QR ile $\varepsilon$-yakın bulunur.

Soru 4: Tekil değerleri bulmak için neden AᵀA’yı açıkça kurmazsın?

Cevap: $\sigma = \sqrt{\lambda_i(A^{T}A)}$ (yani $\sigma$, $A^{T}A$’nın bir özdeğerinin kareköküdür) matematiksel olarak doğru ama $A^{T}A$ kurmak kondisyon sayısını kareler ($\kappa \to \kappa^2$). Küçük tekil değerlerin bilgisi yuvarlama hatasında kaybolur (örneğin $\sigma = 10^{-4}$ ise $\sigma^2 = 10^{-8}$ makine epsilon’una gömülür). Bunun yerine SVD doğrudan $A$’yı bidiagonalleştirir ($A^{T}A$’sız) ve en küçük $\sigma$’ların doğruluğunu korur. Ters problemler ve düşük-rank yaklaşımda bu kritiktir.

13.15 Egzersizler

Cevapsız problemler. Çöz, sonra numpy ile kontrol et.

Egzersiz 1. $A = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}$ için bir QR iterasyon adımı yap: $A = QR$ bul, sonra $A_1 = RQ$ hesapla. $A_1$’in köşegeninin özdeğerlere (3, 1) yaklaştığını gözlemle.

Egzersiz 2. $A = \begin{pmatrix} 5 & 1 \\ 0 & 2 \end{pmatrix}$ için $s = 2$ shift uygula: $(A - 2I) = QR$, $A_1 = RQ + 2I$. $A_1$’in özdeğerlerinin hâlâ 5 ve 2 olduğunu doğrula.

Egzersiz 3. Aşağıdaki simetrik matris zaten tridiagonal mi? QR iterasyonunda tridiagonal kalır mı? Kaç bağımsız sayı içerir ($n = 4$)? \[A = \begin{pmatrix} 2 & 1 & 0 & 0 \\ 1 & 2 & 1 & 0 \\ 0 & 1 & 2 & 1 \\ 0 & 0 & 1 & 2 \end{pmatrix}\]

Egzersiz 4. Python ile QR iterasyonunu elle yap:

import numpy as np

A = np.array([[2.0, 1.0], [1.0, 2.0]])
for k in range(5):
    Q, R = np.linalg.qr(A)
    A = R @ Q                      # QR iterasyon adımı
    print(f"adım {k+1}, köşegen:", np.diag(A))   # 3, 1'e yakınsar
print("eig(A0):", np.linalg.eigvalsh([[2.0, 1.0], [1.0, 2.0]]))

Egzersiz 5. (Ders 13 habercisi.) Ders 13 rastlantısal matris çarpımına geçer: dev $AB$ çarpımını tüm kolonlar yerine örneklenmiş kolon/satır çiftleriyle yaklaşık hesaplamak. $AB = \sum$ ($A$’nın kolonu)($B$’nin satırı) ifadesini hatırla (Ders 1); neden bazı terimleri olasılıkla örneklemek tüm toplamı yaklaşık verebilir? Bir terim seçme olasılığını ne ile orantılı alırdın?

13.16 Sonraki Ders İçin Hazırlık

Ders 13: Rastlantısal Matris Çarpımı

Ders 12’de kesin özdeğer/SVD’yi gördük. Ders 13 dev matrisler için olasılığa döner: örnekleme ile yaklaşık hesap.

Rastlantısal matris çarpımı: kolon/satır çiftlerini örnekle
Norm-kare örnekleme olasılığı (önemli terimleri seç)
Beklenen değer ve varyans (Stat 110 köprüsü)
Randomized SVD’ye giriş; büyük-ölçek ML

Ders 13 Öncesi Yapılacak

Bu dersin egzersizlerini çöz, özellikle Egzersiz 5’i (örnekleme sezgisi).
Python’da bir $AB$ çarpımını az sayıda kolon/satır çiftiyle yaklaşık hesaplamayı dene; hatayı gözlemle.
Ana cümleyi tekrar oku: “QR iterasyonu özdeğerleri benzerlikle köşegene taşır; Abel yüzünden hep iteratif.”

13.17 Anahtar Kavramlar (Cheat Sheet)

Kavram	Tanım	Strang’de
QR iterasyonu	$A = QR \to A_1 = RQ \to$ tekrarla	2m12
Benzerlik	$A_1 = Q^{-1}AQ$; özdeğerler korunur	4m29
Kübik yakınsama	Köşegen-dışı her adımda küpü alınır	9m29
Özdeğerler köşegende	İterasyon limiti; köşegen → $\lambda$	17m36
Shift	$A - sI$; $\lambda \to \lambda - s$, hızlandırır	10m27
Abel sınırı	5. derece+ kapalı formül yok; iterasyon zorunlu	21m36
Hessenberg	Bir alt köşegen + sıfırlar; ön-işleme	22m56
Simetrik → tridiagonal	~2n sayı; $O(n)$ adım, çok hızlı	27m09
AᵀA’dan kaçın	Kondisyon karelenir; SVD doğrudan $A$’da	28m43
Bidiagonal (SVD)	İki-yönlü ortogonal; $\sigma$’lar için ön-işleme	38m11

13.18 ML Bağlantıları Özeti

QR iterasyonu → eig/eigh/svd’nin motoru (LAPACK); PCA, spektral yöntemler.
Benzerlik ($Q^{-1}AQ$) → özdeğer korur; taban değişiminin ML’deki güvencesi.
Shift → ters iterasyon, önkoşullama; bilinen tahmine hızlı yakınsama.
Simetrik → tridiagonal → kovaryans/Gram/Hessian özdeğerlerini hızlı hesaplama.
AᵀA’dan kaçın → SVD’nin sayısal kararlılığı; küçük $\sigma$’ların korunması.
Abel sınırı → özdeğer/SVD hep yaklaşık ($\varepsilon$-yakın); ML’de “yeterince kesin”.
LAPACK çağır → elle yazma; onyıllarca kararlılık çalışmasının ürünü.

Eğer bu dersten tek bir şey alıp gidersen

eig ve svd’nin motoru QR iterasyonudur: $A = QR \to RQ$ döngüsü her adımda $Q^{-1}AQ$ benzerliğiyle özdeğerleri korur ve köşegen-altını kübik hızla söndürür. Hessenberg (simetrikte tridiagonal) ön-işleme ve shift bunu pratik kılar; SVD ise $A^{T}A$’yı hiç kurmadan bidiagonal forma indirger. Abel yüzünden hep iteratif ($\varepsilon$-yakın) — ama LAPACK bunu milisaniyelerde, güvenilir biçimde yapar.

--- title: "Özdeğer ve Tekil Değerleri Hesaplamak" subtitle: "QR iterasyonu, shift, Hessenberg ve bidiagonal" --- ::: {.callout-note title="Bölüm bilgisi"} **Video:** [Computing Eigenvalues and Singular Values](https://www.youtube.com/watch?v=d32WV1rKoVk) · **OCW:** MIT 18.065 Lecture 12 · **Okuma süresi:** ~36 dk · **Eğitmen:** Gilbert Strang · **Önkoşul:** Ders 11 (QR faktorizasyonu, Gram-Schmidt ve ortonormal tabanlar). ::: ```{python} #| echo: false """ _engine12.py — MIT 18.065 Ders 12 (Özdeğer/Tekil Değer Hesaplama) self-contained motor + viz. Setup hücresi = cat. Figür testi `from _engine12 import *`. matplotlib.use("Agg") burada YOK. """ import numpy as np import matplotlib.pyplot as plt from matplotlib.colors import LinearSegmentedColormap COL_PRIMARY = "#1f4e79"; COL_ACCENT = "#2e75b6"; COL_TEXT = "#13243a" COL_BG = "#eaf1f8"; COL_STEEL_300 = "#aac4dd"; COL_SKY_400 = "#6fa8dc" COL_WHITE = "#ffffff" COL_VEC1 = "#1f4e79"; COL_VEC2 = "#2e75b6"; COL_VEC3 = "#e67e22" COL_TEAL = "#17a2b8"; COL_PURPLE = "#6f42c1" NAVY_CMAP = LinearSegmentedColormap.from_list("strang_navy", ["#ffffff", "#cfe0f0", "#6fa8dc", "#2e75b6", "#1f4e79"]) def apply_style(ax): ax.set_facecolor(COL_WHITE); ax.grid(True, alpha=0.25, color=COL_STEEL_300, linewidth=0.8) for sp in ax.spines.values(): sp.set_color(COL_STEEL_300) ax.tick_params(colors=COL_TEXT); ax.title.set_color(COL_TEXT) ax.xaxis.label.set_color(COL_TEXT); ax.yaxis.label.set_color(COL_TEXT) return ax def style_square_axes(ax, lim, title=None): apply_style(ax); ax.set_xlim(-lim, lim); ax.set_ylim(-lim, lim); ax.set_aspect("equal") ax.axhline(0, color=COL_STEEL_300, lw=0.8, zorder=0); ax.axvline(0, color=COL_STEEL_300, lw=0.8, zorder=0) if title: ax.set_title(title, color=COL_TEXT, fontsize=11, fontweight="bold") return ax def heatmap(ax, M, title=None, cmap=None, annotate=True, fmt="{:.2g}", vmin=None, vmax=None, fontsize=11, text_thresh=None): M = np.asarray(M, dtype=float) if cmap is None: cmap = NAVY_CMAP if vmin is None: vmin = float(np.min(M)) if vmax is None: vmax = float(np.max(M)) ax.imshow(M, cmap=cmap, vmin=vmin, vmax=vmax, aspect="equal"); nr, nc = M.shape if text_thresh is None: text_thresh = vmin + 0.62*(vmax-vmin) if annotate and nr*nc <= 64: for i in range(nr): for j in range(nc): v = M[i, j] ax.text(j, i, fmt.format(v), ha="center", va="center", color=COL_WHITE if v >= text_thresh else COL_TEXT, fontsize=fontsize, fontweight="bold") ax.set_xticks(range(nc)); ax.set_yticks(range(nr)); ax.set_xticklabels([]); ax.set_yticklabels([]); ax.tick_params(length=0) for sp in ax.spines.values(): sp.set_color(COL_STEEL_300) if title: ax.set_title(title, color=COL_TEXT, fontsize=12, fontweight="bold") def spy_structure(ax, M, title=None, tol=1e-10): """Sıfır-olmayan yapısını göster (navy=dolu, beyaz=sıfır).""" M = np.asarray(M, dtype=float); mask = (np.abs(M) > tol).astype(float) ax.imshow(mask, cmap=LinearSegmentedColormap.from_list("z", ["#ffffff", COL_PRIMARY]), vmin=0, vmax=1, aspect="equal") nr, nc = M.shape for i in range(nr): for j in range(nc): if abs(M[i, j]) > tol: ax.text(j, i, "•", ha="center", va="center", color=COL_WHITE, fontsize=14, fontweight="bold") ax.set_xticks(range(nc)); ax.set_yticks(range(nr)); ax.set_xticklabels([]); ax.set_yticklabels([]); ax.tick_params(length=0) for sp in ax.spines.values(): sp.set_color(COL_STEEL_300) if title: ax.set_title(title, color=COL_TEXT, fontsize=11, fontweight="bold") # ---- Ders 12 motoru: özdeğer/tekil değer hesabı ---- def qr_iteration(A, steps): """A_0=QR -> A_1=RQ -> ... saf QR iterasyonu. (diag_history, subdiag_history) döner.""" A = np.asarray(A, dtype=float).copy() diag_hist = [np.diag(A).copy()] sub_hist = [float(abs(A[-1, -2])) if A.shape[0] > 1 else 0.0] # alt-köşegen son girdi for _ in range(steps): Q, R = np.linalg.qr(A) A = R @ Q diag_hist.append(np.diag(A).copy()) sub_hist.append(float(abs(A[-1, -2])) if A.shape[0] > 1 else 0.0) return A, np.array(diag_hist), np.array(sub_hist) def _wilkinson_shift(A): """Trailing 2x2 bloğun (simetrik) A[-1,-1]'e en yakın özdeğeri — Wilkinson shift.""" a = A[-2, -2]; b = A[-1, -2]; c = A[-1, -1] d = (a - c) / 2.0 if d == 0 and b == 0: return c denom = abs(d) + np.sqrt(d*d + b*b) sign = 1.0 if d >= 0 else -1.0 return c - sign * (b*b) / denom def qr_iteration_shift(A, steps): """Wilkinson shift'li QR iterasyonu — son-eleman shift patolojisini çözer.""" A = np.asarray(A, dtype=float).copy(); n = A.shape[0] sub_hist = [float(abs(A[-1, -2])) if n > 1 else 0.0] for _ in range(steps): s = _wilkinson_shift(A) if n > 1 else A[-1, -1] Q, R = np.linalg.qr(A - s*np.eye(n)) A = R @ Q + s*np.eye(n) sub_hist.append(float(abs(A[-1, -2])) if n > 1 else 0.0) return A, np.array(sub_hist) def hessenberg_form(A): """A'yı üst-Hessenberg forma indir (benzerlik, Householder). Simetrikte tridiagonal.""" A = np.asarray(A, dtype=float).copy(); n = A.shape[0]; H = A.copy() for k in range(n - 2): x = H[k+1:, k].copy() e = np.zeros_like(x); e[0] = np.linalg.norm(x) * (1.0 if x[0] >= 0 else -1.0) v = x + e nv = np.linalg.norm(v) if nv < 1e-300: continue v = v / nv H[k+1:, :] = H[k+1:, :] - 2.0 * np.outer(v, v @ H[k+1:, :]) H[:, k+1:] = H[:, k+1:] - 2.0 * np.outer(H[:, k+1:] @ v, v) H[np.abs(H) < 1e-12] = 0.0 return H def condition_number(A): s = np.linalg.svd(np.asarray(A, dtype=float), compute_uv=False) return float(s[0] / s[-1]) if s[-1] > 1e-300 else float("inf") def ata_condition(A): """κ(A) ve κ(AᵀA): AᵀA kondisyonu kareler (κ(AᵀA) = κ(A)²).""" A = np.asarray(A, dtype=float) return condition_number(A), condition_number(A.T @ A) def make_bidiagonal(diag, super_diag): """Üst-bidiagonal matris (ana köşegen + bir üst köşegen).""" n = len(diag); B = np.diag(np.asarray(diag, dtype=float)) for i in range(n-1): B[i, i+1] = super_diag[i] return B def cubic_decay_demo(theta0=0.9, steps=6): """Köşegen-dışı girdinin kübik sönmesi: θ -> θ³ -> θ⁹ -> ... (sin tabanlı kavramsal).""" vals = []; t = theta0 for _ in range(steps): vals.append(abs(np.sin(t))); t = t**3 return np.array(vals) ``` ## Bu Derste Ne Var? {#sec-bu-derste-d12} `eig` ve `svd` perde arkasında ne yapar? Ders 11'in QR'ı beklenmedik bir yere uygulanır: **özdeğer hesabı**. Strang QR iterasyonunu, shift'i ve Hessenberg/tridiagonal ön-işlemeyi anlatır. Üç temel fikir: 1. **QR iterasyonu** — $A = QR \to A_1 = RQ \to$ tekrarla; $A_1 = Q^{-1}AQ$ benzerdir (özdeğer korunur), köşegen-altı söner, özdeğerler köşegende belirir. 2. **Ön-işleme** — önce Hessenberg (simetrikte tridiagonal) forma indir; QR'ı çok hızlandırır. İteratif olmak zorunda (Abel: 5. derece denklemin formülü çözümü yok). 3. **Tekil değerler** — $A^{T}A$ KURMA (kondisyon karelenir), determinant KULLANMA; iki-yönlü ortogonal ($Q_1 A Q_2$) $\sigma$'ları korur → bidiagonal forma indir. Bütün bu fikirlerin tek bir merkezden nasıl dallandığını @fig-kavram-haritasi-l12 özetliyor: özdeğer/tekil değer hesabının kalbinde QR iterasyonu, çevresinde benzerlik, shift, Abel sınırı ve ön-işleme vardır. ```{mermaid} %%| label: fig-kavram-haritasi-l12 %%| fig-cap: "Ders 12 kavram haritası: özdeğer / tekil değer hesabı merkezinden ana fikirlere dallar — QR iterasyonu (A = QR → A₁ = RQ → tekrarla), benzerlik (A₁ = Q⁻¹AQ özdeğeri korur), köşegen-altının kübik sönmesi (özdeğerler köşegende), shift (A − sI yakınsamayı hızlandırır), Abel sınırı (5. derece+ kapalı formül yok → iteratif), ön-işleme (Hessenberg, simetrikte tridiagonal) ve SVD (AᵀA KURMA → bidiagonal); ayrıca her şeyi çalıştıran LAPACK eig/svd düğümü." %%| echo: false flowchart TD M["Özdeğer / tekil değer hesabı"] --> QR["QR iterasyonu: A = QR → A₁ = RQ → tekrarla"] M --> SIM["benzerlik A₁ = Q⁻¹AQ → özdeğer korunur"] M --> DEC["köşegen-altı söner (kübik) → özdeğerler köşegende"] M --> SHIFT["shift A − sI → hızlandırır"] M --> ABEL["Abel: 5. derece+ formül yok → iteratif"] M --> PRE["ön-işleme: Hessenberg / simetrik → tridiagonal"] M --> SVD["SVD: AᵀA KURMA → bidiagonal"] LAP["LAPACK eig / svd"] style M fill:#1f4e79,color:#fff,stroke:#13243a,stroke-width:2px style LAP fill:#1f4e79,color:#fff,stroke:#13243a,stroke-width:2px style QR fill:#2e75b6,color:#fff,stroke:#13243a,stroke-width:2px style SIM fill:#2e75b6,color:#fff,stroke:#13243a,stroke-width:2px style DEC fill:#2e75b6,color:#fff,stroke:#13243a,stroke-width:2px style SHIFT fill:#6fa8dc,color:#13243a,stroke:#1f4e79,stroke-width:2px style ABEL fill:#6fa8dc,color:#13243a,stroke:#1f4e79,stroke-width:2px style PRE fill:#6fa8dc,color:#13243a,stroke:#1f4e79,stroke-width:2px style SVD fill:#6fa8dc,color:#13243a,stroke:#1f4e79,stroke-width:2px ``` > *"It's called the QR method because you start by factoring your matrix into QR."* — Strang, 2:12 ::: {.callout-tip title="Builder Notu — eig'in Motoru"} - **QR iterasyonu = eig'in motoru:** `numpy.linalg.eig`/`eigh` arka planda Hessenberg/tridiagonal + shift'li QR (LAPACK) çalıştırır; doğrudan çağırırsın, kütüphane optimize eder. - **Benzerlik = özdeğer korur** — her QR adımı $A_1 = Q^{-1}AQ$; spektral yöntemlerin (PCA, GCN) hesap temeli. - **AᵀA'dan kaçın** — tekil değer için $A^{T}A$ kurmak kondisyonu kareler (Ders 6); SVD doğrudan $A$ üzerinde bidiagonalleştirme + QR ile bulunur. - **Abel sınırı** — özdeğer/tekil değer kesin formülü yok (5. derece+); sadece iteratif yaklaşım, $\varepsilon$-yakın cevap. Tek cümle: özdeğer/tekil değer hesabının motoru QR iterasyonudur — benzerlik dönüşümleriyle köşegen-altını söndürür; Hessenberg/tridiagonal/bidiagonal ön-işleme ve shift onu pratik kılar. ::: ## 1. QR Yöntemi: A = QR → RQ {#sec-qr-yontemi} Özdeğerleri hesaplamak için QR faktorizasyonu (Ders 11) beklenmedik biçimde anahtar olur. Matrisi QR'a ayır, sonra çarpanları **ters sırada** çarp — yeni matris bu: $$A_0 = Q_0 R_0, \qquad A_1 = R_0 Q_0$$ > *"It's called the QR method because you start by factoring your matrix into QR."* — Strang, 2:12 Sonra $A_1$'i tekrar QR'a ayır, ters sırada çarp, $A_2$ üret — tekrar tekrar. Umut: özdeğerler değişmesin ve matris köşegene yakınsasın. QR iterasyonunun bir simetrik matriste köşegeni adım adım özdeğerlere nasıl taşıdığını @fig-qr-iterasyon gösteriyor: köşegen-altı sönerken köşegen değerleri kesik çizgilerle işaretli gerçek özdeğerlere oturuyor. ```{python} #| label: fig-qr-iterasyon #| fig-cap: "QR iterasyonu ($A=QR \\to A_1=RQ$ tekrarla): bir simetrik $A$'nın köşegen girdileri adım adım özdeğerlere (kesik çizgiler) yakınsar — köşegen-altı sıfıra sönerken köşegende özdeğerler beliriyor." #| fig-width: 6.4 #| fig-height: 4.4 #| code-fold: true A = np.array([[4., 1., 0.], [1., 3., 1.], [0., 1., 2.]]) Af, dh, sh = qr_iteration(A, 25) fig, ax = plt.subplots(figsize=(6.4, 4.4)) apply_style(ax) renkler = [COL_PRIMARY, COL_ACCENT, COL_TEAL] for i in range(3): ax.plot(range(len(dh)), dh[:, i], color=renkler[i], marker="o", ms=3, label="köşegen " + str(i + 1)) ev = np.sort(np.linalg.eigvalsh(A))[::-1] for e in ev: ax.axhline(e, ls=":", color=COL_STEEL_300, lw=1) ax.set_xlabel("QR iterasyon adımı") ax.set_ylabel("köşegen değerleri") ax.set_title("QR iterasyonu: köşegen değerleri özdeğerlere yakınsar (A=QR → RQ tekrarla)", color=COL_TEXT, fontsize=10, fontweight="bold") ax.legend() plt.show() ``` ::: {.callout-tip title="Builder Notu — Ters Sırada Çarp"} QR iterasyonu, `numpy.linalg.eig`/`eigh`'in (LAPACK) motorudur. "A = QR sonra RQ" döngüsü, 1960'larda özdeğer hesabını kökten değiştirdi — önceki tüm yöntemleri silip süpürdü. Sen `eig` çağırırsın, arka planda bu döner. ::: ## 2. Neden Özdeğerler Korunur (Benzerlik) {#sec-benzerlik} $A_1$'in özdeğerleri $A_0$'la aynı mı? İki matrisin aynı özdeğere sahip olduğunu göstermenin en iyi yolu: **benzer** olduklarını göstermek (Ders 4). > *"They're similar, that's right."* — Strang, 4:29 $A_1 = R_0 Q_0$. $Q_0 R_0 = A_0$ olduğundan $R_0 = Q_0^{-1}A_0$; yerine koy: $$A_1 = R_0 Q_0 = Q_0^{-1}(Q_0 R_0)Q_0 = Q_0^{-1} A_0 Q_0$$ Bu tam bir benzerlik dönüşümüdür → $A_1$ ve $A_0$ aynı özdeğerlere sahiptir. Her QR adımı özdeğerleri korur; yalnızca temsili değiştirir. ::: {.callout-tip title="Builder Notu — Benzerlik Güvencesi"} "Her adım $Q^{-1}AQ$ benzerliği" güvencesi, iterasyonun özdeğerleri bozmadan matrisi sadeleştirmesini sağlar. Aynı benzerlik fikri (taban değişimi özdeğeri korur) PCA, spektral kümeleme ve ağ reparametrizasyonunun ortak ilkesidir. ::: ## 3. Köşegen-altı Söner → Özdeğerler {#sec-kosegen-alti} Mucize: çoğu matriste QR adımları köşegen-altı girdileri giderek küçültür. $A_0 \to A_1 \to A_2 \ldots$ köşegen-altı epsilonlara iner ve köşegende özdeğerler belirir. > *"...the eigenvalues pop up on the diagonal."* — Strang, 17:36 2×2 örnekte köşegen-dışı girdi her adımda **küpü** alınır ($\sin\theta \to \sin^3\theta \to \sin^9\theta \to \ldots$), yani çok hızlı 0'a gider: > *"...cubic convergence..."* — Strang, 9:29 Köşegen-altı küçük epsilonlar özdeğerleri pek değiştirmez (benzerlik korur), o yüzden köşegen değerleri özdeğerlere yakınsar — en alttaki önce. Köşegen-altı girdinin log eksende ne kadar dik düştüğünü @fig-kubik-yakinsama gösteriyor: birkaç adımda sıfıra çöken bu eğri, kübik yakınsamanın imzasıdır. ```{python} #| label: fig-kubik-yakinsama #| fig-cap: "Köşegen-altı girdi her QR adımında hızla söner (→ 0): A=QR → RQ tekrarlandıkça özdeğerler köşegende beliriyor. Log eksende dik düşüş, kübik yakınsamanın imzasıdır." #| fig-width: 7 #| fig-height: 4.2 #| code-fold: true A = np.array([[4., 1., 0.], [1., 3., 1.], [0., 1., 2.]]) _, _, sh = qr_iteration(A, 12) fig, ax = plt.subplots(figsize=(7, 4.2)) apply_style(ax) ax.semilogy(range(len(sh)), np.maximum(sh, 1e-16), color=COL_PRIMARY, marker="o", ms=5, label="alt-köşegen |girdi|") ax.set_xlabel("QR iterasyon adımı") ax.set_ylabel("alt-köşegen |girdi| (log)") ax.set_title("Köşegen-altı girdi her adımda hızla söner (→ 0): özdeğerler köşegende beliriyor", fontsize=10, fontweight="bold") ax.legend() plt.show() ``` ::: {.callout-tip title="Builder Notu — Kübik Hız"} Kübik yakınsama, QR iterasyonunu pratik kılan şeydir: birkaç adımda makine hassasiyetine ulaşır. Bu hız, `eig`'in milisaniyelerde çalışmasının sebebi; büyük matrislerde ise yalnız baskın özdeğerleri arayan yöntemler (Lanczos, Ders 11) devreye girer. ::: ## 4. Shift (Kaydırma) ile Hızlandırma {#sec-shift} Numerik analistler daha hızlısını istedi ve **shift** (kaydırma) bulundu. Birim matrisin bir katını çıkar, QR yap, ters sırada çarp, kaydırmayı geri ekle: $$A_0 - sI = QR, \qquad A_1 = RQ + sI$$ > *"...the idea of introducing a shift..."* — Strang, 10:27 $sI$ ile kaydırmak özvektörleri **değiştirmez**, özdeğerleri $s$ kadar **kaydırır** ($\lambda \to \lambda - s$). İyi seçilmiş bir shift yakınsamayı çok hızlandırır. Ve benzerlik korunur: $R(Q)$ hesabında $R_0$ ile $R_0^{-1}$ sadeleşir, çıkarılan $sI$ ile eklenen $sI$ birbirini götürür → $A_1$ hâlâ $A_0$'a benzerdir. Shift'in yakınsamayı ne kadar dramatik hızlandırdığını @fig-shift gösteriyor: saf QR sekiz adımda ancak ilerlerken Wilkinson shift'li QR tek adımda makine hassasiyetine çöker. ```{python} #| label: fig-shift #| fig-cap: "Shift (A − sI) yakınsamayı uçurur. Aynı 2×2 simetrik A için alt-köşegen girdisinin büyüklüğü (log ölçek): turuncu kareler saf QR iterasyonu (shift yok) — her adımda yalnızca geometrik olarak küçülür ve 8 adımda hâlâ 10⁻³ düzeyinde. Navy daireler Wilkinson shift'li QR — tek adımda makine hassasiyetine (≈10⁻¹⁶) çöker. Shift, özdeğeri köşegene fırlatarak yakınsamayı dramatik biçimde hızlandırır." #| fig-width: 7 #| fig-height: 4.2 #| code-fold: true # Aynı simetrik A: saf QR vs Wilkinson shift'li QR (alt-köşegen sönmesi) Ash = np.array([[3., 1.], [1., 2.]]) _, _, sh_plain = qr_iteration(Ash, 8) # shift yok _, sh_shift = qr_iteration_shift(Ash, 8) # Wilkinson shift fig, ax = plt.subplots(figsize=(7, 4.2)) apply_style(ax) ax.semilogy(range(len(sh_plain)), np.maximum(sh_plain, 1e-16), color=COL_VEC3, marker="s", ms=5, label="shift yok") ax.semilogy(range(len(sh_shift)), np.maximum(sh_shift, 1e-16), color=COL_PRIMARY, marker="o", ms=5, label="Wilkinson shift") ax.set_xlabel("adım") ax.set_ylabel("alt-köşegen |girdi| (log)") ax.legend() ax.set_title("Shift (A-sI) yakınsamayı uçurur: Wilkinson shift birkaç adımda makine hassasiyeti", fontsize=10, fontweight="bold", color=COL_TEXT) plt.show() ``` ::: {.callout-tip title="Builder Notu — Akıllı Kaydırma"} Shift, QR iterasyonunu pratikte kullanılabilir kılan hızlandırmadır (özellikle son özdeğere yakın shift seçmek). Aynı "kaydır-çöz-geri kaydır" fikri ters iterasyon (inverse iteration) ve önkoşullamada da görülür; bilinen bir özdeğer tahminine yakınsamayı hızlandırır. ::: ## 5. Tam Çözüm İmkânsız (Abel) {#sec-abel} Neden tam çözüm yok, neden iterasyon? Eliminasyonda $Ax = b$'yi sonlu adımda tam çözeriz. Ama özdeğerler $n.$ dereceden bir denklemin kökleridir ve Abel bir asır önce kanıtladı: 5. derece ve üstü denklemin kökleri için **kapalı formül yoktur**. > *"5th degree, yeah."* — Strang, 21:36 Yani özdeğerleri (ve tekil değerleri) sonlu, kesin adımlarla bulmak matematiksel olarak imkânsızdır — yalnızca QR iterasyonuyla istediğimiz kadar ($\varepsilon$) yaklaşabiliriz. Özdeğer problemi, $Ax = b$'den bir zorluk seviyesi yukarıdadır. ::: {.callout-tip title="Builder Notu — Abel'in Duvarı"} Abel sınırı, neden `eig`'in "kesin" değil "$\varepsilon$-yakın" olduğunu açıklar: ~$n^3$ adımda makine hassasiyetine ulaşır ama prensipte sonsuz adım gerekir. Bu, sayısal lineer cebir ile cebirin temel ayrımı — ML'de özdeğer/SVD hep yaklaşık (ama pratikte yeterince kesin). ::: ## 6. Hessenberg Formu (Ön-İşleme) {#sec-hessenberg} İş nerede? QR faktorizasyonunda. Onu hızlandırmak için matrisi önce çok sıfırlı bir forma indir. Tam üçgensel yapamayız (özdeğerleri bulmuş olurduk, Abel yasak), ama köşegenin bir altına kadar sıfırlayabiliriz — **Hessenberg** formu. > *"Upper Hessenberg."* — Strang, 22:56 Hessenberg matris = üst üçgensel + bir alt köşegen, gerisi sıfır (≈yarı $n^2$ sıfır). Bu sıfırlar QR adımlarında sıfır kalır, böylece her QR çok daha ucuz. Tam yöntem: **(1)** A'yı benzerlikle Hessenberg'e indir, **(2)** shift'li QR uygula. Dolu bir simetrik matrisin ön-işlemeyle nasıl tridiagonal yapıya indiğini @fig-yapi-uclu gösteriyor: 16 dolu girdi yalnız ana köşegen + bir alt/üst köşegene (~2n sayı) iniyor. ```{python} #| label: fig-yapi-uclu #| fig-cap: "Ön-işleme: simetrik bir matris A, benzerlik dönüşümleriyle tridiagonal forma indirilir. Sol panelde dolu simetrik A'nın 16 girdisi, sağ panelde tridiagonal yapının yalnızca ana köşegen ile bir alt/üst köşegeni (~2n sayı) doludur. Özdeğerler korunur, sonraki QR adımları O(n) çok hızlı çalışır." #| fig-width: 7 #| fig-height: 3.6 #| code-fold: true S = np.array([[4., 1., 2., 0.5], [1., 3., 0.7, 1.], [2., 0.7, 5., 1.2], [0.5, 1., 1.2, 2.]]) fig, axs = plt.subplots(1, 2, figsize=(7, 3.6)) spy_structure(axs[0], S, "simetrik A (dolu)") spy_structure(axs[1], hessenberg_form(S), "tridiagonal (~2n sayı)") fig.suptitle("Ön-işleme: simetrik A → tridiagonal (benzerlik, özdeğer korunur); QR adımları O(n) çok hızlı", color=COL_TEXT, fontsize=10, fontweight="bold") plt.show() ``` ::: {.callout-tip title="Builder Notu — Yarı Yol Sıfır"} Hessenberg ön-işleme, `eig`'in iki aşamalı yapısının ilk yarısıdır (LAPACK). Benzerlik dönüşümüyle (Householder) yapıldığından özdeğerleri korur ve sonraki QR adımlarının maliyetini $O(n^2)$'den çok aşağı çeker — pratik özdeğer hesabının sırrı. ::: ## 7. Simetrik → Tridiagonal {#sec-tridiagonal} Matris simetrikse daha da iyi. QR adımları simetriyi korur ($A_0$ simetrik → $A_1$ simetrik). Simetrik + Hessenberg = **tridiagonal**: yalnız ana köşegen + bir üst + bir alt köşegen. > *"...tridiagonal matrix."* — Strang, 27:09 Tridiagonal matriste yalnızca ~2n sayı vardır (üst ve alt köşegen simetriden eşit). QR adımları tridiagonalliği korur, böylece her adım $O(n^2)$ yerine $O(n)$ — "bomba gibi" hızlı. Simetrik `eigh` bu yüzden çok hızlıdır. ::: {.callout-tip title="Builder Notu — İki Köşegen Yeter"} Simetrik → tridiagonal indirgeme, kovaryans/Gram/Hessian gibi ML matrislerinin özdeğerlerini hesaplamanın hızlı yoludur (`numpy.linalg.eigh`). PCA, kernel yöntemleri ve spektral kümeleme bu rutinin hızına dayanır. ::: ## 8. eig(A): Hessenberg + Shift'li QR {#sec-eig-d12} Tam algoritma iki adımdır: **(1)** A'yı Hessenberg (simetrikse tridiagonal) forma indir, **(2)** shift'li QR uygula. `eig(A)` perde arkasında bunu yapar — ama Matlab/NumPy kendi kodunu değil, profesyonel **LAPACK** rutinlerini çağırır. LAPACK, on yazarlı, onyıllarca emek verilmiş sayısal lineer cebir "İncili"dir; özdeğer kodları indirilebilir ve her ciddi sistem ona dayanır. Yani sen `eig`/`eigh`/`svd` çağırırsın, dünyanın en iyi sayısal analistlerinin kodu çalışır. ::: {.callout-tip title="Builder Notu — LAPACK'i Çağır"} "Kendin yazma, LAPACK çağır" — sayısal ML'nin altın kuralı. Özdeğer/SVD rutinleri (geev, syev, gesdd) onlarca yıllık kararlılık çalışmasının ürünü; elle QR yazmak hem yavaş hem riskli. NumPy/PyTorch/SciPy hepsi LAPACK'e köprüdür. ::: ## 9. Tekil Değerler: AᵀA ve Determinant'tan KAÇIN {#sec-ata-kacin-d12} Tekil değerler $A^{T}A$'nın özdeğerlerinin karekökleridir — ama bu yolla **hesaplanmaz**. > *"...You would never form A transpose A."* — Strang, 28:43 $A^{T}A$ kurmak kondisyon sayısını **kareler** (Ders 6): küçük tekil değerlerin bilgisi yuvarlama hatasında kaybolur. İki "asla yapma": (1) $A^{T}A$ kurma; (2) özdeğerleri determinant denkleminden ($\det(A - \lambda I) = 0$) bulma — hem çok yavaş hem umutsuzca kötü-koşullu ($n^2$ bilgi $n$ katsayıya sıkışır). Bunun yerine SVD doğrudan $A$ üzerinde çalışır. Kondisyon sayısının $A^{T}A$ kurmakla nasıl karelendiğini @fig-ata-squaring gösteriyor: $\kappa(A^{T}A) = \kappa(A)^2$ eğrisi $\kappa(A)$'nın çok üstüne fırlar, küçük tekil değerleri yutar. ```{python} #| label: fig-ata-squaring #| fig-cap: "AᵀA kondisyonu KARELER: κ(AᵀA) = κ(A)² (navy noktalar turuncu κ(A)² eğrisiyle çakışır), oysa κ(A) (steel kesikli, y=x) yarı eğimde kalır. Küçük tekil değerler AᵀA'da kaybolur — bu yüzden SVD, AᵀA'yı kurmadan A üzerinden bidiagonal yolla çalışır." #| fig-width: 6.2 #| fig-height: 4.2 #| code-fold: true kvals = [2., 4., 8., 16., 32., 64.] kA = []; kAtA = [] for k in kvals: M = np.diag([k, 1.]) a, b = ata_condition(M) kA.append(a); kAtA.append(b) kA = np.array(kA); kAtA = np.array(kAtA) fig, ax = plt.subplots(figsize=(6.2, 4.2)) apply_style(ax) ax.loglog(kA, kAtA, color=COL_PRIMARY, marker="o", ms=5, label=r"$\kappa(A^T A)$") ax.loglog(kA, kA**2, color=COL_VEC3, ls=":", label=r"$\kappa(A)^2$") ax.loglog(kA, kA, color=COL_STEEL_300, ls="--", label=r"$\kappa(A)$ (y=x)") ax.set_xlabel(r"$\kappa(A)$") ax.set_ylabel("kondisyon") ax.legend() ax.set_title(r"$A^T A$ kondisyonu KARELER: küçük tekil değerler kaybolur" "\n" r"$\rightarrow$ SVD $A^T A$ kurmadan çalışır", color=COL_TEXT, fontsize=11, fontweight="bold") plt.show() ``` ::: {.callout-tip title="Builder Notu — AᵀA'yı Asla Kurma"} "AᵀA kurma, determinant kullanma" — iki yaygın hatayı yasaklar. `np.linalg.svd` doğrudan $A$'yı bidiagonalleştirir ($A^{T}A$'sız); en küçük tekil değerlerin doğruluğunu korur. Ters problemler, düşük-rank yaklaşım ve PCA bu kararlılığa bağlıdır. ::: ## 10. Değişmezlik: Benzerlik vs İki-Yönlü Ortogonal {#sec-degismezlik} Özdeğer ve tekil değer için "neyi serbestçe değiştirebilirim" soruları farklı cevap verir. Özdeğer, **benzerlik** altında değişmez (her iki yan aynı matris ve tersi): $$Q^{-1} A Q \;\Rightarrow\; \text{same eigenvalues}$$ Tekil değer ise **iki ayrı** ortogonal matris altında değişmez (SVD'de $A = U \Sigma V^{T}$; her iki yana farklı ortogonal çarpabilirim): $$Q_1 A Q_2 \;\Rightarrow\; \text{same singular values}$$ Çünkü $Q_1 U$ ve $V^{T}Q_2$ yine ortogonaldir, ortadaki $\Sigma$ değişmez. Eigenvalue'da tek bir $Q$ ile sınırlıyken (tridiagonal'a iner), singular value'da iki serbestlik var — daha çok sadeleştirme. İki ortogonal serbestliğin neye yol açtığını ve $B^{T}B$'nin tridiagonal çıkışını @fig-bidiagonal gösteriyor: $Q_1 A Q_2$ tekil değeri koruduğundan $A$ bidiagonal'e iner, $B^{T}B$ ise eigenvalue dünyasının tridiagonal'ıdır. ```{python} #| label: fig-bidiagonal #| fig-cap: "Değişmezlik ve bidiagonal indirgeme: ortogonal $Q_1 A Q_2$ tekil değerleri korur, böylece $A$ üst-bidiagonal forma iner (SVD ön-işleme). $B^{\\mathsf T}B$ ise tridiagonaldir — özdeğer dünyasına $A^{\\mathsf T}A$'yı hiç kurmadan geçilir." #| fig-width: 7 #| fig-height: 3.6 #| code-fold: true B = make_bidiagonal([3., 4., 2.5], [1.2, 0.9]) BtB = B.T @ B fig, axs = plt.subplots(1, 2, figsize=(7, 3.6)) spy_structure(axs[0], B, "A -> bidiagonal (SVD ön-işleme)") spy_structure(axs[1], BtB, "B^T B = tridiagonal (özdeğer dünyası)") fig.suptitle("Değişmezlik: Q1 A Q2 tekil değeri korur -> A bidiagonal'e iner; B^T B tridiagonal (A^T A kurmadan)", fontsize=9) fig.tight_layout() plt.show() ``` ::: {.callout-tip title="Builder Notu — Hangi Dönüşüm Neyi Korur"} "Hangi dönüşüm neyi korur" ayrımı temeldir: benzerlik (taban değişimi) özdeğeri, iki-yönlü ortogonal tekil değeri korur. Bu, PCA'nın (kovaryans benzerliği) ve SVD-tabanlı sıkıştırmanın (ortogonal değişmezlik) neden taban seçiminden bağımsız olduğunu açıklar. ::: ## 11. Bidiagonal Form (SVD İçin) {#sec-bidiagonal} İki ortogonal serbestlik sayesinde SVD ön-işlemesi tridiagonal'dan daha ileri gider: **bidiagonal** form (ana köşegen + bir üst köşegen, gerisi sıfır). > *"...reduce it even further from tridiagonal to bidiagonal."* — Strang, 38:11 Algoritma yine iki aşamalı: **(1)** A'yı iki-yönlü ortogonal ile bidiagonal'e indir ($\sigma$'lar korunur), **(2)** QR-tipi yöntemle $\sigma$'ları bul. Bidiagonal $A$ için $A^{T}A$ tridiagonaldir — eigenvalue dünyasıyla tam örtüşür. Böylece SVD, $A^{T}A$'yı hiç açıkça kurmadan hesaplanır. ::: {.callout-tip title="Builder Notu — Bidiagonal'e İn"} Bidiagonalleştirme + örtük QR, `np.linalg.svd`'nin (LAPACK gesdd/gesvd) yaptığıdır: $A^{T}A$'sız, sayısal kararlı SVD. Düşük-rank yaklaşım, PCA, pseudoinverse ve gürültü gidermenin güvenilir temeli. ::: ## Bu Dersin Özeti {#sec-ozet-d12} 1. **QR iterasyonu** — $A = QR \to A_1 = RQ \to$ tekrarla; özdeğerler köşegende belirir. 2. **Benzerlik** — $A_1 = Q^{-1}AQ$; özdeğerler korunur. 3. **Köşegen-altı söner** — kübik yakınsama; köşegen → özdeğerler. 4. **Shift** — $A - sI$ ile hızlandır; benzerlik korunur, $\lambda \to \lambda - s$. 5. **Abel sınırı** — 5. derece+ kapalı formülü yok; iterasyon zorunlu ($\varepsilon$-yakın). 6. **Hessenberg** — bir alt köşegen + sıfırlar; ön-işleme QR'ı hızlandırır. 7. **Simetrik → tridiagonal** — ~2n sayı; $O(n)$ adım, çok hızlı. 8. **eig(A)** — Hessenberg + shift'li QR; LAPACK. 9. **AᵀA ve determinant'tan KAÇIN** — kondisyon karelenir / kötü-koşullu. 10. **Değişmezlik** — $Q^{-1}AQ$ özdeğeri, $Q_1 A Q_2$ tekil değeri korur; SVD → bidiagonal. ::: {.callout-important title="Tek Bir Cümle"} Özdeğer/tekil değer hesabının motoru QR iterasyonudur: $A = QR \to RQ$ döngüsü her adımda $Q^{-1}AQ$ benzerliğiyle özdeğerleri korur ve köşegen-altını söndürür; Hessenberg/tridiagonal/bidiagonal ön-işleme ve shift bunu pratik kılar — ama Abel yüzünden hep iteratif ($\varepsilon$-yakın), asla kesin. ::: ## Kontrol Soruları {#sec-sorular-d12} ::: {.callout-note title="Soru 1: QR iterasyonunda A₁ = RQ'nun A₀ = QR ile aynı özdeğerlere sahip olduğunu göster." collapse="true"} **Cevap:** $A_0 = QR$ olduğundan $R = Q^{-1}A_0$. Yerine koy: $$A_1 = RQ = Q^{-1}A_0 Q$$ Bu bir benzerlik dönüşümü ($M = Q$ ile $M^{-1}A_0 M$). Benzer matrisler aynı özdeğerlere sahiptir (Ders 4). $Q$ ortogonal olduğundan $Q^{-1} = Q^{T}$, hesap kararlı. Demek ki tüm $A_0, A_1, A_2, \ldots$ aynı özdeğerlere sahiptir; köşegende beliren değerler gerçek özdeğerlerdir. ::: ::: {.callout-note title="Soru 2: A − sI kaydırması özdeğerleri ve özvektörleri nasıl etkiler? Neden yakınsamayı hızlandırır?" collapse="true"} **Cevap:** $A_0 v = \lambda v$ ise $(A_0 - sI)v = (\lambda - s)v$: özvektörler **aynı**, özdeğerler $s$ kadar **kayar** ($\lambda \to \lambda - s$). Eğer $s$ bir özdeğere (örneğin en küçüğüne) yakınsa, o özdeğer 0'a yaklaşır ve QR adımında köşegen-altı o satırda çok hızlı söner. İyi shift seçimi kübik yakınsamayı daha da hızlandırır. Kaydırma geri eklenince ($A_1 = RQ + sI$) benzerlik korunur. ::: ::: {.callout-note title="Soru 3: Neden A'yı basit adımlarla tam üst üçgensel (özdeğerler köşegende) yapamayız, sadece Hessenberg'e indirebiliriz?" collapse="true"} **Cevap:** Tam üçgensel yapabilseydik özdeğerleri köşegende **kesin** okurduk — sonlu adımda. Ama özdeğerler $n.$ dereceden bir denklemin kökleridir ve Abel kanıtladı: 5. derece+ için kapalı formül yoktur. Sonlu kesin adımlarla çözmek bu teoremi çiğnerdi. Bu yüzden en fazla Hessenberg'e (bir alt köşegen kalır) inebiliriz; gerisi iteratif QR ile $\varepsilon$-yakın bulunur. ::: ::: {.callout-note title="Soru 4: Tekil değerleri bulmak için neden AᵀA'yı açıkça kurmazsın?" collapse="true"} **Cevap:** $\sigma = \sqrt{\lambda_i(A^{T}A)}$ (yani $\sigma$, $A^{T}A$'nın bir özdeğerinin kareköküdür) matematiksel olarak doğru ama $A^{T}A$ kurmak **kondisyon sayısını kareler** ($\kappa \to \kappa^2$). Küçük tekil değerlerin bilgisi yuvarlama hatasında kaybolur (örneğin $\sigma = 10^{-4}$ ise $\sigma^2 = 10^{-8}$ makine epsilon'una gömülür). Bunun yerine SVD doğrudan $A$'yı bidiagonalleştirir ($A^{T}A$'sız) ve en küçük $\sigma$'ların doğruluğunu korur. Ters problemler ve düşük-rank yaklaşımda bu kritiktir. ::: ## Egzersizler {#sec-egzersizler-d12} Cevapsız problemler. Çöz, sonra `numpy` ile kontrol et. **Egzersiz 1.** $A = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}$ için bir QR iterasyon adımı yap: $A = QR$ bul, sonra $A_1 = RQ$ hesapla. $A_1$'in köşegeninin özdeğerlere (3, 1) yaklaştığını gözlemle. **Egzersiz 2.** $A = \begin{pmatrix} 5 & 1 \\ 0 & 2 \end{pmatrix}$ için $s = 2$ shift uygula: $(A - 2I) = QR$, $A_1 = RQ + 2I$. $A_1$'in özdeğerlerinin hâlâ 5 ve 2 olduğunu doğrula. **Egzersiz 3.** Aşağıdaki simetrik matris zaten tridiagonal mi? QR iterasyonunda tridiagonal kalır mı? Kaç bağımsız sayı içerir ($n = 4$)? $$A = \begin{pmatrix} 2 & 1 & 0 & 0 \\ 1 & 2 & 1 & 0 \\ 0 & 1 & 2 & 1 \\ 0 & 0 & 1 & 2 \end{pmatrix}$$ **Egzersiz 4.** Python ile QR iterasyonunu elle yap: ```python import numpy as np A = np.array([[2.0, 1.0], [1.0, 2.0]]) for k in range(5): Q, R = np.linalg.qr(A) A = R @ Q # QR iterasyon adımı print(f"adım {k+1}, köşegen:", np.diag(A)) # 3, 1'e yakınsar print("eig(A0):", np.linalg.eigvalsh([[2.0, 1.0], [1.0, 2.0]])) ``` **Egzersiz 5.** (Ders 13 habercisi.) Ders 13 rastlantısal matris çarpımına geçer: dev $AB$ çarpımını tüm kolonlar yerine **örneklenmiş** kolon/satır çiftleriyle yaklaşık hesaplamak. $AB = \sum$ ($A$'nın kolonu)($B$'nin satırı) ifadesini hatırla (Ders 1); neden bazı terimleri olasılıkla örneklemek tüm toplamı yaklaşık verebilir? Bir terim seçme olasılığını ne ile orantılı alırdın? ## Sonraki Ders İçin Hazırlık {#sec-sonraki-d12} **Ders 13: Rastlantısal Matris Çarpımı** Ders 12'de kesin özdeğer/SVD'yi gördük. Ders 13 dev matrisler için olasılığa döner: örnekleme ile yaklaşık hesap. - Rastlantısal matris çarpımı: kolon/satır çiftlerini örnekle - Norm-kare örnekleme olasılığı (önemli terimleri seç) - Beklenen değer ve varyans (Stat 110 köprüsü) - Randomized SVD'ye giriş; büyük-ölçek ML ::: {.callout-warning title="Ders 13 Öncesi Yapılacak"} - Bu dersin egzersizlerini çöz, özellikle Egzersiz 5'i (örnekleme sezgisi). - Python'da bir $AB$ çarpımını az sayıda kolon/satır çiftiyle yaklaşık hesaplamayı dene; hatayı gözlemle. - Ana cümleyi tekrar oku: "QR iterasyonu özdeğerleri benzerlikle köşegene taşır; Abel yüzünden hep iteratif." ::: ## Anahtar Kavramlar (Cheat Sheet) {#sec-cheat-sheet-d12} | Kavram | Tanım | Strang'de | |--------|-------|-----------| | **QR iterasyonu** | $A = QR \to A_1 = RQ \to$ tekrarla | 2m12 | | **Benzerlik** | $A_1 = Q^{-1}AQ$; özdeğerler korunur | 4m29 | | **Kübik yakınsama** | Köşegen-dışı her adımda küpü alınır | 9m29 | | **Özdeğerler köşegende** | İterasyon limiti; köşegen → $\lambda$ | 17m36 | | **Shift** | $A - sI$; $\lambda \to \lambda - s$, hızlandırır | 10m27 | | **Abel sınırı** | 5. derece+ kapalı formül yok; iterasyon zorunlu | 21m36 | | **Hessenberg** | Bir alt köşegen + sıfırlar; ön-işleme | 22m56 | | **Simetrik → tridiagonal** | ~2n sayı; $O(n)$ adım, çok hızlı | 27m09 | | **AᵀA'dan kaçın** | Kondisyon karelenir; SVD doğrudan $A$'da | 28m43 | | **Bidiagonal (SVD)** | İki-yönlü ortogonal; $\sigma$'lar için ön-işleme | 38m11 | ## ML Bağlantıları Özeti {#sec-ml-baglantilar-d12} 1. **QR iterasyonu** → `eig`/`eigh`/`svd`'nin motoru (LAPACK); PCA, spektral yöntemler. 2. **Benzerlik ($Q^{-1}AQ$)** → özdeğer korur; taban değişiminin ML'deki güvencesi. 3. **Shift** → ters iterasyon, önkoşullama; bilinen tahmine hızlı yakınsama. 4. **Simetrik → tridiagonal** → kovaryans/Gram/Hessian özdeğerlerini hızlı hesaplama. 5. **AᵀA'dan kaçın** → SVD'nin sayısal kararlılığı; küçük $\sigma$'ların korunması. 6. **Abel sınırı** → özdeğer/SVD hep yaklaşık ($\varepsilon$-yakın); ML'de "yeterince kesin". 7. **LAPACK çağır** → elle yazma; onyıllarca kararlılık çalışmasının ürünü. ::: {.callout-important title="Eğer bu dersten tek bir şey alıp gidersen"} `eig` ve `svd`'nin motoru QR iterasyonudur: $A = QR \to RQ$ döngüsü her adımda $Q^{-1}AQ$ benzerliğiyle özdeğerleri korur ve köşegen-altını kübik hızla söndürür. Hessenberg (simetrikte tridiagonal) ön-işleme ve shift bunu pratik kılar; SVD ise $A^{T}A$'yı hiç kurmadan bidiagonal forma indirger. Abel yüzünden hep iteratif ($\varepsilon$-yakın) — ama LAPACK bunu milisaniyelerde, güvenilir biçimde yapar. :::