Ταυτοτικός πίνακας Γούντμπερι

Στα μαθηματικά (συγκεκριμένα στη γραμμική άλγεβρα), ο ταυτοτικός πίνακας Γούντμπερι, που πήρε το όνομά της από τον Μαξ Α. Γούντμπερι, λέει ότι ο αντίστροφος μιας rank-k διόρθωσης κάποιου πίνακα μπορεί να υπολογιστεί κάνοντας μια rank-k διόρθωση στον αντίστροφο του αρχικού πίνακα. Εναλλακτικά ονόματα για τον τύπο αυτό είναι το λήμμα αντιστροφής πινάκων, ο τύπος Σέρμαν-Μόρισον-Γούντμπερι ή απλά ο τύπος Γούντμπερι. Ωστόσο, η ταυτότητα εμφανίστηκε σε αρκετές εργασίες πριν από την έκθεση Γούντμπερι.

Ο Ταυτοτικός πίνακας Γούντμπερι είναι

${(A+UCV)}^{-1}=A^{-1}-A^{-1}U{(C^{-1}+V{A}^{-1}U)}^{-1}V{A}^{-1},$

όπου A, U, C και V είναι συμμορφώσιμοι πίνακες: Ο A είναι n×n, ο C είναι k×k, ο U είναι n×k,και ο V είναι k×n. Αυτό μπορεί να προκύψει χρησιμοποιώντας την αντιστροφή πινάκων.

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

Ο Ταυτοτικός πίνακας Γούντμπερι επιτρέπει τον απλό υπολογισμό των αντιστρόφων και των λύσεων των γραμμικών εξισώσεων. Ωστόσο, λίγα είναι γνωστά για την αριθμητική σταθερότητα του τύπου. Δεν υπάρχουν δημοσιευμένα αποτελέσματα σχετικά με τα όρια σφάλματός της. Ανέκδοτα στοιχεία υποδηλώνει ότι μπορεί να αποκλίνει ακόμη και για φαινομενικά καλά παραδείγματα (όταν τόσο ο αρχικός όσο και ο τροποποιημένος πίνακας είναι καλά προετοιμασμένοι).

Συζήτηση

Για να αποδείξουμε αυτό το αποτέλεσμα, θα ξεκινήσουμε με την απόδειξη ενός απλούστερου. Αντικαθιστώντας τους A και C με τον ταυτοτικό πίνακα I, παίρνουμε μια άλλη ταυτότητα που είναι λίγο πιο απλή:

${(I+UV)}^{-1}=I-U{(I+VU)}^{-1}V.$

Για να ανακτήσουμε την αρχική εξίσωση από αυτή την μειωμένη ταυτότητα, αντικαθιστούμε το $U$ με το $A^{-1}U$ και το $V$ με το $CV$.

Η ίδια αυτή η ταυτότητα μπορεί να θεωρηθεί ως ο συνδυασμός δύο απλούστερων ταυτοτήτων. Η πρώτη ταυτότητα προκύπτει από

$I=(I+P{)}^{-1}(I+P)=(I+P{)}^{-1}+(I+P{)}^{-1}P,$

συνεπώς,

$(I+P{)}^{-1}=I-(I+P{)}^{-1}P,$

και αντίστοιχα

$(I+P{)}^{-1}=I-P(I+P{)}^{-1}.$

Η δεύτερη ταυτότητα είναι η λεγόμενη push-through identity $(I+UV{)}^{-1}U=U(I+VU{)}^{-1}$

την οποία λαμβάνουμε από $U(I+VU)=(I+UV)U$

αφού πολλαπλασιάσουμε με $(I+VU{)}^{-1}$ στα δεξιά και με $(I+UV{)}^{-1}$ στα αριστερά.

Συνδυάζοντας τα όλα μαζί,

${(I+UV)}^{-1}=I-UV{(I+UV)}^{-1}=I-U{(I+VU)}^{-1}V.$

