| Author |
Message |
Randy Yates
Guest
|
 Posted:
Sun Dec 11, 2005 8:05 am Post subject:
Eigenvalue Accuracy in Matlab |
|
|
Hi Folks,
Consider the following integer matrix:
A =
1 0 -1
-1 1 0
3 -1 -2
A is a nilpotent matrix of index 3, as can be seen by evaluating A^3.
So then the only eigenvalues of A are zero.
However, Matlab's "eig" function returns:
ans =
-7.178125070607518e-006
3.589062535291640e-006 +6.216541114106220e-006i
3.589062535291640e-006 -6.216541114106220e-006i
Is there no way to get exact results for such simple matrices? Or
is there a way to establish some sort of rounding for these types
of functions?
--
% Randy Yates % "So now it's getting late,
%% Fuquay-Varina, NC % and those who hesitate
%%% 919-577-9882 % got no one..."
%%%% <yates@ieee.org> % 'Waterfall', *Face The Music*, ELO
http://home.earthlink.net/~yatescr |
|
| Back to top |
|
 |
Nasser Abbasi
Guest
|
| Posted:
Sun Dec 11, 2005 8:10 am Post subject:
Re: Eigenvalue Accuracy in Matlab |
|
|
"Randy Yates" <yates@ieee.org> wrote in message
news:irtwxu9y.fsf@ieee.org...
| Quote: | Hi Folks,
Consider the following integer matrix:
A =
1 0 -1
-1 1 0
3 -1 -2
A is a nilpotent matrix of index 3, as can be seen by evaluating
A^3.
So then the only eigenvalues of A are zero.
However, Matlab's "eig" function returns:
ans =
-7.178125070607518e-006
3.589062535291640e-006 +6.216541114106220e-006i
3.589062535291640e-006 -6.216541114106220e-006i
Is there no way to get exact results for such simple matrices? Or
is there a way to establish some sort of rounding for these types
of functions?
--
% Randy Yates % "So now it's getting late,
%% Fuquay-Varina, NC % and those who hesitate
%%% 919-577-9882 % got no one..."
%%%% <yates@ieee.org> % 'Waterfall', *Face The Music*, ELO
http://home.earthlink.net/~yatescr
|
If you want accurate use symbolic.
1 0 -1
-1 1 0
3 -1 -2
ans =
0
0
0
Nasser |
|
| Back to top |
|
|
Randy Yates
Guest
|
| Posted:
Sun Dec 11, 2005 8:33 am Post subject:
Re: Eigenvalue Accuracy in Matlab |
|
|
"Nasser Abbasi" <nma@12000.org> writes:
| Quote: | [...]
If you want accurate use symbolic.
|
Very nice! Thanks Nasser.
--
% Randy Yates % "Ticket to the moon, flight leaves here today
%% Fuquay-Varina, NC % from Satellite 2"
%%% 919-577-9882 % 'Ticket To The Moon'
%%%% <yates@ieee.org> % *Time*, Electric Light Orchestra
http://home.earthlink.net/~yatescr |
|
| Back to top |
|
|
Mr Hrundi V Bakshi
Guest
|
| Posted:
Sun Dec 11, 2005 9:10 am Post subject:
Re: Eigenvalue Accuracy in Matlab |
|
|
"Randy Yates" <yates@ieee.org> wrote in message
news:irtwxu9y.fsf@ieee.org...
| Quote: | Hi Folks,
Consider the following integer matrix:
A =
1 0 -1
-1 1 0
3 -1 -2
A is a nilpotent matrix of index 3, as can be seen by evaluating A^3.
So then the only eigenvalues of A are zero.
|
schur(A) is upper triangular with A's eigenvalues along the diagonal.
--
HTH,
Hrundi V.B. |
|
| Back to top |
|
|
Mr Hrundi V Bakshi
Guest
|
| Posted:
Sun Dec 11, 2005 9:15 am Post subject:
Re: Eigenvalue Accuracy in Matlab |
|
|
"Randy Yates" <yates@ieee.org> wrote in message
news:fyp0wbm9.fsf@ieee.org...
| Quote: | "Mr Hrundi V Bakshi" <mrhrundivbakshi@hotmail.com> writes:
"Randy Yates" <yates@ieee.org> wrote in message
news:irtwxu9y.fsf@ieee.org...
Hi Folks,
Consider the following integer matrix:
A =
1 0 -1
-1 1 0
3 -1 -2
A is a nilpotent matrix of index 3, as can be seen by evaluating A^3.
So then the only eigenvalues of A are zero.
schur(A) is upper triangular with A's eigenvalues along the diagonal.
Same problem.
|
Nah,
ans =
-0.0000 -1.2247 -2.1213
0 0.0000 -3.4641
0 0.0000 0.0000 |
|
| Back to top |
|
|
Randy Yates
Guest
|
| Posted:
Sun Dec 11, 2005 9:15 am Post subject:
Re: Eigenvalue Accuracy in Matlab |
|
|
"Mr Hrundi V Bakshi" <mrhrundivbakshi@hotmail.com> writes:
| Quote: | "Randy Yates" <yates@ieee.org> wrote in message
news:irtwxu9y.fsf@ieee.org...
Hi Folks,
Consider the following integer matrix:
A =
1 0 -1
-1 1 0
3 -1 -2
A is a nilpotent matrix of index 3, as can be seen by evaluating A^3.
So then the only eigenvalues of A are zero.
schur(A) is upper triangular with A's eigenvalues along the diagonal.
|
Same problem.
--
% Randy Yates % "...the answer lies within your soul
%% Fuquay-Varina, NC % 'cause no one knows which side
%%% 919-577-9882 % the coin will fall."
%%%% <yates@ieee.org> % 'Big Wheels', *Out of the Blue*, ELO
http://home.earthlink.net/~yatescr |
|
| Back to top |
|
|
John D'Errico
Guest
|
| Posted:
Sun Dec 11, 2005 9:15 am Post subject:
Re: Eigenvalue Accuracy in Matlab |
|
|
In article <irtwxu9y.fsf@ieee.org>, Randy Yates <yates@ieee.org> wrote:
| Quote: | Hi Folks,
Consider the following integer matrix:
A =
1 0 -1
-1 1 0
3 -1 -2
A is a nilpotent matrix of index 3, as can be seen by evaluating A^3.
So then the only eigenvalues of A are zero.
However, Matlab's "eig" function returns:
ans =
-7.178125070607518e-006
3.589062535291640e-006 +6.216541114106220e-006i
3.589062535291640e-006 -6.216541114106220e-006i
Is there no way to get exact results for such simple matrices? Or
is there a way to establish some sort of rounding for these types
of functions?
|
No. Not without use of symbolic tools. Even they must
fail miserably on a "simple" 5x5 matrix. Ask Galois
why.
Remember that solving for the eigenvalues of a matrix
is a problem highly related to finding the roots of
a polynomial. The characteristic polynomial of this
matrix is a cubic polynomial with a root at zero of
multiplicity 3. Its a surprisingly hard problem to
solve exactly for a root-finding tool. Note that the
accuracy of these eigenvalues is on the order of the
cube root of eps. Its no coincidence.
HTH,
John D'Errico |
|
| Back to top |
|
|
Roger Stafford
Guest
|
| Posted:
Sun Dec 11, 2005 9:15 am Post subject:
Re: Eigenvalue Accuracy in Matlab |
|
|
In article <irtwxu9y.fsf@ieee.org>, Randy Yates <yates@ieee.org> wrote:
| Quote: | Hi Folks,
Consider the following integer matrix:
A =
1 0 -1
-1 1 0
3 -1 -2
A is a nilpotent matrix of index 3, as can be seen by evaluating A^3.
So then the only eigenvalues of A are zero.
However, Matlab's "eig" function returns:
ans =
-7.178125070607518e-006
3.589062535291640e-006 +6.216541114106220e-006i
3.589062535291640e-006 -6.216541114106220e-006i
Is there no way to get exact results for such simple matrices? Or
is there a way to establish some sort of rounding for these types
of functions?
--
% Randy Yates
---------------------------- |
As to the numerical computation of A's eigenvalues, in this case they
are the roots to the cubic equation
0 = det(A - lambda*eye(3)) = -lambda^3
Suppose that matlab, in the process of carrying out a complicated
algorithm for eigenvalue/eigenvector solutions makes a very small roundoff
error out in the 16-th decimal place in the process and arrives at this
equation
-lambda^3 = 3.698563363842292e-16
instead. In this case the solutions for lambda would be:
-7.178125070607523e-06
3.589062535303763e-06 + 6.216438662688082e-06i
3.589062535303763e-06 - 6.216438662688082e-06i
which are quite close to those you obtained!
The point here is that, for this particular ill-conditioned matrix, a
very small rounding error in computing the eigenvalue equation, well
within the limits that could be expected for 64-bit floating point
accuracy, will result in greatly expanded errors for the eigenvalues
themselves. Such instability is inherent in a matrix in which a
multiplicity of its eigenvalues are at, or very close to, zero.
(Remove "xyzzy" and ".invalid" to send me email.)
Roger Stafford |
|
| Back to top |
|
|
Peter K.
Guest
|
| Posted:
Sun Dec 11, 2005 5:15 pm Post subject:
Re: Eigenvalue Accuracy in Matlab |
|
|
"Mr Hrundi V Bakshi" <mrhrundivbakshi@hotmail.com> writes:
| Quote: | "Randy Yates" <yates@ieee.org> wrote in message
news:fyp0wbm9.fsf@ieee.org...
"Mr Hrundi V Bakshi" <mrhrundivbakshi@hotmail.com> writes:
"Randy Yates" <yates@ieee.org> wrote in message
news:irtwxu9y.fsf@ieee.org...
Hi Folks,
Consider the following integer matrix:
A =
1 0 -1
-1 1 0
3 -1 -2
A is a nilpotent matrix of index 3, as can be seen by evaluating A^3.
So then the only eigenvalues of A are zero.
schur(A) is upper triangular with A's eigenvalues along the diagonal.
Same problem.
Nah,
ans =
-0.0000 -1.2247 -2.1213
0 0.0000 -3.4641
0 0.0000 0.0000
|
Yup!
» diag(schur(A))
ans =
1.0e-004 *
-0.0872
0.5866
-0.4994 |
|
| Back to top |
|
|
Randy Yates
Guest
|
| Posted:
Sun Dec 11, 2005 5:15 pm Post subject:
Re: Eigenvalue Accuracy in Matlab |
|
|
John D'Errico <NoKnownAddress@noplace.com> writes:
| Quote: | In article <irtwxu9y.fsf@ieee.org>, Randy Yates <yates@ieee.org> wrote:
Hi Folks,
Consider the following integer matrix:
A =
1 0 -1
-1 1 0
3 -1 -2
A is a nilpotent matrix of index 3, as can be seen by evaluating A^3.
So then the only eigenvalues of A are zero.
However, Matlab's "eig" function returns:
ans =
-7.178125070607518e-006
3.589062535291640e-006 +6.216541114106220e-006i
3.589062535291640e-006 -6.216541114106220e-006i
Is there no way to get exact results for such simple matrices? Or
is there a way to establish some sort of rounding for these types
of functions?
No. Not without use of symbolic tools. Even they must
fail miserably on a "simple" 5x5 matrix. Ask Galois
why.
Remember that solving for the eigenvalues of a matrix
is a problem highly related to finding the roots of
a polynomial. The characteristic polynomial of this
matrix is a cubic polynomial with a root at zero of
multiplicity 3. Its a surprisingly hard problem to
solve exactly for a root-finding tool. Note that the
accuracy of these eigenvalues is on the order of the
cube root of eps. Its no coincidence.
|
Thank you very much, John, not only for the answer, but for the
insight on why. Makes perfect sense.
--
% Randy Yates % "Ticket to the moon, flight leaves here today
%% Fuquay-Varina, NC % from Satellite 2"
%%% 919-577-9882 % 'Ticket To The Moon'
%%%% <yates@ieee.org> % *Time*, Electric Light Orchestra
http://home.earthlink.net/~yatescr |
|
| Back to top |
|
|
Don Orofino
Guest
|
| Posted:
Mon Dec 12, 2005 8:29 am Post subject:
Re: Eigenvalue Accuracy in Matlab |
|
|
Adding very little to the excellent advice given here, a practical method
for assessing "goodness" of the matrix is to compute its condition number.
Well-conditioned matrices will return a reciprocal condition (rcond) result
close to unity; ill-conditioned matrices have rcond close to machine eps.
Accuracy of eig, backsolvers, etc, are all sensitive to condition number.
Your matrix reveals:
8.6357e-018
It's very poorly conditioned ( eig returns digital dandruff ;-) ) Use rcond
to quickly identify ill-conditioned systems.
--Don
"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in
message
news:ellieandrogerxyzzy-1012052135450001@pool1430.cvx4-bradley.dialup.earthlink.net...
| Quote: | In article <irtwxu9y.fsf@ieee.org>, Randy Yates <yates@ieee.org> wrote:
Hi Folks,
Consider the following integer matrix:
A =
1 0 -1
-1 1 0
3 -1 -2
A is a nilpotent matrix of index 3, as can be seen by evaluating A^3.
So then the only eigenvalues of A are zero.
However, Matlab's "eig" function returns:
ans =
-7.178125070607518e-006
3.589062535291640e-006 +6.216541114106220e-006i
3.589062535291640e-006 -6.216541114106220e-006i
Is there no way to get exact results for such simple matrices? Or
is there a way to establish some sort of rounding for these types
of functions?
--
% Randy Yates
----------------------------
As to the numerical computation of A's eigenvalues, in this case they
are the roots to the cubic equation
0 = det(A - lambda*eye(3)) = -lambda^3
Suppose that matlab, in the process of carrying out a complicated
algorithm for eigenvalue/eigenvector solutions makes a very small roundoff
error out in the 16-th decimal place in the process and arrives at this
equation
-lambda^3 = 3.698563363842292e-16
instead. In this case the solutions for lambda would be:
-7.178125070607523e-06
3.589062535303763e-06 + 6.216438662688082e-06i
3.589062535303763e-06 - 6.216438662688082e-06i
which are quite close to those you obtained!
The point here is that, for this particular ill-conditioned matrix, a
very small rounding error in computing the eigenvalue equation, well
within the limits that could be expected for 64-bit floating point
accuracy, will result in greatly expanded errors for the eigenvalues
themselves. Such instability is inherent in a matrix in which a
multiplicity of its eigenvalues are at, or very close to, zero.
(Remove "xyzzy" and ".invalid" to send me email.)
Roger Stafford |
|
|
| Back to top |
|
|
Mr Hrundi V Bakshi
Guest
|
| Posted:
Mon Dec 12, 2005 3:02 pm Post subject:
Re: Eigenvalue Accuracy in Matlab |
|
|
"Don Orofino" <don@mathworks.com> wrote in message
news:dnin9k$4u0$1@fred.mathworks.com...
| Quote: | Adding very little to the excellent advice given here, a practical method
for assessing "goodness" of the matrix is to compute its condition
number.
Well-conditioned matrices will return a reciprocal condition (rcond)
result
close to unity; ill-conditioned matrices have rcond close to machine eps.
Accuracy of eig, backsolvers, etc, are all sensitive to condition number.
Your matrix reveals:
rcond(A)
ans =
8.6357e-018
It's very poorly conditioned ( eig returns digital dandruff ;-) ) Use
rcond
to quickly identify ill-conditioned systems.
--Don
"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in
message
news:ellieandrogerxyzzy-1012052135450001@pool1430.cvx4-bradley.dialup.earthlink.net...
In article <irtwxu9y.fsf@ieee.org>, Randy Yates <yates@ieee.org> wrote:
Hi Folks,
Consider the following integer matrix:
A =
1 0 -1
-1 1 0
3 -1 -2
A is a nilpotent matrix of index 3, as can be seen by evaluating A^3.
So then the only eigenvalues of A are zero.
However, Matlab's "eig" function returns:
ans =
-7.178125070607518e-006
3.589062535291640e-006 +6.216541114106220e-006i
3.589062535291640e-006 -6.216541114106220e-006i
Is there no way to get exact results for such simple matrices? Or
is there a way to establish some sort of rounding for these types
of functions?
--
% Randy Yates
----------------------------
As to the numerical computation of A's eigenvalues, in this case they
are the roots to the cubic equation
0 = det(A - lambda*eye(3)) = -lambda^3
Suppose that matlab, in the process of carrying out a complicated
algorithm for eigenvalue/eigenvector solutions makes a very small
roundoff
error out in the 16-th decimal place in the process and arrives at this
equation
-lambda^3 = 3.698563363842292e-16
instead. In this case the solutions for lambda would be:
-7.178125070607523e-06
3.589062535303763e-06 + 6.216438662688082e-06i
3.589062535303763e-06 - 6.216438662688082e-06i
which are quite close to those you obtained!
The point here is that, for this particular ill-conditioned matrix, a
very small rounding error in computing the eigenvalue equation, well
within the limits that could be expected for 64-bit floating point
accuracy, will result in greatly expanded errors for the eigenvalues
themselves. Such instability is inherent in a matrix in which a
multiplicity of its eigenvalues are at, or very close to, zero.
(Remove "xyzzy" and ".invalid" to send me email.)
Roger Stafford
|
Good point. Also, a dconig for the A in question reveals that Matlab is not
to be trusted in fp arithmetic: indeed that Tr(A) == 0 is sufficient to
...., anyways, do your own homework!
--
Bye,
Hrundi V.B. |
|
| Back to top |
|
|
Peter K.
Guest
|
| Posted:
Mon Dec 12, 2005 5:16 pm Post subject:
Re: Eigenvalue Accuracy in Matlab |
|
|
"Mr Hrundi V Bakshi" <mrhrundivbakshi@hotmail.com> writes:
| Quote: | Good point. Also, a dconig for the A in question reveals that Matlab is not
to be trusted in fp arithmetic: indeed that Tr(A) == 0 is sufficient to
..., anyways, do your own homework!
|
You're just upset because you gave the wrong advice, and don't realise
that "0.0000" in matlab is not really zero. Go do your own homework!
Ciao,
Peter K. |
|
| Back to top |
|
|
Cleve Moler
Guest
|
| Posted:
Tue Dec 13, 2005 1:48 am Post subject:
Re: Eigenvalue Accuracy in Matlab |
|
|
I am afraid that Don has fallen victim to a widely believed misconception.
The condition number of a matrix has nothing to do with the sensitivity or
computed accuracy of its eigenvalues. The condition number of a matrix
measures nearness to singularity. A matrix is singular if and only if it
has an eigenvalue equal to zero. The condition number of the matrix of
eigenvectors is the crucial quantity. If a matrix fails to have a full
set of linearly independent eigenvectors, then its eigenvalues are sensitive
to perturbations, including roundoff error. Such matrices are called
"defective".
This particular example happens to be both singular and defective. If
any scalar value is added to the diagonal elements, then the matrix is no
longer singular, but that scalar value becomes the sensitive eigenvalue.
-- Cleve
moler@mathworks.com
In article <dnin9k$4u0$1@fred.mathworks.com>,
Don Orofino <don@mathworks.com> wrote:
| Quote: | Adding very little to the excellent advice given here, a practical method
for assessing "goodness" of the matrix is to compute its condition number.
Well-conditioned matrices will return a reciprocal condition (rcond) result
close to unity; ill-conditioned matrices have rcond close to machine eps.
Accuracy of eig, backsolvers, etc, are all sensitive to condition number.
Your matrix reveals:
rcond(A)
ans =
8.6357e-018
It's very poorly conditioned ( eig returns digital dandruff ;-) ) Use rcond
to quickly identify ill-conditioned systems.
--Don
"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in
message
news:ellieandrogerxyzzy-1012052135450001@pool1430.cvx4-bradley.dialup.earthlink.net...
In article <irtwxu9y.fsf@ieee.org>, Randy Yates <yates@ieee.org> wrote:
Hi Folks,
Consider the following integer matrix:
A =
1 0 -1
-1 1 0
3 -1 -2
A is a nilpotent matrix of index 3, as can be seen by evaluating A^3.
So then the only eigenvalues of A are zero.
However, Matlab's "eig" function returns:
ans =
-7.178125070607518e-006
3.589062535291640e-006 +6.216541114106220e-006i
3.589062535291640e-006 -6.216541114106220e-006i
Is there no way to get exact results for such simple matrices? Or
is there a way to establish some sort of rounding for these types
of functions?
--
% Randy Yates
----------------------------
As to the numerical computation of A's eigenvalues, in this case they
are the roots to the cubic equation
0 = det(A - lambda*eye(3)) = -lambda^3
Suppose that matlab, in the process of carrying out a complicated
algorithm for eigenvalue/eigenvector solutions makes a very small roundoff
error out in the 16-th decimal place in the process and arrives at this
equation
-lambda^3 = 3.698563363842292e-16
instead. In this case the solutions for lambda would be:
-7.178125070607523e-06
3.589062535303763e-06 + 6.216438662688082e-06i
3.589062535303763e-06 - 6.216438662688082e-06i
which are quite close to those you obtained!
The point here is that, for this particular ill-conditioned matrix, a
very small rounding error in computing the eigenvalue equation, well
within the limits that could be expected for 64-bit floating point
accuracy, will result in greatly expanded errors for the eigenvalues
themselves. Such instability is inherent in a matrix in which a
multiplicity of its eigenvalues are at, or very close to, zero.
(Remove "xyzzy" and ".invalid" to send me email.)
Roger Stafford
|
|
|
| Back to top |
|
|
Mr Hrundi V Bakshi
Guest
|
| Posted:
Tue Dec 13, 2005 9:15 am Post subject:
Re: Eigenvalue Accuracy in Matlab |
|
|
"Peter K." <p.kootsookos@remove.ieee.org> wrote in message
news:uhd9ejyc8.fsf@remove.ieee.org...
| Quote: | "Mr Hrundi V Bakshi" <mrhrundivbakshi@hotmail.com> writes:
Good point. Also, a dconig for the A in question reveals that Matlab is
not
to be trusted in fp arithmetic: indeed that Tr(A) == 0 is sufficient to
..., anyways, do your own homework!
You're just upset because you gave the wrong advice, and don't realise
that "0.0000" in matlab is not really zero. Go do your own homework!
|
I couldn't give a rat's ass what Matlab produces: it's an overpriced tool
within the budget of the naive.
For the A in question, its eigenvalues are threefold degenerately naught 0,
not "0.0000" or any othersuch boloney. Sorry that this escaped you.
--
Tsk,
Hrundi V.B. |
|
| Back to top |
|
|
|
|
|
|
FAQ
Memberlist
Register
Profile
Log in to check your private messages
Log in