The Lanczos Derivative

THE LANCZOS DERIVATIVE Abstract. The Lanczos derivative is attributed to Hungarian mathematician Cornelius Lanczos who developed it in the 1950s. It is an integral based derivative derived from the least squares model. The Lanczos derivative is set apart from other forms of differentiation such as the symmetric and traditional derivatives because it exists for functions where the other derivatives do not. 1. The Definition of the Lanczos Derivative 1.1. Overview of the Least Squares Model. Since the earliest times, humans have been making and recording observations of the world around them. As this process of data collection became more sophisticated, the demand for an accurate mathematical representation of this data also increased. One of the major problems mathematicians faced was the problem of error in physical observations mainly due to human and instrumental imperfections. In the beginning of the 19th century, Carl Friedrich Gauss came up with a “fix” to this problem by using the argument that greater and smaller errors are equally possible in all equations. His process, which became known as the “method of least squares,” found the parameters at which the sum of the squares of the errors was minimized. Today, the method remains an important statistical tool used in many fields such as business, engineering, and marketing. Assume we have a set of discrete data: y1 , y2 , ..., yn . The least squares method finds the function f (k) such that n X (f (k) − yk )2 k=1 1 2 is a minimum. In this section we will look at how the mathematician Cornelius Lanczos used this least squares model to derive a method of differentiation. 1.2. Finding the Derivative. A simple way to approximate the slope between consecutive data points would be to take the change in y and divide it by the change in x. Unfortunately, any kind of error in y would greatly skew the result. Thus, it would be advantageous to use more points, the idea being that the slope changes little over the span of consecutive points. Although one can look at any number of points at a time, we will start by looking at five points y−2 , y−1 , y0 , y1 , and y2 , and assume they lie closely to a parabola. Therefore, let’s use the formula f (k) = a + bk + ck 2 , where a, b, c are coefficients which can be adjusted for our data. Using the least squares method, we set up the function 2 X (f (k) − yk )2 . k=−2 By minimizing the sum of these squares with respect to a, b, c, we will find the best fit parabola. Thus, the function we want to minimize looks like 2 X  2 (a + bk + ck 2 ) − yk . (1) k=−2 Since we are trying to find the value of the derivative of at x = 0, we can differentiate f (k) = a + bk + ck 2 and get f 0 (0) = b. Hence it is the constant b we are interested in. The condition of minimum with respect to b gives us 0 = −4(a − 2b + 4c − y−2 ) − 2(a − b + c − y−1 ) + 2(a + b + c − y1 ) + 4(a + 2b + 4c − y2 ). THE LANCZOS DERIVATIVE 3 All the constants except for b cancel out resulting in b= −2y−2 − y−1 + y1 + 2y2 . 10 So far we have worked under the assumption that we have five data points. Let’s assume instead that the number of data points is 2n + 1, which would therefore give us a more general equation for approximating the derivative. The sum in (1) is the function which we then differentiated in terms of b and set equal to 0. By doing this, we found our approximate derivative b. By doing this same process, only with 2n + 1 data points instead of five, we get n X k=−n   2k (a + bk + ck 2 ) − yk = 0. Since again, the coefficients a and c drop out, our equation becomes 0 = n X 2k(bk − yk ) k=−n n X 2k 2 b = k=−n n X 2kyk k=−n b = n X kyk k=−n n X 2 . k 2 k=1 Here we have assumed that our interval between consecutive observations is one. If we make that interval instead h, we must divide our derivative by the length h and the formula of differentiation for our empirical function becomes (2) b= n X kf (x + kh) k=−n 2 n X k=1 . 2 k h 4 Thus far we have looked only at functions with discrete variables. Let’s assume that we have a dense group of observations, each observation very close to the next. Since we are looking at a very dense group of observations, our sum becomes an integral. We can then rewrite b as b= R − tf (x + t)dt 23 3 3 = 3 2 Z  tf (x + t)dt, − where  is sufficiently small. From here, Lanczos derived the formula for differentiation fL0 (x) (3) 3 = lim 3 →0 2 Z  tf (x + t)dt. − This is the definition of the Lanczos derivative.[2] 1.3. Illustration of the Derivative. Let’s do an example and find the Lanczos derivative of f (x) = x3 . Using the formula, we get Z  3 0 fL (x) = lim 3 t(x + t)3 dt →0 2 −   3 1 2 3 3 4 1 5 2 3 = lim 3 t x + x t + xt + t →0 2 2 4 5 −   3 = lim 3x2 + 2 →0 5 2 = 3x which is, as we should expect, the traditional derivative of x3 . 2. The Accuracy of the Lanczos Derivative Looking at the error of the Lanczos derivative sheds light on both the basic uses and the limitations of the derivative. 2.1. The Lanczos Derivative and the Taylor Series. Let’s assume we can use the Taylor series to represent the function in the Lanczos formula f (x + t). Recall that the Taylor series representation of f (x) centered at x = a is f (x) = f (a) + f 0 (a)(x − a) f 00 (a)(x − a)2 f (3) (a)(x − a)3 + + + ··· . 1! 2! 3! THE LANCZOS DERIVATIVE 5 Let’s choose x as the center of f (x + t) where x is fixed and t varies. Therefore, the Taylor series representation looks like f (x + t) = f (x) + t 0 t2 t3 f (x) + f 00 (x) + f (3) (x) + · · · . 1! 2! 3! We can then find the Lanczos derivative using this sum Z  3 0 tf (x + t)dt fL (x) = lim 3 →0 2 −   3 1 2 1 t3 0 1 t4 00 = lim 3 · t f (x) + · f (x) + · f (x) + · · · →0 2 2 3 1! 4 2!  . − Looking at the Lanczos derivative as an infinite sum can give us some interesting insight into how the Lanczos derivative behaves. If we look at this integral, we can see that all the even powers of t are going to cancel each other out when we substitute ± in for t while our odd powers of t double. Therefore, our derivative becomes   1 2 (3) 0 0 fL (x) = lim f (x) +  f (x) + · · · . →0 10 Thus, the Lanczos derivative does in fact equal f 0 (x) with an error of the order 2 . In Lanczos’ Applied Analysis, he talks about how this error, which he calls “noise,” typically destroys the analytical nature of f (x).[2] Yet Lanczos argues that this error is greatly diminished by the randomness of the errors, which through summation, balances itself out. 2.2. A closer look at the Error of the Lanczos Derivative. In Lanczos’ Generalized Derivative,[3] C. W. Groetsch analyzes more closely the error of the Lanczos derivative. Small errors in the function values are magnified by a factor of 3 . 2 This, Groetsch states, “is not a deficiency in the method, but rather a manifestation of the inherent instability of the differentiation process itself.”[3] To look at this more closely, let us allow f h (t) to be some bounded integrable perturbation of f where |f (t) − f h (t)| ≤ h and h is a known error bound. If we let 6 fL0 (t) be the Lanczos derivative, then
0
0 | f h L (x) − f 0 (x)| ≤ |fL0 (x) − f 0 (x)| + | f h L (x) − fL0 (x)|. Earlier we found that the error of the Lanczos derivative was 2 (3) f (x) 10 by using the Taylor series representation. Let us assume f (3) exists and is bounded by M . Then we can say |fL0 (x) − f 0 (x)| ≤ We can also see that
0 f h L (x) − fL0 (x) M 2  . 10 Z  3 = tf h (x + t) − tf (x + t)dt 23 − Z  3 3h ≤ |t| hdt = . 23 − 2 We can then find our total error by adding these two together, and we get M 2 3h  + . 10 2 Groetsch calls the first error the truncation error because it goes to fh
0 (x) − f 0 (x) ≤ L zero as  → 0. The second error is called the stability error; it blows up as  → 0. Therefore, it’s necessary to find a balance between the two errors to stay between ‘the two numerical hazards.’ 3. The Traditional and Symmetric Derivatives Before we go further into our analysis of the Lanczos derivative, it makes sense to compare it to other forms of differentiation with which we are probably more familiar. In this section we will look at the traditional and symmetric derivatives and see how their properties compare to the Lanczos derivative. 3.1. The Traditional Derivative. The traditional derivative finds the slope by looking at the ordered pairs (x, f (x)) and (x + h, f (x + h)) and finding the rise over run between these points as h → 0: (4) f (x + h) − f (x) . h→0 h f 0 (x) = lim THE LANCZOS DERIVATIVE 7 A function is differentiable at a point x if the limit exists. Otherwise, the function is not differentiable. 3.2. The Symmetric Derivative. The symmetric derivative is similar to the traditional derivative. The difference between the two is that the symmetric derivative (5) fs0 (x) = lim h→0 f (x + h) − f (x − h) 2h uses the points (x − h, f (x − h)) and (x + h, f (x + h)) which lie on either side of (x, f (x)) while the traditional derivative uses the point (x, f (x)) as one of its two points of interest. 3.3. Comparison of the Traditional and Symmetric Derivatives. Theorem 3.1. If f 0 (x) exists, then fs0 (x) exists. Proof. Let f (x) be differentiable at x = a. Therefore, f (a + h) − f (a) h→0 h exists. The symmetric derivative can be rewritten as f 0 (a) = lim f (a + h) − f (a − h) 2h   f (a + h) − f (a) f (a) − f (a − h) + = lim . h→0 2h 2h fs0 (a) = lim h→0 Since f 0 (a) exists, then 1 f (a + h) − f (a) 1 f (a + (−h)) − f (a) · + · 2 h 2 (−h) has a limit of f 0 (a) as h → 0. Therefore, fs0 (a) = f 0 (a) also exists.  It’s important to note that if fs0 (x) exists, f 0 (x) need not exist.[4] One example of this is the derivative of f (x) = |x| at x = 0. With the traditional derivative, we come to a problem: |h| |0 + h| − |0| = lim h→0 h h→0 h f 0 (0) = lim 8 The limit does not exist, and therefore the function is not differentiable at x = 0. Under fs0 (x), we get a different outcome: |0 + h| − |0 − h| 0 = lim = 0. h→0 h→0 2h 2h fs0 (0) = lim Therefore, the derivative under this method exists and equals 0. The symmetric derivative gives us another method to compute the slope when the traditional one does not work. 3.4. Comparison of the Symmetric and Lanczos Derivatives. When we were constructing the Lanczos derivative, we computed formula (2) k X nf (x + nh) n=−k 2 k X . n2 h n=1 We were able to obtain the Lanczos derivative from (2) by assuming that our interval h became infinitely small as our number of points n became infinitely dense. If we look at (2) when n = 1, our function looks surprisingly familiar. We obtain −f (x − h) + f (x + h) . 2h Letting h → 0, we get the exact definition of the symmetric derivative. If we let n = 2, our new equation becomes −2f (x − 2h) − f (x − h) + f (x + h) + 2f (x + 2h) . 10h With a little mathematical manipulation, we can rewrite this as 4 f (x + 2h) − f (x − 2h) 1 f (x + h) − f (x − h) 4 1 · + · = fs0 + fs0 = fs0 . 5 4h 5 2h 5 5 THE LANCZOS DERIVATIVE 9 This trend continues. If we were to continue to compute the slope for varying values of n, we would see that k X nf (x + nh) n=−k 2 k X = n2 h n=1 12 22 k2 0 0 f + f + · · · + fs0 = fs0 . s s k k k X X X n2 n2 n2 n=1 n=1 n=1 This sheds a new light on the Lanczos derivative. The symmetric derivative looks at this tiny interval on each side of x and averages the slope of each side. Lanczos uses the same idea, but uses an infinite number of these minute intervals to measure the gradient. His end outcome is that he uses integration to find its opposite process: differentiation. This seems strange initially, but when we gain an understanding of what we are actually computing, it makes complete sense. The symmetric derivative works by finding the slope over an interval and then letting the interval shrink to 0 whereas the Lanczos derivative works by finding the slope over many intervals, and then shrinking each of these intervals. Theorem 3.2. If fS0 (x) exists, then fL0 (x) exists. Proof. Recall that the definition of the Lanczos derivative is R tf (x + t)dt 3 . fL0 (x) = lim · − →0 2 3 This is of the 0 0 indeterminate form as  → 0, so if we assume that f is continuous, we can apply L’Hospital’s Rule and the Fundamental Theorem of Calculus to the limit to get 3 f (x + ) − f (x − ) f (x + ) − f (x − ) = fs0 (x). fL0 (x) = lim · = lim 2 →0 2 →0 3 2  Therefore, if f is continuous, the limit of the Lanczos derivative equals the symmetric derivative and therefore the Lanczos derivative exists everywhere the symmetric derivative does. 10 0.6 0.4 0.2 0.0 0.2 0.4 0.6 0.8 1.0 x Figure 1. The the graph of y = f (x) is a sequence of isosceles triangles which grow as x → ∞ 3.5. The Relationship of the Derivatives. Conjecture 3.1. Let T D, SD, and LD denote the class of continuous functions with a traditional derivative, symmetric derivative, and Lanczos derivative respectively. Then T D ⊆ SD ⊆ LD We have already shown that if the traditional derivative exists, then so too do the symmetric and therefore the Lanczos derivatives. We also saw that if the symmetric derivative exists, so does the Lanczos derivative. This is not a two way relationship, though. We have looked at an example where the symmetric derivative exists, but the traditional derivative does not. Is there an example where the Lanczos derivative exists, but the symmetric derivative (and hence also the traditional derivative) does not exist? This example is more difficult to construct and is considered in the next section. 4. A Function with solely a Lanczos Derivative The function f (x) shown in Figure 1 equals 0 when x < 0 and is comprised of isosceles triangles when x ≥ 0. Two corners of each THE LANCZOS DERIVATIVE triangle lie on the x-axis and we’ll label these points: r = l= 1 . n+1 11 1 n and The upper point of the triangle lies on the line y = x at the point (c, c) where c is the average of r and l. As x → 0, the triangles get infinitely small and the number of triangles approaches infinity. The equation of our function is f (x) = − c |x − c| + c for l ≤ x < r. c−l For x > 0 and x not lying on any corner of a triangle, we can fairly easily find the traditional derivative f 0 (x). We can simply treat the function like a piece-wise function and find the derivative of the linear equation over the interval containing the point of interest. The symmetric derivative would also exist for these points x, as well as the points at the triangle corners, the derivative in this case being the average slope of either side of the point. Therefore, the symmetric derivative exists for each point x > 0. At x = 0, though, the symmetric derivative no longer exists. Imagine a line going through the upper corner of each of the triangles. The equation of this line is y = x and therefore has a slope of 1. A line going through the lower corners of each of the triangles has a slope of 0. These contrasting values mean that the limit of the symmetric derivative does not exist. We do not run into this same problem with the Lanczos derivative. We can set up the Lanczos derivative with fL0 (0) where r = 1 , n   ∞ Z 3k 3 X r c = lim t − |t − c| + c dt k→∞ 2 c−l n=k l l = 1 , n+1 and c = 2n+1 . 2n(n+1) Our equation within the integral is f (x + t) when x = 0. Above, we have integrated over the interval of one triangle, and then found the sum for the infinite number of triangles, starting at x = 1 k and letting k → ∞. Since in this case,  = n1 , we have to make the proper adjustments to our equation. 12 We can evaluate the integral by changing our intervals so the absolute value can be removed:   Z r  Z r  c c t − |t − c| + c dt = t − (t − c) + c dt c−u c−u l c  Z c  c + t (t − c) + c dt. c−u l Then, we can rewrite the Lanczos derivative in terms of n to get "Z 1     ∞ n 3k 3 X 2n + 1 2n + 1 lim t −(2n + 1) t − + dt k→∞ 2 2n+1 2n(n + 1) 2n(n + 1) 2n(n+1) n=k    # Z 2n+1  2n(n+1) 2n + 1 2n + 1 + t (2n + 1) t − + dt . 1 2n(n + 1) 2n(n + 1) n+1 By evaluating the integrals, we obtain ∞ 3k 3 X (2n + 1)2 . 3 (n + 1)3 k→∞ 2 8n n=k fL0 (0) = lim (2n+1)2 n=k 8n3 (n+1)3 , let us 2 Since y = 8x(2x+1) 3 (x+1)3 is a In order to evaluate integral of (2x+1)2 8x3 (x+1)3 . P∞ compare the sum and the decreasing function when x > 0, 3k 3 2 Z ∞ k ∞ (2x + 1)2 3k 3 X (2n + 1)2 dx < . 8x3 (x + 1)3 2 n=k 8n3 (n + 1)3 Also, the fact that y is a decreasing function means that Z ∞ 3k 3 X (2n + 1)2 3k 3 ∞ (2x + 1)2 < dx 2 n=k+1 8n3 (n + 1)3 2 k 8x3 (x + 1)3 or   Z ∞ ∞ 3k 3 X (2n + 1)2 3k 3 (2k + 1)2 (2x + 1)2 < + dx 2 8n3 (n + 1)3 2 8k 3 (k + 1)3 8x3 (x + 1)3 k n=k Evaluating the integrals, we obtain ∞ 1 3k 3 X (2n + 1)2 3(2k + 1)2 1 < < + . 4 2 n=k 8n3 (n + 1)3 16(k + 1)3 4 THE LANCZOS DERIVATIVE 13 Taking the limit as k → ∞ of this inequality, we get ∞ 3k 3 X (2n + 1)2 1 1 ≤ lim ≤ . 3 3 4 k→∞ 2 8n (n + 1) 4 n=k Now we can use the Squeeze Theorem to find the limit of the sum. Theorem 4.1 (Squeeze Theorem). If f (x) ≤ g(x) ≤ h(x) when x is near a (except possibly at a) and lim f (x) = lim h(x) = L x→a x→a then lim g(x) = L x→a Therefore, from the Squeeze Theorem Z ∞ 3k 3 X (2n + 1)2 1 3k 3 ∞ (2x + 1)2 lim = = lim dx. k→∞ 2 8n3 (n + 1)3 4 k→∞ 2 k 8x3 (x + 1)3 n=k We can now find the limit of the Lanczos derivative through the integral test and L’Hospital’s rule: R ∞ (2t+1)2 3 3 x 8t3 (t+1)3 dt = lim · fL0 (0) = lim · 1 x→∞ x→∞ 2 2 x3 = −(2x+1)2 8x3 (x+1)3 −3 x4 3 (2x + 1)2 x 1 · = . x→∞ 2 24(x + 1)3 4 lim Therefore, the Lanczos method can find a derivative of our function of 14 , while the symmetric and traditional derivatives do not exist. The value 1 4 comes from the process of measuring the average derivative from, in this case, 0 to , over a dense number of intervals and then letting  → 0. 5. Conclusion Although Lanczos’ formula is a more tedious method for finding the derivative than the other more common definitions of differentiation, 14 the Lanczos derivative does carry some advantages over the other formulas. As we saw with the function of triangles, there are circumstances where other derivatives do not exist, but the Lanczos derivative does. This allows us to compute a ‘pseudo-derivative’ at places that are not differentiable under the traditional derivative. Overall, though, the significance is not in the ability of the derivative to compute a pseudo-derivative, but rather in the properties the derivative shares with other mathematical subjects. We looked at how the Lanczos derivative compares to other derivatives and the least squares method. Other topics that can be looked at in relation to the Lanczos derivative are higher order derivatives and Legendre polynomials. For example, we can use the least squares method to look at the Lanczos derivative function f (x + t). The equation Z  (f (x + t) − g(x))2 dt − where g(x) = an x + an−1 xn−1 + · · ·+ a1 x1 + a0 can be minimized, simin lar to the least squares process. The result we obtain by differentiating in terms of the highest order coefficient ends up being very similar to the nth order Legendre polynomial. There is much more that can be researched in this area that might explain why and how this phenomenon occurs. References [1] Bjorck, Ake. Numerical Methods for Least Squares Problems. Philadelphia: Society for Industrial and Applied Mathematics, 1996. [2] Lanczos, Cornelius. Applied Analysis. Englewood Cliffs, N.J.: Prentice Hall, 1961. [3] Groetsch, C. W. Lanczos’ Generalized Derivative. The American Mathematical Monthly; Apr 1998. [4] Poodiac, Robert P. The Symmetric Derivative and the Unit Circle 16 March 2004, http://www2.norwich.edu/rpodiac/cmjarticle2.pdf.