όπου η πρώτη και η δεύτερη ισότητα προέρχονται από την πρώτη και τη δεύτερη ταυτότητα, αντίστοιχα.

Ειδικές περιπτώσεις

Όταν $V,U$ είναι διανύσματα, η ταυτότητα ανάγεται στον τύπο Σέρμαν-Μόρισον.

Στην περίπτωση των κλιμάκων, η μειωμένη εκδοχή είναι απλά

$\frac{1}{1+uv}=1-\frac{uv}{1+uv}.$

Αντίστροφο ενός αθροίσματος

Αν n = k και U = V = I_n είναι ο ταυτοτικός πίνακας, τότε

$\begin{array}{cc}{(A+B)}^{-1}& =A^{-1}-A^{-1}{(B^{-1}+A^{-1})}^{-1}{A}^{-1}\\ & =A^{-1}-A^{-1}{(A{B}^{-1}+I)}^{-1}.\end{array}$

Προχωρώντας με τη συγχώνευση των όρων της ακροδεξιάς πλευράς της παραπάνω εξίσωσης προκύπτει η ταυτότητα της Χούα

${(A+B)}^{-1}=A^{-1}-{(A+A{B}^{-1}A)}^{-1}.$

Μια άλλη χρήσιμη μορφή της ίδιας ταυτότητας είναι

${(A-B)}^{-1}=A^{-1}+A^{-1}B{(A-B)}^{-1},$

η οποία, σε αντίθεση με τις παραπάνω, είναι έγκυρη ακόμα και αν το $B$ είναι ιδιάζουσα, και έχει μια αναδρομική δομή που δίνει

${(A-B)}^{-1}=\sum _{k=0}^{\mathrm{\infty }}{\left(A^{-1}B\right)}^k{A}^{-1}$

αν η φασματική ακτίνα του $A^{-1}B$ είναι μικρότερη από ένα. Δηλαδή, αν το παραπάνω άθροισμα συγκλίνει τότε είναι ίσο με $(A-B{)}^{-1}$.

Αυτή η μορφή μπορεί να χρησιμοποιηθεί σε διαταρακτικές αναπτύξεις όπου το B είναι μια διαταραχή του A.

Παραλλαγές

Διωνυμικό αντίστροφο θεώρημα

Αν A, B, U, V είναι πίνακες μεγέθους n×n', k×k, n×k, k×n, αντίστοιχα, τότε

${(A+UBV)}^{-1}=A^{-1}-A^{-1}UB{(B+BV{A}^{-1}UB)}^{-1}BV{A}^{-1}$

υπό την προϋπόθεση ότι τα A και B + BVA⁻¹UB είναι μη-ιδιάζοντες. Η μη-ιδιάζουσα ιδιότητα του τελευταίου απαιτεί την ύπαρξη του B⁻¹, αφού ισούται με Πρότυπο:Nowrap και η τάξη του τελευταίου δεν μπορεί να υπερβαίνει την τάξη του B..

Εφόσον το Β είναι αντιστρέψιμο, οι δύο όροι Β που πλαισιώνουν την παρενθετική αντίστροφη ποσότητα στη δεξιά πλευρά μπορούν να αντικατασταθούν με Πρότυπο:Nowrap γεγονός που οδηγεί στην αρχική ταυτότητα του Γούντμπερι.

Μια παραλλαγή για την περίπτωση που το B είναι μοναδικό και πιθανώς ακόμη και μη τετραγωνικό: $(A+UBV{)}^{-1}=A^{-1}-A^{-1}U(I+BV{A}^{-1}U{)}^{-1}BV{A}^{-1}.$

Υπάρχουν επίσης τύποι για ορισμένες περιπτώσεις στις οποίες το Α είναι ιδιάζων.

Ψευδοαντίστροφο με θετικούς ημιπεριορισμένους πίνακες

