up

Contents

1 Project Proposal

1.1 Statement of problem

Suppose we have solved \(Ax=b\) and we have determined \(A^{-1}\) during this process. Now a small change is made to \(A\) and we wish to find the new solution \(\hat x\) for \(\hat A x=b\) without having to solve this equation from the start. i.e. without having to find \(\hat A^{-1}\).

A small change in \(A\) can be a one of few elements changed, or one row changed or one column changed.

Using the Sherman-Morrison method we can find \(x\) in \(\hat A x=b\) from the previous knowledge of \(A^{-1}\) without having to calculate \(\hat A^{-1}\) again.

This allows us a saving of computational time since the cost of using Sherman-Morrison method is \(O\left ( n^{2}\right ) \)as opposed to solving \(\hat Ax=b\) directly by calculating \(\hat A^{-1}\) which is \(O\left ( n^{3}\right ) .\)

1.2 Method of solution

1. Input the \(A\) and \(b\) matrices from the user in interactive manner
2. Solve \(Ax=b\) finding \(x\) and \(A^{-1}\)
3. Save \(A^{-1}\)in memory for use later.
4. input the modified \(\hat A\)
5. let \(A-\hat A=-B\), calculate \(B\)
6. let \(B=uw\), find \(2\) such matrices \(u,w\) such that their product is \(B \)
7. let \(v^{T}=w\), this means that we can write \(A=\hat A-uv^{T}\)
8. Solve \(Ay=u\) finding \(y=A^{-1}u\) (\(A^{-1}\)is already known from step 2)
9. Solve \(A^{T}z=v\) finding \(z^{T}=v^{T}A^{-1}\)(\(A^{-1}\)is already known from step 2)
10. find \(\alpha =\frac 1{1-v^{T}y}\)
11. find \(\beta =z^{T}b\)
12. finally find \(\hat x=x+\alpha \beta y\)
13. go to step 4 if the user has more changes in \(A\) to solve for.