Timeline for Shifted QR algorithm—why does the shift help?
Current License: CC BY-SA 4.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 16, 2022 at 18:43 | comment | added | LSpice | You refer to "Answer 3", but the order of answers can change over time (depending on which ordering you use). I guessed which answer you meant, based on its use of inverse power iteration—namely, @DarshRanjan's. I hope that was correct. | |
| Mar 16, 2022 at 18:42 | history | edited | LSpice | CC BY-SA 4.0 |
Link while this is on the front page
|
| Jun 7, 2011 at 17:29 | comment | added | Tongru Huo | Why the shift helps can be explained by considering the QR of $H-rI=QR$. Since H is unreduced Hessenberg, it's first $n-1$ columns are linearly independent for any $r$. But if $r=\lambda_1$, $H-rI$ is singular. Then $r_{nn}=0$ and the last row of $R$ is zero. Then the last row of $H'+rI=RQ$ is zero except $nn$ component is $r$. So $r=\lambda_1$ or close to $\lambda_1$ will make $H'+rI$ $n-1,n$ component zero or closer to zero. This explains why the shift help. But this explanation doesn't fit well with the power iteration, where the component of $x'=(A-rI)x$ in $v_1$ actually decreases. | |
| Jun 7, 2011 at 17:02 | history | answered | Tongru Huo | CC BY-SA 3.0 |