গসিয়ান এলিমিনেশন

১ · রৈখিক সমীকরণ সিস্টেম ও ম্যাট্রিক্স রূপ

বহু বাস্তব-বিশ্বের সমস্যা — বৈদ্যুতিক সার্কিট বিশ্লেষণ, স্ট্রাকচারাল ইঞ্জিনিয়ারিং, ইকোনমিক মডেলিং, কম্পিউটার গ্রাফিক্স — শেষ পর্যন্ত এক গুচ্ছ রৈখিক সমীকরণএমন সমীকরণ যেখানে প্রতিটি অজানা রাশি (variable) শুধু ধ্রুবক দিয়ে গুণিত অবস্থায় থাকে — কোনো বর্গ, ঘাত, বা গুণফল আকারে নয়। সমাধানে পরিণত হয়। যেমন:

এই ধরনের সিস্টেমকে সংক্ষেপে ম্যাট্রিক্স-ভেক্টর আকারে লেখা হয় Ax = b, যেখানে A হলো সহগ (coefficient) ম্যাট্রিক্স, x অজানা রাশিগুলোর ভেক্টর, এবং b ডান-পক্ষের মানগুলোর ভেক্টর। এই কোর্সে (এবং Pyodide স্যান্ডবক্সে) আমরা A-কে একটি Python list of listস হিসেবে উপস্থাপন করি — NumPy ব্যবহার করা হয় না, প্রতিটি অপারেশন হাতে-লেখা। ../math-for-ai/index.html কোর্স ম্যাট্রিক্স ও ভেক্টর কী তা গাণিতিক অবজেক্ট হিসেবে ব্যাখ্যা করে — এখানে আমরা সেগুলো কম্পিউটারে বাস্তবে কীভাবে গণনা করা হয় তা দেখাই।

২ · ফরোয়ার্ড এলিমিনেশন — Upper-Triangular রূপে রূপান্তর

গসিয়ান এলিমিনেশনের মূল ধারণা হলো এক সারি থেকে অন্য সারির উপযুক্ত গুণিতক বিয়োগ করে ধীরে ধীরে প্রতিটি কলামের নিচের অংশ শূন্য করে ফেলা। যদি k-তম ধাপে M[k][k] হলো পিভোট (pivot), তাহলে প্রতিটি নিচের সারি i-এর জন্য একটি factor বের করা হয়:

এই প্রক্রিয়া প্রতিটি কলামের জন্য পুনরাবৃত্তি করলে ম্যাট্রিক্সটি ধীরে ধীরে একটি upper-triangular রূপে চলে আসে — মূল ডায়াগোনালের নিচের সবকিছু শূন্য। (L12-এ দেখা যাবে M[k][k] শূন্যের কাছাকাছি হলে কী সমস্যা হয়, এবং কেন পিভোটিং প্রয়োজন।)

৩ · একটি সত্যিকারের ডেমো — 4x4 সিস্টেম সমাধান

নিচে একটি 4x4 সিস্টেম Ax = b হাতে-লেখা গসিয়ান এলিমিনেশন দিয়ে সমাধান করা হয়েছে, এবং তারপর পাওয়া x মূল সমীকরণে ফিরে বসিয়ে প্রতিটি সমীকরণের অবশিষ্টাংশ (residual) — অর্থাৎ Ax - b — গণনা করে দেখানো হয়েছে এটি প্রকৃতপক্ষে কতটা শূন্যের কাছাকাছি।

def gaussian_eliminate_and_solve(A, b):
    n = len(A)
    # augmented ম্যাট্রিক্স তৈরি (caller-এর A, b অপরিবর্তিত থাকে)
    M = [row[:] + [b[i]] for i, row in enumerate(A)]

    # ফরোয়ার্ড এলিমিনেশন
    for k in range(n - 1):
        for i in range(k + 1, n):
            factor = M[i][k] / M[k][k]
            for j in range(k, n + 1):
                M[i][j] -= factor * M[k][j]

    # ব্যাক-সাবস্টিটিউশন
    x = [0.0] * n
    for i in range(n - 1, -1, -1):
        s = M[i][n]
        for j in range(i + 1, n):
            s -= M[i][j] * x[j]
        x[i] = s / M[i][i]
    return x, M

A = [
    [3.0,  2.0, -1.0,  4.0],
    [2.0,  3.0,  3.0, -2.0],
    [1.0, -1.0,  4.0,  1.0],
    [4.0,  2.0, -1.0,  3.0],
]
b = [12.0, 5.0, 8.0, 10.0]

x, M = gaussian_eliminate_and_solve(A, b)
print("সমাধান x =", [round(v, 6) for v in x])

print()
print("যাচাই -- মূল সমীকরণে বসিয়ে অবশিষ্টাংশ (residual) দেখা:")
for i in range(len(A)):
    lhs = sum(A[i][j] * x[j] for j in range(len(A)))
    residual = lhs - b[i]
    print(f"সমীকরণ {i+1}: গণনাকৃত LHS = {lhs:.10f}   b = {b[i]:.6f}   residual = {residual:.2e}")

সমাধান x = [0.414634, 1.365854, 1.634146, 2.414634]

যাচাই -- মূল সমীকরণে বসিয়ে অবশিষ্টাংশ (residual) দেখা:
সমীকরণ 1: গণনাকৃত LHS = 12.0000000000   b = 12.000000   residual = 0.00e+00
সমীকরণ 2: গণনাকৃত LHS = 5.0000000000   b = 5.000000   residual = -2.66e-15
সমীকরণ 3: গণনাকৃত LHS = 8.0000000000   b = 8.000000   residual = -8.88e-16
সমীকরণ 4: গণনাকৃত LHS = 10.0000000000   b = 10.000000   residual = 0.00e+00