Temel Doğrusal Cebir İşlemleri

Önceki ders iki diziyi öğe öğe eşleştiren işlemleri ele aldı: yayılım, aynı konumdaki iki değeri buluşturur. Tarife hesabının kendisi böyle çalışmaz. Bir abonenin üç dönemlik okuması üç tarife basamağına dağıtıldığında her sonuç değeri bir satırın tamamı ile bir sütunun tamamının birlikte hesabıdır. Bu ders bu iki işlemi — matris çarpımını ve ondan türeyen çözüm problemini — ölçer.

Ölçünün konusu cebir değildir; kuram burada anlatılmaz. Ölçülen şey, aynı sonucu üreten iki yazımın kaç işlem tuttuğu ve soyutlamayı çağırmanın hangi kararı üstlendiğidir. Bu konunun en keskin sayıları buradan çıkıyor, çünkü çözüm probleminde soyutlamanın kazancı satır sayısı değil, algoritma seçimidir.

• SH9. Matris çarpımında soyutlama işlem sayısını değiştirmez. Değiştirdiği şey çağrı yerindeki satır sayısı ve elle yazılan dizin hesabının ortadan kalkmasıdır.
• SH10. Çözümde soyutlamayı çağırmak bir algoritma seçmektir. Tanımdan yazılan yol ile elemenin işlem sayısı aynı büyüklük düzeyinde değildir ve fark boyutla birlikte hızla büyür.
• SH11. Aynı işlem sayısıyla iki farklı sonuç alınabilir. Pivotlama kararı artığın büyüklüğünü belirler; girdi duyarlılığı ise hesaptan bağımsızdır ve kötü koşullanmış bir sistemde ölçüm çözünürlüğü kadar bir fark sonucu yarı yarıya oynatır.

Aynı İşlem, Başka Yazım

# carpim.py — MODELDIR: matris carpimi once elle uc dongu ile, sonra tek cagri
# olarak yaziliyor. Okuma tablosu (1260, 3), tarife matrisi (3, 3); sonuc her
# abonenin uc tarife basamagindaki payi. Kume ve tarife kurgudur.
import inspect

def uretec(tohum):
    s = tohum & 0xFFFFFFFF
    def sonraki():
        nonlocal s
        s = (1664525 * s + 1013904223) & 0xFFFFFFFF
        return s / 4294967296
    return sonraki

ABONE, DONEM = 1260, 3
r = uretec(20260218)
HAM = [round(4 + r() * 56, 2) for _ in range(ABONE * DONEM)]
r2 = uretec(9110723)
p = [r2() for _ in range(ABONE * DONEM)]
BOS = set(sorted(range(len(p)), key=lambda j: p[j])[:581])
OKUMA = [0.0 if j in BOS else HAM[j] for j in range(ABONE * DONEM)]
# Tarife matrisi: her donemin okumasinin uc basamaga dagilim orani (10/25/40 m3).
TARIFE = [0.62, 0.28, 0.10,
          0.55, 0.31, 0.14,
          0.48, 0.34, 0.18]

ISLEM = 0   # bir carpma ve bir toplama
DIZIN = 0   # elle yazilan dizin hesabi sayisi

def carp_elle(A, na, ma, B, mb, nb):
    global ISLEM, DIZIN
    C = [0.0] * (na * nb)
    for i in range(na):
        for j in range(nb):
            t = 0.0
            for k in range(ma):
                t += A[i * ma + k] * B[k * nb + j]
                ISLEM += 1
                DIZIN += 2
            C[i * nb + j] = t
            DIZIN += 1
    return C

def carp(A, ba, B, bb):
    return carp_elle(A, ba[0], ba[1], B, bb[0], bb[1])

ISLEM, DIZIN = 0, 0
C1 = carp_elle(OKUMA, ABONE, DONEM, TARIFE, DONEM, DONEM)
i1, d1 = ISLEM, DIZIN
ISLEM, DIZIN = 0, 0
C2 = carp(OKUMA, (ABONE, DONEM), TARIFE, (DONEM, DONEM))
i2, d2 = ISLEM, DIZIN
satir = lambda f: len(inspect.getsource(f).strip().splitlines())
gen = lambda w: lambda h: "".join(str(v).ljust(w[0]) if j == 0 else str(v).rjust(w[j])
                                  for j, v in enumerate(h))
