>>  <<  Ndx  Usr  Pri  JfC  LJ  Phr  Dic  Rel  Voc  !:  wd  Help  Phrases

9C. Polynomials & Rational Functions

Sums, differences, products, quotients, derivatives, integrals, and compositions of polynomials can be expressed as functions of their coefficients. For example:

   c=: 1 4 6 4 1 [ d=: 1 2 1  [ x=: i.6
   ppr=: +//.@(*/)
   c ppr d
1 6 15 20 15 6 1

   ((c ppr d)p. x) ; ((c p. x)*(d p. x))
+---------------------------------------------------+
|1 64 729 4096 15625 46656|1 64 729 4096 15625 46656|
+---------------------------------------------------+

The polynomial function p. and related facilities such as the Taylor coefficients t. are all defined in terms of ascending powers, as is appropriate to power series. The definition in terms of descending powers commonly used in high-school algebra is discussed at the end of the section.

d0=: sum=: +/@,: Polynomial sum. Try 1 2 sum 1 3 3 1
d1=: dif=: -/@,:      "       difference
d2=: ppr=: +//.@(*/)      "       product
m3=: pdi=: 1: }. ] * i.@#      "       derivative
d4=: pin=: , ] % >:@i.@#      "       integral (left arg gives constant)
m5=: piz=: 0&pin      "       integral 0 constant of integration
m6=: atop=: [ +/ .* 1 0"_ ,ppr/\@(<:@#@[# ,:@]) Composition: (c atop d)&p. is equivalent to (c&p.) @ (d&p.)

Binomial coefficients have an important property illustrated by the following:

   bc=: i.@>: ! ]
   bc n=: 4
1 4 6 4 1
   (bc n) p. x=: i. 6
1 16 81 256 625 1296

   (x+1) ^ n
1 16 81 256 625 1296

This behaviour is extended to the coefficients of a polynomial as follows:

   bct=: !/~@i.
   expand=: bct@# +/ . * ]
   ]d=: expand c=: 3 1 4 2
10 15 10 2

   (c p. x+1) ,: (d p. x)
10 37 96 199 358 585
10 37 96 199 358 585

A polynomial with coefficients c may also be expressed as the product over its roots multiplied by the coefficient of the highest-order term, that is, {:c. The self-inverse monad p. provides the transformations between coefficients and roots. For example:

   c=: _126 _87 _6 3
   ]r=: p. c
+---------+
|3|7 _3 _2|
+---------+

   p. r
_126 _87 _6 3

   (c p. x) ,: (r p. x)
_126 _216 _300 _360 _378 _336
_126 _216 _300 _360 _378 _336

  p. 1 2 3
+--------------------------------------------+
|3|_0.3333333j0.4714045 _0.3333333j_0.4714045|
+--------------------------------------------+
m7=: p. Transformation between roots and coefficients
d8=: p. Polynomial in terms of roots or coefficients
c9=: FIT=: 2 :'x. %. ]^/(i.y.)"_' f FIT d gives coeffs of pn fit of degree d-1

