---
title: "A = LU Faktorizasyonu"
subtitle: "Eliminasyonun doğru matris formu — ve numerik LA'nın temel taşı"
---
::: {.callout-note title="Bölüm bilgisi"}
- **Strang'in videosu:** [YouTube — Lecture 4: A = LU Factorization](https://www.youtube.com/watch?v=MsIvs_6vC38) (≈48 dk)
- **OCW sayfası:** [MIT 18.06SC — Lecture 4](https://ocw.mit.edu/courses/18-06sc-linear-algebra-fall-2011/resources/factorization-into-a-lu/)
- **Okuma süresi:** ≈40 dk
:::
## Bu Derste Ne Var? {#sec-bu-derste}
Ders 3'te ters matrisi ve Gauss–Jordan'ı gördük. Ders 4'ün iki teması:
1. **Kısa hazırlık:** $(AB)^{-1} = B^{-1}A^{-1}$ ve $(A^T)^{-1} = (A^{-1})^T$.
2. **Asıl mesele — $A = LU$:** Ders 2'de $EA = U$ gördük. Şimdi ters çevirip $A = LU$ yazıyoruz. Sebep: $L$ sezgisel olarak güzel bir matris (eliminasyon çarpanları doğrudan yerleşir), $E$ ise değildir (çarpanlar birbirine karışır).
> *"A = LU is the most basic factorization of a matrix."* — Strang, 7:13
```{mermaid}
%%| label: fig-concept-map
%%| fig-cap: "Eliminasyon → A = LU. L çarpanları, U pivotları taşır; partial pivoting gerektiğinde PA = LU."
flowchart LR
A["A (orijinal)"] --> EA["E·A = U<br/>(Ders 2)"]
EA --> Invert["E^{-1} ile çevir"]
Invert --> LU["⭐ A = L·U"]
LU --> L["L: alt üçgensel<br/>köşegen = 1<br/>çarpanlar yerinde"]
LU --> U2["U: üst üçgensel<br/>köşegen = pivotlar"]
LU --> PIVOT["partial pivoting<br/>P·A = L·U"]
LU --> ML["⚡ np.linalg.solve<br/>scipy.linalg.lu_factor<br/>Cholesky (Ders 25/28)"]
style LU fill:#fff3e0,stroke:#e67e22,stroke-width:3px
style ML fill:#fce4ec,stroke:#c2185b,stroke-width:3px
```
::: {.callout-tip title="Builder Notu — Neden LU Her Yerde"}
- **`np.linalg.solve(A, b)`** arka planda: $A = LU$ faktorize et → $Ly = b$ (forward sub) → $Ux = y$ (back sub).
- **Aynı $A$ ile birden çok $\mathbf{b}$ çöz:** LU'yu **bir kez** hesapla, sonra her $\mathbf{b}$ için sadece $O(n^2)$ öde, $O(n^3)$ değil. Kalman filter, Newton's method, batch çözümlerin altyapısı.
- **Cholesky decomposition** (Ders 25/28) LU'nun simetrik pozitif tanımlı özel hali — Bayesian inference, Gaussian processes, normal equations.
- **Maliyet $\approx n^3/3$** — GPU TFLOPS sayıları bu hesapla anlam kazanır.
:::
## $(AB)^{-1} = B^{-1}A^{-1}$ — Çarpımın Tersi {#sec-AB-inverse}
$$
(AB)(B^{-1}A^{-1}) = A(BB^{-1})A^{-1} = A \cdot I \cdot A^{-1} = I \checkmark
$$
Sıra **ters dönüyor**. Strang'in metaforu:
> *"You take off your shoes, you take off your socks; the good way to invert that process is socks back on first, then shoes."* — Strang, 3:21
Çorap önce, ayakkabı sonra; tersi: ayakkabı önce çıkar, çorap sonra.
## $(A^T)^{-1} = (A^{-1})^T$ — Transpoz ve Ters Yer Değiştirir {#sec-transpose-inverse}
$AA^{-1} = I$'yı transpozla:
$$
(AA^{-1})^T = I^T \implies (A^{-1})^T A^T = I
$$
Demek ki $(A^T)^{-1} = (A^{-1})^T$. Transpoz ve ters alma işlemleri **commute eder**.
**ML'de:** Normal equations $(A^T A)^{-1}$ simetri korur. Kovaryans $\Sigma^{-1}$ simetrik kalır. Backprop'ta forward $\mathbf{y} = W\mathbf{x}$ → gradient $W^T$ ile zincirlenir.
## A = LU — Basit 2×2 Örneği {#sec-lu-2x2}
Ders 2'den: $EA = U$. Tersini al:
$$
A = E^{-1} U \quad \Longleftrightarrow \quad A = LU \qquad (L := E^{-1})
$$
**Strang'in örneği:**
$$
A = \begin{pmatrix} 2 & 1 \\ 8 & 7 \end{pmatrix}
$$
Çarpan $\ell_{21} = 8/2 = 4$:
$$
E_{21} = \begin{pmatrix} 1 & 0 \\ -4 & 1 \end{pmatrix}, \quad E_{21} A = \begin{pmatrix} 2 & 1 \\ 0 & 3 \end{pmatrix} = U
$$
$L = E_{21}^{-1}$ — sadece işaret değişir ($-4 \to +4$):
$$
L = \begin{pmatrix} 1 & 0 \\ 4 & 1 \end{pmatrix}, \quad LU = \begin{pmatrix} 1 & 0 \\ 4 & 1 \end{pmatrix}\begin{pmatrix} 2 & 1 \\ 0 & 3 \end{pmatrix} = \begin{pmatrix} 2 & 1 \\ 8 & 7 \end{pmatrix} = A \checkmark
$$
**$L$'nin (2,1) konumundaki $4$**, eliminasyondaki çarpan $\ell_{21}$'in **kendisi**. Rastlantı değil.
```{python}
#| label: fig-LU-yapisi-2x2
#| fig-cap: "$A = LU$ ayrışımı: $L$ alt üçgensel (köşegen 1, çarpanlar yerinde), $U$ üst üçgensel (köşegen = pivotlar)."
#| fig-width: 11
#| fig-height: 4
import numpy as np
import matplotlib.pyplot as plt
A = np.array([[2, 1], [8, 7]], dtype=float)
L = np.array([[1, 0], [4, 1]], dtype=float)
U = np.array([[2, 1], [0, 3]], dtype=float)
def draw(ax, M, title, palette):
n = M.shape[0]
for i in range(n):
for j in range(n):
color = palette(M, i, j)
ax.add_patch(plt.Rectangle((j, n-1-i), 1, 1, facecolor=color, edgecolor='#475569', linewidth=1.5))
ax.text(j+0.5, n-1-i+0.5, f'{M[i,j]:g}', ha='center', va='center',
fontsize=18, fontweight='bold',
color='#1e293b' if M[i,j] != 0 else '#cbd5e0')
ax.set_xlim(0, n); ax.set_ylim(0, n); ax.set_aspect('equal')
ax.set_xticks([]); ax.set_yticks([]); ax.set_title(title, fontsize=12)
for s in ax.spines.values(): s.set_visible(False)
def palL(M, i, j):
if M[i,j] == 0: return '#f1f5f9'
if i == j: return '#fbbf24' # kosegen = 1
if i > j: return '#fed7aa' # carpan
return '#e0e7ff'
def palU(M, i, j):
if M[i,j] == 0: return '#f1f5f9'
if i == j: return '#fbbf24' # pivot
if i < j: return '#bfdbfe'
return '#e0e7ff'
def palA(M, i, j):
if M[i,j] == 0: return '#f1f5f9'
return '#e0e7ff'
fig, axes = plt.subplots(1, 3, figsize=(11, 4))
draw(axes[0], A, r'$A$', palA)
draw(axes[1], L, r'$L$ (köşegen 1, çarpan 4)', palL)
draw(axes[2], U, r'$U$ (pivotlar 2, 3)', palU)
fig.suptitle(r'$A = LU$', fontsize=14, y=1.02)
plt.tight_layout()
plt.show()
```
## A = LDU — Pivotları Köşegene Çekme {#sec-LDU}
$L$ ve $U$ arasında bir asimetri var. Pivotları ayrı bir köşegen matrise çek:
$$
U = \begin{pmatrix} 2 & 1 \\ 0 & 3 \end{pmatrix} = \underbrace{\begin{pmatrix} 2 & 0 \\ 0 & 3 \end{pmatrix}}_{D} \underbrace{\begin{pmatrix} 1 & 1/2 \\ 0 & 1 \end{pmatrix}}_{U'}
$$
$$
A = L D U'
$$
Hem $L$ hem $U'$ köşegende 1'ler taşır; $D$ pivotları. **Simetrik matrisler için $A = L D L^T$** olacak (Ders 25, Cholesky'nin temeli).
## 3×3 — Çarpanlar L'de Doğrudan Oturuyor ⭐ {#sec-3x3-magic}
3×3'te üç eliminasyon adımı: $E_{32} E_{31} E_{21} A = U$, yani $A = (E_{21}^{-1} E_{31}^{-1} E_{32}^{-1}) U = LU$.
Strang'in büyük gözlemi: **Çarpanlar $L$'ye doğrudan yerleşir, hiçbir matris çarpımı gerekmez.**
> *"The multipliers go directly into L. You can throw away A as you create LU."* — Strang, 23:52
```{python}
#| label: fig-carpanlar-Lye-yerleşir
#| fig-cap: "3×3 için çarpanlar L'ye doğrudan yerleşir, E'de karışır. ℓ₂₁=2 ve ℓ₃₂=5 olsun: E'nin (3,1) hücresinde 2·5=10 karışıklığı çıkar, L'de hiç olmaz."
#| fig-width: 11
#| fig-height: 4
E21 = np.array([[1,0,0],[-2,1,0],[0,0,1]], dtype=float)
E32 = np.array([[1,0,0],[0,1,0],[0,-5,1]], dtype=float)
E = E32 @ E21
L21 = np.array([[1,0,0],[2,1,0],[0,0,1]], dtype=float)
L32 = np.array([[1,0,0],[0,1,0],[0,5,1]], dtype=float)
L = L21 @ L32 # ters siralama!
def draw3(ax, M, title, highlight=None):
n = 3
for i in range(n):
for j in range(n):
if M[i,j] == 0:
color = '#f1f5f9'
elif highlight and (i,j) in highlight:
color = '#fca5a5' # karışıklık vurgusu
elif i == j:
color = '#fbbf24'
elif i > j:
color = '#fed7aa'
else:
color = '#bfdbfe'
ax.add_patch(plt.Rectangle((j, n-1-i), 1, 1, facecolor=color, edgecolor='#475569', linewidth=1.5))
ax.text(j+0.5, n-1-i+0.5, f'{M[i,j]:g}', ha='center', va='center',
fontsize=16, fontweight='bold')
ax.set_xlim(0,3); ax.set_ylim(0,3); ax.set_aspect('equal')
ax.set_xticks([]); ax.set_yticks([]); ax.set_title(title, fontsize=11)
for s in ax.spines.values(): s.set_visible(False)
fig, axes = plt.subplots(1, 2, figsize=(11, 4))
draw3(axes[0], E, r'$E = E_{32} E_{21}$ — (3,1)\'de **10** karışıklığı', highlight={(2,0)})
draw3(axes[1], L, r'$L = E_{21}^{-1} E_{32}^{-1}$ — çarpanlar (2, 5) yerlerinde')
plt.tight_layout()
plt.show()
```
**Neden $L$'de karışmıyor?** Ters sırada çarpıyoruz; üst matris ($E_{21}^{-1}$) zaten satır 2'yi etkilemiş, alt matris ($E_{32}^{-1}$) sadece satır 3'e dokunuyor. Üst-alt etkileşim olmadan, her çarpan kendi yerine yerleşir.
::: {.callout-tip title="Builder Notu — LU Cache"}
`scipy.linalg.lu_factor(A)` L ve U'yu compact formatta döndürür. Sonra `lu_solve(LU_factors, b)` her $\mathbf{b}$ için $O(n^2)$ — çok daha ucuz. Newton's method, recursive Bayesian filter, PDE çözücüler, hepsi bu pattern.
:::
## Eliminasyon Maliyeti — $n^3/3$ {#sec-maliyet}
İlk adım: $(n-1) \times (n-1)$ blok değişir → $\sim n^2$ işlem. İkinci: $\sim (n-1)^2$. Toplam:
$$
T(n) = \sum_{k=1}^{n} k^2 \approx \int_0^n x^2\,dx = \frac{n^3}{3}
$$
> *"It's about one third of n cubed. That's the magic operation count."* — Strang, 36:35
**Sağ taraf maliyeti:** $\mathbf{b}$ için $\sim n^2$ — ihmal edilebilir.
| Boyut | LU faktorize | Her $\mathbf{b}$ için çözüm |
|-------|--------------|-----------------------------|
| $n = 100$ | $\sim 10^5$ flop | $\sim 10^4$ flop |
| $n = 1000$ | $\sim 10^9$ flop ($\sim$ 1 sn) | $\sim 10^6$ flop ($\sim$ 1 ms) |
| $n = 10000$ | $\sim 10^{12}$ flop (dk) | $\sim 10^8$ flop ($\sim$ 100 ms) |
**$n$'yi 2× alırsan, maliyet $8 \times$.** Bu, neden modern ML'in tam matris terslerinden kaçındığını açıklıyor: 1B × 1B parametre için $10^{27}$ flop — imkansız. Onun yerine SGD, Adam, KFAC gibi yaklaşık metotlar.
## Permütasyon Matrisleri ve PA = LU {#sec-permutation}
Pivot pozisyonunda sıfır gelirse satır takası gerek. **Permütasyon matrisi $P$** = identity'nin satırları yer değişmiş hali. Soldan çarpma → satır takası.
Genel form: $PA = LU$. `scipy.linalg.lu(A)` her zaman $(P, L, U)$ üçlüsü döner.
**Numerik sağlamlık (partial pivoting):** Pratikte LAPACK her adımda kolondaki en büyük (mutlak) elemanı pivot olarak seçer. Küçük pivota bölme = float hata patlaması.
**$n \times n$ permütasyon sayısı = $n!$:**
- $n = 3 \to 6$
- $n = 4 \to 24$
- $n = 10 \to 3.6$M
Bu hızlı büyüme, "her permütasyonu dene" algoritmalarının neden çalışmadığını (TSP, vb.) açıklıyor.
## $P^{-1} = P^T$ — Permütasyonların Sihirli Özelliği {#sec-P-orthogonal}
Permütasyon matrisleri **ortogonal**:
$$
P^{-1} = P^T
$$
Geometri: $P$ bir takas, geri almak = aynı takası tekrar. Ortogonal matrisler Ders 17'de detaylı işlenecek.
**Grup yapısı:** $n!$ permütasyon bir matematiksel grup oluşturur — kapalı çarpım, identity, terslere sahip. ML'de gruplar simetri = **equivariant networks** (GNN, transformer permütasyon-equivariance, group convolutions).
## Bu Dersin Özeti {#sec-ozet}
1. **$(AB)^{-1} = B^{-1}A^{-1}$** — sıra ters.
2. **$(A^T)^{-1} = (A^{-1})^T$** — transpoz ve ters yer değiştirir.
3. **$A = LU$** — eliminasyonun doğru matris formu.
4. **Çarpanlar $L$'ye doğrudan oturur** — eliminasyon sırasında sadece $\ell_{ij}$ kayıt et, $L$ bedava.
5. **$A = LDU$** — alternatif simetrik form ($D$ pivotları taşır).
6. **Maliyet $\sim n^3/3$** ($\mathbf{b}$ için $\sim n^2$).
7. **Permütasyon matrisleri $P$** — satır takası, $n \times n$ için $n!$ tane.
8. **$P^{-1} = P^T$** — ortogonallik.
::: {.callout-important title="Tek bir cümle"}
Eliminasyon = **$A = LU$** demektir. $L$ eliminasyon çarpanlarını yerinde taşır; $U$ pivotlu üst üçgensel. Numerik LA'nın en temel ayrışımı — `solve` çağrısının arkasında bu çalışıyor.
:::
## Kontrol Soruları {#sec-sorular}
::: {.callout-note collapse="true" title="Soru 1: A = ((3,6),(9,14)) için LU bul."}
$\ell_{21} = 9/3 = 3$. $E_{21} A = U$:
$$
U = \begin{pmatrix} 3 & 6 \\ 0 & -4 \end{pmatrix}
$$
$L$: çarpan $+3$, (2,1)'e:
$$
L = \begin{pmatrix} 1 & 0 \\ 3 & 1 \end{pmatrix}
$$
Pivotlar: $3, -4$. $LU = A$ ✓.
:::
::: {.callout-note collapse="true" title="Soru 2: A = ((1,2),(0,1)), B = ((1,0),(3,1)). (AB)⁻¹'i iki yoldan."}
**Yol 1 — direkt:** $AB = \begin{pmatrix} 7 & 2 \\ 3 & 1 \end{pmatrix}$, $\det = 1$, $(AB)^{-1} = \begin{pmatrix} 1 & -2 \\ -3 & 7 \end{pmatrix}$.
**Yol 2 — formül:** $A^{-1} = \begin{pmatrix} 1 & -2 \\ 0 & 1 \end{pmatrix}$, $B^{-1} = \begin{pmatrix} 1 & 0 \\ -3 & 1 \end{pmatrix}$. Sıra ters:
$$
B^{-1} A^{-1} = \begin{pmatrix} 1 & -2 \\ -3 & 7 \end{pmatrix} \checkmark
$$
$A^{-1} B^{-1}$ yapsaydık yanlış çıkardı.
:::
::: {.callout-note collapse="true" title="Soru 3: A = ((0,1,1),(1,0,1),(1,1,0)) için satır takası gerekli — PA = LU yap."}
(1,1)'de **0** var → satır 1 ↔ satır 2 takas, $P = P_{12}$:
$$
PA = \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 0 \end{pmatrix}
$$
Eliminasyon: $\ell_{31} = 1$, $\ell_{32} = 1$. $U$:
$$
U = \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & -2 \end{pmatrix}
$$
$L$ (çarpanlar):
$$
L = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 1 & 1 \end{pmatrix}
$$
Pivotlar $1, 1, -2$ — sıfır yok, $A$ invertible.
:::
::: {.callout-note collapse="true" title="Soru 4: solve niye inv @ b'den hem hızlı hem doğru? (LU bağlantısı.)"}
**Hız:**
- `inv(A)`: LU + $n$ tane RHS çözümü ($n \cdot n^2 = n^3$) + $\text{inv} \cdot \mathbf{b}$ ($n^2$). Toplam $\sim 4n^3/3$.
- `solve(A, b)`: tek LU ($n^3/3$) + tek forward/back sub ($n^2$). Toplam $\sim n^3/3$. **~$4\times$** hızlı.
**Sağlamlık:** `inv` tüm hücreleri hesaplar → her hücrede float hata birikir; sonra $\text{inv} \cdot \mathbf{b}$ hataları büyütür. `solve` partial pivoting'li LU — stabilite optimize.
**İstisna:** $A^{-1}$'i çok kere kullanacaksan inv hesaplayıp cache'le. Modern Bayesian inference/Kalman: `lu_factor` + `lu_solve` (tam ters yerine LU sakla).
:::
## Egzersizler {#sec-egzersizler}
**Egzersiz 1.** $A = \begin{pmatrix} 2 & 1 & 0 \\ 6 & 4 & 1 \\ 4 & 5 & 3 \end{pmatrix}$ için $LU$ — çarpanları kayıt et, $L$'yi doğrudan inşa et.
**Egzersiz 2.** Egzersiz 1'in $A$'sı için $A\mathbf{x} = (1, 7, 14)^T$:
- Forward sub: $L\mathbf{y} = \mathbf{b}$
- Back sub: $U\mathbf{x} = \mathbf{y}$
**Egzersiz 3.** Tridiagonal $A = \begin{pmatrix} 1 & 1 & 0 & 0 \\ 2 & 3 & 1 & 0 \\ 0 & 4 & 6 & 1 \\ 0 & 0 & 5 & 8 \end{pmatrix}$ için sadece $L$'nin köşegen-altı elemanlarını bul. (Tridiagonal → LU çok hızlı.)
**Egzersiz 4.** *(Python)* `scipy.linalg.lu` ile partial pivoting'li ayrışım.
```{python}
#| label: code-egzersiz-4
#| code-fold: false
import numpy as np
from scipy.linalg import lu
A = np.array([[2, 1, 0], [6, 4, 1], [4, 5, 3]], dtype=float)
P, L, U = lu(A)
print("P =\n", P)
print("L =\n", L)
print("U =\n", U)
print("Pivotlar (diag U):", np.diag(U))
print("P @ L @ U =\n", P @ L @ U)
assert np.allclose(P @ L @ U, A)
```
**Egzersiz 5.** *İspat:* $A$ simetrik ve $LU$ ayrışımı (satır takasısız) varsa, $A = LDL^T$ (Cholesky'nin temeli, Ders 25).
İpucu: $A = LU = LDU'$ ve $A = A^T$. Eşitlikten $L = U'^T$ yani $A = LDL^T$ çıkar.
## Sonraki Ders İçin Hazırlık {#sec-sonraki}
**Ders 5: Transpoz, Permütasyon, Vektör Uzayları $\mathbb{R}^n$**
- Transpoz kuralları, simetrik matrisler ($A = A^T$).
- Permütasyon matrislerinin grup yapısı.
- **Vektör uzayları** $\mathbb{R}^2, \mathbb{R}^3, \mathbb{R}^n$ ve **alt-uzaylar** — Chapter 3'ün açılışı.
::: {.callout-warning title="Ders 5 öncesi yapılacak"}
- Egzersizleri çöz, özellikle **4** (scipy.linalg.lu) ve **5** (Cholesky temeli).
- `solve` vs `inv` performansını $n = 1000$ ve $n = 2000$ için ölç.
- Ana cümleyi tekrar oku: *"Eliminasyon = $A = LU$. Çarpanlar $L$'de yerinde, $U$'da pivotlar."*
:::
## Anahtar Kavramlar (Cheat Sheet) {#sec-cheat-sheet}
| Kavram | Tanım | Strang'da |
|--------|-------|-----------|
| **$(AB)^{-1}$** | $B^{-1}A^{-1}$ — sıra ters | 0:31 |
| **$(A^T)^{-1}$** | $(A^{-1})^T$ — transpoz/ters yer değiştirir | 4:01 |
| **$A = LU$** | Eliminasyonun matris formu | 7:06 |
| **$L$ (lower)** | Alt üçgensel, köşegen 1, çarpanlar yerinde | 12:02 |
| **$U$ (upper)** | Üst üçgensel, köşegen pivotlar | 8:10 |
| **$A = LDU$** | $L, U$'da 1'ler, $D$'de pivotlar | 12:22 |
| **3×3'te 10 problemi** | $E$'de çarpanlar karışır, $L$'de karışmaz | 18:24 |
| **Operation count** | $n^3/3$ + $n^2$ per RHS | 36:35 |
| **Partial pivoting** | Numerik stabilite için en büyüğü pivot | 38:50 |
| **Permütasyon $P$** | Identity satır takası | 39:35 |
| **$PA = LU$** | Genel form | 40:30 |
| **$P^{-1} = P^T$** | Ortogonallik | 47:06 |
| **$n!$ permütasyon** | $n \times n$ için tam sayı | 47:19 |
## ML Bağlantıları Özeti {#sec-ml-baglantilar}
::: {.callout-tip title="7 köprü"}
1. **$A = LU$ = `np.linalg.solve`** → Her solve çağrısının arkasında.
2. **LU cache** → `lu_factor` + `lu_solve` → Kalman/Newton/Bayesian inference.
3. **$n^3/3$ maliyeti** → Tam matris terslerinden kaçınma; SGD/Adam/KFAC.
4. **Cholesky $A = LL^T$** → Bayesian inference, Gaussian processes, normal equations.
5. **$P$ permütasyonu → equivariant networks** → GNN, transformer permütasyon-equivariance, group convolutions.
6. **$(AB)^{-1} = B^{-1}A^{-1}$** → Backward pass, normalizing flows (Glow, RealNVP).
7. **$(A^T)^{-1} = (A^{-1})^T$** → Normal equations simetri koruması; ridge, kernel methods, GP.
:::
::: {.callout-important title="Tek bir şey alıp gideceksen"}
**Eliminasyon = $A = LU$.** $L$ çarpanları yerinde taşır; $U$ pivotlu üst üçgensel. Numerik LA'nın temel taşı — `solve` çağırdığın her yerde arka planda bu çalışıyor.
:::