Category Archives: Mathematics

Introducing Operator Delta

The r^{th} order finite difference of functionf(x) is defined by

\Delta^r f(x) = \begin{cases} f(x+1)-f(x), r=1\\ \Delta(\Delta^{r-1}f(x)), r > 1\end{cases}

From this definition, we have

\Delta f(x) = \Delta^1 f(x) = f(x+1)-f(x)

and,

\Delta^2 f(x) = \Delta (\Delta^{2-1} f(x))

= \Delta (\Delta f(x))

= \Delta( f(x+1)-f(x))

= (f(x+2)-f(x+1)) - (f(x+1)-f(x))

= f(x+2)-2f(x)+f(x+1)

as well as

\Delta^3 f(x) = \Delta (\Delta^2 f(x))

= \Delta (f(x+2)-2f(x)+f(x+1))

= (f(x+3)-2f(x+1)+f(x+2)) - (f(x+2)-2f(x)+f(x+1))

= f(x+3)-3f(x+2)+3f(x+1)-f(x)

The function shown below generates \Delta^r f(x), r:1\rightarrow 5 (see Fig. 1).

delta_(g, n) := block(
    local(f),
    
    define(f[1](x), 
           g(x+1)-g(x)),

    for i : 2 thru n do (
        define(f[i](x), 
               f[i-1](x+1)-f[i-1](x))
    ),

    return(f[n])
);

Fig. 1

Compare to the result of expanding (f(x)-1)^r=\sum\limits_{i=0}^r(-1)^i \binom{r}{i} f(x)^{r-i}, r:1\rightarrow 5 (see Fig. 2)

Fig. 2

It seems that

\Delta^r f(x) = \sum\limits_{i=0}^r(-1)^i \binom{r}{i} f(x+r-i)\quad\quad\quad(1)

Lets prove it!

We have already shown that (1) is true for r= 1, 2, 3.

Assuming (1) is true when r=k-1 \ge 4:

\Delta^{k-1} f(x) = \sum\limits_{i=0}^{k-1}(-1)^i \binom{r}{i} f(x+k-1-i)\quad\quad\quad(2)

When r=k,

\Delta^k f(x) = \Delta(\Delta^{k-1} f(x))

\overset{(2)}{=}\Delta (\sum\limits_{i=0}^{k-1}(-1)^i \binom{k-1}{i}f(x+k-1-i))

=\sum\limits_{i=0}^{k-1}(-1)^i \binom{k-1}{i}f(x+1+k-1-i)-\sum\limits_{i=0}^{k-1}(-1)^i \binom{k-1}{i}f(x+k-1-i)

=(-1)^0 \binom{k-1}{0}f(x+k-0)

+\sum\limits_{i=1}^{k-1}(-1)^i \binom{k-1}{i}f(x+k-i)-\sum\limits_{i=0}^{k-2}(-1)^i \binom{k-1}{i}f(x+k-1-i)

-(-1)^{k-1}\binom{k-1}{k-1}f(x+k-1-(k-1))

\overset{\binom{k-1}{0} = \binom{k-1}{k-1}=1}{=}

f(x+k)+ \sum\limits_{i=1}^{k-1}(-1)^i \binom{k-1}{i}f(x+k-i)-\sum\limits_{i=0}^{k-2}(-1)^i \binom{k-1}{i}f(x+k-1-i) -(-1)^{k-1}f(x)

=f(x+k)+ \sum\limits_{i=1}^{k-1}(-1)^i \binom{k-1}{i}f(x+k-i)+\sum\limits_{i=0}^{k-2}(-1)^{i+1}\binom{k-1}{i}f(x+k-1-i) -(-1)^{k-1}f(x)

\overset{j=i+1, i:0 \rightarrow k-2\implies j:1 \rightarrow k-1}{=}

f(x+k)+ \sum\limits_{i=1}^{k-1}(-1)^i\binom{k-1}{i}f(x+k-i) + \sum\limits_{j=1}^{k-1}(-1)^j \binom{k-1}{j-1}f(x+k-j)-(-1)^{k-1}f(x)

= f(x+k)+ \sum\limits_{i=1}^{k-1}(-1)^i\binom{k-1}{i}f(x+k-i) + \sum\limits_{i=1}^{k-1}(-1)^i\binom{k-1}{i-1}f(x+k-i)+(-1)^k f(x)

