Differences between revisions 7 and 8
 ⇤ ← Revision 7 as of 2008-05-31 01:41:39 → Size: 4462 Editor: RicSherlock Comment: figure captions ← Revision 8 as of 2008-12-08 10:45:49 → ⇥ Size: 4469 Editor: anonymous Comment: converted to 1.6 markup Deletions are marked like this. Additions are marked like this. Line 4: Line 4: ||[[latex(\$f(x)= 3 + x \$)]] ||('''a''')||  ||[[latex(\$f(x)= 1 + 2x + x^2 \$)]]|| ('''b''')|| ||<> ||('''a''')||  ||<>|| ('''b''')|| Line 15: Line 15: The dyadic form of the '''J''' primitive `p.` ([wiki:JDic:dpdot Polynomial]) evaluates a polynomial of order `#x` with coefficients `x` for the argument `y`. So [[latex(\$f(-2)\$)]] for polynomial '''b''' is The dyadic form of the '''J''' primitive `p.` ([[JDic:dpdot|Polynomial]]) evaluates a polynomial of order `#x` with coefficients `x` for the argument `y`. So <> for polynomial '''b''' is Line 22: Line 22: || inline:abintersect.png|| || {{attachment:abintersect.png}}|| Line 33: Line 33: when [[latex(\$x\$)]] is `_2` or `1`. How can we get that result using J? when <> is `_2` or `1`. How can we get that result using J? Line 36: Line 36: (the values for [[latex(\$x\$)]] where a polynomial is zero) (the values for <> where a polynomial is zero) Line 44: Line 44: i.e. ` ` [[latex(\$f(x)= 2 - x - x^2\$)]] ` `('''c''') i.e. ` ` <> ` `('''c''') Line 47: Line 47: monadic form of the '''J''' primitive `p.` ([wiki:JDic:dpdot Roots]): monadic form of the '''J''' primitive `p.` ([[JDic:dpdot|Roots]]): Line 56: Line 56: we can put these ideas all together to give a vector of the [[latex(\$x\$)]] values we can put these ideas all together to give a vector of the <> values Line 83: Line 83: You can test whether [[latex(\$f_0, f_1, ...\$)]] are all equal byforming the sum of [[latex(\$(f_i - f_j)^2\$)]] and setting it to zero. You can test whether <> are all equal byforming the sum of <> and setting it to zero. Line 108: Line 108: ||[[latex(\$f(x)= x^2 \$)]] || ('''d''') ||    ||[[latex(\$f(x)= 2 - x^2 \$)]] || ('''e''') ||    ||[[latex(\$f(x)= 1 \$)]] || ('''f''') || ||<> || ('''d''') ||    ||<> || ('''e''') ||    ||<> || ('''f''') || Line 118: Line 118: || inline:cdeintersect.png|| || {{attachment:cdeintersect.png}}|| Line 125: Line 125: By inspection these polynomials intersect when [[latex(\$x\$)]] is `1` or `_1`. By inspection these polynomials intersect when <> is `1` or `_1`. Line 128: Line 128: can find the [[latex(\$x\$)]] coordinates where they all intersect. can find the <> coordinates where they all intersect. Line 134: Line 134: We can evaluate each polynomial at those [[latex(\$x\$)]] values to show that they all have the same [[latex(\$f(x)\$)]]. We can evaluate each polynomial at those <> values to show that they all have the same <>. Line 147: Line 147: [wiki:JForum:programming/2008-May/010873 forum thread] by JohnRandall, RaulMiller and HenryRich. [[JForum:programming/2008-May/010873|forum thread]] by JohnRandall, RaulMiller and HenryRich.

## Find the intersection of polynomials

### Two polynomials

Given two polynomials, for example:

•  (a) (b)

how can we find their intersection?

The coefficients of the above polynomials from lowest to highest order are:

```a=: 3 1
b=: 1 2 1```

The dyadic form of the J primitive p. (Polynomial) evaluates a polynomial of order #x with coefficients x for the argument y. So for polynomial b is

```   1 2 1 p. _2
1```
 plot _3 3;'a p. y ` b p. y'

We can plot these polynomials as follows:

```   load 'plot'
plot _3 3;'3 1 p. y ` 1 2 1 p. y'
NB. or
plot _3 3;'a p. y ` b p. y'```

From the plot we can see that the two polynomials intersect when is _2 or 1. How can we get that result using J?

This is equivalent to finding the roots (the values for where a polynomial is zero) of a polynomial formed by subtracting polynomial a from polynomial b.

Firstly subtract one polynomial from another:

```   a (-/@,:) b
2 _1 _1```

i.e.         (c)

Then find the roots of the resulting polynomial c using the monadic form of the J primitive p. (Roots):

```   p. 2 _1 _1
┌──┬────┐
│_1│_2 1│
└──┴────┘```

The roots are contained in the 2nd box (the first contains the multiplier) so we can put these ideas all together to give a vector of the values where two polynomials intersect:

```   findIntersect=: 1 {:: [: p. -/@,:

a findIntersect b
_2 1```

Where the roots of the polynomial formed by subtraction are complex, findIntersect will return the complex roots.

```   6 2 1 findIntersect 1 2
0j2.236068 0j_2.236068```

If we only wished to return real roots we could extend findIntersect as follows:

`   6 2 1 (#~ (= +))@findIntersect 1 2`

### Two or more polynomials

The examples given above are probably the best way to find the intersection of 2 polynomials. If you want the common intersection of several, here is a less-succinct method.

You can test whether are all equal by forming the sum of and setting it to zero.

```ppr   =: +//.@(*/)  NB. polynomial product
pdiff =: -/@,:      NB. polynomial difference
pps   =: ppr~      NB. polynomial square

comb=: 4 : 0
k=. i.>:d=.y-x
z=. (d\$<i.0 0),<i.1 0
for. i.x do. z=. k ,.&.> ,&.>/\. >:&.> z end.
; z
)

NB. findIntersectM <list of boxes of coefficients>
NB. returns x-coordinates of common intersection points
findIntersectM=:3 : 0
a=. >y
c=. 2 comb #a
~. (#~ (= +)) 1{:: p. +/ pps@pdiff /"2  c { a
)```

For example to find the intersection of the polynomials:

•  (d) (e) (f)

```d=: 0 0 1
e=: 2 0 _1
f=: 1```

 plot _3 3;'d p. y`e p. y`f p. y'

We can plot these as follows.

```   require 'plot'
plot _3 3;'d p. y ` e p. y ` f p. y'```

By inspection these polynomials intersect when is 1 or _1.

Given a list of boxed coefficients for each polynomial we can find the coordinates where they all intersect.

```   ]r=: findIntersectM c;d;e
1 _1```

We can evaluate each polynomial at those values to show that they all have the same .

```   d p. r
1 1
e p. r
1 1
f p. r
1 1```

## Contributions

This essay was compiled by RicSherlock from posts in this forum thread by JohnRandall, RaulMiller and HenryRich.