Essays/Bisection Method

From J Wiki
Jump to: navigation, search

The bisection method is used to find approximations to a root of a continuous real function.


Introduction

   B=: 1 : '(}.~ _1 ^ ~:/@:*@:u@:}:) @ ({.,(+/%#),}.)'

   (_2 + *:) B 0 2
1 2
   (_2 + *:) B^:2 ]0 2
1 1.5
   (_2 + *:) B^:3 ]0 2
1.25 1.5
   (_2 + *:) B^:_ ]0 2
1.41421 1.41421

   2 - *: (_2 + *:) B^:_ ]0 2
1.28564e_13 _3.24185e_14

B is an adverb where u B is one iteration for finding a root of u , whence u B^:n x is the result of n iterations on initial estimates x and u B^:_ x is the limit (to within the comparison tolerance) of the iterations.

The initial estimates are two numbers (x0,x1) that bracket a root; that is, u x0 and u x1 must have different signs. (Unless both signs are 0 whence both x0 and x1 are roots.) In an iteration, the new estimates obtain by replacing with the mean the estimate whose u-value has the same sign as the u-value of the mean.

Convergents

The convergents (results of iterations) obtain with an appropriate argument to the power operator ^: .

   (_2 + *:) B^:(i.8) 0 2
      0       2
      1       2
      1     1.5
   1.25     1.5
  1.375     1.5
  1.375  1.4375
1.40625  1.4375
1.40625 1.42188

   t=: (_2 + *:) B^:a: 0 2
   $ t
45 2

   2 - *: _5]\ {."1 t
          2           1           1      0.4375    0.109375
   0.109375   0.0224609   0.0224609 0.000427246 0.000427246
0.000427246 0.000427246 0.000427246 0.000427246  8.20011e_5
 8.20011e_5  8.20011e_5  3.88434e_5  1.72643e_5  6.47477e_6
 1.07998e_6  1.07998e_6  1.07998e_6  4.05632e_7  6.84571e_8
 6.84571e_8  6.84571e_8  2.63102e_8  5.23681e_9  5.23681e_9
 5.23681e_9  2.60263e_9  1.28554e_9    6.27e_10 2.97728e_10
1.33092e_10 5.07734e_11 9.61431e_12 9.61431e_12 9.61431e_12
4.46954e_12 1.89693e_12 6.10845e_13 6.10845e_13 2.89324e_13

Rational Numbers

If u uses only rational operations, then the iteration produces rational results on rational initial estimates. In such cases use of _ or a: in ^: should be avoided as the function may not have a rational root.

   (_2 + *:) B^:(5*i.10) 0 2x
                            0                           2
                         11r8                       23r16
                      181r128                     725r512
                   11585r8192                 23171r16384
                741455r524288                 46341r32768
             11863283r8388608           23726567r16777216
          189812531r134217728         759250125r536870912
      24296003999r17179869184         759250125r536870912
    777472127993r549755813888   388736063997r274877906944
24879108095803r17592186044416 6219777023951r4398046511104
   0j_5 ": 2 - *: {."1 (_2 + *:) B^:(5*i.10) 0 2x
2.00000e0 1.09375e_1 4.27246e_4 8.20011e_5 1.07998e_6 6.84571e_8 5.23681e_9 1.33091e_10 4.46947e_12 1.28474e_13



See also



Contributed by Roger Hui.