রুঙ্গের ফেনোমেনন ও পিসওয়াইজ ইন্টারপোলেশন

১ · রুঙ্গের ফেনোমেনন কী

L16-L17-এ আমরা ধরে নিয়েছিলাম বেশি ডেটা পয়েন্ট মানেই স্বাভাবিকভাবে বেশি সঠিক ইন্টারপোলেশন। কিন্তু রুঙ্গের ফেনোমেননRunge's Phenomenonএকটি সুপরিচিত ঘটনা যেখানে সমান-ব্যবধানের নোডে উঁচু-ডিগ্রি পলিনোমিয়াল ইন্টারপোলেশনের এরর ইন্টারভালের কেন্দ্রে কমলেও কিনারায় নাটকীয়ভাবে বাড়তে থাকে — ডিগ্রি যত বাড়ে, কিনারার দোলন তত তীব্র হয়। (Runge's phenomenon, ১৯০১ সালে কার্ল রুঙ্গে আবিষ্কৃত) এই ধারণাকে ভুল প্রমাণ করে একটি নির্দিষ্ট শ্রেণীর ফাংশনের জন্য — বিশেষত যেগুলোর গ্রাফে তীক্ষ্ণ পরিবর্তন (steep curvature) আছে।

ক্লাসিক উদাহরণ হলো:

এই ফাংশনটি x = 0-এর কাছে তীক্ষ্ণভাবে বেঁকে যায় (একটি সরু "চূড়া"), আর ±1-এর কাছে অনেক সমতল। যখন এই ফাংশনকে সমান-ব্যবধানের নোডে স্যাম্পল করে একটি উঁচু-ডিগ্রি পলিনোমিয়াল ফিট করা হয়, পলিনোমিয়ালটি কেন্দ্রে ভালো ফিট করলেও কিনারার কাছে বন্য দোলন (wild oscillation) শুরু করে।

২ · একটি সত্যিকারের ডেমো — এরর বাড়তে দেখা

নিচের কোড সেলে n = 5, 11, 15, 21টি সমান-ব্যবধানের নোডে (অর্থাৎ ডিগ্রি 4, 10, 14, 20-এর পলিনোমিয়াল) লাগ্রাঞ্জ ইন্টারপোলেশন করে দুটো কিনারার-কাছের বিন্দুতে (x = 0.95, 0.98) এবং একটি কেন্দ্রের বিন্দুতে (x = 0.0) পরম এরর গণনা করা হয়েছে।

def runge(x):
    return 1.0 / (1.0 + 25.0 * x**2)

def lagrange_interpolate(xs, ys, x):
    total = 0.0
    n = len(xs)
    for i in range(n):
        term = ys[i]
        for j in range(n):
            if j != i:
                term *= (x - xs[j]) / (xs[i] - xs[j])
        total += term
    return total

def equally_spaced(n, a=-1.0, b=1.0):
    return [a + i*(b-a)/(n-1) for i in range(n)]

for n in [5, 11, 15, 21]:
    xs = equally_spaced(n)
    ys = [runge(x) for x in xs]
    print(f"n = {n} নোড (ডিগ্রি {n-1} পলিনোমিয়াল):")
    for xt in [0.95, 0.98]:
        p = lagrange_interpolate(xs, ys, xt)
        true_v = runge(xt)
        err = abs(p - true_v)
        print(f"  x={xt}: P(x)={p:.6f}  true={true_v:.6f}  এরর={err:.6f}")
    xt = 0.0
    p = lagrange_interpolate(xs, ys, xt)
    true_v = runge(xt)
    print(f"  x={xt}: P(x)={p:.6f}  true={true_v:.6f}  এরর={abs(p-true_v):.6f}  (কেন্দ্র, তুলনার জন্য)")
    print()

৩ · সমাধান — পিসওয়াইজ-লিনিয়ার ইন্টারপোলেশন

সমস্যাটি একক উঁচু-ডিগ্রি পলিনোমিয়ালে — পুরো ইন্টারভাল জুড়ে একটিমাত্র বাঁকানো কার্ভ জোর করে ফিট করানো। পিসওয়াইজ ইন্টারপোলেশন ভিন্ন কৌশল নেয়: পুরো ইন্টারভালকে ছোট ছোট সাব-ইন্টারভালে ভাগ করে প্রতিটিতে একটি সরল (নিচু-ডিগ্রি) ফাংশন ফিট করা — সবচেয়ে সহজ সংস্করণ হলো প্রতিটি দুই পাশের নোডের মধ্যে একটি সরলরেখা টানা (পিসওয়াইজ-লিনিয়ার)।

def piecewise_linear(xs, ys, x):
    n = len(xs)
    for i in range(n-1):
        if xs[i] <= x <= xs[i+1]:
            t = (x - xs[i]) / (xs[i+1] - xs[i])
            return ys[i] + t*(ys[i+1]-ys[i])
    return None

n_pw = 21
xs_pw = equally_spaced(n_pw)
ys_pw = [runge(x) for x in xs_pw]

print(f"পিসওয়াইজ-লিনিয়ার ইন্টারপোলেশন, n = {n_pw} পয়েন্ট (উপরের একই n=21 ডেটাসেট, কিন্তু ডিগ্রি-২০ পলিনোমিয়ালের বদলে সরল রেখাংশ):")
for xt in [0.95, 0.98, 0.0]:
    p = piecewise_linear(xs_pw, ys_pw, xt)
    true_v = runge(xt)
    err = abs(p - true_v)
    print(f"  x={xt}: P_linear(x)={p:.6f}  true={true_v:.6f}  এরর={err:.6f}")