Apply Sherman-Morrison formula in O(n^2). To learn this formula, please look this: https://en.wikipedia.org/wiki/Sherman%E2%80%93Morrison_formula This method returns (A + uv^T)^(-1) where A^(-1) is self. Returns None if it's
(self, u: Matrix, v: Matrix)
| 201 | return result |
| 202 | |
| 203 | def sherman_morrison(self, u: Matrix, v: Matrix) -> Any: |
| 204 | """ |
| 205 | <method Matrix.sherman_morrison> |
| 206 | Apply Sherman-Morrison formula in O(n^2). |
| 207 | To learn this formula, please look this: |
| 208 | https://en.wikipedia.org/wiki/Sherman%E2%80%93Morrison_formula |
| 209 | This method returns (A + uv^T)^(-1) where A^(-1) is self. Returns None if it's |
| 210 | impossible to calculate. |
| 211 | Warning: This method doesn't check if self is invertible. |
| 212 | Make sure self is invertible before execute this method. |
| 213 | Example: |
| 214 | >>> ainv = Matrix(3, 3, 0) |
| 215 | >>> for i in range(3): ainv[i,i] = 1 |
| 216 | ... |
| 217 | >>> u = Matrix(3, 1, 0) |
| 218 | >>> u[0,0], u[1,0], u[2,0] = 1, 2, -3 |
| 219 | >>> v = Matrix(3, 1, 0) |
| 220 | >>> v[0,0], v[1,0], v[2,0] = 4, -2, 5 |
| 221 | >>> ainv.sherman_morrison(u, v) |
| 222 | Matrix consist of 3 rows and 3 columns |
| 223 | [ 1.2857142857142856, -0.14285714285714285, 0.3571428571428571] |
| 224 | [ 0.5714285714285714, 0.7142857142857143, 0.7142857142857142] |
| 225 | [ -0.8571428571428571, 0.42857142857142855, -0.0714285714285714] |
| 226 | """ |
| 227 | |
| 228 | # Size validation |
| 229 | assert isinstance(u, Matrix) |
| 230 | assert isinstance(v, Matrix) |
| 231 | assert self.row == self.column == u.row == v.row # u, v should be column vector |
| 232 | assert u.column == v.column == 1 # u, v should be column vector |
| 233 | |
| 234 | # Calculate |
| 235 | v_t = v.transpose() |
| 236 | numerator_factor = (v_t * self * u)[0, 0] + 1 |
| 237 | if numerator_factor == 0: |
| 238 | return None # It's not invertible |
| 239 | return self - ((self * u) * (v_t * self) * (1.0 / numerator_factor)) |
| 240 | |
| 241 | |
| 242 | # Testing |