The falling factorial function ff=: ^!._1, and the corresponding falling polynomial fp=: p.!._1 are useful in the finite calculus:

   ff=: ^!._1 
   fp=: p.!._1 " 1 0
   c=: 2 1 4 3 [ x=: 6 [ n=: 4
   (x^n),(*/x+0*i.n)
1296 1296

   FIT=: 2 : 'x. %. ] ^/ (i.y.)"_'
   (x ff n),(*/x+_1*i.n)
360 360

   (c p. x),(+/c*x^i.#c)
800 800

   (c fp x),(+/c*x ff i.#c)
488 488 

We will define a linear function to transform the coefficients of a polynomial to the coefficients of an equivalent falling polynomial, that is, (c p. x)-:(fcFc fp x) :

   VM=: ((/ ~) (@i.)) (@#)          NB. Vandermonde adverb
   ^VM                              NB. Normal Vandermonde
^/~@i.@#

   ^VM c=: 3 1 4 2
1 0 0  0
1 1 1  1
1 2 4  8
1 3 9 27

   fcFc=: ] +/ . *~ ^VM %. ff VM    NB. Falling coeffs from normal coeffs
   fcFc c=: 3 1 4 2
3 7 10 2

   (c p. x) ,: (fcFc c) fp x=: 0 1 2 3 4 5
3 10 37 96 199 358
3 10 37 96 199 358
d10=: ff=: ^!._1 Falling factorial (_1-stope)
d11=: fp=: p.!._1 " 1 0 Falling factorial polynomial
a12=: VM=: ((/ ~)(@i.))(@#) Vandermonde adverb
m13=: fcFc=:]+/ .*~^VM%.ff VM Falling coeffs From ordinary coeffs
m14=: cFfc=: fcFc^:_1 Ordinary coeffs From falling coeffs
d15=: taut=: p. -: fcFc@[ fp ] Tautology
d16=: rf=: ^!.1 Rising factorial
a17=: S=: 1 : '^!.x.' Stope adverb (1 S is rf Try 0.1 S)
d18=: mtn=:{.@[+/ .*]*/ .^}.@[ Multinomial e.g. (c,E) mtn x,y,z

If c is a list of coefficients equal in number to the columns of a three-rowed table of exponents E, and if v=: x,y,z, then c +/ . * v */ . ^ E is a multinomial, a weighted sum of powers of x, y, and z. For example:

   v=: 'x y z'=: 2 3 5
   c=: 3 1 4 2 [ E=: 1 0 2 3,1 1 0 0,:1 2 1 0
   E ; (,.v*/ . ^ E) ; (c +/ . * v*/ . ^ E)
+--------------+
|1 0 2 3|30|261|
|1 1 0 0|75|   |
|1 2 1 0|20|   |
|       | 8|   |
+--------------+
   mtn=: {.@[ +/ . * ] */ . ^ }.@[
   (c,E) mtn v
261

If f and g are polynomials, then the function f % g is called a rational function. The conjunction R=: 2 : 'x.&p. % y.&p.' produces a rational function defined by its coefficient arguments:

   R=: 2 : 'x.&p. % y.&p.'
   c=: 1 4 6 4 1 [ d=: 1 2 1  x=: i.6
   c R d
1 4 6 4 1&p. % 1 2 1&p.

   c R d x
1 4 9 16 25 36

   d R c x
1 0.25 0.1111111 0.0625 0.04 0.02777778

The Taylor coefficients of rational functions may provide interesting results. For example:

   c R d t. i. 10
1 2 1 0 0 0 0 0 0 0

   d R c t. i. 10
1 _2 3 _4 5 _6 7 _8 9 _10

   0 1 R 1 _1 _1 t. i. 10
0 1 1 2 3 5 8 13 21 34 Fibonacci numbers
c19=: R=: 2 : 'x.&p. % y.&p.' Rational conjunction
c20=: TR=: 2 : '(x.&p. % y.&p.) t.' Taylor series of rational function

The high-school definition of a polynomial in terms of descending powers may be defined by reversing the order of the coefficients as follows:

   dp=: (|.@[ p. ])"1 1 0
   1 2 3 4 p. i. 7
1 10 49 142 313 586 985

   4 3 2 1 dp i. 7
1 10 49 142 313 586 985

Corresponding definitions of some other functions such as sum, product, and derivative are collected below:

d21=: dp=: (|.@[ p. ])"1 1 0 Polynomial in descending powers
d22=: dsum=: sum&.|. Polynomial sum in descending powers
d23=: ddif=: dif&.|. Polynomial difference in descending powers
d24=: dppr=: ppr Polynomial product in descending powers
m25=: dpdi=: pdi&.|. Polynomial derivative in descending powers
m26=: ".&> 'a=:2&{'; 'b=:1&{'; 'c=:0&{' Coefficients a, b, and c of quadratic
m27=: dsc=: (b^2:) - 4:*a*c Discriminant of quadratic
m28=: r=:(-@b(+,-)%:@dsc)%+:@a Roots of quadratic
d29=: m28@(1: , ,) b d29 c gives roots of 1,b,c
m30=: ] d29"0 i.@>.@(*: % 4:) Arguments limited to real results

For example:

   d=: 1 2 3 4 [ e=: 3 2 5  
   d dsum e
1 5 5 9 
   ((d dsum e)dp y) ,: (d dp y) + (e dp y) [ y=: i.7
9 20 47 96 173 284 435
9 20 47 96 173 284 435

   ((d dppr e)dp y) ,: (d dp y) * (e dp y)
20 100 546 2204 6832 17460 38750
20 100 546 2204 6832 17460 38750

Phrases m33-m35 use the well-known expression from elementary algebra to produce the roots of a quadratic as functions of a three-element list of coefficients for a polynomial with exponents in ascending order. For example:

   (a ; b ; c ; dsc ; r) abc=: 2 _7 3
+---------------------+
|3|_7|2|25|2 0.3333333|
+---------------------+

   abc dp r abc Test roots
0 0

   (a ; b ; c ; dsc ; r) abc=: 1 1 1
+-------------------------------------+
|1|1|1|_3|_0.5j0.866025 _0.5j_0.866025|
+-------------------------------------+

 
   abc dp r abc
1.11022e_16 1.11022e_16

The expression b d36 c gives the roots of the "monic" polynomial with coeffieicnts 1,b,c, and m36 applies it to pairs of non-negative intgers that yield real roots. For example:

   <"1 (i.6) d36"0/ i.3
+--------------------------------------------------------------+
|0 0 |0j1 0j_1                      |0j1.41421 0j_1.41421      |
+----+------------------------------+--------------------------|
|0 _1|_0.5j0.8660254 _0.5j_0.8660254|_0.5j1.32288 _0.5j_1.32288|
+----+------------------------------+--------------------------|
|0 _2|_1 _1                         |_1j1 _1j_1                |
+----+------------------------------+--------------------------|
|0 _3|_0.381966 _2.61803            |_1 _2                     |
+----+------------------------------+--------------------------|
|0 _4|_0.2679492 _3.73205           |_0.5857864 _3.41421       |
+----+------------------------------+--------------------------|
|0 _5|_0.2087122 _4.79129           |_0.4384472 _4.56155       |
+--------------------------------------------------------------+

   m37 6
         0       _6
_0.1715729 _5.82843
_0.3542487 _5.64575
_0.5505103 _5.44949
 _0.763932 _5.23607
        _1       _5
  _1.26795 _4.73205
  _1.58579 _4.41421
        _2       _4


>>  <<  Ndx  Usr  Pri  JfC  LJ  Phr  Dic  Rel  Voc  !:  wd  Help  Phrases