Gauss–Legendre quadrature
সংখ্যাসূচক বিশ্লেষণে, গাউস-লেজেন্ড্রে চতুর্ভুজ একটি ফাংশনের নির্দিষ্ট অবিচ্ছেদ্যকে আনুমানিক করার জন্য গাউসিয়ান চতুর্ভুজের একটি রূপ। ব্যবধানের উপর একীকরণের জন্য, নিয়মটি এই রূপ নেয়ঃ যেখানে n হল ব্যবহৃত নমুনা বিন্দুর সংখ্যা, wi হল চতুর্ভুজ ওজন, এবং xi হল nতম কিংবদন্তি বহুপদের মূল। চতুর্ভুজ ওজনের এই পছন্দটি ওয়াই এবং চতুর্ভুজ নোড xi হল অনন্য পছন্দ যা চতুর্ভুজ নিয়মকে ডিগ্রি বহুপদগুলিকে সঠিকভাবে সংহত করার অনুমতি দেয়। গাউস-লেজেন্ড্রে চতুর্ভুজ নিয়ম গণনা করার জন্য অনেক অ্যালগরিদম তৈরি করা হয়েছে। 1969 সালে উপস্থাপিত গোলুব-ওয়েলশ অ্যালগরিদম নোড এবং ওজনের গণনাকে একটি আইগেনভ্যালু সমস্যায় হ্রাস করে যা কিউআর অ্যালগরিদম দ্বারা সমাধান করা হয়। এই অ্যালগরিদমটি জনপ্রিয় ছিল, তবে উল্লেখযোগ্যভাবে আরও কার্যকর অ্যালগরিদম বিদ্যমান। নিউটন-রাফসন পদ্ধতির উপর ভিত্তি করে অ্যালগরিদমগুলি উল্লেখযোগ্যভাবে বড় সমস্যার আকারের জন্য চতুর্ভুজ নিয়ম গণনা করতে সক্ষম। 2014 সালে, ইগ্নেস বোগার্ট গাউস-লেজেন্ড্রে চতুর্ভুজ ওজন এবং নোডের জন্য স্পষ্ট অ্যাসিম্পটোটিক সূত্র উপস্থাপন করেছিলেন, যা ডাবল-প্রিসিশন মেশিনের এপসাইলনের মধ্যে যে কোনও পছন্দের জন্য সঠিক। এটি এক বিলিয়নের বেশি n মানের জন্য নোড এবং ওজনের গণনার অনুমতি দেয়। ইতিহাস কার্ল ফ্রেডরিখ গাউস প্রথম গাউস-লেজেন্ড্রে চতুর্ভুজ নিয়মটি অর্জন করেছিলেন, 1814 সালে অব্যাহত ভগ্নাংশের সাথে একটি গণনার মাধ্যমে এটি করেছিলেন। তিনি নোড এবং ওজনগুলি 16 অঙ্ক পর্যন্ত গণনা করেছিলেন যাতে হাতে এন = 7 অর্ডার করা যায়। কার্ল গুস্তাভ জ্যাকব জ্যাকোবি চতুর্ভুজ নিয়ম এবং লেজেন্ড্রে বহুপদীর অর্থোগোনাল পরিবারের মধ্যে সংযোগ আবিষ্কার করেন। যেহেতু চতুর্ভুজ ওজন এবং নোডের জন্য কোনও বদ্ধ-ফর্ম সূত্র নেই, বহু দশক ধরে লোকেরা কেবল ছোট এন-এর জন্য এগুলি হাতে-গণনা করতে সক্ষম হয়েছিল এবং ওজন এবং নোড মানযুক্ত টেবিলগুলি উল্লেখ করে চতুর্ভুজ গণনা করতে হয়েছিল। 1942 সালের মধ্যে এই মানগুলি শুধুমাত্র n = 16 পর্যন্ত পরিচিত ছিল। সংজ্ঞা গাউস-লেজেন্ড্রে চতুর্ভুজের সাথে f কে একীভূত করার জন্য, সংশ্লিষ্ট অর্থোগোনাল বহুপদগুলি হল লেজেন্ড্রে বহুপদী, যা দ্বারা চিহ্নিত করা হয়। - তম পলিনোমিয়ালটি স্বাভাবিক করা হয়েছে যাতে,-তম গাউস নোড, এর-তম মূল হয় এবং ওজনগুলি সূত্র দ্বারা দেওয়া হয় কিছু নিম্ন-ক্রমের চতুর্ভুজ নিয়মগুলি সংহত করার জন্য নীচে সারণীবদ্ধ করা হয়েছে। একটি সাধারণ বাস্তব ব্যবধানের উপর একীকরণের জন্য, ব্যবধানের পরিবর্তন প্রয়োগ করা যেতে পারে যাতে সমস্যাটিকে একীকরণের একটিতে রূপান্তরিত করা যায়। অ্যালগরিদম নিউটন-রাফসন পদ্ধতি বেশ কয়েকজন গবেষক ফাংশনের মূল খুঁজে বের করার জন্য নিউটন-রাফসন পদ্ধতির উপর ভিত্তি করে গাউস-লেজেন্ড্রে চতুর্ভুজ নোড এবং ওজন গণনা করার জন্য অ্যালগরিদম তৈরি করেছেন। এই নির্দিষ্ট সমস্যার জন্য বিভিন্ন অপ্টিমাইজেশান ব্যবহার করা হয়। উদাহরণস্বরূপ, কিছু পদ্ধতি ব্যবধানের শেষের কাছাকাছি শিকড়ের ক্লাস্টারিংয়ের সাথে সম্পর্কিত সমস্যাগুলি এড়াতে গণনা করে এবং। কিছু পদ্ধতি ওজন আনুমানিক করার জন্য সূত্র ব্যবহার করে এবং তারপরে নিউটন-রাফসনের কয়েকটি পুনরাবৃত্তি ব্যবহার করে আনুমানিক ত্রুটিকে মেশিনের নির্ভুলতার নিচে নামিয়ে আনে। 1969 সালে, গোলুব এবং ওয়েলশ গাউসিয়ান চতুর্ভুজের নিয়মগুলি গণনার জন্য তাদের পদ্ধতি প্রকাশ করেছিলেন যা তিনটি পদের পুনরাবৃত্তির সম্পর্ককে দেওয়া হয়েছিল যা অন্তর্নিহিত অর্থোগোনাল বহুপদগুলি সন্তুষ্ট করে। তারা একটি গাউসিয়ান চতুর্ভুজ নিয়মের নোডগুলি গণনা করার সমস্যাটিকে একটি নির্দিষ্ট প্রতিসম ত্রিভুজ ম্যাট্রিক্সের আইগেনভ্যালুগুলি খুঁজে বের করার সমস্যায় হ্রাস করে। এই ম্যাট্রিক্সের আইগেনভ্যালু খুঁজে বের করতে কিউআর অ্যালগরিদম ব্যবহার করা হয়। প্রতিসম ত্রিভুজাকার কাঠামোর সুবিধা গ্রহণ করে, সাধারণ আইগেনভ্যালু সমস্যার জন্য প্রত্যাশিত সময়ের বিপরীতে আইগেনভ্যালুগুলি সময়মতো গণনা করা যেতে পারে। উপসর্গহীন সূত্র বিভিন্ন পদ্ধতি তৈরি করা হয়েছে যা নোডগুলি গণনা করার জন্য আনুমানিক বদ্ধ-ফর্ম অভিব্যক্তি ব্যবহার করে। উপরে উল্লিখিত হিসাবে, কিছু পদ্ধতিতে সূত্রগুলি নোডগুলির আনুমানিক হিসাবে ব্যবহৃত হয়, যার পরে কিছু নিউটন-রাফসন পুনরাবৃত্তি করা হয় আনুমানিককে পরিমার্জন করার জন্য। 2014 সালের একটি গবেষণাপত্রে, ইগনেস বোগার্ট নোডগুলির জন্য অ্যাসিম্পটোটিক সূত্রগুলি বের করেছেন যা মেশিনের নির্ভুলতার জন্য এবং ওজনের জন্য যা মেশিনের নির্ভুলতার জন্য সঠিক। এই পদ্ধতিতে অন্যান্য পদ্ধতির মতো কোনও নিউটন-রাফসন পুনরাবৃত্তি বা বেসেল ফাংশনের মূল্যায়নের প্রয়োজন হয় না। গবেষণাপত্রে যেমন দেখানো হয়েছে, পদ্ধতিটি 11 সেকেন্ডে এক বিলিয়ন সমস্যার আকারে নোডগুলি গণনা করতে সক্ষম হয়েছিল। যেহেতু শেষ বিন্দুর কাছাকাছি নোডগুলি এই সমস্যার আকারে একে অপরের খুব কাছাকাছি হয়ে যায়, তাই নোডগুলি গণনা করার এই পদ্ধতিটি মূলত ডাবল-প্রিসিশন ভাসমান বিন্দুতে যে কোনও ব্যবহারিক প্রয়োগের জন্য যথেষ্ট। উচ্চ নির্ভুলতা জোহানসন এবং মেজারোব্বা নির্বিচারে-নির্ভুলতা গাণিতিক পদ্ধতিতে গাউস-লেজেন্ড্রে চতুর্ভুজ নিয়ম গণনা করার একটি কৌশল বর্ণনা করেছেন, যা ছোট এবং বড় উভয়কেই অনুমতি দেয়। 1000 অঙ্কের নির্ভুলতার একটি নিয়ম প্রায় এক সেকেন্ডে গণনা করা যেতে পারে। তাদের পদ্ধতিটি নিউটন-রাফসন পুনরাবৃত্তি সহ বিভিন্ন কৌশল ব্যবহার করে লেজেন্ড্রে বহুপদী মূল্যায়নের জন্য। অ্যালগরিদমটি একটি প্রত্যয়িত ত্রুটি আবদ্ধও প্রদান করে। গিল, সেগুরা এবং টেমে গাউস-জ্যাকোবি চতুর্ভুজের (এবং, বিশেষত, গাউস-লেজেন্ড্রে) গণনার জন্য চতুর্থ ক্রমের অভিসারের সাথে পুনরাবৃত্তিমূলক পদ্ধতিগুলি বর্ণনা করেছেন। পদ্ধতিগুলির চতুর্থ-ক্রমের সমন্বয় নিশ্চিত করার জন্য নোডগুলির একটি অগ্রাধিকার অনুমানের প্রয়োজন হয় না। এমনকি লক্ষ লক্ষ নোড এবং হাজার হাজার অঙ্কের চতুর্ভুজ নিয়মের গণনা একটি সাধারণ ল্যাপটপে সম্ভব হয়। অন্যান্য চতুর্ভুজ নিয়মের সাথে তুলনা গাউস-লেজেন্ড্রে চতুর্ভুজ একটি f ওভার ফাংশনের ইন্টিগ্রাল গণনা করার জন্য খুব সংকীর্ণ অর্থে সর্বোত্তম, যেহেতু অন্য কোনও চতুর্ভুজ নিয়ম n নমুনা পয়েন্ট ব্যবহার করার সময় সমস্ত ডিগ্রি বহুপদকে সঠিকভাবে সংহত করে না। যাইহোক, নির্ভুলতার এই পরিমাপ সাধারণত খুব দরকারী নয়-- বহুপদগুলি সংহত করা খুব সহজ এবং এই যুক্তিটি নিজেই অন্যান্য ফাংশনগুলিকে সংহত করার ক্ষেত্রে আরও ভাল নির্ভুলতার গ্যারান্টি দেয় না। ক্লেনশ-কার্টিস চতুর্ভুজ চেবিশেভ নোডে একটি পলিনোমিয়াল ইন্টারপোলেন্ট দ্বারা আনুমানিক f-এর উপর ভিত্তি করে এবং ঠিক যখন n নমুনা দেওয়া হয় তখন n পর্যন্ত মাত্রার পলিনোমিয়ালগুলিকে সংহত করে। যদিও এটি বহুপদী বা অন্যান্য ফাংশনগুলিকে সংহত করে না যা গাউস-লেজেন্ড্রে চতুর্ভুজের পাশাপাশি একটি বড় পাড়ায় বিশ্লেষণাত্মক, ক্লেনশ-কার্টিস বেশিরভাগ (অ-বিশ্লেষণাত্মক) ইন্টিগ্র্যাণ্ডের জন্য গাউস-লেজেন্ড্রে চতুর্ভুজের প্রায় একই হারে একত্রিত হয়। এছাড়াও, ক্লেনশ-কার্টিস সেই বৈশিষ্ট্যগুলি ভাগ করে নেয় যা গাস-লেজেন্ড্রে চতুর্ভুজ সমস্ত অবিচ্ছিন্ন ইন্টিগ্র্যান্ড f-এর জন্য অভিসরণ এবং সংখ্যাসূচক বৃত্তাকার ত্রুটির জন্য দৃust়তা উপভোগ করে। ক্লেনশ-কার্টিস এফ. এফ. টি-ভিত্তিক পদ্ধতির মাধ্যমে সময়মতো বাস্তবায়ন করা সহজ। নিউটন-কোটস চতুর্ভুজটি একটি বহুপদী ইন্টারপোলেন্ট দ্বারা সমান-ব্যবধানের বিন্দুতে আনুমানিক f-এর উপর ভিত্তি করে এবং ক্লেনশ-কার্টিসের মতো এন নমুনা দেওয়া হলে ঠিক এন পর্যন্ত ডিগ্রির বহুপদগুলিকেও সংহত করে। যাইহোক, এন বৃদ্ধির সাথে সাথে এটি রুঞ্জের ঘটনায় ভুগছে; নিউটন-কোটস কিছু অবিচ্ছিন্ন ইন্টিগ্র্যাণ্ডের জন্য একত্রিত হয় না এবং যখন এটি একত্রিত হয় তখন এটি সংখ্যাসূচক বৃত্তাকার ত্রুটিতে ভুগতে পারে। এইভাবে, ক্লেনশ-কার্টিস এবং গাউস-লেজেন্ড্রে উভয়ই মাঝারি থেকে বড় এন-এর জন্য নিউটন-কোটসের তুলনায় যথেষ্ট সুবিধা উপভোগ করে।