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

From Vigyanwiki
No edit summary
No edit summary
 
(8 intermediate revisions by 3 users not shown)
Line 9: Line 9:
कोई भी वास्तविक वर्ग आव्यूह A को इस रूप में विघटित किया जा सकता है
कोई भी वास्तविक वर्ग आव्यूह A को इस रूप में विघटित किया जा सकता है
: <math> A = QR, </math>
: <math> A = QR, </math>
जहां ''Q'' एक [[ ओर्थोगोनल ]]आव्यूह है (इसके स्तम्भ ऑर्थोगोनल [[इकाई वेक्टर|इकाई]] सदिश हैं अर्थ {{nowrap|<math>Q^\textsf{T} = Q^{-1}</math>)}} और R एक ऊपरी [[त्रिकोणीय मैट्रिक्स|त्रिकोणीय]] आव्यूह है (जिसे सही त्रिकोणीय आव्यूह भी कहा जाता है)। यदि A व्युत्क्रमणीय आव्यूह है, तो गुणनखंड अद्वितीय है यदि हमें R के विकर्ण तत्वों को सकारात्मक होने की आवश्यकता है।
जहां ''Q'' एक [[ ओर्थोगोनल |ओर्थोगोनल]] आव्यूह है (इसके स्तम्भ ऑर्थोगोनल [[इकाई वेक्टर|इकाई]] सदिश हैं अर्थ {{nowrap|<math>Q^\textsf{T} = Q^{-1}</math>)}} और R एक ऊपरी [[त्रिकोणीय मैट्रिक्स|त्रिकोणीय]] आव्यूह है (जिसे सही त्रिकोणीय आव्यूह भी कहा जाता है)। यदि A व्युत्क्रमणीय आव्यूह है, तो गुणनखंड अद्वितीय है यदि हमें R के विकर्ण तत्वों को सकारात्मक होने की आवश्यकता है।




यदि इसके अतिरिक्त ''A'' एक जटिल [[उलटा मैट्रिक्स|वर्ग]] आव्यूह है, तो एक अपघटन ''A'' = ''QR'' है जहां ''Q'' एक [[एकात्मक मैट्रिक्स|एकात्मक]] आव्यूह है (इसलिए {{nowrap|<math>Q^* = Q^{-1}</math>).}}
यदि इसके अतिरिक्त ''A'' एक जटिल [[उलटा मैट्रिक्स|वर्ग]] आव्यूह है, तो एक अपघटन ''A'' = ''QR'' है जहां ''Q'' एक [[एकात्मक मैट्रिक्स|एकात्मक]] आव्यूह है (इसलिए {{nowrap|<math>Q^* = Q^{-1}</math>).}}


यदि ''A'' में ''A'' रैखिक रूप से स्वतंत्र स्तम्भ हैं, तो ''Q'' के पहले ''n'' स्तम्भ ''A'' के [[स्तंभ स्थान]] के लिए ऑर्थोनॉर्मल आधार बनाते हैं। अधिक सामान्यतः Q के पहले के स्तम्भ A के पहले के स्तम्भ की अवधि के लिए एक ऑर्थोनॉर्मल आधार बनाते हैं। कोई भी {{nowrap|1 ≤ ''k'' ≤ ''n''}} तथ्य यह है<ref name="Trefethen">{{cite book |last1=Trefethen |first1=Lloyd N. |last2=Bau |first2=David III |author1-link=Nick Trefethen |title=संख्यात्मक रैखिक बीजगणित|date=1997 |publisher=[[Society for Industrial and Applied Mathematics]] |location=Philadelphia, PA |isbn=978-0-898713-61-9}}</ref> कि A का कोई भी स्तंभ k केवल Q के पहले k स्तंभों पर निर्भर करता है, जो R के त्रिकोणीय रूप से मेल खाता है। <ref name="Trefethen" />
यदि ''A'' में ''A'' रैखिक रूप से स्वतंत्र स्तम्भ हैं, तो ''Q'' के पहले ''n'' स्तम्भ ''A'' के [[स्तंभ स्थान]] के लिए ऑर्थोनॉर्मल आधार बनाते हैं। अधिक सामान्यतः Q के पहले के स्तम्भ A के पहले के स्तम्भ की अवधि के लिए एक ऑर्थोनॉर्मल आधार बनाते हैं। कोई भी {{nowrap|1 ≤ ''k'' ≤ ''n''}} तथ्य यह है<ref name="Trefethen">{{cite book |last1=Trefethen |first1=Lloyd N. |last2=Bau |first2=David III |author1-link=Nick Trefethen |title=संख्यात्मक रैखिक बीजगणित|date=1997 |publisher=[[Society for Industrial and Applied Mathematics]] |location=Philadelphia, PA |isbn=978-0-898713-61-9}}</ref> कि A का कोई भी स्तंभ k केवल Q के पहले k स्तंभों पर निर्भर करता है, जो R के त्रिकोणीय रूप से मेल खाता है। <ref name="Trefethen" />




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


 
अधिक सामान्यतः हम {{nowrap|''m'' ≥ ''n''}} के साथ एक जटिल ''m''×''n'' आव्यूह ए को कारक कर सकते हैं, m×m एकात्मक आव्यूह Q और एक m×n ऊपरी त्रिकोणीय आव्यूह R के उत्पाद के रूप में नीचे (m−n) पंक्तियों के रूप में एक m×n ऊपरी त्रिकोणीय आव्यूह में पूरी तरह से शून्य होते हैं, यह अधिकांशतः विभाजन R, या R और Q दोनों के लिए उपयोगी होता है:
अधिक सामान्यतः हम {{nowrap|''m'' ≥ ''n''}} के साथ एक जटिल ''m''×''n'' आव्यूह ए को कारक कर सकते हैं, m×m एकात्मक आव्यूह Q और एक m×n ऊपरी त्रिकोणीय आव्यूह R के उत्पाद के रूप में नीचे (m−n) पंक्तियों के रूप में एक m×n ऊपरी त्रिकोणीय आव्यूह में पूरी तरह से शून्य होते हैं, यह अधिकांशतः विभाजन R, या R और Q दोनों के लिए उपयोगी होता है:
:<math>
:<math>
   A = QR = Q \begin{bmatrix} R_1 \\ 0 \end{bmatrix}
   A = QR = Q \begin{bmatrix} R_1 \\ 0 \end{bmatrix}
