Μετασχηματισμός Χάουζχολντερ

Στη γραμμική άλγεβρα, ένας μετασχηματισμός Χάουζχολντερ (επίσης γνωστός ως ανάκλαση Χάουζχολντερ ή στοιχειώδης ανακλαστήρας) είναι ένας γραμμικός μετασχηματισμός που περιγράφει μια ανάκλαση γύρω από ένα επίπεδο ή υπερεπίπεδο που περιέχει την αρχή. Ο μετασχηματισμός Χάουζχολντερ χρησιμοποιήθηκε σε μια εργασία του 1958 από τον Άλστον Σκοτ Χάουζχολντερ^[1].

Το ανάλογό του σε γενικό χώρο εσωτερικού γινομένου^[2] είναι ο τελεστής Χάουζχολντερ.

Ορισμός

Μετασχηματισμός

Το υπερεπίπεδο ανάκλασης μπορεί να οριστεί από το κανονικό διάνυσμα του, ένα μοναδιαίο διάνυσμα $v$ (ένα διάνυσμα με μήκος $1$) που είναι ορθογώνιο προς το υπερεπίπεδο. Η αντανάκλαση ενός σημείου $x$ ως προς αυτό το υπερεπίπεδο είναι ο γραμμικός μετασχηματισμός:

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

όπου $v$ δίνεται ως μοναδιαίο διάνυσμα στήλης με συζυγή αντιμετάθεση $v^{\textsf {*}}$.

Πίνακας Χάουζχολντερ

Ο πίνακας που κατασκευάζεται από αυτόν τον μετασχηματισμό μπορεί να εκφραστεί ως εξωτερικό γινόμενο ως εξής:

${\displaystyle P=I-2vv^{*}}$

είναι γνωστός ως πίνακας Χάουζχολντερ, όπου $I$ είναι ο ταυτοτικός πίνακας.

Ιδιότητες

Ο πίνακας Χάουζχολντερ έχει τις ακόλουθες ιδιότητες:

• είναι Ερμιτιανός: $P=P^{*}$,
• είναι μοναδιαίος: $P^{-1}=P^{*}$,
• άρα είναι ενελεκτικός: $P=P^{-1}$.
• Ένας πίνακας Χάουζχολντερ έχει ιδιοτιμές $\pm 1$. Για να το δούμε αυτό, παρατηρούμε ότι αν $u$ είναι ορθογώνιο προς το διάνυσμα $v$ που χρησιμοποιήθηκε για τη δημιουργία του ανακλαστήρα, τότε $Pu=u$, δηλ, $1$ είναι μια ιδιοτιμή πολλαπλότητας $n-1$, αφού υπάρχουν $n-1$ ανεξάρτητα διανύσματα ορθογώνια προς το $v$. Επίσης, παρατηρούμε ότι $Pv=-v$, και έτσι $-1$ είναι μια ιδιοτιμή με πολλαπλότητα $1$.
• Η ορίζουσα ενός ανακλαστήρα Χάουζχολντερ είναι $-1$, αφού η ορίζουσα ενός πίνακα είναι το γινόμενο των ιδιοτιμών του, στην περίπτωση αυτή μία από τις οποίες είναι $-1$ με το υπόλοιπο να είναι $1$ (όπως στο προηγούμενο σημείο).

Εφαρμογές

Γεωμετρική οπτική

Στη γεωμετρική οπτική, η κατοπτρική ανάκλαση μπορεί να εκφραστεί με όρους του πίνακα Χάουζχολντερ

Αριθμητική γραμμική άλγεβρα

Οι μετασχηματισμοί Χάουζχολντερ χρησιμοποιούνται ευρέως στην αριθμητική γραμμική άλγεβρα, για παράδειγμα, για την εκμηδένιση των καταχωρήσεων κάτω από την κύρια διαγώνιο ενός πίνακα,^[3] για την εκτέλεση αναλύσεων QR και στο πρώτο βήμα του αλγορίθμου QR. Χρησιμοποιούνται επίσης ευρέως για τον μετασχηματισμό σε μορφή Έσενμπεργκ. Για συμμετρικούς ή ερμιτιανούς πίνακες, η συμμετρία μπορεί να διατηρηθεί, με αποτέλεσμα την τριδιαγωνοποίηση^[4].

