JPhrases/PolynomialsRational

From J Wiki
Jump to: navigation, search

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