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

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

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

$\left(A+UCV\right)^{-1}=A^{-1}-A^{-1}U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1},$

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

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

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

Συζήτηση

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

$\left(I+UV\right)^{-1}=I-U\left(I+VU\right)^{-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^[7] $(I+UV)^{-1}U=U(I+VU)^{-1}$

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

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

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

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

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

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

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

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

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

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

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

${\begin{aligned}\left(A+B\right)^{-1}&=A^{-1}-A^{-1}\left(B^{-1}+A^{-1}\right)^{-1}A^{-1}\\[1ex]&=A^{-1}-A^{-1}\left(AB^{-1}+{I}\right)^{-1}.\end{aligned}}$

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

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

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

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

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

$\left({A}-{B}\right)^{-1}=\sum _{k=0}^{\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, αντίστοιχα, τότε

$\left(A+UBV\right)^{-1}=A^{-1}-A^{-1}UB\left(B+BVA^{-1}UB\right)^{-1}BVA^{-1}$

υπό την προϋπόθεση ότι τα A και B + BVA⁻¹UB είναι μη-ιδιάζοντες. Η μη-ιδιάζουσα ιδιότητα του τελευταίου απαιτεί την ύπαρξη του B⁻¹, αφού ισούται με B(I + VA⁻¹UB) και η τάξη του τελευταίου δεν μπορεί να υπερβαίνει την τάξη του B.^[7].

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

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

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

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

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

${\begin{aligned}\left(XX^{\mathrm {H} }+YY^{\mathrm {H} }\right)^{+}&=\left(ZZ^{\mathrm {H} }\right)^{+}+\left(I-YZ^{+}\right)^{\mathrm {H} }X^{+\mathrm {H} }EX^{+}\left(I-YZ^{+}\right),\\Z&=\left(I-XX^{+}\right)Y,\\E&=I-X^{+}Y\left(I-Z^{+}Z\right)F^{-1}\left(X^{+}Y\right)^{\mathrm {H} },\\F&=I+\left(I-Z^{+}Z\right)Y^{\mathrm {H} }\left(XX^{\mathrm {H} }\right)^{+}Y\left(I-Z^{+}Z\right),\end{aligned}}$

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

Παράγωγα

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

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

${\begin{aligned}&\left(A+UCV\right)\left[A^{-1}-A^{-1}U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}\right]\\={}&\left\{I-U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}\right\}+\left\{UCVA^{-1}-UCVA^{-1}U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}\right\}\\={}&\left\{I+UCVA^{-1}\right\}-\left\{U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}+UCVA^{-1}U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}\right\}\\={}&I+UCVA^{-1}-\left(U+UCVA^{-1}U\right)\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}\\={}&I+UCVA^{-1}-UC\left(C^{-1}+VA^{-1}U\right)\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}\\={}&I+UCVA^{-1}-UCVA^{-1}\\={}&I.\end{aligned}}$

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

Εφαρμογές

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

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

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

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

Μαυρογιάννης, Ν. Σ. (Μαΐου 2016). «Μία εισαγωγή στους μιγαδικούς αριθμούς». Εκθέτης Φύλλα Μαθηματικής Παιδείας (16): 1-8. http://ekthetis.gr/Ekthetis016.pdf.
Bronshtein, I. N.· Semendyayev, K. A. (29 Ιουνίου 2013). Handbook of Mathematics. Springer Science & Business Media. ISBN 978-3-662-21982-9.
Belevitch V (1950). «Theory of 2n-terminal networks with applications to conference telephony». Electrical Communication 27: 231–244.
Bareiss, E. H. (1969), «Numerical solution of linear equations with Toeplitz and vector Toeplitz matrices», Numerische Mathematik 13 (5): 404–424, doi:10.1007/BF02163269
Goldreich, O.; Tal, A. (2018), «Matrix rigidity of random Toeplitz matrices», Computational Complexity 27 (2): 305–350, doi:10.1007/s00037-016-0144-9
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:10.1561/0100000006
Noor, F.; Morgera, S. D. (1992), «Construction of a Hermitian Toeplitz matrix from an arbitrary set of eigenvalues», IEEE Transactions on Signal Processing 40 (8): 2093–2094, doi:10.1109/78.149978
Pan, Victor Y. (2001), Structured Matrices and Polynomials: unified superfast algorithms, Birkhäuser, ISBN 978-0817642402
Ye, Ke; Lim, Lek-Heng (2016), «Every matrix is a product of Toeplitz matrices», Foundations of Computational Mathematics 16 (3): 577–598, doi:10.1007/s10208-015-9254-z

Δείτε επίσης

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

Παραπομπές

