Differences between revisions 3 and 4
 ⇤ ← Revision 3 as of 2007-10-17 14:37:31 → Size: 3202 Editor: RogerHui Comment: shorter ← Revision 4 as of 2008-12-08 10:45:45 → ⇥ Size: 3164 Editor: anonymous Comment: converted to 1.6 markup Deletions are marked like this. Additions are marked like this. Line 3: Line 3: [[TableOfContents(2)]] <> Line 88: Line 88: [[BR]] <
> Line 91: Line 91: * [http://mathworld.wolfram.com/Bisection.html MathWorld] * [http://en.wikipedia.org/wiki/Bisection_method Wikipedia] * [:../Newton's Method:Newton's Method] * [[MathWorld:Bisection|MathWorld]] * [[WikiPedia:Bisection_method|Wikipedia]] * [[../Newton's Method|Newton's Method]] Line 95: Line 95: [[BR]] <
>

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

Contents

## 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```

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```