Παραγοντοποίηση QR

Οι ανακλάσεις Χάουζχολντερ μπορούν να χρησιμοποιηθούν για τον υπολογισμό της Παραγοντοποίησης QR αντανακλώντας πρώτα μια στήλη ενός πίνακα σε ένα πολλαπλάσιο ενός τυπικού διανύσματος βάσης, υπολογίζοντας τον πίνακα μετασχηματισμού, πολλαπλασιάζοντάς τον με τον αρχικό πίνακα και στη συνέχεια ανατρέχοντας προς τα κάτω στους ${\textstyle (i,i)}$ ελάσσονες αυτού του γινομένου. Για να επιτευχθεί αυτό, αναζητείται ένας ερμιτιανός μοναδιαίος πίνακας Q' ο οποίος παίρνει ένα μιγαδικό διάνυσμα x σε μιγαδικό πολλαπλάσιο ενός μιγαδικού διανύσματος e. Για την ανάλυση QR, το e θα είναι ένα μοναδιαίο διάνυσμα συντεταγμένων, π.χ. για την k-th συντεταγμένη. Ένας μιγαδικός πίνακας Q' που έχει τη μορφή Q' = I - u u* με u* u = 2 έχει την επιθυμητή ιδιότητα να είναι ερμητικά μοναδιαίος. Εδώ το * δηλώνει τη συζυγή ανάστροφος. Δεδομένου ότι τα μόνα δύο διανύσματα που εμπλέκονται είναι τα x και e, το διάνυσμα u πρέπει να έχει τη μορφή u = a x. + b e, όπου a και b είναι μιγαδικοί συντελεστές που πρέπει να προσδιοριστούν. Εφόσον ένας συνολικός συντελεστής φάσης για το u δεν έχει σημασία, ο συντελεστής a μπορεί να επιλεγεί να είναι θετικός πραγματικός. Τώρα Q x = x (1 – a (u* x)) - e (b (u* x)). Για να είναι ο συντελεστής του διανύσματος x μηδέν, οι δύο όροι στο u* x' πρέπει να έχουν την ίδια φάση μέσα σε ένα πολλαπλάσιο των 180 μοιρών, οπότε πρέπει να έχουμε arg(b) = arg(e* x) μέσα σε ένα πολλαπλάσιο των 180 μοιρών. Υπάρχουν δύο λύσεις ανάλογα με το αν επιλέγεται ένα άρτιο ή περιττό πολλαπλάσιο των 180 μοιρών. Επομένως, για να είναι μηδέν ο μιγαδικός συντελεστής του διανύσματος x', πρέπει να λυθούν δύο γραμμικές εξισώσεις στα moduli των a και b. Οι φάσεις των a και b έχουν ήδη προσδιοριστεί. Έστω ότι e είναι το k-th μοναδιαίο διάνυσμα συντεταγμένων έτσι ώστε e* e' = 1 και x_k= e* x και έστω |x|= sqrt(x* x'). Τότε τα a και b μπορούν να εκφραστούν απλά είτε ως a =1/sqrt (|x| (|x|+ |x_k|)) και b = a |x| exp(i*arg(x_k)) είτε ως a =1/sqrt (|x| (|x|- |x_k|)) και b = - a |x| exp(i*arg(x_k)). Ο πολλαπλασιαστής του e είναι -b/a και για τις δύο λύσεις. Η πρώτη λύση είναι καλύτερη επειδή ο παρονομαστής δεν μπορεί να είναι κοντά στο μηδέν σε σχέση με το |x|.

Τριδιαγωνοποίηση

Κύριο άρθρο: Τριδιαγώνιος πίνακας

Η διαδικασία αυτή παρουσιάζεται στο βιβλίο Αριθμητική Ανάλυση των Μπάρντεν και Φέαρς. Χρησιμοποιεί ένα ελαφρώς τροποποιημένο ${\displaystyle \operatorname {sgn} }$ συνάρτηση με ${\displaystyle \operatorname {sgn} (0)=1}$.^[5] Στο πρώτο βήμα, για να σχηματίσουμε τον πίνακα Χάουζχολντερ σε κάθε βήμα πρέπει να προσδιορίσουμε τα ${\textstyle \alpha }$ και ${\textstyle r}$, τα οποία είναι:

${\displaystyle {\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}}}$

