Newton's Method

[Han]

Newton's Method computes the root of a function \( f(x) \) using linear approximations of \( f(x) \) via tangent lines. The formula is
\[ x_{new} = x_{old} - \frac{f(x_{old})}{f'(x_{old})} \]
We use F1 to store the formula for \( f(X) \) (note the capital letter for \( X \) ), and F0 to set up a formula for the right hand side.

CAS computations currently do not recognize local variables. And global variables are generally evaluated during parsing in a program, since the programs run in the Home view. This causes some issues with passing values and expressions to CAS commands. In the Home view, a symbolic expression is surrounded by single-quotes. So in the first example, we create a symbolic expression and "insert" other symbolic expressions (such as the derivative of a function) by using strings. In the later examples, we pass a single string to the CAS command, which parses the string as if typed from the CAS command line. Since the CAS recognizes functional algebra, we create a formula for F0 by simply operating on the functions themselves (the term id is the identity function \( id(x)=x \)) and completely ignore the dummy variables. Since our desired formula is
\[ F0(x):= x - \frac{F1(x)}{F1'(x)} \]
then the equivalent function using functional algebra is
\[ F0 := id - \frac{F1}{F1'} \]

Style 1: Initial attempt as a solution to a specific problem. The function is pre-stored into F1 in the Function App. The user then runs the command NEWT() from the command line, or from the program catalog, or from the [Toolbox] menu (press the "User" menu option).

Code:


export NEWT()
begin
  local n,xold,xnew,err;

  err:=.000001;
  n:=0;
  xnew:=2;
  xold:=xnew-2*err;
  F0:=expr("'X-F1(X)/(" + diff(F1(X),X) + ")'");

  L1:={};

  while (abs(xnew-xold)>err and n<100) do
    n:=n+1;
    L1(n):=xnew;
    xold:=xnew;
    xnew:=F0(xold);
  end;

  L1(n+1):=xnew;

end;

Syle 2: Creating a user interface The INPUT() command is used to allow the user to enter their formula, rather than having it already pre-stored in F1.

Code:


export NEWT2()
begin
  local n,xold,xnew,err,N,f;

  N:=100; err:=.00001; xnew:=1;

  if input(
    {f,xnew,err,N},
    "Newton's Method",
    {"f(X)=", "Guess=", "Error=", "Max Iter.="},
    {
      "Enter the function surrounded by single quotes",
      "Enter the initial guess",
      "Enter the tolerance",
      "Enter the maximum number of iterations"
    },
    {f,xnew,err,N}
  ) then
    F1:=f;

    CAS("F0:=id-F1/F1'");
    L1:={}; L1(1):=xnew;
    for n from 2 to N+1 do
      xold:=xnew;
      xnew:=F0(xold);
      L1(n):=xnew;
      if abs(xnew-xold)<err then break; end;
    end;
    editlist(L1);

  end;

end;

Style 3: Function-like command This style uses functional notation to send inputs to the command NEWT3(). Due to how variables are initialized, this command must be run from the command line. Otherwise, the built-in input screen will prompt for the arguments, and only accept real-valued inputs, and an algebraic expression cannot be entered for f. Usage: NEWT3("X^2-5", 2.1, .0001, 100);

Code:


export NEWT3(f,guess,tol,maxiter)
begin
  local n,xold,xnew,err,N;

  N:=maxiter;
  err:=tol;
  xnew:=guess;

    F1:=f;

    CAS("F0:=id-F1/F1'");
    L1:={}; L1(1):=xnew;
    for n from 2 to N+1 do
      xold:=xnew;
      xnew:=F0(xold);
      L1(n):=xnew;
      if abs(xnew-xold)<err then break; end;
    end;
    editlist(L1);

end;

Style 4: Mix of Style 1 and 3 Usage: Place formula into F1 in the Function App, and run the program NEWT3 either from the command line, the program catalog, or the [Toolbox] interface.

Code:


export NEWT3(guess,tol,maxiter)
begin
  local n,xold,xnew,err,N;

  N:=maxiter;
  err:=tol;
  xnew:=guess;

    CAS("F0:=id-F1/F1'");
    L1:={}; L1(1):=xnew;
    for n from 2 to N+1 do
      xold:=xnew;
      xnew:=F0(xold);
      L1(n):=xnew;
      if abs(xnew-xold)<err then break; end;
    end;
    editlist(L1);

end;

REMARKS:

A more user-friendly program would actually preserve the existing formula for F0, if it exists, and restore it so that the user does not lose their previously stored formulas after running our program. To do this, one could implement:

Code:


LOCAL oldfunc=""; // ensure string type
IFFERR
  oldfunc:=STRING(F0);
THEN
  oldfunc:="";
END;

The error trap is to account for the possibility that there may be no pre-existing F0 formula. We restore the user's old F0 formula by simply using:

Code:


F0:=oldfunc;

Fortunately, this works even if oldfunc is an empty string.