রুট-ফাইন্ডিং সমস্যা ও বাইসেকশন মেথড

১ · রুট-ফাইন্ডিং সমস্যা কী

রুট-ফাইন্ডিং সমস্যাRoot-finding problemএকটি ফাংশন f(x) দেওয়া থাকলে, এমন x মান (মূল বা root) খুঁজে বের করা যেখানে f(x) = 0। হলো নিউমেরিক্যাল অ্যানালাইসিসের সবচেয়ে মৌলিক ও ব্যাপক-প্রয়োগযোগ্য সমস্যাগুলোর একটি: একটি ফাংশন f(x) দেওয়া থাকলে, এমন এক বা একাধিক x মান বের করা যেখানে f(x) = 0। এই ফর্মটি বিস্ময়কর রকম সাধারণ — f(x) = x - cos(x) লিখলে L01-এর সমীকরণ x = cos(x)-ও একটি রুট-ফাইন্ডিং সমস্যা, আর যেকোনো সমীকরণ g(x) = h(x)-কে f(x) = g(x) - h(x) = 0 আকারে লেখা যায়।

এই মডিউল (M2) জুড়ে আমরা একই ধরনের সমস্যা — একটি একক-চলকের অ-লিনিয়ার সমীকরণ সমাধান — বিভিন্ন কৌশলে সমাধান করব: বাইসেকশন (এই পাঠ), ফিক্সড-পয়েন্ট ইটারেশন (L06), নিউটন-রাফসন (L07), সেকেন্ট ও রেগুলা ফালসি (L08), এবং সবশেষে L09-এ সবগুলো মেথড একসাথে তুলনা করা হবে।

২ · ইন্টারমিডিয়েট ভ্যালু থিওরেম — বাইসেকশনের ভিত্তি

বাইসেকশন মেথড একটি একদম সরল কিন্তু শক্তিশালী গাণিতিক সত্যের উপর দাঁড়িয়ে আছে — ইন্টারমিডিয়েট ভ্যালু থিওরেমIntermediate Value Theorem (IVT)যদি f একটি কন্টিনিউয়াস ফাংশন হয় এবং [a, b]-এর উপর f(a) ও f(b)-এর চিহ্ন বিপরীত হয়, তাহলে (a, b)-এর মধ্যে অন্তত একটি বিন্দু c থাকবে যেখানে f(c) = 0।। সহজ কথায়: যদি একটি কন্টিনিউয়াস (অবিচ্ছিন্ন) ফাংশন একটি ইন্টারভালের এক প্রান্তে ঋণাত্মক এবং অন্য প্রান্তে ধনাত্মক হয়, তাহলে মাঝে কোথাও এটি অবশ্যই শূন্য হবে — কারণ একটি কন্টিনিউয়াস ফাংশন "লাফ দিয়ে" চিহ্ন পরিবর্তন করতে পারে না।

এই থিওরেমটি একটি অস্তিত্ব নিশ্চয়তা দেয় (রুট আছে), কিন্তু রুটটি ঠিক কোথায় তা বলে না। বাইসেকশন মেথড এই নিশ্চয়তাকে একটি অ্যালগরিদমে রূপান্তরিত করে: ইন্টারভালকে বারবার অর্ধেক করে, প্রতিবার চিহ্ন পরীক্ষা করে রুটটি যে অর্ধেকে আছে সেই দিকে "এগিয়ে যায়" — এভাবে ইন্টারভালটি ধীরে ধীরে রুটের চারপাশে সংকুচিত হতে থাকে।

৩ · একটি নতুন উদাহরণ — x³ - x - 2 = 0

L01-এ আমরা x = cos(x) সমাধান করেছিলাম। এই পাঠে ধারাবাহিকতা বজায় রেখে কিন্তু একটি নতুন সমীকরণ ব্যবহার করব যা এই পুরো M2 মডিউল জুড়ে (L06–L09-এ) বারবার ফিরে আসবে:

$$f(x) = x^3 - x - 2 = 0$$