y = gen([28, 16, 16, 10])
sapan = sum(1 for a, b in zip(C1, C2) if abs(a - b) > 1e-9)
print(f"(1260, 3) x (3, 3) -> (1260, 3); sonuc {len(C1)} oge, {sapan} oge 1e-9 esiginin "
      f"ustunde sapiyor\n")
print(y(["olcu", "elle uc dongu", "tek cagri", "oran"]))
print(y(["cagri yerinde satir", satir(carp_elle), satir(carp), f"{satir(carp_elle)/satir(carp):.1f}x"]))
print(y(["carpma-toplama sayisi", i1, i2, f"{i1/i2:.1f}x"]))
print(y(["elle dizin hesabi", d1, 0, "-"]))
print(f"\ncarpma sayisi {ABONE} x {DONEM} x {DONEM} = {ABONE*DONEM*DONEM}; soyutlama bu sayiyi "
      f"degistirmez, yalnizca {d1} dizin hesabini cagri yerinden kaldirir")

(1260, 3) x (3, 3) -> (1260, 3); sonuc 3780 oge, 0 oge 1e-9 esiginin ustunde sapiyor

olcu                           elle uc dongu       tek cagri      oran
cagri yerinde satir                       13               2      6.5x
carpma-toplama sayisi                  11340           11340      1.0x
elle dizin hesabi                      26460               0         -

carpma sayisi 1260 x 3 x 3 = 11340; soyutlama bu sayiyi degistirmez, yalnizca 26460 dizin hesabini cagri yerinden kaldirir

Matris çarpımında soyutlamanın kazancı ölçüldüğünde ortaya çıkan sayı bir uyarıdır. Çarpma sayısı iki yazımda da 11.340 — bu sayı biçimlerden çıkar, yazımdan değil, ve hiçbir çağrı onu düşürmez. Değişen tek şey nerede yazıldığıdır: çağrı yerindeki satır 13’ten 2’ye iner ve 26.460 elle dizin hesabı ortadan kalkar. A[i * ma + k] ile B[k * nb + j] ifadelerinin her biri düz belleği iki boyutlu okumanın elle yazılmış halidir ve bu iki ifadenin birinde çarpanları yer değiştirmek hiçbir hata üretmez, yalnız başka bir sayı üretir.

Kazancın gerçek adı budur: soyutlama hesabı hızlandırmaz, yanlış yazılabilecek yer sayısını düşürür. Ölçek büyüdüğünde bu değişmez; çarpma sayısı biçimlerin çarpımıdır ve bir kütüphane onu ancak farklı bir algoritma seçerek değiştirebilir. Bir sonraki bölüm tam olarak bunun yapıldığı yeri gösteriyor.

Soyutlamanın Seçtiği Algoritma

# cozum.py — MODELDIR: ayni denklem takimi iki yolla cozuluyor. Birincisi tanimdan
# yazilir (determinant kofaktor acilimiyla), ikincisi elemeyle. Islem sayaci ikisini
# de sayiyor; kutuphane cagrilmiyor, iki algoritma da acikca yaziliyor.
KOF = 0
ELE = 0

def det_kofaktor(M, n):
    global KOF
    if n == 1:
        return M[0]
    t = 0.0
    for j in range(n):
        alt = [M[i*n+k] for i in range(1, n) for k in range(n) if k != j]
        KOF += 1
        t += (1 if j % 2 == 0 else -1) * M[j] * det_kofaktor(alt, n - 1)
    return t

def coz_eleme(M, b, n, pivotla=True):
    global ELE
    A = [list(M[i*n:(i+1)*n]) + [b[i]] for i in range(n)]
    for k in range(n):
        if pivotla:
            en = max(range(k, n), key=lambda i: abs(A[i][k]))
            A[k], A[en] = A[en], A[k]
        for i in range(k + 1, n):
            c = A[i][k] / A[k][k]
            for j in range(k, n + 1):
                A[i][j] -= c * A[k][j]
                ELE += 1
    x = [0.0] * n
    for i in range(n - 1, -1, -1):
        t = A[i][n]
        for j in range(i + 1, n):
            t -= A[i][j] * x[j]
            ELE += 1
        x[i] = t / A[i][i]
    return x

