נוסחת וודברי

באלגברה לינארית שבמתמטיקה, נוסחת וודרבי (או נוסחת וודרבי להיפוך מטריצות) היא נוסחה לחישוב ההופכי של מטריצה אחרי שינוי מדרגה k. הנוסחה נקראת על שם מקס וודרבי, אשר פרסם את התוצאה ב-1950. גרסה לנוסחה זו עבור שינוי מדרגה 1 נקראת נוסחת שרמן-מוריסון.

ניסוח הנוסחה

יהיו:

• A מטריצה הפיכה בגודל $n\times n$
• C מטריצה הפיכה בגודל $k\times k$
• U,V מטריצות בגודל $k\times n$ ו $n\times k$ בהתאמה.

אז:

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

בדיקת נכונות

ניתן לבדוק בקלות את נכונות הנוסחא, על ידי חישוב הכפל:

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

סיבוכיות

בהינתן חישב מוקדם של ההופכי של A, סיבוכיות החישוב של $\left(A+UCV\right)^{-1}$ היא ${\mathcal {O}}\left(n^{2}k+k^{3}\right)$ במקום ${\mathcal {O}}\left(n^{3}\right)$ בחישוב נאיבי.