CODEWITHSUNDEEP
scalanumerical-methodsnumerical
Chris Bedford
Chris Bedford

Reputation: 2702

when testing for convergence using successive approximation technique, why does this code divide by the guess twice?

While working through the coursera class on scala I ran into the code below (from another question asked here by Sudipta Deb.)

package src.com.sudipta.week2.coursera
import scala.math.abs
import scala.annotation.tailrec

object FixedPoint {
  println("Welcome to the Scala worksheet")       //> Welcome to the Scala worksheet

  val tolerance = 0.0001                          //> tolerance  : Double = 1.0E-4
  def isCloseEnough(x: Double, y: Double): Boolean = {
    abs((x - y) / x) / x < tolerance
  }                                               //> isCloseEnough: (x: Double, y: Double)Boolean
  def fixedPoint(f: Double => Double)(firstGuess: Double): Double = {
    @tailrec
    def iterate(guess: Double): Double = {
      val next = f(guess)
      if (isCloseEnough(guess, next)) next
      else iterate(next)
    }
    iterate(firstGuess)
  }                                               //> fixedPoint: (f: Double => Double)(firstGuess: Double)Double

  def myFixedPoint = fixedPoint(x => 1 + x / 2)(1)//> myFixedPoint: => Double
  myFixedPoint                                    //> res0: Double = 1.999755859375

  def squareRoot(x: Double) = fixedPoint(y => (y + x / y) / 2)(1)
                                                  //> squareRoot: (x: Double)Double
  squareRoot(2)                                   //> res1: Double = 1.4142135623746899

  def calculateAverate(f: Double => Double)(x: Double) = (x + f(x)) / 2
                                                  //> calculateAverate: (f: Double => Double)(x: Double)Double
  def myNewSquareRoot(x: Double): Double = fixedPoint(calculateAverate(y => x / y))(1)
                                                  //> myNewSquareRoot: (x: Double)Double
  myNewSquareRoot(2)                              //> res2: Double = 1.4142135623746899
}

My puzzlement concerns the isCloseEnough function.

I understand that for guesses which are large numbers, the difference between a guess and the large value that the function returns could potentially be very big all the time, so we may never converge. Conversely, if the guess is small, and if what f(x) produces is small then we will likely converge too quickly. So dividing through by the guess like this:

  def isCloseEnough(x: Double, y: Double): Boolean = {
    abs((x - y) / x) / x < tolerance
  }

makes perfect sense. (here is 'x' is the guess, and y is f_of_x.)

My question is why do why does the solution given divide by the guess TWICE ?

Wouldn't that undo all the benefits of dividing through by the guess the first time ?

As an example... let's say that my current guess and the value actually returned by the function given my current x is as shown below:

import math.abs
var guess=.0000008f
var f_of_x=.00000079999f

And lets' say my tolerance is 

var tolerance=.0001

These numbers look pretty close, and indeed, if i divide through by x ONCE, i see that the result is less than my tolerance.

( abs(guess  -  f_of_x) / guess)  
res3: Float = 1.2505552E-5

However, if i divide through by x TWICE the result is much greater than my tolerance, which would suggest we need to keep iterating.. which seems wrong since guess and observed f(x) are so close.

scala> ( abs(guess  -  f_of_x) / guess) / guess
res11: Float = 15.632331

Thanks in advance for any help you can provide.

Upvotes: 0

Views: 98

Answers (1)

Lutz Lehmann
Lutz Lehmann

Reputation: 26040

You are completely right, it does not make sense. Further, the second division is outside of the absolute value rendering the inequality true for any negative x.

Perhaps someone got confused with testing for quadratic convergence.

Upvotes: 1

Related Questions