Class: Interval

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/interval.rb,
lib/interval.rb

Overview

A class representing the finite union of closed mathematical intervals in the extended real set.

The real set is extended with +Infinity and -Infinity, and the intervals are closed, i.e. they include their extrema.

Direct Known Subclasses

Multiple, Simple

Defined Under Namespace

Modules: Exception Classes: Multiple, Simple

Constant Summary collapse

NewtonOptions =

The default options for Interval#newton.

{
:maxIterations => 100,
:verbose => false }
E =

The sharp interval that includes which Euler’s constant.



PI =





The sharp interval that includes Pi.

















Class Method Summary
collapse





Instance Method Summary
collapse






Class Method Details





.[](*array) ⇒ Object







Create a closed (multi-)interval with the given numerical extrema.


Interval[3]              # In mathematical notation: [3,3]
Interval[1,2]            # In mathematical notation: [1,2]
Interval[[1,2],[3,4]]    # Union of [1,2] and [3,4]



Note that the created interval is always in canonical form:


Interval[[1,3],[2,4]]    # => Interval[1, 4]
















40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57




# File 'lib/interval.rb', line 40

def Interval.[](*array)
  union(*
    if array.empty?
      []
    elsif array.first.kind_of?(Array)
      array.select{|x| !x.empty?}.map { |x| Simple.new(*x) }
    else
      [Simple.new(*array)]
    end
  )
rescue StandardError
  unless
      array.all?{|x| Numeric === x} && array.size <= 2 ||
      array.all?{|x| Array === x && x.size <= 2 && x.all?{|c| Numeric === c}}
    raise Exception::Construction, array
  end
  raise
end












.eval(&block) ⇒ Object







Construct an interval by evaluating the given block using rounding down and rounding up modes.


Interval.eval{1/3.0}     # => Interval[0.333333333333333, 0.333333333333333]
















101
102
103
104
105




# File 'lib/interval.rb', line 101

def Interval.eval(&block)
  Simple.new(
    FPU.down {block.call},
    FPU.up   {block.call})
end












.sum(*array) ⇒ Object







Add all the arguments using Kahan’s summation formula, which provides sharper results than conventional sum.















84
85
86
87
88
89
90
91
92
93
94




# File 'lib/interval.rb', line 84

def Interval.sum(*array)
  Interval.union *array.inject([[Interval[0],Interval[0]]]) {|sc, xx|
    sc.inject([]){|a1,(s,c)|
      xx.inject(a1){|a2,x|
        y = x.dsub(c)
        t = s + y
        a2 + [[t, t.dsub(s).dsub(y)]]
      }
    }
  }.transpose.first
end












.union(*array) ⇒ Object







Create the union of an array of intervals.


Interval.union(Interval[1,2], Interval[3,4])
                         # => Interval[[1, 2], [3, 4]]
















64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80




# File 'lib/interval.rb', line 64

def Interval.union(*array)
  l = []
  array.map{|x| x.components}.flatten.sort_by{|x| x.inf}.each{|x|
    if x.sup < x.inf
      # skip it
    elsif l.empty? || x.inf > l.last.sup
      l <<= x
    elsif x.sup > l.last.sup
      l[-1] = Simple.new(l.last.inf, x.sup)
    end
  }
  if l.size == 1
    l.first
  else
    Interval::Multiple.new(l)
  end
end













Instance Method Details





#&(other) ⇒ Object







Set intersection.


Interval[1,3] & Interval[2,4]
                         # => Interval[2,3]
Interval[1,2] & Interval[3,4]
                         # => Interval[]
(Interval[1,2] & Interval[3,4]).empty?
                         # => true
















310
311
312




# File 'lib/interval.rb', line 310

def & (other)
  # implemented below
end












#*(other) ⇒ Object







Multiplication of intervals.


Interval[1,2] * Intervals[3,4]
                         # => Interval[3, 8]
Interval[2] * Interval[2]
                         # => Interval[4]



Note that


Interval[0,1]  * Interval[2,Infinity]
                         # => Interval[-Infinity, Infinity]
















297
298
299




# File 'lib/interval.rb', line 297

def * (other)
  # implemented below
end












#**(n) ⇒ Object







Integer power.


Interval[-2,2]**2        # => Interval[0, 4]
















265
266
267




# File 'lib/interval.rb', line 265

def ** (n)
  Interval.union(*map{|x| (x**n)})
end












#+(other) ⇒ Object







Sum of intervals.


Interval[1,2] + Interval[3,4]
                         # => Interval[4, 6]
Interval[2] + Interval[2]
                         # => Interval[4]



Note that


Interval[-Infinity] + Interval[Infinity]
                         # => Interval[-Infinity, Infinity]
















