Numerical Algorithms for Visual

Computing II

Assignment 8

Jan Hendrik Dithmar

2031259

Andreas Steinel

2029984

Assignment 8  Dithmar (2031259), Steinel (2029984)

8.1 Shake That!

a. As you like, the inline source code:

function upwind()
// constructing signal as follows:
// sig   00000 11111 11111 00000 00000 ...
// idx  -4   0 1     6     11    16    ...
signal = zeros(50,1);
signal(5:15,1) = 1;
s  = 20;      // steps
a  = 2.0;     // parameter a
dx = 0.1;     // delta x
dt = 0.025;   // delta t
// plot original signal
plot2d(1:50,signal,style=1)
for i=1:s
  // build boundary-zero-ed signal and shift one to left
  n = size(signal,1)
  tmp = zeros(n+2,1)
  tmp(2:n+1,1) = signal(1:n,1);
  for j=1:n
   signal(j,1) = dt * a / dx * (tmp(j,1) - tmp(j+1,1)) + tmp(j+1,1)
  end
  // plot every 5 iterations
  if modulo(i,5) == 0
    plot2d(1:50,signal,style=i/5)
  end
end
endfunction

The plot shows every fifth iteration and also includes the initial signal. b. We know from the lecture

u_{i} ≈ u(iΔx) =^{(2.12)} u(x)
u_{i−1} ≈ u((i − 1)Δx) =^{(2.12)} u(x − Δx)
u^{n} ≈ u(nΔt) =^{(2.12)} u(t)
u^{n+1} ≈ u((n + 1)Δt) =^{(2.12)} u(t + Δt)

Let’s compute the Taylor expansions:

u(x) = u(x)
u(x − Δx) = u(x) + [(x − Δx) − x]u′(x) + \frac{[(x + Δx) − x]^{2}}{2} u′′(x)

+\frac{[(x − Δx) − x]^{3}}{6} u′′′(x) + \frac{[(x + Δx) − x]^{4}}{24} u′′′′(x)

+\frac{[(x − Δx) − x]^{5}}{120} u′′′′′(x) + O(Δx^{6})

u(t) = u(t)
u(t + Δt) = u(t) + [(t + Δt) − t]u′(t) + \frac{[(t + Δt) − t]^{2}}{2} u′′(t)

+\frac{[(t + Δt) − t]^{3}}{6} u′′′(t) + \frac{[(t + Δt) − t]^{4}}{24} u′′′′(t)

+\frac{[(t + Δt) − t]^{5}}{120} u′′′′′(t) + O(Δx^{6})

Let’s compute the local truncation error (neglecting the arguments x and t, respectively):

L(u) = \frac{u_{i}^{n+1} − u_{i}^{n}}{Δt} + a \frac{u_{i}^{n} − u_{i−1}^{n}}{Δx} − 0

L(u) = \frac{1}{Δt} [u + Δtu_{t} + \frac{Δt^{2}}{2} u_{tt} + \frac{Δt^{3}}{6} u_{ttt}

+\frac{Δt^{4}}{24} u_{tttt} + \frac{Δt^{5}}{120} u_{ttttt} + O(Δt^{6})]

−\frac{u}{Δt} + a (\frac{u}{Δx}

−\frac{1}{Δx} [u − Δxu_{x} + \frac{Δx^{2}}{2} u_{xx} − \frac{Δx^{3}}{6} u_{xxx}

+\frac{Δx^{4}}{24} u_{xxxx} − \frac{Δx^{5}}{120} u_{xxxxx} + O(Δx^{6})])
= \underbrace{(u_{t} + au_{x})}_{=0} \underbrace{+\frac{Δt}{2}u_{tt} + \frac{Δt^{2}}{6} u_{ttt} + \frac{Δt^{3}}{24} u_{tttt} + \frac{Δt^{4}}{120} u_{ttttt} + O(Δt^{5})}_{O(Δt)}

+ \underbrace{a (−\frac{Δx}{2}u_{xx} + \frac{Δx^{2}}{6} u_{xxx} − \frac{Δx^{3}}{24} u_{xxxx} + \frac{Δx^{4}}{120} u_{xxxxx} + O(Δx^{5}))}_{O(Δx)}

