Why the $C$ constant is defined like this in the Theorem:
There is the proof of Theorem provided by the book, i underlined what i do not understood.
The text where i found this Theorem was Numerical Linear Algebra , Trefethen and Bau.
Asked
Active
Viewed 385 times
0
-
I'm not sure the image of the Theorem has enough context to be able to explain why the choice shown for $C$ makes the result true. It seems to refer to an iteration defined above in the text. Perhaps you should include a citation for the text where you found this. – hardmath Jun 09 '17 at 21:06
-
I forgot to post in the image but Assumption (28.4) in the proof of the Theorem is about real symmetrical matrices and says that the first n+1 eigenvalues of A in the sense of norm ordering are different. – Joan Guastalla Jun 09 '17 at 21:35
-
The title contains an important clue to the meaning of your Question as it concerns the "power method". If you understand the algorithm you are asking about, you should include its explanation in the body of your Question. Try to make the problem formulation as self-contained as possible. – hardmath Jun 09 '17 at 21:52
1 Answers
0
Consider the ordinary power method. It looks like $x_k=\frac{A^k x_0}{\| A^k x_0 \|}=\frac{\sum_{i=1}^n \lambda_i^k c_i(x_0) v_i}{\left \| \sum_{i=1}^n \lambda_i^n c_i(x_0) v_i \right \|}$, where $c_i$ are scalars. If $c_1$ and $c_2$ are both nonzero, then we divide top and bottom by $\lambda_1^n c_1(x_0)$ to reveal the normalized version of $v_1 + \sum_{i=2}^n (\lambda_i/\lambda_1)^k (c_i/c_1) v_i$. This is $O(|\lambda_2/\lambda_1|^k)$ (why?).
Suppose instead we had $n-1$ vectors $x_0^{(j)}$ with $c_i(x_0^{(j)})=0$ for all $i<j$, $c_j(x_0^{(j)}) \neq 0,c_{j+1}(x_0^{(j)}) \neq 0$. Suppose we ran power iteration on each of those. Then the iteration of $x_0^{(j)}$ will give us $v_j$, and by an argument just like the one above, its error is $O(|\lambda_{j+1}/\lambda_j|^k)$.
This is not exactly how simultaneous iteration actually works: if it were then we would be able to immediately read off the eigenvectors from the initial conditions, in which case there would be no need to do any iteration. But the orthogonalization procedure used in simultaneous iteration essentially aims to make this be the situation as $k \to \infty$. In effect, once $x_k^{(1)}$ has nearly converged, $x_k^{(2)}$, being orthogonal to $x_k^{(1)}$, can't have much of a component in the direction of $v_1$, so its deviation from $v_2$ must arise primarily from the contribution of the component in the direction of $v_3$, etc.
Ian
- 101,645
-
For the situation described in the second paragraph i can see that the order of convergence to all eigenvectors will be the C that i had asked, but i did not understand how this idea was applied in Simultaneous Power Iteration. – Joan Guastalla Jun 09 '17 at 23:24
-
1@JoanGuastalla You really just need to go through the details. The idea of the calculation is no different than what I said in the third paragraph: if all eigenvalues have distinct moduli, power iteration with $x_0^{(1)}$ is converging to $v_1$, and $x_k^{(2)}$ is kept orthogonal to $x_k^{(1)}$ then $x_k^{(2)}$ must be converging to some other eigenvector (generically it will be $v_2$). – Ian Jun 09 '17 at 23:39