রৈখিক বীজগণিত/বিষয়: পাওয়ার মেথড

বাস্তবে, আইগেনমান এবং আইগেনভেক্টর গণনা করা একটি কঠিন সমস্যা। বিভিন্ন প্রয়োগের ক্ষেত্রে প্রায়শই যে বৃহৎ আকারের ম্যাট্রিক্সগুলোর মুখোমুখি হতে হয়, সেগুলোর বৈশিষ্ট্যসূচক বহুপদী খুঁজে বের করা এবং সমাধান করা অত্যন্ত ধীরগতির এবং জটিল। এজন্য অন্যান্য পরোক্ষ কৌশল ব্যবহার করা হয়, যা বৈশিষ্ট্যসূচক বহুপদী এড়িয়ে চলে। এখানে আমরা এমন একটি পদ্ধতি দেখব যা বৃহৎ আকারের "স্পার্স" ম্যাট্রিক্সের (যার সিংহভাগ ভুক্তিই শূন্য) জন্য অত্যন্ত উপযোগী।

ধরা যাক, একটি $n\times n$ ম্যাট্রিক্স $T$-এর $n$ সংখ্যক স্বতন্ত্র আইগেনমান রয়েছে: ${\lambda }_1$, ${\lambda }_2$, ..., ${\lambda }_n$। তাহলে ${ℝ}^n$-এর এমন একটি ভিত্তি থাকবে যা এর সাথে সম্পর্কিত আইগেনভেক্টর $⟨{\overrightarrow{\zeta }}_1,\dots ,{\overrightarrow{\zeta }}_n⟩$ দ্বারা গঠিত। যেকোনো $\overrightarrow{v}\in {ℝ}^n$-এর জন্য, যেখানে $\overrightarrow{v}=c_1{\overrightarrow{\zeta }}_1+\dots +c_n{\overrightarrow{\zeta }}_n$, $\overrightarrow{v}$-এর উপর $T$-এর পুনরাবৃত্তি ঘটালে নিচের সমীকরণগুলো পাওয়া যায়:

$\begin{array}{cc}T\overrightarrow{v}& =c_1{\lambda }_1{\overrightarrow{\zeta }}_1+c_2{\lambda }_2{\overrightarrow{\zeta }}_2+\dots +c_n{\lambda }_n{\overrightarrow{\zeta }}_n\\ T^2\overrightarrow{v}& =c_1{\lambda }_1^2{\overrightarrow{\zeta }}_1+c_2{\lambda }_2^2{\overrightarrow{\zeta }}_2+\dots +c_n{\lambda }_n^2{\overrightarrow{\zeta }}_n\\ T^3\overrightarrow{v}& =c_1{\lambda }_1^3{\overrightarrow{\zeta }}_1+c_2{\lambda }_2^3{\overrightarrow{\zeta }}_2+\dots +c_n{\lambda }_n^3{\overrightarrow{\zeta }}_n\\ & ⋮\\ T^k\overrightarrow{v}& =c_1{\lambda }_1^k{\overrightarrow{\zeta }}_1+c_2{\lambda }_2^k{\overrightarrow{\zeta }}_2+\dots +c_n{\lambda }_n^k{\overrightarrow{\zeta }}_n\end{array}$

যদি আইগেনমানগুলোর মধ্যে যেকোনো একটির, ধরা যাক ${\lambda }_1$-এর পরম মান অন্য যেকোনো আইগেনমানের চেয়ে বড় হয়, তবে উপরের রাশিতে এর পদটিই প্রধান বা প্রভাবশালী হয়ে উঠবে। অন্যভাবে বললে, সমীকরণটিকে ${\lambda }_1^k$ দ্বারা ভাগ করলে এটি পাওয়া যায়:

$\frac{T^k\overrightarrow{v}}{{\lambda }_1^k}=c_1{\overrightarrow{\zeta }}_1+c_2\frac{{\lambda }_2^k}{{\lambda }_1^k}{\overrightarrow{\zeta }}_2+\dots +c_n\frac{{\lambda }_n^k}{{\lambda }_1^k}{\overrightarrow{\zeta }}_n$

এবং যেহেতু ধরে নেওয়া হয়েছে যে ${\lambda }_1$-এর পরম মান সবচেয়ে বড়, তাই $k$-এর মান যত বাড়বে, ভগ্নাংশগুলোর মান তত শূন্যের কাছাকাছি পৌঁছাবে। ফলস্বরূপ, সম্পূর্ণ রাশিটি $c_1{\overrightarrow{\zeta }}_1$-এর দিকে ধাবিত হবে।

