QR অ্যালগরিদম

১ · QR ডিকম্পোজিশন — সংক্ষিপ্ত রিমাইন্ডার

যেকোনো ম্যাট্রিক্স A-কে দুটি ম্যাট্রিক্সের গুণফলে লেখা যায়: A = QR, যেখানে Q একটি অর্থোগোনাল ম্যাট্রিক্স (এর কলামগুলো একে অপরের সাথে লম্ব এবং প্রতিটির দৈর্ঘ্য ১) এবং R একটি আপার-ট্রায়াঙ্গুলার ম্যাট্রিক্স। এটি বের করার একটি সহজ, ক্লাসিক পদ্ধতি হলো Gram-Schmidt প্রক্রিয়া — A-এর কলামগুলোকে একে একে নিয়ে, আগের অর্থোগোনালাইজড কলামগুলোর দিকে থাকা অংশ বিয়োগ করে, বাকি অংশটুকু নরমালাইজ করে Q-এর পরবর্তী কলাম তৈরি করা হয় — আর সেই "কতটুকু বিয়োগ হলো ও নরমালাইজ হলো" তথ্যগুলোই R-এর এন্ট্রি।

২ · QR অ্যালগরিদমের মূল ইটারেশন

QR অ্যালগরিদমের ধারণাটি প্রায় জাদুর মতো সহজ: A₀ = A দিয়ে শুরু করে, প্রতি ধাপে —

$$A_k = Q_k R_k \qquad\text{(QR ডিকম্পোজ করো)}$$

$$A_{k+1} = R_k Q_k \qquad\text{(গুণের ক্রম উল্টে নতুন ম্যাট্রিক্স বানাও)}$$

লক্ষ্য করুন A_{k+1} = R_k Q_k = Q_k^{-1} (Q_k R_k) Q_k = Q_k^{-1} A_k Q_k — অর্থাৎ A_{k+1} সবসময় A_k-এর একটি সিমিলারিটি ট্রান্সফর্মেশন (Q অর্থোগোনাল হওয়ায় Q⁻¹ = Qᵀ)। সিমিলারিটি ট্রান্সফর্মেশন আইগেনভ্যালু পরিবর্তন করে না — শুধু ম্যাট্রিক্সের "রূপ" বদলায়। কিছু শর্তের অধীনে (যেমন সব আইগেনভ্যালুর ম্যাগনিটিউড ভিন্ন), এই ইটারেশন বার বার প্রয়োগ করলে ম্যাট্রিক্স একটি আপার-ট্রায়াঙ্গুলার (বা প্রায়-ডায়াগোনাল) রূপে কনভার্জ করে, যার ডায়াগোনাল এন্ট্রিগুলোই মূল ম্যাট্রিক্সের আইগেনভ্যালু — ম্যাগনিটিউড অনুযায়ী সাজানো।

৩ · হাতে-কলমে বাস্তবায়ন — একই ম্যাট্রিক্সে সত্যিকারের কনভারজেন্স

L38-L39-এর একই ম্যাট্রিক্স ব্যবহার করা হচ্ছে, যাতে ফলাফল সরাসরি তুলনীয় হয় — প্রকৃত আইগেনভ্যালু ইতিমধ্যে জানা: প্রায় ৫.২১৪৩২, ২.৪৬০৮১, ও ১.৩২৪৮৭ (L38-এ পাওয়ার মেথড দিয়ে, L39-এ শিফটেড ইনভার্স পাওয়ার মেথড দিয়ে):

$$A_0 = \begin{bmatrix} 4 & 1 & 1 \\ 1 & 3 & 1 \\ 1 & 1 & 2 \end{bmatrix}$$

import math

A = [
    [4.0, 1.0, 1.0],
    [1.0, 3.0, 1.0],
    [1.0, 1.0, 2.0],
]
n = 3

def get_col(M, j):
    return [M[i][j] for i in range(len(M))]

def dot(u, v):
    return sum(a * b for a, b in zip(u, v))

def norm(v):
    return math.sqrt(dot(v, v))

def gram_schmidt_qr(M):
    # সরলীকৃত, ইলাস্ট্রেটিভ Gram-Schmidt QR ডিকম্পোজিশন -- হাতে-লেখা, কোনো লাইব্রেরি নেই
    n = len(M)
    cols = [get_col(M, j) for j in range(n)]
    Q_cols = []
    R = [[0.0] * n for _ in range(n)]
    for j in range(n):
        v = cols[j][:]
        for i in range(j):
            R[i][j] = dot(Q_cols[i], cols[j])
            v = [v[k] - R[i][j] * Q_cols[i][k] for k in range(n)]
        R[j][j] = norm(v)
        Q_cols.append([x / R[j][j] for x in v])
    Q = [[Q_cols[j][i] for j in range(n)] for i in range(n)]
    return Q, R

def matmul(M1, M2):
    rows, mid, cols = len(M1), len(M2), len(M2[0])
    result = [[0.0] * cols for _ in range(rows)]
    for i in range(rows):
        for j in range(cols):
            result[i][j] = sum(M1[i][k] * M2[k][j] for k in range(mid))
    return result

Ak = [row[:] for row in A]
print(f"শুরুর ডায়াগোনাল: {[round(Ak[i][i], 6) for i in range(n)]}")
print()

for it in range(1, 13):
    Q, R = gram_schmidt_qr(Ak)
    Ak = matmul(R, Q)               # ক্রম উল্টে A_(k+1) = R*Q
    diag = [round(Ak[i][i], 6) for i in range(n)]
    off_diag_max = max(abs(Ak[i][j]) for i in range(n) for j in range(n) if i != j)
    print(f"ইটার {it:2d}: ডায়াগোনাল = {diag}   সর্বোচ্চ অফ-ডায়াগোনাল = {off_diag_max:.6f}")

print()
print("চূড়ান্ত ম্যাট্রিক্স:")
for row in Ak:
    print([round(x, 6) for x in row])

৪ · কেন এটি একবারে সবগুলো আইগেনভ্যালু দেয়

পাওয়ার মেথড শুধু একটি আইগেন-দিকের "প্রাধান্য" ব্যবহার করে — কিন্তু QR অ্যালগরিদম প্রতি ধাপে পুরো স্পেস-এর একটি অর্থোগোনাল বেসিসকে পুনর্গঠন করে, যেখানে প্রতিটি কলাম একসাথে তার নিজস্ব আইগেন-দিকের দিকে ঘুরতে থাকে — অনেকটা যেন nটি পাওয়ার মেথড একসাথে, সমান্তরালে চলছে, কিন্তু প্রতি ধাপে Gram-Schmidt দিয়ে একে অপরের সাথে অর্থোগোনাল রাখা হচ্ছে যাতে সবাই একই ডমিন্যান্ট দিকে "ধসে" না পড়ে। এই কারণেই উপরের আউটপুটে ডায়াগোনালের তিনটি মান একসাথে নিজ নিজ প্রকৃত আইগেনভ্যালুর দিকে কনভার্জ করছে, এবং অফ-ডায়াগোনাল এন্ট্রি ধীরে ধীরে শূন্যের দিকে যাচ্ছে।