Line 26: Line 25:
   = Q_1 R_1,
   = Q_1 R_1,
</math>
</math>
जहां ''R''<sub>1</sub> एक n×n ऊपरी त्रिकोणीय आव्यूह है, 0 एक है {{nowrap|(''m'' − ''n'')×''n''}} शून्यआव्यूह, ''Q''<sub>1</sub> ''m''×''n'', ''Q''<sub>2</sub> है {{nowrap|''m''×(''m'' − ''n'')}}, और ''Q''<sub>1</sub> और ''Q''<sub>2</sub> दोनों में ऑर्थोगोनल स्तम्भ हैं।
जहां ''R''<sub>1</sub> एक n×n ऊपरी त्रिकोणीय आव्यूह है, 0 एक है {{nowrap|(''m'' − ''n'')×''n''}} शून्यआव्यूह, ''Q''<sub>1</sub> ''m''×''n'', ''Q''<sub>2</sub> है {{nowrap|''m''×(''m'' − ''n'')}}, और ''Q''<sub>1</sub> और ''Q''<sub>2</sub> दोनों में ऑर्थोगोनल स्तम्भ हैं।


{{harvtxt|Golub|Van Loan|1996|loc=§5.2}} ''Q''<sub>1</sub>''R''<sub>1</sub> को ''A'' का पतला QR गुणनखंड कहते हैं; ट्रेफेथेन और बाउ इसे घटी हुई QR गुणनखंडन कहते हैं।'''<ref name="Trefethen" />''' यदि A पूर्ण पद n का है और हमें आवश्यकता है कि ''R''<sub>1</sub> के विकर्ण तत्व सकारात्मक हैं तो ''R''<sub>1</sub> और ''Q''<sub>1</sub> अद्वितीय हैं, किन्तु सामान्यतः Q<sub>2</sub> नहीं है। ''R''<sub>1</sub> तब ''A''* ''A'' (= ''A''<sup>T</sup>''A'' यदि A वास्तविक है) के चोल्स्की अपघटन के ऊपरी त्रिकोणीय कारक के समान है।
{{harvtxt|Golub|Van Loan|1996|loc=§5.2}} ''Q''<sub>1</sub>''R''<sub>1</sub> को ''A'' का पतला QR गुणनखंड कहते हैं; ट्रेफेथेन और बाउ इसे घटी हुई QR गुणनखंडन कहते हैं।'''<ref name="Trefethen" />''' यदि A पूर्ण पद n का है और हमें आवश्यकता है कि ''R''<sub>1</sub> के विकर्ण तत्व सकारात्मक हैं तो ''R''<sub>1</sub> और ''Q''<sub>1</sub> अद्वितीय हैं, किन्तु सामान्यतः Q<sub>2</sub> नहीं है। ''R''<sub>1</sub> तब ''A''* ''A'' (= ''A''<sup>T</sup>''A'' यदि A वास्तविक है) के चोल्स्की अपघटन के ऊपरी त्रिकोणीय कारक के समान है।


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


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


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


