क्यूआर अपघटन: Difference between revisions

Revision as of 22:14, 25 May 2023

रैखिक बीजगणित में, एक QR अपघटन, जिसे QR कारककरण या Q कारककरण के रूप में भी जाना जाता है, एक आव्यूह A का एक ऑर्थोनॉर्मल आव्यूह Q के उत्पाद (A = QR) और ऊपरी त्रिकोणीय आव्यूह R , QR अपघटन का एक अपघटन होता है। अधिकांशतः उपयोग किया जाता है रैखिक न्यूनतम वर्गों की समस्या को हल करने के लिए और एक विशेष आइगेनवैल्यू एल्गोरिथम, QR एल्गोरिदम का आधार है।

स्थिति और परिभाषाएँ

वर्ग आव्यूह

कोई भी वास्तविक वर्ग आव्यूह A को इस रूप में विघटित किया जा सकता है

A=QR,

जहां Q एक ओर्थोगोनल आव्यूह है (इसके स्तम्भ ऑर्थोगोनल इकाई सदिश हैं अर्थ $Q^{\textsf {T}}=Q^{-1}$ ) और R एक ऊपरी त्रिकोणीय आव्यूह है (जिसे सही त्रिकोणीय आव्यूह भी कहा जाता है)। यदि A व्युत्क्रमणीय आव्यूह है, तो गुणनखंड अद्वितीय है यदि हमें R के विकर्ण तत्वों को सकारात्मक होने की आवश्यकता है।

यदि इसके अतिरिक्त A एक जटिल वर्ग आव्यूह है, तो एक अपघटन A = QR है जहां Q एक एकात्मक आव्यूह है (इसलिए $Q^{*}=Q^{-1}$ ).

यदि A में A रैखिक रूप से स्वतंत्र स्तम्भ हैं, तो Q के पहले n स्तम्भ A के स्तंभ स्थान के लिए ऑर्थोनॉर्मल आधार बनाते हैं। अधिक सामान्यतः Q के पहले के स्तम्भ A के पहले के स्तम्भ की अवधि के लिए एक ऑर्थोनॉर्मल आधार बनाते हैं। कोई भी 1 ≤ k ≤ n तथ्य यह है^[1] कि A का कोई भी स्तंभ k केवल Q के पहले k स्तंभों पर निर्भर करता है, जो R के त्रिकोणीय रूप से मेल खाता है। ^[1]

आयताकारआव्यूह

अधिक सामान्यतः हम m ≥ n के साथ एक जटिल m×n आव्यूह ए को कारक कर सकते हैं, m×m एकात्मक आव्यूह Q और एक m×n ऊपरी त्रिकोणीय आव्यूह R के उत्पाद के रूप में नीचे (m−n) पंक्तियों के रूप में एक m×n ऊपरी त्रिकोणीय आव्यूह में पूरी तरह से शून्य होते हैं, यह अधिकांशतः विभाजन R, या R और Q दोनों के लिए उपयोगी होता है:

A=QR=Q{\begin{bmatrix}R_{1}\\0\end{bmatrix}}={\begin{bmatrix}Q_{1}&Q_{2}\end{bmatrix}}{\begin{bmatrix}R_{1}\\0\end{bmatrix}}=Q_{1}R_{1},

जहां R₁ एक n×n ऊपरी त्रिकोणीय आव्यूह है, 0 एक है (m − n)×n शून्यआव्यूह, Q₁ m×n, Q₂ है m×(m − n), और Q₁ और Q₂ दोनों में ऑर्थोगोनल स्तम्भ हैं।

Golub & Van Loan (1996, §5.2) Q₁R₁ को A का पतला QR गुणनखंड कहते हैं; ट्रेफेथेन और बाउ इसे घटी हुई QR गुणनखंडन कहते हैं।^[1] यदि A पूर्ण पद n का है और हमें आवश्यकता है कि R₁ के विकर्ण तत्व सकारात्मक हैं तो R₁ और Q₁ अद्वितीय हैं, किन्तु सामान्यतः Q₂ नहीं है। R₁ तब A* A (= A^TA यदि A वास्तविक है) के चोल्स्की अपघटन के ऊपरी त्रिकोणीय कारक के समान है।

क्यूएल, आरक्यू और एलक्यू अपघटन

अनुरूप रूप से, हम QL, RQ और LQ अपघटन को परिभाषित कर सकते हैं, जिसमें L एक निचला त्रिकोणीय आव्यूह है।

QR अपघटन की गणना

वास्तव में क्यूआर अपघटन की गणना करने के लिए कई विधि हैं, जैसे कि ग्राम-श्मिट प्रक्रिया हाउसहोल्डर रूपांतरण या गिवेंस घूर्णन के माध्यम से प्रत्येक के कई लाभ और हानि हैं।

