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

গণিতে, বুদানের উপপাদ্য একটি উপপাদ্য যা একটি পলিনোমিয়ালের বাস্তব রুটের সংখ্যা একটি অন্তরালে সীমানা নির্ধারণ এবং এই সংখ্যার প্যারিটি গণনা করতে ব্যবহৃত হয়। এটি ১৮০৭ সালে ফ্রাঁসোয়া বুদান ডে বয়সলোরাঁ দ্বারা প্রকাশিত হয়।
একই ধরনের একটি উপপাদ্য ১৮২০ সালে জোসেফ ফুরিয়ে স্বতন্ত্রভাবে প্রকাশ করেছিলেন। এই দুটি উপপাদ্য একে অপরের পরিণতি হিসেবে গণ্য হয়। ফুরিয়ে'র বক্তব্যটি ১৯ শতকের সাহিত্যিকদের মধ্যে অধিক প্রচলিত এবং এটিকে ফুরিয়ে'র, বুদান–ফুরিয়ে, ফুরিয়ে–বুদান এমনকি বুদানের উপপাদ্য হিসেবেও উল্লেখ করা হয়েছে।
বুদানের মূল ফর্মুলেশনটি দ্রুত আধুনিক অ্যালগরিদমগুলিতে ব্যবহৃত হয়, যা পলিনোমিয়ালের বাস্তব-রুট বিচ্ছেদ নির্ধারণ করতে সাহায্য করে।
ধরা যাক formula_1 হলো বাস্তব সংখ্যার একটি সসীম অনুক্রম। একটি "সাইন পরিবর্তন" বা "সাইন চেঞ্জ" সেই দুটি সূচক এর জন্য ঘটে, যখন formula_2 এবং অথবা অথবা formula_3 সকল এর জন্য, যেখানে ।
অর্থাৎ, একটি সাইন পরিবর্তন ঘটে যখন সাইন পরিবর্তিত হয়, যদি শূন্যগুলো উপেক্ষা করা হয়।
পলিনোমিয়ালের বাস্তব রুটগুলো অধ্যয়ন করার জন্য, বিভিন্ন অনুক্রমের সাইন পরিবর্তনের সংখ্যা ব্যবহার করা যেতে পারে। বুদানের উপপাদ্যের জন্য, এটি হলো কৌশলের কোফিসিয়েন্টগুলির অনুক্রম। ফুরিয়ে'র উপপাদ্যের জন্য, এটি হলো একটি বিন্দুর জন্য পরবর্তী ডেরিভেটিভগুলির মানগুলির অনুক্রম। স্টার্মের উপপাদ্য এর জন্য এটি হলো একটি বিন্দুর জন্য স্টার্ম সিকোয়েন্স এর মানগুলির অনুক্রম।
এই প্রবন্ধে বর্ণিত সমস্ত ফলাফল দেস্কার্টেসের সাইন রুলের উপর ভিত্তি করে।
যদি একটি একক ভেরিয়েবল পলিনোমিয়াল হয় যার বাস্তব কোফিসিয়েন্ট রয়েছে, তাহলে আমরা দ্বারা এর ইতিবাচক বাস্তব রুটগুলির সংখ্যা বোঝাবো, যা তাদের গুণফলসহ গণনা করা হয়, এবং দ্বারা এর কোফিসিয়েন্টের অনুক্রমে সাইন পরিবর্তনের সংখ্যা বোঝানো হয়। দেস্কার্টেস এর সাইন রুল asserts যে
বিশেষত, যদি , তবে ।
ধরা যাক একটি একক ভেরিয়েবল পলিনোমিয়াল যার বাস্তব কোফিসিয়েন্ট রয়েছে, আমরা দ্বারা বাস্তব রুটের সংখ্যা বোঝাবো, যা তাদের গুণফলসহ গণনা করা হয়, এর জন্য একটি অর্ধ-খোলা অন্তরাল (যেখানে বাস্তব সংখ্যা)। আমরা দ্বারা পলিনোমিয়াল এর কোফিসিয়েন্টগুলির অনুক্রমে সাইন পরিবর্তনের সংখ্যা বোঝাবো। বিশেষত, আমরা হিসেবে আগে উল্লিখিত নোটেশন ব্যবহার করব।
বুদানের উপপাদ্য হলো:
যেহেতু formula_5 ঋণাত্মক নয়, এটি নির্দেশ করে যে formula_6
এটি দেস্কার্টেসের সাইন রুলের একটি সাধারণীকরণ, কারণ, যদি যথেষ্ট বড় হয়, এটি এর সকল বাস্তব রুটের চেয়ে বড় হবে এবং এর সমস্ত কোফিসিয়েন্ট ইতিবাচক হবে, অর্থাৎ formula_7। সুতরাং formula_8 এবং formula_9 যা দেস্কার্টেসের সাইন রুলকে বুদানের উপপাদ্যের একটি বিশেষ ক্ষেত্র তৈরি করে।
দেস্কার্টেসের সাইন রুলের মতো, যদি formula_10 তাহলে formula_11 এর মানে হল যে, যদি formula_12 হয়, তবে একটি "শূন্য-রুট পরীক্ষা" এবং একটি "এক-রুট পরীক্ষা" রয়েছে।
১. পলিনোমিয়াল এবং খোলা অন্তরাল দেওয়া থাকলে, আমরা পাই:
তাহলে, formula_14, এবং বুদানের উপপাদ্য অনুসারে, পলিনোমিয়াল এর খোলা অন্তরালে দুইটি অথবা শূন্য বাস্তব রুট থাকবে।
২. একই পলিনোমিয়াল দিয়ে, আমরা পাই:
তাহলে, formula_16, এবং বুদানের উপপাদ্য অনুসারে, পলিনোমিয়াল এর খোলা অন্তরালে কোনো বাস্তব রুট নেই। এটি বুদানের উপপাদ্য ব্যবহারের একটি শূন্য-রুট পরীক্ষার উদাহরণ।
ফুরিয়ে'র পলিনোমিয়াল বাস্তব রুট সম্পর্কিত উপপাদ্য, যা ফুরিয়ে–বুদান উপপাদ্য অথবা বুদান–ফুরিয়ে উপপাদ্য (কখনও কখনও শুধু বুদানের উপপাদ্য নামে পরিচিত) ঠিক বুদানের উপপাদ্যের মতই, তবে এখানে এবং এর জন্য এর কোফিসিয়েন্টগুলির অনুক্রমের পরিবর্তে, এর ডেরিভেটিভগুলির অনুক্রম ব্যবহৃত হয়।
প্রতিটি উপপাদ্য অন্যটির পরিণতি হিসেবে গণ্য হয়। এটি টেলর সম্প্রসারণ থেকে উদ্ভূত:
পলিনোমিয়াল এর এ টেলর সম্প্রসারণ, যা নির্দেশ করে যে এর কোফিসিয়েন্ট হল formula_18 দ্বারা ভাগ করা এর একটি ধনাত্মক সংখ্যা। সুতরাং, ফুরিয়ে'র উপপাদ্য এবং বুদানের উপপাদ্য উভয়ের সিকোয়েন্সগুলির সাইন পরিবর্তনের সংখ্যা সমান।
এই দুটি উপপাদ্যের মধ্যে এই শক্তিশালী সম্পর্কটি ১৯ শতকে অগ্রগণ্যতা সম্পর্কিত বিতর্কের ব্যাখ্যা দিতে পারে এবং একে অন্যের জন্য বিভিন্ন নামের ব্যবহার বুঝিয়ে দিতে পারে। আধুনিক ব্যবহার অনুযায়ী, কম্পিউটার গণনায় বুদানের উপপাদ্য সাধারণত পছন্দ করা হয়, কারণ ফুরিয়ে'র উপপাদ্যে সিকোয়েন্সগুলির কোফিসিয়েন্টগুলি বুদানের উপপাদ্যের তুলনায় অনেক বড়, কারণ সেখানে ফ্যাক্টোরিয়াল ফ্যাক্টর থাকে।
যেহেতু প্রতিটি উপপাদ্য একে অপরের উপবীজগণিত, তাই ফুরিয়ে'র উপপাদ্য প্রমাণ করা যথেষ্ট।
প্রমাণ:
ধরা যাক formula_19 হল formula_20-এর ডিগ্রি, যাতে formula_21 গুলি অ-ধ্রুবক পলিনোমিয়াল, formula_22 একটি অ-শূন্য ধ্রুবক এবং formula_23 সবই অভিন্ন শূন্য।
formula_24 এর একটি ফাংশন হিসেবে, formula_25 শুধুমাত্র formula_21 এর মধ্যে যেকোনো একটি রুটে পরিবর্তন ঘটাতে পারে।
যদি formula_25 formula_28 তে পরিবর্তিত হয়, তাহলে কোন formula_29 এর জন্য, formula_30 এর একটি রুট formula_24 তে থাকবে, এবং formula_32 এর কোনো রুট formula_24 তে থাকবে না।
যদি formula_34, তাহলে formula_35 হবে যেখানে কিছু formula_36 এবং formula_37 একটি পলিনোমিয়াল হবে যা formula_38। formula_39 গুলিকে formula_40 এবং formula_41 তে একটি ছোট formula_42 এর জন্য স্পষ্টভাবে গণনা করলে, আমরা পাই formula_43।
এই সমীকরণে, formula_44 পদটি formula_45 এর সাইন পরিবর্তন থেকে উদ্ভূত যা formula_46 থেকে formula_47 তে পরিবর্তিত হয়। formula_48 পদটি উচ্চতর সাইন পরিবর্তনের কারণে শূন্য হয়ে যেতে পারে।
যদি formula_49, তাহলে যেহেতু কিছু ডেরিভেটিভ formula_40 তে শূন্য হয়, কিন্তু formula_51 এবং formula_52 অ-শূন্য থাকে, আমরা শুধুমাত্র সাইন পরিবর্তনের একটি সোজা সংখ্যা হারাই:
formula_53
যদি formula_25 formula_55 তে পরিবর্তিত হয়, তবে অনুরূপভাবে যুক্তি দিলে, আমরা দেখতে পাই যে, উভয় ক্ষেত্রে, একটি ছোট formula_42 নেওয়া যেতে পারে যাতে formula_57।
একটি পলিনোমিয়ালের বাস্তব রুট গণনা এবং তাদের অবস্থান নির্ধারণের সমস্যা শুধুমাত্র ১৯ শতকের শুরুতে সুশৃঙ্খলভাবে অধ্যয়ন করা শুরু হয়।
১৮০৭ সালে, ফ্রাঁসোয়া বুদান ডে বয়সলোরাঁ একটি পদ্ধতি আবিষ্কার করেন যার মাধ্যমে তিনি দেস্কার্টেসের সাইন রুল—যা অন্তরালে বৈধ—কোনো অন্তরালে প্রয়োগ করার জন্য সম্প্রসারিত করেন।
জোসেফ ফুরিয়ে ১৮২০ সালে একটি অনুরূপ উপপাদ্য প্রকাশ করেন, যার উপর তিনি বিশ বছরেরও বেশি সময় কাজ করেছেন।
দুটি উপপাদ্যের মধ্যে সাদৃশ্য থাকায়, একটি অগ্রাধিকার বিতর্ক সৃষ্টি হয়, যদিও দুটি উপপাদ্যই স্বাধীনভাবে আবিষ্কৃত হয়েছিল। সাধারণত ১৯ শতকে সমীকরণ তত্ত্ব সম্পর্কিত পাঠ্যবইগুলিতে ফুরিয়ে'র ফর্মুলেশন এবং প্রমাণ ব্যবহার করা হত।
বুদানের এবং ফুরিয়ে'র উপপাদ্যগুলি দ্রুতই অত্যন্ত গুরুত্বপূর্ণ হিসাবে বিবেচিত হতে থাকে, যদিও তারা একটি পলিনোমিয়ালের বাস্তব রুটের সংখ্যা একটি অন্তরালে সম্পূর্ণভাবে গণনা করার সমস্যার সমাধান দেয় না। এই সমস্যা ১৮২৭ সালে স্টার্ম দ্বারা সম্পূর্ণভাবে সমাধান করা হয়।
যদিও স্টার্মের উপপাদ্য দেস্কার্টেসের সাইন রুল এর উপর ভিত্তি করে নয়, স্টার্ম এবং ফুরিয়ে'র উপপাদ্যগুলি শুধুমাত্র সাইন পরিবর্তনের সংখ্যা ব্যবহার করার দিক থেকে সম্পর্কিত নয়, বরং সমস্যাটি সমাধানের জন্য অনুরূপ একটি দৃষ্টিভঙ্গি রয়েছে। স্টার্ম নিজেই স্বীকার করেছেন যে তিনি ফুরিয়ে'র পদ্ধতিগুলি দ্বারা প্রভাবিত হয়েছিলেন: "« 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. »" যার বাংলা অনুবাদ "« এটি তার দ্বারা প্রতিষ্ঠিত নীতিগুলির উপর ভর করে এবং তার প্রমাণগুলির অনুকরণ করে আমি যে নতুন উপপাদ্যগুলি উপস্থাপন করতে যাচ্ছি তা আবিষ্কার করেছি। »"
এ কারণে, ১৯ শতকে ফুরিয়ে'র এবং স্টার্মের উপপাদ্যগুলি প্রায় সমস্ত সমীকরণ তত্ত্ব সম্পর্কিত বইগুলিতে একসাথে উপস্থিত ছিল।
ফুরিয়ে এবং বুদান রুট খোঁজার জন্য অন্তরালের আকার কমানোর সমস্যা খোলাই রেখেছিলেন, যাতে পরিশেষে সাইন পরিবর্তনের সংখ্যা একের বেশি না হয়, এবং নিশ্চিতভাবে বলা যায় যে চূড়ান্ত অন্তরালগুলির মধ্যে প্রতি একটি অন্তত একটি রুট থাকে। এই সমস্যা ১৮৩৪ সালে ভিনসেন্ট সমাধান করেন। সংক্ষেপে, ভিনসেন্টের উপপাদ্য হচ্ছে ক্রমাগত ভগ্নাংশ ব্যবহার করে বুদানের ভেরিয়েবলের লিনিয়ার রূপান্তরগুলোকে মোবিয়াস রূপান্তর দ্বারা প্রতিস্থাপন করা।
বুদান, ফুরিয়ে এবং ভিনসেন্টের উপপাদ্যগুলি ১৯ শতকের শেষের দিকে বিস্মৃত হয়ে যায়। দ্বিতীয় বিশ্বযুদ্ধের আগে শেষ লেখক যিনি এই উপপাদ্যগুলি উল্লেখ করেছিলেন তিনি জোসেফ আলফ্রেড সেরেট। ১৯ শতকের দ্বিতীয়ার্ধে এই উপপাদ্যগুলি আবার পরিচিত হয় ১৯৭৬ সালে জর্জ ই. কলিন্স এবং আলকিভিয়াদিস জি. আক্রিতাস দ্বারা, যারা কম্পিউটার অ্যালজেব্রাতে বাস্তব রুট বিচ্ছেদ করার জন্য একটি দক্ষ অ্যালগরিদম প্রদান করেছিলেন।