Implementing Newton's Method?

Question

For an assignment, I have to implement Newton's method using Module and a For loop. So far, I have

newtMethod[guess_, fun_] :=
 ( Module[{k, x0, x1},
   x0 = guess;
   For[k = 1,
    Abs[x1 - x0] >= .0001,
    k = k + 1,
    x1 = (x0 - fun[x0]/fun'[x0]);
    If[Abs[x1 - x0] < 0, x0 = x1, x1 = x1];
    x1]; Print[x1]])

When I run this, a strange message appears.

f[x_] := Sin[E^x];
newtMethod[2.5, f]
x1$5709

If I remove the Print[x1] part of the code, there's NO output entirely. What am I doing wrong here? Is there any meaning to the weird output? I think my error has to do with what I included in the For loop and what I defined x1 to be, but I'm not sure. Any tips?

Answer 1

The main reason is that x1 is not assigned a value before entering the for loop:

newtMethod[guess_, 
  fun_] := (Module[{k, x0, x1}, x0 = guess; 
   x1 = (x0 - fun[x0]/fun'[x0]);
   For[k = 1, Abs[x1 - x0] < .0001, k = k + 1, 
    x1 = (x0 - fun[x0]/fun'[x0]);
    If[Abs[x1 - x0] < 0, x0 = x1, x1 = x1];
    x1]; Print[x1]])

f[x_] := Sin[E^x];
newtMethod[2.5, f]
FindRoot[Sin[E^x] == 0, {x, 2.5}]

Answer 2

Worth putting it out there that the For loop is not your friend. This does the same

newtonOneLine // Clear
newtonOneLine[fun_, x0_, tol_ : .0001, maxIters_ : 1000] :=
 
 Module[{fp = fun'},
  FixedPoint[# - (fun[#]/fp[#]) &, 
   x0, 
   SameTest -> (Abs[#1 - #2] < tol &)
   ]
  ]

Answer 3

Well, since interest in Newton's method never seems to fade on this site, here's a Iterator[] based approach:

Needs@"GeneralUtilities`";

(*
 * fixedPointIterator
 *   Returns x = f[x] unless x == f[x]
 *)
ClearAll[fixedPointIterator];
fixedPointIterator[f_, x0_, sameQ_ : SameQ] := 
 GeneralUtilities`NewIterator[
  fixedPointIterator,  (* name *)
  {x = x0},            (* state variables *)
  With[{xx = f[x]},    (* iterator action *)
   If[sameQ[x, xx],
    GeneralUtilities`IteratorExhausted,
    x = xx]]
  ]

newtonIterator[f_, x0_, sameQ_ : Equal] :=
 fixedPointIterator[# - f[#]/f'[#] &, x0, sameQ]

ff[x_] := Sin[E^x];
rootIt = newtonIterator[ff, 2.5];

ReadList[rootIt, 100 (* max iterations *)]
ff[%] (* check *)

(*
  {2.53316, 2.53103, 2.53102, 2.53102}
  {0.0268055, 0.0000221047, 1.94364*10^-11, -4.89859*10^-16}
*)

Note: Equal compares real numbers with tolerance (equal up to their last seven bits). SameQ compares real numbers with smaller tolerance (equal up to their last bit). Pass a custom comparator to use a different tolerance.

Also, the overhead of Iterator[] makes it fairly slow compared to, say, FixedPoint[].

Answer 4

First, let me just cleaning up the orignal code and the answer from https://mathematica.stackexchange.com/a/234969/148:

newtMethod[guess_, fun_] := 
  Module[{k, x0 = guess, x1},
  x1 = x0 - fun[x0]/fun'[x0];
  For[k = 1, Abs[x1 - x0] < .0001, k++, 
   x1 = x0 - fun[x0]/fun'[x0];
   If[Abs[x1 - x0] < 0, x0 = x1, x1 = x1]];
  x1]

This returns the most recent value of x1 rather than printing it; initializes x0 within the first argument to Module; and elides superfluous parentheses.

Note 1: For serious work, you'd want to use a fixed limit on the number of steps, either through hard-coding into the body of newtMethod or as an additional, argument to newtMethod. (For that matter, it would be more generally useful to make the tolerance .0001 another argument to newtMethod.)

Note 2: It is dangerous to use as stopping criterion just closeness of successive x-values to each other, and essential for some functions &meash; those that are fairly flat — to use in addition closeness of the value of f at the current x to the desired value 0.

Answer 5

Not at all sure what is going on here.

1. The For loop test seems backwards. In the test example the logic test is initially not true so the loop isn't executed.

2. In the If statement the test for Abs[anything]<0 doesn't seem to make sense?