Construct $A =Q\Lambda Q^T$. $Q$ is found by applying $QR$ factorization to $B=$randn($n$), and $\Lambda$ is defined to be
\begin{align*}
\Lambda = \mathrm{diag}(\lambda_1,\lambda_2,\ldots,\lambda_n),
\end{align*}
where $(\lambda_i)_{i=1}^n$ is a colloction of iid random variables and $\lambda_1$ is uniform on $[-1,1]$. It's clear that $\|A\|<1$. Let $\vec b=$rand($n,1$), which means its entries are uniformly distributed random variables on $[0,1]$.
When solving $(I – A)\vec x = \vec b$, I apply the Neumann series iteration as follows:
\begin{align*}
\vec x_0 &= \vec 0,\\
\vec x_j &= A\vec x_{j-1} + b, \quad j = 1,2,3\ldots.
\end{align*}
There are two ways to define the number of iterations.
First, define the number of iterations $\hat k_\epsilon(A)$ as
\begin{align*}
\hat k_\epsilon(A) = \min \left\{ k : \frac{\|A\|^k}{1 – \|A\|} \sqrt{n}< \epsilon\right\}.
\end{align*}
Also, define the number of iterations $\tilde k_\epsilon(A,\vec b, \vec x_0)$ as
\begin{align*}
\tilde k_\epsilon(A,\vec b, \vec x_0) &= \min \left\{ k : \|\vec x – \vec x_k\| < \epsilon\right\}.
\end{align*}
When $\vec b \sim \text{rand(n)}$, and $\vec x_0 = 0$, I want to show that
\begin{align*}
\hat k_\epsilon(A) \geq \tilde k_\epsilon(A,\vec b, \vec x_0).
\end{align*}
Besides, I want to find an expression for $\hat k_\epsilon(A)$ in terms of the eigenvalues of $A$? Since $\hat k_\epsilon(A)$ is affected only by $A$ and $\epsilon$, can I just write $\frac{\|A\|^k}{1 – \|A\|} \sqrt{n}= \epsilon$ and move everything except $k$ to the RHS and estimate the value of $k$? Is this the desired expression of $\hat k_\epsilon(A)$?
Best Answer
Let $\rho=\sup_i(|\lambda_i|)$. Then $||A||_2=\rho$. If $\rho<1$, then the sequence $(x_i)$ converges and you easily can calculate $k$.
Beware, if, for example $n$ is great and $\rho\approx 1-1/n$, then the convergence is very slow and the cost of the calculation of its limit becomes greater than the cost of the calculation of $(I-A)^{-1}$.
If you uniformly choose the $(\lambda_i)$ in $[-1,1]$, then you will be very often in the above case!!