ফিক্সড-পয়েন্ট ইটারেশন

১ · x = g(x) আকারে পুনর্লিখন

ফিক্সড-পয়েন্ট ইটারেশনFixed-point iterationএকটি সমীকরণ f(x) = 0-কে x = g(x) আকারে পুনর্লিখন করে x_{n+1} = g(x_n) সূত্র বারবার প্রয়োগ করে রুট খোঁজার মেথড — যেই বিন্দুতে x = g(x), তাকে g-এর "ফিক্সড পয়েন্ট" বলা হয়। বাইসেকশন (L05) শুধু ফাংশনের চিহ্ন ব্যবহার করত এবং প্রতি ধাপে একটি ব্র্যাকেট প্রয়োজন ছিল। ফিক্সড-পয়েন্ট ইটারেশন সম্পূর্ণ ভিন্ন পথ নেয়: সমীকরণ f(x) = 0-কে বীজগাণিতিকভাবে x = g(x) আকারে সাজিয়ে, একটি প্রাথমিক অনুমান x₀ থেকে শুরু করে বারবার x_{n+1} = g(x_n) গণনা করা হয়। যেই বিন্দুতে সিকোয়েন্সটি স্থির হয়ে যায় (x = g(x)), সেটাই ফাংশনের ফিক্সড পয়েন্ট — এবং একটু বীজগণিত করলে দেখা যায় সেটাই মূল সমীকরণের রুট।

একই সমীকরণকে একাধিকভাবে x = g(x) আকারে লেখা যায়। L05-এর সমীকরণ f(x) = x³ - x - 2 = 0 নিয়ে দুটি ভিন্ন পুনর্লিখন বিবেচনা করা যাক:

$$g_1(x) = \sqrt[3]{x + 2} \qquad \text{এবং} \qquad g_2(x) = x^3 - 2$$

দুটোই বীজগাণিতিকভাবে সঠিক — উভয়ের ফিক্সড পয়েন্টেই মূল সমীকরণের রুট। কিন্তু নিচে দেখা যাবে একটি চমৎকারভাবে কনভার্জ করে, আর অন্যটি ভয়াবহভাবে ডাইভার্জ করে — শুধু বীজগণিতে সঠিক হওয়াই যথেষ্ট নয়।

২ · কনভার্জিং উদাহরণ — g₁(x) = (x+2)^(1/3)

নিচের কোড সেলে x₀ = 1.0 থেকে শুরু করে g₁ দিয়ে ইটারেট করা হয়েছে, এবং প্রতিবার L05-এর রেফারেন্স মূল 1.5213797068-এর বিপরীতে প্রকৃত এরর দেখানো হয়েছে।

reference_root = 1.5213797068045678  # L05-এ বের করা x**3 - x - 2 = 0-এর মূল

def g_conv(x):
    return (x + 2) ** (1 / 3)

print("=== কনভার্জিং: g(x) = (x+2)^(1/3) ===")
x = 1.0
print(f"{'ইটার':>4} {'x':>14} {'এরর':>14}")
for i in range(1, 11):
    x_new = g_conv(x)
    err = abs(x_new - reference_root)
    print(f"{i:4d} {x_new:14.8f} {err:14.10f}")
    x = x_new

# ফিক্সড পয়েন্টের কাছে ঢাল (derivative) পরীক্ষা
def gprime_conv(x):
    return (1 / 3) * (x + 2) ** (-2 / 3)

print()
print(f"g'(root) = {gprime_conv(reference_root):.6f}   (|g'(root)| < 1 → কনভার্জ করবে)")

৩ · ডাইভার্জিং উদাহরণ — g₂(x) = x³ - 2

এবার একই মূল সমীকরণের একটি ভিন্ন, সমান বৈধ পুনর্লিখন ব্যবহার করা যাক। এখানে শুরুর বিন্দু x₀ = 1.4 — রুটের (1.5214) খুবই কাছাকাছি, তারপরও কী হয় দেখা যাক। যেহেতু এটি খুব দ্রুত অত্যন্ত বড় মানে পৌঁছাতে পারে, কোডে একটি সেফটি-গার্ড (magnitude 10¹²-এর বেশি হলে থামা) রাখা হয়েছে যাতে সেল ক্র্যাশ বা হ্যাং না করে।

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

print("=== ডাইভার্জিং: g(x) = x^3 - 2 ===")
x = 1.4  # রুটের খুব কাছাকাছি শুরু, তবুও...
print(f"{'ইটার':>4} {'x':>20}")
for i in range(1, 11):
    try:
        x_new = g_div(x)
    except OverflowError:
        print(f"{i:4d}  OverflowError -- x অসীমের দিকে ডাইভার্জ করেছে")
        break
    print(f"{i:4d} {x_new:20.4f}")
    x = x_new
    if abs(x) > 1e12:
        print("      ... মান 1e12 ছাড়িয়ে গেছে, স্পষ্টভাবে ডাইভার্জ করছে, থামানো হলো")
        break

def gprime_div(x):
    return 3 * x ** 2

print()
print(f"g'(root) = {gprime_div(1.5213797068045678):.4f}   (|g'(root)| > 1 → ডাইভার্জ করবে)")

৪ · কনভারজেন্স শর্ত — কেন |g'(x)| < 1

এই আচরণটি কাকতালীয় নয় — এর পেছনে একটি সরল ব্যাখ্যা আছে। যদি x* ফিক্সড পয়েন্ট হয় (x* = g(x*)) এবং e_n = x_n - x* এররকে সংজ্ঞায়িত করি, তাহলে টেইলর সম্প্রসারণ (Taylor expansion) ব্যবহার করে দেখানো যায়:

$$e_{n+1} \approx g'(x^*) \cdot e_n$$

অর্থাৎ প্রতি ধাপে এরর প্রায় g'(x*) গুণ হয়ে যায়। যদি |g'(x*)| < 1 হয়, তাহলে এরর ক্রমাগত ছোট হতে থাকবে (কনভার্জ করবে); যদি |g'(x*)| > 1 হয়, তাহলে এরর ক্রমাগত বড় হতে থাকবে (ডাইভার্জ করবে) — ঠিক যেমনটা উপরের দুটি কোড সেলে সত্যিকারের গণনায় দেখা গেল (0.1440 বনাম 6.9438)।