हाउसहोल्डर ट्रांसफ़ॉर्मेशन

रैखिक बीजगणित में, एक हाउसहोल्डर परिवर्तन (जिसे हाउसहोल्डर परावर्तन या प्राथमिक प्रतिक्षेपक के रूप में भी जाना जाता है) एक रैखिक परिवर्तन है जो एक प्लेन (गणित) या अतिसमतल के बारे में एक परावर्तन (गणित) का वर्णन करता है जिसमें मूल होता है। एलस्टन स्कॉट हाउसहोल्डर द्वारा 1958 के पेपर में हाउसहोल्डर परिवर्तन का उपयोग किया गया था।

सामान्य आंतरिक उत्पाद रिक्त स्थान पर इसका एनालॉग हाउसहोल्डर संचालिका है।

परिभाषा

परिवर्तन

प्रतिबिंब अतिसमतल को इसके सामान्य वेक्टर, एक इकाई वेक्टर ${\textstyle v}$ द्वारा परिभाषित किया जा सकता है (लंबाई के साथ एक वेक्टर ${\textstyle 1}$) जो अतिसमतल के लिए ओर्थोगोनल है एक बिंदु ${\textstyle x}$ का प्रतिबिंब (ज्यामिति) इस अतिसमतल के बारे में रैखिक परिवर्तन है:

$x-2\langle x,v\rangle v=x-2v\left(v^{\textsf {H}}x\right),$

जहाँ ${\textstyle v}$ हर्मिटियन ट्रांसपोज़ ${\textstyle v^{\textsf {H}}}$ के साथ स्तंभ इकाई वेक्टर के रूप में दिया गया है .

हाउसहोल्डर आव्यूह

इस परिवर्तन से निर्मित आव्यूह को बाहरी उत्पाद के रूप में व्यक्त किया जा सकता है:

$P=I-2vv^{\textsf {H}}$

हाउसहोल्डर आव्यूह के रूप में जाना जाता है, जहां ${\textstyle I}$ पहचान आव्यूह है।

गुण

हाउसहोल्डर आव्यूह में निम्नलिखित गुण होते हैं:

• यह हर्मिटियन आव्यूह है: ${\textstyle P=P^{\textsf {H}}}$,
• यह एकात्मक आव्यूह है: ${\textstyle P^{-1}=P^{\textsf {H}}}$,
• इसलिए यह अनैच्छिक आव्यूह है: ${\textstyle P=P^{-1}}$.
• हाउसहोल्डर आव्यूह में आइगेनवैल्यू {${\textstyle \pm 1}$} होते हैं। इसे देखने के लिए, ध्यान दें कि यदि {${\textstyle u}$} सदिश {${\textstyle v}$} के लिए ओर्थोगोनल है, जिसका उपयोग परावर्तक बनाने के लिए किया गया था, तो {${\textstyle Pu=u}$} ${\textstyle 1}$ बहुलता {${\textstyle n-1}$} का आइगेनमान है, क्योंकि {${\textstyle n-1}$} स्वतंत्र सदिश ऑर्थोगोनल हैं { ${\textstyle v}$}। इसके अलावा, {${\textstyle Pv=-v}$} पर ध्यान दें, और इसलिए {${\textstyle -1}$} बहुलता (${\textstyle 1}$) के साथ एक ईगेनवैल्यू है।
• हाउसहोल्डर परावर्तक का निर्धारक ${\textstyle -1}$ होता है , चूंकि एक आव्यूह का निर्धारक इसके ईगेनवैल्यू ​​​​का उत्पाद है, इस स्थति में जिनमें से एक ${\textstyle -1}$ है शेष ${\textstyle 1}$ होने के साथ (जैसा कि पिछले बिंदु में है)।

अनुप्रयोग

ज्यामितीय प्रकाशिकी

ज्यामितीय प्रकाशिकी में स्पेक्युलर प्रतिबिंब को हाउसहोल्डर आव्यूह के संदर्भ में व्यक्त किया जा सकता है (देखें स्पेक्युलर परावर्तन या वेक्टर सूत्रीकरण § Notes).

संख्यात्मक रैखिक बीजगणित