kofaktor_islem = lambda n: 0 if n <= 1 else n * (1 + kofaktor_islem(n - 1))
rk = uretec(70117)
def kare(n):
    M = [round(1 + rk() * 9, 3) for _ in range(n * n)]
    b = [round(1 + rk() * 9, 3) for _ in range(n)]
    return M, b

w = gen([6, 18, 14, 14, 12])
print(w(["n", "kofaktor islemi", "formul", "eleme islemi", "oran"]))
for n in (2, 3, 4, 5, 6, 7, 8):
    M, b = kare(n)
    KOF, ELE = 0, 0
    det_kofaktor(M, n)
    k = KOF
    coz_eleme(M, b, n)
    print(w([n, k, kofaktor_islem(n), ELE, f"{k/max(ELE,1):.0f}x"]))
for n in (12,):
    M, b = kare(n)
    ELE = 0
    x = coz_eleme(M, b, n)
    art = max(abs(sum(M[i*n+j] * x[j] for j in range(n)) - b[i]) for i in range(n))
    print(w([n, "-", kofaktor_islem(n), ELE, f"{kofaktor_islem(n)/ELE:.0f}x"]))
    print(f"\nn = {n} icin kofaktor acilimi {kofaktor_islem(n)} islem ister; eleme {ELE} islemle "
          f"bitirir, oran {kofaktor_islem(n)/ELE:.0f} kat")
    print(f"elemenin cozumu denklemi sagliyor: en buyuk artik {art:.2e}, "
          f"esik 1e-9 (katsayilar 1e1 buyuklugunde, 64 bit kesirli tipin cozunurlugu 1e-16)")

n        kofaktor islemi        formul  eleme islemi        oran
2                      2             2             4          0x
3                      9             9            14          1x
4                     40            40            32          1x
5                    205           205            60          3x
6                   1236          1236           100         12x
7                   8659          8659           154         56x
8                  69280         69280           224        309x
12                     -     823059744           704    1169119x

n = 12 icin kofaktor acilimi 823059744 islem ister; eleme 704 islemle bitirir, oran 1169119 kat
elemenin cozumu denklemi sagliyor: en buyuk artik 2.66e-15, esik 1e-9 (katsayilar 1e1 buyuklugunde, 64 bit kesirli tipin cozunurlugu 1e-16)

Soru şudur: üç tarife basamağının birim fiyatı bilinmiyor, ama birkaç abone grubunun toplam faturası ve her grubun basamaklardaki tüketimi biliniyor. Bu bir denklem takımıdır ve iki yolla çözülür. Tanımdan yazılan yol determinantı kofaktör açılımıyla hesaplar; eleme yolu satırları birbirinden çıkararak bilinmeyenleri teker teker yalıtır.

Tablo iki yolun aynı büyüklük düzeyinde olmadığını gösteriyor. n = 4’e kadar fark yoktur, hatta eleme daha fazla iş yapar. n = 6’da oran 12 kat, n = 8’de 309 kattır. Ölçülen sayılar formülle birebir tutuyor — kofaktör açılımının işlem sayısı $T(n) = n \cdot (1 + T(n-1))$ özyinelemesini izler ve bu, n arttıkça çarpanın kendisinin de arttığı bir büyümedir. n = 12 için 823.059.744 işlem eder; eleme aynı sistemi 704 işlemle bitirir. Oran 1.169.119 kat.

Ölçünün kursa taşınan biçimi budur: bir çözüm işlevini çağırmak bir kısayol değil, bir algoritma seçimidir. Kazanç satır sayısında değil, işlem sayısının büyüme biçimindedir. Aynı nedenle, hangi algoritmanın seçildiğini bilmeden çağrılan bir çözüm işlevi, hangi işlem sayısına razı olunduğunu bilmeden verilmiş bir karardır.

Sayısal Duyarlılık