===ग्राम-श्मिट प्रक्रिया का उपयोग ===
===ग्राम-श्मिट प्रक्रिया का उपयोग ===
Line 145: Line 143:




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


Line 157: Line 155:


=== गृहस्थ प्रतिबिंबों का उपयोग करना ===
=== गृहस्थ प्रतिबिंबों का उपयोग करना ===
[[File:Householder.svg|thumb|क्यूआर-अपघटन के लिए हाउसहोल्डर प्रतिबिंब: लक्ष्य एक रैखिक परिवर्तन खोजना है जो सदिश को बदलता है <math>\mathbf x</math> एक ही लंबाई के एक सदिश में जो समरेख है <math>\mathbf e_1</math>. हम एक ऑर्थोगोनल प्रोजेक्शन (ग्राम-श्मिट) का उपयोग कर सकते हैं किन्तु यह संख्यात्मक रूप से अस्थिर होगा यदि वैक्टर <math>\mathbf x</math> और <math>\mathbf e_1</math> ऑर्थोगोनल के करीब हैं। इसके बजाय, गृहस्थ प्रतिबिंब बिंदीदार रेखा के माध्यम से प्रतिबिंबित होता है (बीच के कोण को द्विभाजित करने के लिए चुना गया है <math>\mathbf x</math> और {{nowrap|<math>\mathbf e_1</math>).}} इस रूपांतरण के साथ अधिकतम कोण 45 डिग्री है।]]
[[File:Householder.svg|thumb|QR-अपघटन के लिए हाउसहोल्डर प्रतिबिंब: लक्ष्य एक रैखिक परिवर्तन खोजना है जो सदिश को बदलता है <math>\mathbf x</math> एक ही लंबाई के एक सदिश में जो समरेख है <math>\mathbf e_1</math>. हम एक ऑर्थोगोनल प्रोजेक्शन (ग्राम-श्मिट) का उपयोग कर सकते हैं किन्तु यह संख्यात्मक रूप से अस्थिर होगा यदि वैक्टर <math>\mathbf x</math> और <math>\mathbf e_1</math> ऑर्थोगोनल के करीब हैं। इसके बजाय, गृहस्थ प्रतिबिंब बिंदीदार रेखा के माध्यम से प्रतिबिंबित होता है (बीच के कोण को द्विभाजित करने के लिए चुना गया है <math>\mathbf x</math> और {{nowrap|<math>\mathbf e_1</math>).}} इस रूपांतरण के साथ अधिकतम कोण 45 डिग्री है।]]
 


एक [[ गृहस्थ प्रतिबिंब | गृहस्थ प्रतिबिंबों]] (या हाउसहोल्डर रूपांतरण ) एक ऐसा रूपांतरण है जो एक सदिश लेता है और इसे किसी प्लेन या [[ hyperplane |हाइपरप्लेन]] के बारे में दर्शाता है। हम {{nowrap|''m'' ≥ ''n''}} के साथ m-by-n आव्यूह <math>A</math> के QR गुणनखंड की गणना करने के लिए इस ऑपरेशन का उपयोग कर सकते हैं।
एक [[ गृहस्थ प्रतिबिंब |गृहस्थ प्रतिबिंबों]] (या हाउसहोल्डर रूपांतरण ) एक ऐसा रूपांतरण है जो एक सदिश लेता है और इसे किसी प्लेन या [[ hyperplane |हाइपरप्लेन]] के बारे में दर्शाता है। हम {{nowrap|''m'' ≥ ''n''}} के साथ m-by-n आव्यूह <math>A</math> के QR गुणनखंड की गणना करने के लिए इस ऑपरेशन का उपयोग कर सकते हैं।


''Q'' का उपयोग एक सदिश को इस तरह से प्रतिबिंबित करने के लिए किया जा सकता है कि सभी निर्देशांक किन्तु एक विलुप्त हो जाता है।
''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>
Line 168: Line 165:
और नीचे Q के निर्माण में संयुग्मी वाष्पोत्सर्जन द्वारा स्थानापन्न स्थानापन्न।
और नीचे Q के निर्माण में संयुग्मी वाष्पोत्सर्जन द्वारा स्थानापन्न स्थानापन्न।