Από τα $\alpha$ και $r$, κατασκευάστε το διάνυσμα $v$:

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

όπου $v_{1}=0$, $v_{2}={\frac {a_{21}-\alpha }{2r}}$, και :${\displaystyle v_{k}={\frac {a_{k1}}{2r}}}$ για κάθε ${\displaystyle k=3,4\ldots n}$

Στη συνέχεια, υπολογίζουμε:

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

Αφού βρεθεί το $P^{1}$ και υπολογιστεί το $A^{(2)}$ η διαδικασία επαναλαμβάνεται για $k=2,3,\ldots ,n-2$ ως εξής:

${\displaystyle {\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}}}$

Συνεχίζοντας με αυτόν τον τρόπο, σχηματίζεται ο τριδιαγώνιος και συμμετρικός πίνακας.

Παραδείγματα

Σε αυτό το παράδειγμα, επίσης από τους Μπάρντεν και Φέαρς,^[5] ο συγκεκριμένος πίνακας μετασχηματίζεται στον παρόμοιο τριδιαγωνικό πίνακα A₃ με τη χρήση της μεθόδου Χάουζχολντερ.

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

Ακολουθώντας αυτά τα βήματα στη μέθοδο Χάουζχολντερ, έχουμε:

Ο πρώτος πίνακας Χάουζχολντερ:

${\displaystyle {\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}}}$

Χρησιμοποιήσαμε $A_{2}$ για να σχηματίσουμε

${\displaystyle {\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}}}$

Όπως βλέπουμε, το τελικό αποτέλεσμα είναι ένας τριδιαγώνιος συμμετρικός πίνακας που είναι παρόμοιος με τον αρχικό. Η διαδικασία ολοκληρώνεται μετά από δύο βήματα.

Υπολογιστική και θεωρητική σχέση με άλλους μοναδιαίους μετασχηματισμούς

Δείτε επίσης: Περιστροφή (μαθηματικά)^[6]

Ο μετασχηματισμός Χάουζχολντερ είναι μια αντανάκλαση γύρω από ένα υπερεπίπεδο με μοναδιαίο κανονικό διάνυσμα $v$, όπως αναφέρθηκε προηγουμένως. Ένας $N$-προς-$N$ μοναδιαίος μετασχηματισμός $U$ ικανοποιεί την $UU^{*}=I$. Λαμβάνοντας την ορίζουσα ($N$-th δύναμη του γεωμετρικού μέσου) και το ίχνος (ανάλογο του αριθμητικού μέσου) ενός μοναδιαίου πίνακα αποκαλύπτει ότι οι ιδιοτιμές του $\lambda _{i}$ έχουν μοναδιαίο συντελεστή. Αυτό μπορεί να γίνει άμεσα και γρήγορα αντιληπτό:

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

Δεδομένου ότι οι αριθμητικοί και οι γεωμετρικοί μέσοι είναι ίσοι αν οι μεταβλητές είναι σταθερές ( βλ. Ανισότητα αριθμητικού-γεωμετρικού μέσου), τεκμηριώνουμε τον ισχυρισμό του μοναδιαίου modulus.

Για την περίπτωση των μοναδιαίων πινάκων πραγματικής αξίας λαμβάνουμε ορθογώνιους πίνακες,${\textstyle UU^{\textsf {T}}=I}$. Προκύπτει μάλλον εύκολα ( βλ. ορθογώνιος πίνακας) ότι οποιοσδήποτε ορθογώνιος πίνακας μπορεί να παραγοντοποιηθεί σε ένα γινόμενο περιστροφών 2 επί 2, που ονομάζονται περιστροφές Γκίβενς, και ανακλάσεις Χάουσχολντερ. Αυτό είναι ελκυστικό διαισθητικά, δεδομένου ότι ο πολλαπλασιασμός ενός διανύσματος με έναν ορθογώνιο πίνακα διατηρεί το μήκος αυτού του διανύσματος, και οι περιστροφές και οι ανακλάσεις εξαντλούν το σύνολο των (πραγματικών τιμών) γεωμετρικών πράξεων που καθιστούν αμετάβλητο το μήκος ενός διανύσματος.