এর অর্থ হলো (যতক্ষণ না $c_1$ শূন্য হচ্ছে), $k$-এর মান বৃদ্ধির সাথে সাথে $T^k\overrightarrow{v}$ ভেক্টরগুলো প্রধান আইগেনমানের সাথে সম্পর্কিত আইগেনভেক্টরের দিকের দিকে ঝুঁকে পড়বে। এবং ফলশ্রুতিতে, এদের দৈর্ঘ্যের অনুপাত $|T^k\overrightarrow{v}|/|T^{k-1}\overrightarrow{v}|$ সেই প্রধান আইগেনমানের মানের দিকে ধাবিত হবে।

উদাহরণস্বরূপ, (এর জন্য একটি নমুনা কম্পিউটার কোড অনুশীলনীর পরে দেওয়া হয়েছে), যেহেতু ম্যাট্রিক্সটি—

$T=\left(\begin{array}{cc}3& 0\\ 8& -1\end{array}\right)$

একটি ত্রিভুজাকার ম্যাট্রিক্স, তাই এর আইগেনমানগুলো হলো এর প্রধান কর্ণের ভুক্তিগুলোই, অর্থাৎ $3$ এবং $-1$। যেকোনো একটি ভেক্টর $\overrightarrow{v}$-এর উপাদান হিসেবে $1$ এবং $1$ ধরে নিলে পাওয়া যায়:

$\begin{array}{cccccc}\overrightarrow{v}& T\overrightarrow{v}& T^2\overrightarrow{v}& \cdots & T^9\overrightarrow{v}& T^{10}\overrightarrow{v}\\ \left(\begin{array}{c}1\\ 1\end{array}\right)& \left(\begin{array}{c}3\\ 7\end{array}\right)& \left(\begin{array}{c}9\\ 17\end{array}\right)& \cdots & \left(\begin{array}{c}19683\\ 39367\end{array}\right)& \left(\begin{array}{c}59049\\ 118097\end{array}\right)\end{array}$

এবং শেষের দুটি ভেক্টরের দৈর্ঘ্যের অনুপাত হলো $2.9999$।

পদ্ধতিটি বাস্তবায়নের ক্ষেত্রে দুটি বিষয় বিবেচনা করতে হবে। প্রথম বিষয়টি হলো, $T$-এর ঘাত বা পাওয়ার বের করে তা $\overrightarrow{v}$-এর উপর প্রয়োগ করার পরিবর্তে, আমরা ${\overrightarrow{v}}_1$-কে $T\overrightarrow{v}$ হিসেবে গণনা করব এবং তারপর ${\overrightarrow{v}}_2$-কে $T{\overrightarrow{v}}_1$ হিসেবে গণনা করব, ইত্যাদি (অর্থাৎ, আমরা কখনোই আলাদাভাবে $T^2$, $T^3$ ইত্যাদি হিসাব করব না)। এই ম্যাট্রিক্স-ভেক্টর গুণফলগুলো $T$ অনেক বড় হলেও খুব দ্রুত করা সম্ভব, যদি তা একটি স্পার্স ম্যাট্রিক্স হয়। দ্বিতীয় বিষয়টি হলো, সংখ্যাগুলো যেন কম্পিউটারের ধারণক্ষমতার বাইরে গিয়ে ওভারফ্লো না করে, সেজন্য আমরা প্রতিটি ধাপে ${\overrightarrow{v}}_i$ ভেক্টরগুলোকে নরমালাইজ করে নিতে পারি। উদাহরণস্বরূপ, আমরা প্রতিটি ${\overrightarrow{v}}_i$-কে তার নিজস্ব দৈর্ঘ্য দ্বারা ভাগ করতে পারি (অন্যান্য উপায়ের মধ্যে রয়েছে একে এর বৃহত্তম উপাদান দ্বারা ভাগ করা, অথবা কেবল এর প্রথম উপাদান দ্বারা ভাগ করা)। সুতরাং আমরা এই পদ্ধতিটি বাস্তবায়ন করব নিচের প্রক্রিয়াটির মাধ্যমে—

