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

रैखिक बीजगणित में, एक हाउसहोल्डर ट्रांसफ़ॉर्मेशन (जिसे हाउसहोल्डर रिफ्लेक्शन या प्राथमिक रिफ्लेक्टर के रूप में भी जाना जाता है) एक रैखिक परिवर्तन है जो एक प्लेन (गणित) या hyperplane के बारे में एक रिफ्लेक्शन (गणित) का वर्णन करता है जिसमें मूल होता है। एलस्टन स्कॉट हाउसहोल्डर द्वारा 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}$ बहुलता का एक eigenvalue है ${\textstyle n-1}$, क्योंकि वहां हैं ${\textstyle n-1}$ स्वतंत्र वैक्टर ओर्थोगोनल करने के लिए ${\textstyle v}$. साथ ही, नोटिस करें ${\textstyle Pv=-v}$, इसलिए ${\textstyle -1}$ बहुलता के साथ एक eigenvalue है ${\textstyle 1}$.
• गृहस्थ परावर्तक का निर्धारक होता है ${\textstyle -1}$, चूंकि एक मैट्रिक्स का निर्धारक इसके eigenvalues ​​​​का उत्पाद है, इस मामले में जिनमें से एक है ${\textstyle -1}$ शेष होने के साथ ${\textstyle 1}$ (जैसा कि पिछले बिंदु में है)।

अनुप्रयोग

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

ज्यामितीय प्रकाशिकी में, स्पेक्युलर प्रतिबिंब को हाउसहोल्डर मैट्रिक्स के संदर्भ में व्यक्त किया जा सकता है (देखेंSpecular reflection § Vector formulation).

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

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

क्यूआर अपघटन

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

त्रिभुजकरण

Main article: Tridiagonal matrix

इस प्रक्रिया को बर्डन एंड फेयरेस द्वारा न्यूमेरिकल एनालिसिस में प्रस्तुत किया गया है। यह थोड़ा बदला हुआ उपयोग करता है $\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}}$

इस तरह से जारी रखते हुए, त्रिभुज और सममित मैट्रिक्स बनता है।

उदाहरण

इस उदाहरण में, बर्डन और फेयरेस से भी,दिया गया मैट्रिक्स समान त्रिभुज मैट्रिक्स A में रूपांतरित हो जाता है₃ गृहस्थ पद्धति का उपयोग करके।

$\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: Rotation (mathematics)

हाउसहोल्डर ट्रांसफ़ॉर्मेशन यूनिट नॉर्मल वेक्टर वाले हाइपरप्लेन के बारे में एक प्रतिबिंब है ${\textstyle v}$, जैसा कि पहले कहा गया है। एक ${\textstyle N}$-द्वारा-${\textstyle N}$ एकात्मक परिवर्तन ${\textstyle U}$ संतुष्ट ${\textstyle UU^{\textsf {H}}=I}$. निर्धारक लेना (${\textstyle N}$-ज्यामितीय माध्य की शक्ति) और एक एकात्मक मैट्रिक्स के ट्रेस (अंकगणित माध्य के समानुपाती) से पता चलता है कि इसके eigenvalues ${\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.