Γενικά, η ταυτότητα του Γούντμπερι δεν είναι έγκυρη εάν μία ή περισσότερες αντιστροφές αντικατασταθούν από ψευδοαντιστροφές (Μουρ-Πένροουζ). Ωστόσο, εάν οι $A$ and $C$ είναι θετικά ημιπεπεριορισμένοι και $V=U^{\mathrm{H}}$ (υπονοώντας ότι το $A+UCV$ είναι το ίδιο θετικά ημιτελές), τότε ο ακόλουθος τύπος παρέχει μια γενίκευση:

$\begin{array}{cc}{(X{X}^{\mathrm{H}}+Y{Y}^{\mathrm{H}})}^{+}& ={\left(Z{Z}^{\mathrm{H}}\right)}^{+}+{(I-Y{Z}^{+})}^{\mathrm{H}}{X}^{+\mathrm{H}}E{X}^{+}(I-Y{Z}^{+}),\\ Z& =(I-X{X}^{+})Y,\\ E& =I-X^{+}Y(I-Z^{+}Z)F^{-1}{\left(X^{+}Y\right)}^{\mathrm{H}},\\ F& =I+(I-Z^{+}Z)Y^{\mathrm{H}}{\left(X{X}^{\mathrm{H}}\right)}^{+}Y(I-Z^{+}Z),\end{array}$

όπου $A+UC{U}^{\mathrm{H}}$ μπορεί να γραφεί ως $X{X}^{\mathrm{H}}+Y{Y}^{\mathrm{H}}$ επειδή κάθε θετικά ημιτελής πίνακας είναι ίσος με $M{M}^{\mathrm{H}}$ για κάποιο $M$.

Παράγωγα

Άμεση απόδειξη

Ο τύπος μπορεί να αποδειχθεί ελέγχοντας ότι $(A+UCV)$ επί το υποτιθέμενο αντίστροφό του στη δεξιά πλευρά της ταυτότητας του Γούντμπερι δίνει τον ταυτοτικό πίνακα:

$\begin{array}{cc}& (A+UCV)[A^{-1}-A^{-1}U{(C^{-1}+V{A}^{-1}U)}^{-1}V{A}^{-1}]\\ =& \{I-U{(C^{-1}+V{A}^{-1}U)}^{-1}V{A}^{-1}\}+\{UCV{A}^{-1}-UCV{A}^{-1}U{(C^{-1}+V{A}^{-1}U)}^{-1}V{A}^{-1}\}\\ =& \{I+UCV{A}^{-1}\}-\{U{(C^{-1}+V{A}^{-1}U)}^{-1}V{A}^{-1}+UCV{A}^{-1}U{(C^{-1}+V{A}^{-1}U)}^{-1}V{A}^{-1}\}\\ =& I+UCV{A}^{-1}-(U+UCV{A}^{-1}U){(C^{-1}+V{A}^{-1}U)}^{-1}V{A}^{-1}\\ =& I+UCV{A}^{-1}-UC(C^{-1}+V{A}^{-1}U){(C^{-1}+V{A}^{-1}U)}^{-1}V{A}^{-1}\\ =& I+UCV{A}^{-1}-UCV{A}^{-1}\\ =& I.\end{array}$

Εναλλακτικές αποδείξεις

Πρότυπο:Collapse top Ας εξετάσουμε πρώτα αυτές τις χρήσιμες ταυτότητες,

$\begin{array}{cc}U+UCV{A}^{-1}U& =UC(C^{-1}+V{A}^{-1}U)=(A+UCV)A^{-1}U\\ {(A+UCV)}^{-1}UC& =A^{-1}U{(C^{-1}+V{A}^{-1}U)}^{-1}\end{array}$

Τώρα,