ग्राम-श्मिट प्रक्रिया का उपयोग

पूर्ण स्तंभ पद आव्यूह के स्तंभों पर प्रयुक्त ग्राम-श्मिट प्रक्रिया पर विचार करें $A={\begin{bmatrix}\mathbf {a} _{1}&\cdots &\mathbf {a} _{n}\end{bmatrix}}$ , आंतरिक उत्पाद के साथ $\langle \mathbf {v} ,\mathbf {w} \rangle =\mathbf {v} ^{\textsf {T}}\mathbf {w}$ (या $\langle \mathbf {v} ,\mathbf {w} \rangle =\mathbf {v} ^{*}\mathbf {w}$ जटिल स्थिति के लिए)।

सदिश प्रक्षेपण को परिभाषित करें:

\operatorname {proj} _{\mathbf {u} }\mathbf {a} ={\frac {\left\langle \mathbf {u} ,\mathbf {a} \right\rangle }{\left\langle \mathbf {u} ,\mathbf {u} \right\rangle }}{\mathbf {u} }

तब:

\begin{aligned} u_{1} & = a_{1}, & e_{1} & = \frac{u_{1}}{‖ u_{1} ‖} \\ u_{2} & = a_{2} - {proj}_{u_{1}} a_{2}, & e_{2} & = \frac{u_{2}}{‖ u_{2} ‖} \\ u_{3} & = a_{3} - {proj}_{u_{1}} a_{3} - {proj}_{u_{2}} \end{aligned}

[1]

@@ Line 164: / Line 164: @@
 ''Q'' का उपयोग एक सदिश को इस तरह से प्रतिबिंबित करने के लिए किया जा सकता है कि सभी निर्देशांक किन्तु एक विलुप्त  हो जाता है।
-मान लीजिए <math>\mathbf{x}</math> <math>A</math> का एक स्वेच्छ वास्तविक m-आयामी स्तंभ सदिश है जैसे कि <math>\|\mathbf{x}\| = |\alpha|</math> एक अदिश α के लिए यदि एल्गोरिदम [[फ़्लोटिंग-पॉइंट अंकगणित]] का उपयोग करके कार्यान्वित किया जाता है, तो {{nowrap|<math>\mathbf{x}</math>,}} के k-वें समन्वय के रूप में α को विपरीत चिह्न प्राप्त करना चाहिए, जहां <math>x_k</math> धुरी समन्वय होना है जिसके बाद मैट्रिक्स में सभी प्रविष्टियां 0 हैं महत्व के हानि से बचने के लिए A का अंतिम ऊपरी त्रिकोणीय रूप जटिल स्थिति में सेट करें<ref>{{citation | first1=Josef | last1=Stoer | first2=Roland | last2=Bulirsch | year=2002 | title=Introduction to Numerical Analysis | edition=3rd | publisher=Springer | isbn=0-387-95452-X |page=225}}</ref>
+मान लीजिए <math>\mathbf{x}</math> <math>A</math> का एक स्वेच्छ वास्तविक m-आयामी स्तंभ सदिश है जैसे कि <math>\|\mathbf{x}\| = |\alpha|</math> एक अदिश α के लिए यदि एल्गोरिदम [[फ़्लोटिंग-पॉइंट अंकगणित]] का उपयोग करके कार्यान्वित किया जाता है, तो {{nowrap|<math>\mathbf{x}</math>,}} के k-वें समन्वय के रूप में α को विपरीत चिह्न प्राप्त करना चाहिए, जहां <math>x_k</math> धुरी समन्वय होना है जिसके बाद आव्यूह में सभी प्रविष्टियां 0 हैं महत्व के हानि से बचने के लिए A का अंतिम ऊपरी त्रिकोणीय रूप जटिल स्थिति में सेट करें<ref>{{citation | first1=Josef | last1=Stoer | first2=Roland | last2=Bulirsch | year=2002 | title=Introduction to Numerical Analysis | edition=3rd | publisher=Springer | isbn=0-387-95452-X |page=225}}</ref>
 :<math>\alpha = -e^{i \arg x_k} \|\mathbf{x}\|</math>
 और नीचे Q के निर्माण में संयुग्मी वाष्पोत्सर्जन द्वारा स्थानापन्न स्थानापन्न।
@@ Line 179: / Line 179: @@
 <math>Q</math> एक ''m''-by-''m'' हाउसहोल्डर आव्यूह है, जो सममित और ऑर्थोगोनल दोनों है (जटिल स्थिति में हर्मिटियन और एकात्मक) और
 : <math>Q\mathbf{x} = \begin{bmatrix} \alpha \\ 0 \\ \vdots \\ 0 \end{bmatrix}.</math>
