1
$\begingroup$

I am trying to determine for which initial values Newton's approximation of specific functions (EX: f(x)=x^2 -1)converge and to what numbers it will converge to. *Where Newton's approximations are x[n+1] = x[n] - ( f(x[n]) / f'(x[n]) )

Since Newton's approximations are iterated functions, I am confused on if I need to make this a recurrence equation and then just alter the x[0] term (which would represent the initial value. Even to enter the recurrence equation, I've tried solving for a closed formula which hasn't been effective.

In addition, I don't know if determining if it converges (and to what number) should simply require the Limit function or something more complex. If it does just require the limit function, would x be approaching the initial value?

Instead, I've also thought about using "Table" simply to display a specific number of iterations and determine convergence myself.

Below is some of the code I have tried.

F[x_] := x^2 - 1
Limit[x - F[x]/D[F[x]], x -> 1]

RSolve[x[n + 1] == x[n] - ((x[n])^2 - 1)/(2*x[n]), x[n], n]
Limit[-I Cot[2^n C[1]], x -> 0]

Table[Limit[x - F[x]/D[F[x]], x -> 1], {20}]
$\endgroup$
  • 1
    $\begingroup$ Given a function and a starting point, one way to go about certifying convergence is via Smale et al's "alpha theory". Roughly, one shows the point is in a region wherein application of Newton's method is guaranteed to be a contraction operator. A web search should bring up a number of relevant hits. $\endgroup$ – Daniel Lichtblau Mar 17 '15 at 14:45
1
$\begingroup$
f[x_] := x^2 - 1;
df = D[f[x], x];
lastX = .7;(*guess*)
k = 1;(*counter,just in case*)
err = Infinity;
SetOptions[$FrontEnd, PrintPrecision -> 16]
r = First@Last@Reap@While[err > 0.000001 && k < 10,
      Sow[{k, err, lastX}];
      currentX = lastX - f[lastX]/(df /. x -> lastX);
      err = Abs[f[currentX] - f[lastX]];
      lastX = currentX;
      k++];
Grid[Join[{{"k", "error", "current x"}}, r], Frame -> All]

Mathematica graphics

 FindRoot[x^2 - 1 == 0, {x, .7}]

Mathematica graphics

$\endgroup$
  • $\begingroup$ so here you have a loop starting at 0.7 and converging to 1, through 10 iterations. this indicates that 0.7 converges. and then to determine specifically to what 0.7 converges to, you use the FindRoot function? $\endgroup$ – mentorship Mar 17 '15 at 16:31
  • $\begingroup$ Also - how could I make it so that it displayed the all "currentX" for each k (for initial values that oscillate for example), besides simply using multiple codes with k<1, k<2, etc. $\endgroup$ – mentorship Mar 18 '15 at 3:13
  • $\begingroup$ @mentorship updated. The loop does not run for 10 times. This is an upper limit only. It is an && condition $\endgroup$ – Nasser Mar 18 '15 at 3:27
  • $\begingroup$ oh! this makes much more sense thank you! $\endgroup$ – mentorship Mar 18 '15 at 4:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.