281
282
283




# File 'lib/interval.rb', line 281

def + (other)
  # implemented below
end












#-(other) ⇒ Object







Subtraction: A - B is equivalent to A + (-B).















322
323
324




# File 'lib/interval.rb', line 322

def - (other)
  self + (-other)
end












#-@ ⇒ Object







Unitary minus: applied to I returns -I.


-Interval[1,2]           # => Interval[-2, -1]
















181
182
183




# File 'lib/interval.rb', line 181

def -@
  self.class.new map{|x| -x}.reverse
end












#/(other) ⇒ Object







Division: A / B is equivalent to A * (B ** -1).















327
328
329




# File 'lib/interval.rb', line 327

def / (other)
  self * other.to_interval.inverse
end












#==(other) ⇒ Object







Two intervals are equal if and only if they have equal components.


Interval[[1,3],[2,4]] == Interval[1,4]
                         # => true
















153
154
155




# File 'lib/interval.rb', line 153

def == (other)
  self.class === other && self.components == other.components
end












#atan ⇒ Object







The arc tangent function.


4 * Interval[1].atan     # => Interval::PI
















216
217
218




# File 'lib/interval.rb', line 216

def atan
  # implemented below
end












#coerce(other) ⇒ Object







Make other into an interval.















173
174
175




# File 'lib/interval.rb', line 173

def coerce (other)
  [other.to_interval, self]
end












#construction ⇒ Object







Returns a list of the parameters that can be used to reconstruct the interval.


a = Interval[1,2]        # => Interval[1, 2]
b = a.construction       # => [1, 2]
Interval[*b] == a        # => true
















114
115
116




# File 'lib/interval.rb', line 114

def construction
  map{|x| x.extrema.uniq}
end












#cos ⇒ Object







The cosine function.


(Interval::PI/3).cos     # => Interval[0.5, 0.5]
















224
225
226




# File 'lib/interval.rb', line 224

def cos
  # implemented below
end












#cosh ⇒ Object







Hyperbolic cosine.















245
246
247




# File 'lib/interval.rb', line 245

def cosh
  # implemented below
end












#degenerate? ⇒ Boolean







An interval is degenerate if each component includes exactly one element.


Interval









Returns:


    

  • 
(Boolean)

    • 










361
362
363




# File 'lib/interval.rb', line 361

def degenerate?
  all? {|x| x.degenerate?}
end












#empty? ⇒ Boolean







True if the interval has no elements.








Returns:


    

  • 
(Boolean)

    • 










341
342
343




# File 'lib/interval.rb', line 341

def empty?
  components.empty?
end












#exp ⇒ Object







The exponential function.


Interval[[-Infinity,0],[1,Infinity]].exp
                         # => Interval[[0,1],[Math::E,Infinity]]
















199
200
201




# File 'lib/interval.rb', line 199

def exp
  # implemented below
end












#hull ⇒ Object







The hull is the smallest simple interval containing the interval itself.


Interval[[1,2],[3,4]]    # => Interval[1, 4]
















369
370
371
372
373
374
375




# File 'lib/interval.rb', line 369

def hull
  if empty?
    Interval[]
  else
    Interval[components.first.inf, components.last.sup]
  end
end












#include?(x) ⇒ Boolean







True if a point x belongs to the interval.


Interval[[1,2],[3,4]].include?(1.5)
                         # => true
Interval[[1,2],[3,4]].include?(2.5)
                         # => false









Returns:


    

  • 
(Boolean)

    • 










163
164
165




# File 'lib/interval.rb', line 163

def include?(x)
  any?{|i| i.include?(x)}
end












#inspect ⇒ Object







Overrides Object#inspect, returning a string representation of the interval.


Interval[1,2].inspect    #= > "Interval[1, 2]"
















140
141
142




# File 'lib/interval.rb', line 140

def inspect
  "Interval" + construction.inspect
end












#inverse ⇒ Object







The inverse of the interval, I.inverse is the same as 1/I.


Interval[1,2].inverse    # => Interval[0.5, 1.0]
Interval[-2,4].inverse   # => Interval[[-Infinity, -0.5], [0.25, Infinity]]
















190
191
192




# File 'lib/interval.rb', line 190

def inverse
  # implemented below
end












#log ⇒ Object







The logarithm function.


Interval[1,Math::E].log  # Interval[0,1]
Interval[-1,+1].log      # Interval[-Infinity,0]
















208
209
210




# File 'lib/interval.rb', line 208

def log
  # implemented below
end












#newton(f, fp, opts = {}) ⇒ Object







Solve a non-linear equation using the Newton-Raphson method, finding all solutions in a in interval.


For instance, to solve


x**3 == x