Ο μετασχηματισμός Χάουζχολντερ αποδείχτηκε ότι έχει μια σχέση ένα προς ένα με την κανονική αποσύνθεση των μοναδιαίων πινάκων που ορίζεται στη θεωρία ομάδων, η οποία μπορεί να χρησιμοποιηθεί για την παραμετροποίηση μοναδιαίων τελεστών με πολύ αποτελεσματικό τρόπο.^[7]

Τέλος, σημειώνουμε ότι ένας μεμονωμένος μετασχηματισμός Χάουζχολντερ, σε αντίθεση με έναν μεμονωμένο μετασχηματισμό Γκίβενς, μπορεί να δράσει σε όλες τις στήλες ενός πίνακα και ως εκ τούτου παρουσιάζει το χαμηλότερο υπολογιστικό κόστος για την παραγοντοποίηση QR και την τριδιαγωνοποίηση. Η ποινή για αυτή την «υπολογιστική βελτιστότητα» είναι, φυσικά, ότι οι πράξεις Χάουζχολντερ δεν μπορούν να παραλληλιστούν τόσο βαθιά ή αποτελεσματικά. Ως εκ τούτου, η Χάουζχολντερ προτιμάται για πυκνούς πίνακες σε ακολουθιακές μηχανές, ενώ η Γκίβενς προτιμάται για αραιούς πίνακες και/ή παράλληλες μηχανές.

Δημοσιεύσεις

• Olivier D. Faugeras (1992). «What can be seen in three dimensions with an uncalibrated stereo rig?». 

• Olivier D. Faugeras; Q.T. Luong; Steven Maybank (1992). «Camera self-calibration: Theory and experiments». doi:10.1007/3-540-55426-2_37. 

• Q.T. Luong and Olivier D. Faugeras (1996). «The Fundamental Matrix: Theory, Algorithms, and Stability Analysis». International Journal of Computer Vision 17 (1): 43–75. doi:10.1007/BF00127818. 

• Olivier Faugeras and Q.T. Luong (2001). The Geometry of Multiple Images. MIT Press. ISBN 978-0-262-06220-6. 

• Richard I. Hartley (1992). «Estimation of relative camera positions for uncalibrated cameras». http://axiom.anu.edu.au/~hartley/Papers/eccv92/Higgins/higgins.pdf. ^{[νεκρός σύνδεσμος]}

• Richard Hartley and Andrew Zisserman (2003). Multiple View Geometry in Computer Vision. Cambridge University Press. ISBN 978-0-521-54051-3. 

• Richard I. Hartley (1997). «In Defense of the Eight-Point Algorithm». IEEE Transactions on Pattern Analysis and Machine Intelligence 19 (6): 580–593. doi:10.1109/34.601246. 
• Beauregard, Raymond A.; Fraleigh, John B. (1973), A First Course In Linear Algebra: with Optional Introduction to Groups, Rings, and Fields, Boston: Houghton Mifflin Company, ISBN 0-395-14017-X, https://archive.org/details/firstcourseinlin0000beau 
• Diaconis, Persi; Shahshahani, Mehrdad (1987), «The subgroup algorithm for generating uniform random variables», Probability in the Engineering and Informational Sciences 1: 15–32, doi:10.1017/S0269964800000255, ISSN 0269-9648 
• Dubrulle, Augustin A. (1999), «An Optimum Iteration for the Matrix Polar Decomposition», Electronic Transactions on Numerical Analysis 8: 21–25, http://etna.mcs.kent.edu/ 
• Poole, David (2006), Linear Algebra: A Modern Introduction (2nd έκδοση), Brooks/Cole, ISBN 0-534-99845-3 
• Strang, Gilbert (July 19, 2005), Linear Algebra and Its Applications (4th έκδοση), Brooks Cole, ISBN 978-0-03-010567-8 

