<a href="https://colab.research.google.com/github/JiaminJIAN/20MA573/blob/master/src/Upwind_finite_difference_scheme.ipynb" target="_parent"></a>

# **Upwind finite difference scheme**

## **Introduction:**

Consider the BVP:

$$
\begin{cases}
Lu = - u^{''} + b u^{'} + c u = f, & x \in (0, 1) \\
u(0) = u(1) = 0 &
\end{cases}$$

Using the Upwind difference, the finite difference operator is as following:

- UFD:
$$ u_{i}^{'} \approx 
\begin{cases}
\delta_{h} u_{i} = \frac{u_{i+1}^{h} - u_{i}^{h}}{h}, & b(x) < 0 \\
\delta_{-h} u_{i} = \frac{u_{i}^{h} - u_{i-1}^{h}}{h} , & b(x) \geq 0.
\end{cases}$$

- SCFD:

$$u_{i}^{''} \approx \delta_{h} \delta_{-h} u_{i} = \frac{u_{i+1}^{h} - 2 u_{i}^{h} + u_{i-1}^{h}}{h^{2}}.$$

By the formula of UFD for $u^{'}$, we have 

$$b u^{'} = (b^{+} - b^{-}) u^{'} \approx b^{+} (\delta_{-h} u) - b^{-} (\delta_{h} u).$$

Then for the above BVP, for $i = 1, 2, \dots, N-1$, we have

$$ - \frac{u_{i+1}^{h} - 2 u_{i}^{h} + u_{i-1}^{h}}{h^{2}} + b^{+} \frac{u_{i}^{h} - u_{i-1}^{h}}{h} - b^{-} \frac{u_{i+1}^{h} - u_{i}^{h}}{h} + c u_{i}^{h} = \hat{f_{i}}. $$

By sorting out the parameters, we have

$$- u_{i-1}^{h} (\frac{1}{h^{2}} + \frac{b^{+}}{h}) + u_{i}^{h} (\frac{2}{h^{2}} + \frac{|b|}{h} + c) - u_{i+1}^{h} (\frac{1}{h^{2}} + \frac{b^{-}}{h}) = \hat{f_{i}}.$$

Then we know that UFD solution $u^{h}$ solves

$$
\begin{cases}
u_{0}^{h} = 0 \\-r u_{i-1}^{h} + s u_{i}^{h} - t u_{i+1}^{h} = \hat{f_{i}}, & i = 1, 2, \dots, N-1 \\
u_{N}^{h} = 0
\end{cases}$$

where $r = \frac{1}{h^{2}} + \frac{b^{+}}{h}$, $s = \frac{2}{h^{2}} + \frac{|b|}{h} + c$ and $t = \frac{1}{h^{2}} + \frac{b^{-}}{h}$.



```

```

## **Exercise:**

Consider ODE

$$- u^{''} + u = x, \, \forall x \in (0, 1), u(0) = u(1) = 0.$$

Answer the following questions:

- Prove that 
$$u(x) = x - \frac{\exp(x - 1) - \exp(- x - 1)}{1 - \exp(-2)}$$
is the unique solution.

- Using the upwind finite difference scheme, find out the matrix $L^{h}$ and vector $R^{h}f$, such that the numerical solution satisfies $L^{h} u^{h} = R^{h} f$.

- Convert $L^{h} u^{h} = R^{h} f$ to Markovian Reward Process.

- Write a pseudocode for value iteration.

- Write a pseudocode for first visit Monte-Carlo method.

- Prove the consistency.

- Prove the stability.

- Find convergence rate.




```

```

## **Solution:**

(1) Prove that 
$$u(x) = x - \frac{\exp(x - 1) - \exp(- x - 1)}{1 - \exp(-2)}$$
is the unique solution.

Proof:

Firstly we consider the equation

$$ - u^{''} + u = 0,$$

the solution is $u(x) = c_{1} e^{x} + c_{2} e^{-x}$, where $c_{1}$ and $c_{2}$ are constants we need to calculate. Since $u(x) = x$ is a solution of the ODE $- u^{''} + u = x$, so we know that $u(x) = x + c_{1} e^{x} + c_{2} e^{-x}$. As $u(0) = u(1) = 0$, we have

$$
\begin{cases}
c_{1} + c_{2} = 0 \\
1 + c_{1} e + c_{2} e^{-1}  = 0.
\end{cases}$$

By calculation we can get $c_{1} = - \frac{e^{-1}}{1 - e^{-2}}$ and $c_{2} = \frac{e^{-1}}{1 - e^{-2}}$. Thus we know the solution of the above ODE is

$$u(x) = x - \frac{\exp(x - 1) - \exp(- x - 1)}{1 - \exp(-2)}.$$


```

```

(2) Using the upwind finite difference scheme, find out the matrix $L^{h}$ and vector $R^{h}f$, such that the numerical solution satisfies $L^{h} u^{h} = R^{h} f$.

Solution:

Applying the UFD scheme for the above ODE, for $i = 1, 2, \dots, N-1$, we have

$$- u_{i-1}^{h} \frac{1}{h^{2}} + u_{i}^{h} (\frac{2}{h^{2}} + 1) - u_{i+1}^{h} \frac{1}{h^{2}} = \hat{f_{i}}.$$

Denote $r = \frac{1}{h^{2}}$, $s = \frac{2}{h^{2}} + 1$ and $t = \frac{1}{h^{2}}$, we know that UFD solution $u^{h}$ solves

$$
\begin{cases}
u_{0}^{h} = 0 \\-r u_{i-1}^{h} + s u_{i}^{h} - t u_{i+1}^{h} = \hat{f_{i}}, & i = 1, 2, \dots, N-1 \\
u_{N}^{h} = 0.
\end{cases}$$

Let $h = \frac{1}{N}$, UFD is to solve for $u^{h} \in \mathbb{R}^{N+1}$ from $L^{h} u^{h} = R^{h} \hat{f}$, where

$$ L^{h} = 
 \begin{bmatrix}
 1  &  0  &  0  &  0  &  0  & 0  \\
 -r &  s  & -r  &  0  &  0  & 0  \\
 0  & -r  & s   &  -r &  0  & 0  \\
 0  &  0  & \ddots  &  \ddots  & \ddots  & 0   \\
 0  &  0  & 0   & -r  &  s  & -r  \\
 0  &  0  & 0   &  0  &  0  &  1 
\end{bmatrix}
$$

is a $(N+1) \times (N+1)$ matrix and 

$$R^{h} \hat{f} =(0, \frac{1}{N}, \frac{2}{N}, \dots, \frac{N-1}{N}, 0 )^{\text{T}}$$

is a $(N+1) \times 1$ vector.


```

```

(3) Convert $L^{h} u^{h} = R^{h} f$ to Markovian Reward Process.

Solution:

Applying the UFD scheme for the above ODE, for $i = 1, 2, \dots, N-1$, we have

$$- u_{i-1}^{h} \frac{1}{h^{2}} + u_{i}^{h} (\frac{2}{h^{2}} + 1) - u_{i+1}^{h} \frac{1}{h^{2}} = \hat{f_{i}},$$

where $\hat{f_{i}} = x_{i}$, then we have

$$ (\frac{2}{h^{2}} + 1) u_{i}^{h} = \frac{1}{h^{2}} ( u_{i-1}^{h} + u_{i+1}^{h}) + x_{i} .$$

Divide $\frac{2}{h^{2}} + 1$ on the both side, we have

$$u_{i}^{h} = \frac{2}{2+h^{2}} (\frac{h^{2}}{2} x_{i} + \frac{1}{2} u_{i-1}^{h} + \frac{1}{2} u_{i+1}^{h}).$$

Denote $\gamma = \frac{2}{2+h^{2}}$, $l^{h}(x) = \frac{h^{2}}{2} x$ and $p^{h}(x+h|x) = p^{h}(x-h|x) = \frac{1}{2}$, then we can get Markovian Reward Process as follows:

$$u(x) = \gamma \{l^{h}(x) + p^{h}(x+h|x) u(x+h) + p^{h}(x-h|x)u(x-h) \}$$


```

```

(4) Write a pseudocode for value iteration.

(5) Write a pseudocode for first visit Monte-Carlo method.

Solution: 

The pseudocode of (4) and (5) is presented in the file:

[Pseudocode_hw12](https://github.com/JiaminJIAN/20MA573/blob/master/src/pseudocode_hw12.pdf)


```

```

(6) Prove the consistency.

Solution:

We need to show that there exists $\alpha > 0$ such that for any small $h$ we have

$$\|L^{h}R^{h}v - R^{h}Lv\|_{\infty} \leq K h^{\alpha}, \forall v \in C^{2}(0,1) \cap C[0,1].$$

If $i = 0$, then 

$$(L^{h}R^{h}v)_{i} = (R^{h}v)_{0} = v(x_{0}) = 0,$$

while

$$(R^{h}Lv)_{i} = Lv(x_{0}) = v(x_{0}) = 0. $$

If $i = N$, then

$$(L^{h}R^{h}v)_{i} = (R^{h}v)_{N} = v(x_{N}) = 0,$$

while

$$(R^{h}Lv)_{i} = Lv(x_{N}) = v(x_{N}) = 0.$$

And if $1 \leq i \leq N-1$, then

$$(L^{h}R^{h}v)_{i} = - \delta_{h} \delta_{-h} v(x_{i}) + v(x_{i}),$$

while

$$(R^{h}Lv)_{i} = - v^{''}(x_{i}) + v(x_{i}).$$

Therefore, by the Taylor expasion, for any small $h$ we have

$$\|L^{h}R^{h}v - R^{h}Lv\|_{\infty} \leq K h^{\alpha}, \forall v \in C^{2}(0,1) \cap C[0,1].$$



```

```

(7) Prove the stability.

Solution:

We need to show that there exists a K such that

$$\|v\|_{\infty} \leq K \|L^{h}v\|_{\infty}, \forall v \in \mathbb{R}^{N+1}.$$

If $|v_{0}| = \|v\|_{\infty}$, then

$$\|L^{h}v\|_{\infty} \geq |(L^{h}v)_{0}| = |v_{0}| = \|v\|_{\infty}.$$

If $|v_{N}| = \|v\|_{\infty}$, then

$$\|L^{h}v\|_{\infty} \geq |(L^{h}v)_{N}| = |v_{N}| = \|v\|_{\infty}.$$

And if $|v_{i}| = \|v\|_{\infty}$ for some $1 \leq i \leq N-1$, then

\begin{equation}
\begin{aligned}
\|L^{h}v\|_{\infty} &\geq |(L^{h}v)_{i}| \\
&= |-r v_{i-1} + s v_{i} - t v_{i+1}| \\
&\geq s |v_{i}| - r |v_{i-1}| - t |v_{i+1}| \\
&\geq (s - r - t) |v_{i}| \\
&\geq |v_{i}| = \|v\|_{\infty} .
\end{aligned}
\end{equation}

Hence we know that

$$\|v\|_{\infty} \leq  \|L^{h}v\|_{\infty}, \forall v \in \mathbb{R}^{N+1}.$$


```

```

(8) Find convergence rate.

Solution:

Let $u^{h}$ be the numerical solution, we have

\begin{equation}
\begin{aligned}
\|u^{h} - R^{h}u\|_{\infty} &\leq \|L^{h}(u^{h} - R^{h}u)\|_{\infty} \\
&= \|L^{h}u^{h} - L^{h}R^{h}u\|_{\infty} \\
&= \|R^{h} \hat{f} - L^{h}R^{h}u\|_{\infty} \\
&= \|R^{h} Lu - L^{h}R^{h}u\|_{\infty} \\
&= O(h^{2}).
\end{aligned}
\end{equation}

f487e118bb544242463a96d9b0e46d6c4b58141f
ipynb
Jupyter Notebook
src/Upwind_finite_difference_scheme.ipynb
JiaminJIAN/20MA573
a9bc42a769b112c9beb9b1fcafb742a768a2a18e
MIT
2020-02-07T23:11:44.000Z
2020-02-08T14:39:45.000Z
src/Upwind_finite_difference_scheme.ipynb
JiaminJIAN/20MA573
a9bc42a769b112c9beb9b1fcafb742a768a2a18e
MIT
src/Upwind_finite_difference_scheme.ipynb
JiaminJIAN/20MA573
a9bc42a769b112c9beb9b1fcafb742a768a2a18e
MIT
Qwen/Qwen-72B
1. YES
2. YES