- #1
azdang
- 84
- 0
Homework Statement
Let A be a nxn real symmetric positive definite matrix and x not equal to 0 a real nx1 vector. Show how to computre xTA-1x in n3/3 + O(n2) arithmetic operations.
Homework Equations
The Attempt at a Solution
Some things I think I do know:
If A is real spd, so is A-1.
Therefore, A-1=LLT where L is a lower triangular matrix with positive diagonal elements.
I also know in class it was stated that solving Ax = b by Cholesky Factorization requires n3/3 + O(n2) arithmetic operations.
Also, I might be wrong, but I think we are looking for there to be (n-1)2 + O(n) operations, then you would say that is equivalent to [tex]\sum[/tex]j=1n-1j2 and then [tex]\sum[/tex]j=1kj2=k(k+1)(2k+1)/6 = 2k3/6 + O(n2) = k3/3 + O(k2).
I'm not sure how to piece these all together or if I even need this information, and I'm missing something else.
Does anyone have any ideas? Thank you so much.
Last edited: