কনভারজেন্স রেট ও সঠিক রুট-ফাইন্ডিং মেথড বাছাই

Convergence rates & choosing a root-finding method

৭ মিনিট পড়া মধ্যম · Intermediate Python কোডসহ সম্পূর্ণ বাংলায়

এক নজরে · TL;DR

এই পাঠ M2-এর সমাপনী — একই সমীকরণ x³ - x - 2 = 0-এ, একই টলারেন্স 10⁻⁸-এ, চারটি মেথড একসাথে একই কোড সেলে চালিয়ে প্রকৃত ইটারেশন-সংখ্যা তুলনা করা হয়েছে।
ফলাফল: বাইসেকশন ২৮, ফিক্সড-পয়েন্ট ১১, সেকেন্ট ৭, নিউটন-রাফসন ৫ ইটারেশন — কনভারজেন্স অর্ডারের তাত্ত্বিক ক্রম হুবহু প্রতিফলিত হয়েছে।
প্রতিটি মেথডের একটি নির্দিষ্ট কনভারজেন্স অর্ডার আছে — বাইসেকশন (১, লিনিয়ার), সেকেন্ট (~১.৬১৮), নিউটন-রাফসন (২, কোয়াড্রেটিক) — যা নির্ধারণ করে এরর প্রতি ধাপে কত দ্রুত কমে।
কিন্তু "সবচেয়ে দ্রুত" মানে "সবসময় সেরা" নয় — নির্ভরযোগ্যতা, ব্র্যাকেট প্রয়োজনীয়তা ও ডেরিভেটিভ প্রাপ্যতা বিবেচনা করে একটি সিদ্ধান্ত-কাঠামো এই পাঠে দেওয়া হয়েছে।

এই পাঠে যা শিখবেন

M2-এর চারটি মেথডকে একই কোড সেলে, একই সমীকরণে, একই টলারেন্সে চালিয়ে সরাসরি তুলনা করা
কনভারজেন্স অর্ডার কী এবং তা কীভাবে ইটারেশন-সংখ্যার পার্থক্য ব্যাখ্যা করে তা বোঝা
প্রতিটি মেথডের নির্ভরযোগ্যতা-বনাম-গতির ট্রেড-অফ একনজরে সংক্ষিপ্ত করা
একটি ব্যবহারিক সিদ্ধান্ত-কাঠামো ব্যবহার করে নতুন পরিস্থিতিতে সঠিক মেথড বেছে নেওয়া

১ · কনভারজেন্স অর্ডার — একটি দ্রুত পুনরালোচনা

M2-এর প্রতিটি পাঠে আমরা একটি নির্দিষ্ট ধরনের কনভারজেন্স আচরণ দেখেছি:

বাইসেকশন (L05)
লিনিয়ার কনভারজেন্স — প্রতি ধাপে এরর ঠিক অর্ধেক হয় (অর্ডার ১)। সম্পূর্ণ নিশ্চিত, কিন্তু ধীর।

ফিক্সড-পয়েন্ট (L06)
লিনিয়ার কনভারজেন্স, কিন্তু অনুপাত g'(x*)-এর উপর নির্ভর করে — ভালো g(x)-এ বাইসেকশনের চেয়ে দ্রুত, খারাপ g(x)-এ ডাইভার্জ করতে পারে।

নিউটন-রাফসন (L07)
কোয়াড্রেটিক কনভারজেন্স (অর্ডার ২) — এরর প্রায় বর্গ হয়ে যায় প্রতি ধাপে। সবচেয়ে দ্রুত, কিন্তু ডেরিভেটিভ প্রয়োজন ও শূন্য-ডেরিভেটিভে ব্যর্থ হতে পারে।

সেকেন্ট (L08)
সুপার-লিনিয়ার কনভারজেন্স (অর্ডার ≈ ১.৬১৮, সোনালী অনুপাত) — ডেরিভেটিভ ছাড়াই নিউটনের প্রায় সমান গতি।

২ · সরাসরি তুলনা — একই সমীকরণ, একই টলারেন্স, একই কোড সেল

