क्यूआर अपघटन

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

मामले और परिभाषाएँ

स्क्वायर मैट्रिक्स

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

$A=QR,$

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

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

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

आयताकार मैट्रिक्स

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

$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},$

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

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.