फिर, जहाँ <math>\mathbf{e}_1</math> सदिश है [1 0 ⋯ 0]<sup>T</sup>, ||·|| यूक्लिडियन मानदंड है और <math>I</math> एक ''m''×''m'' पहचान आव्यूह सेट है
फिर, जहाँ <math>\mathbf{e}_1</math> सदिश है [1 0 ⋯ 0]<sup>T</sup>, ||·|| यूक्लिडियन मानदंड है और <math>I</math> एक ''m''×''m'' पहचान आव्यूह सेट है
: <math>\begin{align}
: <math>\begin{align}
   \mathbf{u} &= \mathbf{x} - \alpha\mathbf{e}_1, \\
   \mathbf{u} &= \mathbf{x} - \alpha\mathbf{e}_1, \\
Line 177: Line 174:
: <math>Q = I - 2\mathbf{v}\mathbf{v}^*.</math>
: <math>Q = I - 2\mathbf{v}\mathbf{v}^*.</math>


<math>Q</math> एक ''m''-by-''m'' हाउसहोल्डर आव्यूह है, जो सममित और ऑर्थोगोनल दोनों है (जटिल स्थिति में हर्मिटियन और एकात्मक) और
<math>Q</math> एक ''m''-by-''m'' हाउसहोल्डर आव्यूह है जो सममित और ऑर्थोगोनल दोनों है (जटिल स्थिति में हर्मिटियन और एकात्मक) और
: <math>Q\mathbf{x} = \begin{bmatrix} \alpha \\ 0 \\ \vdots \\ 0 \end{bmatrix}.</math>
: <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>''A'' में होता है (पहली पंक्ति को छोड़कर)।
इसका उपयोग धीरे-धीरे ''m''-by-''n'' आव्यूह ''A'' को ऊपरी त्रिकोणीय आव्यूह रूप में बदलने के लिए किया जा सकता है। सबसे पहले, हम A को हाउसहोल्डर आव्यूह ''Q''<sub>1</sub> से गुणा करते हैं जब हम x के लिए पहला आव्यूह स्तम्भ चुनते हैं तो हम प्राप्त करते हैं। इसका परिणाम बाएं स्तंभ में शून्य के साथ एक आव्यूह ''Q''<sub>1</sub>''A'' में होता है (पहली पंक्ति को छोड़कर)।
: <math>Q_1A = \begin{bmatrix}
: <math>Q_1A = \begin{bmatrix}
   \alpha_1 & \star & \cdots & \star \\
   \alpha_1 & \star & \cdots & \star \\
Line 191: Line 188:
       0  & Q_k'
       0  & Q_k'
\end{bmatrix}.</math>
\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>
:<math>R = Q_t \cdots Q_2 Q_1 A</math>
एक ऊपरी त्रिकोणीय आव्यूह है। के साथ
एक ऊपरी त्रिकोणीय आव्यूह है। के साथ                                                                                              
:<math>\begin{align}
:<math>\begin{align}
Q^\textsf{T} &= Q_t \cdots Q_2 Q_1, \\
Q^\textsf{T} &= Q_t \cdots Q_2 Q_1, \\
Line 200: Line 197:
\end{align}</math>
\end{align}</math>


<math>A = QR</math> <math>A</math> का एक QR अपघटन है।
<math>A = QR</math> <math>A</math> का एक QR अपघटन है।                                                                            


'''उपरोक्त ग्राम-श्मिट विधि की तुलना''' में इस पद्धति में [[संख्यात्मक स्थिरता]] अधिक है।<!--See the below example, and compare above-->
उपरोक्त ग्राम-श्मिट विधि की तुलना में इस पद्धति में [[संख्यात्मक स्थिरता]] अधिक है।
निम्न तालिका आकार n के साथ एक वर्ग आव्यूह मानते हुए, हाउसहोल्डर परिवर्तन द्वारा क्यूआर-अपघटन के k-वें चरण में संचालन की संख्या देती है।
 
निम्न तालिका आकार n के साथ एक वर्ग आव्यूह मानते हुए हाउसहोल्डर परिवर्तन द्वारा QR-अपघटन के k-वें चरण में संचालन की संख्या देती है।
{| class="wikitable"
{| class="wikitable"
|-
|-
! Operation
! आपरेशन
! Number of operations in the ''k''-th step
! k-वें चरण में संचालन की संख्या
|-
|-
| Multiplications
| गुणन
| <math>2(n - k + 1)^2</math>
| <math>2(n - k + 1)^2</math>
|-
|-
| Additions
| जोड़
| <math>(n - k + 1)^2 + (n - k + 1)(n - k) + 2 </math>
| <math>(n - k + 1)^2 + (n - k + 1)(n - k) + 2 </math>
|-
|-
| Division
| विभाजन
| <math>1</math>
| <math>1</math>
|-
|-
| Square root
| वर्गमूल
| <math>1</math>
| <math>1</math>
|}
|}
इन संख्याओं का योग करना {{nowrap|''n'' − 1}} चरण (आकार n के एक वर्ग आव्यूह के लिए), एल्गोरिथ्म की जटिलता (फ्लोटिंग पॉइंट गुणन के संदर्भ में) द्वारा दी गई है
इन संख्याओं का योग करना {{nowrap|''n'' − 1}} चरण (आकार n के एक वर्ग आव्यूह के लिए) एल्गोरिथ्म की जटिलता (फ्लोटिंग पॉइंट गुणन के संदर्भ में) द्वारा दी गई है
:<math>\frac{2}{3}n^3 + n^2 + \frac{1}{3}n - 2 = O\left(n^3\right).</math>
:<math>\frac{2}{3}n^3 + n^2 + \frac{1}{3}n - 2 = O\left(n^3\right).</math>
 
