Back to Basics: Newton-Raphson Method in Powershell

In the last post we looked at the Bisection Method to solve a simple problem, finding the square root of a real number. This week we are going to use the same exact problem, but use a better algorthim.

Newton's method (also known as the Newton–Raphson method), named after Isaac Newton and Joseph Raphson, is a method for finding successively better approximations to the roots (or zeroes) of a real-valued function. The algorithm is first in the class of Householder's methods, succeeded by Halley's method.

The Newton-Raphson method in one variable:

Given a function ƒ(x) and its derivative ƒ '(x), we begin with a first guess x₀ for a root of the function. Provided the function is reasonably well-behaved a better approximation x₁ is

Geometrically, x₁ is the intersection with the x-axis of a line tangent to f at f(x₀).

The process is repeated until a sufficiently accurate value is reached:

So basically we start with an initial guess, find the tangent where it crosses the x axis as the next guess, and iterate.

So lets define a function to find a square root using this method:

function squareRootNR {            
 Param(            
  [parameter(Position=0,             
  Mandatory=$true,             
  HelpMessage="Enter a non-negative number." )]             
  [ValidateScript({$_ -gt 0})]             
  [float]$x,            
  [parameter(Position=1,             
  Mandatory=$true,             
  HelpMessage="Enter upper bound on the relative error." )]             
  [ValidateScript({$_ -gt 0})]            
  $epsilon            
 )            
             
 $guess = $x / 2.0            
 $diff = [Math]::Pow($guess,2) - $x            
 $ctr = 1            
             
 while ([Math]::Abs($diff) -gt $epsilon -and $ctr -lt 100) {            
  $guess = $guess - $diff / (2.0 * $guess)            
  $diff = [Math]::Pow($guess,2) - $x            
  $ctr += 1            
 }            
             
 if ($ctr -ge 100) {            
  Write-Warning "Iteration count exceeded."            
 }            
             
 Write-Host "NRMethod. Number of Iterations was:", $ctr, " and Estimate is: ", $guess            
 return $guess            
}

PS H:\Development\Powershell> squareRootNr -x 9 -epsilon 0.000001            
NRMethod. Number of Iterations was: 5  and Estimate is:  3.00000000003932            
3.00000000003932     
       
Lets compare this against our last attempt using the Bisection method:
PS H:\Development\Powershell> squareRootBi -x 9 -epsilon 0.000001            
BiMethod. Number of Iterations was: 25  and Estimate is:  3.00000008940697            
3.00000008940697

As you can see we need much fewer iterations to solve the same problem.

Back to Basics: Successive Approximation in Powershell

In the last few posts we talked about exhaustive enumeration where we try all "possible" values until we find the solution. But what if there is no exact answer? What if we cannot enumerate all of the guesses? What we need is an ability to improve our guesses.

Enter Successive Approximation:

1. Start with a guess
2. Iterate
3. Improve our guess

So how do we do that? We are going to start with something called the Bisection Method. Lets see what Wikipedia has to say:

The bisection method in mathematics is a root-finding method which repeatedly bisects an interval and then selects a subinterval in which a root must lie for further processing. It is a very simple and robust method, but it is also relatively slow. Because of this, it is often used to obtain a rough approximation to a solution which is then used as a starting point for more rapidly converging methods.^[1] The method is also called the binary search method^[2] and is similar to the computer science Binary Search, where the range of possible solutions is halved each iteration.

The method is applicable when we wish to solve the equation f(x) = 0 for the real variable x, where f is a continuous function defined on an interval [a, b] and f(a) and f(b) have opposite signs. In this case aand b are said to bracket a root since, by the intermediate value theorem, the f must have at least one root in the interval (a, b).

At each step the method divides the interval in two by computing the midpoint c = (a+b) / 2 of the interval and the value of the function f(c) at that point. Unless c is itself a root (which is very unlikely, but possible) there are now two possibilities: either f(a) and f(c) have opposite signs and bracket a root, or f(c) and f(b) have opposite signs and bracket a root. The method selects the subinterval that is a bracket as a new interval to be used in the next step. In this way the interval that contains a zero of f is reduced in width by 50% at each step. The process is continued until the interval is sufficiently small.

As always lets use a problem we can all understand, finding the square root of a real number. Lets write a Bisection search function and test it.

            
function squareRootBi {            
 Param(            
  [parameter(Position=0,             
  Mandatory=$true,             
  HelpMessage="Enter a non-negative number." )]             
  [ValidateScript({$_ -gt 0})]             
  $x,            
  [parameter(Position=1,             
  Mandatory=$true,             
  HelpMessage="Enter upper bound on the relative error." )]             
  [ValidateScript({$_ -gt 0})]            
  $epsilon            
 )            
             
 $low = 0            
 $high = $x            
 $guess = ($low + $high) / 2.0            
 $ctr = 1            
             
 while ([Math]::Abs([Math]::Pow($guess,2) - $x) -gt $epsilon -and $ctr -le 100) {            
  if ([Math]::Pow($guess,2) -lt $x) {            
   $low = $guess # Set the lower bound bisection value            
  } else {            
   $high = $guess # Set the higher bound bisection value            
  }            
              
  $guess = ($low + $high) / 2.0            
  $ctr += 1            
 }            
             
 if ($ctr -ge 100) {            
  Write-Warning "Iteration count exceeded."            
 }            
             
 Write-Host "BiMethod. Number of Iterations was:", $ctr, " and Estimate is: ", $guess            
 return $guess            
}

PS H:\Development\Powershell> squareRootBi -x 9 -epsilon 0.0001            
BiMethod. Number of Iterations was: 18  and Estimate is:  2.9999885559082            
2.9999885559082

Stay tuned for the next post where we dive into a much better way to solve this, the Newton-Raphson Method.

Back to Basics: Recursion

Google recursion and besides for the joke "Did you mean: recursion" you'll find a plethora of examples, definitions, and people showing you how clever they are.

Put simply, recursion is broken down like this:

• Base case - simpliest possible solution
• Inductive step - break problem into a simplier version of the same problem with some other steps to execute.

Ok clear as mud. So as always lets take a problem and break it down.

A lot of examples show recursion using the Fibonacci sequence. However I always liked the "Blastoff!" example from How to Think Like a Computer Scientist.

Alright lets define a function:

function countdown {            
 param(            
  [int]$n            
 )
 if ($n -le 0) {            
  Write-Host "Blastoff!"            
 } else {            
  $n            
  countdown($n-1)            
 }            
}

Now lets source our function and run it:

PS H:\Development\Powershell> . .\recursion.ps1            
PS H:\Development\Powershell> countdown -n 10            
10            
9            
8            
7            
6            
5            
4            
3            
2            
1            
Blastoff!

See recursion isn't so bad after all.