প্রথমে একটি ব্র্যাকেট (bracket) বের করতে হবে যেখানে চিহ্ন বিপরীত। f(1) = 1 - 1 - 2 = -2 (ঋণাত্মক) এবং f(2) = 8 - 2 - 2 = 4 (ধনাত্মক) — তাই IVT অনুযায়ী 1 ও 2-এর মাঝে একটি রুট নিশ্চিতভাবে আছে। নিচের কোড সেলে বাইসেকশন মেথড দিয়ে এই রুটটি ধাপে ধাপে বের করা হয়েছে, প্রতিটি ইটারেশনে একটি অত্যন্ত নির্ভুল রেফারেন্স মূলের (২০০ ইটারেশনের বাইসেকশন দিয়ে আগেই গণনা করা) বিপরীতে প্রকৃত এরর দেখানো হয়েছে।

def f(x):
    return x**3 - x - 2

a, b = 1.0, 2.0
print(f"f({a}) = {f(a):.6f}   f({b}) = {f(b):.6f}")
print()

# অনেক বেশি ইটারেশন চালিয়ে একটি অত্যন্ত নির্ভুল রেফারেন্স মূল আগেই বের করা
ra, rb = 1.0, 2.0
for _ in range(200):
    m = (ra + rb) / 2
    if f(ra) * f(m) < 0:
        rb = m
    else:
        ra = m
reference_root = (ra + rb) / 2
print(f"রেফারেন্স মূল (২০০ ইটারেশন পর): {reference_root:.10f}")
print()

N = 12
a, b = 1.0, 2.0
print(f"{'ইটার':>4} {'x':>12} {'f(x)':>12} {'প্রস্থ':>10} {'এরর':>12}")
for i in range(1, N + 1):
    mid = (a + b) / 2
    fm = f(mid)
    if f(a) * fm < 0:
        b = mid
    else:
        a = mid
    err = abs(mid - reference_root)
    print(f"{i:4d} {mid:12.6f} {fm:+12.6f} {b - a:10.6f} {err:12.8f}")

final = (a + b) / 2
print()
print(f"{N} ইটারেশন পর চূড়ান্ত আনুমানিক মূল: {final:.6f}")
print(f"চূড়ান্ত প্রকৃত এরর: {abs(final - reference_root):.8f}")

৪ · এরর বাউন্ড ও লিনিয়ার কনভারজেন্স

বাইসেকশনের একটি বিশেষ শক্তি হলো এর এররের উপর একটি গাণিতিকভাবে প্রমাণযোগ্য উপরের সীমা আছে। যদি প্রাথমিক ইন্টারভাল প্রস্থ b - a হয়, তাহলে nটি ইটারেশন পর এরর সবসময় নিশ্চিতভাবে:

$$|x_n - x^*| \le \frac{b - a}{2^{n+1}}$$

এই সূত্রের মানে হলো আমরা আগে থেকেই বলতে পারি ঠিক কত ইটারেশন লাগবে একটি নির্দিষ্ট নির্ভুলতায় পৌঁছাতে — অন্য কোনো তথ্য ছাড়াই। যেহেতু এরর প্রতি ধাপে একটি স্থির অনুপাতে (অর্ধেক) কমে, একে লিনিয়ার কনভারজেন্সLinear convergenceযখন প্রতি ইটারেশনে এরর একটি স্থির অনুপাতে (এখানে ১/২) কমে যায় — কনভারজেন্স রেট সম্পর্কে বিস্তারিত L09-এ। বলা হয় — L01-এর বাইসেকশন ডেমোতেও এই একই বৈশিষ্ট্য দেখা গিয়েছিল।

৫ · বাইসেকশনের সীমাবদ্ধতা

এই সীমাবদ্ধতাগুলোই পরবর্তী পাঠগুলোর প্রেরণা: L06-এ ফিক্সড-পয়েন্ট ইটারেশন ব্র্যাকেট ছাড়াই কাজ করার চেষ্টা করবে, আর L07-এর নিউটন-রাফসন ফাংশনের ঢাল (derivative) ব্যবহার করে অনেক দ্রুত কনভার্জ করবে — যদিও প্রতিটি নতুন মেথডই নিজস্ব নতুন ঝুঁকি নিয়ে আসবে।