- #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 x

^{T}A

^{-1}x in n

^{3}/3 + O(n

^{2}) 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}=LL

^{T}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 n

^{3}/3 + O(n

^{2}) 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=1}

^{n-1}j

^{2}and then [tex]\sum[/tex]

_{j=1}

^{k}j

^{2}=k(k+1)(2k+1)/6 = 2k

^{3}/6 + O(n

^{2}) = k

^{3}/3 + O(k

^{2}).

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: