{"id":5056,"date":"2019-08-05T14:35:31","date_gmt":"2019-08-05T19:35:31","guid":{"rendered":"https:\/\/blogs.mathworks.com\/cleve\/?p=5056"},"modified":"2019-09-10T13:22:43","modified_gmt":"2019-09-10T18:22:43","slug":"the-qr-algorithm-computes-eigenvalues-and-singular-values","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/cleve\/2019\/08\/05\/the-qr-algorithm-computes-eigenvalues-and-singular-values\/","title":{"rendered":"The QR Algorithm Computes Eigenvalues and Singular Values"},"content":{"rendered":"<div class=\"content\">\r\n\r\nThe QR algorithm is one of the world's most successful algorithms. We can use animated gifs to illustrate three variants of the algorithm, one for computing the eigenvalues of a nonsymmetric matrix, one for a symmetric matrix, and one for the singular values of a rectangular matrix. In all three cases, the QR iteration itself is preceded by a reduction to a compact form. All transformations are orthogonal similarities using Givens and Householder transformations. These are numerically stable, preserve eigenvalues, and preserve any symmetry.\r\n\r\n<!--\/introduction-->\r\n<h3>Contents<\/h3>\r\n<div>\r\n<ul>\r\n \t<li><a href=\"#291005a0-96b4-4ee5-a0f7-eb31d276d2c1\">Nonsymmetric eigenvalues<\/a><\/li>\r\n \t<li><a href=\"#acf8ed63-275a-4135-92fb-fcd51965e887\">Symmetric eigenvalues<\/a><\/li>\r\n \t<li><a href=\"#f766aaf7-35fd-4813-a844-1df0dbcfc05d\">SVD<\/a><\/li>\r\n \t<li><a href=\"#fda5b238-8498-470d-a2df-247cd61d622c\">Software<\/a><\/li>\r\n<\/ul>\r\n<\/div>\r\nThe starting matrix for all three variants is based on flipping the <a href=\"https:\/\/blogs.mathworks.com\/cleve\/2014\/01\/06\/the-rosser-matrix\/\">Rosser matrix<\/a>.\r\n<pre class=\"codeinput\">   A = fliplr(rosser)\r\n<\/pre>\r\n<pre class=\"codeoutput\">A =\r\n\r\n    29   -49   -52    -8   407  -192   196   611\r\n   -44    -8   -43   -71  -192   113   899   196\r\n    52     8    49    61   196   899   113  -192\r\n   -23    59    44     8   611   196  -192   407\r\n   208   208  -599   411     8    61   -71    -8\r\n   208   208   411  -599    44    49   -43   -52\r\n  -911    99   208   208    59     8    -8   -49\r\n    99  -911   208   208   -23    52   -44    29\r\n\r\n<\/pre>\r\n<h4>Nonsymmetric eigenvalues<a name=\"291005a0-96b4-4ee5-a0f7-eb31d276d2c1\"><\/a><\/h4>\r\nHere is a static picture of the starting matrix. Notice that it is not symmetric.\r\n\r\n<img decoding=\"async\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/eigsvdgif_1a.gif\" alt=\"\" hspace=\"5\" vspace=\"5\" \/>\r\n\r\nThe initial reduction uses <tt>n-2<\/tt> Householder similarites to introduce zeroes below the subdiagonal a column at a time. The result is known as a <i>Hessenberg matrix<\/i> (don't let spell-checkers change that to <i>Heisenberg matrix<\/i>.)\r\n\r\n<img decoding=\"async\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/eigsvdgif_1b.gif\" alt=\"\" hspace=\"5\" vspace=\"5\" \/>\r\n\r\nNow the QR algorithm gradually reduces most subdiagonal elements to roundoff level, so they can be set to zero. The corresponding diagonal element is an eigenvalue. The iteration count is shown in the title. The element below the diagonal in the last row is the initial target; it requires four iterations. The next two rows require three iterations each. The remaining subdiagonals require just one or two iterations each.\r\n\r\n<img decoding=\"async\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/eigsvdgif_1c.gif\" alt=\"\" hspace=\"5\" vspace=\"5\" \/>\r\n\r\nAll this is done with real arithmetic, although a real, nonsymmetric matrix may have complex eigenvalues. So the final matrix may have 2-by-2 bumps on the diagonal. This example has one bump in rows 3 and 4. The eigenvalues of a bump are a complex conjugate pair of eigenvalues of the input matrix. All the other diagonal elements are real eigenvalues of the input matrix.\r\n\r\n<img decoding=\"async\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/eigsvdgif_1d.gif\" alt=\"\" hspace=\"5\" vspace=\"5\" \/>\r\n\r\nThe computed eigenvalues are:\r\n<pre>       -1010.9\r\n        1017.3\r\n       -14.529 + 903.74i\r\n       -14.529 - 903.74i\r\n         206.9\r\n       -30.004\r\n        1.7094\r\n     5.614e-13<\/pre>\r\n<h4>Symmetric eigenvalues<a name=\"acf8ed63-275a-4135-92fb-fcd51965e887\"><\/a><\/h4>\r\nA symmetric matrix is\r\n<pre class=\"codeinput\">   S = (A + A')\/2;\r\n   fprintf([repmat(<span class=\"string\">' %7.1f'<\/span>,1,8) <span class=\"string\">'\\n'<\/span>],S)\r\n<\/pre>\r\n<pre class=\"codeoutput\">    29.0   -46.5     0.0   -15.5   307.5     8.0  -357.5   355.0\r\n   -46.5    -8.0   -17.5    -6.0     8.0   160.5   499.0  -357.5\r\n     0.0   -17.5    49.0    52.5  -201.5   655.0   160.5     8.0\r\n   -15.5    -6.0    52.5     8.0   511.0  -201.5     8.0   307.5\r\n   307.5     8.0  -201.5   511.0     8.0    52.5    -6.0   -15.5\r\n     8.0   160.5   655.0  -201.5    52.5    49.0   -17.5     0.0\r\n  -357.5   499.0   160.5     8.0    -6.0   -17.5    -8.0   -46.5\r\n   355.0  -357.5     8.0   307.5   -15.5     0.0   -46.5    29.0\r\n<\/pre>\r\nHere is the static picture. (The computation is done on half of the matrix, but we show the entire array.)\r\n\r\n<img decoding=\"async\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/eigsvdgif_2a.gif\" alt=\"\" hspace=\"5\" vspace=\"5\" \/>\r\n\r\nBy symmetry the six Householders that zero the columns also zero the rows.\r\n\r\n<img decoding=\"async\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/eigsvdgif_2b.gif\" alt=\"\" hspace=\"5\" vspace=\"5\" \/>\r\n\r\nNow the QR iteration works on just two vectors, the diagonal and the off-diagonal.\r\n\r\n<img decoding=\"async\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/eigsvdgif_2c.gif\" alt=\"\" hspace=\"5\" vspace=\"5\" \/>\r\n\r\nThe limit is the diagonal containing the eigenvalues.\r\n\r\n<img decoding=\"async\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/eigsvdgif_2d.gif\" alt=\"\" hspace=\"5\" vspace=\"5\" \/>\r\n<pre>       -1010.9\r\n        1017.4\r\n       -558.86\r\n       -481.89\r\n        -86.32\r\n         109.7\r\n         662.7\r\n        504.27<\/pre>\r\n<h4>SVD<a name=\"f766aaf7-35fd-4813-a844-1df0dbcfc05d\"><\/a><\/h4>\r\nMake our test matrix rectangular by inserting a couple of rows of the identity matrix.\r\n<pre class=\"codeinput\">   I = eye(8,8);\r\n   A = [A(1:4,:); I(1,:); A(5:8,:); I(2,:)]\r\n<\/pre>\r\n<pre class=\"codeoutput\">A =\r\n\r\n    29   -49   -52    -8   407  -192   196   611\r\n   -44    -8   -43   -71  -192   113   899   196\r\n    52     8    49    61   196   899   113  -192\r\n   -23    59    44     8   611   196  -192   407\r\n     1     0     0     0     0     0     0     0\r\n   208   208  -599   411     8    61   -71    -8\r\n   208   208   411  -599    44    49   -43   -52\r\n  -911    99   208   208    59     8    -8   -49\r\n    99  -911   208   208   -23    52   -44    29\r\n     0     1     0     0     0     0     0     0\r\n\r\n<\/pre>\r\n<img decoding=\"async\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/eigsvdgif_3a.gif\" alt=\"\" hspace=\"5\" vspace=\"5\" \/>\r\n\r\nUse a Householder operating from the left to zero a column and then another Householder operating from the right to zero most of a row.\r\n\r\n<img decoding=\"async\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/eigsvdgif_3b.gif\" alt=\"\" hspace=\"5\" vspace=\"5\" \/>\r\n\r\nNow a two-sided QR iteration reduces the off diagonal to negligible size.\r\n\r\n<img decoding=\"async\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/eigsvdgif_3c.gif\" alt=\"\" hspace=\"5\" vspace=\"5\" \/>\r\n\r\nThe resulting diagonal contains the singular values.\r\n\r\n<img decoding=\"async\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/eigsvdgif_3d.gif\" alt=\"\" hspace=\"5\" vspace=\"5\" \/>\r\n<pre>       0.44272\r\n       0.13184\r\n          1000\r\n          1000\r\n        1019.9\r\n          1020\r\n          1020\r\n          1020<\/pre>\r\n<h4>Software<a name=\"fda5b238-8498-470d-a2df-247cd61d622c\"><\/a><\/h4>\r\nSee <tt>eigsvdgui<\/tt> in <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/37976-numerical-computing-with-matlab\">Numerical Computing with MATLAB<\/a> or <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/59085-cleve_s-laboratory\">Cleve's Laboratory<\/a>.\r\n<script language=\"JavaScript\"> <!-- \r\n    function grabCode_30b0fff5ba91433a82ea2ab0a529df22() {\r\n        \/\/ Remember the title so we can use it in the new page\r\n        title = document.title;\r\n\r\n        \/\/ Break up these strings so that their presence\r\n        \/\/ in the Javascript doesn't mess up the search for\r\n        \/\/ the MATLAB code.\r\n        t1='30b0fff5ba91433a82ea2ab0a529df22 ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' 30b0fff5ba91433a82ea2ab0a529df22';\r\n    \r\n        b=document.getElementsByTagName('body')[0];\r\n        i1=b.innerHTML.indexOf(t1)+t1.length;\r\n        i2=b.innerHTML.indexOf(t2);\r\n \r\n        code_string = b.innerHTML.substring(i1, i2);\r\n        code_string = code_string.replace(\/REPLACE_WITH_DASH_DASH\/g,'--');\r\n\r\n        \/\/ Use \/x3C\/g instead of the less-than character to avoid errors \r\n        \/\/ in the XML parser.\r\n        \/\/ Use '\\x26#60;' instead of '<' so that the XML parser\r\n        \/\/ doesn't go ahead and substitute the less-than character. \r\n        code_string = code_string.replace(\/\\x3C\/g, '\\x26#60;');\r\n\r\n        copyright = 'Copyright 2019 The MathWorks, Inc.';\r\n\r\n        w = window.open();\r\n        d = w.document;\r\n        d.write('<\/p>\r\n<pre>\\n');\r\n        d.write(code_string);\r\n\r\n        \/\/ Add copyright line at the bottom if specified.\r\n        if (copyright.length > 0) {\r\n            d.writeln('');\r\n            d.writeln('%%');\r\n            if (copyright.length > 0) {\r\n                d.writeln('% _' + copyright + '_');\r\n            }\r\n        }\r\n\r\n        d.write('<\/pre>\r\n<p>\\n');\r\n\r\n        d.title = title + ' (MATLAB code)';\r\n        d.close();\r\n    }   \r\n     --> <\/script>\r\n<p style=\"text-align: right; font-size: xx-small; font-weight: lighter; font-style: italic; color: gray;\">\r\n<a><span style=\"font-size: x-small; font-style: italic;\">Get\r\nthe MATLAB code<noscript>(requires JavaScript)<\/noscript><\/span><\/a>\r\n\r\nPublished with MATLAB\u00ae R2018b<\/p>\r\n\r\n<\/div>\r\n<!--\r\n30b0fff5ba91433a82ea2ab0a529df22 ##### SOURCE BEGIN #####\r\n%% The QR Algorithm Computes Eigenvalues and Singular Values\r\n% The QR algorithm is one of the world's most successful algorithms.\r\n% We can use animated gifs to illustrate three variants of the algorithm,\r\n% one for computing the eigenvalues of a nonsymmetric matrix,\r\n% one for a symmetric matrix,\r\n% and one for the singular values of a rectangular matrix.\r\n% In all three cases, the QR iteration itself is preceded by a reduction\r\n% to a compact form.  All transformations are orthogonal similarities\r\n% using Givens and Householder transformations.  These are numerically\r\n% stable, preserve eigenvalues, and preserve any symmetry.\r\n\r\n%%\r\n% The starting matrix for all three variants is based on flipping the\r\n% <https:\/\/blogs.mathworks.com\/cleve\/2014\/01\/06\/the-rosser-matrix\/ % Rosser matrix>.\r\n\r\nA = fliplr(rosser)\r\n\r\n%% Nonsymmetric eigenvalues\r\n% Here is a static picture of the starting matrix.  Notice that it is not\r\n% symmetric.\r\n%\r\n% <<eigsvdgif_1a.gif>>\r\n%\r\n\r\n%%\r\n% The initial reduction uses |n-2| Householder similarites to introduce\r\n% zeroes below the subdiagonal a column at a time.\r\n% The result is known as a _Hessenberg matrix_ (don't let spell-checkers\r\n% change that to _Heisenberg matrix_.)\r\n%\r\n% <<eigsvdgif_1b.gif>>\r\n%\r\n\r\n%%\r\n% Now the QR algorithm gradually reduces most subdiagonal elements to\r\n% roundoff level, so they can be set to zero.  The corresponding\r\n% diagonal element is an eigenvalue.  The iteration count\r\n% is shown in the title.  The element below the diagonal in the last\r\n% row is the initial target; it requires four iterations. The next two\r\n% rows require three iterations each.  The remaining subdiagonals\r\n% require just one or two iterations each.\r\n%\r\n% <<eigsvdgif_1c.gif>>\r\n%\r\n\r\n%%\r\n% All this is done with real arithmetic, although a real, nonsymmetric\r\n% matrix may have complex eigenvalues.  So the final matrix may have\r\n% 2-by-2 bumps on the diagonal.  This example has one bump in rows 3 and 4.\r\n% The eigenvalues of a bump are a complex conjugate pair of eigenvalues\r\n% of the input matrix.  All the other diagonal elements are real\r\n% eigenvalues of the input matrix.\r\n%\r\n%\r\n% <<eigsvdgif_1d.gif>>\r\n%\r\n\r\n%%\r\n% The computed eigenvalues are:\r\n%\r\n%         -1010.9\r\n%          1017.3\r\n%         -14.529 + 903.74i\r\n%         -14.529 - 903.74i\r\n%           206.9\r\n%         -30.004\r\n%          1.7094\r\n%       5.614e-13\r\n%\r\n\r\n%% Symmetric eigenvalues\r\n% A symmetric matrix is\r\n\r\nS = (A + A')\/2;\r\nfprintf([repmat(' %7.1f',1,8) '\\n'],S)\r\n\r\n%%\r\n% Here is the static picture.  (The computation is done on half\r\n% of the matrix, but we show the entire array.)\r\n%\r\n% <<eigsvdgif_2a.gif>>\r\n%\r\n\r\n%%\r\n% By symmetry the six Householders that zero the columns also zero\r\n% the rows.\r\n%\r\n% <<eigsvdgif_2b.gif>>\r\n%\r\n\r\n%%\r\n% Now the QR iteration works on just two vectors, the diagonal and the\r\n% off-diagonal.\r\n%\r\n% <<eigsvdgif_2c.gif>>\r\n%\r\n\r\n%%\r\n% The limit is the diagonal containing the eigenvalues.\r\n%\r\n% <<eigsvdgif_2d.gif>>\r\n%\r\n%\r\n%         -1010.9\r\n%          1017.4\r\n%         -558.86\r\n%         -481.89\r\n%          -86.32\r\n%           109.7\r\n%           662.7\r\n%          504.27\r\n\r\n%% SVD\r\n% Make our test matrix rectangular by inserting a couple of rows of the\r\n% identity matrix.\r\n\r\nI = eye(8,8);\r\nA = [A(1:4,:); I(1,:); A(5:8,:); I(2,:)]\r\n\r\n%%\r\n%\r\n% <<eigsvdgif_3a.gif>>\r\n%\r\n% Use a Householder operating from the left to zero a column and then\r\n% another Householder operating from the right to zero most of a row.\r\n%\r\n% <<eigsvdgif_3b.gif>>\r\n%\r\n% Now a two-sided QR iteration reduces the off diagonal to negligible\r\n% size.\r\n%\r\n% <<eigsvdgif_3c.gif>>\r\n%\r\n% The resulting diagonal contains the singular values.\r\n%\r\n% <<eigsvdgif_3d.gif>>\r\n%\r\n%         0.44272\r\n%         0.13184\r\n%            1000\r\n%            1000\r\n%          1019.9\r\n%            1020\r\n%            1020\r\n%            1020\r\n\r\n%% Software\r\n% See |eigsvdgui| in\r\n% <https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/37976-numerical-computing-with-matlab % Numerical Computing with MATLAB> or\r\n% <https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/59085-cleve_s-laboratory % Cleve's Laboratory>.\r\n##### SOURCE END ##### 30b0fff5ba91433a82ea2ab0a529df22\r\n-->","protected":false},"excerpt":{"rendered":"<div class=\"overview-image\"><img src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/eigsvdgif_1d.gif\" class=\"img-responsive attachment-post-thumbnail size-post-thumbnail wp-post-image\" alt=\"\" decoding=\"async\" loading=\"lazy\" \/><\/div><p>\r\n\r\nThe QR algorithm is one of the world's most successful algorithms. We can use animated gifs to illustrate three variants of the algorithm, one for computing the eigenvalues of a nonsymmetric... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/cleve\/2019\/08\/05\/the-qr-algorithm-computes-eigenvalues-and-singular-values\/\">read more >><\/a><\/p>","protected":false},"author":78,"featured_media":5066,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[13,6,30],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/5056"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/users\/78"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/comments?post=5056"}],"version-history":[{"count":7,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/5056\/revisions"}],"predecessor-version":[{"id":5362,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/5056\/revisions\/5362"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/media\/5066"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/media?parent=5056"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/categories?post=5056"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/tags?post=5056"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}