JPhrases/PolynomialsRational
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