বুদানের উপপাদ্য

গণিতে, বুদানের উপপাদ্য একটি উপপাদ্য যা একটি পলিনোমিয়ালের বাস্তব রুটের সংখ্যা একটি অন্তরালে সীমানা নির্ধারণ এবং এই সংখ্যার প্যারিটি গণনা করতে ব্যবহৃত হয়। এটি ১৮০৭ সালে ফ্রাঁসোয়া বুদান ডে বয়সলোরাঁ দ্বারা প্রকাশিত হয়।

একই ধরনের একটি উপপাদ্য ১৮২০ সালে জোসেফ ফুরিয়ে স্বতন্ত্রভাবে প্রকাশ করেছিলেন। এই দুটি উপপাদ্য একে অপরের পরিণতি হিসেবে গণ্য হয়। ফুরিয়ে'র বক্তব্যটি ১৯ শতকের সাহিত্যিকদের মধ্যে অধিক প্রচলিত এবং এটিকে ফুরিয়ে'র, বুদান–ফুরিয়ে, ফুরিয়ে–বুদান এমনকি বুদানের উপপাদ্য হিসেবেও উল্লেখ করা হয়েছে।

বুদানের মূল ফর্মুলেশনটি দ্রুত আধুনিক অ্যালগরিদমগুলিতে ব্যবহৃত হয়, যা পলিনোমিয়ালের বাস্তব-রুট বিচ্ছেদ নির্ধারণ করতে সাহায্য করে।

সাইন পরিবর্তন

ধরা যাক $c_0,c_1,c_2,\dots c_k$ হলো বাস্তব সংখ্যার একটি সসীম অনুক্রম। একটি সাইন পরিবর্তন বা সাইন চেঞ্জ সেই দুটি সূচক টেমপ্লেট:Math এর জন্য ঘটে, যখন $c_i{c}_j<0,$ এবং অথবা টেমপ্লেট:Math অথবা $c_k=0$ সকল টেমপ্লেট:Mvar এর জন্য, যেখানে টেমপ্লেট:Math।

অর্থাৎ, একটি সাইন পরিবর্তন ঘটে যখন সাইন পরিবর্তিত হয়, যদি শূন্যগুলো উপেক্ষা করা হয়।

পলিনোমিয়ালের বাস্তব রুটগুলো অধ্যয়ন করার জন্য, বিভিন্ন অনুক্রমের সাইন পরিবর্তনের সংখ্যা ব্যবহার করা যেতে পারে। বুদানের উপপাদ্যের জন্য, এটি হলো কৌশলের কোফিসিয়েন্টগুলির অনুক্রম। ফুরিয়ে'র উপপাদ্যের জন্য, এটি হলো একটি বিন্দুর জন্য পরবর্তী ডেরিভেটিভগুলির মানগুলির অনুক্রম। স্টার্মের উপপাদ্য এর জন্য এটি হলো একটি বিন্দুর জন্য স্টার্ম সিকোয়েন্স এর মানগুলির অনুক্রম।

দেস্কার্টেসের সাইন রুল

এই প্রবন্ধে বর্ণিত সমস্ত ফলাফল দেস্কার্টেসের সাইন রুলের উপর ভিত্তি করে।

যদি টেমপ্লেট:Math একটি একক ভেরিয়েবল পলিনোমিয়াল হয় যার বাস্তব কোফিসিয়েন্ট রয়েছে, তাহলে আমরা টেমপ্লেট:Math দ্বারা এর ইতিবাচক বাস্তব রুটগুলির সংখ্যা বোঝাবো, যা তাদের গুণফলসহ গণনা করা হয়, এবং টেমপ্লেট:Math দ্বারা এর কোফিসিয়েন্টের অনুক্রমে সাইন পরিবর্তনের সংখ্যা বোঝানো হয়। দেস্কার্টেস এর সাইন রুল asserts যে

টেমপ্লেট:Math একটি ঋণাত্মক পার্থক্যহীন জোড় সংখ্যা।

