क्यूआर अपघटन

रैखिक बीजगणित में, एक 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 तथ्य यह है कि A का कोई भी स्तंभ k केवल Q के पहले k स्तंभों पर निर्भर करता है, जो R के त्रिकोणीय रूप से मेल खाता है।

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

अधिक सामान्यतः हम 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) कॉल क्यू₁R₁ ए का पतला क्यूआर गुणनखंडन; ट्रेफेथेन और बाउ इसे घटी हुई QR गुणनखंडन कहते हैं।यदि A पूर्ण आव्यूह रैंक n का है और हमें आवश्यकता है कि R के विकर्ण तत्व₁ सकारात्मक हैं तो आर₁ और क्यू₁ अद्वितीय हैं, लेकिन सामान्य तौर पर Q₂ क्या नहीं है। आर₁ तब ए के चोल्स्की अपघटन के ऊपरी त्रिकोणीय कारक के बराबर हैTemplate:Starred ए (= ए^TA यदि A वास्तविक है)।

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

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

क्यूआर अपघटन की गणना

वास्तव में क्यूआर अपघटन की गणना करने के लिए कई तरीके हैं, जैसे कि ग्राम-श्मिट प्रक्रिया, गृहस्थ परिवर्तन या घुमाव देता है के माध्यम से। प्रत्येक के कई फायदे और नुकसान हैं।

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

Further information: Gram–Schmidt § Numerical stability

पूर्ण स्तंभ रैंक आव्यूह के स्तंभों पर लागू ग्राम-श्मिट प्रक्रिया पर विचार करें $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}\mathbf {u} _{1}&=\mathbf {a} _{1},&\mathbf {e} _{1}&={\frac {\mathbf {u} _{1}}{\|\mathbf {u} _{1}\|}}\\\mathbf {u} _{2}&=\mathbf {a} _{2}-\operatorname {proj} _{\mathbf {u} _{1}}\mathbf {a} _{2},&\mathbf {e} _{2}&={\frac {\mathbf {u} _{2}}{\|\mathbf {u} _{2}\|}}\\\mathbf {u} _{3}&=\mathbf {a} _{3}-\operatorname {proj} _{\mathbf {u} _{1}}\mathbf {a} _{3}-\operatorname {proj} _{\mathbf {u} _{2}}\mathbf {a} _{3},&\mathbf {e} _{3}&={\frac {\mathbf {u} _{3}}{\|\mathbf {u} _{3}\|}}\\&\;\;\vdots &&\;\;\vdots \\\mathbf {u} _{k}&=\mathbf {a} _{k}-\sum _{j=1}^{k-1}\operatorname {proj} _{\mathbf {u} _{j}}\mathbf {a} _{k},&\mathbf {e} _{k}&={\frac {\mathbf {u} _{k}}{\|\mathbf {u} _{k}\|}}\end{aligned}}$

अब हम व्यक्त कर सकते हैं $\mathbf {a} _{i}$हमारे नए संगणित ऑर्थोनॉर्मल आधार पर:

${\begin{aligned}\mathbf {a} _{1}&=\left\langle \mathbf {e} _{1},\mathbf {a} _{1}\right\rangle \mathbf {e} _{1}\\\mathbf {a} _{2}&=\left\langle \mathbf {e} _{1},\mathbf {a} _{2}\right\rangle \mathbf {e} _{1}+\left\langle \mathbf {e} _{2},\mathbf {a} _{2}\right\rangle \mathbf {e} _{2}\\\mathbf {a} _{3}&=\left\langle \mathbf {e} _{1},\mathbf {a} _{3}\right\rangle \mathbf {e} _{1}+\left\langle \mathbf {e} _{2},\mathbf {a} _{3}\right\rangle \mathbf {e} _{2}+\left\langle \mathbf {e} _{3},\mathbf {a} _{3}\right\rangle \mathbf {e} _{3}\\&\;\;\vdots \\\mathbf {a} _{k}&=\sum _{j=1}^{k}\left\langle \mathbf {e} _{j},\mathbf {a} _{k}\right\rangle \mathbf {e} _{j}\end{aligned}}$

कहाँ $\left\langle \mathbf {e} _{i},\mathbf {a} _{i}\right\rangle =\left\|\mathbf {u} _{i}\right\|$. इसे आव्यूह रूप में लिखा जा सकता है:

$A=QR$

कहाँ:

$Q={\begin{bmatrix}\mathbf {e} _{1}&\cdots &\mathbf {e} _{n}\end{bmatrix}}$

और

$R={\begin{bmatrix}\langle \mathbf {e} _{1},\mathbf {a} _{1}\rangle &\langle \mathbf {e} _{1},\mathbf {a} _{2}\rangle &\langle \mathbf {e} _{1},\mathbf {a} _{3}\rangle &\cdots &\langle \mathbf {e} _{1},\mathbf {a} _{n}\rangle \\0&\langle \mathbf {e} _{2},\mathbf {a} _{2}\rangle &\langle \mathbf {e} _{2},\mathbf {a} _{3}\rangle &\cdots &\langle \mathbf {e} _{2},\mathbf {a} _{n}\rangle \\0&0&\langle \mathbf {e} _{3},\mathbf {a} _{3}\rangle &\cdots &\langle \mathbf {e} _{3},\mathbf {a} _{n}\rangle \\\vdots &\vdots &\vdots &\ddots &\vdots \\0&0&0&\cdots &\langle \mathbf {e} _{n},\mathbf {a} _{n}\rangle \\\end{bmatrix}}.$

उदाहरण

के अपघटन पर विचार करें

$A={\begin{bmatrix}12&-51&4\\6&167&-68\\-4&24&-41\end{bmatrix}}.$

याद रखें कि एक ऑर्थोनॉर्मल आव्यूह $Q$ संपत्ति है $Q^{\textsf {T}}Q=I$.

फिर, हम गणना कर सकते हैं $Q$ ग्राम-श्मिट के माध्यम से निम्नानुसार:

${\begin{aligned}U={\begin{bmatrix}\mathbf {u} _{1}&\mathbf {u} _{2}&\mathbf {u} _{3}\end{bmatrix}}&={\begin{bmatrix}12&-69&-58/5\\6&158&6/5\\-4&30&-33\end{bmatrix}};\\Q={\begin{bmatrix}{\frac {\mathbf {u} _{1}}{\|\mathbf {u} _{1}\|}}&{\frac {\mathbf {u} _{2}}{\|\mathbf {u} _{2}\|}}&{\frac {\mathbf {u} _{3}}{\|\mathbf {u} _{3}\|}}\end{bmatrix}}&={\begin{bmatrix}6/7&-69/175&-58/175\\3/7&158/175&6/175\\-2/7&6/35&-33/35\end{bmatrix}}.\end{aligned}}$

इस प्रकार, हमारे पास है

${\begin{aligned}Q^{\textsf {T}}A&=Q^{\textsf {T}}Q\,R=R;\\R&=Q^{\textsf {T}}A={\begin{bmatrix}14&21&-14\\0&175&-70\\0&0&35\end{bmatrix}}.\end{aligned}}$

आरक्यू अपघटन से संबंध

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

क्यूआर अपघटन ए के स्तम्भ का ग्राम-श्मिट ऑर्थोगोनलाइज़ेशन है, जो पहले स्तम्भ से शुरू हुआ था।

RQ अपघटन अंतिम पंक्ति से शुरू की गई A की पंक्तियों का ग्राम-श्मिट ऑर्थोगोनलाइज़ेशन है।

फायदे और नुकसान

ग्राम-श्मिट प्रक्रिया स्वाभाविक रूप से संख्यात्मक रूप से अस्थिर है। जबकि अनुमानों के आवेदन में ऑर्थोगोनलाइज़ेशन के लिए एक आकर्षक ज्यामितीय सादृश्य है, ऑर्थोगोनलाइज़ेशन स्वयं संख्यात्मक त्रुटि के लिए प्रवण है। कार्यान्वयन में आसानी एक महत्वपूर्ण लाभ है।

गृहस्थ चिंतन का प्रयोग

