9
\$\begingroup\$

My preferred way to approximate a derivative is the central difference, its more accurate than forward difference or backward difference, and I'm too lazy to go higher-order. But the central difference requires a data point on either side of point you are evaluating. Normally this means you end up not having a derivative at either endpoint. To solve it, I want you to switch to forward and backward difference at the edges:

Specifically, I want you to use a forward difference for the first point, a backward difference for the last point, and a central difference for all the points in the middle. Also, you can assume x values are evenly spaced, and focus only on y. Use these formulas:

enter image description here

Good luck, I'm looking forward to seeing if someone comes up with a simple rule which reproduces all 3 derivatives in the right places!

EX INPUT:

0.034  9.62    8.885   3.477   2.38

I will use FD, CD, and BD to denote which algorithm to use in which spot, so above 5 points are used to approximate derivatives using

FD     CD      CD      CD     BD

And then the calculated values would be:

9.586  4.4255 -3.0715 -3.2525 -1.097 

You can assume that there will always be at least 3 input points, and you can calculate using single or double precision.

And as always, shortest answer wins.

\$\endgroup\$
  • 3
    \$\begingroup\$ Just a nitpick, central/forward/backward differences are just approximations of derivatives at a point, not the derivatives themselves. \$\endgroup\$ – Liam Jun 21 '16 at 22:08
  • \$\begingroup\$ I don't understand what each input and output number corresponds to. \$\endgroup\$ – xnor Jun 21 '16 at 23:26
  • \$\begingroup\$ @xnor, i put a brief description between the input and output explaining what algorithm to use for which data point. Does it make sense now? \$\endgroup\$ – Tony Ruth Jun 21 '16 at 23:29
  • \$\begingroup\$ Yes, I think it makes sense. For 5 inputs, you'd do [a,b,c,d,e] -> [b-a,(c-a)/2,(d-b)/2,(e-c)/2,e-d]. Can there be fewer that 3 input points? \$\endgroup\$ – xnor Jun 21 '16 at 23:35
  • \$\begingroup\$ @xnor, that's right. And, I updated so you can assume at least 3 input points. \$\endgroup\$ – Tony Ruth Jun 21 '16 at 23:37

10 Answers 10

4
\$\begingroup\$

Jelly, 13 10 bytes

I.ịṚjI+2\H

Try it online!

How it works

I.ịṚjI+2\H  Main link. Argument: A (array)

I           Increments; compute the deltas of consecutive values.
            For [a, b, c, d, e], this yields [b-a, c-b, d-c, e-d].
 .ị         At-index 0.5; get the the last and first element.
            This yields [e-d, b-a].
   Ṛ        Reverse the pair.
            This yields [b-a, e-d].
    jI      Join, separating by the increments.
            This yields [b-a, b-a, c-b, d-c, e-d, e-d].
      +2\   Add the values of all overlapping pairs.
            This yields [2(b-a), c-a, d-b, e-c, 2(e-d)].
         H  Halve all resulting numbers.
            This yields [b-a, (c-a)/2, (d-b)/2, (e-c)/2, e-d]. 
\$\endgroup\$
3
\$\begingroup\$

MATL, 21 15 bytes

2/d1)6Mh8Mt0)h+

TryItOnline

Halves the input vector, and takes successive differences, to give d=[i(2)-i(1) i(3)-i(2) ... i(end)-i(end-1)]/2 and then makes two modified vectors, [d(1) d] and [d d(end)], and adds them.

The older version was better (because convolution), but 21 bytes

d1j)6M1)6MTT2/H3$Y+bv
\$\endgroup\$
  • 1
    \$\begingroup\$ I see, pretty clever. So you take a list of forward differences, and a list of backwards differences and average them to get the central difference. Then the endpoints are fixed by instead averaging 2 forward differences or 2 backward differences (in the same spot). Since the forward and backward difference are just shifted from each other by one spot, you get to reuse a lot of structure. \$\endgroup\$ – Tony Ruth Jun 22 '16 at 21:41
  • \$\begingroup\$ Just forward differences, otherwise yes. Doing (y(i)-y(i-1))+(y(i+1)-y(i)) gives y(i+1)-y(i-1), which is twice the centred difference. \$\endgroup\$ – David Jun 22 '16 at 22:35
