क्यूआर अपघटन

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

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

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

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

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

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

Further information: ग्राम-श्मिट या संख्यात्मक स्थिरता

पूर्ण स्तंभ पद आव्यूह के स्तंभों पर प्रयुक्त ग्राम-श्मिट प्रक्रिया पर विचार करें $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 अपघटन से एकमात्र अंतर इन आव्यूह का क्रम है।

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

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

लाभ और हानि

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

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

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

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

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

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

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

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

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

${\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$ एक m-by-m हाउसहोल्डर आव्यूह है, जो सममित और ऑर्थोगोनल दोनों है (जटिल स्थिति में हर्मिटियन और एकात्मक) और

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

इसका उपयोग धीरे-धीरे m-by-n आव्यूह A को ऊपरी त्रिकोणीय आव्यूह रूप में बदलने के लिए किया जा सकता है। सबसे पहले, हम 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.