क्यूआर-अपघटन के लिए हाउसहोल्डर प्रतिबिंब: लक्ष्य एक रैखिक परिवर्तन खोजना है जो वेक्टर को बदलता है $\mathbf {x}$ एक ही लंबाई के एक सदिश में जो समरेख है $\mathbf {e} _{1}$. हम एक ऑर्थोगोनल प्रोजेक्शन (ग्राम-श्मिट) का उपयोग कर सकते हैं लेकिन यह संख्यात्मक रूप से अस्थिर होगा यदि वैक्टर $\mathbf {x}$ और $\mathbf {e} _{1}$ ऑर्थोगोनल के करीब हैं। इसके बजाय, गृहस्थ प्रतिबिंब बिंदीदार रेखा के माध्यम से प्रतिबिंबित होता है (बीच के कोण को द्विभाजित करने के लिए चुना गया है $\mathbf {x}$ और $\mathbf {e} _{1}$). इस रूपांतरण के साथ अधिकतम कोण 45 डिग्री है।

एक गृहस्थ प्रतिबिंब (या हाउसहोल्डर ट्रांसफॉर्मेशन) एक ऐसा ट्रांसफॉर्मेशन है जो एक वेक्टर लेता है और इसे किसी प्लेन (गणित) या hyperplane के बारे में दर्शाता है। हम इस ऑपरेशन का उपयोग एम-बाय-एन आव्यूह के क्यूआर फैक्टराइजेशन की गणना के लिए कर सकते हैं $A$ साथ m ≥ n.

क्यू का उपयोग एक सदिश को इस तरह से प्रतिबिंबित करने के लिए किया जा सकता है कि सभी निर्देशांक लेकिन एक गायब हो जाता है।

