✖

রৈখিক সমীকরণজোট

রৈখিক সমীকরণজোট (system of linear equations) হলো n টি চলকবিশিষ্ট m টি রৈখিক সমীকরণের একটি সেট। সমীকরণজোট সমাধান করে আমরা এমন মান পাই, যা আমাদের n টি চলকের জায়গায় বসালে সব সমীকরণ সত্য হয়।

রৈখিক সমীকরণজোটের সংজ্ঞা

তুমি নিশ্চয়ই এ ধরনের সহজ সমীকরণজোট আগে দেখেছ

a11x+a12y=b1a21x+a22y=b2

যেখানে a11,…,a22, b1, b2 প্রদত্ত বাস্তব সংখ্যা এবং x ও y চলক। সাধারণ রৈখিক সমীকরণের মতোই এই সমীকরণজোটের সমাধানের সংখ্যা ভিন্ন হতে পারে — কোনো সমাধান নেই, একটি সমাধান, অথবা অসংখ্য সমাধান। রৈখিক সমীকরণজোটের ক্ষেত্রে সমাধানের সংখ্যা এবং সমাধান খুঁজে বের করার প্রশ্নটি একটি সহজ রৈখিক সমীকরণের চেয়ে জটিল।

রৈখিক সমীকরণজোটের সংজ্ঞা:

a11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2⋮⋮⋮⋮⋮⋮⋮⋮⋮am1x1+am2x2+…+amnxn=bm

যেখানে a11, …, amn, b1, …, bm হলো বাস্তব সংখ্যা। এই জোটকে বলা হয় n টি অজ্ঞাত রাশি x1, …, xn এবং সহগ a11, …, amn বিশিষ্ট m টি রৈখিক সমীকরণের জোট। রৈখিক সমীকরণজোটের একটি নির্দিষ্ট উদাহরণ দেখতে এমন হতে পারে:

3x1+−2x2+4x3+5x4=15x1+4x2+2x3+−10x4=211x1+8x2+10x3+20x4=4

তবে কোনো aij ঋণাত্মক হলে সাধারণত এভাবে লেখা হয়:

3x1−2x2+4x3+5x4=15x1+4x2+2x3−10x4=211x1+8x2+10x3+20x4=4

তবু এখানেও a12 = −2 এবং a24 = −10।

ম্যাট্রিক্স আকারে লেখা

এই সমীকরণজোটকে আমরা ম্যাট্রিক্স আকারে রূপান্তর করতে পারি। মোট তিনটি ম্যাট্রিক্স সংজ্ঞায়িত করি: একটি সহগের জন্য, একটি সমীকরণগুলোর ডানপক্ষের জন্য এবং একটি চলকগুলোর জন্য। ম্যাট্রিক্সগুলো দেখতে এমন হবে:

A=(a11a12…a1na21a22…a2n⋮⋮⋱⋮am1am2…amn),b=(b1b2⋮bm),x=(x1x2⋮xn)

ম্যাট্রিক্স A তে মূল সমীকরণগুলোর সহগ আছে, একে বলি “সহগ ম্যাট্রিক্স” (coefficient matrix)। ম্যাট্রিক্স b তে আছে সমীকরণগুলোর ডানপক্ষ, আর ম্যাট্রিক্স x এ আছে চলকগুলো। তখন পুরো সমীকরণজোটকে একটি সমীকরণ হিসেবে লেখা যায়

Ax=b

এই সমীকরণের অর্থ আছে, কারণ বামপক্ষে আছে দুইটি ম্যাট্রিক্সের গুণফল এবং ডানপক্ষে একটি ম্যাট্রিক্স, আর এদের ক্রম মিলে যায়। বামপক্ষের গুণটি করে দেখি। আমরা m × n ক্রমের ম্যাট্রিক্সকে n × 1 ক্রমের ম্যাট্রিক্স দিয়ে গুণ করছি, তাই ফলাফলের ম্যাট্রিক্সের ক্রম হবে m × 1, এতে m টি সারি ও একটি কলাম থাকবে। এ পর্যন্ত সব ঠিক আছে।

