অ্যালগরিদম স্ট্যাবিলিটি, কন্ডিশনিং ও কনভারজেন্স

১ · কন্ডিশনিং — সমস্যার একটি ধর্ম

কন্ডিশনিংকন্ডিশনিং (Conditioning)একটি গাণিতিক সমস্যার নিজস্ব সংবেদনশীলতা — ইনপুটের ছোট পরিবর্তনে আউটপুট কতটা বদলায় তার পরিমাপ। এটি সমস্যার ধর্ম, ব্যবহৃত অ্যালগরিদমের নয়। বোঝায় একটি সমস্যা তার ইনপুটের ছোট পরিবর্তনের প্রতি কতটা সংবেদনশীল। একটি ভালো-কন্ডিশনড (well-conditioned) সমস্যায়, ইনপুটে একটি ছোট পরিবর্তন আউটপুটেও একটি ছোট, প্রত্যাশিত পরিবর্তন ঘটায়। একটি ইল-কন্ডিশনড (ill-conditioned) সমস্যায়, ইনপুটে একটি ক্ষুদ্র পরিবর্তন আউটপুটে বিশাল, অসামঞ্জস্যপূর্ণ পরিবর্তন ঘটাতে পারে — এবং এটি ঘটে এমনকি একটি গাণিতিকভাবে সম্পূর্ণ সঠিক অ্যালগরিদম ব্যবহার করলেও, কারণ সমস্যাটাই স্বভাবতই অস্থির।

একটি ধ্রুপদী উদাহরণ হলো দুটি রেখার ছেদবিন্দু বের করা। যদি দুটি রেখা একে অপরের প্রায় সমান্তরাল হয়, তাদের ছেদবিন্দু বের করা ইল-কন্ডিশনড — কারণ একটি রেখার ঢালে সামান্য পরিবর্তনও ছেদবিন্দুকে অনেক দূরে সরিয়ে দিতে পারে। নিচের কোড সেলে ঠিক এই ঘটনাটি একটি ২x২ রৈখিক সমীকরণ সিস্টেমে হাতে-লেখা Cramer's rule দিয়ে সরাসরি দেখানো হয়েছে।

২ · সত্যিকারের ডেমো — ভালো-কন্ডিশনড বনাম ইল-কন্ডিশনড ২x২ সিস্টেম

দুটি অজানা $x, y$-এর একটি $2 \times 2$ সিস্টেম:

$$a_{11}x + a_{12}y = b_1 \qquad a_{21}x + a_{22}y = b_2$$

Cramer's rule দিয়ে হাতে সমাধান করা যায়:

$$\text{det} = a_{11}a_{22} - a_{12}a_{21}, \qquad x = \frac{b_1 a_{22} - a_{12} b_2}{\text{det}}, \qquad y = \frac{a_{11} b_2 - b_1 a_{21}}{\text{det}}$$

নিচের কোড সেলে দুটি সিস্টেম সমাধান করা হয়েছে — একটি ভালো-কন্ডিশনড (2x + y = 5, x - 3y = -1) এবং একটি ইল-কন্ডিশনড, প্রায়-সিঙ্গুলার (x + y = 2, x + 1.0001y = 2.0001 — দুটি রেখা প্রায় সমান্তরাল)। প্রতিটি সিস্টেমে a₂₂-কে ঠিক 0.001 বাড়িয়ে দেখা হয়েছে সমাধান কতটা বদলায়।

def solve_2x2(a11, a12, a21, a22, b1, b2):
    det = a11 * a22 - a12 * a21
    x = (b1 * a22 - a12 * b2) / det
    y = (a11 * b2 - b1 * a21) / det
    return x, y, det

print("=== ভালো-কন্ডিশনড সিস্টেম ===")
print("2x + y = 5 ;  x - 3y = -1")
a11, a12, a21, a22, b1, b2 = 2.0, 1.0, 1.0, -3.0, 5.0, -1.0
x1, y1, det1 = solve_2x2(a11, a12, a21, a22, b1, b2)
print(f"মূল সমাধান: x = {x1:.6f}, y = {y1:.6f}   (det = {det1:.6f})")

x1p, y1p, det1p = solve_2x2(a11, a12, a21, a22 + 0.001, b1, b2)
print(f"a22 += 0.001 পর: x = {x1p:.6f}, y = {y1p:.6f}   (det = {det1p:.6f})")
dx1, dy1 = x1p - x1, y1p - y1
print(f"সমাধানের পরিবর্তন: dx = {dx1:.8f}, dy = {dy1:.8f}")
print()