==== उदाहरण                                                                                                                                                                                           ====
 
==== उदाहरण ====
आइए हम के अपघटन की गणना करें
आइए हम के अपघटन की गणना करें
: <math>A = \begin{bmatrix}
: <math>A = \begin{bmatrix}
Line 232: Line 228:
   -4 &  24 & -41
   -4 &  24 & -41
\end{bmatrix}.</math>
\end{bmatrix}.</math>
सबसे पहले, हमें एक प्रतिबिंब खोजने की जरूरत है जो आव्यूह ए, सदिश के पहले स्तम्भ को बदल देता है {{nowrap|<math>\mathbf{a}_1 = \begin{bmatrix} 12 & 6 & -4 \end{bmatrix}^\textsf{T}</math>,}} में {{nowrap|<math>\left\|\mathbf{a}_1\right\| \mathbf{e}_1 = \begin{bmatrix} \alpha & 0 & 0\end{bmatrix}^\textsf{T}</math>.}}
सबसे पहले हमें एक प्रतिबिंब खोजने की जरूरत है जो आव्यूह ''A'', सदिश के पहले स्तम्भ को बदल देता है {{nowrap|<math>\mathbf{a}_1 = \begin{bmatrix} 12 & 6 & -4 \end{bmatrix}^\textsf{T}</math>,}} में {{nowrap|<math>\left\|\mathbf{a}_1\right\| \mathbf{e}_1 = \begin{bmatrix} \alpha & 0 & 0\end{bmatrix}^\textsf{T}</math>.}}


अब,
अब,
Line 266: Line 262:
इसलिए हमारे पास पहले से ही लगभग एक त्रिकोणीय आव्यूह है। हमें केवल (3, 2) प्रविष्टि को शून्य करना है।
इसलिए हमारे पास पहले से ही लगभग एक त्रिकोणीय आव्यूह है। हमें केवल (3, 2) प्रविष्टि को शून्य करना है।


(1, 1) गौण (रैखिक बीजगणित) लें, और फिर प्रक्रिया को फिर से प्रयुक्त करें
(1, 1) गौण (रैखिक बीजगणित) लें और फिर प्रक्रिया को फिर से प्रयुक्त करें
:<math>A' = M_{11} = \begin{bmatrix}
:<math>A' = M_{11} = \begin{bmatrix}
   -49 & -14 \\
   -49 & -14 \\
   168 & -77
   168 & -77
\end{bmatrix}.</math>
\end{bmatrix}.</math>
उपरोक्त विधि के अनुसार, हम गृहस्थ परिवर्तन का आव्यूह प्राप्त करते हैं
उपरोक्त विधि के अनुसार हम गृहस्थ परिवर्तन का आव्यूह प्राप्त करते हैं
:<math>Q_2 = \begin{bmatrix}
:<math>Q_2 = \begin{bmatrix}
   1 &    0 &  0 \\
   1 &    0 &  0 \\
Line 277: Line 273:
   0 & 24/25 &  7/25
   0 & 24/25 &  7/25
\end{bmatrix}</math>
\end{bmatrix}</math>
यह सुनिश्चित करने के लिए कि प्रक्रिया का अगला चरण ठीक से काम कर रहा है, 1 के साथ सीधा योग करने के बाद।
यह सुनिश्चित करने के लिए कि प्रक्रिया का अगला चरण ठीक से काम कर रहा है 1 के साथ सीधा योग करने के बाद।


अब, हम पाते हैं
अब, हम पाते हैं
Line 298: Line 294:
   \end{bmatrix}.
   \end{bmatrix}.
\end{align}</math>
\end{align}</math>
आव्यूह क्यू ओर्थोगोनल है और आर ऊपरी त्रिकोणीय है, इसलिए {{nowrap|1=''A'' = ''QR''}} आवश्यक क्यूआर अपघटन है।
आव्यूह ''Q'' ओर्थोगोनल है और आर ऊपरी त्रिकोणीय है, इसलिए {{nowrap|1=''A'' = ''QR''}} आवश्यक QR अपघटन है।