# duyarlilik.py — MODELDIR: uc abone grubunun toplam faturasindan uc tarife
# basamaginin birim fiyati cozuluyor. Katsayilar her grubun basamaklardaki m3
# miktari; kurgudur. Ilk iki grubun tuketim profili birbirine cok yakin.
carpMV = lambda M, x, n: [sum(M[i*n+j] * x[j] for j in range(n)) for i in range(n)]
GERCEK = [12.50, 18.75, 27.40]          # birim fiyat, kurgu
KAT = [10.00, 15.00, 5.00,
       10.02, 15.04, 5.01,
       8.00, 20.00, 12.00]
FATURA = carpMV(KAT, GERCEK, 3)
x0 = coz_eleme(KAT, FATURA, 3)
KAT2 = list(KAT)
KAT2[0] = KAT[0] + 0.01                 # sayac cozunurlugu kadar tek bir degisiklik
x1 = coz_eleme(KAT2, FATURA, 3)
u = gen([16, 16, 18, 14])
print(f"katsayi matrisinin determinanti {det_kofaktor(KAT, 3):.4f}\n")
print(u(["basamak", "cozulen fiyat", "0,01 m3 sonrasi", "sapma yuzde"]))
for i, ad in enumerate(["10 m3", "25 m3", "40 m3"]):
    print(u([ad, f"{x0[i]:.6f}", f"{x1[i]:.6f}",
             f"{100*abs(x1[i]-GERCEK[i])/GERCEK[i]:.2f}"]))
print(f"\ngirdideki tek bir 0,01 m3 degisiklik ilk basamagin fiyatini yuzde "
      f"{100*abs(x1[0]-GERCEK[0])/GERCEK[0]:.2f} oynatiyor; hesapta hicbir hata yok")

# Pivotlama karari. Ilk katsayi kuculdukce pivotsuz eleme bozuluyor; deger burada
# gercek bir okuma degil, algoritmanin davranisini olcen bir sondadir.
v = gen([18, 18, 18, 14])
print("\n" + v(["ilk katsayi", "pivotlu artik", "pivotsuz artik", "islem sayisi"]))
for eps in (1e-2, 1e-6, 1e-10, 1e-14, 0.0):
    T = [eps, 15.00, 5.00, 10.02, 15.04, 5.01, 8.00, 20.00, 12.00]
    bt = carpMV(T, GERCEK, 3)
    artik = lambda xx: max(abs(sum(T[i*3+j] * xx[j] for j in range(3)) - bt[i])
                           for i in range(3))
    ELE = 0
    xp = coz_eleme(T, bt, 3, True)
    n_islem = ELE
    try:
        xn = coz_eleme(T, bt, 3, False)
        pa = f"{artik(xn):.3e}"
    except ZeroDivisionError:
        pa = "cozum yok"
    print(v([f"{eps:g}", f"{artik(xp):.3e}", pa, n_islem]))
print("\npivotlama islem sayisini degistirmiyor; degistirdigi sey artigin buyuklugu")

katsayi matrisinin determinanti 0.8000

basamak            cozulen fiyat   0,01 m3 sonrasi   sapma yuzde
10 m3                  12.500000          6.239082         50.09
25 m3                  18.750000         25.001560         33.34
40 m3                  27.400000         21.154679         22.79

girdideki tek bir 0,01 m3 degisiklik ilk basamagin fiyatini yuzde 50.09 oynatiyor; hesapta hicbir hata yok

ilk katsayi            pivotlu artik    pivotsuz artik  islem sayisi
0.01                       0.000e+00         8.538e-11            14
1e-06                      0.000e+00         5.687e-07            14
1e-10                      0.000e+00         4.120e-03            14
1e-14                      0.000e+00         7.237e+01            14
0                          0.000e+00         cozum yok            14

pivotlama islem sayisini degistirmiyor; degistirdigi sey artigin buyuklugu

Üst tablo hesabın dışındaki bir duyarlılığı ölçüyor. İlk iki abone grubunun tüketim profili birbirine çok yakın; katsayı matrisinin determinantı 0,8 gibi küçük bir sayı. Bu sistemde girdiye sayaç çözünürlüğü kadar, yani 0,01 m³ eklenince ilk basamağın birim fiyatı 12,50’den 6,24’e düşer, yüzde 50,09 sapma. Diğer iki basamak da yüzde 33 ve yüzde 23 oynar. Hesapta hiçbir hata yoktur; her iki sonuç da kendi girdisinin doğru çözümüdür. Oynayan şey girdinin kendisidir ve girdi zaten ölçümle geldiği için 0,01 m³’lük belirsizliği taşır.

