C. Polynomials & Rational Functions

>> << Ndx Usr Pri 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 Phr Dic Rel Voc !: wd Help Phrases