هوية مصفوفة وودبري

في الرياضيات ، وتحديدًا في الجبر الخطي ، تنص متطابقة مصفوفة وودبري - نسبةً إلى ماكس أ. وودبري ^{[ 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}=IU\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}=IP(I+P)^{-1}.$ الهوية الثانية هي ما يسمى بهوية الدفع المباشر ^{[ 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}=IU\left(I+VU\right)^{-1}V.$ حيث تأتي المساواة الأولى والثانية من الهوية الأولى والثانية، على التوالي.

حالات خاصة

متى $V,U$ إذا كانت متجهات ، فإن المتطابقة تختزل إلى صيغة شيرمان-موريسون .

في حالة الكمية العددية ، تكون النسخة المختزلة ببساطة ${\frac {1}{1+uv}}=1-{\frac {uv}{1+vu}}.$

معكوس المجموع

إذا كانت 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 اللذين يحيطان بالكمية العكسية بين قوسين في الجانب الأيمن بـ ( 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}\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}}$

براهين بديلة

برهان جبري

لنبدأ بالنظر في هذه الهويات المفيدة، ${\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}}$

الاشتقاق عن طريق الحذف القطاعي

يمكن استنتاج متطابقة مصفوفة وودبري بسهولة عن طريق حل مسألة عكس مصفوفة الكتلة التالية ${\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}.

لقد استنتجنا هوية مصفوفة وودبري.

الاشتقاق من تحليل LDU

نبدأ بالمصفوفة ${\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}}$ وهو تحليل LDU لمصفوفة الكتلة إلى مصفوفات مثلثية علوية وقطرية ومثلثة سفلية.

وبقلب كلا الطرفين نحصل على ${\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\\-VA^{-1}&I\end{bmatrix}}\\[8pt]&={\begin{bmatrix}A^{-1}+A^{-1}U\left(C-VA^{-1}U\right)^{-1}VA^{-1}&-A^{-1}U\left(C-VA^{-1}U\right)^{-1}\\-\left(C-VA^{-1}U\right)^{-1}VA^{-1}&\left(C-VA^{-1}U\right)^{-1}\end{bmatrix}}\qquad \mathrm {(1)} \end{aligned}}$

كان بإمكاننا فعل ذلك بالطريقة الأخرى بنفس الكفاءة (بشرط أن تكون 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}}$

والآن، بعكس كلا الجانبين مرة أخرى، ${\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}\\0&I\end{bmatrix}}\\[8pt]&={\begin{bmatrix}\left(A-UC^{-1}V\right)^{-1}&-\left(A-UC^{-1}V\right)^{-1}UC^{-1}\\-C^{-1}V\left(A-UC^{-1}V\right)^{-1}&C^{-1}+C^{-1}V\left(A-UC^{-1}V\right)^{-1}UC^{-1}\end{bmatrix}}\qquad \mathrm {(2)} \end{aligned}}$

بمقارنة العنصرين (1، 1) من الطرف الأيمن للمعادلتين (1) و(2) أعلاه، نحصل على صيغة وودبري. $\left(A-UC^{-1}V\right)^{-1}=A^{-1}+A^{-1}U\left(C-VA^{-1}U\right)^{-1}VA^{-1}.$

التطبيقات

تُفيد هذه المتطابقة في بعض العمليات الحسابية العددية حيث تم حساب A ^{− 1} مسبقًا، والمطلوب حساب ( A + UCV ) ⁻^1. وبوجود معكوس A ، يكفي إيجاد معكوس C ^{− 1} + VA ^{− 1}U للحصول على النتيجة باستخدام الطرف الأيمن من المتطابقة. إذا كان بُعد C أصغر بكثير من بُعد A ، فإن هذه الطريقة أكثر كفاءة من إيجاد معكوس A + UCV مباشرةً. ومن الأمثلة الشائعة إيجاد معكوس تحديث منخفض الرتبة A + UCV للمصفوفة A (حيث U تحتوي على عدد قليل من الأعمدة و V على عدد قليل من الصفوف)، أو إيجاد تقريب لمعكوس المصفوفة A + B حيث يمكن تقريب المصفوفة B بمصفوفة منخفضة الرتبة UCV ، على سبيل المثال باستخدام تحليل القيم المفردة .

يُستخدم هذا الأسلوب، على سبيل المثال، في مرشح كالمان وطرق المربعات الصغرى المتكررة ، لاستبدال الحل البارامتري ، الذي يتطلب عكس مصفوفة بحجم متجه الحالة، بحل قائم على معادلات الشرط. في حالة مرشح كالمان، تكون أبعاد هذه المصفوفة مساوية لأبعاد متجه الملاحظات، أي أنها قد تصل إلى 1 في حالة معالجة ملاحظة جديدة واحدة فقط في كل مرة. وهذا يُسرّع بشكل ملحوظ حسابات المرشح التي غالبًا ما تتم في الوقت الفعلي.

في حالة كون C هي مصفوفة الوحدة I ، فإن المصفوفة $I+VA^{-1}U$ يُعرف في الجبر الخطي العددي والمعادلات التفاضلية الجزئية العددية باسم مصفوفة السعة . ^{[ 4 ]}

انظر أيضاً