এবার এই তত্ত্বগুলো একসাথে যাচাই করার সময় — L05–L08-এর সব মেথড একই সমীকরণ f(x) = x³ - x - 2-এ, একই টলারেন্স 10⁻⁸-এ, একই কোড সেলে চালিয়ে সরাসরি ইটারেশন-সংখ্যা তুলনা করা হয়েছে। ফিক্সড-পয়েন্ট ইটারেশনের জন্য L06-এর কনভার্জিং g(x) = (x+2)^(1/3) ব্যবহার করা হয়েছে (ডাইভার্জিং সংস্করণটি তুলনার যোগ্য নয়, কারণ সেটি কখনোই কনভার্জ করে না)।

Python

reference_root = 1.5213797068045678
TOL = 1e-8

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

def fprime(x):
    return 3 * x**2 - 1

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

results = {}

# বাইসেকশন
a, b = 1.0, 2.0
for i in range(1, 100):
    mid = (a + b) / 2
    fm = f(mid)
    if b - a < TOL:
        break
    if f(a) * fm < 0:
        b = mid
    else:
        a = mid
results['বাইসেকশন'] = (i, mid, abs(mid - reference_root))

# ফিক্সড-পয়েন্ট (কনভার্জিং g)
x = 1.0
for i in range(1, 100):
    x_new = g_conv(x)
    if abs(x_new - x) < TOL:
        x = x_new
        break
    x = x_new
results['ফিক্সড-পয়েন্ট'] = (i, x, abs(x - reference_root))

# নিউটন-রাফসন
x = 1.2
for i in range(1, 100):
    fx = f(x)
    x_new = x - fx / fprime(x)
    if abs(x_new - x) < TOL:
        x = x_new
        break
    x = x_new
results['নিউটন-রাফসন'] = (i, x, abs(x - reference_root))

# সেকেন্ট
x0, x1 = 1.0, 1.2
for i in range(1, 100):
    f0, f1 = f(x0), f(x1)
    x2 = x1 - f1 * (x1 - x0) / (f1 - f0)
    if abs(x2 - x1) < TOL:
        x1 = x2
        break
    x0, x1 = x1, x2
results['সেকেন্ট'] = (i, x1, abs(x1 - reference_root))

print(f"{'মেথড':<16}{'ইটারেশন':>12}{'চূড়ান্ত x':>18}{'এরর':>16}")
for name, (it, xv, err) in results.items():
    print(f"{name:<16}{it:>12}{xv:>18.10f}{err:>16.2e}")