3
\$\begingroup\$

Python with NumPy, 29 bytes

import numpy;numpy.gradient

This happens to be the default behaviour of NumPy's gradient function. The bytes were counted according to this consensus.

\$\endgroup\$
1
\$\begingroup\$

05AB1E, 20 19 17 14 bytes

¥Ð¦øO;s¤s0èŠ)˜

Explained

¥Ð              # triplicate deltas of list
                  [9.585999999999999, -0.7349999999999994, -5.4079999999999995, -1.097]
  ¦øO;          # get central difference (fold addition over deltas and divide by 2)
                  [4.4254999999999995, -3.0714999999999995, -3.2524999999999995]
      s¤        # get backwards difference
                  -1.097
        s0è     # get forwards difference
                  9.585999999999999
           Š)˜  # reorder differences, merge to list and flatten
                  [9.585999999999999, 4.4254999999999995, -3.0714999999999995, -3.2524999999999995, -1.097]

Try it online

Saved 2 bytes thanks to @Adnan

\$\endgroup\$
1
\$\begingroup\$

Julia, 8 bytes

gradient

Inspired by @MartinEnder's Python answer. Try it online!

\$\endgroup\$
  • \$\begingroup\$ This also works in Matlab and in Octave \$\endgroup\$ – Luis Mendo Jun 22 '16 at 17:05
1
\$\begingroup\$

Pyth, 14 bytes

.OM>L2._seB-Vt

Try it online: Demonstration

Explanation:

.OM>L2._seB-VtQQ   implicitly add two Qs (input arrays) at the end
           -VtQQ   get all neighbored differences
        seB        get the last element of ^ and append it to ^
      ._           compute all prefixes
   >L2             reduce all prefixes to the last two elements
.OM                compute the average of each ^
\$\endgroup\$
1
\$\begingroup\$

J, 21 bytes

[:((,{:)+{.,])2-~/\-:

Similar to the approach used in @David's solution.

Usage

   f =: [:((,{:)+{.,])2-~/\-:
   f 0.034 9.62 8.885 3.477 2.38
9.586 4.4255 _3.0715 _3.2525 _1.097

Explanation

[:((,{:)+{.,])2-~/\-:  Input: list A
                   -:  Halve each value in A
              2   \    Select each overlapping sublist of size 2 in A
               -~/     Reduce it using subtraction to get the difference
[:(          )         Operate on the list of differences, call it D
            ]          Identity function, returns D
         {.            Get the head of D
           ,           Join them to get [head(D), D]
   ( {:)               Get the tail of D
    ,                  Join them to get [D, tail(D)]
        +              Add them together elementwise to get the derivatives and return
\$\endgroup\$
0
\$\begingroup\$

Pyth - 29 bytes

Stupid simple approach.

s[_-F<Q2mc-@Qhd@Qtd2tUtQ_-F>2

Try it online here.

\$\endgroup\$
0
\$\begingroup\$

JavaScript (ES6), 62 bytes

a=>a.map((_,i)=>i&&i--<a.length-2?(a[i+2]-a[i])/2:a[i+1]-a[i])
\$\endgroup\$
0
\$\begingroup\$

Pyth, 27 24 23 21 bytes

.bcF_-VNYK++]hJ,VUQQJ]eJttK
.bcF-VYN+]hJ,VQUQJ+tJ]eJ
++hJ-V+tQeQ+hQQcR2PtJeJ
*V++1*].5ttlQ1-V+tQeQ+h
*V++1m.5ttQ1-V+tQeQ+h

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.