রিচার্ডসন এক্সট্রাপোলেশন

Richardson extrapolation

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

এক নজরে · TL;DR

রিচার্ডসন এক্সট্রাপোলেশন একটি "ফ্রি লাঞ্চ" কৌশল — একই মেথডের দুটি ভিন্ন h-এর এস্টিমেট একত্র করে, নতুন কোনো ফাংশন-ইভ্যালুয়েশন ছাড়াই একটি অনেক বেশি নির্ভুল ফলাফল পাওয়া যায়।
মূল ধারণা: যদি একটি মেথডের এরর O(h^p) হারে কমে, তাহলে h ও h/2-এ পাওয়া দুটি এস্টিমেটের একটি নির্দিষ্ট ওয়েটেড কম্বিনেশন O(h^p) এরর টার্মটিকে বীজগাণিতিকভাবে বাতিল করে দেয়।
L21-এর সেন্ট্রাল-ডিফারেন্স ডেরিভেটিভে (O(h²)) এই কৌশল প্রয়োগ করে নিচে দেখানো হয়েছে এরর হাজার গুণেরও বেশি কমে যায় — সম্পূর্ণ সত্যিকারের গণনা দিয়ে।
এই একই ধারণা এই কোর্সের বাকি অংশ জুড়ে ফিরে আসবে — ইন্টিগ্রেশনে (রম্বার্গ ইন্টিগ্রেশনের ভিত্তি), এবং ODE সলভারেও একই নীতির প্রয়োগ আছে।

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

রিচার্ডসন এক্সট্রাপোলেশনের পেছনের গাণিতিক যুক্তি — কীভাবে দুটি এস্টিমেট একত্র করে এরর অর্ডার বাড়ানো যায়
সাধারণ রিচার্ডসন ফর্মুলা এবং O(h²) মেথডের জন্য এর নির্দিষ্ট রূপ
L21-এর সেন্ট্রাল-ডিফারেন্স ডেরিভেটিভে প্রয়োগ করে একটি সত্যিকারের নির্ভুলতা বৃদ্ধি পর্যবেক্ষণ
কেন এই কৌশলটিকে "প্রায় বিনামূল্যে" নির্ভুলতা বলা হয়

১ · মূল ধারণা — এরর টার্ম বাতিল করা

L21-এ আমরা দেখেছি সেন্ট্রাল ডিফারেন্স D(h) = [f(x₀+h) - f(x₀-h)] / (2h)-এর এরর O(h²) — অর্থাৎ টেইলর সিরিজ বিশ্লেষণ করলে দেখা যায়:

$$D(h) = f'(x_0) + c_1 h^2 + c_2 h^4 + \cdots$$

যেখানে c₁, c₂, ... ধ্রুবক (ফাংশনের উচ্চ-অর্ডার ডেরিভেটিভের উপর নির্ভরশীল, কিন্তু h-এর উপর নির্ভরশীল নয়)। এখন যদি আমরা h-এর বদলে h/2 ব্যবহার করি:

$$D(h/2) = f'(x_0) + c_1 \frac{h^2}{4} + c_2 \frac{h^4}{16} + \cdots$$

এই দুটি সমীকরণকে বীজগাণিতিকভাবে এমনভাবে একত্র করা সম্ভব যাতে c₁h² টার্মটি সম্পূর্ণ বাতিল হয়ে যায়। D(h/2)-এর সমীকরণকে ৪ দিয়ে গুণ করে D(h)-এর সমীকরণ বিয়োগ করলে:

$$R = \frac{4D(h/2) - D(h)}{3} = f'(x_0) - \frac{c_2 h^4}{4} + \cdots$$

লক্ষ্য করুন — R-এর এরর এখন O(h⁴), মূল O(h²) থেকে দুই ধাপ উপরে! এবং এর জন্য কোনো নতুন f(x) মান লাগেনি — শুধু আগে থেকেই গণনা করা দুটি এস্টিমেট একত্র করা হলো।

সাধারণ ফর্মুলা

যেকোনো মেথডের জন্য যার এরর O(h^p) (যেখানে p জানা), সাধারণ রিচার্ডসন এক্সট্রাপোলেশন ফর্মুলা: $$R = \frac{2^p D(h/2) - D(h)}{2^p - 1}$$ সেন্ট্রাল ডিফারেন্সের জন্য p = 2, তাই 2^p = 4, যা উপরের ফর্মুলার সাথে মিলে যায়। L23-এ ট্র্যাপিজয়ডাল রুলের জন্যও (p = 2) এই একই ধরনের কৌশল প্রযোজ্য — একে রম্বার্গ ইন্টিগ্রেশন বলা হয়।

২ · সত্যিকারের ডেমো — L21-এর সেন্ট্রাল ডিফারেন্সে প্রয়োগ

