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.