poster
2019-11-23, 21:01
This is a summary of my talk at the conference Celebrating the Centenary of James H. Wilkinson's Birth (https://nla-group.org/2019/01/21/celebrating-the-centenary-of-james-h-wilkinsons-birth/) at the University of Manchester, May 29.
Jim Wilkinson knew that a matrix with badly conditioned simple eigenvalues must be close to a matrix with multiple eigenvalues. How can you find the nearest matrix where some of the eigenvalues have found their mates?
Much of this talk is my interpretation of the 2011 paper (https://doi.org/10.1016/j.laa.2010.09.022) by Rafikul Alam, Shreemayee Bora, Ralph Byers and Michael Overton, "Characterization and construction of the nearest defective matrix via coalescence of pseudospectral components," in Linear Algebra and its Applications, vol. 435, pp. 494-513. Overton's accompanying code neardefmat is over 1000 lines of MATLAB® and is available from his web page (https://cs.nyu.edu/faculty/overton/software/neardefmat/).
Contents
A 3-by-3 Example (https://blogs.mathworks.com/cleve/2019/05/28/matrix-eigenvalue-dating-service/#52913f70-5370-44dd-a7c0-850721b7271e)
Frank(9) (https://blogs.mathworks.com/cleve/2019/05/28/matrix-eigenvalue-dating-service/#da296679-fa4a-45ba-a2c5-549e2adbfd6f)
Wilkinson(9) (https://blogs.mathworks.com/cleve/2019/05/28/matrix-eigenvalue-dating-service/#78f7a630-8511-4a79-b309-34e3037bf3c4)
A 3-by-3 Example
In last week's blog post, "An Eigenvalue Sensitivity Example" (https://blogs.mathworks.com/cleve/2019/05/22/an-eigenvalue-sensitivity-example/), I resurrected this example from the 1980 User's Guide. For a moment, let's forget how it was constructed and start with
A = [ -64 82 21; 144 -178 -46; -771 962 248]A = -64 82 21 144 -178 -46 -771 962 248The computed eigenvalues are
format long lambda = eig(A)lambda = 3.000000000003868 0.999999999998212 1.999999999997978The exact eigenvalues are 1, 2 and 3. We've lost about four figures. This is predicted by the eigenvalue condition numbers,
format short kappa = condeig(A)kappa = 833.1092 450.7228 383.7564These condition numbers come from the right eigenvector matrix
[X,~] = eig(A)X = 0.0891 0.0735 -0.1089 -0.1782 -0.1923 0.1634 0.9800 0.9786 -0.9805And the left eigenvector matrix
Y = inv(X)Y = -521.9612 628.5984 162.7621 265.1820 -353.5760 -88.3940 -257.0058 275.3634 73.4302The rows of Y are left eigenvectors. They are normalized so that their dot product with the right eigenvectors is one.
Y*Xans = 1.0000 -0.0000 -0.0000 -0.0000 1.0000 -0.0000 -0.0000 0.0000 1.0000A function introduced in 2017b that computes the 2-norm of the columns of a matrix comes in handy at this point.
kappa = (vecnorm(Y').*vecnorm(X))'kappa = 833.1092 450.7228 383.7564EigTool (http://www.cs.ox.ac.uk/pseudospectra/eigtool/) is open MATLAB software for analyzing eigenvalues, pseudospectra, and related spectral properties of matrices. It was developed at Oxford from 1999 - 2002 by Thomas Wright under the direction of Nick Trefethen. It is now maintained by Mark Embree.
Here is the pseudospectrum of our example matrix.
eigtool(A)
http://blogs.mathworks.com/cleve/files/fig1-1.png
You can see the three eigenvalues at 1, 2 and 3. The contours outline the regions where the eigenvalues can move when the matrix is perturbed by a specified amount.
This animated gif adjusts the region around the eigenvalues at 2 and 3 until the regions coalesce in a saddle point near 2.4.
http://blogs.mathworks.com/cleve/files/eigtool_movie_blog.gif
To see more precisely where they coalesce, we use the function neardefmat, nearest defective matrix, written by Michael Overton, a professor at NYU. The outputs from neardefmat are B, the nearest defective matrix, and z, the resulting double eigenvalue. By default neardefmat prints some useful details about the computation.
format long = neardefmat(A)neardefmat: lower bound on distance is 0.000299834 and upper bound is 0.00618718neardefmat: finished, lowest saddle found is 2.41449 + 0 i with dist = 0.000375171, mu = 0, |u'*v| = 3.67335e-06 singular vector residual norms are 1.8334e-13, 5.17298e-14 this saddle point was found in search # 3distance to nearest defective matrix B found is 0.000375171neardefmat: two closest computed eigenvalues of B differ by 0.00269716 and condition numbers of these eigenvalues are 272230, 272669B = 1.0e+02 * -0.639999774916363 0.819999582124016 0.210002343527353 1.439999736641696 -1.779999511065701 -0.460002742035793 -7.710000068576393 9.620000127314574 2.479999285995845z = 2.414492300748820B is constructed from z, an SVD and a rank one perturbation of A.
I = eye(3); [U,S,V] = svd(A - z*I); format short sigma = S(3,3) u = U(:,3) v = V(:,3) format long B = A - sigma*u*v'sigma = 3.7517e-04u = -0.6373 0.7457 0.1942v = 0.0941 -0.1748 0.9801B = 1.0e+02 * -0.639999774916363 0.819999582124016 0.210002343527353 1.439999736641696 -1.779999511065701 -0.460002742035793 -7.710000068576393 9.620000127314574 2.479999285995845This is essentially the same perturbation that I used to construct A in last week's blog post. The size of the perturbation is
sigma = S(3,3) sigma = norm(B - A)sigma = 3.751705175569800e-04sigma = 3.751705175556183e-04By construction, B has a double eigenvalue, but the eigenvalue's condition is infinite, so it is not computed accurately.
eig(B)ans = 2.417189453582737 2.414492295643361 1.168318252152021[B]Frank(9)
Wilkinson was interested in the Frank family of matrices. Of course, we can find them in the gallery.
help private/frank FRANK Frank matrix. F = GALLERY('FRANK',N, K) is the Frank matrix of order N. It is upper Hessenberg with determinant 1. If K = 1, the elements are reflected about the anti-diagonal (1,N)--(N,1). The eigenvalues of F may be obtained in terms of the zeros of the Hermite polynomials. They are positive and occur in reciprocal pairs; thus if N is odd, 1 is an eigenvalue. F has FLOOR(N/2) ill-conditioned eigenvalues---the smaller ones.The 9x9 Frank matrix fits nicely on the page.
F = gallery('frank',9)F = 9 8 7 6 5 4 3 2 1 8 8 7 6 5 4 3 2 1 0 7 7 6 5 4 3 2 1 0 0 6 6 5 4 3 2 1 0 0 0 5 5 4 3 2 1 0 0 0 0 4 4 3 2 1 0 0 0 0 0 3 3 2 1 0 0 0 0 0 0 2 2 1 0 0 0 0 0 0 0 1 1The matrix is clearly far from symmetric. Since it is almost upper triangular you might think the eigenvalues are near the diagonal elements, but they are not. Here they are, sorted.
format long [lambda,p] = sort(eig(F)); lambdalambda = 0.044802721845067 0.082015890201792 0.162582729486328 0.374121140912600 0.999999999999966 2.672931012564413 6.150714797051293 12.192759202150013 22.320072505788492And here are the corresponding condition numbers.
format short e kappa = condeig(F); kappa = kappa(p)kappa = 1.4762e+04 2.5134e+04 1.1907e+04 1.5996e+03 6.8615e+01 3.6210e+00 1.5268e+00 2.3903e+00 1.9916e+00The three smallest eigenvalues have the largest condition numbers. We expect the nearest defective matrix to bring two of them together.
Eigtool of the Frank matrix.
eigtool(F)
http://blogs.mathworks.com/cleve/files/fig3-1.png
Focus on the three smallest eigenvalues. The red contour shows the regions containing the two that are coalescing.
http://blogs.mathworks.com/cleve/files/fig4.png
Find the nearest defective matrix.
format long = neardefmat(F);neardefmat: lower bound on distance is 3.4791e-07 and upper bound is 8.76938e-05neardefmat: finished, lowest saddle found is 0.06104 + 0 i with dist = 5.01214e-07, mu = 0, |u'*v| = 6.09133e-10 singular vector residual norms are 3.6435e-15, 6.12511e-16 this saddle point was found in search # 1distance to nearest defective matrix B found is 5.01214e-07neardefmat: two closest computed eigenvalues of B differ by 1.7808e-06 and condition numbers of these eigenvalues are 3.62946e+08, 3.62937e+08The two smallest eigenvalues have merged, but they are hyper-sensitive.
sort(eig(B))ans = 0.061039353359070 0.061041134158948 0.168054858422710 0.373370423277969 1.000016557229929 2.672931171283966 6.150714794349185 12.192759202129578 22.320072505788680If we're not too strict on the tolerance, the eigenvector matrix X is rank deficient, implying the matrix B is defective.
[X,~] = eig(B); rank(X,1.e-8)ans = 8We can get a picture of the perturbation with the imagesc function. First, the matrix itself. You can see its upper Hessenberg (nearly upper triangular) structure.
imagesc(F)
http://blogs.mathworks.com/cleve/files/fig5.png
Now, the picture of the perturbation shows that it is concentrated in the upper right-hand corner.
imagesc(F-B)
http://blogs.mathworks.com/cleve/files/fig6.png
[B]Wilkinson(9)
What perturbation of a symmetric matrix makes its eigenvalues coalesce? A great example was provided by Wilkinson himself.
help wilkinson W = wilkinson(9) WILKINSON Wilkinson's eigenvalue test matrix. W = WILKINSON(n) is J. H. Wilkinson's eigenvalue test matrix, Wn+. It is a symmetric, tridiagonal matrix with pairs of nearly, but not exactly, equal eigenvalues. The most frequently used case is WILKINSON(21). W = WILKINSON(n,CLASSNAME) returns a matrix of class CLASSNAME, which can be either 'single' or 'double' (the default). Example: WILKINSON(7) is 3 1 0 0 0 0 0 1 2 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 2 1 0 0 0 0 0 1 3 Reference page in Doc Center doc wilkinsonW = 4 1 0 0 0 0 0 0 0 1 3 1 0 0 0 0 0 0 0 1 2 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 2 1 0 0 0 0 0 0 0 1 3 1 0 0 0 0 0 0 0 1 4W is symmetric and tridiagonal with ones on the off-diagonals. In order to have a multiple eigenvalue such a matrix has to have a pair of zeroes somewhere on the sub- and super-diagonal. But this matrix does not have any small off-diagonal elements. Nevertheless, the two largest eigenvalues are very close to each other.
lambda = eig(W)lambda = -1.125422415673319 0.254718759825861 0.952584219075215 1.822717080887109 2.178284739549981 3.177282919112892 3.247396472578982 4.745281240174140 4.747156984469142Since the matrix is symmetric, the left and right eigenvectors are orthogonal and transposes of each other. All the eigenvalues are perfectly well conditioned. Where should we look for the coalescing eigenvalues?
kappa = condeig(W)kappa = 1.000000000000000 1.000000000000000 1.000000000000000 1.000000000000000 1.000000000000000 1.000000000000000 1.000000000000000 1.000000000000000 1.000000000000000Eigtool of Wilkinson(9). There are only seven circles for a 9x9 matrix -- the two circles on the right each contain two eigenvalues.
eigtool(W)
http://blogs.mathworks.com/cleve/files/fig7.png
Let's zoom way in on the rightmost circle.
http://blogs.mathworks.com/cleve/files/fig8.png
The -3.04 contours are just barely kissing. This is a different kind of saddle point -- a nonsmooth one. You will have to study the Alam et al paper to see why this is so important.
Let's see what neardefmat has to say about Wilkinson's matrix.
[B,z] = neardefmat(W);neardefmat: A is normal within tolerance distance to nearest defective matrix B is 0.000937872neardefmat: two closest computed eigenvalues of B differ by 2.01677e-09 and condition numbers of these eigenvalues are 465036, 465036Sure enough, W is symmetric and hence normal. A rather different algorithm is required.
The perturbed eigenvalues have small imaginary parts.
eig(B)ans = -1.125422415673318 + 0.000000000000000i 0.254718759825861 + 0.000000000000000i 0.952584219075214 + 0.000000000000000i 1.822717080887109 + 0.000000000000000i 2.178284739549983 + 0.000000000000000i 3.177282919112890 + 0.000000000000000i 3.247396472578982 + 0.000000000000000i 4.746219112321641 + 0.000000001008386i 4.746219112321641 - 0.000000001008386iFinally, here are images of the symmetric, tridiagonal matrix W and the very nonsymmetric perturbation W-B that brings two of its eigenvalues together.
http://blogs.mathworks.com/cleve/files/fig9.png
http://blogs.mathworks.com/cleve/files/fig10.png
Get the MATLAB code
Published with MATLAB® R2018b
更多... (http://feedproxy.google.com/~r/mathworks/moler/~3/d6m5QpJuvS8/)
Jim Wilkinson knew that a matrix with badly conditioned simple eigenvalues must be close to a matrix with multiple eigenvalues. How can you find the nearest matrix where some of the eigenvalues have found their mates?
Much of this talk is my interpretation of the 2011 paper (https://doi.org/10.1016/j.laa.2010.09.022) by Rafikul Alam, Shreemayee Bora, Ralph Byers and Michael Overton, "Characterization and construction of the nearest defective matrix via coalescence of pseudospectral components," in Linear Algebra and its Applications, vol. 435, pp. 494-513. Overton's accompanying code neardefmat is over 1000 lines of MATLAB® and is available from his web page (https://cs.nyu.edu/faculty/overton/software/neardefmat/).
Contents
A 3-by-3 Example (https://blogs.mathworks.com/cleve/2019/05/28/matrix-eigenvalue-dating-service/#52913f70-5370-44dd-a7c0-850721b7271e)
Frank(9) (https://blogs.mathworks.com/cleve/2019/05/28/matrix-eigenvalue-dating-service/#da296679-fa4a-45ba-a2c5-549e2adbfd6f)
Wilkinson(9) (https://blogs.mathworks.com/cleve/2019/05/28/matrix-eigenvalue-dating-service/#78f7a630-8511-4a79-b309-34e3037bf3c4)
A 3-by-3 Example
In last week's blog post, "An Eigenvalue Sensitivity Example" (https://blogs.mathworks.com/cleve/2019/05/22/an-eigenvalue-sensitivity-example/), I resurrected this example from the 1980 User's Guide. For a moment, let's forget how it was constructed and start with
A = [ -64 82 21; 144 -178 -46; -771 962 248]A = -64 82 21 144 -178 -46 -771 962 248The computed eigenvalues are
format long lambda = eig(A)lambda = 3.000000000003868 0.999999999998212 1.999999999997978The exact eigenvalues are 1, 2 and 3. We've lost about four figures. This is predicted by the eigenvalue condition numbers,
format short kappa = condeig(A)kappa = 833.1092 450.7228 383.7564These condition numbers come from the right eigenvector matrix
[X,~] = eig(A)X = 0.0891 0.0735 -0.1089 -0.1782 -0.1923 0.1634 0.9800 0.9786 -0.9805And the left eigenvector matrix
Y = inv(X)Y = -521.9612 628.5984 162.7621 265.1820 -353.5760 -88.3940 -257.0058 275.3634 73.4302The rows of Y are left eigenvectors. They are normalized so that their dot product with the right eigenvectors is one.
Y*Xans = 1.0000 -0.0000 -0.0000 -0.0000 1.0000 -0.0000 -0.0000 0.0000 1.0000A function introduced in 2017b that computes the 2-norm of the columns of a matrix comes in handy at this point.
kappa = (vecnorm(Y').*vecnorm(X))'kappa = 833.1092 450.7228 383.7564EigTool (http://www.cs.ox.ac.uk/pseudospectra/eigtool/) is open MATLAB software for analyzing eigenvalues, pseudospectra, and related spectral properties of matrices. It was developed at Oxford from 1999 - 2002 by Thomas Wright under the direction of Nick Trefethen. It is now maintained by Mark Embree.
Here is the pseudospectrum of our example matrix.
eigtool(A)
http://blogs.mathworks.com/cleve/files/fig1-1.png
You can see the three eigenvalues at 1, 2 and 3. The contours outline the regions where the eigenvalues can move when the matrix is perturbed by a specified amount.
This animated gif adjusts the region around the eigenvalues at 2 and 3 until the regions coalesce in a saddle point near 2.4.
http://blogs.mathworks.com/cleve/files/eigtool_movie_blog.gif
To see more precisely where they coalesce, we use the function neardefmat, nearest defective matrix, written by Michael Overton, a professor at NYU. The outputs from neardefmat are B, the nearest defective matrix, and z, the resulting double eigenvalue. By default neardefmat prints some useful details about the computation.
format long = neardefmat(A)neardefmat: lower bound on distance is 0.000299834 and upper bound is 0.00618718neardefmat: finished, lowest saddle found is 2.41449 + 0 i with dist = 0.000375171, mu = 0, |u'*v| = 3.67335e-06 singular vector residual norms are 1.8334e-13, 5.17298e-14 this saddle point was found in search # 3distance to nearest defective matrix B found is 0.000375171neardefmat: two closest computed eigenvalues of B differ by 0.00269716 and condition numbers of these eigenvalues are 272230, 272669B = 1.0e+02 * -0.639999774916363 0.819999582124016 0.210002343527353 1.439999736641696 -1.779999511065701 -0.460002742035793 -7.710000068576393 9.620000127314574 2.479999285995845z = 2.414492300748820B is constructed from z, an SVD and a rank one perturbation of A.
I = eye(3); [U,S,V] = svd(A - z*I); format short sigma = S(3,3) u = U(:,3) v = V(:,3) format long B = A - sigma*u*v'sigma = 3.7517e-04u = -0.6373 0.7457 0.1942v = 0.0941 -0.1748 0.9801B = 1.0e+02 * -0.639999774916363 0.819999582124016 0.210002343527353 1.439999736641696 -1.779999511065701 -0.460002742035793 -7.710000068576393 9.620000127314574 2.479999285995845This is essentially the same perturbation that I used to construct A in last week's blog post. The size of the perturbation is
sigma = S(3,3) sigma = norm(B - A)sigma = 3.751705175569800e-04sigma = 3.751705175556183e-04By construction, B has a double eigenvalue, but the eigenvalue's condition is infinite, so it is not computed accurately.
eig(B)ans = 2.417189453582737 2.414492295643361 1.168318252152021[B]Frank(9)
Wilkinson was interested in the Frank family of matrices. Of course, we can find them in the gallery.
help private/frank FRANK Frank matrix. F = GALLERY('FRANK',N, K) is the Frank matrix of order N. It is upper Hessenberg with determinant 1. If K = 1, the elements are reflected about the anti-diagonal (1,N)--(N,1). The eigenvalues of F may be obtained in terms of the zeros of the Hermite polynomials. They are positive and occur in reciprocal pairs; thus if N is odd, 1 is an eigenvalue. F has FLOOR(N/2) ill-conditioned eigenvalues---the smaller ones.The 9x9 Frank matrix fits nicely on the page.
F = gallery('frank',9)F = 9 8 7 6 5 4 3 2 1 8 8 7 6 5 4 3 2 1 0 7 7 6 5 4 3 2 1 0 0 6 6 5 4 3 2 1 0 0 0 5 5 4 3 2 1 0 0 0 0 4 4 3 2 1 0 0 0 0 0 3 3 2 1 0 0 0 0 0 0 2 2 1 0 0 0 0 0 0 0 1 1The matrix is clearly far from symmetric. Since it is almost upper triangular you might think the eigenvalues are near the diagonal elements, but they are not. Here they are, sorted.
format long [lambda,p] = sort(eig(F)); lambdalambda = 0.044802721845067 0.082015890201792 0.162582729486328 0.374121140912600 0.999999999999966 2.672931012564413 6.150714797051293 12.192759202150013 22.320072505788492And here are the corresponding condition numbers.
format short e kappa = condeig(F); kappa = kappa(p)kappa = 1.4762e+04 2.5134e+04 1.1907e+04 1.5996e+03 6.8615e+01 3.6210e+00 1.5268e+00 2.3903e+00 1.9916e+00The three smallest eigenvalues have the largest condition numbers. We expect the nearest defective matrix to bring two of them together.
Eigtool of the Frank matrix.
eigtool(F)
http://blogs.mathworks.com/cleve/files/fig3-1.png
Focus on the three smallest eigenvalues. The red contour shows the regions containing the two that are coalescing.
http://blogs.mathworks.com/cleve/files/fig4.png
Find the nearest defective matrix.
format long = neardefmat(F);neardefmat: lower bound on distance is 3.4791e-07 and upper bound is 8.76938e-05neardefmat: finished, lowest saddle found is 0.06104 + 0 i with dist = 5.01214e-07, mu = 0, |u'*v| = 6.09133e-10 singular vector residual norms are 3.6435e-15, 6.12511e-16 this saddle point was found in search # 1distance to nearest defective matrix B found is 5.01214e-07neardefmat: two closest computed eigenvalues of B differ by 1.7808e-06 and condition numbers of these eigenvalues are 3.62946e+08, 3.62937e+08The two smallest eigenvalues have merged, but they are hyper-sensitive.
sort(eig(B))ans = 0.061039353359070 0.061041134158948 0.168054858422710 0.373370423277969 1.000016557229929 2.672931171283966 6.150714794349185 12.192759202129578 22.320072505788680If we're not too strict on the tolerance, the eigenvector matrix X is rank deficient, implying the matrix B is defective.
[X,~] = eig(B); rank(X,1.e-8)ans = 8We can get a picture of the perturbation with the imagesc function. First, the matrix itself. You can see its upper Hessenberg (nearly upper triangular) structure.
imagesc(F)
http://blogs.mathworks.com/cleve/files/fig5.png
Now, the picture of the perturbation shows that it is concentrated in the upper right-hand corner.
imagesc(F-B)
http://blogs.mathworks.com/cleve/files/fig6.png
[B]Wilkinson(9)
What perturbation of a symmetric matrix makes its eigenvalues coalesce? A great example was provided by Wilkinson himself.
help wilkinson W = wilkinson(9) WILKINSON Wilkinson's eigenvalue test matrix. W = WILKINSON(n) is J. H. Wilkinson's eigenvalue test matrix, Wn+. It is a symmetric, tridiagonal matrix with pairs of nearly, but not exactly, equal eigenvalues. The most frequently used case is WILKINSON(21). W = WILKINSON(n,CLASSNAME) returns a matrix of class CLASSNAME, which can be either 'single' or 'double' (the default). Example: WILKINSON(7) is 3 1 0 0 0 0 0 1 2 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 2 1 0 0 0 0 0 1 3 Reference page in Doc Center doc wilkinsonW = 4 1 0 0 0 0 0 0 0 1 3 1 0 0 0 0 0 0 0 1 2 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 2 1 0 0 0 0 0 0 0 1 3 1 0 0 0 0 0 0 0 1 4W is symmetric and tridiagonal with ones on the off-diagonals. In order to have a multiple eigenvalue such a matrix has to have a pair of zeroes somewhere on the sub- and super-diagonal. But this matrix does not have any small off-diagonal elements. Nevertheless, the two largest eigenvalues are very close to each other.
lambda = eig(W)lambda = -1.125422415673319 0.254718759825861 0.952584219075215 1.822717080887109 2.178284739549981 3.177282919112892 3.247396472578982 4.745281240174140 4.747156984469142Since the matrix is symmetric, the left and right eigenvectors are orthogonal and transposes of each other. All the eigenvalues are perfectly well conditioned. Where should we look for the coalescing eigenvalues?
kappa = condeig(W)kappa = 1.000000000000000 1.000000000000000 1.000000000000000 1.000000000000000 1.000000000000000 1.000000000000000 1.000000000000000 1.000000000000000 1.000000000000000Eigtool of Wilkinson(9). There are only seven circles for a 9x9 matrix -- the two circles on the right each contain two eigenvalues.
eigtool(W)
http://blogs.mathworks.com/cleve/files/fig7.png
Let's zoom way in on the rightmost circle.
http://blogs.mathworks.com/cleve/files/fig8.png
The -3.04 contours are just barely kissing. This is a different kind of saddle point -- a nonsmooth one. You will have to study the Alam et al paper to see why this is so important.
Let's see what neardefmat has to say about Wilkinson's matrix.
[B,z] = neardefmat(W);neardefmat: A is normal within tolerance distance to nearest defective matrix B is 0.000937872neardefmat: two closest computed eigenvalues of B differ by 2.01677e-09 and condition numbers of these eigenvalues are 465036, 465036Sure enough, W is symmetric and hence normal. A rather different algorithm is required.
The perturbed eigenvalues have small imaginary parts.
eig(B)ans = -1.125422415673318 + 0.000000000000000i 0.254718759825861 + 0.000000000000000i 0.952584219075214 + 0.000000000000000i 1.822717080887109 + 0.000000000000000i 2.178284739549983 + 0.000000000000000i 3.177282919112890 + 0.000000000000000i 3.247396472578982 + 0.000000000000000i 4.746219112321641 + 0.000000001008386i 4.746219112321641 - 0.000000001008386iFinally, here are images of the symmetric, tridiagonal matrix W and the very nonsymmetric perturbation W-B that brings two of its eigenvalues together.
http://blogs.mathworks.com/cleve/files/fig9.png
http://blogs.mathworks.com/cleve/files/fig10.png
Get the MATLAB code
Published with MATLAB® R2018b
更多... (http://feedproxy.google.com/~r/mathworks/moler/~3/d6m5QpJuvS8/)