gradient descent and eigenvalues (seeking references)

Main Page | Report this Page

Science Forum Index » Math - Numerical Analysis Forum » gradient descent and eigenvalues (seeking references)

Page 1 of 1

Author

Message

Guest

Posted: Thu Mar 15, 2007 5:01 pm

hello!
I am looking for references about the following fact:
For a linear equations system Ax=b with n unknowns, we have:
r[i+1]<--r[i]+a A r
where "r" is the residual and "a" the step size.
if we take for each step "i"
a = -1/lambda[i]
where "lambda[i]" is the i'th eigenvalue of A
then we reach the solution of Ax=b in at most n steps.

(the proof is quite simple, so I don't give it here :)

Thanks,
N M A

Guest

Posted: Thu Mar 15, 2007 5:21 pm

I'v forgotten to mension that lambda[i] is in C* (A is invertibe,
otherwise we do a minimisation)

N M A

paya

Posted: Thu Mar 15, 2007 6:16 pm

Guest

On Mar 15, 11:21 pm, NaitMerzoukAbdela...@gmail.com wrote:

Quote:

I'v forgotten to mension that lambda[i] is in C* (A is invertibe,
otherwise we do a minimisation)

N M A

Hello,

I don't know I understand it well. When A is a nonsingular n by n
matrix you have r_n=p(A)r_0, where r_n is the characteristic
polynomial of A. So of course p(A)=0 and hence r_n=0 implying you are
in the exact solution. I still do not know what is such a method good
for, because you must know all eigenvalues of A to compute the
solution of a linear system with this matrix A. Computing eigenvalues
is definitely much harder task than to compute the solution of a
linear system. Anyway, (almost) whichever book on optimization could
serve as a reference for descent methods. The theory around the Cayley-
Hamilton theorem (which is why this "method" works) can be found in
every good book on matrix theory.

P.J.

Guest

Posted: Thu Mar 15, 2007 8:00 pm

On 16 mar, 00:16, "paya" <pavel.jira...@gmail.com> wrote:

Quote:

On Mar 15, 11:21 pm, NaitMerzoukAbdela...@gmail.com wrote:

I'v forgotten to mension that lambda[i] is in C* (A is invertibe,
otherwise we do a minimisation)

N M A

Hello,

I don't know I understand it well. When A is a nonsingular n by n
matrix you have r_n=p(A)r_0, where r_n is the characteristic
polynomial of A. So of course p(A)=0 and hence r_n=0 implying you are
in the exact solution. I still do not know what is such a method good
for, because you must know all eigenvalues of A to compute the
solution of a linear system with this matrix A. Computing eigenvalues
is definitely much harder task than to compute the solution of a
linear system. Anyway, (almost) whichever book on optimization could
serve as a reference for descent methods. The theory around the Cayley-
Hamilton theorem (which is why this "method" works) can be found in
every good book on matrix theory.

P.J.

Thanks,
Well, i never said that this is a method, but it's sometimes hard to
find reference about something that one do not know how it's called.
I'll sleep tonight less stupid than before :)

N M A

Page 1 of 1 All times are GMT - 5 Hours The time now is Tue Oct 07, 2008 6:04 am Science Forum Index