we rewrite it first in the form


x**3 - x == 0



The left-hand side of this equation has derivative


3* x**2 - 1



To find all solutions in [-100,100] we call


Interval[-100,100].newton(proc {|x| x**3 - x}, proc {|x| 3* x**2 - 1})
                         # => Interval[[-1.0], [-0.0], [1.0]]



a sharp result showing the three roots -1, 0 and +1.















396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447




# File 'lib/interval.rb', line 396

def newton(f, fp, opts = {})
  effectiveOpts = NewtonOptions.dup.update(opts)
  verbose = effectiveOpts[:verbose]
  puts "Starting on #{self}" if verbose
  step = proc {|w,ww| (w - f.call(Interval[w]) / fp.call(ww) ) & ww}
  self.map{|xx|
    effectiveOpts[:maxIterations].times{
      previous = xx;
      xx = step.call(xx.midpoint,xx)
      if previous == xx
        if xx.sharp?
          puts "Sharp fixed point #{xx}" if verbose
          xx = Interval[xx.extrema.select {|x| f.call(Interval[x]).include?(0)}]
          break
        end
        nonminimal_extrema = xx.extrema.reject {|x| f.call(Interval[x]).include?(0)}
        if nonminimal_extrema == [] then
          puts "Unsharp fixed point #{xx}" if verbose
          break
        end
        if nonminimal_extrema.each {|x|
            yy = step.call(x,xx)
            if yy != xx
              xx = yy;
              break
            end
          }
          xx = Interval[
            if nonminimal_extrema.include?(xx.inf)
              xx.inf + xx.inf.ulp
            else
              xx.inf
            end,
            if nonminimal_extrema.include?(xx.sup)
              xx.sup - xx.sup.ulp
            else
              xx.sup
            end]
        end
      end
      if xx.empty?
        puts "No solution" if verbose
        break
      elsif ! xx.simple?
        puts "Branch splitting" if verbose
        xx = xx.newton(f,fp,opts)
        break
      end
    } && verbose && puts("Failed convergence #{effectiveOpts[:maxIterations]}")
    xx
  }. inject{|a,x| a |=x}
end












#op ⇒ Object







Implement binary operations: Sum (+), Multiplication (*) and Intersection (&)















255
256
257
258
259




# File 'lib/interval.rb', line 255

[:inverse, :exp, :log, :atan, :cos, :sin, :tan, :cosh, :sinh].each {|op|
  define_method(op) {
    Interval.union(*map{|x| x.send(op)})
  }
}












#sharp? ⇒ Boolean







An interval is sharp if each pair of extrema differ by at most a bit in the least significant position.


Interval[3].sharp?       # => true
Interval[1,2].sharp?     # => false
(1/Interval[3.0]).sharp? # => true
Interval[[1],[2]].sharp? # => true









Returns:


    

  • 
(Boolean)

    • 










353
354
355




# File 'lib/interval.rb', line 353

def sharp?
  all? {|x| x.sharp?}
end












#simple? ⇒ Boolean







True if the interval is simple, i.e., if it has only one connected component.


Interval[1,2].simple?    # => true
Interval[[1,2],[3,4]].simple?
                         # => false



If simple? is true, then the object is in fact of class Interval::Simple.


Interval[1,2].class      # => Interval::Simple
Interval[1,2].midpoint   # => 1.5
Interval[[1,2],[3,4]].midpoint
                         # raises a NoMethodError exception









Returns:


    

  • 
(Boolean)

    • 










132
133
134




# File 'lib/interval.rb', line 132

def simple?
  false
end












#sin ⇒ Object







The sine function.


(Interval::PI/6).sin     # => Interval[0.5, 0.5]
















232
233
234




# File 'lib/interval.rb', line 232

def sin
  # implemented below
end












#sinh ⇒ Object







Hyperbolic sine.















250
251
252




# File 'lib/interval.rb', line 250

def sinh
  # implemented below
end












#tan ⇒ Object







The tangent function.


The cosine function.     # => Interval[1.0, 1.0]
















240
241
242




# File 'lib/interval.rb', line 240

def tan
  # implemented below
end












#to_interval ⇒ Object







Return itself.















168
169
170




# File 'lib/interval.rb', line 168

def to_interval
  self
end












#to_s ⇒ Object







Overrides Object#to_s and uses #inspect to create a string representation of the interval.















145
146
147




# File 'lib/interval.rb', line 145

def to_s
  inspect
end












#|(other) ⇒ Object







Set union.


Interval[1,3] | Interval[2,4]
                         # => Interval[1, 4]
















336
337
338




# File 'lib/interval.rb', line 336

def | (other)
  Interval.union(other.to_interval, self)
end