এবার ম্যাট্রিক্স গুণের প্রচলিত অ্যালগরিদম প্রয়োগ করি, শুরু করি ম্যাট্রিক্স A এর প্রথম সারি এবং ম্যাট্রিক্স x এর প্রথম কলাম দিয়ে (অন্য কোনো কলাম সেখানে নেই)। পাই:

a11x1+a12x2+…+a1nxn

এই যোগফল থেকে আমরা নতুন ম্যাট্রিক্সের প্রথম উপাদান, অর্থাৎ b1 এর মান পেলাম। পুরোটা সমীকরণে বসালে পাই:

a11x1+a12x2+…+a1nxn=b1

আমরা ঠিক আমাদের সমীকরণজোটের প্রথম সমীকরণটি পেলাম। অন্য সারিগুলোর জন্যও একইভাবে এগোনো যায়। এবার বর্ধিত ম্যাট্রিক্স (augmented matrix) সংজ্ঞায়িত করি, যা হলো সহগ ম্যাট্রিক্সের সঙ্গে ম্যাট্রিক্স b এভাবে যুক্ত করে পাওয়া ম্যাট্রিক্স:

B=(A|b)=(a11a12…a1nb1a21a22…a2nb2⋮⋮⋱⋮⋮am1am2…amnbm)

এরপর আমাদের আগ্রহ থাকবে এই বর্ধিত ম্যাট্রিক্সের র‍্যাঙ্ক নিয়ে। মূল (অবর্ধিত) সহগ ম্যাট্রিক্সের র‍্যাঙ্ককে লিখব rank(A), আর বর্ধিত ম্যাট্রিক্সের র‍্যাঙ্ক rank(A|b)। এই দুইটি র‍্যাঙ্কের মধ্যে সম্পর্ক কী? ম্যাট্রিক্স A এর সঙ্গে কলাম b যুক্ত করলে দুইটি অবস্থা হতে পারে: নতুন কলামটি যদি ম্যাট্রিক্স A এর কলামগুলোর রৈখিক সমাবেশ হয়, তাহলে র‍্যাঙ্ক বদলায় না। রৈখিক সমাবেশ না হলে র‍্যাঙ্ক এক বেড়ে যাবে।

রুশে–কাপেলির উপপাদ্য

বর্ধিত ম্যাট্রিক্সের র‍্যাঙ্ক আমাদের জন্য গুরুত্বপূর্ণ হবে, কারণ একটি গুরুত্বপূর্ণ উপপাদ্য আছে, রুশে–কাপেলির উপপাদ্য (Rouché–Capelli theorem, কোথাও ফ্রোবেনিয়াসের উপপাদ্য নামেও পরিচিত): সমীকরণজোট Ax = b এর সমাধান থাকে যদি এবং কেবল যদি সহগ ম্যাট্রিক্সের র‍্যাঙ্ক বর্ধিত ম্যাট্রিক্সের র‍্যাঙ্কের সমান হয়: rank(A) = rank(A|b)।

এবার দেখাই যে উপপাদ্যটি অন্তত এক দিকে সত্য — যদি x = β সমীকরণ Ax = b এর একটি সমাধান হয়, তাহলে rank(A) = rank(A|b)। এই র‍্যাঙ্ক দুইটি সমান হতে হলে কলাম b কে ম্যাট্রিক্স A এর কলামগুলোর রৈখিক সমাবেশ হতে হবে। বিস্তারিত লিখি। ম্যাট্রিক্স β দেখতে এমন:

β=(β1β2⋮βn)

আর আমাদের দাবি হলো, x1 এর জায়গায় β1 ইত্যাদি বসালে সমীকরণজোটের সব সমীকরণ সত্য হবে:

a11β1+a12β2+…+a1nβn=b1a21β1+a22β2+…+a2nβn=b2⋮⋮⋮⋮⋮⋮⋮⋮⋮am1β1+am2β2+…+amnβn=bm