[ = (\frac{Δt}{2}u_{tt} − a\frac{Δx}{2}u_{xx}) + O((Δt)^{2}) + O((Δx)^{2})]
= O(Δt) + O(Δx)

c. We have

u_{t} + au_{x} = 0 ⇔ u_{t} = −au_{x}.
u_{tt} = (−au_{x})_{t}
= −a(u_{x})_{t}
u_{xx} = (−\frac{1}{a}u_{t})_{x}
= −\frac{1}{a}(u_{t})_{x}
= −\frac{1}{a}(u_{x})_{t}

Now, let’s check the relationship:

u_{tt} = a^{2}u_{xx}
−a(u_{x})_{t} = a^{2} (−\frac{1}{a}) (u_{x})_{t}
a = a ✓

d. We use the second last line of the computation of L(u) which reads

L(u) = \frac{Δt}{2}u_{tt} − a\frac{Δx}{2}u_{xx} + O((Δt)^{2}) + O((Δx)^{2})
=^{Hint 2} \frac{Δt}{2}u_{tt} − a\frac{Δx}{2}u_{xx} + O((Δx)^{2})
=^{Hint 3} \frac{Δt}{2}(a^{2}u_{xx}) − a\frac{Δx}{2}u_{xx} + O((Δx)^{2})
= u_{xx} (\frac{a^{2} Δt − a Δx}{2}) + O((Δx)^{2})
=^{Hint 2} u_{xx} (\frac{a^{2} (λΔx) − aΔx}{2}) + O((Δx)^{2})
= u_{xx} \underbrace{(\frac{a Δx}{2} (a λ − 1))}_{α(Δx)} +O((Δx)^{2})

□

The term u_{xx}α(Δx) leads to a smoothing of the signal which depends heavily on a.

e. We derived in the previous two parts of this exercise the first level order accurate solution with the leading error term. If we want to modify the given equation of the upwind scheme in such a way that it is secondorder accurate, we have to build an equation so that the first order error term cancels out.

In this part of the exercise, we have to prove that the following equation is second-order accurate:

u_{t} + au_{x} = \frac{aΔx}{2}(1 − aλ)u_{xx}
u_{t} + au_{x} + \frac{aΔx}{2}(aλ − 1)u_{xx} = 0

With the result from the previous exercise we get immediately the second-order accuracy.

L(u) = \underbrace{(u_{t} + au_{x} + u_{xx} (\frac{a Δx}{2} (a λ − 1)))}_{=0} +O((Δx)^{2})

□

8.2 No Time To Chill

a. We know from the lecture that

u_{i}^{n+1} = u_{i}^{n} − a\frac{Δt}{Δx}(u_{i}^{n} − u_{i−1}^{n})

can be expressed by a scheme function H

H(u_{i−1}^{n}, u_{i}^{n}) = u_{i}^{n} − a\frac{Δt}{Δx}(u_{i}^{n} − u_{i−1}^{n}).

A scheme is monotone if

\frac{∂H}{∂u_{i−1}^{n}} = a\frac{Δt}{Δx} ≥ 0
\frac{∂H}{∂u_{i}^{n}} = 1 − a\frac{Δt}{Δx} ≥ 0

⇔ Δt ≤ \frac{Δx}{a}

(a)

Δt ≤ \frac{Δx}{a_{1}} = \frac{2}{5} ≥ 0
a_{1} \frac{Δt}{Δx} ≤ 0.5 · \frac{0.4}{0.2} = 1 ≥ 0 ✓
For Δt ≤ \frac{2}{5} = 0.4, the scheme is monotone.

(b)

Δt ≤ \frac{Δx}{a_{2}} = \frac{1}{25} ≥ 0
a_{2} \frac{Δt}{Δx} ≤ 5 · \frac{0.04}{0.2} = 1 ≥ 0 ✓

For Δt ≤ \frac{1}{25} = 0.04, the scheme is monotone. b. For the resulting conditions, we get a discrete minimum-maximum-

principle for Δt ≤ \frac{2}{5} and Δt ≤ \frac{1}{25}, respectively, since the monotony property implies for hyperbolic PDEs an upper and lower bound in the L_{∞}-norm. This directly implies stability.