↑ Max A. Woodbury, Inverting modified matrices, Memorandum Rept. 42, Statistical Research Group, Princeton University, Princeton, NJ, 1950, 4pp MR 38136
↑ Max A. Woodbury, The Stability of Out-Input Matrices. Chicago, Ill., 1949. 5 pp. MR 32564
↑ Guttmann, Louis (1946). «Enlargement methods for computing the inverse matrix». Ann. Math. Statist. 17 (3): 336–343. doi:10.1214/aoms/1177730946.
↑ ^4,0 ^4,1 Hager, William W. (1989). «Updating the inverse of a matrix». SIAM Review 31 (2): 221–239. doi:10.1137/1031049. MR 997457.
↑ Higham, Nicholas (2002). Accuracy and Stability of Numerical Algorithms (2nd έκδοση). SIAM. σελ. 258. ISBN 978-0-89871-521-7. MR 1927606.
↑ «MathOverflow discussion». MathOverflow.
↑ ^7,0 ^7,1 ^7,2 Henderson, H. V.; Searle, S. R. (1981). «On deriving the inverse of a sum of matrices». SIAM Review 23 (1): 53–60. doi:10.1137/1023004. http://ecommons.cornell.edu/bitstream/1813/32749/1/BU-647-M.pdf.
↑ Kurt S. Riedel, "A Sherman–Morrison–Woodbury Identity for Rank Augmenting Matrices with Application to Centering", SIAM Journal on Matrix Analysis and Applications, 13 (1992)659-662, doi:10.1137/0613040 preprint MR 1152773
↑ Bernstein, Dennis S. (2018). Scalar, Vector, and Matrix Mathematics: Theory, Facts, and Formulas (Revised and expanded έκδοση). Princeton: Princeton University Press. σελ. 638. ISBN 9780691151205.
↑ Schott, James R. (2017). Matrix analysis for statistics (Third έκδοση). Hoboken, New Jersey: John Wiley & Sons, Inc. σελ. 219. ISBN 9781119092483.

Atkinson, Kendall E. (1989), An Introduction to Numerical Analysis, John Wiley & Sons, ISBN 0-471-62489-6 .
Davis, Timothy A. (2006), Direct Methods for Sparse Linear Systems, Society for Industrial and Applied Mathematics, ISBN 978-0-898716-13-9 .
Feige, Uriel (2000), «Coping with the NP-Hardness of the Graph Bandwidth Problem», Algorithm Theory - SWAT 2000, Lecture Notes in Computer Science, 1851, doi:10.1007/3-540-44985-X_2 .
Golub, Gene H.; Van Loan, Charles F. (1996), Matrix Computations (3rd έκδοση), Baltimore: Johns Hopkins, ISBN 978-0-8018-5414-9 .
Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), «Section 2.4», Numerical Recipes: The Art of Scientific Computing (3rd έκδοση), New York: Cambridge University Press, ISBN 978-0-521-88068-8, http://apps.nrbook.com/empanel/index.html?pg=56 .

[1] Max A. Woodbury, Inverting modified matrices, Memorandum Rept. 42, Statistical Research Group, Princeton University, Princeton, NJ, 1950, 4pp MR 38136

[2] Max A. Woodbury, The Stability of Out-Input Matrices. Chicago, Ill., 1949. 5 pp. MR 32564

[guttman-3] Guttmann, Louis (1946). «Enlargement methods for computing the inverse matrix». Ann. Math. Statist. 17 (3): 336–343. doi:10.1214/aoms/1177730946.

[hager-4] 4,0 ^4,1 Hager, William W. (1989). «Updating the inverse of a matrix». SIAM Review 31 (2): 221–239. doi:10.1137/1031049. MR 997457.

[higham-5] Higham, Nicholas (2002). Accuracy and Stability of Numerical Algorithms (2nd έκδοση). SIAM. σελ. 258. ISBN 978-0-89871-521-7. MR 1927606.

[6] «MathOverflow discussion». MathOverflow.

[HS-7] 7,0 ^7,1 ^7,2 Henderson, H. V.; Searle, S. R. (1981). «On deriving the inverse of a sum of matrices». SIAM Review 23 (1): 53–60. doi:10.1137/1023004. http://ecommons.cornell.edu/bitstream/1813/32749/1/BU-647-M.pdf.

[8] Kurt S. Riedel, "A Sherman–Morrison–Woodbury Identity for Rank Augmenting Matrices with Application to Centering", SIAM Journal on Matrix Analysis and Applications, 13 (1992)659-662, doi:10.1137/0613040 preprint MR 1152773

[9] Bernstein, Dennis S. (2018). Scalar, Vector, and Matrix Mathematics: Theory, Facts, and Formulas (Revised and expanded έκδοση). Princeton: Princeton University Press. σελ. 638. ISBN 9780691151205.

[10] Schott, James R. (2017). Matrix analysis for statistics (Third έκδοση). Hoboken, New Jersey: John Wiley & Sons, Inc. σελ. 219. ISBN 9781119092483.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]