Problem 4a
edit
Consider the boundary value problem
{
−
u
″
(
x
)
+
b
(
x
)
u
(
x
)
=
f
(
x
)
,
0
≤
x
≤
1
u
(
0
)
=
u
l
,
u
(
1
)
=
u
r
(
1
)
{\displaystyle {\begin{cases}-u''(x)+b(x)u(x)=f(x),0\leq x\leq 1\\u(0)=u_{l},u(1)=u_{r}\end{cases}}\qquad (1)\!\,}
where
b
(
x
)
,
f
(
x
)
∈
C
[
0
,
1
]
{\displaystyle b(x),f(x)\in C[0,1]\!\,}
, and
b
(
x
)
≥
0
{\displaystyle b(x)\geq 0\!\,}
. Formulate a difference method for the approximate solution of
(
1
)
{\displaystyle (1)\!\,}
on a uniform mesh of size
h
{\displaystyle h\!\,}
. Explain how
u
″
(
x
)
{\displaystyle u''(x)\!\,}
is approximated by a difference quotient
Solution 4a
edit
From Taylor expansion of
u
(
x
+
h
)
{\displaystyle u(x+h)\!\,}
and
u
(
x
−
h
)
{\displaystyle u(x-h)\!\,}
around
x
{\displaystyle x\!\,}
, we have
u
″
(
x
)
=
u
(
x
+
h
)
−
2
u
(
x
)
+
u
(
x
−
h
)
h
2
+
u
⁗
(
ξ
)
12
h
2
{\displaystyle u''(x)={\frac {u(x+h)-2u(x)+u(x-h)}{h^{2}}}+{\frac {u''''(\xi )}{12}}h^{2}\!\,}
Let
P
=
{
x
i
}
i
=
0
N
+
1
{\displaystyle P=\{x_{i}\}_{i=0}^{N+1}\!\,}
be a uniform partition of
[
0
,
1
]
{\displaystyle [0,1]\!\,}
with step size
h
{\displaystyle h\!\,}
Then for
i
=
2
,
…
,
N
−
1
{\displaystyle i=2,\ldots ,N-1\!\,}
we have
[
−
1
h
2
2
h
2
+
b
(
x
i
)
−
1
h
2
]
[
u
i
−
1
u
i
u
i
+
1
]
=
f
(
x
i
)
{\displaystyle {\begin{bmatrix}-{\frac {1}{h^{2}}}&&&{\frac {2}{h^{2}}}+b(x_{i})&&&-{\frac {1}{h^{2}}}\end{bmatrix}}{\begin{bmatrix}u_{i-1}\\u_{i}\\u_{i+1}\end{bmatrix}}=f(x_{i})\!\,}
For
i
=
1
:
{\displaystyle i=1:\!\,}
[
2
h
2
+
b
(
x
1
)
−
1
h
2
]
[
u
1
u
2
]
=
f
(
x
1
)
+
u
l
h
2
{\displaystyle {\begin{bmatrix}{\frac {2}{h^{2}}}+b(x_{1})&&&-{\frac {1}{h^{2}}}\end{bmatrix}}{\begin{bmatrix}u_{1}\\u_{2}\end{bmatrix}}=f(x_{1})+{\frac {u_{l}}{h^{2}}}\!\,}
For
i
=
N
:
{\displaystyle i=N:\!\,}
[
−
1
h
2
2
h
2
+
b
(
x
N
)
]
[
u
N
−
1
u
N
]
=
f
(
x
N
)
+
u
r
h
2
{\displaystyle {\begin{bmatrix}-{\frac {1}{h^{2}}}&&&{\frac {2}{h^{2}}}+b(x_{N})\end{bmatrix}}{\begin{bmatrix}u_{N-1}\\u_{N}\end{bmatrix}}=f(x_{N})+{\frac {u_{r}}{h^{2}}}\!\,}
Problem 4b
edit
Solution 4b
edit
[
2
h
−
1
h
−
1
h
2
h
−
1
h
⋱
⋱
⋱
−
1
h
2
h
]
[
u
1
⋮
⋮
u
N
]
=
[
∫
0
1
f
ϕ
i
⋮
∫
0
1
f
ϕ
N
]
{\displaystyle {\begin{bmatrix}{\frac {2}{h}}&-{\frac {1}{h}}&&&\\-{\frac {1}{h}}&{\frac {2}{h}}&-{\frac {1}{h}}&&\\&\ddots &\ddots &\ddots &\\&&&-{\frac {1}{h}}&{\frac {2}{h}}\end{bmatrix}}{\begin{bmatrix}u_{1}\\\vdots \\\vdots \\u_{N}\end{bmatrix}}={\begin{bmatrix}\int _{0}^{1}f\phi _{i}\\\vdots \\\\\int _{0}^{1}f\phi _{N}\end{bmatrix}}\!\,}
Since we are integrating hat functions on the right hand side, an appropriate quadrature formula would be to take half of the midpoint rule. The regular midpoint rule would give double the actual integral value of a hat function.
Therefore
∫
0
1
f
(
x
)
ϕ
i
(
x
)
≈
h
f
(
x
i
)
{\displaystyle \int _{0}^{1}f(x)\phi _{i}(x)\approx hf(x_{i})\!\,}
Then the finite difference method and the finite element method yield the same matrix.
Problem 4c
edit
Show that the matrix in
(
b
)
{\displaystyle (b)\!\,}
is non singluar.
Solution 4c
edit
Since the matrix is diagonally dominant, it is non-singular.
To show that the matrix has a non-zero determinant, 2n elementary row operation can be used to show that
[
2
h
−
1
h
−
1
h
2
h
−
1
h
⋱
⋱
−
1
h
2
h
]
{\displaystyle {\begin{bmatrix}{\frac {2}{h}}&-{\frac {1}{h}}&&\\-{\frac {1}{h}}&{\frac {2}{h}}&-{\frac {1}{h}}&\\&\ddots &\ddots &\\&&-{\frac {1}{h}}&{\frac {2}{h}}\end{bmatrix}}}
has the same determinant as
[
−
1
h
2
h
−
1
h
⋱
⋱
⋱
−
1
h
2
h
n
+
1
h
]
{\displaystyle {\begin{bmatrix}-{\frac {1}{h}}&{\frac {2}{h}}&-{\frac {1}{h}}&\\&\ddots &\ddots &\ddots &\\&&-{\frac {1}{h}}&{\frac {2}{h}}\\&&&{\frac {n+1}{h}}\\\end{bmatrix}}}
which is
n
+
1
h
n
≠
0
{\displaystyle {\frac {n+1}{h^{n}}}\neq 0}
.
Problem 5
edit
Consider the following dissipative initial value problem,
{
y
′
+
f
(
y
)
=
0
,
0
≤
x
≤
1
y
(
0
)
=
y
0
(
2
)
{\displaystyle {\begin{cases}y'+f(y)=0,0\leq x\leq 1\\y(0)=y_{0}\end{cases}}\qquad (2)\!\,}
where
f
:
R
→
R
{\displaystyle f:R\rightarrow R\!\,}
is smooth and satisfies
0
≤
f
′
(
y
)
{\displaystyle 0\leq f'(y)\!\,}
Problem 5a
edit
Write the Backward Euler Method for (2). This gives rise to an algebraic equation. Explain how you would solve this equation.
Solution 5a
edit
Using Taylor Expansion we have
y
(
x
−
h
)
=
y
(
x
)
−
y
′
(
x
)
h
+
y
″
(
ξ
)
2
h
2
y
(
x
)
=
y
(
x
−
h
)
+
y
′
(
x
)
h
−
y
″
(
ξ
)
2
h
2
y
(
x
n
)
=
y
(
x
n
−
1
)
+
y
′
(
x
n
)
⏟
−
f
(
y
(
x
n
)
)
h
−
y
″
(
ξ
)
2
h
2
⏟
O
(
h
2
)
(
∗
)
{\displaystyle {\begin{aligned}y(x-h)&=y(x)-y'(x)h+{\frac {y''(\xi )}{2}}h^{2}\\y(x)&=y(x-h)+y'(x)h-{\frac {y''(\xi )}{2}}h^{2}\\y(x_{n})&=y(x_{n-1})+\underbrace {y'(x_{n})} _{-f(y(x_{n}))}h-\underbrace {{\frac {y''(\xi )}{2}}h^{2}} _{O(h^{2})}\qquad (*)\\\end{aligned}}}
Thus we have Backwards Euler Method:
y
n
=
y
n
−
1
−
h
f
(
y
n
)
(
∗
∗
)
{\displaystyle y_{n}=y_{n-1}-hf(y_{n})\qquad (**)\!\,}
Let
e
n
≡
y
(
x
n
−
1
)
−
y
n
{\displaystyle e_{n}\equiv y(x_{n-1})-y_{n}\!\,}
Problem 5b
edit
Derive an error estimate of the form
|
y
(
x
n
)
−
y
n
|
≤
M
2
h
,
n
=
1
,
2
,
…
{\displaystyle |y(x_{n})-y_{n}|\leq {\frac {M}{2}}h,n=1,2,\ldots \!\,}
where
M
=
max
0
≤
x
≤
1
|
y
″
(
x
)
|
{\displaystyle M=\max _{0\leq x\leq 1}|y''(x)|\!\,}
. Do this directly, not as an application of a standard theorem. (Note that there is no exponential on the right hand side.
Solution 5b
edit
Subtracting
(
∗
)
{\displaystyle (*)\!\,}
and
(
∗
∗
)
{\displaystyle (**)\!\,}
, we have
e
n
=
e
n
−
1
−
h
[
f
(
y
(
x
n
)
)
−
f
(
y
n
)
]
−
y
″
(
ξ
)
2
h
2
=
e
n
−
1
−
h
f
′
(
y
(
α
)
)
e
n
−
y
″
(
ξ
)
2
h
2
(by MVT)
e
n
2
=
e
n
−
1
e
n
−
h
f
′
(
y
α
)
⏟
<
0
e
n
2
−
y
″
(
ξ
)
2
h
2
e
n
≤
e
n
−
1
e
n
−
y
″
(
ξ
)
2
h
2
e
n
e
n
≤
e
n
−
1
−
y
″
(
ξ
)
2
h
2
‖
e
n
‖
≤
‖
e
n
−
1
‖
+
‖
y
″
‖
∞
2
h
2
‖
e
n
‖
≤
n
‖
y
″
‖
∞
2
h
2
≤
M
2
h
{\displaystyle {\begin{aligned}e_{n}&=e_{n-1}-h[f(y(x_{n}))-f(y_{n})]-{\frac {y''(\xi )}{2}}h^{2}\\&=e_{n-1}-hf'(y(\alpha ))e_{n}-{\frac {y''(\xi )}{2}}h^{2}\quad {\mbox{ (by MVT) }}\\e_{n}^{2}&=e_{n-1}e_{n}-h\underbrace {f'(y\alpha )} _{<0}e_{n}^{2}-{\frac {y''(\xi )}{2}}h^{2}e_{n}\\&\leq e_{n-1}e_{n}-{\frac {y''(\xi )}{2}}h^{2}e_{n}\\e_{n}&\leq e_{n-1}-{\frac {y''(\xi )}{2}}h^{2}\\\|e_{n}\|&\leq \|e_{n-1}\|+{\frac {\|y''\|_{\infty }}{2}}h^{2}\\\|e_{n}\|&\leq n{\frac {\|y''\|_{\infty }}{2}}h^{2}\\&\leq {\frac {M}{2}}h\end{aligned}}\!\,}
Problem 6
edit
Solution 6
edit