মূল নির্ণয়ে নিউটনের মেথড#
এটি একটি ইটারেটিভ মেথড যা আইজ্যাক নিউটন ১৬৬৪ সালের দিকে আবিষ্কার করেছিলেন। তবে, এই মেথডটিকে কখনো কখনো র্যাফসন মেথডও বলা হয়, যেহেতু র্যাফসন নিউটনের কয়েক বছর পর একই অ্যালগরিদম আবিষ্কার করেছিলেন, কিন্তু তাঁর নিবন্ধটি অনেক আগে প্রকাশিত হয়েছিল।
সমস্যাটি নিম্নরূপ। নিম্নলিখিত সমীকরণটি দেওয়া আছে:
$$f(x) = 0$$আমরা সমীকরণটি সমাধান করতে চাই। আরও সুনির্দিষ্টভাবে, আমরা এর একটি মূল খুঁজতে চাই (ধরে নেওয়া হচ্ছে মূলটি বিদ্যমান)। ধরে নেওয়া হচ্ছে $f(x)$ একটি ব্যবধান $[a, b]$ এ অবিচ্ছিন্ন এবং অন্তরণযোগ্য।
অ্যালগরিদম#
অ্যালগরিদমের ইনপুট প্যারামিটারগুলো শুধু ফাংশন $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}$ কাঙ্ক্ষিত মূলের আরও কাছে হবে।
অভিসারের হার দ্বিঘাত, যা শর্তসাপেক্ষে বলতে গেলে, আনুমানিক মান $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$ মিলিসেকেন্ড সময় নেবে।