संख्यात्मक रेखीय बीजगणित में घरेलू परिवर्तनों का व्यापक रूप से उपयोग किया जाता है, उदाहरण के लिए, आव्यूह के मुख्य विकर्ण के नीचे की प्रविष्टियों को मिटाने के लिए क्यूआर अपघटन करने के लिए और क्यूआर एल्गोरिदम के पहले चरण में हेसनबर्ग आव्यूह फॉर्म में बदलने के लिए उनका व्यापक रूप से उपयोग किया जाता है। सममित या हर्मिटियन आव्यूह मैट्रिसेस के लिए, समरूपता को संरक्षित किया जा सकता है, जिसके परिणामस्वरूप ट्राइडायगोनलाइज़ेशन होता है।

क्यूआर अपघटन

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

त्रिभुजकरण

Main article: त्रिकोणीय आव्यूह

इस प्रक्रिया को बर्डन एंड फेयरेस द्वारा न्यूमेरिकल एनालिसिस में प्रस्तुत किया गया है। यह थोड़ा परिवर्तित $\operatorname {sgn}$ कार्य का उपयोग करता है $\operatorname {sgn} (0)=1$ के साथ कार्य करें .

पहले चरण में, प्रत्येक चरण में हाउसहोल्डर आव्यूह बनाने के लिए हमें ${\textstyle \alpha }$ और ${\textstyle r}$, निर्धारित करने की आवश्यकता है जो हैं:

${\begin{aligned}\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)}};\end{aligned}}$

${\textstyle \alpha }$ और ${\textstyle r}$ से वेक्टर ${\textstyle v}$ बनाएँ।

$v^{(1)}={\begin{bmatrix}v_{1}\\v_{2}\\\vdots \\v_{n}\end{bmatrix}},$

जहाँ ${\textstyle v_{1}=0}$, ${\textstyle v_{2}={\frac {a_{21}-\alpha }{2r}}}$, और

$v_{k}={\frac {a_{k1}}{2r}}$ प्रत्येक के लिए $k=3,4\ldots n$

फिर गणना करें:

${\begin{aligned}P^{1}&=I-2v^{(1)}\left(v^{(1)}\right)^{\textsf {T}}\\A^{(2)}&=P^{1}AP^{1}\end{aligned}}$

${\textstyle P^{1}}$ मिलने और ${\textstyle A^{(2)}}$ की गणना करने के बाद ${\textstyle k=2,3,\ldots ,n-2}$ के लिए प्रक्रिया को इस प्रकार दोहराया जाता है:

${\begin{aligned}\alpha &=-\operatorname {sgn} \left(a_{k+1,k}^{k}\right){\sqrt {\sum _{j=k+1}^{n}\left(a_{jk}^{k}\right)^{2}}}\\[2pt]r&={\sqrt {{\frac {1}{2}}\left(\alpha ^{2}-a_{k+1,k}^{k}\alpha \right)}}\\[2pt]v_{1}^{k}&=v_{2}^{k}=\cdots =v_{k}^{k}=0\\[2pt]v_{k+1}^{k}&={\frac {a_{k+1,k}^{k}-\alpha }{2r}}\\v_{j}^{k}&={\frac {a_{jk}^{k}}{2r}}{\text{ for }}j=k+2,\ k+3,\ \ldots ,\ n\\P^{k}&=I-2v^{(k)}\left(v^{(k)}\right)^{\textsf {T}}\\A^{(k+1)}&=P^{k}A^{(k)}P^{k}\end{aligned}}$

इस तरह से जारी रखते हुए, त्रिभुज और सममित आव्यूह बनता है।

उदाहरण

इस उदाहरण में, बर्डन और फेयरेस से भी दिए गए आव्यूह को हाउसहोल्डर विधि का उपयोग करके समान त्रिकोणीय आव्यूह A3 में बदल दिया गया है।

$\mathbf {A} ={\begin{bmatrix}4&1&-2&2\\1&2&0&1\\-2&0&3&-2\\2&1&-2&-1\end{bmatrix}},$

हाउसहोल्डर पद्धति में उन चरणों का अनुसरण करने पर हमारे पास:

पहला हाउसहोल्डर आव्यूह :