Bu, konunun en önemli sınırıdır: iki ölçüm arasındaki fark sayaçtan okunamayacak kadar küçükken sonuç yarı yarıya değişiyorsa, o sonuç raporlanabilir bir sayı değildir. Bir çözüm işlevinin verdiği değer doğru olabilir ve aynı zamanda anlamsız olabilir; ikisini ayıran şey girdiyi oynatıp sonucun ne kadar hareket ettiğine bakmaktır.

Alt tablo ise soyutlamanın gizlediği kararı gösteriyor. Pivotlama, elemenin her adımında en büyük katsayıyı öne almaktır ve işlem sayısını hiç değiştirmez: beş satırın hepsinde 14. Değiştirdiği şey artıktır. İlk katsayı 0,01 iken pivotsuz elemenin artığı 8,538e-11 ile eşiğin altındadır ve iki yol ayırt edilemez. Katsayı küçüldükçe artık büyür: 1e-10’da 4,120e-03, 1e-14’te 7,237e+01 — yani sonuç artık denklemi hiç sağlamaz. Katsayı sıfır olduğunda pivotsuz eleme çözüm bile üretemez, pivotlu eleme aynı 14 işlemle doğru sonucu verir. Bir çözüm işlevini çağırırken pivotlamanın açık olup olmadığı yazılmıyorsa, artığın büyüklüğü hakkında hiçbir şey iddia edilemez.

Özet

• Matris çarpımında soyutlama işlem sayısını değiştirmez: 11.340 çarpma iki yazımda da aynıdır; çağrı yerindeki satır 13’ten 2’ye iner ve 26.460 elle dizin hesabı ortadan kalkar.
• Çözümde kazanç bir algoritma seçimidir: kofaktör açılımı ile eleme n = 4’e kadar denk, n = 8’de 309 kat, n = 12’de 823.059.744’e karşı 704 işlemle 1.169.119 kat ayrışır.
• Elemenin çözümü denklemi sağlar: n = 12’de en büyük artık 2,66e-15 ve 1e-9 eşiğinin çok altındadır.
• Pivotlama işlem sayısını değiştirmez (14’te sabit), artığı değiştirir: ilk katsayı küçüldükçe pivotsuz artık 8,538e-11’den 7,237e+01’e çıkar, katsayı sıfırken çözüm hiç üretilmez.
• Kötü koşullanmış bir tarife sisteminde (determinant 0,8) girdiye sayaç çözünürlüğü kadar 0,01 m³ eklenince birim fiyatlar yüzde 50,09, 33,34 ve 22,79 sapar; hesapta hata yoktur.

Sonraki Adım

Beş derste sayısal hesabın yapısı kuruldu ve her adımda iki sayı yan yana durdu. Ortam sabitlendiğinde defter 17 adımın 17’sinde aynı sonucu verdi, dizi arayüzü aynı işi 22 satır yerine 2 satırda ve 188.864 bayt yerine 30.320 baytta yaptı, vektörleştirme satırı beşte bire indirirken geçişi üçe katladı, yayılım kurulmayan diziyle 30.320 bayt kazandırırken uyumsuz bir biçimde 1.586.340 öğeyi sessizce yanlış hesapladı ve çözüm işlevi 1.169.119 katlık bir işlem farkını tek bir çağrının arkasına aldı.

Sayılar hızlandı, ama bu beş dersin bütün kod bloklarında tekrarlanan bir şey var: hangi sütunun ne olduğunu söyleyen tek şey koddur. OKUMA[i * DONEM + d] ifadesi ikinci boyutun dönem olduğunu bilen bir insan olmadan hiçbir anlam taşımaz; TARIFE matrisinin satırlarının dönem, sütunlarının basamak olduğu hiçbir yerde yazılı değildir; 581 boş hücrenin hangileri olduğu diziden okunamaz. Dizinin etiketi yoktur. Sonraki konu, veri çerçeveleri, tam bu eksiği ele alır: etiket eklendiğinde hangi işler kendiliğinden doğru olur ve etiketin üstlendiği hizalama hangi kararı görünmez kılar.