Δείτε επίσης

• Field Arithmetic
• Πραγματικό προβολικό επίπεδο
• Μιγαδικός αριθμός
• Αντιερμιτιανός πίνακας
• Μέγιστος κοινός διαιρέτης
• Υπολογιστική βιολογία
• Ελάσσων (γραμμική άλγεβρα)
• Προβολή (γραμμική άλγεβρα)
• Συμμετρικός πίνακας
• Άλγεβρα Μπουλ
• Πολλαπλασιασμός πινάκων
• Επαναλαμβανόμενη συνάρτηση
• Χώρος Γραμμών και Χώρος Στηλών
• Αντιστρέψιμος πίνακας
• Σχέση ισοδυναμίας
• High performance algorithms for reduction to condensed (Hessenberg, tridiagonal, bidiagonal) form

Εξωτερικοί σύνδεσμοι

• English - Greek Dictionary of Pure and Applied Mathematics Εθνικό Μετσόβιο Πολυτεχνείο
• Αγγλοελληνικό Λεξικό Μαθηματικής Ορολογίας - Πανεπιστήμιο Κύπρου
• Matrix calculator
• Matrix Analysis
• Complex-Valued Matrix Derivatives: With Applications in Signal Processing ...
• Foundation Mathematics for Computer Science: A Visual Approach
• Multidimensional Statistical Analysis and Theory of Random Matrices ...
• Quantum Probability and Spectral Analysis of Graphs.
• Symplectic Methods in Harmonic Analysis and in Mathematical Physics...
• Computer Analysis of Images and Patterns: 16th International Conference ...
• High Performance Algorithms for Structured Matrix Problems ..
• Matrix Operations for Engineers and Scientists: An Essential Guide in Linear ........
• Applied Mathematical Methods...

Παραπομπές

1. Householder, A. S. (1958). «Unitary Triangularization of a Nonsymmetric Matrix». Journal of the ACM 5 (4): 339–342. doi:10.1145/320941.320947.
   MR 0111128
   . https://hal.archives-ouvertes.fr/hal-01316095/file/p339householderb.pdf. 
2. «Χώροι με εσωτερικό γινόμενο - Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών» (PDF). 
3. Taboga, Marco. «Householder matrix, Lectures on matrix algebra». 
4. Schabauer, Hannes; Pacher, Christoph; Sunderland, Andrew G.; Gansterer, Wilfried N. (2010-05-01). «Toward a parallel solver for generalized complex symmetric eigenvalue problems» (στα αγγλικά). Procedia Computer Science 1 (1): 437–445. doi:10.1016/j.procs.2010.04.047. 
5. Burden, Richard· Faires, Douglas· Burden, Annette (2016). Numerical analysis (10th έκδοση). Thomson Brooks/Cole. ISBN 9781305253667. 
6. «Rotation | Encyclopedia.com». www.encyclopedia.com. Ανακτήθηκε στις 20 Σεπτεμβρίου 2024. 
7. Renan Cabrera; Traci Strohecker; Herschel Rabitz (2010). «The canonical coset decomposition of unitary matrices through Householder transformations». Journal of Mathematical Physics 51 (8): 082101. doi:10.1063/1.3466798. Bibcode: 2010JMP....51h2101C. 

• Epipolar Geometry and the Fundamental Matrix (chapter from Hartley & Zisserman)
• 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.
  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
  . 
• Cipra, Barry A. (2000). «The Best of the 20th Century: Editors Name Top 10 Algorithms». SIAM News 33 (4): 1. https://archive.siam.org/news/news.php?id=637.  (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 έκδοση). New York: Cambridge University Press. ISBN 978-0-521-88068-8. Αρχειοθετήθηκε από το πρωτότυπο στις 11 Αυγούστου 2011. Ανακτήθηκε στις 13 Αυγούστου 2011.