প্রকৃত আউটপুট: বাইসেকশন — ২৮ ইটারেশন, ফিক্সড-পয়েন্ট — ১১ ইটারেশন, সেকেন্ট — ৭ ইটারেশন, নিউটন-রাফসন — ৫ ইটারেশন — এবং সবগুলো একই রুট ১.৫২১৩৭৯৭০৬৮-এ কনভার্জ করেছে, শুধু ভিন্ন গতিতে। এই ক্রমটি ঠিক তাত্ত্বিক কনভারজেন্স অর্ডারের ক্রম অনুসরণ করে: বাইসেকশন (অর্ডার ১) সবচেয়ে ধীর, তারপর ফিক্সড-পয়েন্ট (এই নির্দিষ্ট g(x)-এর জন্য g' ≈ 0.144, লিনিয়ার কিন্তু অনুকূল অনুপাতে), তারপর সেকেন্ট (অর্ডার ≈১.৬১৮), সবচেয়ে দ্রুত নিউটন-রাফসন (অর্ডার ২)।

৩ · সিদ্ধান্ত-কাঠামো — কোন মেথড কখন

নিচের টেবিলটি M2-এর পুরো মডিউলকে একটি ব্যবহারিক সিদ্ধান্ত-কাঠামোতে সংক্ষিপ্ত করে। এটি M11/L52-এর বৃহত্তর "সঠিক মেথড বাছাই" কাঠামোর একটি বিশেষ (রুট-ফাইন্ডিং-নির্দিষ্ট) সংস্করণ হিসেবে দেখা যেতে পারে।

নির্ভরযোগ্যতাই সবচেয়ে গুরুত্বপূর্ণ হলে
বাইসেকশন বেছে নিন — এর ব্যর্থতার কোনো পরিচিত পরিস্থিতি নেই (একটি বৈধ ব্র্যাকেট থাকলে), এবং এরর বাউন্ড আগে থেকেই জানা যায়।

ডেরিভেটিভ সহজলভ্য ও গতি গুরুত্বপূর্ণ হলে
নিউটন-রাফসন বেছে নিন — তবে একটি ভালো শুরুর অনুমান দরকার এবং ডেরিভেটিভ-শূন্য পরিস্থিতির জন্য গার্ড রাখুন (L07)।

ডেরিভেটিভ পাওয়া কঠিন হলে
সেকেন্ট মেথড বেছে নিন — প্রায় নিউটনের কাছাকাছি গতি, ডেরিভেটিভ ছাড়াই (L08)।

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

মূল কথা · Key takeaway

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

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।

প্র ০১ তুলনা টেবিলে ফিক্সড-পয়েন্ট (১১ ইটারেশন) সেকেন্টের (৭ ইটারেশন) চেয়ে বেশি ইটারেশন নিলেও, উভয়েই "লিনিয়ার-এর চেয়ে ভালো" বলে গণ্য হতে পারে কেন?

ফিক্সড-পয়েন্ট প্রযুক্তিগতভাবে লিনিয়ার কনভারজেন্স (অর্ডার ১), কিন্তু এর অনুপাত g'(x*) ≈ 0.144 বাইসেকশনের 0.5 অনুপাতের চেয়ে অনেক ছোট — তাই প্রতি ধাপে এরর অনেক বেশি কমে, যদিও কনভারজেন্স "অর্ডার" একই। এটি একটি গুরুত্বপূর্ণ পার্থক্য মনে করিয়ে দেয়: শুধু অর্ডার নয়, অনুপাত (rate constant)-ও ব্যবহারিক গতি নির্ধারণ করে।

প্র ০২ যদি সমীকরণটি এমন হতো যেখানে ডেরিভেটিভ কোথাও শূন্যের কাছাকাছি না যায় এবং একটি ভালো শুরুর অনুমানও সহজলভ্য, তাহলে কি বাইসেকশন ব্যবহার করার কোনো কারণ থাকত?

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

প্র ০৩ M2-এর চারটি মেথডের মধ্যে কোনটি একটি একাধিক (multiple) রুট (যেমন (x-1)²=0)-এর ক্ষেত্রে সবচেয়ে সমস্যায় পড়তে পারে বলে আপনার ধারণা?

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

অনুশীলন

চিন্তা করুন: তুলনা কোড সেলে টলারেন্স TOL = 1e-8-কে 1e-12-এ কঠোর করলে, কোন মেথডের ইটারেশন-সংখ্যা সবচেয়ে বেশি বাড়বে বলে আপনার ধারণা — বাইসেকশন নাকি নিউটন-রাফসন?

বাইসেকশনের ইটারেশন-সংখ্যা অনেক বেশি বাড়বে, কারণ লিনিয়ার কনভারজেন্সে প্রতিটি অতিরিক্ত দশমিক স্থানের নির্ভুলতার জন্য প্রায় একই সংখ্যক অতিরিক্ত ইটারেশন লাগে (প্রায় স্থির হারে)। নিউটন-রাফসনের জন্য মাত্র ১–২টি অতিরিক্ত ইটারেশন লাগবে, কারণ কোয়াড্রেটিক কনভারজেন্সে সঠিক ডিজিটের সংখ্যা প্রতি ধাপে প্রায় দ্বিগুণ হয়।
পরীক্ষা করুন: কোড সেলে টলারেন্স সত্যিই 1e-12-এ বদলে Run চেপে আপনার অনুমান যাচাই করুন — প্রতিটি মেথডের নতুন ইটারেশন-সংখ্যা লক্ষ্য করুন।

এই টলারেন্সে (যা মেশিন-প্রিসিশনের অত্যন্ত কাছাকাছি) নিউটন-রাফসন ও সেকেন্ট প্রায় একই ইটারেশন-সংখ্যায় থামবে যা 1e-8-এ থেমেছিল (কারণ তারা ইতিমধ্যে মেশিন-প্রিসিশন সীমার কাছাকাছি পৌঁছে গিয়েছিল), কিন্তু বাইসেকশন ও ফিক্সড-পয়েন্টের ইটারেশন-সংখ্যা লক্ষণীয়ভাবে বেড়ে যাবে — এটি লিনিয়ার বনাম দ্রুত কনভারজেন্সের ব্যবহারিক প্রভাব আরও স্পষ্টভাবে দেখায়।