Essays/Bisection Method
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.