वुडबरी आव्यूह समरूपता: Difference between revisions

Latest revision as of 15:43, 4 September 2023

गणित में (विशेष रूप से रैखिक बीजगणित), वुडबरी आव्यूह समरूपता, जिसका नाम मैक्स ए. वुडबरी के नाम पर रखा गया है,^[1]^[2] जो यह कहते है कि कुछ आव्यूह (गणित) के पद-k सुधार के व्युत्क्रम की गणना मूल आव्यूह के व्युत्क्रम में पद-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}X$ और $V=CY$ है।

इस समरूपता को ही दो सरल समरूपताों के संयोजन के रूप में देखा जा सकता है। इस प्रकार से हम पहली समरूपता

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

दूसरी समरूपता तथाकथित पुश-थ्रू समरूपता^[7]

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

है जिसे हम दाईं ओर $(I+VU)^{-1}$ और बाईं ओर $(I+UV)^{-1}$

से गुणा करने के बाद

U(I+VU)=(I+UV)U

से प्राप्त करते हैं।

सभी को एक साथ रखने पर,

\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}(B^{-1}+A^{-1})^{-1}A^{-1}\\&={A}^{-1}-{A}^{-1}\left({A}{B}^{-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$ एकल होने पर भी मान्य है, और इसमें एक पुनरावर्ती संरचना है जो $A^{-1}B$ का वर्णक्रमीय त्रिज्या एक से कम होने पर

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

उत्पन्न करती है। अर्थात्, यदि उपरोक्त योग अभिसरित होता है तो यह $(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 पदों को (B⁻¹)⁻¹ से प्रतिस्थापित किया जा सकता है, जिसके परिणामस्वरूप मूल वुडबरी समरूपता प्राप्त होती है।

इस प्रकार से जब B एकल हो और संभवतः गैर-वर्ग भी हो, तो इसके लिए भिन्नता:^[7]

(A+UBV)^{-1}=A^{-1}-A^{-1}U(I+BVA^{-1}U)^{-1}BVA^{-1}.

अतः कुछ स्थितियों के लिए सूत्र भी स्थित हैं जिनमें A एकल है।^[8]

धनात्मक अर्धनिश्चित आव्यूह के साथ छद्म व्युत्क्रम

इस प्रकार से सामान्यतः वुडबरी की समरूपता मान्य नहीं है यदि या अधिक व्युत्क्रमों को मूर-पेनरोज़ व्युत्क्रम या (मूर-पेनरोज़) छद्म व्युत्क्रम द्वारा प्रतिस्थापित किया जाता है। यद्यपि, यदि $A$ और $C$ धनात्मक अर्धनिश्चित आव्यूह हैं, और $V=U^{\mathrm {H} }$ (इसका तात्पर्य यह है कि $A+UCV$ स्वयं धनात्मक अर्धनिश्चित है), तो निम्न सूत्र सामान्यीकरण प्रदान करता है:^[9]^[10]

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

जहाँ $A+UCU^{\mathrm {H} }$ को $XX^{\mathrm {H} }+YY^{\mathrm {H} }$ के रूप में लिखा जा सकता है क्योंकि कोई भी धनात्मक अर्धनिश्चित आव्यूह कुछ $M$ के लिए $MM^{\mathrm {H} }$ के बराबर है।

व्युत्पत्तियाँ

प्रत्यक्ष प्रमाण

इस प्रकार से सूत्र को यह जांच कर सिद्ध किया जा सकता है कि वुडबरी समरूपता के दाईं ओर $(A+UCV)$ गुना इसके कथित व्युत्क्रम से समरूपता आव्यूह मिलता है:

\begin{aligned} (A + U C V) [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}} + {U C V A^{- 1} - U C V A^{- 1} U {(C^{- 1} + V A^{- 1} U)}^{- 1} V A^{- 1}} \\ = & {I + U C V A^{- 1}} - {U {(C^{- 1} + V A^{- 1} U)}^{- 1} V A^{- 1} + U C V A^{- 1} U {(C^{- 1} + V A^{- 1} U)}^{- 1} V A^{- 1}} \\ = & I + U C V A^{- 1} - (U + U C V A^{} \end{aligned}

वैकल्पिक प्रमाण

style="background: #F0F2F5; font-size:87%; padding:0.2em 0.3em; text-align:center; " |

बीजगणितीय प्रमाण

पहले इन उपयोगी समरूपताओं पर विचार करें,

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

अब,

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

style="background: #F0F2F5; font-size:87%; padding:0.2em 0.3em; text-align:center; " |

ब्लॉकवार उन्मूलन के माध्यम से व्युत्पत्ति

वुडबरी आव्यूह समरूपता प्राप्त करना निम्नलिखित ब्लॉक आव्यूह व्युत्क्रम समस्या

{\begin{bmatrix}A&U\\V&-C^{-1}\end{bmatrix}}{\begin{bmatrix}X\\Y\end{bmatrix}}={\begin{bmatrix}I\\0\end{bmatrix}}

को हल करके सरलता से किया जाता है। विस्तार करते हुए, हम देख सकते हैं कि उपरोक्त

{\begin{cases}AX+UY=I\\VX-C^{-1}Y=0\end{cases}}

तक कम हो जाता है जो $(A+UCV)X=I$ के बराबर है। पहले समीकरण को हटाकर, हम उस $X=A^{-1}(I-UY)$ को पाते हैं, जिसे $VA^{-1}(I-UY)=C^{-1}Y$ खोजने के लिए दूसरे में प्रतिस्थापित किया जा सकता है। विस्तार और पुनर्व्यवस्थित करते हुए, हमारे निकट $VA^{-1}=\left(C^{-1}+VA^{-1}U\right)Y$ , या $\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}=Y$ है। अंत में, हम अपने $AX+UY=I$ में स्थानापन्न करते हैं, और हमारे निकट $AX+U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}=I$ होता है। इस प्रकार,

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

हमने वुडबरी आव्यूह समरूपता प्राप्त की है।

style="background: #F0F2F5; font-size:87%; padding:0.2em 0.3em; text-align:center; " |

एलडीयू अपघटन से व्युत्पत्ति

हम आव्यूह

{\begin{bmatrix}A&U\\V&C\end{bmatrix}}

से प्रारम्भ करते हैं A के अंतर्गत प्रविष्टि को हटाने पर (यह देखते हुए कि A व्युत्क्रम है) हमें

{\begin{bmatrix}I&0\\-VA^{-1}&I\end{bmatrix}}{\begin{bmatrix}A&U\\V&C\end{bmatrix}}={\begin{bmatrix}A&U\\0&C-VA^{-1}U\end{bmatrix}}

मिलता है

इसी प्रकार, C के ऊपर की प्रविष्टि को हटाने से

{\begin{bmatrix}A&U\\V&C\end{bmatrix}}{\begin{bmatrix}I&-A^{-1}U\\0&I\end{bmatrix}}={\begin{bmatrix}A&0\\V&C-VA^{-1}U\end{bmatrix}}

मिलता है

अब उपरोक्त दोनों को मिलाकर हमें

{\begin{bmatrix}I&0\\-VA^{-1}&I\end{bmatrix}}{\begin{bmatrix}A&U\\V&C\end{bmatrix}}{\begin{bmatrix}I&-A^{-1}U\\0&I\end{bmatrix}}={\begin{bmatrix}A&0\\0&C-VA^{-1}U\end{bmatrix}}

प्राप्त होता है

दाईं ओर जाने पर

{\begin{bmatrix}A&U\\V&C\end{bmatrix}}={\begin{bmatrix}I&0\\VA^{-1}&I\end{bmatrix}}{\begin{bmatrix}A&0\\0&C-VA^{-1}U\end{bmatrix}}{\begin{bmatrix}I&A^{-1}U\\0&I\end{bmatrix}}

मिलता है जो ब्लॉक आव्यूह का ऊपरी त्रिकोणीय, विकर्ण और निचले त्रिकोणीय आव्यूह में एलडीयू अपघटन है।

अब दोनों पक्षों को व्युत्क्रमित करने पर

{\displaystyle {\begin{aligned}{\begin{bmatrix}A&U\\V&C\end{bmatrix}}^{-1}&={\begin{bmatrix}I&A^{-1}U\\0&I\end{bmatrix}}^{-1}{\begin{bmatrix}A&0\\0&C-VA^{-1}U\end{bmatrix}}^{-1}{\begin{bmatrix}I&0\\VA^{-1}&I\end{bmatrix}}^{-1}\\[8pt]&={\begin{bmatrix}I&-A^{-1}U\\0&I\end{bmatrix}}{\begin{bmatrix}A^{-1}&0\\0&\left(C-VA^{-1}U\right)^{-1}\end{bmatrix}}{\begin{bmatrix}I&0\\-

प्राप्त होता है

हम इसे समान रूप से दूसरी विधि से भी कर सकते थे (परंतु C व्युत्क्रम हो) अर्थात

{\begin{bmatrix}A&U\\V&C\end{bmatrix}}={\begin{bmatrix}I&UC^{-1}\\0&I\end{bmatrix}}{\begin{bmatrix}A-UC^{-1}V&0\\0&C\end{bmatrix}}{\begin{bmatrix}I&0\\C^{-1}V&I\end{bmatrix}}

अब फिर से दोनों पक्षों को व्युत्क्रमित करके,

{\displaystyle {\begin{aligned}{\begin{bmatrix}A&U\\V&C\end{bmatrix}}^{-1}&={\begin{bmatrix}I&0\\C^{-1}V&I\end{bmatrix}}^{-1}{\begin{bmatrix}A-UC^{-1}V&0\\0&C\end{bmatrix}}^{-1}{\begin{bmatrix}I&UC^{-1}\\0&I\end{bmatrix}}^{-1}\\[8pt]&={\begin{bmatrix}I&0\\-C^{-1}V&I\end{bmatrix}}{\begin{bmatrix}\left(A-UC^{-1}V\right)^{-1}&0\\0&C^{-1}\end{bmatrix}}{\begin{bmatrix}I&-UC^

अब उपरोक्त (1) और (2) के आरएचएस के अवयवों (1, 1) की तुलना करने से वुडबरी सूत्र

\left(A-UC^{-1}V\right)^{-1}=A^{-1}+A^{-1}U\left(C-VA^{-1}U\right)^{-1}VA^{-1}

मिलता है।

अनुप्रयोग

अतः यह समरूपता कुछ संख्यात्मक गणनाओं में उपयोगी है जहां A⁻¹ की गणना पहले ही की जा चुकी है और (A + UCV)⁻¹ की गणना करना वांछित है। A का व्युत्क्रम उपलब्ध होने पर, पहचान के दाईं ओर का उपयोग करके परिणाम प्राप्त करने के लिए मात्र C^{−1 + VA⁻¹U का व्युत्क्रम ज्ञात करना आवश्यक है। यदि C की विमा A से बहुत छोटी है, तो यह A + UCV को प्रत्यक्षतः व्युत्क्रमित करने की तुलना में अधिक कुशल है। इस प्रकार से सामान्य स्थित A के निम्न-पद अद्यतन A + UCV (जहां U में मात्र कुछ स्तम्भ हैं और V में मात्र कुछ पंक्तियां हैं) का व्युत्क्रम ढूंढना है, या आव्यूह A + B के व्युत्क्रम का अनुमान लगाना है जहां आव्यूह B को निम्न-पद आव्यूह UCV द्वारा अनुमानित किया जा सकता है, उदाहरण के लिए एकल मान अपघटन का उपयोग करना।}

इसे लागू किया जाता है, उदाहरण के लिए, कलमन निस्पंदन और पुनरावर्ती न्यूनतम वर्ग विधियों में, पैरामीट्रिक हल को बदलने के लिए, स्थिति समीकरण आधारित हल के साथ, अवस्था सदिश आकार आव्यूह के व्युत्क्रम की आवश्यकता होती है। इस प्रकार से कलमन निस्पंदन की स्थिति में इस आव्यूह में अवलोकनों की सदिश विमा होती है, अर्थात, समय में मात्र नवीन अवलोकन संसाधित होने की स्थिति में 1 जितना छोटा होता है। अतः यह निस्पंदन की प्रायः वास्तविक समय गणनाओं को महत्वपूर्ण रूप से गति देता है।

इस प्रकार से उस स्थिति में जब C समरूपता आव्यूह I है, आव्यूह $I+VA^{-1}U$ को संख्यात्मक रैखिक बीजगणित और संख्यात्मक आंशिक अंतर समीकरणों में संधारित्र आव्यूह के रूप में जाना जाता है।^[4]

यह भी देखें

शर्मन-मॉरिसन सूत्र
शूर पूरक
आव्यूह निर्धारक लेम्मा, निर्धारक के लिए पद-k अद्यतन के लिए सूत्र
व्युत्क्रम आव्यूह
मूर-पेनरोज़ छद्मइव्युत्क्रम छद्मव्युत्क्रम को अद्यतन कर रहा है

↑ 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. MR32564
↑ 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. JSTOR 2030425. MR 0997457.
↑ Higham, Nicholas (2002). संख्यात्मक एल्गोरिदम की सटीकता और स्थिरता (2nd ed.). SIAM. p. 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). "आव्यूहों के योग का व्युत्क्रम निकालने पर" (PDF). SIAM Review. 23 (1): 53–60. doi:10.1137/1023004. hdl:1813/32749. JSTOR 2029838.
↑ 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 MR1152773
↑ Bernstein, Dennis S. (2018). Scalar, Vector, and Matrix Mathematics: Theory, Facts, and Formulas (Revised and expanded ed.). Princeton: Princeton University Press. p. 638. ISBN 9780691151205.
↑ Schott, James R. (2017). सांख्यिकी के लिए मैट्रिक्स विश्लेषण (Third ed.). Hoboken, New Jersey: John Wiley & Sons, Inc. p. 219. ISBN 9781119092483.

Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Section 2.7.3. Woodbury Formula", Numerical Recipes: The Art of Scientific Computing (3rd ed.), New York: Cambridge University Press, ISBN 978-0-521-88068-8

बाहरी संबंध

[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. MR32564

[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. JSTOR 2030425. MR 0997457.

[higham-5] Higham, Nicholas (2002). संख्यात्मक एल्गोरिदम की सटीकता और स्थिरता (2nd ed.). SIAM. p. 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). "आव्यूहों के योग का व्युत्क्रम निकालने पर" (PDF). SIAM Review. 23 (1): 53–60. doi:10.1137/1023004. hdl:1813/32749. JSTOR 2029838.

[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 MR1152773

[9] Bernstein, Dennis S. (2018). Scalar, Vector, and Matrix Mathematics: Theory, Facts, and Formulas (Revised and expanded ed.). Princeton: Princeton University Press. p. 638. ISBN 9780691151205.

[10] Schott, James R. (2017). सांख्यिकी के लिए मैट्रिक्स विश्लेषण (Third ed.). Hoboken, New Jersey: John Wiley & Sons, Inc. p. 219. ISBN 9781119092483.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

Anonymous

Search

वुडबरी आव्यूह समरूपता: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 15:43, 4 September 2023

Contents