-'''इसका उपयोग धीरे-धीरे ''m''-by-''n'' आव्यूह ''A''  को ऊपरी त्रिकोणीय आव्यूह''' रूप में बदलने के लिए किया जा सकता है। सबसे पहले, हम A को हाउसहोल्डर आव्यूह Q से गुणा करते हैं<sub>1</sub> जब हम x के लिए पहला आव्यूह स्तम्भ चुनते हैं तो हम प्राप्त करते हैं। इसका परिणाम एक आव्यूह 'Q'' में होता है<sub>1</sub>ए बाएं स्तम्भ में शून्य के साथ (पहली पंक्ति को छोड़कर)।''
+इसका उपयोग धीरे-धीरे ''m''-by-''n'' आव्यूह ''A''  को ऊपरी त्रिकोणीय आव्यूह रूप में बदलने के लिए किया जा सकता है। सबसे पहले, हम A को हाउसहोल्डर आव्यूह ''Q''<sub>1</sub> से गुणा करते हैं जब हम x के लिए पहला आव्यूह स्तम्भ चुनते हैं तो हम प्राप्त करते हैं। इसका परिणाम बाएं स्तंभ में शून्य के साथ एक आव्यूह ''Q''<sub>1</sub>''A'' में होता है (पहली पंक्ति को छोड़कर)।
 : <math>Q_1A = \begin{bmatrix}
    \alpha_1 & \star & \cdots & \star \\
@@ Line 186: / Line 186: @@
 &       &        &
 \end{bmatrix}</math>
-इसे A' के लिए दोहराया जा सकता है (Q से प्राप्त किया गया है<sub>1</sub>ए पहली पंक्ति और पहले स्तम्भ को हटाकर), जिसके परिणामस्वरूप हाउसहोल्डर आव्यूह क्यू' होता है<sub>2</sub>. ध्यान दें कि क्यू'<sub>2</sub> Q से छोटा है<sub>1</sub>. चूंकि हम चाहते हैं कि यह वास्तव में क्यू पर काम करे<sub>1</sub>A' के अतिरिक्त हमें इसे ऊपरी बाईं ओर विस्तारित करने की आवश्यकता है, 1 या सामान्य रूप से भरकर:
+इसे A' के लिए दोहराया जा सकता है (पहली पंक्ति और पहले स्तम्भ को हटाकर ''Q''<sub>1</sub>''A'' से प्राप्त), जिसके परिणामस्वरूप हाउसहोल्डर आव्यूह ''Q''′<sub>2</sub>' बनता है। ध्यान दें कि''Q''′<sub>2</sub>'''Q''<sub>1</sub> से छोटा है। चूँकि हम चाहते हैं कि यह वास्तव में A' के अतिरिक्त ''Q''<sub>1</sub>''A'' पर संचालित हो, इसलिए हमें इसे 1 या सामान्य रूप से भरते हुए ऊपरी बाएँ में विस्तारित करने की आवश्यकता है:
 :<math>Q_k = \begin{bmatrix}
    I_{k-1} & 0    \\
   & Q_k'
 \end{bmatrix}.</math>
-बाद <math>t</math> इस प्रक्रिया के पुनरावृत्तियों, {{nowrap|<math>t = \min(m - 1, n)</math>,}}
+इस <math>t</math> प्रक्रिया पुनरावृत्तियों के बाद   {{nowrap|<math>t = \min(m - 1, n)</math>,}}
 :<math>R = Q_t \cdots Q_2 Q_1 A</math>
 एक ऊपरी त्रिकोणीय आव्यूह है। के साथ
@@ Line 200: / Line 200: @@
 \end{align}</math>
-<math>A = QR</math> का QR अपघटन है <math>A</math>.
+<math>A = QR</math> <math>A</math> का एक QR अपघटन है।
-उपरोक्त ग्राम-श्मिट विधि की तुलना में इस पद्धति में [[संख्यात्मक स्थिरता]] अधिक है।<!--See the below example, and compare above-->
+'''उपरोक्त ग्राम-श्मिट विधि की तुलना''' में इस पद्धति में [[संख्यात्मक स्थिरता]] अधिक है।<!--See the below example, and compare above-->
 निम्न तालिका आकार n के साथ एक वर्ग आव्यूह मानते हुए, हाउसहोल्डर परिवर्तन द्वारा क्यूआर-अपघटन के k-वें चरण में संचालन की संख्या देती है।
 {| class="wikitable"

Anonymous

Search

क्यूआर अपघटन: Difference between revisions

Namespaces

More

Page actions