Re: newton convergence


In article <1164779832.143502.200050@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
"vsgdp" <cloud00769@xxxxxxxxx> writes:
Hi, my book shows Newton's method can converge quadratically, but the
only example they give is a comparison between fixed point iteration
and Newton's method, and just shows that after three iterations
Newton's method is doing good while fixed point is not. How does this
show it is quadratic? More generally, how does one experimentally show
Newton's method is quadratic? What is the test?



x^* zero, assumptions f two times continuously differentiable, f'(x^*)
invertible

x^k current value
0 = f(x^*) = f(x^k) + f'(x^k)*(x^*-x^k)
+ integral_{0 to 1}(1-t)* f''(x^k+t*(x^*-xk))dt*(x^*-x^k)^2
by taylors theorem
0 = f(x^k) + f'(x^k)*(x^{k+1}-x^k) by definition

subtract
0 = f'(x^k)*(x^{k+1}-x^*) + integral......
multiply by inverse(f'(x^k)) using assumption on f'(x^*) and continuity
getting
x^{k+1}-x^*= inverse(f'(x^k)*integral.....
now taking norms, using continuity etc you get
||x^{k+1}-x^*|| <= const*||x^*-x^k||^2

a practical test is simply
||f(x^{k+1})||/||f(x^k||^2 <= const ???
but be careful: for bad x^0, it will last a while until this settles down, and
then, because of the fast convergence and the roundoff effects, the quotient
will behave chaotic finally.
hth
peter
.