QR Algorithm

[JoeSpencer1]

Right now my QR algorithm is unable to create an R matrix that is totally upper triangular. It works pretty well for matrices with all real eigenvalues, but then for the case when a matrix has complex or imaginary eigenvalues it is unable to recognize that.

[JoeSpencer1]

As a stopgap solution I am creating the R matrix incorrectly. It is unable to find columns that are linearly independent yet, I think.

[JoeSpencer1]

Complex eigenvalues require the double QR algorithm.

[JoeSpencer1]

You'll have to use double steps. Follow these instructions on roughly page 15: https://people.inf.ethz.ch/arbenz/ewp/Lnotes/2010/chapter3.pdf

[JoeSpencer1]

Once you have an upper hessenberg matrix (zeros below the diagonal), use this process. It's on page 66 (16). https://people.inf.ethz.ch/arbenz/ewp/Lnotes/2010/chapter3.pdf

[JoeSpencer1]

[JoeSpencer1]

[JoeSpencer1]

Page 58. https://people.inf.ethz.ch/arbenz/ewp/Lnotes/2010/chapter3.pdf

[JoeSpencer1]

https://www.youtube.com/watch?v=RSm_Mqi0aSA

[JoeSpencer1]

https://www.youtube.com/watch?v=w6clp9UqRRE

[JoeSpencer1]

http://math.utep.edu/faculty/xzeng/2017spring_math5330/2017spring_math5330/MATH_5330_Computational_Methods_of_Linear_Algebra_files/ln14.pdf Page 7-8

[JoeSpencer1]

I think the link above explains it best.

[JoeSpencer1]

Ok, you need to do it in Hessenberg form.

[JoeSpencer1]

Page 413 of textbook.

[JoeSpencer1]

Page 413-Chapter 18.

[JoeSpencer1]

You need to put matrices in upper Hessenberg form before QR-ing: Page 396-Chapter 18.

[JoeSpencer1]

These are called Householder matrices, to get the row and the row below it.

[JoeSpencer1]

https://www.youtube.com/watch?v=OqgYYqy0M4w Householder matrix

[JoeSpencer1]

This video walks through Householder matrices better. https://www.youtube.com/watch?v=s_rhzm6uW_E

[JoeSpencer1]

Or just the wikipedia article. https://en.wikipedia.org/wiki/Householder_transformation

[JoeSpencer1]

Now it simplifies to a Householder matrix.

[JoeSpencer1]

This video shows how to take the eigenvalues from a Schur matrix. You also need Householder form. https://www.youtube.com/watch?v=voKfs7M9Nr0

[JoeSpencer1]

[JoeSpencer1]

[JoeSpencer1]

https://pi.math.cornell.edu/~web6140/TopTenAlgorithms/QRalgorithm.html

[JoeSpencer1]

[JoeSpencer1]

Whoops, I think those three actually only work for symmetric matrices. Instead you're just supposed to use the nn entry as the shift. https://web.stanford.edu/class/cme335/lecture5

[JoeSpencer1]

I have it mostly working! Now there's just a segmentation fault that needs to be resolved.

[JoeSpencer1]

I think I could resolve the seg fault (and create a few more) by using pointers instead of a vector.

[JoeSpencer1]

Ok, breaking down the matrix into QR still works.

[JoeSpencer1]

I think the part where I subtract an identity matrix multiplied by the imaginary portion got deleted.

[JoeSpencer1]

At this point it can converge for complex eignevalues too. It seems like the order is reversed, though, and the pointers still do not work.

[JoeSpencer1]

To keep the QR algorithm from going off track, make it not move to the next step until each of the bottom entries of the diagonal are there too. If it’s a complex eigenvalue, instead check the 2 entries of the diagonal that goes up to the right.

[JoeSpencer1]

To receive the finished qr matrices, add vectors of vectors to the vector in the constructor. This way they won’t require more space.

[JoeSpencer1]

Halleluja! It lives!

[JoeSpencer1]

Now it can return a value for the QR algorithm, but it is still not accurate. I think I messed up the threshold for what's an accurate value to return.

[JoeSpencer1]

I need to determine a way to make the matrices in the QR algorithm stay true to the previous matrices within a tighter tolerance.

[JoeSpencer1]

Eureka! Now it skip straight to the end if the eigenvalues are all real instead of doing the risky cycling through other rows.

[JoeSpencer1]

Hmm I actually just broke it again...

[JoeSpencer1]

I've fixed it again. You might have to fiddle with the tolerances in the future.

[JoeSpencer1]

I should make it so each term in this algorithm converges to within the accuracy of itself. I was measuring convergence with a number, but I think I should use a boolean operator instead. Also, the way the QR algorithm is currently set up it doesn't return any eigenvectors.

[JoeSpencer1]

Ok, now it's within 0.00001 for the real portion and 0.00002 for the imaginary portion, which I'm saying is close enought.