রৈখিক বীজগণিত/বিষয়: নির্ণায়ক গণনার গতি/সমাধান

সমাধান

এখানকার বেশিরভাগ সমস্যা সমাধানের জন্যই কম্পিউটার থাকা প্রয়োজন।

সমস্যা ১

কম্পিউটার সিস্টেম র‍্যান্ডম বা এলোমেলো সংখ্যা তৈরি করতে পারে। (অবশ্য এগুলো কেবল ছদ্ম-এলোমেলো সংখ্যা, কারণ এরা কোনো অ্যালগরিদম দ্বারা তৈরি হয়। তবে এরা এলোমেলো হওয়ার বিভিন্ন গ্রহণযোগ্য পরিসংখ্যানিক পরীক্ষায় উত্তীর্ণ হয়)।

1. $5\!\times \!5$ আকারের একটি অ্যারে এলোমেলো সংখ্যা দিয়ে পূরণ করুন (ধরি, বিস্তার $[0..1)$)। দেখুন এটি সিঙ্গুলার কি না। এই পরীক্ষাটি কয়েকবার পুনরাবৃত্তি করুন। (এই অর্থে) সিঙ্গুলার ম্যাট্রিক্স কি প্রায়ই দেখা যায় নাকি বিরল?
2. আপনার কম্পিউটার অ্যালজেব্রা সিস্টেমে এলোমেলো সংখ্যাযুক্ত দশটি $5\!\times \!5$ অ্যারের নির্ণায়ক বের করতে কত সময় লাগে তা পরিমাপ করুন। প্রতিটি অ্যারের জন্য গড় সময় বের করুন। $15\!\times \!15$, $25\!\times \!25$ এবং $35\!\times \!35$ অ্যারের জন্যও পূর্ববর্তী কাজটি পুনরাবৃত্তি করুন। (খেয়াল করুন, কোনো অ্যারে সিঙ্গুলার হলে তা মাঝে মাঝে খুব দ্রুতই বোঝা যায়। উদাহরণস্বরূপ, যদি প্রথম সারিটি দ্বিতীয়টির সমান হয়। প্রথম অংশের উত্তরের আলোকে, আপনি কি মনে করেন যে আপনার প্রাপ্ত গড় সময়ের ক্ষেত্রে সিঙ্গুলার সিস্টেমগুলো বড় কোনো প্রভাব ফেলবে?)
3. গড় সময়ের বিপরীতে ইনপুটের আকারের একটি লেখচিত্র আঁকুন।

উত্তর

1. অক্টেভ-এ rank(rand(5)) কমান্ডটি একটি $5\!\times \!5$ ম্যাট্রিক্সের র‍্যাংক বের করে। এর ভুক্তিগুলো $[0..1)$ ব্যবধিতে (সুষমভাবে বন্টিত) থাকে। নিচের লুপটি পরীক্ষাটি ৫০০০ বার চালায়: octave:1> for i=1:5000
   > if rank(rand(5))<5 printf("That's one."); endif
   > endfor
   এটি (কয়েক সেকেন্ড পর) কোনো আউটপুট ছাড়াই প্রম্পটটি ফেরত দেয়। অক্টেভ স্ক্রিপ্ট:
   
   function elapsed_time = detspeed (size)
   a=rand(size);
   tic();
   for i=1:10
   det(a);
   endfor
   elapsed_time=toc();
   endfunction
   
   
   নিচের সেশনটি তৈরি করে।
   
   octave:1> detspeed(5)
   ans = 0.019505
   octave:2> detspeed(15)
   ans = 0.0054691
   octave:3> detspeed(25)
   ans = 0.0097431
   octave:4> detspeed(35)
   ans = 0.017398
   
2. এখানে উপাত্তগুলো (সামান্য পূর্ণসংখ্যায় রূপান্তর করে) এবং লেখচিত্রটি দেওয়া হলো।

   ${\begin{array}{r|ccccccccc}{\text{ম্যাট্রিক্স সারি}}&15&25&35&45&55&65&75&85&95\\\hline {\text{দশটির জন্য সময়}}&0.0034&0.0098&0.0675&0.0285&0.0443&0.0663&0.1428&0.2282&0.1686\end{array}}$

   (এই উপাত্তগুলো উপরের স্ক্রিপ্টটি বিশবার চালিয়ে তার গড় করে নেওয়া হয়েছে। কারণ নির্বাচিত এলোমেলো ম্যাট্রিক্সগুলো মাঝে মাঝে অস্বাভাবিক রকম বেশি বা কম সময় নিতে পারে। তা সত্ত্বেও, এই সময়ের ওপর খুব বেশি নির্ভর করা ঠিক হবে না। এটি কেবলই একটি পরীক্ষা)।

   

