क्यूआर अपघटन

रैखिक बीजगणित में, एक 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 वास्तविक है) के चोल्स्की अपघटन के ऊपरी त्रिकोणीय कारक के समान है।

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

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

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

वास्तव में 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 की पंक्तियों का ग्राम-श्मिट ऑर्थोगोनलाइज़ेशन है।

लाभ और हानि

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

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

QR-अपघटन के लिए हाउसहोल्डर प्रतिबिंब: लक्ष्य एक रैखिक परिवर्तन खोजना है जो सदिश को बदलता है $\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₁A में होता है (पहली पंक्ति को छोड़कर)।

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

इसे A' के लिए दोहराया जा सकता है (पहली पंक्ति और पहले स्तम्भ को हटाकर Q₁A से प्राप्त), जिसके परिणामस्वरूप हाउसहोल्डर आव्यूह Q′₂' बनता है। ध्यान दें किQ′₂'Q₁ से छोटा है। चूँकि हम चाहते हैं कि यह वास्तव में A' के अतिरिक्त 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$ $A$ का एक QR अपघटन है।

उपरोक्त ग्राम-श्मिट विधि की तुलना में इस पद्धति में संख्यात्मक स्थिरता अधिक है।

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

आपरेशन	k-वें चरण में संचालन की संख्या
गुणन	$2(n-k+1)^{2}$
जोड़	$(n-k+1)^{2}+(n-k+1)(n-k)+2$
विभाजन	$1$
वर्गमूल	$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}}.$

सबसे पहले हमें एक प्रतिबिंब खोजने की जरूरत है जो आव्यूह A, सदिश के पहले स्तम्भ को बदल देता है $\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}}$

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

लाभ और हानि

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

गिवेंस घूर्णन का उपयोग

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

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

उदाहरण

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

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

सबसे पहले, हमें एक घूर्णन आव्यूह बनाने की आवश्यकता है जो सबसे निचले बाएँ तत्व को शून्य कर देगा, $a_{31}=-4$. हम इस आव्यूह को गिवेंस घूर्णन विधि का उपयोग करके बनाते हैं, और आव्यूह को $G_{1}$ कहते हैं। हम X अक्ष के साथ इंगित करने के लिए पहले सदिश ${\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$, है, और QR अपघटन $A=QR$. है।

लाभ और हानि

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

एक निर्धारक या ईजेनवेल्यूज ​​​​के उत्पाद से संबंध

वर्ग आव्यूह के निर्धारक को खोजने के लिए हम QR अपघटन का उपयोग कर सकते हैं। मान लीजिए एक आव्यूह के$A=QR$ रूप में विघटित है तो हमारे पास हैं

det A = \det Q \det R.

Q को इस प्रकार चुना जा सकता है कि det Q = 1 इस प्रकार,

गणित> क्यू </ गणित> को इस तरह चुना जा सकता है गणित>\det Q = 1</गणित>। इस प्रकार,

<गणित प्रदर्शन = 'ब्लॉक'>\det A = \det R = \prod_i$r_{ii}$</math>

जहां $r_{ii}$ के विकर्ण पर प्रविष्टियाँ हैं $R$. इसके अतिरिक्त क्योंकि निर्धारक आइजन वैल्यूज ​​​​के उत्पाद के समान है हमारे पास है

<गणित प्रदर्शन = 'ब्लॉक'> \prod_{i} r_{ii} = \prod_{i} \lambda_{i}</math>

जहां

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

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

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

$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$ समान हैं, चूँकि उनके जटिल ईजेनवेल्यूज ​​​​भिन्न हो सकते हैं। चूँकि यदि A वर्गाकार है, तो

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

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

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

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

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

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

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

प्रत्यक्ष आव्यूह व्युत्क्रम की तुलना में, QR अपघटन का उपयोग करने वाले व्युत्क्रम समाधान संख्यात्मक रूप से अधिक स्थिर होते हैं जैसा कि उनकी घटी हुई स्थिति संख्या से स्पष्ट होता है।

अधोनिर्धारित ($m<n$) रैखिक समस्या को हल करने के लिए $A\mathbf {x} =\mathbf {b}$जहां आव्यूह $A$ का आयाम $m\times n$ और रैंक $m$, है, पहले के ट्रांसपोज़ का QR गुणनखंड ज्ञात करें $A$:$A^{\textsf {T}}=QR$, जहां Q एक ऑर्थोगोनल आव्यूह है (जिससे $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}$ सीधे आगे प्रतिस्थापन द्वारा बाद वाली विधि में अधिक संख्यात्मक स्पष्टता और कम संगणनाएँ हैं।

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

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

सामान्यीकरण

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

यह भी देखें

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

अग्रिम पठन

• 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.