Editing Inverse iteration (section)

=== Calculate inverse matrix or solve system of linear equations ===

We can rewrite the formula in the following way:
<math display="block"> (A - \mu I) b_{k+1} = \frac{b_k}{C_k}, </math>

emphasizing that to find the next approximation  <math> b_{k+1} </math> we may solve a system of linear equations. 
There are two options: one may choose an algorithm that solves a linear system, or one may calculate the inverse <math>(A - \mu I)^{-1}</math> and then apply it to the vector.
Both options have complexity ''O''(''n''<sup>3</sup>), the exact number depends on the chosen method.

The choice depends also on the number of iterations. Naively, if at each iteration one solves a linear system, the complexity will be ''k''&thinsp;''O''(''n''<sup>3</sup>), where ''k'' is number of iterations; similarly, calculating the inverse matrix and applying it at each iteration is of complexity ''k''&thinsp;''O''(''n''<sup>3</sup>).
Note, however, that if the eigenvalue estimate <math>\mu</math> remains constant, then we may reduce the complexity to ''O''(''n''<sup>3</sup>) + ''k''&thinsp;''O''(''n''<sup>2</sup>) with either method.
Calculating the inverse matrix once, and storing it to apply at each iteration is of complexity ''O''(''n''<sup>3</sup>) + ''k''&thinsp;''O''(''n''<sup>2</sup>).
Storing an [[LU decomposition]] of <math>(A - \mu I)</math> and using [[Triangular matrix#Forward and back substitution|forward and back substitution]] to solve the system of equations at each iteration is also of complexity ''O''(''n''<sup>3</sup>) + ''k''&thinsp;''O''(''n''<sup>2</sup>).

Inverting the matrix will typically have a greater initial cost, but lower cost at each iteration. Conversely, solving systems of linear equations will typically have a lesser initial cost, but require more operations for each iteration.