Essays/Newton's Method

From J Wiki
Jump to: navigation, search

Newton's method is used to find approximations to a root of a differentiable function.


Introduction

   N=: 1 : '- u % u d. 1'
   (_2 + *:) N 1
1.5
   (_2 + *:) N^:2 ]1
1.41667
   (_2 + *:) N^:3 ]1
1.41422
   (_2 + *:) N^:_ ]1
1.41421

   2 - *: (_2 + *:) N^:_ ]1
4.44089e_16

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

Convergents

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

   (_2 + *:) N^:(i.8) 1
1 1.5 1.41667 1.41422 1.41421 1.41421 1.41421 1.41421
   (_2 + *:) N^:a: 1
1 1.5 1.41667 1.41422 1.41421 1.41421

   2 - *: (_2 + *:) N^:(i.8) 1
1 _0.25 _0.00694444 _6.0073e_6 _4.51061e_12 _4.44089e_16 4.44089e_16 _4.44089e_16

Rational Numbers

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

   (_2 + *:) N^:(i.8) 1x
1 3r2 17r12 577r408 665857r470832 886731088897r627013566048 ...
   0j50 ": ,. (_2 + *:) N^:(i.8) 1x
1.00000000000000000000000000000000000000000000000000
1.50000000000000000000000000000000000000000000000000
1.41666666666666666666666666666666666666666666666667
1.41421568627450980392156862745098039215686274509804
1.41421356237468991062629557889013491011655962211574
1.41421356237309504880168962350253024361498192577620
1.41421356237309504880168872420969807856967187537723
1.41421356237309504880168872420969807856967187537695

   2 - *: (_2 + *:) N^:(i.8) 1x
1 _1r4 _1r144 _1r166464 _1r221682772224 _1r393146012008229658338304 ...
   0j_5 ": 2 - *: (_2 + *:) N^:(i.8) 1x
1.00000e0 _2.50000e_1 _6.94444e_3 _6.00730e_6 _4.51095e_12 _2.54358e_24 _8.08727e_49 _8.17550e_98



See also



Contributed by Roger Hui. An earlier version of the text appeared in the J Forum on 2007-10-13.