>>  <<  Ndx  Usr  Pri  Phr  Dic  Rel  Voc  !:  wd  Help  Dictionary

27. Polynomials: Roots from Coefficients (Kerner's Method)

Newton's method applies to one root at a time and requires a good starting approximation. Kerner's method is a generalization that gives all the roots, starting from a list a and dividing each element of the residual f a by the derivative with respect to the corresponding root. It applies only to a polynomial whose highest order coefficient is 1, and we first normalize the coefficients by dividing by the last, yielding a polynomial having the same roots. The method converges to complex roots only if at least one of the initial approximations is complex. We will use the Taylor series approximation to the exponential function, because the corresponding polynomial has complex roots:
   ]d=: ^ t. i.6
1 1 0.5 0.166667 0.0416667 0.00833333

   ]c=: (norm=: % {:) d
120 120 60 20 5 1

   +. a=: (init=: r.@}.@i.@#) c |a
 0.540302  0.841471 1 1 1 1 1
_0.416147  0.909297
_0.989992  0.14112
_0.653644 _0.756802
 0.283662 _0.958924

   deriv=: [: */ 0&=@{.}@(-/~ ,: 1:)

   kerner=: 1 : 0
] - x.&p. % deriv@]
)

   r=: c kerner ^:_ a
   +.(/:|) r                  Real and imaginary parts of roots sorted by magnitude
_2.18061 4.57601e_31
 _1.6495     1.69393
 _1.6495    _1.69393
0.239806     3.12834
0.239806    _3.12834

   >./|c p. r
1.04488e_13
These results may be compared with the use of the primitive p. on the un-normalized coefficients d . Thus:
   p. 2 4 2
+-+-----+
|2|_1 _1|
+-+-----+

   ,.;}.p. d
 0.2398064j3.12834
0.2398064j_3.12834
   _1.6495j1.69393
  _1.6495j_1.69393
          _2.18061
Newton's method may also be used for a complex root:
   +. d NEWTON ^:0 1 2 3 _ a=: 1j1
        1        1
0.0166065  0.99639
_0.990523 0.992532
 _1.95338  1.10685
  _1.6495   1.6939


>>  <<  Ndx  Usr  Pri  Phr  Dic  Rel  Voc  !:  wd  Help  Dictionary