এবার সমীকরণগুলো একটু অন্যভাবে লিখি। প্রথম কলামটি দেখলে দেখা যায়, সেখানে সবসময় a11, a21, …, am1 মানগুলো আছে, যাদের একই মান β1 দিয়ে গুণ করা হয়েছে। কলামটিকে আলাদা একটি ম্যাট্রিক্স হিসেবে নিলে মান β1 কে ম্যাট্রিক্সের সামনে সাধারণ উৎপাদক হিসেবে বের করে আনা যায়, এতে পাই:

(a11β1a21β1⋮am1β1)=β1(a11a21⋮am1)

এভাবে পুরো সমীকরণজোটটি নতুন করে লিখতে পারি:

β1(a11a21⋮am1)+β2(a12a22⋮am2)+…+βn(a1na2n⋮amn)=(b1b2⋮bm)

এই সমীকরণ সত্য হতে হলে ডানপক্ষের ম্যাট্রিক্সকে বামপক্ষের কলাম ম্যাট্রিক্সগুলোর রৈখিক সমাবেশ হতে হবে, আর β1, …, βn মানগুলোকে হতে হবে এদের সহগ।

এভাবে আমরা প্রমাণ করলাম যে ম্যাট্রিক্স β সমীকরণজোটের সমাধান হলে জোটের ডানপক্ষ, অর্থাৎ ম্যাট্রিক্স b কে সহগ ম্যাট্রিক্সের কলামগুলোর রৈখিক সমাবেশ হতে হবে। আর ম্যাট্রিক্স b এর কলামটি যদি ম্যাট্রিক্স A এর কলামগুলোর রৈখিক সমাবেশ হয়, তাহলে ম্যাট্রিক্স A এর র‍্যাঙ্ক ম্যাট্রিক্স (A|b) এর র‍্যাঙ্কের সমান হতেই হবে।

একই সঙ্গে সত্য যে, যদি rank(A) = rank(A|b) = k হয় এবং k অজ্ঞাত রাশির সংখ্যার সমান হয়, অর্থাৎ k = n, তাহলে সমীকরণজোটের ঠিক একটি সমাধান আছে। যদি k < n হয়, তাহলে সমীকরণজোটের অসংখ্য সমাধান আছে, এবং এদের লিখতে আমাদের n − k টি পরামিতি লাগবে।

প্রাথমিক সারি রূপান্তর

আগের সমীকরণ থেকে এটাও দেখা যায় যে ম্যাট্রিক্স (A|b) এ প্রাথমিক সারি রূপান্তর করলে সমীকরণজোটের সমাধান বদলায় না। যদি দ্বিতীয় সারির সঙ্গে প্রথম সারি যোগ করি, তাহলে এই সমীকরণ পাই:

β1(a11a21+a11⋮am1)+β2(a12a22+a12⋮am2)+…+βn(a1na2n+a1n⋮amn)=(b1b2+b1⋮bm)

দ্বিতীয় সারিটি বিস্তারিত লিখলে পাই:

β1(a21+a11)+β2(a22+a12)+…+βn(a2n+a1n)=b1+b2

বন্ধনী খুলে গুণ করি:

β1a21+β1a11+β2a22+β2a12+…+βna2n+βna1n=b1+b2

এবার পদগুলো একটু সাজিয়ে নিই:

(β1a11+β2a12+…+βna1n)+(β1a21+β2a22+…+βna2n)=b1+b2

প্রথম বন্ধনীতে আসলে আছে প্রথম সারি, আর দ্বিতীয় বন্ধনীতে মূল দ্বিতীয় সারি। আমরা জানি প্রথম সারিটি b1 এর সমান এবং দ্বিতীয় সারিটি b2 এর সমান। এটি মূল সমীকরণগুলো থেকেই জানি। তাই প্রথম বন্ধনীর জায়গায় b1 এবং দ্বিতীয়টির জায়গায় b2 লিখতে পারি:

b1+b2=b1+b2.

একইভাবে পুরো সারিকে একটি ধ্রুবক c ≠ 0 দিয়ে গুণ করলেও সমীকরণজোটের সত্যতা বদলায় না। তবে সাবধান, কলাম রূপান্তর এখানে করা যায় না।

একটি সমাধান বিশিষ্ট সমীকরণজোট

