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, can do the same thing, but with $ 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

What if the last term looked like this?

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

What does that tell us?

1. The value of $ \Delta x $ can be bigger to approximate this function

• What we're trying to do with it - i.e. discretize it (define it, explain it)

• Definition of limit

• Derivative is to continuous function what algebraic difference is to discrete function
  • i.e. imagine a limit for a discrete function...... it wouldn't turn into a derivative!
  • $ \lim_{\Delta x \rightarrow \delta} $ versus $ \lim_{\Delta x \rightarrow 0} $

• Taylor series
  • Expand a nearby point $ (x+\Delta x) $ about another point $ (x) $
  • Rearrange to put difference in terms of derivative
  • Truncation error, order of error