صيغة شيرمان-موريسون
مكمل شور
مبرهنة محدد المصفوفة ، صيغة لتحديث رتبة k إلى محدد
المصفوفة القابلة للعكس
معكوس مور-بنروز الزائف § تحديث المعكوس الزائف

ملحوظات

↑ ماكس أ. وودبري، عكس المصفوفات المعدلة ، تقرير مذكرة رقم 42، مجموعة البحوث الإحصائية، جامعة برينستون، برينستون، نيوجيرسي، 1950، 4 صفحات MR 0038136
↑ ماكس أ. وودبري، استقرار مصفوفات الإدخال والإخراج . شيكاغو، إلينوي، 1949. 5 صفحات. MR 0032564
↑ غوتمان، لويس (1946). "طرق التوسيع لحساب المصفوفة العكسية" . حوليات الإحصاء الرياضي . 17 (3): 336-343 . doi : 10.1214/aoms/1177730946 .
1 2 هاجر، ويليام و . (1989). "تحديث معكوس المصفوفة". مجلة SIAM Review . 31 (2): 221-239 . doi : 10.1137/1031049 . JSTOR 2030425. MR 0997457 .
↑ هايام ، نيكولاس (2002). دقة واستقرار الخوارزميات العددية ( الطبعة الثانية). SIAM . ص 258. ISBN 978-0-89871-521-7. MR 1927606 .
↑ "مناقشة على موقع MathOverflow" . MathOverflow .
1 2 3 هندرسون، إتش في؛ سيرل، إس آر (1981). "حول اشتقاق معكوس مجموع المصفوفات" (ملف PDF) . مجلة SIAM Review . 23 (1): 53-60 . doi : 10.1137/1023004 . hdl : 1813/32749 . JSTOR 2029838 .
↑ كورت س. ريدل، "هوية شيرمان-موريسون-وودبري لمصفوفات زيادة الرتبة مع تطبيق على التمركز"، مجلة SIAM لتحليل المصفوفات وتطبيقاتها ، 13 (1992) 659-662، doi : 10.1137/0613040، نسخة ما قبل النشر MR 1152773
↑ بيرنشتاين، دينيس س. (2018). الرياضيات العددية والمتجهة والمصفوفية: النظرية والحقائق والصيغ (طبعة منقحة وموسعة ). برينستون: مطبعة جامعة برينستون. ص 638. ISBN 9780691151205.
↑ شوت، جيمس ر. (2017). تحليل المصفوفات للإحصاء ( الطبعة الثالثة). هوبوكين، نيو جيرسي: جون وايلي وأولاده، ص 219. ISBN 9781119092483.

بريس، دبليو إتش؛ تيوكولسكي، إس إيه؛ فيترلينغ، دبليو تي؛ فلانيري، بي بي (2007)، "القسم 2.7.3. صيغة وودبري" ، وصفات عددية: فن الحوسبة العلمية ( الطبعة الثالثة)، نيويورك: مطبعة جامعة كامبريدج، رقم ISBN 978-0-521-88068-8

روابط خارجية

[1] ماكس أ. وودبري، عكس المصفوفات المعدلة ، تقرير مذكرة رقم 42، مجموعة البحوث الإحصائية، جامعة برينستون، برينستون، نيوجيرسي، 1950، 4 صفحات MR 0038136

[2] ماكس أ. وودبري، استقرار مصفوفات الإدخال والإخراج . شيكاغو، إلينوي، 1949. 5 صفحات. MR 0032564

[guttman-3] غوتمان، لويس (1946). "طرق التوسيع لحساب المصفوفة العكسية" . حوليات الإحصاء الرياضي . 17 (3): 336-343 . doi : 10.1214/aoms/1177730946 .

[hager-4] 1 2 هاجر، ويليام و . (1989). "تحديث معكوس المصفوفة". مجلة SIAM Review . 31 (2): 221-239 . doi : 10.1137/1031049 . JSTOR 2030425. MR 0997457 .

[higham-5] هايام ، نيكولاس (2002). دقة واستقرار الخوارزميات العددية ( الطبعة الثانية). SIAM . ص 258. ISBN 978-0-89871-521-7. MR 1927606 .

[6] "مناقشة على موقع MathOverflow" . MathOverflow .

[HS-7] 1 2 3 هندرسون، إتش في؛ سيرل، إس آر (1981). "حول اشتقاق معكوس مجموع المصفوفات" (ملف PDF) . مجلة SIAM Review . 23 (1): 53-60 . doi : 10.1137/1023004 . hdl : 1813/32749 . JSTOR 2029838 .

[8] كورت س. ريدل، "هوية شيرمان-موريسون-وودبري لمصفوفات زيادة الرتبة مع تطبيق على التمركز"، مجلة SIAM لتحليل المصفوفات وتطبيقاتها ، 13 (1992) 659-662، doi : 10.1137/0613040، نسخة ما قبل النشر MR 1152773

[9] بيرنشتاين، دينيس س. (2018). الرياضيات العددية والمتجهة والمصفوفية: النظرية والحقائق والصيغ (طبعة منقحة وموسعة ). برينستون: مطبعة جامعة برينستون. ص 638. ISBN 9780691151205.

[10] شوت، جيمس ر. (2017). تحليل المصفوفات للإحصاء ( الطبعة الثالثة). هوبوكين، نيو جيرسي: جون وايلي وأولاده، ص 219. ISBN 9781119092483.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