$\begin{array}{cc}{A}^{-1}& ={(A+UCV)}^{-1}(A+UCV)A^{-1}\\ & ={(A+UCV)}^{-1}(I+UCV{A}^{-1})\\ & ={(A+UCV)}^{-1}+{(A+UCV)}^{-1}UCV{A}^{-1}\\ & ={(A+UCV)}^{-1}+A^{-1}U{(C^{-1}+V{A}^{-1}U)}^{-1}V{A}^{-1}.\end{array}$ Πρότυπο:Collapse bottom

Πρότυπο:Collapse top Η εξαγωγή της ταυτοτικής ταυτότητας του πίνακα του Γούντμπερι γίνεται εύκολα με την επίλυση του ακόλουθου προβλήματος αντιστροφής του πίνακα

$\left[\begin{array}{cc}A& U\\ V& -C^{-1}\end{array}\right]\left[\begin{array}{c}X\\ Y\end{array}\right]=\left[\begin{array}{c}I\\ 0\end{array}\right].$

Με την ανάπτυξη, μπορούμε να δούμε ότι τα παραπάνω ανάγονται σε

$\{\begin{array}{c}AX+UY=I\\ VX-C^{-1}Y=0\end{array}$ που ισοδυναμεί με $(A+UCV)X=I$. Εξαλείφοντας την πρώτη εξίσωση, διαπιστώνουμε ότι $X=A^{-1}(I-UY)$, το οποίο μπορεί να αντικατασταθεί στο δεύτερο για να βρεθεί $V{A}^{-1}(I-UY)=C^{-1}Y$. Αναπτύσσοντας και αναδιατάσσοντας, έχουμε $V{A}^{-1}=(C^{-1}+V{A}^{-1}U)Y$, or ${(C^{-1}+V{A}^{-1}U)}^{-1}V{A}^{-1}=Y$. Τέλος, αντικαθιστούμε στο $AX+UY=I$, και έχουμε $AX+U{(C^{-1}+V{A}^{-1}U)}^{-1}V{A}^{-1}=I$. Συνεπώς,

$(A+UCV{)}^{-1}=X=A^{-1}-A^{-1}U{(C^{-1}+V{A}^{-1}U)}^{-1}V{A}^{-1}.$

Παραγάγαμε την ταυτότητα του πίνακα Γούντμπερι. Πρότυπο:Collapse bottom

Αρχίζουμε με τον πίνακα

$\left[\begin{array}{cc}A& U\\ V& C\end{array}\right]$

Εξαλείφοντας την καταχώρηση κάτω από το A (δεδομένου ότι το A είναι αντιστρέψιμο) έχουμε

$\left[\begin{array}{cc}I& 0\\ -V{A}^{-1}& I\end{array}\right]\left[\begin{array}{cc}A& U\\ V& C\end{array}\right]=\left[\begin{array}{cc}A& U\\ 0& C-V{A}^{-1}U\end{array}\right]$

Ομοίως, η εξάλειψη της καταχώρησης πάνω από το C δίνει

$\left[\begin{array}{cc}A& U\\ V& C\end{array}\right]\left[\begin{array}{cc}I& -A^{-1}U\\ 0& I\end{array}\right]=\left[\begin{array}{cc}A& 0\\ V& C-V{A}^{-1}U\end{array}\right]$

Τώρα συνδυάζοντας τα δύο παραπάνω, έχουμε

$\left[\begin{array}{cc}I& 0\\ -V{A}^{-1}& I\end{array}\right]\left[\begin{array}{cc}A& U\\ V& C\end{array}\right]\left[\begin{array}{cc}I& -A^{-1}U\\ 0& I\end{array}\right]=\left[\begin{array}{cc}A& 0\\ 0& C-V{A}^{-1}U\end{array}\right]$

Η μετακίνηση προς τη δεξιά πλευρά δίνει

$\left[\begin{array}{cc}A& U\\ V& C\end{array}\right]=\left[\begin{array}{cc}I& 0\\ V{A}^{-1}& I\end{array}\right]\left[\begin{array}{cc}A& 0\\ 0& C-V{A}^{-1}U\end{array}\right]\left[\begin{array}{cc}I& A^{-1}U\\ 0& I\end{array}\right]$

η οποία είναι η αποσύνθεση LDU του σύνθετου πίνακα σε έναν άνω τριγωνικό, διαγώνιο και κάτω τριγωνικό πίνακα.

Τώρα αντιστρέφοντας και τις δύο πλευρές προκύπτει

$\begin{array}{cc}{\left[\begin{array}{cc}A& U\\ V& C\end{array}\right]}^{-1}& ={\left[\begin{array}{cc}I& A^{-1}U\\ 0& I\end{array}\right]}^{-1}{\left[\begin{array}{cc}A& 0\\ 0& C-V{A}^{-1}U\end{array}\right]}^{-1}{\left[\begin{array}{cc}I& 0\\ V{A}^{-1}& I\end{array}\right]}^{-1}\\ & =\left[\begin{array}{cc}I& -A^{-1}U\\ 0& I\end{array}\right]\left[\begin{array}{cc}{A}^{-1}& 0\\ 0& {(C-V{A}^{-1}U)}^{-1}\end{array}\right]\left[\begin{array}{cc}I& 0\\ -V{A}^{-1}& I\end{array}\right]\\ & =\left[\begin{array}{cc}{A}^{-1}+A^{-1}U{(C-V{A}^{-1}U)}^{-1}V{A}^{-1}& -A^{-1}U{(C-V{A}^{-1}U)}^{-1}\\ -{(C-V{A}^{-1}U)}^{-1}V{A}^{-1}& {(C-V{A}^{-1}U)}^{-1}\end{array}\right]\mathrm{(}\mathrm{1}\mathrm{)}\end{array}$

Θα μπορούσαμε εξίσου καλά να το είχαμε κάνει με τον άλλο τρόπο (υπό την προϋπόθεση ότι το C είναι αντιστρέψιμο), δηλ.

$\left[\begin{array}{cc}A& U\\ V& C\end{array}\right]=\left[\begin{array}{cc}I& U{C}^{-1}\\ 0& I\end{array}\right]\left[\begin{array}{cc}A-U{C}^{-1}V& 0\\ 0& C\end{array}\right]\left[\begin{array}{cc}I& 0\\ C^{-1}V& I\end{array}\right]$

Τώρα και πάλι αντιστρέφοντας και τις δύο πλευρές,

$\begin{array}{cc}{\left[\begin{array}{cc}A& U\\ V& C\end{array}\right]}^{-1}& ={\left[\begin{array}{cc}I& 0\\ C^{-1}V& I\end{array}\right]}^{-1}{\left[\begin{array}{cc}A-U{C}^{-1}V& 0\\ 0& C\end{array}\right]}^{-1}{\left[\begin{array}{cc}I& U{C}^{-1}\\ 0& I\end{array}\right]}^{-1}\\ & =\left[\begin{array}{cc}I& 0\\ -C^{-1}V& I\end{array}\right]\left[\begin{array}{cc}{(A-U{C}^{-1}V)}^{-1}& 0\\ 0& C^{-1}\end{array}\right]\left[\begin{array}{cc}I& -U{C}^{-1}\\ 0& I\end{array}\right]\\ & =\left[\begin{array}{cc}{(A-U{C}^{-1}V)}^{-1}& -{(A-U{C}^{-1}V)}^{-1}U{C}^{-1}\\ -C^{-1}V{(A-U{C}^{-1}V)}^{-1}& C^{-1}+C^{-1}V{(A-U{C}^{-1}V)}^{-1}U{C}^{-1}\end{array}\right]\mathrm{(}\mathrm{2}\mathrm{)}\end{array}$

Συγκρίνοντας τώρα τα στοιχεία (1, 1) του RHS των (1) και (2) παραπάνω, προκύπτει ο τύπος Γούντμπερι

${(A-U{C}^{-1}V)}^{-1}=A^{-1}+A^{-1}U{(C-V{A}^{-1}U)}^{-1}V{A}^{-1}.$ Πρότυπο:Collapse bottom

Εφαρμογές

Η ταυτότητα αυτή είναι χρήσιμη σε ορισμένους αριθμητικούς υπολογισμούς όπου το A⁻¹ έχει ήδη υπολογιστεί και είναι επιθυμητό να υπολογιστεί το (A + UCV)⁻¹. Με το αντίστροφο του A διαθέσιμο, είναι απαραίτητο να βρεθεί μόνο το αντίστροφο του C⁻¹ + VA⁻¹U για να προκύψει το αποτέλεσμα χρησιμοποιώντας το δεξί μέρος της ταυτότητας. Εάν το C έχει πολύ μικρότερη διάσταση από το A, αυτό είναι πιο αποτελεσματικό από την απευθείας αντιστροφή του A + UCV. Μια συνηθισμένη περίπτωση είναι η εύρεση του αντίστροφου μιας χαμηλής τάξης ενημέρωσης A + UCV του A(όπου το U έχει μόνο λίγες στήλες και το V μόνο λίγες γραμμές), ή η εύρεση μιας προσέγγισης του αντίστροφου του πίνακα A + B όπου ο πίνακας B μπορεί να προσεγγιστεί από έναν χαμηλής τάξης πίνακα UCV, για παράδειγμα χρησιμοποιώντας την Ανάλυση πίνακα σε ιδιάζουσες τιμές.

Αυτό εφαρμόζεται, π.χ. στο φίλτρο Κάλμαν και στις αναδρομικές μεθόδους ελαχίστων τετραγώνων, για την αντικατάσταση της παραμετρικής λύσης, που απαιτεί αντιστροφή ενός πίνακα μεγέθους διανύσματος κατάστασης, με μια λύση βασισμένη σε εξισώσεις κατάστασης. Στην περίπτωση του φίλτρου Κάλμαν, ο πίνακας αυτός έχει τις διαστάσεις του διανύσματος των παρατηρήσεων, δηλαδή είναι τόσο μικρός όσο το 1 στην περίπτωση που επεξεργάζεται κάθε φορά μόνο μία νέα παρατήρηση. Αυτό επιταχύνει σημαντικά τους συχνά σε πραγματικό χρόνο υπολογισμούς του φίλτρου.

Στην περίπτωση που ο C είναι ο ταυτοτικός πίνακας I, ο πίνακας $I+V{A}^{-1}U$ είναι γνωστός στην αριθμητική γραμμική άλγεβρα και στις αριθμητικές μερικές διαφορικές εξισώσεις ως πίνακας χωρητικότητας.

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

• Πρότυπο:Cite journal
• Πρότυπο:Cite book
• Πρότυπο:Cite journal
• Πρότυπο:Citation
• Πρότυπο:Citation
• Golub G. H., van Loan C. F. (1996), Matrix Computations (Johns Hopkins University Press) §4.7—Toeplitz and Related Systems
• Gray R. M., Toeplitz and Circulant Matrices: A Review (Now Publishers) Πρότυπο:Doi
• Πρότυπο:Citation
• Πρότυπο:Citation
• Πρότυπο:Citation

Δείτε επίσης

• 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 ...
• Exercises of Matrices and Linear Algebra
• Fourier Transforms: Approach to Scientific Principles
• Sampling Theory: Beyond Bandlimited Systems.
• Physics and Combinatorics 2000: Proceedings of the Nagoya 2000 International ...
• Optimal and Robust State Estimation: Finite Impulse Response (FIR) and ...
• The Gaussian Approximation Potential: An Interatomic Potential Derived from ...
• Toeplitz and Circulant Matrices: A Review

Παραπομπές

• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.
• Πρότυπο:Citation.