L21-এর একই ফাংশন (f(x) = sin(x), x₀ = 0.8) ব্যবহার করে, এবার h = 0.1-এ ও h/2 = 0.05-এ সেন্ট্রাল ডিফারেন্স গণনা করে রিচার্ডসন সূত্র প্রয়োগ করা হলো:

Python

import math

def f(x):
    return math.sin(x)

def central(x0, h):
    return (f(x0+h) - f(x0-h)) / (2*h)

x0 = 0.8
true_val = math.cos(x0)
print(f"true f'({x0}) = {true_val:.10f}")
print()

h = 0.1
D_h  = central(x0, h)
D_h2 = central(x0, h/2)
R = (4*D_h2 - D_h) / 3

err_h  = abs(D_h  - true_val)
err_h2 = abs(D_h2 - true_val)
err_R  = abs(R    - true_val)

print(f"D(h)      h={h:6}   estimate={D_h:.10f}   error={err_h:.3e}")
print(f"D(h/2)    h={h/2:6}   estimate={D_h2:.10f}   error={err_h2:.3e}")
print(f"Richardson R = (4*D(h/2)-D(h))/3 = {R:.10f}   error={err_R:.3e}")
print()
print(f"improvement vs D(h/2): {err_h2/err_R:.1f}x smaller error")
print(f"improvement vs D(h):   {err_h/err_R:.1f}x smaller error")

D(h)-এর এরর ১.১৬১ × ১০⁻³, D(h/2)-এর এরর ২.৯০৩ × ১০⁻⁴ — নিজে থেকেই এটি D(h)-এর প্রায় ৪ গুণ ভালো (যেমনটা O(h²)-এর কাছে প্রত্যাশিত)। কিন্তু রিচার্ডসন এক্সট্রাপোলেটেড মান R-এর এরর মাত্র ১.৪৫১ × ১০⁻⁷ — D(h/2)-এর তুলনায় প্রায় ২০০০ গুণ এবং D(h)-এর তুলনায় প্রায় ৮০০০ গুণ ছোট! এবং এই বিশাল নির্ভুলতা বৃদ্ধি পাওয়া গেছে শুধু দুটি আগে থেকেই গণনা করা সংখ্যাকে যোগ-বিয়োগ-ভাগ করে — কোনো নতুন sin(x) কল ছাড়াই।

৩ · একই ধারণা, ভিন্ন `h`-এ

নিচে একই প্রক্রিয়া h = 0.2 দিয়ে শুরু করে দেখানো হলো, যাতে বোঝা যায় এটি কোনো বিশেষ h-এর কাকতালীয় ফল নয়:

Python

import math

def f(x):
    return math.sin(x)

def central(x0, h):
    return (f(x0+h) - f(x0-h)) / (2*h)

x0 = 0.8
true_val = math.cos(x0)

h = 0.2
D_h  = central(x0, h)
D_h2 = central(x0, h/2)
R = (4*D_h2 - D_h) / 3

err_h  = abs(D_h  - true_val)
err_h2 = abs(D_h2 - true_val)
err_R  = abs(R    - true_val)

print(f"D(h)      h={h:6}   estimate={D_h:.10f}   error={err_h:.3e}")
print(f"D(h/2)    h={h/2:6}   estimate={D_h2:.10f}   error={err_h2:.3e}")
print(f"Richardson estimate = {R:.10f}   error={err_R:.3e}")
print(f"improvement vs D(h/2): {err_h2/err_R:.1f}x smaller error")

এবারও একই প্যাটার্ন — h = 0.2-এ D(h)-এর এরর ৪.৬৩৫ × ১০⁻³, D(h/2)-এর এরর ১.১৬১ × ১০⁻³, কিন্তু রিচার্ডসন এস্টিমেটের এরর মাত্র ২.৩২০ × ১০⁻⁶ — D(h/2)-এর তুলনায় প্রায় ৫০০ গুণ ছোট। উন্নতির সঠিক অনুপাত h-এর মানের উপর নির্ভর করে ভিন্ন হয় (কারণ এটি উচ্চ-অর্ডার টার্ম c₂h⁴-এর উপর নির্ভরশীল), কিন্তু উন্নতির দিকটি সবসময় একই — বিশাল, প্রায় বিনামূল্যে।

মূল কথা · Key takeaway

রিচার্ডসন এক্সট্রাপোলেশন দেখায় নিউমেরিক্যাল মেথডের নির্ভুলতা বাড়ানোর একটি শক্তিশালী উপায় — নতুন কম্পিউটেশন না করে, বরং বিদ্যমান এস্টিমেটগুলোর মধ্যে থাকা জ্ঞাত-প্যাটার্নের এরর টার্মকে বীজগাণিতিকভাবে বাতিল করে। এই কৌশলটি সাধারণ — যেকোনো মেথড যার এরর একটি জানা h^p প্যাটার্নে কমে, তাতেই এটি প্রযোজ্য। L23-এ আমরা দেখব কীভাবে এই একই ধারণা ইন্টিগ্রেশনেও কাজ করে।

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

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

