נוסחת וודברי

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

ניסוח הנוסחה

יהיו:

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

אז:

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

בדיקת נכונות

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

$\begin{array}{cc}(A+UCV)[A^{-1}-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}$

סיבוכיות

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

קישורים חיצוניים

• תבנית:MathWorld