${\begin{aligned}Q_{1}&={\begin{bmatrix}1&0&0&0\\0&-{\frac {1}{3}}&{\frac {2}{3}}&-{\frac {2}{3}}\\0&{\frac {2}{3}}&{\frac {2}{3}}&{\frac {1}{3}}\\0&-{\frac {2}{3}}&{\frac {1}{3}}&{\frac {2}{3}}\end{bmatrix}},\\A_{2}=Q_{1}AQ_{1}&={\begin{bmatrix}4&-3&0&0\\-3&{\frac {10}{3}}&1&{\frac {4}{3}}\\0&1&{\frac {5}{3}}&-{\frac {4}{3}}\\0&{\frac {4}{3}}&-{\frac {4}{3}}&-1\end{bmatrix}},\end{aligned}}$

बनाने के लिए ${\textstyle A_{2}}$ का उपयोग किया

${\begin{aligned}Q_{2}&={\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&-{\frac {3}{5}}&-{\frac {4}{5}}\\0&0&-{\frac {4}{5}}&{\frac {3}{5}}\end{bmatrix}},\\A_{3}=Q_{2}A_{2}Q_{2}&={\begin{bmatrix}4&-3&0&0\\-3&{\frac {10}{3}}&-{\frac {5}{3}}&0\\0&-{\frac {5}{3}}&-{\frac {33}{25}}&{\frac {68}{75}}\\0&0&{\frac {68}{75}}&{\frac {149}{75}}\end{bmatrix}},\end{aligned}}$

जैसा कि हम देख सकते हैं, अंतिम परिणाम एक त्रिकोणीय सममित आव्यूह है जो मूल के समान है। प्रक्रिया दो चरणों के बाद समाप्त हो गई है।

अन्य एकात्मक परिवर्तनों के लिए कम्प्यूटेशनल और सैद्धांतिक संबंध

See also: परिक्रमण (गणित)

जैसा कि पहले कहा गया है। हाउसहोल्डर परिवर्तन ईकाई नॉर्मल वेक्टर ${\textstyle v}$ वाले अतिसमतल के बारे में एक प्रतिबिंब है एक ${\textstyle N}$-द्वारा-${\textstyle N}$ एकात्मक परिवर्तन${\textstyle UU^{\textsf {H}}=I}$. ${\textstyle U}$ को संतुष्ट करता है निर्धारक (${\textstyle N}$-ज्यामितीय माध्य की शक्ति) और एक एकात्मक आव्यूह के रूपांतरण (अंकगणित माध्य के समानुपाती) से पता चलता है कि इसके ईगेनवैल्यू ${\textstyle \lambda _{i}}$ इकाई मापांक है। इसे सीधे और तेजी से देखा जा सकता है:

${\begin{aligned}{\frac {\operatorname {Trace} \left(UU^{\textsf {H}}\right)}{N}}&={\frac {\sum _{j=1}^{N}\left|\lambda _{j}\right|^{2}}{N}}=1,&\operatorname {det} \left(UU^{\textsf {H}}\right)&=\prod _{j=1}^{N}\left|\lambda _{j}\right|^{2}=1.\end{aligned}}$

चूंकि अंकगणितीय और ज्यामितीय साधन समान हैं यदि चर स्थिर हैं (अंकगणित और ज्यामितीय साधनों की असमानता देखें), हम इकाई मापांक का दावा स्थापित करते हैं।

वास्तविक मूल्यवान एकात्मक मेट्रिसेस के स्थति में हम ऑर्थोगोनल मेट्रिसेस ${\textstyle UU^{\textsf {T}}=I}$ प्राप्त करते हैं, यह अपेक्षाकृत आसानी से अनुसरण करता है (ऑर्थोगोनल आव्यूह देखें) कि कोई भी ऑर्थोगोनल आव्यूह क्यूआर अपघटन हो सकता है या घुमाव देता है का उपयोग 2 से 2 घूर्णन के उत्पाद में किया जाता है, जिसे गिवेंस घूर्णन और हाउसहोल्डर प्रतिबिंब कहा जाता है। यह सहज रूप से अपील कर रहा है क्योंकि एक ऑर्थोगोनल आव्यूह द्वारा एक वेक्टर के गुणन से उस वेक्टर की लंबाई को संरक्षित किया जाता है, और घुमाव और प्रतिबिंब (वास्तविक मूल्यवान) ज्यामितीय संचालन के स्थित को समाप्त कर देते हैं जो एक वेक्टर की लंबाई को अपरिवर्तित करते हैं।

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

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

शीनों पर गिवेंस को प्राथमिकता दी जाती है।

यह भी देखें

• घुमाव देता है
• जैकोबी रोटेशन

संदर्भ

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