==== लाभ और हानि ====
==== लाभ और हानि ====


आर आव्यूह में शून्य उत्पन्न करने के लिए तंत्र के रूप में प्रतिबिंबों के उपयोग के कारण घरेलू परिवर्तनों का उपयोग स्वाभाविक रूप से संख्यात्मक रूप से स्थिर क्यूआर अपघटन एल्गोरिदम का सबसे सरल है। हालाँकि, हाउसहोल्डर रिफ्लेक्शन एल्गोरिथ्म बैंडविड्थ भारी है और समानांतर नहीं है, क्योंकि प्रत्येक प्रतिबिंब जो एक नया शून्य तत्व उत्पन्न करता है, दोनों Q और R आव्यूह की संपूर्णता को बदल देता है।
''R'' आव्यूह में शून्य उत्पन्न करने के लिए तंत्र के रूप में प्रतिबिंबों के उपयोग के कारण घरेलू परिवर्तनों का उपयोग स्वाभाविक रूप से संख्यात्मक रूप से स्थिर QR अपघटन एल्गोरिदम का सबसे सरल है। चूँकि हाउसहोल्डर प्रतिबिंबों एल्गोरिथ्म बैंडविड्थ भारी है और समानांतर नहीं है क्योंकि प्रत्येक प्रतिबिंब जो एक नया शून्य तत्व उत्पन्न करता है, दोनों Q और R आव्यूह की संपूर्णता को बदल देता है।


=== गिवेंस घूर्णन का उपयोग ===
=== गिवेंस घूर्णन का उपयोग ===
क्यूआर अपघटन की गणना गिवेंस घूर्णन की एक श्रृंखला के साथ भी की जा सकती है। प्रत्येक घुमाव आव्यूह के उप-विकर्ण में एक तत्व को शून्य करता है, जिससे R आव्यूह बनता है। गिवेंस के सभी घुमावों का संयोजन ऑर्थोगोनल क्यू आव्यूह बनाता है।
QR अपघटन की गणना गिवेंस घूर्णन की एक श्रृंखला के साथ भी की जा सकती है। प्रत्येक घुमाव आव्यूह के उप-विकर्ण में एक तत्व को शून्य करता है जिससे R आव्यूह बनता है। गिवेंस के सभी घुमावों का संयोजन ऑर्थोगोनल Q आव्यूह बनाता है।


व्यवहार में, गिवेंस घूर्णन वास्तव में एक संपूर्ण आव्यूह का निर्माण करके और एक आव्यूह गुणन करके नहीं किया जाता है। एक गिवेंस घूर्णन प्रक्रिया का उपयोग इसके अतिरिक्त किया जाता है जो विरल तत्वों को संभालने के अतिरिक्त काम के बिना विरल गिवेंस आव्यूह गुणन के समान होता है। गिवेंस घूर्णन प्रक्रिया उन स्थितियों में उपयोगी होती है जहां केवल अपेक्षाकृत कुछ ऑफ-डायगोनल तत्वों को शून्य करने की आवश्यकता होती है, और घरेलू परिवर्तनों की तुलना में अधिक आसानी से समानांतर होती है।
व्यवहार में, गिवेंस घूर्णन वास्तव में एक संपूर्ण आव्यूह का निर्माण करके और एक आव्यूह गुणन करके नहीं किया जाता है। एक गिवेंस घूर्णन प्रक्रिया का उपयोग इसके अतिरिक्त किया जाता है जो विरल तत्वों को संभालने के अतिरिक्त काम के बिना विरल गिवेंस आव्यूह गुणन के समान होता है। गिवेंस घूर्णन प्रक्रिया उन स्थितियों में उपयोगी होती है जहां केवल अपेक्षाकृत कुछ ऑफ-डायगोनल तत्वों को शून्य करने की आवश्यकता होती है और घरेलू परिवर्तनों की तुलना में अधिक आसानी से समानांतर होती है।


==== उदाहरण ====
==== उदाहरण ====
Line 316: Line 312:
   -4 &  24 & -41
   -4 &  24 & -41
