Basic discretization techniques

Could maybe do an "engineer" approach and a "mathematician" approach... Two ways of presenting the same material

Introduction

What are we trying to do?

Before discussing discretization, we must first discuss what we're discretizing

We start with some differential equation - either partial differential equation or ordinary differential equation

Let's say we have a function $ u $ of space and time $ x,t $

What is the general form of a partial differential equation for $ u $? (Introduction_to_partial_differential_equations)

$ F(x,t,u_x,u_xx,\dots,u_t,u_tt,\dots) = 0 $

Revisit example of heat equation, solved analytically using separation of variables (Analytical_solution_of_PDEs#Example_3:_Heat_Equation):

$ \Theta_t = \alpha^2 \Theta_{xx} $

How did we treat $ \Theta $? How did we solve the PDE? We assumed a form for the solution, plugged it in, and found out some additional information

For example, we assumed a solution of the form $ X(x) T(t) $, and then we found, for time:

$ T = c_1 \exp{( -\lambda^2 \alpha^2 t )} $

and something similar for $ X(x) $.

So the answer is: we solved the PDE by finding functions that satisfied certain conditions...

Solution approach:

• We assumed a form for the solution
  • Found two ordinary differential equations that the solution had to satisfy
• We then had a general solution (that worked for any boundary and initial conditions)
  • Found values for constants by plugging our boundary conditions into the general solution
• When then had a (less general) solution that worked for our boundary conditions, and worked for any initial conditions
  • Found values for the remaining constants by plugging our initial conditions into the solution
• Final result: we found a solution that worked for our boundary conditions and our initial conditions

Can we do this with a computer?

Short answer: not really.

Long answer: Yes, we can. But what happens when we have a complicated, nonlinear partial differential equation? A partial differential equation that has no analytical solution?

The point is: who cares if we can find analytical solutions with a computer? We want a different method that is more robust than analytical solutions

Functions are continuous. What is the opposite of continuous? Discrete - if we don't want an analytical (functional) solution, we need a discrete solution

Discrete - means, the solution only exists at discrete points, and is not an exact solution, but only an approximation

What is a derivative?

Limit definition of a derivative:

$ \frac{d u(x)}{dx} = \displaystyle{ \lim_{\Delta x \rightarrow 0} } \frac{ u(x_0 + \Delta x) - u(x_0) }{ \Delta x } $

This is saying, when $ \Delta x $ is "small enough", the algebraic difference $ \frac{ u(x_0 + \Delta x) - u(x_0) }{ \Delta x} $ is a good approximation for the derivative; if $ \Delta x $ is small enough, the representation becomes exact.

OK, so naturally we want to know: how small? How small does $ \Delta x $ have to be?

Using a Taylor series expansion for $ u(x_0 + \Delta x) $ in terms of $ u(x_0) $:

$ u(x_0 + \Delta x) = u(x_0) + \left. \frac{\partial u}{\partial x} \right|_{0} \Delta x + \left. \frac{\partial^2 u}{\partial x^2} \right|_{0} \frac{(\Delta x)^2}{2!} + \dots + \left. \frac{\partial^n u}{\partial x^n} \right|_{\xi} \frac{ (\Delta x)^n }{ n! } \qquad x_0 \leq \xi \leq x_0 + \Delta x $

What does the Taylor series tell us about how small $ \Delta x $ needs to be?

Rearrange the Taylor series to look like the limit definition of the derivative...

$ \left. \frac{\partial u}{\partial x} \right|_{x_0} = \frac{ u(x_0 + \Delta x) - u(x) }{ \Delta x } - \left. \frac{\partial^2 u}{\partial x^2} \right|_0 \frac{\Delta x}{2!} - \dots $

For a discrete representation, values of $ u $ can be indexed at each discrete point using some index $ i $, so that $ u_i = u(x_0) $, $ u_{i+1} = u(x_0 + \Delta x) $, etc...

$ \left. \frac{\partial u}{\partial x} \right|_{i} = \frac{ u_{i+1} - u_{i} }{ \Delta x } - \left. \frac{\partial^2 u}{\partial x^2} \right|_0 \frac{\Delta x}{2!} - \dots $

This is a forward difference.

Let's look at this last term... This is an "error" in our difference approximation. So we can replace it with:

$ - \left. \frac{ \partial^2 u}{\partial x^2} \right|_0 \frac{\Delta x}{2!} = O( \Delta ) $

where $ O() $ is the order of the error.

Tells us two things:

1. For the difference approximation of the derivative to be accurate, we have to have $ \Delta x $ become really small to make our error really small.

2. We ALSO need $ \frac{\partial^2 u}{\partial x^2} $ to be really small.

That means if we're trying to approximate a function with a large second derivative, we need an even smaller $ \Delta x $.

Applying this concept: the red line is a very high-order polynomial, and the blue line is a low-order polynomial.

Which one has a larger second derivative?

Which one will require a smaller $ \Delta x $?

We didn't get an exact answer to the question "how big should $ \Delta x $ be, but we've got an idea now

Next, we can write another Taylor series, this time for the point $ u(x_0 - \Delta x) $:

$ u(x_0 - \Delta x) = u(x_0) - \left. \frac{ \partial u }{ \partial x } \right|_0 \Delta x + \left. \frac{ \partial^2 u}{ \partial^2 x} \right|_0 \frac{ (\Delta x)^2 }{ 2! } - \left. \frac{ \partial^3 u}{ \partial^3 x} \right|_0 \frac{ (\Delta x)^3 }{ 3! } + \dots $

This is a backward difference.

Rearranging it the same way we did the forward difference,

$ \left. \frac{ \partial u}{\partial x} \right|_{i} = - \frac{ u_i - u_{i-1} }{ \Delta x } + \frac{ \partial^2 u }{ \partial x^2 } \frac{ \Delta x }{2!} + \dots $

So this one has an extra error term, that is also $ O(\Delta x) $.

Can we represent the derivative some other way?

Yes!

In fact, we can represent the derivative a whole bunch of different ways.

We've shown approximations of the derivative of $ u $ at the point $ x $ using the value of $ u(x-\Delta x) $ and $ u(x + \Delta x) $ - but what about using both?

How to approximate the derivative $ u(x) $ at $ x $ using both the value of $ u(x-\Delta x) $ and $ u(x+\Delta x) $?

Subtracting the backward difference from the forward difference yields a central difference:

$ \frac{ \partial u }{ \partial x } = \frac{ u_{i+1} - u_{i-1} }{ 2 \Delta x } + O( (\Delta x)^2 ) $

The order term is different, because the first-order error terms canceled out. What does that tell us?

1. To approximate a given function, the $ \Delta x $ for a central difference scheme can be larger than the $ \Delta x $ for a forward or backward difference scheme

2. If a function has large gradients (and thus a larger error term), a central difference scheme will approximate the derivative better than a forward or backward difference scheme for the same $ \Delta x $

Alternative approach

An alternative way to think about derivatives for a discrete function...

For a continuous function $ f(x), x \in X $, the limit is defined as:

$ \displaystyle{ \lim_{\Delta x \rightarrow 0} \frac{ f(x + \Delta x) - f(x) }{ \Delta x } } = \frac{\partial f}{\partial x} $

Now, for a discrete function

$ f_{i} \qquad i=1,2,\dots,N $

(where $ N $ is the number of discrete points used to represent the domain $ X $), the distance between locations at which the function can be sampled can't go to zero, it can only go to $ X/N $(the $ \Delta x $ for the discretized domain). This makes the discrete function's limit:

$ \displaystyle{ \lim_{ \Delta x \rightarrow \frac{X}{N} } \frac{ f(x + \Delta x) - f(x) }{ \Delta x } } \approx \frac{ \partial f }{ \partial x } $

While this isn't rigorous, it's another way to think about the discrete vs. continuous case.