= f(x+k) + \sum\limits_{i=1}^{k-1}(-1)^i f(x+k-i) (\binom{k-1}{i} + \binom{k-1}{i-1})+(-1)^k f(x)

\overset{\binom{k-1}{i} + \binom{k-1}{i-1}=\binom{k}{i}}{=}

f(x+k)+ \sum\limits_{i=1}^{k-1}(-1)^i \binom{k}{i} f(x+k-i)+(-1)^k f(x)

= (-1)^0 \binom{k}{0}f(x+k-0)+\sum\limits_{i=1}^{k-1}(-1)^i \binom{k}{i} f(x+k-i)+(-1)^k \binom{k}{k} f(x+k-k)

= \sum\limits_{i=0}^{k}(-1)^i \binom{k}{i} f(x+k-i)

Advertisements

Finite Difference Approximations of Derivatives

We will derive the finite difference approximations for y'(x) and y''(x).

Let

y'_i, y''_i denotes y'(x_i) and y''(x_i) respectively

and

h = x_{i+1}-x_i = x_i -x_{i-1} > 0.

We prove that

[1] y_i' \approx \frac{y_{i+1} - y_i}{h}

Let x=x_{i+1}, a=x_i, Taylor series

y(x) = y(a) + y'(a) (x-a) +  O((x-a)^2)

is

y(x_{i+1}) = y(x_i) + y'(x_i)(x_{i+1}-x_i)+O((x_{i+1} - x_i)^2)

i.e.,

y_{i+1} = y_i + y'_i h + O(h^2)

Hence,

\frac{y_{i+1} -y_i}{h} = y'_i + O(h)


[2] y_i' \approx \frac{y_{i+1}-y_{i-1}}{2h}

Let x = x_{i+1}, a = x_i, Taylor series

y(x) = y(a) + y'(a) (x-a) + \frac{y''(a)}{2!} (x-a)^2 + O((x-a)^3)

becomes

y(x_{i+1}) = y(x_i) + y'(x_i)(x_{i+1}-x_i) + \frac{y''_i}{2!} (x_{i+1}-x_i)^2 + O((x_{i+1}-x_i)^3)

It follows that

y_{i+1}= y_i + y'_i h + \frac{y''_i}{2!} h^2 + O(h^3)\quad\quad\quad(1)

Similarly, let x=x_{i-1}, a = x_i,

y_{i-1}= y_i + y'_i (x_{i-1}-x_1) + \frac{y''_i}{2!} (x_{i-1}-x_i)^2 + O((x_{x-1}-x_i)^3

Since x_{i-1}-x_i = -(x_i - x_{i-1}) = -h, we have

y_{i-1} = y_i - y'_i h + \frac{y''_i}{2!} + O(h^3)\quad\quad\quad(2)

(1)-(2) \implies

y_{i+1}-y_{i-1} = 2y'_i h + O(h^3)

Therefore,

\frac{y_{i+1}-y_{i-1}}{2h} = y'_i + O(h^2)


[3] y_i'' \approx \frac{y_{i+1}-2y_i+y_{i-1}}{h^2}

Let x = x_{i+1}, a=x_i, Taylor series

y(x) = y(a) + y'(a) (x-a) + \frac{y''(a)}{2!} (x-a)^2 + \frac{y'''(a)}{3!} (x-a)^3 + O((x-a)^4)

becomes

y(x_{i+1}) = y(x_i) + y'(x_i) (x_{i+1}-x_i) + \frac{y''(x_i)}{2!} (x_{i+1} - x_i)^2

+ \frac{y'''(x_i)}{3!}(x_{i+1} - x_i)^3 + O((x_{i+1}-x_{i})^4).

That is,

y_{i+1} = y_i + y_i' h + \frac{y_i''}{2!} h^2 +  \frac{y_i'''}{3!} h^3  + O(h^4)\quad\quad\quad(3)

Similarly, let x = x_{i-1}, a=x_i, we have

y(x_{i-1}) = y(x_i) + y'(x_i) (x_{i-1}-x_i) + \frac{y''(x_i)}{2!} (x_{i-1} - x_i)^2