\end{bmatrix}.</math>
\end{bmatrix}.</math>
सबसे पहले, हमें एक घूर्णन आव्यूह बनाने की जरूरत है जो सबसे निचले बाएँ तत्व को शून्य कर देगा, {{nowrap|1=<math>a_{31} = -4</math>.}} हम इस आव्यूह को गिवेंस घूर्णन विधि का उपयोग करके बनाते हैं, और आव्यूह को कॉल करते हैं <math>G_1</math>. हम पहले सदिश को घुमाएंगे {{nowrap|<math>\begin{bmatrix} 12 & -4 \end{bmatrix}</math>,}} एक्स अक्ष के साथ इंगित करने के लिए। इस सदिश का एक कोण है {{nowrap|<math display="inline">\theta = \arctan\left(\frac{-(-4)}{12}\right)</math>.}} हम ऑर्थोगोनल गिवेंस घूर्णन आव्यूह बनाते हैं, <math>G_1</math>:
सबसे पहले हमें एक घूर्णन आव्यूह बनाने की आवश्यकता है जो सबसे निचले बाएँ तत्व को शून्य कर देगा, {{nowrap|1=<math>a_{31} = -4</math>.}} हम इस आव्यूह को गिवेंस घूर्णन विधि का उपयोग करके बनाते हैं और आव्यूह को <math>G_1</math> कहते हैं। हम ''X'' अक्ष के साथ इंगित करने के लिए पहले सदिश {{nowrap|<math>\begin{bmatrix} 12 & -4 \end{bmatrix}</math>,}}को घुमाएंगे इस सदिश का एक कोण {{nowrap|<math display="inline">\theta = \arctan\left(\frac{-(-4)}{12}\right)</math>.}} है। हम ऑर्थोगोनल गिवेंस घूर्णन आव्यूह <math>G_1</math> बनाते हैं:


:<math>\begin{align}
:<math>\begin{align}
Line 330: Line 326:
   \end{bmatrix}
   \end{bmatrix}
\end{align}</math>
\end{align}</math>
और का परिणाम <math>G_1A</math> में अब शून्य है <math>a_{31}</math> तत्व।
और <math>G_1A</math> के परिणाम में अब <math>a_{31}</math> तत्व में शून्य है।
:<math>G_1A \approx \begin{bmatrix}
:<math>G_1A \approx \begin{bmatrix}
   12.64911 & -55.97231 &  16.76007 \\
   12.64911 & -55.97231 &  16.76007 \\
Line 336: Line 332:
   0      &  6.64078 & -37.6311  
   0      &  6.64078 & -37.6311  
\end{bmatrix}</math>
\end{bmatrix}</math>
हम इसी तरह गिवेंस मैट्रिसेस बना सकते हैं <math>G_2</math> और {{nowrap|<math>G_3</math>,}} जो उप-विकर्ण तत्वों को शून्य कर देगा <math>a_{21}</math> और {{nowrap|<math>a_{32}</math>,}} एक त्रिकोणीय आव्यूह का निर्माण {{nowrap|<math>R</math>.}} ओर्थोगोनल आव्यूह <math>Q^\textsf{T}</math> गिवेंस के सभी आव्यूहों के गुणनफल से बनता है {{nowrap|<math>Q^\textsf{T} = G_3 G_2 G_1</math>.}} इस प्रकार, हमारे पास है {{nowrap|<math>G_3 G_2 G_1 A = Q^\textsf{T} A = R</math>,}} और क्यूआर अपघटन है {{nowrap|<math>A = QR</math>.}}
हम गिवेंस मैट्रिसेस <math>G_2</math> और {{nowrap|<math>G_3</math>,}} बना सकते हैं, जो उप-विकर्ण तत्वों <math>a_{21}</math> और {{nowrap|<math>a_{32}</math>,}} को शून्य कर देगा, जिससे त्रिकोणीय आव्यूह {{nowrap|<math>R</math>.}} बन जाएगा। ऑर्थोगोनल आव्यूह <math>Q^\textsf{T}</math> सभी गिवेंस आव्यूह {{nowrap|<math>Q^\textsf{T} = G_3 G_2 G_1</math>.}} के गुणनफल से बनता है। इस प्रकार हमारे पास {{nowrap|<math>G_3 G_2 G_1 A = Q^\textsf{T} A = R</math>,}} है, और QR अपघटन {{nowrap|<math>A = QR</math>.}} है।


==== लाभ और हानि ====
==== लाभ और हानि ====


