আইগেনভ্যালু সমস্যা ও পাওয়ার মেথড

১ · আইগেনভ্যালু ও আইগেনভেক্টর — সংক্ষিপ্ত রিমাইন্ডার

একটি আইগেনভেক্টরএকটি নন-জিরো ভেক্টর v যাকে ম্যাট্রিক্স A দিয়ে গুণ করলে দিক অপরিবর্তিত থাকে — শুধু দৈর্ঘ্য একটি স্কেলার λ (আইগেনভ্যালু) দিয়ে গুণ হয়। হলো এমন একটি নন-জিরো ভেক্টর v, যাকে n×n ম্যাট্রিক্স A দিয়ে গুণ করলে সরাসরি সেই একই ভেক্টরের একটি স্কেলড সংস্করণ পাওয়া যায়:

$$Av = \lambda v$$

এখানে λ (ল্যাম্বডা) হলো সেই আইগেনভেক্টরের সাথে যুক্ত আইগেনভ্যালু। জ্যামিতিকভাবে, বেশিরভাগ ভেক্টরকে A দিয়ে গুণ করলে তার দিক ও দৈর্ঘ্য দুটোই বদলে যায় — কিন্তু আইগেনভেক্টরগুলো হলো সেই বিশেষ দিকগুলো যেখানে A-এর প্রভাব শুধু একটি সরল স্কেলিং। একটি n×n ম্যাট্রিক্সের (সাধারণভাবে) nটি আইগেনভ্যালু থাকতে পারে। এই বস্তুগুলো কী এবং এগুলোর বীজগাণিতিক বৈশিষ্ট্য (characteristic polynomial দিয়ে হাতে বের করা ইত্যাদি) নিয়ে বিস্তারিত Math for AI & ML কোর্সে আছে — এই পাঠ ধরে নেয় সেই ভিত্তি আছে, এবং প্রশ্ন করে: বড় ম্যাট্রিক্সে এগুলো কম্পিউটারে বাস্তবে কীভাবে গণনা করা হয়? কারণ characteristic polynomial-এর মূল বের করা (যেমন L05-L09-এর রুট-ফাইন্ডিং মেথড দিয়ে) ৪×৪ বা তার চেয়ে বড় ম্যাট্রিক্সের জন্য ব্যবহারিকভাবে অসম্ভব হয়ে যায় — তাই M8-এর বাকি পাঠগুলো সম্পূর্ণ ভিন্ন, ইটারেটিভ পথ নেয়।

২ · পাওয়ার মেথডের ধারণা

পাওয়ার মেথড-এর মূল স্বজ্ঞা সহজ: যেকোনো শুরুর ভেক্টর v₀-কে, তাত্ত্বিকভাবে, ম্যাট্রিক্সের সব আইগেনভেক্টরের একটি মিশ্রণ (লিনিয়ার কম্বিনেশন) হিসেবে লেখা যায়। যখন এই ভেক্টরকে বার বার A দিয়ে গুণ করা হয়, প্রতিটি আইগেন-দিকের অবদান তার নিজস্ব আইগেনভ্যালুর ঘাত (power) অনুযায়ী বাড়ে বা কমে — আর যেহেতু ডমিন্যান্ট আইগেনভ্যালু λ₁ সবচেয়ে বড়, k বার গুণ করার পর সেই দিকটাই বাকিদের তুলনায় দ্রুততম বাড়ে এবং ধীরে ধীরে পুরো ভেক্টরে প্রাধান্য বিস্তার করে — এই থেকেই মেথডের নাম "পাওয়ার" (ঘাত) মেথড।

প্রতি ধাপে Av দ্রুত বিশাল বা ক্ষুদ্র হয়ে যেতে পারে (যদি |λ₁| > 1 বা < 1) — তাই প্রতি ইটারেশনের পর ভেক্টরকে তার নিজের নর্ম দিয়ে ভাগ করে নরমালাইজ করা হয়, যাতে দৈর্ঘ্য সবসময় ১ থাকে এবং দিকটাই একমাত্র যা পর্যবেক্ষণ করা হয়। আইগেনভ্যালুর আনুমান বের করতে প্রতি ইটারেশনে Rayleigh quotient ব্যবহার করা হয়:

