हाउसहोल्डर ट्रांसफ़ॉर्मेशन: Difference between revisions
m (Abhishek moved page गृहस्थ परिवर्तन to हाउसहोल्डर ट्रांसफ़ॉर्मेशन without leaving a redirect) |
No edit summary |
||
Line 1: | Line 1: | ||
{{short description|Concept in linear algebra}} | {{short description|Concept in linear algebra}} | ||
रैखिक बीजगणित में, एक हाउसहोल्डर | रैखिक बीजगणित में, एक हाउसहोल्डर परिवर्तन (जिसे हाउसहोल्डर परावर्तन या प्राथमिक प्रतिक्षेपक के रूप में भी जाना जाता है) एक [[रैखिक परिवर्तन]] है जो एक प्लेन (गणित) या [[ hyperplane | हाइपरप्लेन]] के बारे में एक परावर्तन (गणित) का वर्णन करता है जिसमें मूल होता है। [[एलस्टन स्कॉट हाउसहोल्डर]] द्वारा 1958 के पेपर में हाउसहोल्डर परिवर्तन का उपयोग किया गया था।<ref>{{cite journal | ||
|first=A. S. |last=Householder |authorlink=Alston Scott Householder | |first=A. S. |last=Householder |authorlink=Alston Scott Householder | ||
|title=Unitary Triangularization of a Nonsymmetric Matrix | |title=Unitary Triangularization of a Nonsymmetric Matrix | ||
Line 6: | Line 6: | ||
|volume=5 |issue=4 |year=1958 |pages=339–342 | |volume=5 |issue=4 |year=1958 |pages=339–342 | ||
|doi=10.1145/320941.320947 |mr=0111128 | |doi=10.1145/320941.320947 |mr=0111128 | ||
|s2cid=9858625 |url=https://hal.archives-ouvertes.fr/hal-01316095/file/p339householderb.pdf }}</ref> | |s2cid=9858625 |url=https://hal.archives-ouvertes.fr/hal-01316095/file/p339householderb.pdf }}</ref> | ||
सामान्य [[आंतरिक उत्पाद रिक्त स्थान]] पर इसका एनालॉग [[ गृहस्थ संचालिका ]] है। | |||
सामान्य [[आंतरिक उत्पाद रिक्त स्थान]] पर इसका एनालॉग [[ गृहस्थ संचालिका | हाउसहोल्डर संचालिका]] है। | |||
== परिभाषा == | == परिभाषा == | ||
Line 13: | Line 14: | ||
=== परिवर्तन === | === परिवर्तन === | ||
प्रतिबिंब हाइपरप्लेन को इसके सामान्य वेक्टर, एक [[ इकाई वेक्टर | प्रतिबिंब हाइपरप्लेन को इसके सामान्य वेक्टर, एक [[ इकाई वेक्टर | इकाई वेक्टर <math display="inline">v</math>]] द्वारा परिभाषित किया जा सकता है (लंबाई के साथ एक वेक्टर <math display="inline">1</math>) जो हाइपरप्लेन के लिए [[ओर्थोगोनल]] है। एक बिंदु <math display="inline">x</math> का प्रतिबिंब (ज्यामिति) इस हाइपरप्लेन के बारे में रैखिक परिवर्तन है: | ||
: <math>x - 2\langle x, v\rangle v = x - 2v\left(v^\textsf{H} x\right), </math> | : <math>x - 2\langle x, v\rangle v = x - 2v\left(v^\textsf{H} x\right), </math> | ||
जहाँ <math display="inline">v</math> [[हर्मिटियन ट्रांसपोज़]] <math display="inline">v^\textsf{H}</math> के साथ स्तंभ इकाई वेक्टर के रूप में दिया गया है . | |||
=== हाउसहोल्डर | === हाउसहोल्डर आव्यूह === | ||
इस परिवर्तन से निर्मित | इस परिवर्तन से निर्मित आव्यूह को [[बाहरी उत्पाद]] के रूप में व्यक्त किया जा सकता है: | ||
: <math>P = I - 2vv^\textsf{H}</math> | : <math>P = I - 2vv^\textsf{H}</math> | ||
हाउसहोल्डर | हाउसहोल्डर आव्यूह के रूप में जाना जाता है, जहां <math display="inline">I</math> पहचान आव्यूह है। | ||
==== गुण ==== | ==== गुण ==== | ||
हाउसहोल्डर | हाउसहोल्डर आव्यूह में निम्नलिखित गुण होते हैं: | ||
* यह [[हर्मिटियन मैट्रिक्स]] है: <math display="inline">P = P^\textsf{H}</math>, | * यह [[हर्मिटियन मैट्रिक्स|हर्मिटियन आव्यूह]] है: <math display="inline">P = P^\textsf{H}</math>, | ||
* यह [[एकात्मक मैट्रिक्स]] है: <math display="inline">P^{-1} = P^\textsf{H}</math>, | * यह [[एकात्मक मैट्रिक्स|एकात्मक आव्यूह]] है: <math display="inline">P^{-1} = P^\textsf{H}</math>, | ||
* इसलिए यह [[अनैच्छिक मैट्रिक्स]] है: <math display="inline">P = P^{-1}</math>. | * इसलिए यह [[अनैच्छिक मैट्रिक्स|अनैच्छिक आव्यूह]] है: <math display="inline">P = P^{-1}</math>. | ||
* | * हाउसहोल्डर आव्यूह में आइगेनवैल्यू {<math display="inline">\pm 1</math>} होते हैं। इसे देखने के लिए, ध्यान दें कि यदि {<math display="inline">u</math>} सदिश {<math display="inline">v</math>} के लिए ओर्थोगोनल है, जिसका उपयोग परावर्तक बनाने के लिए किया गया था, तो {<math display="inline">Pu = u</math>} <math display="inline">1</math> बहुलता {<math display="inline">n - 1</math>} का आइगेनमान है, क्योंकि {<math display="inline">n - 1</math>} स्वतंत्र सदिश ऑर्थोगोनल हैं { <math display="inline">v</math>}। इसके अलावा, {<math display="inline">Pv = -v</math>} पर ध्यान दें, और इसलिए {<math display="inline">-1</math>} बहुलता (<math display="inline">1</math>) के साथ एक ईगेनवैल्यू है। | ||
* | * हाउसहोल्डर परावर्तक का निर्धारक <math display="inline">-1</math> होता है , चूंकि एक आव्यूह का निर्धारक इसके ईगेनवैल्यू का उत्पाद है, इस स्थति में जिनमें से एक <math display="inline">-1</math> है शेष <math display="inline">1</math> होने के साथ (जैसा कि पिछले बिंदु में है)। | ||
== अनुप्रयोग == | == अनुप्रयोग == | ||
Line 38: | Line 39: | ||
===ज्यामितीय प्रकाशिकी === | ===ज्यामितीय प्रकाशिकी === | ||
ज्यामितीय प्रकाशिकी में, स्पेक्युलर प्रतिबिंब को हाउसहोल्डर | ज्यामितीय प्रकाशिकी में, स्पेक्युलर प्रतिबिंब को हाउसहोल्डर आव्यूह के संदर्भ में व्यक्त किया जा सकता है (देखें {{section link|स्पेक्युलर परावर्तन या वेक्टर सूत्रीकरण}}). | ||
=== [[संख्यात्मक रैखिक बीजगणित]] === | === [[संख्यात्मक रैखिक बीजगणित]] === | ||
संख्यात्मक रेखीय बीजगणित में घरेलू परिवर्तनों का व्यापक रूप से उपयोग किया जाता है, उदाहरण के लिए, | संख्यात्मक रेखीय बीजगणित में घरेलू परिवर्तनों का व्यापक रूप से उपयोग किया जाता है, उदाहरण के लिए, आव्यूह के मुख्य विकर्ण के नीचे की प्रविष्टियों को मिटाने के लिए<ref name=taboga>{{cite web | last1 = Taboga | first1 = Marco | url = https://www.statlect.com/matrix-algebra/Householder-matrix | title = Householder matrix, Lectures on matrix algebra.}}</ref> [[क्यूआर अपघटन]] करने के लिए और [[क्यूआर एल्गोरिदम]] के पहले चरण में[[ हेसनबर्ग मैट्रिक्स | हेसनबर्ग आव्यूह]] फॉर्म में बदलने के लिए उनका व्यापक रूप से उपयोग किया जाता है। सममित या हर्मिटियन आव्यूह मैट्रिसेस के लिए, समरूपता को संरक्षित किया जा सकता है, जिसके परिणामस्वरूप ट्राइडायगोनलाइज़ेशन होता है।<ref>{{Cite journal|last1=Schabauer|first1=Hannes|last2=Pacher|first2=Christoph|last3=Sunderland|first3=Andrew G.|last4=Gansterer|first4=Wilfried N.|date=2010-05-01|title=सामान्यीकृत जटिल सममित eigenvalue समस्याओं के लिए एक समानांतर सॉल्वर की ओर|journal=Procedia Computer Science|language=en|volume=1|issue=1|pages=437–445|doi=10.1016/j.procs.2010.04.047|doi-access=free}}</ref> | ||
==== क्यूआर अपघटन ==== | ==== क्यूआर अपघटन ==== | ||
हाउसहोल्डर प्रतिबिंबों का उपयोग क्यूआर अपघटन की गणना करने के लिए किया जा सकता है, | हाउसहोल्डर प्रतिबिंबों का उपयोग क्यूआर अपघटन की गणना करने के लिए किया जा सकता है, आव्यूह के पहले एक स्तम्भ को एक मानक आधार वेक्टर के एक से अधिक पर प्रतिबिंबित करके, परिवर्तन आव्यूह की गणना करके, इसे मूल आव्यूह के साथ गुणा करके और फिर <math display="inline">(i, i)</math> नीचे की ओर पुनरावर्ती उस उत्पाद का [[मामूली (रैखिक बीजगणित)|सामान्य (रैखिक बीजगणित)]]। | ||
==== त्रिभुजकरण ==== | ==== त्रिभुजकरण ==== | ||
{{main| | {{main|त्रिकोणीय आव्यूह}} | ||
इस प्रक्रिया को बर्डन एंड फेयरेस द्वारा न्यूमेरिकल एनालिसिस में प्रस्तुत किया गया है। यह थोड़ा | |||
पहले चरण में, प्रत्येक चरण में हाउसहोल्डर | इस प्रक्रिया को बर्डन एंड फेयरेस द्वारा न्यूमेरिकल एनालिसिस में प्रस्तुत किया गया है। यह थोड़ा परिवर्तित <math>\operatorname{sgn}</math> कार्य का उपयोग करता है <math>\operatorname{sgn}(0) = 1</math> के साथ कार्य करें .<ref name='burden'>{{cite book |last1=Burden |first1=Richard |last2=Faires |first2=Douglas |last3=Burden |first3=Annette |title=संख्यात्मक विश्लेषण|date=2016 |publisher=Thomson Brooks/Cole |isbn=9781305253667 |edition=10th}}</ref> | ||
पहले चरण में, प्रत्येक चरण में हाउसहोल्डर आव्यूह बनाने के लिए हमें <math display="inline">\alpha</math> और <math display="inline">r</math>, निर्धारित करने की आवश्यकता है जो हैं: | |||
:<math>\begin{align} | :<math>\begin{align} | ||
\alpha &= -\operatorname{sgn}\left(a_{21}\right)\sqrt{\sum_{j=2}^n a_{j1}^2}; \\ | \alpha &= -\operatorname{sgn}\left(a_{21}\right)\sqrt{\sum_{j=2}^n a_{j1}^2}; \\ | ||
r &= \sqrt{\frac{1}{2}\left(\alpha^2 - a_{21}\alpha\right)}; | r &= \sqrt{\frac{1}{2}\left(\alpha^2 - a_{21}\alpha\right)}; | ||
\end{align}</math> | \end{align}</math> | ||
<math display="inline">\alpha</math> और <math display="inline">r</math> से वेक्टर <math display="inline">v</math> बनाएँ। | |||
:<math>v^{(1)} = \begin{bmatrix} v_1 \\ v_2 \\ \vdots \\ v_n \end{bmatrix},</math> | :<math>v^{(1)} = \begin{bmatrix} v_1 \\ v_2 \\ \vdots \\ v_n \end{bmatrix},</math> | ||
जहाँ <math display="inline">v_1 = 0</math>, <math display="inline">v_2 = \frac{a_{21} - \alpha}{2r}</math>, और | |||
:<math>v_k = \frac{a_{k1}}{2r}</math> प्रत्येक के लिए <math>k = 3, 4 \ldots n</math> | :<math>v_k = \frac{a_{k1}}{2r}</math> प्रत्येक के लिए <math>k = 3, 4 \ldots n</math> | ||
फिर गणना करें: | फिर गणना करें: | ||
Line 67: | Line 71: | ||
A^{(2)} &= P^1 AP^1 | A^{(2)} &= P^1 AP^1 | ||
\end{align}</math> | \end{align}</math> | ||
<math display="inline">P^1</math> मिलने और <math display="inline">A^{(2)}</math> की गणना करने के बाद <math display="inline">k = 2, 3, \ldots, n - 2</math> के लिए प्रक्रिया को इस प्रकार दोहराया जाता है: | |||
:<math>\begin{align} | :<math>\begin{align} | ||
Line 78: | Line 82: | ||
A^{(k+1)} &= P^k A^{(k)}P^k | A^{(k+1)} &= P^k A^{(k)}P^k | ||
\end{align}</math> | \end{align}</math> | ||
इस तरह से जारी रखते हुए, त्रिभुज और सममित | इस तरह से जारी रखते हुए, त्रिभुज और सममित आव्यूह बनता है। | ||
==== उदाहरण ==== | ==== उदाहरण ==== | ||
इस उदाहरण में, बर्डन और फेयरेस से भी | इस उदाहरण में, बर्डन और फेयरेस से भी दिए गए आव्यूह को हाउसहोल्डर विधि का उपयोग करके समान त्रिकोणीय आव्यूह A3 में बदल दिया गया है।<ref name="burden" /> | ||
: <math>\mathbf{A} = \begin{bmatrix} | : <math>\mathbf{A} = \begin{bmatrix} | ||
Line 90: | Line 94: | ||
2 & 1 & -2 & -1 | 2 & 1 & -2 & -1 | ||
\end{bmatrix},</math> | \end{bmatrix},</math> | ||
हाउसहोल्डर | हाउसहोल्डर पद्धति में उन चरणों का अनुसरण करने पर हमारे पास: | ||
पहला हाउसहोल्डर | पहला हाउसहोल्डर आव्यूह : | ||
: <math>\begin{align} | : <math>\begin{align} | ||
Q_1 &= \begin{bmatrix} | Q_1 &= \begin{bmatrix} | ||
Line 107: | Line 111: | ||
\end{bmatrix}, | \end{bmatrix}, | ||
\end{align}</math> | \end{align}</math> | ||
बनाने के लिए <math display="inline">A_2</math> का उपयोग किया | |||
: <math>\begin{align} | : <math>\begin{align} | ||
Q_2 &= \begin{bmatrix} | Q_2 &= \begin{bmatrix} | ||
Line 122: | Line 126: | ||
\end{bmatrix}, | \end{bmatrix}, | ||
\end{align}</math> | \end{align}</math> | ||
जैसा कि हम देख सकते हैं, अंतिम परिणाम एक त्रिकोणीय सममित | जैसा कि हम देख सकते हैं, अंतिम परिणाम एक त्रिकोणीय सममित आव्यूह है जो मूल के समान है। प्रक्रिया दो चरणों के बाद समाप्त हो गई है। | ||
== अन्य एकात्मक परिवर्तनों के लिए कम्प्यूटेशनल और सैद्धांतिक संबंध == | == अन्य एकात्मक परिवर्तनों के लिए कम्प्यूटेशनल और सैद्धांतिक संबंध == | ||
{{see also| | {{see also|परिक्रमण (गणित)}} | ||
हाउसहोल्डर | |||
हाउसहोल्डर परिवर्तन यूनिट नॉर्मल वेक्टर वाले हाइपरप्लेन के बारे में एक प्रतिबिंब है <math display="inline">v</math>, जैसा कि पहले कहा गया है। एक <math display="inline">N</math>-द्वारा-<math display="inline">N</math> [[एकात्मक परिवर्तन]] <math display="inline">U</math> संतुष्ट <math display="inline">UU^\textsf{H} = I</math>. निर्धारक लेना (<math display="inline">N</math>-ज्यामितीय माध्य की शक्ति) और एक एकात्मक आव्यूह के ट्रेस (अंकगणित माध्य के समानुपाती) से पता चलता है कि इसके ईगेनवैल्यू <math display="inline">\lambda_i</math> इकाई मापांक है। इसे सीधे और तेजी से देखा जा सकता है: | |||
:<math>\begin{align} | :<math>\begin{align} | ||
\frac{\operatorname{Trace}\left(UU^\textsf{H}\right)}{N} &= | \frac{\operatorname{Trace}\left(UU^\textsf{H}\right)}{N} &= | ||
Line 135: | Line 140: | ||
चूंकि अंकगणितीय और ज्यामितीय साधन समान हैं यदि चर स्थिर हैं ([[अंकगणित और ज्यामितीय साधनों की असमानता]] देखें), हम इकाई मापांक का दावा स्थापित करते हैं। | चूंकि अंकगणितीय और ज्यामितीय साधन समान हैं यदि चर स्थिर हैं ([[अंकगणित और ज्यामितीय साधनों की असमानता]] देखें), हम इकाई मापांक का दावा स्थापित करते हैं। | ||
वास्तविक मूल्यवान एकात्मक मेट्रिसेस के | वास्तविक मूल्यवान एकात्मक मेट्रिसेस के स्थति में हम [[ऑर्थोगोनल मेट्रिसेस]] प्राप्त करते हैं, <math display="inline">UU^\textsf{T} = I</math>. यह अपेक्षाकृत आसानी से अनुसरण करता है ([[ऑर्थोगोनल मैट्रिक्स|ऑर्थोगोनल आव्यूह]] देखें) कि कोई भी ऑर्थोगोनल आव्यूह क्यूआर अपघटन हो सकता है # [[ घुमाव देता है ]] का उपयोग 2 से 2 रोटेशन के उत्पाद में किया जाता है, जिसे गिवेंस रोटेशन और हाउसहोल्डर रिफ्लेक्शंस कहा जाता है। यह सहज रूप से अपील कर रहा है क्योंकि एक ऑर्थोगोनल आव्यूह द्वारा एक वेक्टर के गुणन से उस वेक्टर की लंबाई को संरक्षित किया जाता है, और घुमाव और प्रतिबिंब (वास्तविक मूल्यवान) ज्यामितीय संचालन के सेट को समाप्त कर देते हैं जो एक वेक्टर की लंबाई को अपरिवर्तित करते हैं। | ||
हाउसहोल्डर परिवर्तन को समूह सिद्धांत में परिभाषित एकात्मक मैट्रिसेस के कैनोनिकल कोसेट अपघटन के साथ एक-से-एक संबंध दिखाया गया था, जिसका उपयोग बहुत ही कुशल तरीके से एकात्मक ऑपरेटरों को पैरामीट्रिज करने के लिए किया जा सकता है।<ref>{{cite journal | हाउसहोल्डर परिवर्तन को समूह सिद्धांत में परिभाषित एकात्मक मैट्रिसेस के कैनोनिकल कोसेट अपघटन के साथ एक-से-एक संबंध दिखाया गया था, जिसका उपयोग बहुत ही कुशल तरीके से एकात्मक ऑपरेटरों को पैरामीट्रिज करने के लिए किया जा सकता है।<ref>{{cite journal | ||
Line 144: | Line 149: | ||
|arxiv=1008.2477|bibcode=2010JMP....51h2101C | |arxiv=1008.2477|bibcode=2010JMP....51h2101C | ||
|s2cid=119641896 }}</ref> | |s2cid=119641896 }}</ref> | ||
अंत में हम ध्यान देते हैं कि एक सिंगल हाउसहोल्डर ट्रांसफॉर्म, एक अकेले गिवेंस ट्रांसफॉर्म के विपरीत, एक | अंत में हम ध्यान देते हैं कि एक सिंगल हाउसहोल्डर ट्रांसफॉर्म, एक अकेले गिवेंस ट्रांसफॉर्म के विपरीत, एक आव्यूह के सभी स्तम्भ पर कार्य कर सकता है, और इस तरह क्यूआर अपघटन और ट्राइडायगोनलाइजेशन के लिए सबसे कम कम्प्यूटेशनल लागत प्रदर्शित करता है। इस कम्प्यूटेशनल इष्टतमता के लिए दंड, निश्चित रूप से, घरेलू संचालन को गहराई से या कुशलतापूर्वक समानांतर नहीं किया जा सकता है। इस प्रकार अनुक्रमिक मशीनों पर सघन मैट्रिसेस के लिए हाउसहोल्डर को प्राथमिकता दी जाती है, जबकि विरल मैट्रिसेस और/या समानांतर मशीनों पर गिवेंस को प्राथमिकता दी जाती है। | ||
== यह भी देखें == | == यह भी देखें == |
Revision as of 09:52, 25 April 2023
रैखिक बीजगणित में, एक हाउसहोल्डर परिवर्तन (जिसे हाउसहोल्डर परावर्तन या प्राथमिक प्रतिक्षेपक के रूप में भी जाना जाता है) एक रैखिक परिवर्तन है जो एक प्लेन (गणित) या हाइपरप्लेन के बारे में एक परावर्तन (गणित) का वर्णन करता है जिसमें मूल होता है। एलस्टन स्कॉट हाउसहोल्डर द्वारा 1958 के पेपर में हाउसहोल्डर परिवर्तन का उपयोग किया गया था।[1]
सामान्य आंतरिक उत्पाद रिक्त स्थान पर इसका एनालॉग हाउसहोल्डर संचालिका है।
परिभाषा
परिवर्तन
प्रतिबिंब हाइपरप्लेन को इसके सामान्य वेक्टर, एक इकाई वेक्टर द्वारा परिभाषित किया जा सकता है (लंबाई के साथ एक वेक्टर ) जो हाइपरप्लेन के लिए ओर्थोगोनल है। एक बिंदु का प्रतिबिंब (ज्यामिति) इस हाइपरप्लेन के बारे में रैखिक परिवर्तन है:
जहाँ हर्मिटियन ट्रांसपोज़ के साथ स्तंभ इकाई वेक्टर के रूप में दिया गया है .
हाउसहोल्डर आव्यूह
इस परिवर्तन से निर्मित आव्यूह को बाहरी उत्पाद के रूप में व्यक्त किया जा सकता है:
हाउसहोल्डर आव्यूह के रूप में जाना जाता है, जहां पहचान आव्यूह है।
गुण
हाउसहोल्डर आव्यूह में निम्नलिखित गुण होते हैं:
- यह हर्मिटियन आव्यूह है: ,
- यह एकात्मक आव्यूह है: ,
- इसलिए यह अनैच्छिक आव्यूह है: .
- हाउसहोल्डर आव्यूह में आइगेनवैल्यू {} होते हैं। इसे देखने के लिए, ध्यान दें कि यदि {} सदिश {} के लिए ओर्थोगोनल है, जिसका उपयोग परावर्तक बनाने के लिए किया गया था, तो {} बहुलता {} का आइगेनमान है, क्योंकि {} स्वतंत्र सदिश ऑर्थोगोनल हैं { }। इसके अलावा, {} पर ध्यान दें, और इसलिए {} बहुलता () के साथ एक ईगेनवैल्यू है।
- हाउसहोल्डर परावर्तक का निर्धारक होता है , चूंकि एक आव्यूह का निर्धारक इसके ईगेनवैल्यू का उत्पाद है, इस स्थति में जिनमें से एक है शेष होने के साथ (जैसा कि पिछले बिंदु में है)।
अनुप्रयोग
ज्यामितीय प्रकाशिकी
ज्यामितीय प्रकाशिकी में, स्पेक्युलर प्रतिबिंब को हाउसहोल्डर आव्यूह के संदर्भ में व्यक्त किया जा सकता है (देखें स्पेक्युलर परावर्तन या वेक्टर सूत्रीकरण § Notes).
संख्यात्मक रैखिक बीजगणित
संख्यात्मक रेखीय बीजगणित में घरेलू परिवर्तनों का व्यापक रूप से उपयोग किया जाता है, उदाहरण के लिए, आव्यूह के मुख्य विकर्ण के नीचे की प्रविष्टियों को मिटाने के लिए[2] क्यूआर अपघटन करने के लिए और क्यूआर एल्गोरिदम के पहले चरण में हेसनबर्ग आव्यूह फॉर्म में बदलने के लिए उनका व्यापक रूप से उपयोग किया जाता है। सममित या हर्मिटियन आव्यूह मैट्रिसेस के लिए, समरूपता को संरक्षित किया जा सकता है, जिसके परिणामस्वरूप ट्राइडायगोनलाइज़ेशन होता है।[3]
क्यूआर अपघटन
हाउसहोल्डर प्रतिबिंबों का उपयोग क्यूआर अपघटन की गणना करने के लिए किया जा सकता है, आव्यूह के पहले एक स्तम्भ को एक मानक आधार वेक्टर के एक से अधिक पर प्रतिबिंबित करके, परिवर्तन आव्यूह की गणना करके, इसे मूल आव्यूह के साथ गुणा करके और फिर नीचे की ओर पुनरावर्ती उस उत्पाद का सामान्य (रैखिक बीजगणित)।
त्रिभुजकरण
इस प्रक्रिया को बर्डन एंड फेयरेस द्वारा न्यूमेरिकल एनालिसिस में प्रस्तुत किया गया है। यह थोड़ा परिवर्तित कार्य का उपयोग करता है के साथ कार्य करें .[4]
पहले चरण में, प्रत्येक चरण में हाउसहोल्डर आव्यूह बनाने के लिए हमें और , निर्धारित करने की आवश्यकता है जो हैं:
और से वेक्टर बनाएँ।
जहाँ , , और
- प्रत्येक के लिए
फिर गणना करें:
मिलने और की गणना करने के बाद के लिए प्रक्रिया को इस प्रकार दोहराया जाता है:
इस तरह से जारी रखते हुए, त्रिभुज और सममित आव्यूह बनता है।
उदाहरण
इस उदाहरण में, बर्डन और फेयरेस से भी दिए गए आव्यूह को हाउसहोल्डर विधि का उपयोग करके समान त्रिकोणीय आव्यूह A3 में बदल दिया गया है।[4]
हाउसहोल्डर पद्धति में उन चरणों का अनुसरण करने पर हमारे पास:
पहला हाउसहोल्डर आव्यूह :
बनाने के लिए का उपयोग किया
जैसा कि हम देख सकते हैं, अंतिम परिणाम एक त्रिकोणीय सममित आव्यूह है जो मूल के समान है। प्रक्रिया दो चरणों के बाद समाप्त हो गई है।
अन्य एकात्मक परिवर्तनों के लिए कम्प्यूटेशनल और सैद्धांतिक संबंध
हाउसहोल्डर परिवर्तन यूनिट नॉर्मल वेक्टर वाले हाइपरप्लेन के बारे में एक प्रतिबिंब है , जैसा कि पहले कहा गया है। एक -द्वारा- एकात्मक परिवर्तन संतुष्ट . निर्धारक लेना (-ज्यामितीय माध्य की शक्ति) और एक एकात्मक आव्यूह के ट्रेस (अंकगणित माध्य के समानुपाती) से पता चलता है कि इसके ईगेनवैल्यू इकाई मापांक है। इसे सीधे और तेजी से देखा जा सकता है:
चूंकि अंकगणितीय और ज्यामितीय साधन समान हैं यदि चर स्थिर हैं (अंकगणित और ज्यामितीय साधनों की असमानता देखें), हम इकाई मापांक का दावा स्थापित करते हैं।
वास्तविक मूल्यवान एकात्मक मेट्रिसेस के स्थति में हम ऑर्थोगोनल मेट्रिसेस प्राप्त करते हैं, . यह अपेक्षाकृत आसानी से अनुसरण करता है (ऑर्थोगोनल आव्यूह देखें) कि कोई भी ऑर्थोगोनल आव्यूह क्यूआर अपघटन हो सकता है # घुमाव देता है का उपयोग 2 से 2 रोटेशन के उत्पाद में किया जाता है, जिसे गिवेंस रोटेशन और हाउसहोल्डर रिफ्लेक्शंस कहा जाता है। यह सहज रूप से अपील कर रहा है क्योंकि एक ऑर्थोगोनल आव्यूह द्वारा एक वेक्टर के गुणन से उस वेक्टर की लंबाई को संरक्षित किया जाता है, और घुमाव और प्रतिबिंब (वास्तविक मूल्यवान) ज्यामितीय संचालन के सेट को समाप्त कर देते हैं जो एक वेक्टर की लंबाई को अपरिवर्तित करते हैं।
हाउसहोल्डर परिवर्तन को समूह सिद्धांत में परिभाषित एकात्मक मैट्रिसेस के कैनोनिकल कोसेट अपघटन के साथ एक-से-एक संबंध दिखाया गया था, जिसका उपयोग बहुत ही कुशल तरीके से एकात्मक ऑपरेटरों को पैरामीट्रिज करने के लिए किया जा सकता है।[5] अंत में हम ध्यान देते हैं कि एक सिंगल हाउसहोल्डर ट्रांसफॉर्म, एक अकेले गिवेंस ट्रांसफॉर्म के विपरीत, एक आव्यूह के सभी स्तम्भ पर कार्य कर सकता है, और इस तरह क्यूआर अपघटन और ट्राइडायगोनलाइजेशन के लिए सबसे कम कम्प्यूटेशनल लागत प्रदर्शित करता है। इस कम्प्यूटेशनल इष्टतमता के लिए दंड, निश्चित रूप से, घरेलू संचालन को गहराई से या कुशलतापूर्वक समानांतर नहीं किया जा सकता है। इस प्रकार अनुक्रमिक मशीनों पर सघन मैट्रिसेस के लिए हाउसहोल्डर को प्राथमिकता दी जाती है, जबकि विरल मैट्रिसेस और/या समानांतर मशीनों पर गिवेंस को प्राथमिकता दी जाती है।
यह भी देखें
- घुमाव देता है
- जैकोबी रोटेशन
टिप्पणियाँ
- ↑ Householder, A. S. (1958). "Unitary Triangularization of a Nonsymmetric Matrix" (PDF). Journal of the ACM. 5 (4): 339–342. doi:10.1145/320941.320947. MR 0111128. S2CID 9858625.
- ↑ Taboga, Marco. "Householder matrix, Lectures on matrix algebra".
- ↑ Schabauer, Hannes; Pacher, Christoph; Sunderland, Andrew G.; Gansterer, Wilfried N. (2010-05-01). "सामान्यीकृत जटिल सममित eigenvalue समस्याओं के लिए एक समानांतर सॉल्वर की ओर". Procedia Computer Science (in English). 1 (1): 437–445. doi:10.1016/j.procs.2010.04.047.
- ↑ 4.0 4.1 Burden, Richard; Faires, Douglas; Burden, Annette (2016). संख्यात्मक विश्लेषण (10th ed.). Thomson Brooks/Cole. ISBN 9781305253667.
- ↑ Renan Cabrera; Traci Strohecker; Herschel Rabitz (2010). "The canonical coset decomposition of unitary matrices through Householder transformations". Journal of Mathematical Physics. 51 (8): 082101. arXiv:1008.2477. Bibcode:2010JMP....51h2101C. doi:10.1063/1.3466798. S2CID 119641896.
संदर्भ
- LaBudde, C.D. (1963). "The reduction of an arbitrary real square matrix to tridiagonal form using similarity transformations". Mathematics of Computation. American Mathematical Society. 17 (84): 433–437. doi:10.2307/2004005. JSTOR 2004005. MR 0156455.
- Morrison, D.D. (1960). "Remarks on the Unitary Triangularization of a Nonsymmetric Matrix". Journal of the ACM. 7 (2): 185–186. doi:10.1145/321021.321030. MR 0114291. S2CID 23361868.
- Cipra, Barry A. (2000). "The Best of the 20th Century: Editors Name Top 10 Algorithms". 33 (4): 1.
{{cite journal}}
: Cite journal requires|journal=
(help) (Herein Householder Transformation is cited as a top 10 algorithm of this century) - Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Section 11.3.2. Householder Method". Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8.