On 2006-07-15 17:04:38 -0300, Greg Steele <gregsteele@speakeasy.net> said:

> gokul_s1 wrote:
>> Thanks for your response.
>> I guess the answer does lie in the condition number of the matrix.
>> Consider this matrix [1 10 10
>> 0 1 10;
>> 0 0 1 ]
>> This matrix has all eigen values equal to 1...but it is still ill
>> conditioned. It is quite interesting to know that the eigenvalues play no
>> role in determining the stability of the inverse!
>>
>>
>>
>>
>
> I would argue that eigenvalues do play a role. The eigenvalues of
> interest are not those of the original matrix A, but of A'A. The
> condition number of A can be defined as
>
> max Eig(A'A)/ min Eig(A'A)

The matrix is not symmetric so the eigensystem is more complicated.
The eigenvectors are deficient.
When the matix is symmetric, or Herrmitian for complex values, then the
eigenvectors are guaranteed to be well behaved.
Looking at the singular values avoids this complication. It is the same
information that you get fron A'A and AA'.

Reply by Greg Steele●July 15, 20062006-07-15

gokul_s1 wrote:

> Thanks for your response.
>
> I guess the answer does lie in the condition number of the matrix.
> Consider this matrix [1 10 10
> 0 1 10;
> 0 0 1 ]
> This matrix has all eigen values equal to 1...but it is still ill
> conditioned. It is quite interesting to know that the eigenvalues play no
> role in determining the stability of the inverse!
>
>
>
>

I would argue that eigenvalues do play a role. The eigenvalues of
interest are not those of the original matrix A, but of A'A. The
condition number of A can be defined as
max Eig(A'A)/ min Eig(A'A)

Reply by Jerry Avins●July 12, 20062006-07-12

gokul_s1 wrote:

> Thanks for your response.
>
> I guess the answer does lie in the condition number of the matrix.
> Consider this matrix [1 10 10
> 0 1 10;
> 0 0 1 ]
> This matrix ...

Your tabs don't act like my tabs. Please use spaces.
Jerry
--
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

Reply by gokul_s1●July 12, 20062006-07-12

Thanks for your response.
I guess the answer does lie in the condition number of the matrix.
Consider this matrix [1 10 10
0 1 10;
0 0 1 ]
This matrix has all eigen values equal to 1...but it is still ill
conditioned. It is quite interesting to know that the eigenvalues play no
role in determining the stability of the inverse!

Reply by Clay●July 12, 20062006-07-12

gokul_s1 wrote:

> Why is the inversion of a Toeplitz system Ax=b, where A is a Toeplitz
> matrix, ill-posed even when A is not rank deficient?. If A is full rank,
> shouldnt the system have a unique solution and not be affected by small
> noise perturbations?. How can one relate the ill-posedness of
> deconvolution problems to the behaviour of the Toeplitz Matrix.
>
> Would appreciate a reply
>
> Thanks
> -Goks

Hello Goks,
To follow up on what Gordon said, you may wish to look up condition
numbers as applied to matrices. And you will find how it is very easy
to create a matrix that is numerically very difficult t work with.
A good book on numerical analysis that I would recommend is Forman S.
Acton's "Numerical Methods That Work." He offers an interlude in the
middle of the book about what to not compute. And gives a lot of
examples of things are ill conditioned. Try looking up Hilbert
Matrices. It is easy to set up a system where Hx=b and H is a Hilbert
matrix and ith element of b is chosen to be the sum the elements on row
i. The solution is simply x=(1,1,1,1,1,1,...,1). But try this on a
computer and see how close you get!
IHTH,
Clay S. Turner

Reply by Gordon Sande●July 12, 20062006-07-12

On 2006-07-12 11:16:05 -0300, "gokul_s1" <swamygok@msu.edu> said:

> Why is the inversion of a Toeplitz system Ax=b, where A is a Toeplitz
> matrix, ill-posed even when A is not rank deficient?. If A is full rank,
> shouldnt the system have a unique solution and not be affected by small
> noise perturbations?. How can one relate the ill-posedness of
> deconvolution problems to the behaviour of the Toeplitz Matrix.
>
> Would appreciate a reply
>
> Thanks
> -Goks

Think about the inverse of
1 0 0
0 1 0
0 0 10^-10
which is of full rank and provides unique solutions.
Is it prone to amplify small errors in the third component?
Full rank, and thus uniqueness, does not mean that the
inverse will be small. Large values in the inverse will
tend to amplify small perturbations.
Try looking at the values in the inverse with the eigenvalues
as a quick way to get there. One will see that Toeplitz matrices
can be ill conditioned.

Reply by gokul_s1●July 12, 20062006-07-12

Why is the inversion of a Toeplitz system Ax=b, where A is a Toeplitz
matrix, ill-posed even when A is not rank deficient?. If A is full rank,
shouldnt the system have a unique solution and not be affected by small
noise perturbations?. How can one relate the ill-posedness of
deconvolution problems to the behaviour of the Toeplitz Matrix.
Would appreciate a reply
Thanks
-Goks