একটি উদাহরণে দেখাব, ঠিক একটি সমাধান বিশিষ্ট সমীকরণজোট কীভাবে সমাধান করা যায়। এই সমীকরণজোটটি নিই:

2x1+3x2+7x3=473x1+8x2+x3=503x2+3x3=27

ম্যাট্রিক্স A দেখতে এমন হবে:

A=(237381033)

এবার এই ম্যাট্রিক্সের র‍্যাঙ্ক নির্ণয় করি:

(237381033)∼(69216162033)∼(692107−19033)∼(6921021−5702121)∼(6921021−570078)

দেখা যাচ্ছে rank(A) = 3। এ থেকে এটাও আসে যে rank(A|b) = 3, কারণ 3 × 4 ক্রমের ম্যাট্রিক্সের র‍্যাঙ্ক সর্বোচ্চ তিন হতে পারে। জোটে তিনটি অজ্ঞাত রাশি আছে, তাই পুরো সমীকরণজোটের ঠিক একটি সমাধান আছে। এটি কীভাবে খুঁজে পাব?

গাউসীয় অপনয়ন পদ্ধতি

গাউসীয় অপনয়ন (Gaussian elimination) হলো বর্ধিত ম্যাট্রিক্সকে সারি সোপান আকারে রূপান্তর করা। ম্যাট্রিক্সকে সারি সোপান আকারে আনলে আমরা একটি চলকের মান বের করতে পারব। একটি চলকের মান পাওয়ার পর সেই মান অন্য সমীকরণগুলোতে বসাতে শুরু করতে পারি।

ম্যাট্রিক্স (A|b) দেখতে এমন:

(A|b)=(237473815003327)

একে সারি সোপান আকারে আনি। আগের ধাপের মতোই একই রূপান্তর করব, শুধু এবার চতুর্থ কলামেও এগুলো প্রয়োগ করব:

(237473815003327)∼(6921141616210003327)∼(692114107−19−4103327)∼(6921141021−57−12302121189)∼(6921141021−57−1230078312)

আমরা প্রাথমিক সারি রূপান্তর করেছি, তাই এই ম্যাট্রিক্সটি একটি সমতুল্য সমীকরণজোট বর্ণনা করে — এমন জোট, যার সমাধান সেট একই। আমাদের শেষ ম্যাট্রিক্সের সহগগুলো ব্যবহার করে সমীকরণজোটটিকে ম্যাট্রিক্স আকার থেকে সাধারণ আকারে লিখি:

6x1+9x2+21x3=14121x2−57x3=−12378x3=312

এবার শেষ সমীকরণ থেকে শুরু করি। এটি বলে 78x3 = 312। x3 এর মান কত হতে হবে? এটি একটি সহজ রৈখিক সমীকরণ, তাই

78x3=312x3=31278x3=4

প্রথম চলক x3 এর মান পেলাম। এই মান দ্বিতীয় সমীকরণে বসাই। এই সমীকরণ পাই:

21x2−57x3=−12321x2−57⋅4=−12321x2=−123+22821x2=105x2=10521x2=5

আর শেষে নির্ণীত দুইটি মানই প্রথম সমীকরণে বসাই:

6x1+9x2+21x3=1416x1+9⋅5+21⋅4=1416x1+45+84=1416x1=12x1=2

চলক x1 এর মান দুই। এখন আমাদের হাতে সম্পূর্ণ সমাধান আছে। আমরা লিখতে পারি x = (x1, x2, x3) = (2, 5, 4)। দেখতেই পাচ্ছ, গাউসীয় অপনয়ন পদ্ধতি রৈখিক সমীকরণজোট সমাধানের একটি সহজ অথচ কার্যকর পদ্ধতি।

অসংখ্য সমাধান

যদি rank(A) = rank(A|b) = k হয় এবং k অজ্ঞাত রাশির সংখ্যার চেয়ে ছোট হয়, k < n, তাহলে সমীকরণজোটের অসংখ্য সমাধান আছে। একটি সহজ উদাহরণ নিই:

4x1+x2=512x1+3x2=15