print("=== ইল-কন্ডিশনড (প্রায়-সিঙ্গুলার) সিস্টেম ===")
print("x + y = 2 ;  x + 1.0001y = 2.0001   (দুই রেখা প্রায় সমান্তরাল)")
a11, a12, a21, a22, b1, b2 = 1.0, 1.0, 1.0, 1.0001, 2.0, 2.0001
x2, y2, det2 = solve_2x2(a11, a12, a21, a22, b1, b2)
print(f"মূল সমাধান: x = {x2:.6f}, y = {y2:.6f}   (det = {det2:.8f})")

x2p, y2p, det2p = solve_2x2(a11, a12, a21, a22 + 0.001, b1, b2)
print(f"a22 += 0.001 পর: x = {x2p:.6f}, y = {y2p:.6f}   (det = {det2p:.8f})")
dx2, dy2 = x2p - x2, y2p - y2
print(f"সমাধানের পরিবর্তন: dx = {dx2:.8f}, dy = {dy2:.8f}")
print()

shift1 = abs(dx1) + abs(dy1)
shift2 = abs(dx2) + abs(dy2)
print(f"ভালো-কন্ডিশনড মোট পরিবর্তন = {shift1:.8f}")
print(f"ইল-কন্ডিশনড মোট পরিবর্তন  = {shift2:.8f}")
print(f"সংবেদনশীলতার অনুপাত = {shift2 / shift1:.2f}x")

৩ · স্ট্যাবিলিটি — অ্যালগরিদমের একটি ধর্ম

কন্ডিশনিং সমস্যার নিজস্ব ধর্ম হলেও, স্ট্যাবিলিটি নির্ভর করে আমরা সমস্যাটি কীভাবে সমাধান করছি তার উপর। একটি ভালো-কন্ডিশনড সমস্যাও একটি অস্থিতিশীল (numerically unstable) অ্যালগরিদম দিয়ে সমাধান করলে ভুল ফলাফল দিতে পারে — কারণ অ্যালগরিদমটি নিজেই গণনার মাঝপথে রাউন্ড-অফ এরর বাড়িয়ে তোলে (যেমন L03-এর catastrophic cancellation বারবার ঘটলে)। বিপরীতে, একটি স্থিতিশীল অ্যালগরিদম গণনার সময় এরর জমতে দেয় না বা নিয়ন্ত্রণে রাখে। M3-এ (গসিয়ান এলিমিনেশন) আমরা দেখব কীভাবে পিভোটিং নামের একটি সহজ কৌশল একই গাণিতিক সমস্যাকে অনেক বেশি স্থিতিশীলভাবে সমাধান করতে সাহায্য করে (বিস্তারিত M3/L12-এ)।

৪ · কনভারজেন্স — ইটারেটিভ মেথডের পরিমাপ

এই কোর্সের বেশিরভাগ মেথডই ইটারেটিভ — অর্থাৎ এরা একটি প্রাথমিক অনুমান থেকে শুরু করে ধাপে ধাপে সঠিক উত্তরের কাছাকাছি পৌঁছায় (L01-এর বাইসেকশন ডেমো এর একটি উদাহরণ)। কনভারজেন্সকনভারজেন্স (Convergence)একটি ইটারেটিভ মেথডের ধারাবাহিক অনুমানগুলো সত্যিকারের উত্তরের কতটা কাছাকাছি এবং কত দ্রুত পৌঁছায় তার বর্ণনা। বর্ণনা করে এই প্রক্রিয়াটি কত দ্রুত এবং কতটা নির্ভরযোগ্যভাবে ঘটে। L01-এর বাইসেকশন মেথড লিনিয়ার কনভারজেন্স দেখিয়েছিল (প্রতি ধাপে ইন্টারভাল অর্ধেক)। M2-তে আমরা দেখব নিউটন-রাফসন মেথড কোয়াড্রেটিক কনভারজেন্স দেখায় (প্রতি ধাপে এরর মোটামুটি বর্গ হয়ে যায়) — অনেক দ্রুত, কিন্তু কখনো কখনো সম্পূর্ণ ব্যর্থও হতে পারে। কনভারজেন্স, কন্ডিশনিং ও স্ট্যাবিলিটি — এই তিনটি ধারণা একসাথে ঠিক করে একটি নিউমেরিক্যাল সমাধান বাস্তবে কতটা নির্ভরযোগ্য, এবং Module 1-এর বাকি অংশ জুড়ে এই তিনটিই ফিরে ফিরে আসবে।