সমস্যা ২

উপরে আলোচিত দুটি পদ্ধতি ব্যবহার করে নিচের প্রত্যেকটির নির্ণায়ক হাতে-কলমে হিসাব করুন।

1. ${\begin{vmatrix}2&1\\5&-3\end{vmatrix}}$
2. ${\begin{vmatrix}3&1&1\\-1&0&5\\-1&2&-2\end{vmatrix}}$
3. ${\begin{vmatrix}2&1&0&0\\1&3&2&0\\0&-1&-2&1\\0&0&-2&1\end{vmatrix}}$

প্রতিটি পদ্ধতির ক্ষেত্রে কয়টি গুণ ও ভাগ ব্যবহার করা হয়েছে তা গণনা করুন। (কম্পিউটারে যোগ ও বিয়োগের চেয়ে গুণ ও ভাগ করতে অনেক বেশি সময় লাগে। তাই অ্যালগরিদম প্রণেতারা এগুলো নিয়ে বেশি চিন্তিত থাকেন)।

উত্তর

কয়টি অপারেশন লাগবে তা মূলত অপারেশনগুলো কীভাবে সম্পাদন করা হচ্ছে তার ওপর নির্ভর করে।

1. নির্ণায়কটি হলো $-11$। সারি কমানোর জন্য দুটি গুণসহ একটিমাত্র পিভট প্রয়োজন হয় ($2$-এর সাথে $-5/2$ গুণ করে $5$-এর সাথে যোগ এবং $1$-এর সাথে $-5/2$ গুণ করে $-3$-এর সাথে যোগ)। প্রধান কর্ণ বরাবর গুণ করতে আরও একটি গুণের প্রয়োজন হয়। বিন্যাস সম্প্রসারণে দুটি গুণের প্রয়োজন হয় ($2$-এর সাথে $-3$ গুণ এবং $5$-এর সাথে $1$ গুণ)।
2. নির্ণায়কটি হলো $-39$। অপারেশনগুলো গণনা করা একটি সাধারণ কাজ।
3. নির্ণায়কটি হলো $4$।

সমস্যা ৩

আপনি কি এমন কোনো $10\!\times \!10$ অ্যারে তৈরি করতে পারেন যা কমাতে আপনার কম্পিউটার সিস্টেমের সবচেয়ে বেশি সময় লাগবে? সবচেয়ে কম সময় লাগবে কোনটিতে?

উত্তর

এটি শুরু করার একটি উপায় হলো অক্টেভে এগুলো তুলনা করা: det(rand(10));, এর বিপরীতে det(hilb(10));, এর বিপরীতে det(eye(10)); এবং এর বিপরীতে det(zeroes(10));। আপনি tic(); det(rand(10)); toc() ব্যবহার করে এদের সময় পরিমাপ করতে পারেন।

সমস্যা ৪

গাউসের পদ্ধতির মাধ্যমে নির্ণায়ক গণনার সরাসরি প্রয়োগের জন্য ফোরট্রান (FORTRAN) প্রোগ্রামটির বাকি অংশ লিখুন। (শূন্য পিভটের জন্য পরীক্ষা করার প্রয়োজন নেই)। আপনার কম্পিউটার অ্যালজেব্রা সিস্টেমে ব্যবহৃত কোডের সাথে আপনার কোডটির গতির তুলনা করুন।

উত্তর

এটি বেশ সহজ।

DO 5 ROW=1, N
PIVINV=1.0/A(ROW,ROW)
DO 10 I=ROW+1, N
DO 20 J=I, N
A(I,J)=A(I,J)-PIVINV*A(ROW,J)
20 CONTINUE
10 CONTINUE
5 CONTINUE

সমস্যা ৫

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

উত্তর

হ্যাঁ, কারণ $J$ সবচেয়ে ভেতরের লুপে অবস্থিত।