? estimate newton step
Cheng Cosine
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?
Peter Spellucci
In article <31a630a8-aa04-4c7c...@d4g2000yqa.googlegroups.com>,
Cheng Cosine <ase...@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'.
>So we have:
>
> x(k+1) = x(k)-A'*A*x(k) = ( I-A'*A )*x(k)
>
>
> Did I do anything wrong?
peter
CCC
(Peter Spellucci) wrote:
> In article <31a630a8-aa04-4c7c-857f-30d834331...@d4g2000yqa.googlegroups.com>,
> Cheng Cosine <asec...@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
>
> - 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.
Peter Spellucci
In article <1e98c090-2e81-486d...@b9g2000yqm.googlegroups.com>,
CCC <ase...@gmail.com> writes:
>On Jul 2, 12:01=A0pm, spellu...@fb04814.mathematik.tu-darmstadt.de
>(Peter Spellucci) wrote:
>> In article <31a630a8-aa04-4c7c-857f-30d834331...@d4g2000yqa.googlegroups.=
>com>,
>> =A0Cheng Cosine <asec...@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.
>>
is this the zero of the tangent???
>>
>> > Since f(x) =3D A*x, then df(x) =3D A'.
>> wrong
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)
>> >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
peter
CCC
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.
Torsten Hennig
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.
CCC
wrote:
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.
Peter Spellucci
In article <733ee3c6-fec9-4ff0...@i6g2000yqj.googlegroups.com>,
CCC <ase...@gmail.com> writes:
>On Jul 3, 2:24=A0am, Torsten Hennig <Torsten.Hen...@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.
>>
>> (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?
>
>
>
an overdetermined system will not have a solution in general,
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
CCC
Well, what if we simply use pseudoinverse in this case?
CCC
> Well, what if we simply use pseudoinverse in this case?
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?
Chip Eastham
> 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.
regards, chip
CCC
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,
Peter Spellucci
In article <b8ad5a7e-5a68-40b0...@a7g2000yqk.googlegroups.com>,
CCC <ase...@gmail.com> writes:
>On Jul 3, 10:45=A0pm, Chip Eastham <hardm...@gmail.com> wrote:
>> On Jul 2, 12:48=A0pm, CCC <asec...@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.
>> 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
>>
>
>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,
>
>
>
>
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
MeAmI.org
Qualitative results (-> further by Musatov):
In particular, if k := max(\D(z,x) : x GV — z), then every x belongs
to \jj(z ... 6.10] Let D = (V, A) be a k-arc-strong directed
multigraph and let x,y be...Slide 1Max-Cut Max-Directed-Cut Min-
Bisection Sparsest-Cut Balanced-Separator .... technique of using
Fourier transforms to analyze [Dictator Tests] seems very
strong. ....
Test: Choose triple (x, y, z) from Dn. D = w. prob. = ). ) ) ) z. y.
x ...
6 d(G) 6 2r(G) 6 2r(D) > 1 > 2rfrom u to v is the length of a shortest
(directed) u v path. The eccentricity of a ...
The sought strong. digraph D is constructed in Fig. 1. z ...
min e(u) = e(y) = r = r(D);. max e(u) = e(z ....
x. n. = b) be a shortest oriented walk from a to b through w. and let
the node x ...
going from x. i. = w to b is. 6 d ..
Methods for statistical data analysis of multivariate observations:
For step 3a, however, the following is substituted: if x and y are
entities clustered in C]+ , but not in Cj, define d([x, y], z) = max{<f
(x, z), d(y, z)}
Directed tree-width examples:
A set S ⊆ D \ Z is Z-normal, if there is no directed walk in D \ Z
with ....
Let Y be the first position of the four cops, in ....
t > e} is the union of strong components in D \ X ...
--
Musatov
MeAmI.org
Qualitative results (-> further by Musatov):