$$\lambda_{\text{est}} = v^{\top} (A v)$$

যেখানে v ইতিমধ্যে নরমালাইজড (দৈর্ঘ্য ১)। এটি একটি সিমেট্রিক ম্যাট্রিক্সের জন্য বিশেষভাবে ভালো কাজ করে — নিচের ডেমোর ম্যাট্রিক্সটিও সিমেট্রিক।

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

নিচের ম্যাট্রিক্স A সিমেট্রিক এবং পজিটিভ-ডেফিনিট (M3/M14-এর কন্ডিশনিং আলোচনার মতো একটি সুন্দরভাবে-আচরণকারী ম্যাট্রিক্স):

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

নিচের কোড সেলে matvec (ম্যাট্রিক্স-ভেক্টর গুণ), norm ও normalize সম্পূর্ণ হাতে লেখা — কোনো NumPy নেই। শুরুর ভেক্টর v₀ = [1, 1, 1], এবং প্রতি ইটারেশনে Rayleigh quotient দিয়ে আইগেনভ্যালুর আনুমান ও আগের ইটারেশনের তুলনায় পরিবর্তনের পরিমাণ প্রিন্ট করা হয়েছে।

import math

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

def matvec(M, v):
    return [sum(M[i][j] * v[j] for j in range(len(v))) for i in range(len(M))]

def norm(v):
    return math.sqrt(sum(x * x for x in v))

def normalize(v):
    n = norm(v)
    return [x / n for x in v]

v = [1.0, 1.0, 1.0]     # শুরুর ভেক্টর -- যেকোনো নন-জিরো ভেক্টর দিয়ে শুরু করা যায়
prev_eig = None

print(f"{'ইটার':>4} | {'eigenvalue আনুমান':>20} | {'পরিবর্তন':>14}")
for i in range(1, 13):
    w = matvec(A, v)          # ধাপ ১: A দিয়ে গুণ
    v = normalize(w)          # ধাপ ২: নরমালাইজ (দৈর্ঘ্য ১ রাখা)
    Av = matvec(A, v)
    eig_est = sum(v[k] * Av[k] for k in range(len(v)))   # Rayleigh quotient
    if prev_eig is None:
        print(f"{i:4d} | {eig_est:20.10f} | {'--':>14}")
    else:
        print(f"{i:4d} | {eig_est:20.10f} | {abs(eig_est - prev_eig):14.10f}")
    prev_eig = eig_est

print()
print(f"চূড়ান্ত আইগেনভেক্টর: {[round(x, 6) for x in v]}")
print(f"চূড়ান্ত আইগেনভ্যালু আনুমান: {prev_eig:.10f}")

৪ · কনভারজেন্স রেট ও সীমাবদ্ধতা

পাওয়ার মেথডের কনভারজেন্স রেট নির্ভর করে দুটি সবচেয়ে বড় আইগেনভ্যালুর অনুপাতের উপর — যত ছোট |λ₂/λ₁|, তত দ্রুত কনভারজেন্স। উপরের ম্যাট্রিক্সের প্রকৃত আইগেনভ্যালুগুলো (পরের পাঠগুলোতে ভিন্ন মেথড দিয়ে নিশ্চিত হবে) প্রায় ৫.২১৪৩২, ২.৪৬০৮১, ও ১.৩২৪৮৭ — তাই |λ₂/λ₁| ≈ ২.৪৬০৮১/৫.২১৪৩২ ≈ ০.৪৭২। Rayleigh quotient ব্যবহার করলে (সিমেট্রিক ম্যাট্রিক্সের জন্য) এই অনুপাতের বর্গ অনুযায়ী এরর কমে (≈ ০.৪৭২² ≈ ০.২২৩) — উপরের আউটপুটে প্রতি ধাপে পরিবর্তনের অনুপাত পর্যবেক্ষণ করলে (যেমন ০.০০০৪৮৭/০.০০২২০০ ≈ ০.২২) এই তাত্ত্বিক হারের সাথে বাস্তব সংখ্যাগুলো সত্যিই মিলে যায়।