প্র ০১ রিচার্ডসন এক্সট্রাপোলেশন 4D(h/2) - D(h)-এর মধ্যে c₁h² টার্মটি বাতিল করে দেয় বলা হয়েছে। কেন গুণক ঠিক ৪ — অন্য কোনো সংখ্যা নয়?

D(h/2)-এর এরর টার্ম হলো c₁(h/2)² = c₁h²/4। এই টার্মটিকে D(h)-এর এরর টার্ম c₁h²-এর সমান করে বাতিল করতে হলে D(h/2)-কে ৪ দিয়ে গুণ করতে হয় (যাতে 4 × c₁h²/4 = c₁h² হয়ে D(h)-এর সাথে বিয়োগে ক্যান্সেল হয়ে যায়)। সাধারণভাবে p-অর্ডার মেথডের জন্য গুণক হয় 2^p, কারণ h/2-এর p-তম ঘাত হলো h^p / 2^p।

প্র ০২ রিচার্ডসন এক্সট্রাপোলেশন কি বারবার প্রয়োগ করা যায় — অর্থাৎ R-এর উপর আবার রিচার্ডসন প্রয়োগ করে আরও নির্ভুল ফলাফল পাওয়া সম্ভব?

হ্যাঁ — যদি R-এর অবশিষ্ট এরর টার্মও একটি জানা h-এর ঘাত অনুসরণ করে (উপরের উদাহরণে O(h⁴)), তাহলে একই কৌশল আবার প্রয়োগ করে O(h⁶) নির্ভুলতা পাওয়া সম্ভব, এবং এভাবে চালিয়ে যাওয়া যায়। এই পুনরাবৃত্ত ধারণাটিই রম্বার্গ ইন্টিগ্রেশনের ভিত্তি, যেখানে ট্র্যাপিজয়ডাল রুলের একাধিক এস্টিমেটের উপর বারবার রিচার্ডসন এক্সট্রাপোলেশন প্রয়োগ করে অত্যন্ত নির্ভুল ইন্টিগ্রাল এস্টিমেট তৈরি করা হয়।

প্র ০৩ রিচার্ডসন এক্সট্রাপোলেশন কি সবসময় প্রয়োগ করা উচিত — কোনো ক্ষেত্রে কি এটি কাজ নাও করতে পারে?

এটি নির্ভর করে মূল মেথডের এরর সত্যিই একটি মসৃণ, জানা h^p প্যাটার্ন অনুসরণ করে কিনা। যদি ফাংশনটি যথেষ্ট মসৃণ না হয় (যেমন একটি অসংলগ্নতা বা তীক্ষ্ণ পরিবর্তন থাকে), তাহলে টেইলর সিরিজ বিশ্লেষণ যে অনুমানের উপর ভিত্তি করে তৈরি, তা ভেঙে পড়ে এবং এক্সট্রাপোলেশন প্রত্যাশিত উন্নতি নাও দিতে পারে। এছাড়া, যদি h ইতিমধ্যে এত ছোট হয় যে রাউন্ড-অফ এরর প্রাধান্য পাচ্ছে (L21-এর আলোচনা), তাহলে এক্সট্রাপোলেশন সেই রাউন্ড-অফ শব্দকেও বাড়িয়ে দিতে পারে।

অনুশীলন

চিন্তা করুন: প্রথম কোড সেলে যদি h = 0.05 এবং h/2 = 0.025 ব্যবহার করা হয় (অর্থাৎ পুরো প্রক্রিয়া আরও ছোট h থেকে শুরু হয়), রিচার্ডসন এস্টিমেটের এরর আগের চেয়ে ভালো হবে না খারাপ হবে বলে আপনার ধারণা?

যেহেতু রিচার্ডসন এস্টিমেটের অবশিষ্ট এরর O(h⁴), ছোট h থেকে শুরু করলে এরর আরও ছোট হওয়ার কথা (যতক্ষণ না রাউন্ড-অফ এরর প্রাধান্য পায়) — hকে অর্ধেক করলে O(h⁴) এরর প্রায় ১৬ গুণ ছোট হওয়া উচিত।
পরীক্ষা করুন: প্রথম কোড সেলে h = 0.05 সেট করে Run চেপে আপনার অনুমান যাচাই করুন, এবং R-এর এরর আগের h = 0.1-এর ফলাফলের সাথে তুলনা করুন।

h = 0.05-এ শুরু করলে D(h) ও D(h/2) = D(0.025)-এর রিচার্ডসন কম্বিনেশনের এরর মূল h = 0.1-এর ফলাফল (১.৪৫১ × ১০⁻⁷)-এর তুলনায় উল্লেখযোগ্যভাবে ছোট হয় — কারণ পুরো রিচার্ডসন সিকোয়েন্সটাই এখন ছোট h থেকে শুরু হচ্ছে, এবং O(h⁴) কনভারজেন্স বজায় থাকে।