বিশেষত, যদি টেমপ্লেট:Math, তবে টেমপ্লেট:Math।

বুদানের উপপাদ্য

ধরা যাক একটি একক ভেরিয়েবল পলিনোমিয়াল টেমপ্লেট:Math যার বাস্তব কোফিসিয়েন্ট রয়েছে, আমরা টেমপ্লেট:Math দ্বারা বাস্তব রুটের সংখ্যা বোঝাবো, যা তাদের গুণফলসহ গণনা করা হয়, টেমপ্লেট:Mvar এর জন্য একটি অর্ধ-খোলা অন্তরাল টেমপ্লেট:Math (যেখানে টেমপ্লেট:Math বাস্তব সংখ্যা)। আমরা টেমপ্লেট:Math দ্বারা পলিনোমিয়াল টেমপ্লেট:Math এর কোফিসিয়েন্টগুলির অনুক্রমে সাইন পরিবর্তনের সংখ্যা বোঝাবো। বিশেষত, আমরা টেমপ্লেট:Math হিসেবে আগে উল্লিখিত নোটেশন ব্যবহার করব।

বুদানের উপপাদ্য হলো:

$v_{\ell }(p)-v_r(p)-{\mathrm{\#}}_{(\ell ,r]}$ একটি ঋণাত্মক পার্থক্যহীন জোড় সংখ্যা।

যেহেতু ${\mathrm{\#}}_{(\ell ,r]}$ ঋণাত্মক নয়, এটি নির্দেশ করে যে $v_{\ell }(p)\ge v_r(p).$

এটি দেস্কার্টেসের সাইন রুলের একটি সাধারণীকরণ, কারণ, যদি টেমপ্লেট:Mvar যথেষ্ট বড় হয়, এটি টেমপ্লেট:Mvar এর সকল বাস্তব রুটের চেয়ে বড় হবে এবং টেমপ্লেট:Math এর সমস্ত কোফিসিয়েন্ট ইতিবাচক হবে, অর্থাৎ $v_r(p)=0$। সুতরাং $v_0(p)=v_0(p)-v_r(p),$ এবং ${\mathrm{\#}}_{+}={\mathrm{\#}}_{(0,r)},$ যা দেস্কার্টেসের সাইন রুলকে বুদানের উপপাদ্যের একটি বিশেষ ক্ষেত্র তৈরি করে।

দেস্কার্টেসের সাইন রুলের মতো, যদি $v_{\ell }(p)-v_r(p)\le 1,$ তাহলে ${\mathrm{\#}}_{(\ell ,r]}=v_{\ell }(p)-v_r(p).$ এর মানে হল যে, যদি $v_{\ell }(p)-v_r(p)\le 1$ হয়, তবে একটি "শূন্য-রুট পরীক্ষা" এবং একটি "এক-রুট পরীক্ষা" রয়েছে।

উদাহরণ

১. পলিনোমিয়াল টেমপ্লেট:Math এবং খোলা অন্তরাল টেমপ্লেট:Math দেওয়া থাকলে, আমরা পাই:

$\begin{array}{cc}p(x+0)& =p(x)=x^3-7x+7\\ p(x+2)& =(x+2{)}^3-7(x+2)+7=x^3+6x^2+5x+1\end{array}.$

তাহলে, $v_0(p)-v_2(p)=2-0=2$, এবং বুদানের উপপাদ্য অনুসারে, পলিনোমিয়াল টেমপ্লেট:Math এর খোলা অন্তরালে টেমপ্লেট:Math দুইটি অথবা শূন্য বাস্তব রুট থাকবে।

২. একই পলিনোমিয়াল টেমপ্লেট:Math দিয়ে, আমরা পাই:

$p(x+1)=(x+1{)}^3-7(x+1)+7=x^3+3x^2-4x+1.$

তাহলে, $v_0(p)-v_1(p)=2-2=0$, এবং বুদানের উপপাদ্য অনুসারে, পলিনোমিয়াল টেমপ্লেট:Math এর খোলা অন্তরালে টেমপ্লেট:Math কোনো বাস্তব রুট নেই। এটি বুদানের উপপাদ্য ব্যবহারের একটি শূন্য-রুট পরীক্ষার উদাহরণ।

ফুরিয়ে'র উপপাদ্য টেমপ্লেট:Anchor

ফুরিয়ে'র পলিনোমিয়াল বাস্তব রুট সম্পর্কিত উপপাদ্য, যা ফুরিয়ে–বুদান উপপাদ্য অথবা বুদান–ফুরিয়ে উপপাদ্য (কখনও কখনও শুধু বুদানের উপপাদ্য নামে পরিচিত) ঠিক বুদানের উপপাদ্যের মতই, তবে এখানে টেমপ্লেট:Math এবং টেমপ্লেট:Mvar এর জন্য টেমপ্লেট:Math এর কোফিসিয়েন্টগুলির অনুক্রমের পরিবর্তে, টেমপ্লেট:Mvar এর ডেরিভেটিভগুলির অনুক্রম ব্যবহৃত হয়।

প্রতিটি উপপাদ্য অন্যটির পরিণতি হিসেবে গণ্য হয়। এটি টেলর সম্প্রসারণ থেকে উদ্ভূত:

$p(x)=\sum _{i=0}^{\mathrm{deg}p}\frac{p^{(i)}(h)}{i!}(x-h{)}^i$

পলিনোমিয়াল টেমপ্লেট:Mvar এর টেমপ্লেট:Mvar এ টেলর সম্প্রসারণ, যা নির্দেশ করে যে টেমপ্লেট:Math এর কোফিসিয়েন্ট টেমপ্লেট:Math হল $p^{(i)}(h)$ দ্বারা ভাগ করা টেমপ্লেট:Math এর একটি ধনাত্মক সংখ্যা। সুতরাং, ফুরিয়ে'র উপপাদ্য এবং বুদানের উপপাদ্য উভয়ের সিকোয়েন্সগুলির সাইন পরিবর্তনের সংখ্যা সমান।

এই দুটি উপপাদ্যের মধ্যে এই শক্তিশালী সম্পর্কটি ১৯ শতকে অগ্রগণ্যতা সম্পর্কিত বিতর্কের ব্যাখ্যা দিতে পারে এবং একে অন্যের জন্য বিভিন্ন নামের ব্যবহার বুঝিয়ে দিতে পারে। আধুনিক ব্যবহার অনুযায়ী, কম্পিউটার গণনায় বুদানের উপপাদ্য সাধারণত পছন্দ করা হয়, কারণ ফুরিয়ে'র উপপাদ্যে সিকোয়েন্সগুলির কোফিসিয়েন্টগুলি বুদানের উপপাদ্যের তুলনায় অনেক বড়, কারণ সেখানে ফ্যাক্টোরিয়াল ফ্যাক্টর থাকে।

প্রমাণ

যেহেতু প্রতিটি উপপাদ্য একে অপরের উপবীজগণিত, তাই ফুরিয়ে'র উপপাদ্য প্রমাণ করা যথেষ্ট।

প্রমাণ:

ধরা যাক $n$ হল $f$-এর ডিগ্রি, যাতে $f,f^{\prime },...,f^{(n-1)}$ গুলি অ-ধ্রুবক পলিনোমিয়াল, $f^{(n)}$ একটি অ-শূন্য ধ্রুবক এবং $f^{(n+1)},...$ সবই অভিন্ন শূন্য।

$t$ এর একটি ফাংশন হিসেবে, $v_t(f)$ শুধুমাত্র $f,f^{\prime },...,f^{(n-1)}$ এর মধ্যে যেকোনো একটি রুটে পরিবর্তন ঘটাতে পারে।

যদি $v_t(f)$ $t=r$ তে পরিবর্তিত হয়, তাহলে কোন $k$ এর জন্য, $f^{(k)}(x)$ এর একটি রুট $t$ তে থাকবে, এবং $f,f^{\prime },...,f^{(k-1)}$ এর কোনো রুট $t$ তে থাকবে না।

যদি $k=0$, তাহলে $f(x)=(x-r{)}^{s}p(x-r)$ হবে যেখানে কিছু $s\ge 1$ এবং $p$ একটি পলিনোমিয়াল হবে যা $p(0)\ne 0$। $f,f^{\prime },...,f^{(n)}$ গুলিকে $r$ এবং $r-ϵ$ তে একটি ছোট $ϵ$ এর জন্য স্পষ্টভাবে গণনা করলে, আমরা পাই $v_r(f)=v_{r-ϵ}(f)-s-2s^{\prime },\mathrm{\exists }{s}^{\prime }\ge 0$।

এই সমীকরণে, $-s$ পদটি $f,f^{\prime },...,f^{(s)}$ এর সাইন পরিবর্তন থেকে উদ্ভূত যা $(-1{)}^s\mathrm{sign}(p(0)),(-1{)}^{s-1}\mathrm{sign}(p(0)),...,-\mathrm{sign}(p(0)),\mathrm{sign}(p(0))$ থেকে $0,0,...,0,\mathrm{sign}(p(0))$ তে পরিবর্তিত হয়। $-2s^{\prime },\mathrm{\exists }{s}^{\prime }\ge 0$ পদটি উচ্চতর সাইন পরিবর্তনের কারণে শূন্য হয়ে যেতে পারে।

যদি $k\ge 1$, তাহলে যেহেতু কিছু ডেরিভেটিভ $r$ তে শূন্য হয়, কিন্তু $f^{(k-1)}(x)$ এবং $f^{(n)}(x)$ অ-শূন্য থাকে, আমরা শুধুমাত্র সাইন পরিবর্তনের একটি সোজা সংখ্যা হারাই:

$$v_r(f)=v_{r-ϵ}(f)-2s^{\prime },\mathrm{\exists }{s}^{\prime }\ge 0$$

যদি $v_t(f)$ $t=l$ তে পরিবর্তিত হয়, তবে অনুরূপভাবে যুক্তি দিলে, আমরা দেখতে পাই যে, উভয় ক্ষেত্রে, একটি ছোট $ϵ$ নেওয়া যেতে পারে যাতে $v_{l+ϵ}(f)=v_l(f)$।

ইতিহাস

একটি পলিনোমিয়ালের বাস্তব রুট গণনা এবং তাদের অবস্থান নির্ধারণের সমস্যা শুধুমাত্র ১৯ শতকের শুরুতে সুশৃঙ্খলভাবে অধ্যয়ন করা শুরু হয়।

১৮০৭ সালে, ফ্রাঁসোয়া বুদান ডে বয়সলোরাঁ একটি পদ্ধতি আবিষ্কার করেন যার মাধ্যমে তিনি দেস্কার্টেসের সাইন রুল—যা টেমপ্লেট:Math অন্তরালে বৈধ—কোনো অন্তরালে প্রয়োগ করার জন্য সম্প্রসারিত করেন।

জোসেফ ফুরিয়ে ১৮২০ সালে একটি অনুরূপ উপপাদ্য প্রকাশ করেন, যার উপর তিনি বিশ বছরেরও বেশি সময় কাজ করেছেন।

দুটি উপপাদ্যের মধ্যে সাদৃশ্য থাকায়, একটি অগ্রাধিকার বিতর্ক সৃষ্টি হয়, যদিও দুটি উপপাদ্যই স্বাধীনভাবে আবিষ্কৃত হয়েছিল। সাধারণত ১৯ শতকে সমীকরণ তত্ত্ব সম্পর্কিত পাঠ্যবইগুলিতে ফুরিয়ে'র ফর্মুলেশন এবং প্রমাণ ব্যবহার করা হত।

১৯ শতকে ব্যবহৃত

বুদানের এবং ফুরিয়ে'র উপপাদ্যগুলি দ্রুতই অত্যন্ত গুরুত্বপূর্ণ হিসাবে বিবেচিত হতে থাকে, যদিও তারা একটি পলিনোমিয়ালের বাস্তব রুটের সংখ্যা একটি অন্তরালে সম্পূর্ণভাবে গণনা করার সমস্যার সমাধান দেয় না। এই সমস্যা ১৮২৭ সালে স্টার্ম দ্বারা সম্পূর্ণভাবে সমাধান করা হয়।

যদিও স্টার্মের উপপাদ্য দেস্কার্টেসের সাইন রুল এর উপর ভিত্তি করে নয়, স্টার্ম এবং ফুরিয়ে'র উপপাদ্যগুলি শুধুমাত্র সাইন পরিবর্তনের সংখ্যা ব্যবহার করার দিক থেকে সম্পর্কিত নয়, বরং সমস্যাটি সমাধানের জন্য অনুরূপ একটি দৃষ্টিভঙ্গি রয়েছে। স্টার্ম নিজেই স্বীকার করেছেন যে তিনি ফুরিয়ে'র পদ্ধতিগুলি দ্বারা প্রভাবিত হয়েছিলেন: « C'est en m'appuyant sur les principes qu'il a posés, et en imitant ses démonstrations, que j'ai trouvé les nouveaux théorèmes que je vais énoncer. » যার বাংলা অনুবাদ « এটি তার দ্বারা প্রতিষ্ঠিত নীতিগুলির উপর ভর করে এবং তার প্রমাণগুলির অনুকরণ করে আমি যে নতুন উপপাদ্যগুলি উপস্থাপন করতে যাচ্ছি তা আবিষ্কার করেছি। »

এ কারণে, ১৯ শতকে ফুরিয়ে'র এবং স্টার্মের উপপাদ্যগুলি প্রায় সমস্ত সমীকরণ তত্ত্ব সম্পর্কিত বইগুলিতে একসাথে উপস্থিত ছিল।

ফুরিয়ে এবং বুদান রুট খোঁজার জন্য অন্তরালের আকার কমানোর সমস্যা খোলাই রেখেছিলেন, যাতে পরিশেষে সাইন পরিবর্তনের সংখ্যা একের বেশি না হয়, এবং নিশ্চিতভাবে বলা যায় যে চূড়ান্ত অন্তরালগুলির মধ্যে প্রতি একটি অন্তত একটি রুট থাকে। এই সমস্যা ১৮৩৪ সালে ভিনসেন্ট সমাধান করেন। সংক্ষেপে, ভিনসেন্টের উপপাদ্য হচ্ছে ক্রমাগত ভগ্নাংশ ব্যবহার করে বুদানের ভেরিয়েবলের লিনিয়ার রূপান্তরগুলোকে মোবিয়াস রূপান্তর দ্বারা প্রতিস্থাপন করা।

বুদান, ফুরিয়ে এবং ভিনসেন্টের উপপাদ্যগুলি ১৯ শতকের শেষের দিকে বিস্মৃত হয়ে যায়। দ্বিতীয় বিশ্বযুদ্ধের আগে শেষ লেখক যিনি এই উপপাদ্যগুলি উল্লেখ করেছিলেন তিনি জোসেফ আলফ্রেড সেরেট। ১৯ শতকের দ্বিতীয়ার্ধে এই উপপাদ্যগুলি আবার পরিচিত হয় ১৯৭৬ সালে জর্জ ই. কলিন্স এবং আলকিভিয়াদিস জি. আক্রিতাস দ্বারা, যারা কম্পিউটার অ্যালজেব্রাতে বাস্তব রুট বিচ্ছেদ করার জন্য একটি দক্ষ অ্যালগরিদম প্রদান করেছিলেন।

দেখুন আরও

• পলিনোমিয়াল রুটের বৈশিষ্ট্য
• রুট-খোঁজা অ্যালগরিদম