$\begin{array}{cc}{\overrightarrow{w}}_0& ={\overrightarrow{v}}_0/|{\overrightarrow{v}}_0|\\ {\overrightarrow{v}}_1& =T{\overrightarrow{w}}_0\\ {\overrightarrow{w}}_1& ={\overrightarrow{v}}_1/|{\overrightarrow{v}}_1|\\ {\overrightarrow{v}}_2& =T{\overrightarrow{w}}_2\\ & ⋮\\ {\overrightarrow{w}}_{k-1}& ={\overrightarrow{v}}_{k-1}/|{\overrightarrow{v}}_{k-1}|\\ {\overrightarrow{v}}_k& =T{\overrightarrow{w}}_k\end{array}$

যতক্ষণ না আমরা আশানুরূপ ফলাফল পাচ্ছি। তখন ${\overrightarrow{v}}_k$ ভেক্টরটি একটি আইগেনভেক্টরের কাছাকাছি মান নির্দেশ করবে এবং প্রধান আইগেনমানের কাছাকাছি মানটি হবে $|{\overrightarrow{v}}_k|/|{\overrightarrow{w}}_{k-1}|=|{\overrightarrow{v}}_k|$ অনুপাতটি।

ফলাফলে সন্তুষ্ট হওয়ার একটি উপায় হতে পারে—আইগেনমানের কাছাকাছি মানটি একটি নির্দিষ্ট অবস্থানে থিতু হওয়া পর্যন্ত পুনরাবৃত্তি চালিয়ে যাওয়া। উদাহরণস্বরূপ, আমরা কোনো নির্দিষ্ট সংখ্যক ধাপের পর পুনরাবৃত্তি বন্ধ না করে, যখন $|{\overrightarrow{v}}_k|$ এবং $|{\overrightarrow{v}}_{k-1}|$-এর মধ্যকার পার্থক্য এক শতাংশের কম হবে, অথবা যখন এদের মান দশমিকের পর দ্বিতীয় তাৎপর্যপূর্ণ অঙ্ক পর্যন্ত মিলে যাবে, তখন এই প্রক্রিয়াটি থামানোর সিদ্ধান্ত নিতে পারি।

কনভারজেন্স বা অভিসরণের হার নির্ধারিত হয় মূলত $|{\lambda }_2/{\lambda }_1|$-এর ঘাত বা পাওয়ার কত দ্রুত শূন্যের দিকে ধাবিত হচ্ছে তার ওপর, যেখানে ${\lambda }_2$ হলো দ্বিতীয় বৃহত্তম পরম মানের আইগেনমান। যদি এই অনুপাতটি ১-এর চেয়ে অনেক কম হয় তবে অভিসরণ খুব দ্রুত ঘটে, কিন্তু এটি যদি ১-এর চেয়ে সামান্য কম হয় তবে অভিসরণ বেশ ধীরগতির হতে পারে। ফলশ্রুতিতে, আইগেনমান খোঁজার জন্য ঘাত পদ্ধতি সবচেয়ে বেশি ব্যবহৃত উপায় নয় (যদিও এটি সবচেয়ে সহজ পদ্ধতি; আর ঠিক এই কারণেই বৈশিষ্ট্যসূচক বহুপদী সমাধান না করেও যে আইগেনমান গণনা করা সম্ভব—তা উদাহরণের মাধ্যমে দেখানোর জন্য এটিকে এখানে অন্তর্ভুক্ত করা হয়েছে)। এর পরিবর্তে বিভিন্ন ধরনের পদ্ধতি রয়েছে যেগুলো সাধারণত প্রদত্ত ম্যাট্রিক্স $T$-কে প্রথমে এটির সদৃশ অন্য একটি ম্যাট্রিক্স দ্বারা প্রতিস্থাপন করে কাজ করে, যার ফলে আইগেনমান একই থাকে কিন্তু ম্যাট্রিক্সটি একটি সংক্ষিপ্ত রূপ লাভ করে, যেমন "ত্রিপদী রূপ": যেখানে কেবল প্রধান কর্ণ এবং এর ঠিক উপরে বা নিচের ভুক্তিগুলোই অ-শূন্য হয়। এরপর আইগেনমানগুলো খুঁজে বের করার জন্য বিশেষ কৌশল ব্যবহার করা যেতে পারে। একবার আইগেনমানগুলো জানা হয়ে গেলে, $T$-এর আইগেনভেক্টরগুলো খুব সহজেই গণনা করা যায়। এই অন্যান্য পদ্ধতিগুলো আমাদের আলোচনার পরিধির বাইরে।

অনুশীলনী

সমস্যা ১