होने देना $\mathbf {x}$ का एक मनमाना वास्तविक एम-आयामी स्तम्भ वेक्टर बनें $A$ ऐसा है कि $\|\mathbf {x} \|=|\alpha |$ एक अदिश α के लिए। यदि एल्गोरिथ्म फ़्लोटिंग-पॉइंट अंकगणित का उपयोग करके कार्यान्वित किया जाता है, तो α को k-वें समन्वय के रूप में विपरीत चिह्न प्राप्त करना चाहिए $\mathbf {x}$, कहाँ $x_{k}$ धुरी समन्वय होना है जिसके बाद आव्यूह ए में सभी प्रविष्टियां 0 हैं{{'}महत्व के नुकसान से बचने के लिए } का अंतिम ऊपरी त्रिकोणीय रूप। जटिल स्थिति में, सेट करें

$\alpha =-e^{i\arg x_{k}}\|\mathbf {x} \|$

और नीचे Q के निर्माण में संयुग्मी वाष्पोत्सर्जन द्वारा स्थानापन्न स्थानापन्न।

तब कहां $\mathbf {e} _{1}$ सदिश है [1 0 ⋯ 0]^टी, ||·|| यूक्लिडियन स्पेस #यूक्लिडियन मानदंड है और $I$ एक एम × एम पहचान आव्यूह है, सेट

${\begin{aligned}\mathbf {u} &=\mathbf {x} -\alpha \mathbf {e} _{1},\\\mathbf {v} &={\frac {\mathbf {u} }{\|\mathbf {u} \|}},\\Q&=I-2\mathbf {v} \mathbf {v} ^{\textsf {T}}.\end{aligned}}$

या अगर $A$ जटिल है

$Q=I-2\mathbf {v} \mathbf {v} ^{*}.$

$Q$ एक एम-बाय-एम हाउसहोल्डर आव्यूह है, जो सममित और ऑर्थोगोनल दोनों है (जटिल स्थिति में हर्मिटियन और एकात्मक), और

$Q\mathbf {x} ={\begin{bmatrix}\alpha \\0\\\vdots \\0\end{bmatrix}}.$

इसका उपयोग धीरे-धीरे एम-बाय-एन आव्यूह ए को ऊपरी त्रिकोणीय आव्यूह फॉर्म में बदलने के लिए किया जा सकता है। सबसे पहले, हम A को हाउसहोल्डर आव्यूह Q से गुणा करते हैं₁ जब हम x के लिए पहला आव्यूह स्तम्भ चुनते हैं तो हम प्राप्त करते हैं। इसका परिणाम एक आव्यूह 'Q में होता है₁ए बाएं स्तम्भ में शून्य के साथ (पहली पंक्ति को छोड़कर)।

$Q_{1}A={\begin{bmatrix}\alpha _{1}&\star &\cdots &\star \\0&&&\\\vdots &&A'&\\0&&&\end{bmatrix}}$

इसे A' के लिए दोहराया जा सकता है (Q से प्राप्त किया गया है₁ए पहली पंक्ति और पहले स्तम्भ को हटाकर), जिसके परिणामस्वरूप हाउसहोल्डर आव्यूह क्यू' होता है₂. ध्यान दें कि क्यू'₂ Q से छोटा है₁. चूंकि हम चाहते हैं कि यह वास्तव में क्यू पर काम करे₁A' के अतिरिक्त हमें इसे ऊपरी बाईं ओर विस्तारित करने की आवश्यकता है, 1 या सामान्य रूप से भरकर:

$Q_{k}={\begin{bmatrix}I_{k-1}&0\\0&Q_{k}'\end{bmatrix}}.$

बाद $t$ इस प्रक्रिया के पुनरावृत्तियों, $t=\min(m-1,n)$,

$R=Q_{t}\cdots Q_{2}Q_{1}A$

एक ऊपरी त्रिकोणीय आव्यूह है। के साथ

${\begin{aligned}Q^{\textsf {T}}&=Q_{t}\cdots Q_{2}Q_{1},\\Q&=Q_{1}^{\textsf {T}}Q_{2}^{\textsf {T}}\cdots Q_{t}^{\textsf {T}},\\&=Q_{1}Q_{2}\cdots Q_{t},\end{aligned}}$

$A=QR$ का QR अपघटन है $A$.

उपरोक्त ग्राम-श्मिट विधि की तुलना में इस पद्धति में संख्यात्मक स्थिरता अधिक है। निम्न तालिका आकार n के साथ एक वर्ग आव्यूह मानते हुए, हाउसहोल्डर परिवर्तन द्वारा क्यूआर-अपघटन के k-वें चरण में संचालन की संख्या देती है।

Operation	Number of operations in the k-th step
Multiplications	$2(n-k+1)^{2}$
Additions	$(n-k+1)^{2}+(n-k+1)(n-k)+2$
Division	$1$
Square root	$1$

इन संख्याओं का योग करना n − 1 चरण (आकार n के एक वर्ग आव्यूह के लिए), एल्गोरिथ्म की जटिलता (फ्लोटिंग पॉइंट गुणन के संदर्भ में) द्वारा दी गई है

${\frac {2}{3}}n^{3}+n^{2}+{\frac {1}{3}}n-2=O\left(n^{3}\right).$

उदाहरण

आइए हम के अपघटन की गणना करें

$A={\begin{bmatrix}12&-51&4\\6&167&-68\\-4&24&-41\end{bmatrix}}.$

सबसे पहले, हमें एक प्रतिबिंब खोजने की जरूरत है जो आव्यूह ए, वेक्टर के पहले स्तम्भ को बदल देता है $\mathbf {a} _{1}={\begin{bmatrix}12&6&-4\end{bmatrix}}^{\textsf {T}}$, में $\left\|\mathbf {a} _{1}\right\|\mathbf {e} _{1}={\begin{bmatrix}\alpha &0&0\end{bmatrix}}^{\textsf {T}}$.

अब,

$\mathbf {u} =\mathbf {x} -\alpha \mathbf {e} _{1},$

और

$\mathbf {v} ={\frac {\mathbf {u} }{\|\mathbf {u} \|}}.$

यहाँ,

$\alpha =14$ और $\mathbf {x} =\mathbf {a} _{1}={\begin{bmatrix}12&6&-4\end{bmatrix}}^{\textsf {T}}$

इसलिए

$\mathbf {u} ={\begin{bmatrix}-2&6&-4\end{bmatrix}}^{\textsf {T}}=2{\begin{bmatrix}-1&3&-2\end{bmatrix}}^{\textsf {T}}$ और $\mathbf {v} ={\frac {1}{\sqrt {14}}}{\begin{bmatrix}-1&3&-2\end{bmatrix}}^{\textsf {T}}$, और तब

${\begin{aligned}Q_{1}={}&I-{\frac {2}{{\sqrt {14}}{\sqrt {14}}}}{\begin{bmatrix}-1\\3\\-2\end{bmatrix}}{\begin{bmatrix}-1&3&-2\end{bmatrix}}\\={}&I-{\frac {1}{7}}{\begin{bmatrix}1&-3&2\\-3&9&-6\\2&-6&4\end{bmatrix}}\\={}&{\begin{bmatrix}6/7&3/7&-2/7\\3/7&-2/7&6/7\\-2/7&6/7&3/7\\\end{bmatrix}}.\end{aligned}}$

अब निरीक्षण करें:

$Q_{1}A={\begin{bmatrix}14&21&-14\\0&-49&-14\\0&168&-77\end{bmatrix}},$

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

(1, 1) गौण (रैखिक बीजगणित) लें, और फिर प्रक्रिया को फिर से लागू करें

$A'=M_{11}={\begin{bmatrix}-49&-14\\168&-77\end{bmatrix}}.$

उपरोक्त विधि के अनुसार, हम गृहस्थ परिवर्तन का आव्यूह प्राप्त करते हैं

$Q_{2}={\begin{bmatrix}1&0&0\\0&-7/25&24/25\\0&24/25&7/25\end{bmatrix}}$

यह सुनिश्चित करने के लिए कि प्रक्रिया का अगला चरण ठीक से काम कर रहा है, 1 के साथ सीधा योग करने के बाद।

अब, हम पाते हैं

$Q=Q_{1}^{\textsf {T}}Q_{2}^{\textsf {T}}={\begin{bmatrix}6/7&-69/175&58/175\\3/7&158/175&-6/175\\-2/7&6/35&33/35\end{bmatrix}}.$

या, चार दशमलव अंकों तक,

${\begin{aligned}Q&=Q_{1}^{\textsf {T}}Q_{2}^{\textsf {T}}={\begin{bmatrix}0.8571&-0.3943&0.3314\\0.4286&0.9029&-0.0343\\-0.2857&0.1714&0.9429\end{bmatrix}}\\R&=Q_{2}Q_{1}A=Q^{\textsf {T}}A={\begin{bmatrix}14&21&-14\\0&175&-70\\0&0&-35\end{bmatrix}}.\end{aligned}}$

आव्यूह क्यू ओर्थोगोनल है और आर ऊपरी त्रिकोणीय है, इसलिए A = QR आवश्यक क्यूआर अपघटन है।

फायदे और नुकसान

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

गिवेंस रोटेशन का उपयोग

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

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

उदाहरण

आइए हम के अपघटन की गणना करें

$A={\begin{bmatrix}12&-51&4\\6&167&-68\\-4&24&-41\end{bmatrix}}.$

सबसे पहले, हमें एक रोटेशन आव्यूह बनाने की जरूरत है जो सबसे निचले बाएँ तत्व को शून्य कर देगा, $a_{31}=-4$. हम इस आव्यूह को गिवेंस रोटेशन विधि का उपयोग करके बनाते हैं, और आव्यूह को कॉल करते हैं $G_{1}$. हम पहले वेक्टर को घुमाएंगे ${\begin{bmatrix}12&-4\end{bmatrix}}$, एक्स अक्ष के साथ इंगित करने के लिए। इस वेक्टर का एक कोण है ${\textstyle \theta =\arctan \left({\frac {-(-4)}{12}}\right)}$. हम ऑर्थोगोनल गिवेंस रोटेशन आव्यूह बनाते हैं, $G_{1}$:

${\begin{aligned}G_{1}&={\begin{bmatrix}\cos(\theta )&0&-\sin(\theta )\\0&1&0\\\sin(\theta )&0&\cos(\theta )\end{bmatrix}}\\&\approx {\begin{bmatrix}0.94868&0&-0.31622\\0&1&0\\0.31622&0&0.94868\end{bmatrix}}\end{aligned}}$

और का परिणाम $G_{1}A$ में अब शून्य है $a_{31}$ तत्व।

$G_{1}A\approx {\begin{bmatrix}12.64911&-55.97231&16.76007\\6&167&-68\\0&6.64078&-37.6311\end{bmatrix}}$

हम इसी तरह गिवेंस मैट्रिसेस बना सकते हैं $G_{2}$ और $G_{3}$, जो उप-विकर्ण तत्वों को शून्य कर देगा $a_{21}$ और $a_{32}$, एक त्रिकोणीय आव्यूह का निर्माण $R$. ओर्थोगोनल आव्यूह $Q^{\textsf {T}}$ गिवेंस के सभी आव्यूहों के गुणनफल से बनता है $Q^{\textsf {T}}=G_{3}G_{2}G_{1}$. इस प्रकार, हमारे पास है $G_{3}G_{2}G_{1}A=Q^{\textsf {T}}A=R$, और क्यूआर अपघटन है $A=QR$.

फायदे और नुकसान

गिवेंस रोटेशन के माध्यम से क्यूआर अपघटन को लागू करने के लिए सबसे अधिक शामिल है, क्योंकि एल्गोरिथम का पूरी तरह से दोहन करने के लिए आवश्यक पंक्तियों का क्रम निर्धारित करने के लिए तुच्छ नहीं है। हालाँकि, इसका एक महत्वपूर्ण लाभ है कि प्रत्येक नया शून्य तत्व $a_{ij}$ केवल उस पंक्ति को प्रभावित करता है जिसके तत्व को शून्य किया जाना है (i) और ऊपर की पंक्ति (j)। यह गिवेंस रोटेशन एल्गोरिथम को हाउसहोल्डर रिफ्लेक्शन तकनीक की तुलना में अधिक बैंडविड्थ कुशल और समानांतर बनाता है।

एक निर्धारक या eigenvalues ​​​​के उत्पाद से संबंध

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

गणित> क्यू </ गणित> को इस तरह चुना जा सकता है गणित>\det क्यू = 1</गणित>। इस प्रकार, <गणित प्रदर्शन = 'ब्लॉक'>\det A = \det R = \prod_i r_{ii}</math>

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

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

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

गैर-स्क्वायर आव्यूह ए के लिए क्यूआर अपघटन के साथ प्रारंभ करें:

$A=Q{\begin{bmatrix}R\\0\end{bmatrix}},\qquad Q^{*}Q=I$

कहाँ $0$ शून्य आव्यूह को दर्शाता है और $Q$ एकात्मक आव्यूह है।

एकवचन मूल्य अपघटन और एक आव्यूह के निर्धारक के गुणों से, हमारे पास है

${\Big |}\prod _{i}r_{ii}{\Big |}=\prod _{i}\sigma _{i},$

जहां $\sigma _{i}$ के विलक्षण मूल्य हैं $A$.

ध्यान दें कि के विलक्षण मूल्य $A$ और $R$ समान हैं, हालांकि उनके जटिल eigenvalues ​​​​भिन्न हो सकते हैं। हालाँकि, यदि A वर्गाकार है, तो

${\prod _{i}\sigma _{i}}={\Big |}\prod _{i}\lambda _{i}{\Big |}.$

यह इस प्रकार है कि क्यूआर अपघटन का उपयोग आव्यूह के आइगेनवैल्यू या एकवचन मूल्यों के उत्पाद की कुशलता से गणना करने के लिए किया जा सकता है।

स्तम्भ पिवोटिंग

पिवोटेड क्यूआर सामान्य ग्राम-श्मिट से अलग है जिसमें यह प्रत्येक नए चरण की शुरुआत में सबसे बड़ा शेष स्तम्भ लेता है- स्तम्भ पिवोटिंग- और इस प्रकार एक क्रमपरिवर्तन आव्यूह पी पेश करता है:

$AP=QR\quad \iff \quad A=QRP^{\textsf {T}}$

स्तम्भ पिवोटिंग तब उपयोगी होती है जब ए (लगभग) रैंक की कमी होती है, या ऐसा होने का संदेह होता है। यह संख्यात्मक सटीकता में भी सुधार कर सकता है। पी आमतौर पर चुना जाता है ताकि आर के विकर्ण तत्व गैर-बढ़ते हों: $\left|r_{11}\right|\geq \left|r_{22}\right|\geq \cdots \geq \left|r_{nn}\right|$. यह एक विलक्षण मूल्य अपघटन की तुलना में कम कम्प्यूटेशनल लागत पर ए के (संख्यात्मक) रैंक को खोजने के लिए इस्तेमाल किया जा सकता है, तथाकथित रैंक-खुलासा क्यूआर एल्गोरिदम का आधार बनता है।

रैखिक उलटा समस्याओं के समाधान के लिए प्रयोग

प्रत्यक्ष आव्यूह व्युत्क्रम की तुलना में, क्यूआर अपघटन का उपयोग करने वाले व्युत्क्रम समाधान संख्यात्मक रूप से अधिक स्थिर होते हैं जैसा कि उनकी घटी हुई स्थिति संख्या से स्पष्ट होता है। अनिर्धारित को हल करने के लिए ($m<n$) रैखिक समस्या $A\mathbf {x} =\mathbf {b}$ जहां आव्यूह $A$ आयाम हैं $m\times n$ और रैंक $m$, सबसे पहले के स्थानान्तरण का QR गुणनखंड ज्ञात कीजिए $A$: $A^{\textsf {T}}=QR$, जहां क्यू एक ओर्थोगोनल आव्यूह है (यानी $Q^{\textsf {T}}=Q^{-1}$), और R का एक विशेष रूप है: $R=\left[{\begin{smallmatrix}R_{1}\\0\end{smallmatrix}}\right]$. यहाँ $R_{1}$ एक वर्ग है $m\times m$ सही त्रिकोणीयआव्यूह, और शून्य आव्यूह का आयाम है $(n-m)\times m$. कुछ बीजगणित के बाद, यह दिखाया जा सकता है कि व्युत्क्रम समस्या का समाधान इस प्रकार व्यक्त किया जा सकता है: $\mathbf {x} =Q\left[{\begin{smallmatrix}\left(R_{1}^{\textsf {T}}\right)^{-1}\mathbf {b} \\0\end{smallmatrix}}\right]$ जहां कोई भी मिल सकता है $R_{1}^{-1}$ गाऊसी उन्मूलन या गणना द्वारा $\left(R_{1}^{\textsf {T}}\right)^{-1}\mathbf {b}$ सीधे त्रिकोणीय आव्यूह द्वारा # फॉरवर्ड और बैक प्रतिस्थापन। बाद वाली तकनीक में अधिक संख्यात्मक सटीकता और कम संगणनाएँ हैं।

समाधान खोजने के लिए ${\hat {\mathbf {x} }}$ अतिनिर्धारित करने के लिए ($m\geq n$) संकट $A\mathbf {x} =\mathbf {b}$ जो आदर्श को कम करता है $\left\|A{\hat {\mathbf {x} }}-\mathbf {b} \right\|$, सबसे पहले का QR गुणनखंड ज्ञात कीजिए $A$: $A=QR$. समाधान तब के रूप में व्यक्त किया जा सकता है ${\hat {\mathbf {x} }}=R_{1}^{-1}\left(Q_{1}^{\textsf {T}}\mathbf {b} \right)$, कहाँ $Q_{1}$ एक $m\times n$ आव्यूह पहले युक्त $n$ पूर्ण ऑर्थोनॉर्मल आधार के स्तम्भ $Q$ और कहाँ $R_{1}$ पहले जैसा है। कम निर्धारित स्थिति के बराबर, त्रिकोणीय आव्यूह # आगे और पीछे प्रतिस्थापन का उपयोग इसे जल्दी और सटीक रूप से खोजने के लिए किया जा सकता है ${\hat {\mathbf {x} }}$ स्पष्ट रूप से उलटे बिना $R_{1}$. ($Q_{1}$ और $R_{1}$ संख्यात्मक पुस्तकालयों द्वारा अधिकांशतः आर्थिक क्यूआर अपघटन के रूप में प्रदान किया जाता है।)

सामान्यीकरण

इवासावा अपघटन अर्ध-सरल झूठ समूहों के लिए क्यूआर अपघटन को सामान्यीकृत करता है।

यह भी देखें

• ध्रुवीय अपघटन
• आइगेनवैल्यू अपघटन
• आव्यूह का आइगेनडीकम्पोज़िशन
• लू अपघटन
• विलक्षण मान अपघटन

अग्रिम पठन

• Golub, Gene H.; Van Loan, Charles F. (1996), Matrix Computations (3rd ed.), Johns Hopkins, ISBN 978-0-8018-5414-9.
• Horn, Roger A.; Johnson, Charles R. (1985), Matrix Analysis, Cambridge University Press, sec. 2.8, ISBN 0-521-38632-2
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Section 2.10. QR Decomposition", Numerical Recipes: The Art of Scientific Computing (3rd ed.), New York: Cambridge University Press, ISBN 978-0-521-88068-8

बाहरी संबंध

• Online Matrix Calculator Performs QR decomposition of matrices.
• LAPACK users manual gives details of subroutines to calculate the QR decomposition
• Mathematica users manual gives details and examples of routines to calculate QR decomposition
• ALGLIB includes a partial port of the LAPACK to C++, C#, Delphi, etc.
• Eigen::QR Includes C++ implementation of QR decomposition.