দেখা যাচ্ছে, দ্বিতীয় সমীকরণটি প্রথম সমীকরণের তিনগুণ। প্রথম সমীকরণকে মাইনাস তিন দিয়ে গুণ করে দ্বিতীয় সারির সঙ্গে যোগ করলে পাই:

4x1+x2=50x1+0x2=0

এখন চলকের সংখ্যা দুই, n = 2, সহগ ম্যাট্রিক্সের র‍্যাঙ্ক এক, rank(A) = 1, আর বর্ধিত ম্যাট্রিক্সের র‍্যাঙ্কও এক, rank(A|b) = 1। এখানে k < n, তাই জোটের অসংখ্য সমাধান আছে। এই সমাধানগুলো কীভাবে খুঁজে পাব?

সমীকরণগুলো দেখি। দ্বিতীয় সমীকরণটি সব x1, x2 এর জন্য সত্য, তাই আমাদের আগ্রহ শুধু প্রথম সমীকরণে। আসলে প্রথম সমীকরণকে সিদ্ধ করে এমন সব জোড় x1, x2 ই এই সমীকরণজোটের সব সমাধানের সেট গঠন করবে। তাই সমীকরণ 4x1 + x2 = 5 এর সমাধান নির্ণয় করি। সমীকরণটিকে x2 = 5 − 4x1 আকারে লিখি।

এরপর একটি পরামিতির সাহায্য নিই। পরামিতি t বেছে নিই। এখন জোড় x1, x2 কে পরামিতি t দিয়ে এমনভাবে প্রকাশ করার চেষ্টা করব, যাতে লিখতে পারি যে, যেমন, (t, t + 2) আকারের সব জোড় জোটের সমাধান। অর্থাৎ (1, 3) বা (14, 16) এর মতো জোড়। উদ্দেশ্য হলো একটি চলকের মানকে অন্য চলক দিয়ে এমনভাবে প্রকাশ করা, যাতে জানি যে x1 এর মান এত হলে x2 এর মান হবে, যেমন, তার তিনগুণ। শুরুর বিন্দু হিসেবে x1 বেছে নিই।

তাই ধরি t = x1। চলক x1 এর মান t হলে চলক x2 এর মান কত হবে? আগের সমীকরণ থেকে দেখা যায়, এর মান হবে x2 = 5 − 4x1। সুতরাং x1 = t হলে x2 = 5 − 4t। তাই লিখতে পারি, (t, 5 − 4t) আকারের সব জোড় সমীকরণজোটের সমাধান।

এটি যাচাই করে দেখতে পারি। t এর জায়গায় এক বসালে পাই: x1 = 1 এবং x2 = 5 − 4 · 1 = 1। এই মানগুলো সমীকরণে বসাই: 4 · 1 + 1 = 5, সমীকরণ মিলে যায়।

t এর জায়গায় পাঁচ বসালে পাই: x1 = 5, x2 = 5 − 4 · 5 = −15। সমীকরণে বসিয়ে পাই: 4 · 5 − 15 = 5। মিলে যায়।

সাধারণ ও বিশেষ সমাধান

পরামিতির সাহায্যে লেখা সমীকরণজোটের সমাধানকে বলা হয় সাধারণ সমাধান (general solution)। নির্দিষ্ট সমাধানকে, অর্থাৎ পরামিতিগুলোর জায়গায় নির্দিষ্ট সংখ্যা বসালে যা পাওয়া যায়, তাকে বলা হয় বিশেষ সমাধান (particular solution)।

তাই আগের উদাহরণ থেকে: (x1, x2) = (t, 5 − 4t) হলো সমীকরণজোটের সাধারণ সমাধান, আর (1, 1) ও (5, −15) হলো বিশেষ সমাধান।

যদি সহগ ম্যাট্রিক্স A ও বর্ধিত ম্যাট্রিক্স (A|b) থাকে এবং এদের র‍্যাঙ্ক সমান হয়, rank(A) = rank(A|b) = k, তাহলে সাধারণ সমাধান প্রকাশ করতে আমাদের n − k টি পরামিতি লাগে। লক্ষ কর, n = k হলে আমাদের শূন্য সংখ্যক পরামিতি লাগে। এটিই সেই ক্ষেত্র, যখন সমীকরণজোটের ঠিক একটি সমাধান থাকে — তখন কোনো পরামিতির দরকার হয় না।

