õıııııÃıııııııııııııııııııııııııııııııııııııııııııııııÀ ş 0 1ş 0 1 2 3 4 5 6 7 8 9 10 11ş ş 2 3ş 12 13 14 15 16 17 18 19 20 21 22 23ş ş ş 24 25 26 27 28 29 30 31 32 33 34 35ş ş 4 5ş 36 37 38 39 40 41 42 43 44 45 46 47ş ş 6 7ş 48 49 50 51 52 53 54 55 56 57 58 59ş ş ş 60 61 62 63 64 65 66 67 68 69 70 71ş ş 8 9ş 72 73 74 75 76 77 78 79 80 81 82 83ş ş10 11ş 84 85 86 87 88 89 90 91 92 93 94 95ş ş ş 96 97 98 99 100 101 102 103 104 105 106 107ş ş ş108 109 110 111 112 113 114 115 116 117 118 119ş ş ş120 121 122 123 124 125 126 127 128 129 130 131ş ş ş132 133 134 135 136 137 138 139 140 141 142 143ş ÁıııııÂıııııııııııııııııııııııııııııııııııııııııııııııã (i. 3 2 2) 0 cut i. 12 12 õııııııııÃıııııııııııııııııııııııııııÃıııııııııııÀ ş 1 2 3ş 53 54 55 56 57 58 59ş105 106 107ş ş13 14 15ş 65 66 67 68 69 70 71ş117 118 119ş ş ş 77 78 79 80 81 82 83ş129 130 131ş ş ş 89 90 91 92 93 94 95ş141 142 143ş ş ş101 102 103 104 105 106 107ş ş ş ş113 114 115 116 117 118 119ş ş ÁııııııııÂıııııııııııııııııııııııııııÂıııııııııııã GEOMETRY We will illustrate the topic of coordinate geometry by defining functions for polygons in two dimensions that give the displacements between adjacent vertices, the length of sides, the semiperimeter, and the area based on Heron's formula. We also present a more general definition for area that not only gives the signed area (positive if the vertices appear in counter-clockwise order), but also applies to polyhedra in higher dimensions (in which case the name area might better be replaced by volume). This definition is based on the use of the determinant applied to a square matrix obtained by bordering a table of vertices t by a final row of the values %!#t . Thus: (length=. +/&.*:) 5 12 13 disp=. ] - 1&|."1 sides=. length@disp semiper=. -:@(+/)@sides HERON=. %:@(*/)@(semiper - 0: , sides) area=. -/ . * @ (] , %@!@#) t=. 0 0 4 ,: 3 4 7 (];(1&|."1);disp;sides;semiper;HERON;area) t õıııııÃıııııÃıııııııÃıııııııııııÃıııııııÃıÃııÀ ş0 0 4ş0 4 0ş 0 _4 4ş1 5 5.65685ş5.82843ş2ş_2ş ş3 4 7ş4 7 3ş_1 _3 4ş ş ş ş ş ÁıııııÂıııııÂıııııııÂıııııııııııÂıııııııÂıÂııã tet1=.6 0 3 0,3 6 5 8,:7 4 0 5 tet2=. 0,.=i.3 3 tet1;(area tet1);tet2;(area tet2) õıııııııÃııııÃıııııııÃııııııııııÀ ş6 0 3 0ş11.5ş0 1 0 0ş_0.1666667ş ş3 6 5 8ş ş0 0 1 0ş ş ş7 4 0 5ş ş0 0 0 1ş ş ÁıııııııÂııııÂıııııııÂııııııııııã SYMBOLIC FUNCTIONS For any function, a corresponding symbolic function can be defined to display the expression rather than evaluate it. For example: minus=. [ , '-'"_ , ] 'a' minus 'b' a-b list=. 'abcd' table=. 4 4$'ABCDEFGHIJKLMNOP' minus/list a-b-c-d (minus/\list);('01'minus"0/list);(minus//.table);table õıııııııÃıııÃıııııııÃııııÀ şa ş0-aşA şABCDş şa-b ş0-bşB-E şEFGHş şa-b-c ş0-cşC-F-I şIJKLş şa-b-c-dş0-dşD-G-J-MşMNOPş ş ş şH-K-N ş ş ş ş1-aşL-O ş ş ş ş1-bşP ş ş ş ş1-cş ş ş ş ş1-dş ş ş ÁıııııııÂıııÂıııııııÂııııã (list)=. 4 3 2 1 ". minus/\list 4 1 3 2 3 minus/\ 'abcdefg' a-b-c b-c-d c-d-e d-e-f e-f-g 3 minus/\. 'abcdefg' d-e-f-g a-e-f-g a-b-f-g a-b-c-g a-b-c-d DIRECTED GRAPHS A directed graph is a collection of nodes with connections or arcs specified between certain pairs of nodes. It can be used to specify matters such as the precedences in a set of processes (stuffing of envelopes must precede sealing), or the structure of a tree. The connections can be specified by a boolean connection matrix instead of by arcs, and the connection matrix can be determined from the list of arcs. The connection matrix is very convenient for determining various properties of the graph, such as the in-degrees (number of arcs entering a node), the out-degrees, immediate descendants, and the closure, or connection to every node reachable through some path. For example: from=. 3 7 2 5 5 7 1 5 5 5 2 6 1 2 3 7 7 4 7 2 7 4 to=. 5 6 0 2 6 2 7 6 0 7 3 3 2 1 7 0 4 2 3 0 0 3 $ arcs=. from,.to 22 2 |: arcs { nodes=. 'ABCDEFGH' Transposed for display DHCFFHBFFFCGBCDHHEHCHE FGACGCHGAHDDCBHAECDAAD CM=. #. e.~ [: i. [ , [ Connection matrix from arcs ]cm=. (>:>./,arcs) CM arcs 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1 0 0 0 0 1 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 1 1 1 0 1 0 (+/cm);(+/"1 cm); (+/+/cm);(#arcs);(#~.arcs) õıııııııııııııııÃıııııııııııııııÃııÃııÃııÀ ş3 1 4 4 1 1 2 3ş0 2 3 2 2 4 1 5ş19ş22ş19ş ÁıııııııııııııııÂıııııııııııııııÂııÂııÂııã The foregoing results are the in, out, and total degrees; followed by the number of arcs, and the number of distinct arcs. A boolean vector b may be used to represent the nodes b#nodes, and the inner product b+./ . *. cm gives the same representation of the nodes reachable from them. The immediate family (which includes the original points themselves) is therefore given by the function imfam : imfam=. [ +. +./ . *. (b=. 1 0 0 0 0 0 0 1) imfam cm 1 0 1 1 1 0 1 1 Just as b imfam cm produces the immediate family of b, so does the phrase cmimfam cm produce the immediate families of each of the rows of cm. We will, however, use a new sparser connection matrix that will be more instructive, and will use powers of imfam to produce families of further generations, including an infinite power to give the closure of the connection matrix; that is, the connection matrix for all points reachable by a path of any length: cm=. (i. =/ <:@i.) 8 <"2 cm imfam^:0 1 2 _ cm õıııııııııııııııÃıııııııııııııııÃıııııııııııııııÃıııııııııııııııÀ ş0 1 0 0 0 0 0 0ş0 1 1 0 0 0 0 0ş0 1 1 1 0 0 0 0ş0 1 1 1 1 1 1 1ş ş0 0 1 0 0 0 0 0ş0 0 1 1 0 0 0 0ş0 0 1 1 1 0 0 0ş0 0 1 1 1 1 1 1ş ş0 0 0 1 0 0 0 0ş0 0 0 1 1 0 0 0ş0 0 0 1 1 1 0 0ş0 0 0 1 1 1 1 1ş ş0 0 0 0 1 0 0 0ş0 0 0 0 1 1 0 0ş0 0 0 0 1 1 1 0ş0 0 0 0 1 1 1 1ş ş0 0 0 0 0 1 0 0ş0 0 0 0 0 1 1 0ş0 0 0 0 0 1 1 1ş0 0 0 0 0 1 1 1ş ş0 0 0 0 0 0 1 0ş0 0 0 0 0 0 1 1ş0 0 0 0 0 0 1 1ş0 0 0 0 0 0 1 1ş ş0 0 0 0 0 0 0 1ş0 0 0 0 0 0 0 1ş0 0 0 0 0 0 0 1ş0 0 0 0 0 0 0 1ş ş0 0 0 0 0 0 0 0ş0 0 0 0 0 0 0 0ş0 0 0 0 0 0 0 0ş0 0 0 0 0 0 0 0ş ÁıııııııııııııııÂıııııııııııııııÂıııııııııııııııÂıııııııııııııııã The closure of cm can therefore be expressed as cm imfam^:_ cm, and a monadic closure function can be defined as follows: closure=. imfam^:_ ~ closure cm 0 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 The complete definition of the closure function may now be displayed as follows: closure f. ([ +. +./ .*.)^:_~ DISTANCE The street distance between two points will be defined as the sum of the magnitudes of the difference of their coordinates along each axis. Thus: d=. +/@|@:-"1 p=. 3 5 1 [ q=. 7 4 0 p d q 6 table=. #: i. 2^3 (]; d/~) table Table and distances between each pair of points in it õıııııÃıııııııııııııııÀ ş0 0 0ş0 1 1 2 1 2 2 3ş ş0 0 1ş1 0 2 1 2 1 3 2ş ş0 1 0ş1 2 0 1 2 3 1 2ş ş0 1 1ş2 1 1 0 3 2 2 1ş ş1 0 0ş1 2 2 3 0 1 1 2ş ş1 0 1ş2 1 3 2 1 0 2 1ş ş1 1 0ş2 3 1 2 1 2 0 1ş ş1 1 1ş3 2 2 1 2 1 1 0ş ÁıııııÂıııııııııııııııã g=. [ * [ = d/~@] (];(d/~);(1&g);(2&g)) table õıııııÃıııııııııııııııÃıııııııııııııııÃıııııııııııııııÀ ş0 0 0ş0 1 1 2 1 2 2 3ş0 1 1 0 1 0 0 0ş0 0 0 2 0 2 2 0ş ş0 0 1ş1 0 2 1 2 1 3 2ş1 0 0 1 0 1 0 0ş0 0 2 0 2 0 0 2ş ş0 1 0ş1 2 0 1 2 3 1 2ş1 0 0 1 0 0 1 0ş0 2 0 0 2 0 0 2ş ş0 1 1ş2 1 1 0 3 2 2 1ş0 1 1 0 0 0 0 1ş2 0 0 0 0 2 2 0ş ş1 0 0ş1 2 2 3 0 1 1 2ş1 0 0 0 0 1 1 0ş0 2 2 0 0 0 0 2ş ş1 0 1ş2 1 3 2 1 0 2 1ş0 1 0 0 1 0 0 1ş2 0 0 2 0 0 2 0ş ş1 1 0ş2 3 1 2 1 2 0 1ş0 0 1 0 1 0 0 1ş2 0 0 2 0 2 0 0ş ş1 1 1ş3 2 2 1 2 1 1 0ş0 0 0 1 0 1 1 0ş0 2 2 0 2 0 0 0ş ÁıııııÂıııııııııııııııÂıııııııııııııııÂıııııııııııııııã {&' .+*' &.> (];(d/~);(1&g);(2&g);(3&g)) table õıııÃııııııııÃııııııııÃııııııııÃııııııııÀ ş ş ..+.++*ş .. . ş + ++ ş *ş ş .ş. +.+.*+ş. . . ş + + +ş * ş ş . ş.+ .+*.+ş. . . ş + + +ş * ş ş ..ş+.. *++.ş .. .ş+ ++ ş * ş ş. ş.++* ..+ş. .. ş ++ +ş * ş ş. .ş+.*+. +.ş . . .ş+ + + ş * ş ş.. ş+*.+.+ .ş . . .ş+ + + ş * ş ş...ş*++.+.. ş . .. ş ++ + ş* ş ÁıııÂııııııııÂııııııııÂııııııııÂııııııııã POLYNOMIALS The monadic function M=. 3: * ] ^ 2: is a multiple of an integral power of its argument, and is called a monomial; and a sum of monomials such as SM=.(3:*]^2:)+(2.5"_*]^4:)+(_5"_*]^0:) is a polynomial. Any polynomial can be expressed in the standard form c&p, where c is a suitable list of coefficients, and where p=. +/@([*]^i.@#@[)"1 0. For example: SM=.á(3:*]^2:)+(2.5"_*]^4:)+(_5"_*]^0:) p=. +/@([*]^i.@#@[)"1 0 c=. _5 0 3 0 2.5 x=. _2 _1 0 1 2 (SM x),(c p x),:(c&p x) 47 0.5 _5 0.5 47 47 0.5 _5 0.5 47 47 0.5 _5 0.5 47 The primitive p. is equivalent to the function p defined above, and will be used hereafter. The polynomial c&p.is very important for a number of reasons, including: 1. It applies to any numeric argument, real or complex (and the parameter c may also be complex). 2. It can be used to approximate a wide range of functions. 3. It is closed under a number of operations; that is, the sum, difference, product, the composition @, the derivative, and the integral of polynomials are themselves polynomials. 4. The coefficients of the results of each case listed in 3 are easily expressed. For example, if #c equals #d, then c&p. + d&p. is equal to (c+d)&p. . More generally, it is equal to (+/c,:d)&p. . Thus: ps=. +/@,: Polynomial sum pd=. -/@,: Polynomial difference pp=. +//.@(*/) Polynomial product D=. ("0)(D.1) Scalar (rank 0) first derivative pD=. 1: }. ] * i.@# Polynomial derivative pI=. 0: , ] % 1: + i.@# Polynomial integral For example: c=. 1 2 1 [ d=. 1 3 3 1 x=. 2 1 0 _1 _2 ,.&.>((c pp d);((c pp d)&p. x);((c&p.*d&p.)x)) õııÃıııÃıııÀ ş 1ş243ş243ş ş 5ş 32ş 32ş ş10ş 1ş 1ş ş10ş 0ş 0ş ş 5ş _1ş _1ş ş 1ş ş ş ÁııÂıııÂıııã ,.&.>((d&p.D x);(pD d);((pD d)&p. x);(pI d);(pD pI d)) õııÃıÃııÃııııÃıÀ ş27ş3ş27ş 0ş1ş ş12ş6ş12ş 1ş3ş ş 3ş3ş 3ş 1.5ş3ş ş 0ş ş 0ş 1ş1ş ş 3ş ş 3ş0.25ş ş ÁııÂıÂııÂııııÂıã ]e=. c(ps pp pd)d 0 _2 _9 _16 _14 _6 _1 e&p. x _648 _48 0 0 0 ((c&p.+d&p.)*(c&p.-d&p.)) x _648 _48 0 0 0 f=. c&p.(+*-) d&p. f x _648 _48 0 0 0 ]g=. pD c pp d 5 20 30 20 5 g&p. x 405 80 5 0 5 (c&p.*d&p.) D x 405 80 5 0 5 POLYNOMIALS In terms of roots The product */y-r is called a polynomial in terms of the roots r, because it can also be expressed as a polynomial applied to the argument y, and because r is the list of rootsor zeros of the resulting function. For example: y=. 7 [ r=. 2 3 5 [ x=. 7 6 5 4 3 2 */y-r 40 pp=. +//.@(*/) c=. pp/monomials=. (- ,. 1:) r cfr=. [: pp/ - ,. 1: Coefficients from roots pir=. */@(]-[)"1 0 Polynomial in terms of roots ,.&.>(r;monomials;c;(cfr r);(c&p. y);(r pir x)) õıÃııııÃıııÃıııÃııÃııÀ ş2ş_2 1ş_30ş_30ş40ş40ş ş3ş_3 1ş 31ş 31ş ş12ş ş5ş_5 1ş_10ş_10ş ş 0ş ş ş ş 1ş 1ş ş_2ş ş ş ş ş ş ş 0ş ş ş ş ş ş ş 0ş ÁıÂııııÂıııÂıııÂııÂııã Since the last (highest order) coefficient produced by cfr is necessarily 1, the function pir cannot produce a general polynomial, but it can if provided with a multiplier. We therefore re-define cfr and pir to apply to a boxed list of multiplier and roots as follows: CFR=. (* cfr)&>/ PIR=. CFR@[ p. ] CFR 3;r _90 93 _30 3 (3;r) PIR x 120 36 0 _6 0 0 We now illustrate the use of a polynomial in approximation: ]ce=. ^ t. i. 7 First seven terms of Taylor series for exponential 1 1 0.5 0.166667 0.0416667 0.00833333 0.00138889 (^ - ce&p.) _1 _0.5 0 0.5 1 Comparison with exponential _0.000176114 _1.45834e_6 0 1.65264e_6 0.000226273 pD ce The exponential function is equal to its own derivative 1 1 0.5 0.166667 0.0416667 0.00833333 POLYNOMIALS Roots from coefficients (Newtons Method) Because the polynomials (m;r)&PIR and (c=.CFR (m;r))&p.are identical, the parameters m;r and c are said to be different representations of the same function. Each representation has its own useful properties. For example, addition of polynomials is easy in the coefficient representation but difficult in the root representation; the identification of the zeros of the function is difficult in the coefficient representation but trivial in the root representation. It is therefore useful to have functions that transform each representation to the other. CFR serves for one direction; the inverse problem is approached by methods of successive approximation. For any function f, the difference (f r)-(f a) for nearby points r and a is approximately equal to the difference r-a multiplied by the slope of the tangent to the graph of f at the point a,f a, that is, the derivative of f at a. Conversely, the difference r-a is approximated by ((f r)-(f a))%f D a, and r is approximated by a+((f r)-(f a))%f D a. If f is the polynomial c&p. and r is one of its roots, then f r is zero, and if a is an approximation to r, the expression for r reduces to a-(f a)%f D a. This may provide a better approximation to r, and is embodied in Newtons method, defined as an adverb, and illustrated as follows: newton=. 1 : 0 ] - x. % x.D ) f=. (c=. 12 _10 2)&p. f a=. 2.4 f newton a _0.48 1.2 f newton ^:0 1 2 3 4 _ a f 2 2.4 1.2 1.75385 1.9594 1.99848 2 0 ]a=. (^ - 4:) newton ^: 0 1 2 3 _ a=. 1 1 1.47152 1.38982 1.3863 1.38629 ^ {: a 4 For the particular case of polynomials, we may define an adverb that applies to coefficients and uses the polynomial derivative pD instead of the general derivative D: pD= .1: }. ] * i.@# NEWTON=. 1 : 0 ] - x.&p. % (pD x.)&p. ) c NEWTON ^:0 1 2 3 4 _ a=. 2.4 2.4 1.2 1.75385 1.9594 1.99848 2 POLYNOMIALS Roots from coefficients (Kerners Method) Newton's method applies only to one root at a time and usually requires a rather good starting approximation. Kerners method is a generalization that gives all the roots, starting from a list a and dividing each element of the residual f a by the derivative with respect to the corresponding root. The method applies only to a polynomial whose highest order coefficient is 1, and we first normalize the coefficients by dividing by the last, yielding a polynomial having the same roots. Moreover, the method will converge to complex roots only if at least one of the initial approximations is complex. We will use the Taylor series approximation to the exponential function, because the corresponding polynomial has complex roots: ]d=. ^ t. i.6 1 1 0.5 0.166667 0.0416667 0.00833333 ]c=. (norm=. % {:) d 120 120 60 20 5 1 +. a=. (init=. r.@}.@i.@#) c |a 0.540302 0.841471 1 1 1 1 1 _0.416147 0.909297 _0.989992 0.14112 _0.653644 _0.756802 0.283662 _0.958924 deriv=. [: */ 0&=@{.}@(-/~ ,: 1:) kerner=. 1 : 0 ] - x.&p. % deriv@] ) r=. c k ^:_ a +.(/:|) r _2.18061 _1.03444e_36 _1.6495 _1.69393 _1.6495 1.69393 0.239806 _3.12834 0.239806 3.12834 >./|c p. r