+ \frac{y'''(x_i)}{3!}(x_{i-1} - x_i)^3 + O((x_{i-1}-x_{i})^4).

i.e.,

y_{i-1} = y_i - y_i' h + \frac{y_i''}{2!} h^2 - \frac{y_i'''}{3!} h^3  + O(h^4)\quad\quad\quad(4)

(3) + (4) \implies

y_{i+1}+y_{i-1} = 2y_i +y_i'' h^2 + O(h^4).

Therefore,

\frac{y_{i+1}-2y_i+y_{i-1}}{h^2} = y_i'' + O(h^2)

A pair of non-identical twins

A complex number x + i y can be plotted in a complex plain where the x coordinate is the real axis and the y coordinate the imaginary.

Let’s consider the following iteration:

z_{n+1} = z_{n}^2 + c\quad\quad\quad(1)

where z, c are complex numbers.

If (1) are started at z_0 = 0 for various values of c and plotted in c-space, we have the Mandelbrot set:

When c is held fixed and points generated by (1) are plotted in z-space, the result is the Julia set:

Constructing the tangent line of circle without calculus

The tangent line of a circle can be defined as a line that intersects the circle at one point only.

Put a circle in the rectangular coordinate system.

Let (x_0, y_0) be a point on a circle. The tangent line at (x_0, y_0) is a line intersects the circle at (x_0, y_0) only.

Let’s first find a function y=kx+m that represents the line.

From circle’s equation x^2+y^2=r^2, we have

y^2=r^2-x^2

Since the line intersects the circle at (x_0, y_0) only,

r^2-x^2=(kx+m)^2

has only one solution.

That means

k^2x^2+x^2+2kmx+m^2-r^2 =0

has only one solution. i.e., its discriminant

(2km)^2-4(k^2+1)(m^2-r^2)=0\quad\quad\quad(1)

By the definition of slope,

kx+m-y_0 = k(x-x_0).

It follows that

m =y_0-kx_0\quad\quad\quad(2)

Substitute (2) into (1) and solve for k gives

k = \frac{-x_0}{y_0}\quad\quad\quad(3)

The slope of line connecting (0, 0) and (x_0, y_0) where x_0 \neq 0 is \frac{y_0}{x_0}.

Since \frac{-x_0}{y_0}\cdot \frac{y_0}{x_0} = -1, the tangent line is perpendicular to the line connecting (0, 0) and (x_0, y_0).

Substitute (3) into y = k x +m, we have

y=-\frac{x_0}{y_0} x + m\quad\quad\quad(4).

The fact that the line intersects the circle at (x_0, y_0) means

y_0 = -\frac{x_0^2}{y_0} + m

or

y_0^2=-x_0^2+ my_0.

Hence,

m =\frac{x_0^2+y_0^2}{y_0} =  \frac{r^2}{y_0}.

It follows that by (4),

x_0 x +y_0 y = r^2\quad\quad\quad(5)

(5) is derived under the assumption that y_0 \neq 0. However, by letting y_0 =0 in (5), we obtain two tangent lines that can not be expressed in the form of y=kx+m:

x=-r, x=r

Constructing the tangent line of quadratic without calculus

The tangent line of a quadratic function at (x_0, y_0)is a line y=kx+m that intersects y=ax^2+bx+c at (x_0, y_0=ax_0^2+bx_0+c) only.

The presence of function y=kx+m immediately excludes the vertical line x=x_0 which also intersects y=ax^2+bx+c at (x_0, ax_0^2+bx_0+c) only (see Fig. 1).

Fig. 1

Let’s find k.

Line y = kx+m intersects y=ax^2+bx+c at (x_0, ax_0^2+bx_0+c) only means quadratic equation

ax^2+bx +c =kx +m

has only one solution. That is, the discriminant of ax^2+bx+c-kx-m =0 is zero:

(b-k)^2-4a(c-m) = 0\quad\quad\quad(1)

Fig. 2

And, by the definition of slope (see Fig. 2),

(x-x_0)k = (kx+m)-(ax_0^2+bx_0+c).

It follows that

m = (ax_0^2+b_0+c)-x_0 k\quad\quad\quad(2)

Substituting (2) into (1), we have

(b-k)^2-4a(c-((a_0 x^2+b x_0 + c)-x_0 k)=0.

Solve it for k gives

k = 2 a x_0 +b.

Fig. 3