উদাহরণ

নিচের রৈখিক সমীকরণজোটটি সমাধান কর:

3x1−2x2+4x3+5x4=15x1−4x2+2x3+10x4=211x1−8x2+10x3+20x4=4

প্রথমে ম্যাট্রিক্স A ও (A|b) এর র‍্যাঙ্ক নির্ণয় করি। বর্ধিত ম্যাট্রিক্সটিকে সারি সোপান আকারে আনি, এ থেকে দুইটি ম্যাট্রিক্সেরই র‍্যাঙ্ক পাওয়া যাবে। রূপান্তর শুরু করি। (প্রথম সারিকে দুই দিয়ে গুণ করি, তারপর প্রথম ও দ্বিতীয় সারি যোগ করে এই ফলাফল তৃতীয় সারি থেকে বিয়োগ করি। এরপর দ্বিতীয় সারি থেকে প্রথম সারি বিয়োগ করি এবং শেষে প্রথম সারিকে আবার দুই দিয়ে ভাগ করি।)

(A|b)=(3−24515−4210211−810204)∼(6−481025−4210211−810204)∼(6−481025−4210200000)∼(6−48102−10−60000000)∼(3−2451−10−60000000)

এই শেষ ম্যাট্রিক্স থেকেই দেখা যায় যে rank(A) = rank(A|b) = k = 2। অথচ অজ্ঞাত রাশির সংখ্যা n = 4, তাই আমাদের n − k = 2 টি পরামিতি লাগবে। শেষ ম্যাট্রিক্স অনুযায়ী সমীকরণগুলো লিখি:

3x1−2x2+4x3+5x4=1−x1−6x3=0

দ্বিতীয় সমীকরণ থেকে পাই

−x1−6x3=0−x1=6x3x1=−6x3

প্রথম পরামিতিটি বেছে নিই, t = x3। তখন লিখতে পারি x1 = −6t। এটি প্রথম সমীকরণে বসাতে পারি:

3(−6t)−2x2+4t+5x4=1−18t−2x2+4t+5x4=1−14t−2x2+5x4=1−2x2=1+14t−5x4x2=−12−7t+52x4

এবার দ্বিতীয় পরামিতিটি কাজে লাগাই, s = x4। তখন লিখতে পারি

x2=−12−7t+52s

এভাবে জোটের সাধারণ সমাধান পাই:

(x1,x2,x3,x4)=(−6t,−12−7t+52s,t,s)

কিছু বিশেষ সমাধান যাচাই করে দেখতে পারি। যেমন s = t = 0। তখন পাই: (x1,x2,x3,x4)=(0,−12,0,0)। মূল সমীকরণগুলোতে বসালে:

3x1−2x2+4x3+5x4=15x1−4x2+2x3+10x4=211x1−8x2+10x3+20x4=4

এই সমীকরণগুলো পাই:

0−2⋅(−12)+0+0=10−4⋅(−12)+0+0=20−8⋅(−12)+0+0=4

শূন্য পদগুলো বাদ দিয়ে এবং ভগ্নাংশগুলো গুণ করে পাই:

1=12=24=4

আরেকটি বিশেষ সমাধান দেখি: s = 2, t = 1। তখন পাই:

x1=−6x2=−12−7+5=−52x3=1x4=2

সমীকরণগুলোতে বসাই:

−18−2(−52)+4+10=1−30−4(−52)+2+20=2−66−8(−52)+10+40=4

সরল করি:

−4+5=1−8+10=2−16+20=4

আর শেষে পাই:

1=12=24=4

মনে হচ্ছে, প্রাপ্ত সাধারণ সমাধানটি সঠিক।

সূচিপত্র: রৈখিক সমীকরণজোট, ক্রেমারের নিয়ম, সমমাত্রিক রৈখিক সমীকরণজোট