गिवेंस घूर्णन के माध्यम से क्यूआर अपघटन को प्रयुक्त करने के लिए सबसे अधिक शामिल है, क्योंकि एल्गोरिथम का पूरी तरह से दोहन करने के लिए आवश्यक पंक्तियों का क्रम निर्धारित करने के लिए तुच्छ नहीं है। हालाँकि, इसका एक महत्वपूर्ण लाभ है कि प्रत्येक नया शून्य तत्व <math>a_{ij}</math> केवल उस पंक्ति को प्रभावित करता है जिसके तत्व को शून्य किया जाना है (i) और ऊपर की पंक्ति (j)। यह गिवेंस घूर्णन एल्गोरिथम को हाउसहोल्डर रिफ्लेक्शन तकनीक की तुलना में अधिक बैंडविड्थ कुशल और समानांतर बनाता है।
गिवेंस घूर्णन के माध्यम से QR अपघटन को प्रयुक्त करने के लिए सबसे अधिक सम्मिलित है, क्योंकि एल्गोरिथम का पूरी तरह से दोहन करने के लिए आवश्यक पंक्तियों का क्रम निर्धारित करने के लिए तुच्छ नहीं है। चूँकि इसका एक महत्वपूर्ण लाभ है कि प्रत्येक नया शून्य तत्व <math>a_{ij}</math> केवल उस पंक्ति को प्रभावित करता है जिसमें तत्व शून्य (i) और एक पंक्ति ऊपर (j) है। यह गिवेंस घूर्णन एल्गोरिथम को हाउसहोल्डर प्रतिबिंब विधि की तुलना में अधिक बैंडविड्थ कुशल और समानांतर बनाता है।
 
== एक निर्धारक या ईजेनवेल्यूज ​​​​के उत्पाद से संबंध ==
वर्ग आव्यूह के निर्धारक को खोजने के लिए हम QR अपघटन का उपयोग कर सकते हैं। मान लीजिए एक आव्यूह के<math>A = QR</math> रूप में विघटित है तो हमारे पास हैं
 
<math>det A = det Q det R.</math>


== एक निर्धारक या eigenvalues ​​​​के उत्पाद से संबंध ==
Q को इस प्रकार चुना जा सकता है कि det Q = 1 इस प्रकार,
वर्ग आव्यूह के निर्धारक को खोजने के लिए हम क्यूआर अपघटन का उपयोग कर सकते हैं। मान लीजिए एक आव्यूह के रूप में विघटित है <math>A = QR</math>. तो हमारे पास हैं
<गणित प्रदर्शन = 'ब्लॉक'>\det A = \det Q \det R.</math>


<math>det A = det R = \Big|\prod_i r_{ii}\Big|</math>


गणित> क्यू </ गणित> को इस तरह चुना जा सकता है  गणित>\det क्यू = 1</गणित>। इस प्रकार,
जहां <math>r_{ii}</math> के विकर्ण पर प्रविष्टियाँ हैं <math>R</math>. इसके अतिरिक्त क्योंकि निर्धारक आइजन वैल्यूज ​​​​के उत्पाद के समान है हमारे पास है
<गणित प्रदर्शन = 'ब्लॉक'>\det A = \det R = \prod_i r_{ii}</math>


जहां <math>r_{ii}</math> के विकर्ण पर प्रविष्टियाँ हैं <math>R</math>. इसके अलावा, क्योंकि निर्धारक eigenvalues ​​​​के उत्पाद के समान है, हमारे पास है
<math> \Big|\prod_i r_{ii}\Big|= \Big|\prod_i \lambda_i\Big|.</math>
<गणित प्रदर्शन = 'ब्लॉक'> \prod_{i} r_{ii} = \prod_{i} \lambda_{i}<nowiki></math></nowiki>


जहां  
जहां  
math>\lambda_i</math> के आइगेनवैल्यू हैं  गणित>ए</गणित>.


हम उपरोक्त गुणों को एक गैर-वर्ग जटिल आव्यूह तक बढ़ा सकते हैं <math>A</math> गैर-स्क्वायर जटिल मैट्रिसेस के लिए क्यूआर अपघटन की परिभाषा को पेश करके और आइगेनवैल्यू को एकवचन मूल्यों के साथ बदलकर।
<math> \lambda_i</math>''A''  के आइगेनवैल्यू हैं
 
हम गैर-वर्ग जटिल आव्यूह के लिए QR अपघटन की परिभाषा को प्रस्तुत करके और एकवचन मानो के साथ ईजेनवेल्यूज को बदलकर उपरोक्त गुणों को एक गैर-वर्ग जटिल आव्यूह <math>A</math> तक बढ़ा सकते हैं।


गैर-स्क्वायर आव्यूह ए के लिए क्यूआर अपघटन के साथ प्रारंभ करें:
गैर-वर्ग आव्यूह ''A'' के लिए QR अपघटन के साथ प्रारंभ करें:
: <math>A = Q \begin{bmatrix} R \\ 0 \end{bmatrix}, \qquad Q^* Q = I</math>
: <math>A = Q \begin{bmatrix} R \\ 0 \end{bmatrix}, \qquad Q^* Q = I</math>
जहाँ <math>0<