মূল নির্ণয়ে নিউটনের মেথড#
এটা একটি ইটারেটিভ মেথড যা আইজ্যাক নিউটন ১৬৬৪ সালের দিকে আবিষ্কার করেছিলেন। তবে, এই মেথডটিকে কখনো কখনো র্যাফসন মেথডও বলা হয়, যেহেতু র্যাফসন নিউটনের কয়েক বছর পর একই অ্যালগরিদম আবিষ্কার করেছিলেন, কিন্তু তাঁর আর্টিকেলটা অনেক আগে প্রকাশিত হয়েছিল।
সমস্যাটা এরকম। নিচের ইকুয়েশনটি দেওয়া আছে:
$$f(x) = 0$$আমরা ইকুয়েশনটি সমাধান করতে চাই। সোজা কথায়, আমরা এর একটি মূল খুঁজতে চাই (ধরে নেওয়া হচ্ছে মূলটি বিদ্যমান)। ধরে নেওয়া হচ্ছে $f(x)$ একটি ব্যবধান $[a, b]$ এ কন্টিনিউয়াস (continuous) এবং ডিফারেনশিয়েবল (differentiable)।
অ্যালগরিদম#
অ্যালগরিদমের ইনপুট প্যারামিটারগুলো শুধু ফাংশন $f(x)$ নয়, প্রাথমিক আনুমানিক মানও - কোনো $x_0$, যা দিয়ে অ্যালগরিদম শুরু হয়।
ধরি আমরা ইতিমধ্যে $x_i$ গণনা করেছি, $x_{i+1}$ এভাবে গণনা করি। $x = x_i$ বিন্দুতে $f(x)$ ফাংশনের গ্রাফে স্পর্শক আঁকি, এবং এই স্পর্শকের $x$-অক্ষের সাথে ছেদবিন্দু খুঁজি। $x_{i+1}$ কে প্রাপ্ত বিন্দুর $x$-স্থানাঙ্কের সমান ধরা হয়, এবং আমরা পুরো প্রক্রিয়াটি শুরু থেকে পুনরাবৃত্তি করি।
নিচের সূত্রটি বের করা কঠিন নয়,
$$ x_{i+1} = x_i - \frac{f(x_i)}{f^\prime(x_i)} $$প্রথমে, আমরা ঢাল $f'(x)$, অর্থাৎ $f(x)$ এর অন্তরক গণনা করি, এবং তারপর স্পর্শকের ইকুয়েশন নির্ণয় করি যা হলো,
$$ y - f(x_i) = f'(x_i)(x - x_i) $$স্পর্শকটি x-অক্ষকে $y = 0$ এবং $x = x_{i+1}$ স্থানাঙ্কে ছেদ করে,
$$ - f(x_i) = f'(x_i)(x_{i+1} - x_i) $$এখন, ইকুয়েশনটি সমাধান করে আমরা $x_{i+1}$ এর মান পাই।
এটা বুঝতেই পারছো যে ফাংশন $f(x)$ যদি “ভালো” (মসৃণ) হয়, এবং $x_i$ মূলের যথেষ্ট কাছাকাছি হয়, তাহলে $x_{i+1}$ কাঙ্ক্ষিত মূলের আরও কাছে হবে।
কনভার্জেন্সের (convergence) হার কোয়াড্রাটিক (quadratic)। তারমানে, আনুমানিক মান $x_i$ এর সঠিক অঙ্কের সংখ্যা প্রতিটি ইটারেশনে দ্বিগুণ হয়।
বর্গমূল গণনায় প্রয়োগ#
নিউটনের মেথডের উদাহরণ হিসেবে বর্গমূল গণনা ব্যবহার করা যাক।
যদি আমরা $f(x) = x^2 - n$ বসাই, তাহলে রাশিটি সরলীকরণের পর পাই:
$$ x_{i+1} = \frac{x_i + \frac{n}{x_i}}{2} $$সমস্যার প্রথম সাধারণ রূপটি হলো যখন একটি মূলদ সংখ্যা $n$ দেওয়া আছে, এবং এর মূল কিছু নির্ভুলতা eps সহ গণনা করতে হবে:
double sqrt_newton(double n) {
const double eps = 1E-15;
double x = 1;
for (;;) {
double nx = (x + n / x) / 2;
if (abs(x - nx) < eps)
break;
x = nx;
}
return x;
}সমস্যার আরেকটি সাধারণ রূপ হলো যখন আমাদের পূর্ণসংখ্যা মূল গণনা করতে হয় (দেওয়া $n$ এর জন্য সবচেয়ে বড় $x$ খুঁজতে হবে যেন $x^2 \le n$)। এখানে অ্যালগরিদমের শেষ শর্ত কিছুটা পরিবর্তন করতে হবে, কারণ এমন হতে পারে যে $x$ উত্তরের কাছে “লাফাতে” শুরু করবে। অতএব, আমরা একটি শর্ত যোগ করি যে যদি আগের ধাপে $x$ এর মান কমে থাকে, এবং বর্তমান ধাপে এটা বাড়ানোর চেষ্টা করে, তাহলে অ্যালগরিদম থামাতে হবে।
int isqrt_newton(int n) {
int x = 1;
bool decreased = false;
for (;;) {
int nx = (x + n / x) >> 1;
if (x == nx || nx > x && decreased)
break;
decreased = nx < x;
x = nx;
}
return x;
}সবশেষে, তৃতীয় রূপটি দেখো - bignum অ্যারিথমেটিকের ক্ষেত্রে। যেহেতু সংখ্যা $n$ যথেষ্ট বড় হতে পারে, প্রাথমিক আনুমানিক মানের দিকে মনোযোগ দেওয়া দরকার। এটা বোঝাই যাচ্ছে যে এটা মূলের যত কাছে হবে, তত দ্রুত ফলাফল পাওয়া যাবে। $2^{\textrm{bits}/2}$ সংখ্যাটিকে প্রাথমিক আনুমানিক মান হিসেবে নেওয়া যথেষ্ট সহজ এবং কার্যকর, যেখানে $\textrm{bits}$ হলো সংখ্যা $n$ এর বিটের সংখ্যা। নিচে এই রূপটি দেখানো Java কোড দেওয়া হলো:
public static BigInteger isqrtNewton(BigInteger n) {
BigInteger a = BigInteger.ONE.shiftLeft(n.bitLength() / 2);
boolean p_dec = false;
for (;;) {
BigInteger b = n.divide(a).add(a).shiftRight(1);
if (a.compareTo(b) == 0 || a.compareTo(b) < 0 && p_dec)
break;
p_dec = a.compareTo(b) > 0;
a = b;
}
return a;
}উদাহরণস্বরূপ, $n = 10^{1000}$ এর জন্য এই কোড $60$ মিলিসেকেন্ডে চলে, এবং যদি আমরা উন্নত প্রাথমিক আনুমানিক মান নির্বাচন সরিয়ে দিই ($1$ থেকে শুরু করি), তাহলে এটা প্রায় $120$ মিলিসেকেন্ড সময় নেবে।