Suppose A is a dense symmetric positive definite 1000x1000 matrix with κ(A)=100. Estimate roughly how many flops are required to solve `Ax = b to ten-digit accuracy by (a) Cholesky factorization, (b) Richardson iteration with the optimal parameter α and (c) CG
I believe for (A) it would just be $~(1/3)*m^3=(1/3)*1000^3$, but I'm not sure how to go about calculating the flop count for Richardson or CG
Since you didn't tell us where you are stuck, I can only give you a hint how to start.
For the Cholesky-Decomposition, under the assumption that you don't have any round-off errors, the result will the exact solution. To do the decomposition for a matrix $A∈ℝ^{n×n}$ you have to do $n$ square roots, $\frac{n(n-1)}{2}$ divisions, $\frac{n(n^2-1)}{6}$ multiplications and $\frac{n(n^2-1)}{6}$ additions. And then you also need to do a step of backwards and forwards solving.
So reducing this to $n^3$ is not fair since you can hide a lot in the $\mathcal{O(n^2)}$ term of $\frac{1}{3}n^3+\mathcal{O}(3)$.
The convergence rate of the CG-Method is given by:
$$\|x_k-x\|_A≤2\left(\frac{\sqrt{κ(A)}-1}{\sqrt{κ(A)}+1}\right)^k\|x_0-x\|_A.$$
.
For the Richardson-Iteration you need to look at the following error propagation: $$\|x_k-x\|=\|(I-ωA)(x_{k-1}-x)\| ≤ \|(I-ωA)\|\|(x_{k-1}-x)\|≤\|(I-ωA)\|^k\|(x_{0}-x)\|$$ So the interesting value is the spectral radius of $G_ω:=I-ωA$. The parameter ω is chosen such that this value is optimal. With a bit of work one can get $$\min_{ω}ρ(G_ω) = 1-\frac{2}{κ(A)+1} $$