{"id":4055,"date":"2018-04-05T13:34:27","date_gmt":"2018-04-05T13:34:27","guid":{"rendered":"http:\/\/www.dyalog.com\/blog\/?p=4055"},"modified":"2018-04-19T07:40:27","modified_gmt":"2018-04-19T07:40:27","slug":"linear-interpolation","status":"publish","type":"post","link":"https:\/\/www.dyalog.com\/blog\/2018\/04\/linear-interpolation\/","title":{"rendered":"Linear Interpolation"},"content":{"rendered":"<p><code class=\"language-apl\">\u2395io=0<\/code> assumed throughout; works in 1-origin with the obvious modifications.<\/p>\n<h2>Introduction<\/h2>\n<p>On Wednesday, a question arrived via Dyalog Support from an intern in Africa: If <code class=\"language-apl\">M<\/code> is the matrix on the left, use linear interpolation to compute the result on the right.<\/p>\n<pre><code class=\"language-apl\">   1 20         1 20\r\n   4 80         2 40\r\n   6 82         3 60\r\n                4 80\r\n                5 81\r\n                6 82\r\n<\/code><\/pre>\n<h2>Linear Interpolation<\/h2>\n<p>Two points <code class=\"language-apl\">(x0,y0)<\/code> and <code class=\"language-apl\">(x1,y1)<\/code> specify a line; for any <code class=\"language-apl\">x<\/code> there is a unique <code class=\"language-apl\">y<\/code> on that line (assuming <code class=\"language-apl\">x0\u2260x1<\/code>). The equation for the line derives as follows, starting from its slope <code class=\"language-apl\">m<\/code>:<\/p>\n<pre><code class=\"language-apl\">   m = (y1-y0) \u00f7 (x1-x0)\r\n   (y-y0) = m \u00d7 (x-x0)\r\n   y = y0 + m \u00d7 (x-x0)\r\n<\/code><\/pre>\n<p>Therefore, if <code class=\"language-apl\">\u237a<\/code> is a 2-by-2 matrix of the two points and <code class=\"language-apl\">\u2375<\/code> are the x-values to be interpolated, then:<\/p>\n<pre><code class=\"language-apl\">   g \u2190 {(\u2283\u233d\u237a)+(\u2375-\u2283\u237a)\u00f7\u00f7\/-\u233f\u237a}\r\n\r\n   \u22a2 M\u21901 4 6,\u236a20 80 82\r\n1 20\r\n4 80\r\n6 82\r\n\r\n   M[0 1;] g 2 3\r\n40 60\r\n   M[1 2;] g 5\r\n81\r\n<\/code><\/pre>\n<h2>A New Twist, A New Solution<\/h2>\n<p>The problem as posed implicitly required that:<\/p>\n<ul>\n<li>The x-values are the positive integers bounded by <code class=\"language-apl\">\u2283\u2296M<\/code>.<\/li>\n<li>Appropriate rows of the matrix are selected for a given x-value.<\/li>\n<li>The missing x-values and their interpolations are &#8220;slotted back&#8221; into the argument matrix.<\/li>\n<\/ul>\n<p>These requirements are best met by <code class=\"language-apl\">\u2378<\/code>, <em>interval index<\/em>, a relatively new primitive function introduced in Dyalog APL version 16.0. The left argument <code class=\"language-apl\">\u237a<\/code> must be sorted and partitions the universe into disjoint contiguous intervals; <code class=\"language-apl\">\u237a\u2378\u2375<\/code> finds the index of the interval which contains an item of <code class=\"language-apl\">\u2375<\/code>. The result is <code class=\"language-apl\">\u2395io<\/code> dependent.<\/p>\n<p>For the given matrix <code class=\"language-apl\">M<\/code>, the partition (of the real numbers in this case) is depicted below. As in conventional mathematical notation, <code class=\"language-apl\">[<\/code> denotes that the interval includes the left end-point and <code class=\"language-apl\">)<\/code> denotes that the interval excludes the right end-point.<\/p>\n<pre><code class=\"language-apl\">          1        4      6\r\n\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500)[\u2500\u2500\u2500\u2500\u2500\u2500\u2500)[\u2500\u2500\u2500\u2500\u2500)[\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\r\n     \u00af1       0       1       2\r\n\r\n   v\u2190\u00af5 0 1 2.5 6 3 4 5 9 8 7\r\n\r\n   1 4 6 \u2378 v\r\n\u00af1 \u00af1 0 0 2 0 1 1 2 2 2\r\n\r\n   v ,[\u00af0.5] 1 4 6 \u2378 v\r\n\u00af5  0 1 2.5 6 3 4 5 9 8 7\r\n\u00af1 \u00af1 0 0   2 0 1 1 2 2 2\r\n<\/code><\/pre>\n<p>With <code class=\"language-apl\">\u2378<\/code> in hand, the problem can be solved as follows:<\/p>\n<pre><code class=\"language-apl\">interpol\u2190{\r\n  (x y)\u2190\u2193\u2349\u2375\r\n  m\u2190m,\u2283\u233dm\u2190(2-\/y)\u00f7(2-\/x)\r\n  j\u21900\u2308x\u2378i\u21901+\u2373\u2283\u233dx\r\n  i,\u236ay[j]+m[j]\u00d7i-x[j]\r\n}\r\n\r\n   interpol M\r\n1 20\r\n2 40\r\n3 60\r\n4 80\r\n5 81\r\n6 82\r\n<\/code><\/pre>\n<p>The problem of x-values less than the first end-point is finessed by applying <code class=\"language-apl\">0\u2308<\/code> to the interval indices, and that of x-values greater than or equal to the last end-point is finessed by repeating the last slope <code class=\"language-apl\">m\u2190m,\u2283\u233dm<\/code>.<\/p>\n<p>It is possible to do the interpolation only on the missing indices (2 3 5 in this case) and insert them into the argument matrix. It seems neater to simply interpolate everything, and in so doing provide a check that the interpolated values equal the values given in the argument.<\/p>\n<h2>An Alternative Interpolation<\/h2>\n<p>Interpolating according to two selected rows of a matrix of points treats the function as piecewise linear, with sharp inflection points where the lines join (different slopes between adjacent lines). A \u201cholistic\u201d alternative approach is possible: the matrix can be interpreted as specifying a single line and the interpolation is according to this single line. The <code class=\"language-apl\">\u2339<\/code> primitive function computes the coefficients of the line which best fits the points:<\/p>\n<pre><code class=\"language-apl\">   \u2395rl\u21907*5  \u235d for reproducible random numbers\r\n\r\n   \u22a2 M\u2190t,\u236a(?7\u23745)+\u00af17+3\u00d7t\u2190?7\u2374100\r\n35  89\r\n98 278\r\n19  44\r\n 4  \u00af5\r\n62 170\r\n49 133\r\n25  59\r\n\r\n   M[;1] \u2339 1,M[;,0]    \u235d y-intercept and slope\r\n\u00af15.3164 2.99731\r\n\r\n   interpola \u2190 {(1,\u23640\u22a2\u2375)+.\u00d7\u237a[;1]\u23391,\u237a[;,0]}\r\n\r\n   M[;1] ,[\u00af0.5] M interpola M[;0]\r\n89      278    44      \u00af5       170     133     59     \r\n89.5895 278.42 41.6325 \u00af3.32713 170.517 131.552 59.6164\r\n\r\n   M interpola 33 35 37 39.7\r\n83.5949 89.5895 95.5841 103.677\r\n<\/code><\/pre>\n<h2>Finally<\/h2>\n<p>Our best wishes to the intern. Welcome to APL!<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u2395io=0 assumed throughout; works in 1-origin with the obvious modifications. Introduction On Wednesday, a question arrived via Dyalog Support from an intern in Africa: If M is the matrix on the left, use linear interpolation to compute the result on &hellip; <a href=\"https:\/\/www.dyalog.com\/blog\/2018\/04\/linear-interpolation\/\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":13,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8],"tags":[],"class_list":["post-4055","post","type-post","status-publish","format-standard","hentry","category-apl-language"],"_links":{"self":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts\/4055","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/users\/13"}],"replies":[{"embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/comments?post=4055"}],"version-history":[{"count":8,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts\/4055\/revisions"}],"predecessor-version":[{"id":5080,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/posts\/4055\/revisions\/5080"}],"wp:attachment":[{"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/media?parent=4055"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/categories?post=4055"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.dyalog.com\/blog\/wp-json\/wp\/v2\/tags?post=4055"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}