 |
|
| Science Forum Index » Math - Numerical Analysis Forum » ? estimate newton step... |
|
Page 1 of 1 |
|
| Author |
Message |
| Cheng Cosine... |
 Posted: Thu Jul 02, 2009 5:51 am |
|
|
|
Guest
|
Hi:
Newton method is an old and famous algorithm to solve equations. But
in general we do not have an estimate on the steps we will get the
convergent result. Nevertheless, will we be able to estimate this in
the case that the problem at hand is linear or only 2nd order?
At the 1st though it seems that we can finish iteration in 1 step if
f is s linear function.
Use Newton's method to solve f(x) = 0 -> x(k+1) = x(k)-df(k)'*f(k)
Since f(x) = A*x, then df(x) = A'. So we have:
x(k+1) = x(k)-A'*A*x(k) = ( I-A'*A )*x(k)
Don't see how we will go.
Did I do anything wrong? |
|
|
| Back to top |
|
|
|
| Peter Spellucci... |
| Posted: Thu Jul 02, 2009 6:01 am |
|
|
|
Guest
|
In article <31a630a8-aa04-4c7c-857f-30d834331162 at (no spam) d4g2000yqa.googlegroups.com>,
Cheng Cosine <asecant at (no spam) gmail.com> writes:
[quote:4ae79c9405]Hi:
Newton method is an old and famous algorithm to solve equations. But
in general we do not have an estimate on the steps we will get the
convergent result. Nevertheless, will we be able to estimate this in
the case that the problem at hand is linear or only 2nd order?
At the 1st though it seems that we can finish iteration in 1 step if
f is s linear function.
Use Newton's method to solve f(x) = 0 -> x(k+1) = x(k)-df(k)'*f(k)
Since f(x) = A*x, then df(x) = A'.
wrong
So we have:
x(k+1) = x(k)-A'*A*x(k) = ( I-A'*A )*x(k)
even more wrong
Don't see how we will go.
Did I do anything wrong?
yes , almost anything which could be done wrong[/quote:4ae79c9405]
peter |
|
|
| Back to top |
|
|
|
| CCC... |
| Posted: Thu Jul 02, 2009 6:48 am |
|
|
|
Guest
|
On Jul 2, 12:01 pm, spellu... at (no spam) fb04814.mathematik.tu-darmstadt.de
(Peter Spellucci) wrote:
[quote:60ebe29a11]In article <31a630a8-aa04-4c7c-857f-30d834331... at (no spam) d4g2000yqa.googlegroups.com>,
Cheng Cosine <asec... at (no spam) gmail.com> writes:
Hi:
Newton method is an old and famous algorithm to solve equations. But
in general we do not have an estimate on the steps we will get the
convergent result. Nevertheless, will we be able to estimate this in
the case that the problem at hand is linear or only 2nd order?
At the 1st though it seems that we can finish iteration in 1 step if
f is s linear function.
Use Newton's method to solve f(x) = 0 -> x(k+1) = x(k)-df(k)'*f(k)
Since f(x) = A*x, then df(x) = A'.
wrong
So we have:
x(k+1) = x(k)-A'*A*x(k) = ( I-A'*A )*x(k)
even more wrong
Don't see how we will go.
Did I do anything wrong?
yes , almost anything which could be done wrong
peter- Hide quoted text -
- Show quoted text -
[/quote:60ebe29a11]
Well, where did I do wrong and how to fix it then?
The very first question is: can we always get correct result using
Newton method IF the function is linear. |
|
|
| Back to top |
|
|
|
| Peter Spellucci... |
| Posted: Thu Jul 02, 2009 9:09 am |
|
|
|
Guest
|
In article <1e98c090-2e81-486d-8615-a93ab70d4350 at (no spam) b9g2000yqm.googlegroups.com>,
CCC <asecant at (no spam) gmail.com> writes:
[quote:c4856bb865]On Jul 2, 12:01=A0pm, spellu... at (no spam) fb04814.mathematik.tu-darmstadt.de
(Peter Spellucci) wrote:
In article <31a630a8-aa04-4c7c-857f-30d834331... at (no spam) d4g2000yqa.googlegroups.=
com>,
=A0Cheng Cosine <asec... at (no spam) gmail.com> writes:
Hi:
Newton method is an old and famous algorithm to solve equations. But
in general we do not have an estimate on the steps we will get the
convergent result. Nevertheless, will we be able to estimate this in
the case that the problem at hand is linear or only 2nd order?
At the 1st though it seems that we can finish iteration in 1 step if
f is s linear function.
Use Newton's method to solve f(x) =3D 0 -> x(k+1) =3D x(k)-df(k)'*f(k)
[/quote:c4856bb865]
is this the zero of the tangent???
[quote:c4856bb865]
Since f(x) =3D A*x, then df(x) =3D A'.
wrong
[/quote:c4856bb865]
A' : you mean the transpose: no !
f is a vector function with components f(1), f(n)
f(i) = sum a(i,j)*x(j) - b(i)
then
df(i)/dx(j) = a(i,j)
[quote:c4856bb865]So we have:
=A0x(k+1) =3D x(k)-A'*A*x(k) =3D ( I-A'*A )*x(k)
even more wrong
Don't see how we will go.
=A0Did I do anything wrong?
yes , almost anything which could be done wrong
peter- Hide quoted text -
- Show quoted text -
Well, where did I do wrong and how to fix it then?
The very first question is: can we always get correct result using
Newton method IF the function is linear.
hth[/quote:c4856bb865]
peter |
|
|
| Back to top |
|
|
|
| CCC... |
| Posted: Thu Jul 02, 2009 10:23 am |
|
|
|
Guest
|
f = A*x, df = A
Newton algorithm:
x(k+1) = x(k)-df'*f = x(k)-A'*A*x(k)
The remaining question is that can we estimate the steps required to
converge in advance. |
|
|
| Back to top |
|
|
|
| Torsten Hennig... |
| Posted: Thu Jul 02, 2009 8:24 pm |
|
|
|
Guest
|
[quote:03e3d4781d]
f = A*x, df = A
Newton algorithm:
x(k+1) = x(k)-df'*f = x(k)-A'*A*x(k)
The remaining question is that can we estimate the
steps required to
converge in advance.
[/quote:03e3d4781d]
f(x) = A*x
(df/dx)^(-1) = A^(-1)
Newton's algorithm:
x_1 = x_0 - A^(-1)*A*x_0 = 0
Since A*x = 0 has solution x=0, convergence to
the correct solution is achieved in one step.
Best wishes
Torsten. |
|
|
| Back to top |
|
|
|
| CCC... |
| Posted: Fri Jul 03, 2009 2:54 am |
|
|
|
Guest
|
On Jul 3, 2:24 am, Torsten Hennig <Torsten.Hen... at (no spam) umsicht.fhg.de>
wrote:
[quote:b6e6f5d096]f = A*x, df = A
Newton algorithm:
x(k+1) = x(k)-df'*f = x(k)-A'*A*x(k)
The remaining question is that can we estimate the
steps required to
converge in advance.
f(x) = A*x
(df/dx)^(-1) = A^(-1)
Newton's algorithm:
x_1 = x_0 - A^(-1)*A*x_0 = 0
Since A*x = 0 has solution x=0, convergence to
the correct solution is achieved in one step.
[/quote:b6e6f5d096]
Thank you Torsten :)
How about in the case that A is not a square matrix?
In that case we do not have x_0 - inv(A)*A*x_0 = x_0 - x_0 = 0. |
|
|
| Back to top |
|
|
|
| Peter Spellucci... |
| Posted: Fri Jul 03, 2009 3:18 am |
|
|
|
Guest
|
In article <733ee3c6-fec9-4ff0-bce2-3b485e6b682f at (no spam) i6g2000yqj.googlegroups.com>,
CCC <asecant at (no spam) gmail.com> writes:
[quote:230644ac8a]On Jul 3, 2:24=A0am, Torsten Hennig <Torsten.Hen... at (no spam) umsicht.fhg.de
wrote:
f =3D A*x, df =3D A
Newton algorithm:
=A0x(k+1) =3D x(k)-df'*f =3D x(k)-A'*A*x(k)
The remaining question is that can we estimate the
steps required to
converge in advance.
f(x) =3D A*x
(df/dx)^(-1) =3D A^(-1)
Newton's algorithm:
x_1 =3D x_0 - A^(-1)*A*x_0 =3D 0
Since A*x =3D 0 has solution x=3D0, convergence to
the correct solution is achieved in one step.
Thank you Torsten :)
How about in the case that A is not a square matrix?
In that case we do not have x_0 - inv(A)*A*x_0 =3D x_0 - x_0 =3D 0.
an overdetermined system will not have a solution in general,[/quote:230644ac8a]
neither in the linear nor in the nonlinear case.
then you will have the problem
||F(x)||_2^2 = min_x
a (non)linear least squares problem.
Newton's method turns into Gauss-Newton-method:
given x_k either solve
||J_F(x_k) d_k + F(x_k)||_2^2 = min_d_k subject to ||D_k|| <= \delta_k
and adapt \delta_k if necessary such that
0 < rho <= (||F(x_k)||_2^2 - ||F(x_k+d_k)||_2^2)/(||F(x_k)||_2^2-||||J_F(x_k) d_k + F(x_k)||_2^2)
(i.e. use the trust region method)
or
solve
||J_F(x_k) d_k + F(x_k)||_2^2 = min_d_k (no constraints)
and then compute the stepsize \sigma_k such that
||F(x_k)||_2^2 - ||F(x_k+\sigma_k d_k)||_2^2 >= \rho \sigma_k |F(x_k)^T J_F(x_k)^Td_k |
the stepsize approach.
This asumes thta the Jacobian of F J_F is of full rank. More tricks are required
should J_F be rank deficient.
hth
peter |
|
|
| Back to top |
|
|
|
| CCC... |
| Posted: Fri Jul 03, 2009 4:05 am |
|
|
|
Guest
|
| Well, what if we simply use pseudoinverse in this case? |
|
|
| Back to top |
|
|
|
| CCC... |
| Posted: Fri Jul 03, 2009 4:10 am |
|
|
|
Guest
|
On Jul 3, 10:05 am, CCC <asec... at (no spam) gmail.com> wrote:
[quote:a3edaed8ca]Well, what if we simply use pseudoinverse in this case?
[/quote:a3edaed8ca]
That is, we know in advanced that we do not have a solution to the
original
problem when A is a rectangular matrix. So we re-define a problem that
has
a solution. We add an additional constraint by minimizing the norm of
the
best approximate solution we are to seek. Then we "always" have a
solution?
I mean, will it always converge in this case when we still use Newton
algorithm? |
|
|
| Back to top |
|
|
|
| Chip Eastham... |
| Posted: Fri Jul 03, 2009 4:45 pm |
|
|
|
Guest
|
On Jul 2, 12:48 pm, CCC <asec... at (no spam) gmail.com> wrote:
[quote:da2fe2a7eb]The very first question is: can we always get correct result using
Newton method IF the function is linear.
[/quote:da2fe2a7eb]
Yes, but there's nothing magic going on here.
If the function is linear, f(x) = Ax, then
the "gradient" of f is A, and the Newton step
will be to "solve" a linear system having the
coefficient matrix A, which is tantamount to
solving the original equation f(x) = c.
regards, chip |
|
|
| Back to top |
|
|
|
| CCC... |
| Posted: Fri Jul 03, 2009 5:15 pm |
|
|
|
Guest
|
On Jul 3, 10:45 pm, Chip Eastham <hardm... at (no spam) gmail.com> wrote:
[quote:82428de598]On Jul 2, 12:48 pm, CCC <asec... at (no spam) gmail.com> wrote:
The very first question is: can we always get correct result using
Newton method IF the function is linear.
Yes, but there's nothing magic going on here.
If the function is linear, f(x) = Ax, then
the "gradient" of f is A, and the Newton step
will be to "solve" a linear system having the
coefficient matrix A, which is tantamount to
solving the original equation f(x) = c.
[/quote:82428de598]
Ah, indeed, Chip:
Understadning enough linear problem, let's move the nonlienar one.
Now, let's ask this question: do we have a way to estimate the maximum
iterations for a given nonlinear function solved by Newton's method?
What are the properties of a nonlinear that can help us to ensure the
convergence of Newton's method?
A very first one I can think of is a simple 2nd order function. In
this
case, we are sure that using Newton's method will converge. But can we
estimate the max iterations, if yes how?
Thanks, |
|
|
| Back to top |
|
|
|
| Peter Spellucci... |
| Posted: Sat Jul 04, 2009 2:10 am |
|
|
|
Guest
|
In article <b8ad5a7e-5a68-40b0-acb0-ace2415ab6c6 at (no spam) a7g2000yqk.googlegroups.com>,
CCC <asecant at (no spam) gmail.com> writes:
[quote:d6c258303c]On Jul 3, 10:45=A0pm, Chip Eastham <hardm... at (no spam) gmail.com> wrote:
On Jul 2, 12:48=A0pm, CCC <asec... at (no spam) gmail.com> wrote:
The very first question is: can we always get correct result using
Newton method IF the function is linear.
Yes, but there's nothing magic going on here.
If the function is linear, f(x) =3D Ax, then
the "gradient" of f is A, and the Newton step
will be to "solve" a linear system having the
coefficient matrix A, which is tantamount to
solving the original equation f(x) =3D c.
Ah, indeed, Chip:
Understadning enough linear problem, let's move the nonlienar one.
Now, let's ask this question: do we have a way to estimate the maximum
iterations for a given nonlinear function solved by Newton's method?
What are the properties of a nonlinear that can help us to ensure the
convergence of Newton's method?
A very first one I can think of is a simple 2nd order function. In
this
case, we are sure that using Newton's method will converge. But can we
estimate the max iterations, if yes how?
Thanks,
[/quote:d6c258303c]
you had several questions:
what if we use the pseudoinverse?
the pseudoinverse is in use if you take the Gauss/Newton resp. Levenberg/Marquardt
there is _no_ convergence theory for a Newton method (for a problem
R^n->R^n with a zero solution) other than by Ben Israel but this one had
the unrealistic assumption that the rank of the Jacobian is constant in a
complete neighborhood of the solution. And this is a result of the type
"provided that x0 is sufficiently near to the solution"
minimizing the sum of squares with a norm constraint on x has of course always
a solution but this has nothing to do with guarantee of convergence of the
methods mentioned.
For Gauss-Newton resp. Levenberg-Marquardt there is a complete
convergence theory which guarantees convergence to _one of the possibly many_
stationary points.
look at the classic text by dennis and schnabel: "numerical methods for
unconstrained minimization" (SIAM reprint)
for the ordinary Newton's method there is a complexity result which says that
this is proportional to the reciprocal of the distance of the initial point
to the next point where the Jacobian is rank deficient -- but nothing
quantitiative. (-> results by Smale)
hth
peter |
|
|
| Back to top |
|
|
|
|
|
All times are GMT - 5 Hours
The time now is Fri Dec 11, 2009 7:47 am
|
|