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

26. Polynomials: Roots from Coefficients (Newton's Method)

Because the polynomials (m;r)&PIR and (c=:CFR (m;r))&p. are identical, the parameters m;r and c are said to be different representations of the same function. Each representation has its own useful properties. For example, addition of polynomials is easy in the coefficient representation but difficult in the root representation; the identification of the zeros of the function is difficult in the coefficient representation but trivial in the root representation. It is therefore useful to have functions that transform each representation to the other. CFR serves for one direction; the inverse problem is approached by methods of successive approximation.

For any function f , the difference (f r)-(f a) for nearby points r and a is approximately equal to the difference r-a multiplied by the slope of the tangent to the graph of f at the point a,f a, that is, the derivative of f at a . Conversely, the difference r-a is approximated by ((f r)-(f a))%f D a, and r is approximated by a+((f r)-(f a))%f D a .

If f is the polynomial c&p. and r is one of its roots, then f r is zero, and if a is an approximation to r , the expression for r reduces to a-(f a)%f D a . This may provide a better approximation to r , and is embodied in Newton's method, defined as an adverb, and illustrated as follows:
   newton=: 1 : 0
] - x. % x.D
)

   f=: (c=: 12 _10 2)&p.

   f a=: 2.4 
_0.48

   f newton a
1.2

   f 2
0

   f newton ^:0 1 2 3 4 _ a
2.4 1.2 1.75385 1.9594 1.99848 2

   ]a=: (^ - 4:) newton ^: 0 1 2 3 _ a=: 1
1 1.47152 1.38982 1.3863 1.38629

   ^ {: a
4
For the particular case of polynomials, we may define an adverb that applies to coefficients and uses the polynomial derivative pD instead of the general derivative D :

   pD=: 1: }. ] * i.@#
   NEWTON=: 1 : '] - x.&p. % (pD x.)&p.'

   c NEWTON ^:0 1 2 3 4 _ a=: 2.4
2.4 1.2 1.75385 1.9594 1.99848 2


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