উপাদান বা কম্পোনেন্ট $1$ এবং $2$ বিশিষ্ট ভেক্টর থেকে শুরু করে, নিচের ম্যাট্রিক্সগুলোর বৃহত্তম আইগেনমান অনুমান করতে দশটি পুনরাবৃত্তি ব্যবহার করুন। বৈশিষ্ট্যসূচক সমীকরণ সমাধান করে প্রাপ্ত উত্তরের সাথে আপনার ফলাফলের তুলনা করুন।

1. $\left(\begin{array}{cc}1& 5\\ 0& 4\end{array}\right)$
2. $\left(\begin{array}{cc}3& 2\\ -1& 0\end{array}\right)$

সমস্যা ২

$|{\overrightarrow{v}}_k|-|{\overrightarrow{v}}_{k-1}|$ এর পরম মান $0.01$ এর কম না হওয়া পর্যন্ত পুনরাবৃত্তি করে পূর্ববর্তী অনুশীলনীর কাজটি আবার করুন। প্রতিটি ধাপে, প্রতিটি ভেক্টরকে তার দৈর্ঘ্য দ্বারা ভাগ করে নরমালাইজ করুন। এর জন্য কতটি পুনরাবৃত্তির প্রয়োজন? উত্তরগুলোর মধ্যে কি উল্লেখযোগ্য কোনো পার্থক্য আছে?

সমস্যা ৩

উপাদান বা কম্পোনেন্ট $1$, $2$ এবং $3$ বিশিষ্ট ভেক্টর থেকে শুরু করে, নিচের ম্যাট্রিক্সগুলোর বৃহত্তম আইগেনমান অনুমান করতে দশটি পুনরাবৃত্তি ব্যবহার করুন। বৈশিষ্ট্যসূচক সমীকরণ সমাধান করে প্রাপ্ত উত্তরের সাথে আপনার ফলাফলের তুলনা করুন।

1. $\left(\begin{array}{ccc}4& 0& 1\\ -2& 1& 0\\ -2& 0& 1\end{array}\right)$
2. $\left(\begin{array}{ccc}-1& 2& 2\\ 2& 2& 2\\ -3& -6& -6\end{array}\right)$

সমস্যা ৪

$|{\overrightarrow{v}}_k|-|{\overrightarrow{v}}_{k-1}|$ এর পরম মান $0.01$ এর কম না হওয়া পর্যন্ত পুনরাবৃত্তি করে পূর্ববর্তী অনুশীলনীর কাজটি আবার করুন। প্রতিটি ধাপে, প্রতিটি ভেক্টরকে তার দৈর্ঘ্য দ্বারা ভাগ করে নরমালাইজ করুন। এতে কতটি পুনরাবৃত্তি লাগে? উত্তরগুলোর মধ্যে কি উল্লেখযোগ্য কোনো পার্থক্য আছে?

সমস্যা ৫

যদি $c_1=0$ হয় তবে কী ঘটবে? অর্থাৎ, প্রাথমিক ভেক্টরটির যদি সংশ্লিষ্ট আইগেনভেক্টরের অভিমুখে কোনো উপাদান বা কম্পোনেন্ট না থাকে, তবে কী ঘটবে?

সমস্যা ৬

সবচেয়ে ছোট আইগেনমানটি খুঁজে বের করার জন্য ঘাত পদ্ধতিকে কীভাবে কাজে লাগানো যেতে পারে?

সমাধানসমূহ

উপরের হিসাবটি করার জন্য কম্পিউটার বীজগণিত সিস্টেম অক্টেভে যে কোডটি ব্যবহার করা হয়েছিল তা নিচে দেওয়া হলো। (ফাঁকা লাইন ইত্যাদি বাদ দেওয়ার জন্য এটি হালকা সম্পাদনা করা হয়েছে।)

কম্পিউটার কোড

>T=[3, 0;
8, -1]
T=
3 0
8 -1
>v0=[1; 2]
v0=
1
1
>v1=T*v0
v1=
3
7
>v2=T*v1
v2=
9
17
>T9=T**9
T9=
19683 0
39368 -1
>T10=T**10
T10=
59049 0
118096 1
>v9=T9*v0
v9=
19683
39367
>v10=T10*v0
v10=
59049
118096
>norm(v10)/norm(v9)
ans=2.9999

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

তথ্যসূত্র

• গোল্ট, আর.জে.; হসকিন্স, আর.এফ.; মিলনার, জে.এ.; প্র্যাট, এম.জে. (১৯৭৫), কম্পিউটেশনাল মেথডস ইন লিনিয়ার অ্যালজেব্রা, উইলি উদ্ধৃতি টেমপ্লেট ইংরেজি প্যারামিটার ব্যবহার করেছে (link)

.