Problem 4
edit
Suppose that
f
:
R
→
R
{\displaystyle f:R\rightarrow R\!\,}
is smooth and that the boundary value problem
u
″
=
f
(
u
)
on
(
0
,
1
)
,
u
(
0
)
=
(
1
)
=
0
{\displaystyle u''=f(u){\mbox{ on }}(0,1),\quad u(0)=(1)=0\!\,}
has unique solution.
Problem 4a
edit
For
N
∈
N
{\displaystyle N\in \mathbb {N} \!\,}
, let
x
i
=
1
N
,
i
=
0
,
…
,
N
{\displaystyle x_{i}={\frac {1}{N}},i=0,\ldots ,N\!\,}
. Write down a system of
N
+
1
{\displaystyle N+1\!\,}
equations to obtain an approximation
u
i
{\displaystyle u_{i}\!\,}
for the solution
u
{\displaystyle u\!\,}
at
x
i
{\displaystyle x_{i}\!\,}
by replacing the second derivatives by a symmetric difference quotient.
Solution 4a
edit
The symmetric difference quotient is given by
u
(
x
+
h
)
−
2
u
(
x
)
+
u
(
x
−
h
)
h
2
=
u
″
(
x
)
{\displaystyle {\frac {u(x+h)-2u(x)+u(x-h)}{h^{2}}}=u''(x)\!\,}
Hence we have the following system equations that incorporates the initial conditions
u
(
0
)
=
u
(
1
)
=
0
{\displaystyle u(0)=u(1)=0\!\,}
.
1
h
2
[
1
1
−
2
1
1
−
2
1
⋱
⋱
⋱
1
−
2
1
1
]
⏟
A
[
u
0
u
1
u
2
⋮
⋮
u
n
]
⏟
U
=
[
0
f
(
u
1
)
f
(
u
2
)
⋮
f
(
u
n
−
1
)
0
]
⏟
f
{\displaystyle \underbrace {{\frac {1}{h^{2}}}{\begin{bmatrix}1&&&&&&\\1&-2&1&&&&\\&1&-2&1&&&\\&&\ddots &\ddots &\ddots &&\\&&&&1&-2&1\\&&&&&&1\end{bmatrix}}} _{A}\underbrace {\begin{bmatrix}u_{0}\\u_{1}\\u_{2}\\\vdots \\\vdots \\u_{n}\end{bmatrix}} _{U}=\underbrace {\begin{bmatrix}0\\f(u_{1})\\f(u_{2})\\\vdots \\f(u_{n-1})\\0\end{bmatrix}} _{f}\!\,}
Problem 4b
edit
Write the system of equations in the form
F
(
U
)
=
0
{\displaystyle F(U)=0\!\,}
. Define domain and range of
F
{\displaystyle F\!\,}
and explain the meaning of the variable
U
{\displaystyle U\!\,}
.
Solution 4b
edit
Problem 4c
edit
Formulate Newton's method for the solution of the system in (b) with
U
(
0
)
=
0
{\displaystyle U^{(0)}=0\!\,}
. Give explicit expressions for all objects involved (as far as this is reasonable). Determine a sufficient condition that ensures that the iterates
U
(
k
)
{\displaystyle U^{(k)}\!\,}
in the Newton scheme are defined. Without doing any further calculations, can you decide whether the sequence
U
(
k
)
{\displaystyle U^{(k)}\!\,}
converges. Why or why not?
Solution 4c
edit
Newton's Method
edit
U
k
+
1
=
U
k
−
J
(
F
(
U
(
k
)
)
−
1
F
(
U
(
k
)
)
{\displaystyle U^{k+1}=U^{k}-J(F(U^{(k)})^{-1}F(U^{(k)})\!\,}
where
J
(
A
)
{\displaystyle J(A)\!\,}
denotes the Jacobian of a matrix
A
{\displaystyle A\!\,}
.
Specifically,
J
(
F
(
U
(
k
)
)
=
J
(
A
U
−
F
)
=
A
−
J
(
F
)
{\displaystyle J(F(U^{(k)})=J(AU-F)=A-J(F)\!\,}
Sufficient Condition
edit
If
J
(
F
(
U
(
k
)
)
−
1
{\displaystyle J(F(U^{(k)})^{-1}\!\,}
exists, then
U
(
k
)
{\displaystyle U^{(k)}\!\,}
iterates are defined.
Convergence of sequence
edit
We cannot decide if the sequence converges since Newton's method only guarantees local convergence.
In general, for local convergence of Newton's method we need:
F
{\displaystyle F\!\,}
differentriable
D
(
F
(
U
∗
)
)
{\displaystyle D(F(U^{*}))\!\,}
invertible
D
(
F
)
{\displaystyle D(F)\!\,}
Lipschitz
U
(
0
)
{\displaystyle U^{(0)}\!\,}
close to solution
U
∗
{\displaystyle U^{*}\!\,}
Problem 5
edit
Consider the boundary value problem
−
u
″
=
f
,
0
<
x
<
1
{\displaystyle -u''=f,\quad 0<x<1\!\,}
with boundary conditions
u
(
0
)
=
0
{\displaystyle u(0)=0\!\,}
and
u
′
(
1
)
+
α
u
(
1
)
=
0
{\displaystyle u'(1)+\alpha u(1)=0\!\,}
. Here
α
{\displaystyle \alpha \!\,}
is a given positive number.
Problem 5a
edit
Describe a Galerkin method to solve this problem using piecewise linear functions with respect to a uniform mesh.
Weak Formulation
edit
Find
u
∈
U
=
{
u
∈
H
1
:
u
(
0
)
=
0
}
{\displaystyle u\in U=\{u\in H^{1}:u(0)=0\}\!\,}
such that for all
v
∈
U
{\displaystyle v\in U\!\,}
∫
0
1
−
u
″
v
=
∫
0
1
f
v
{\displaystyle \int _{0}^{1}-u''v=\int _{0}^{1}fv\!\,}
which after integrating by parts and plugging in initial conditions we have
∫
0
1
u
′
v
′
=
∫
0
1
f
v
−
α
u
(
1
)
v
(
1
)
{\displaystyle \int _{0}^{1}u'v'=\int _{0}^{1}fv-\alpha u(1)v(1)\!\,}
Let
{
x
i
}
i
=
0
N
+
1
{\displaystyle \{x_{i}\}_{i=0}^{N+1}\!\,}
be the nodes of a uniform partition of
[
0
,
1
]
{\displaystyle [0,1]\!\,}
where
x
0
=
0
{\displaystyle x_{0}=0\!\,}
and
x
i
=
i
h
{\displaystyle x_{i}=ih\!\,}
.
Let
{
ϕ
i
}
i
=
0
N
+
1
{\displaystyle \{\phi _{i}\}_{i=0}^{N+1}\!\,}
be the standard "hat" functions defined as follows:
For
i
=
1
,
2
…
,
N
{\displaystyle i=1,2\ldots ,N\!\,}
ϕ
i
=
{
x
−
x
i
−
1
h
for
x
∈
[
x
i
−
1
,
x
i
]
x
i
+
1
−
x
h
for
x
∈
[
x
i
,
x
i
+
1
]
0
otherwise
{\displaystyle \phi _{i}={\begin{cases}{\frac {x-x_{i-1}}{h}}&{\mbox{ for }}x\in [x_{i-1},x_{i}]\\{\frac {x_{i+1}-x}{h}}&{\mbox{ for }}x\in [x_{i},x_{i+1}]\\0&{\mbox{ otherwise }}\end{cases}}\!\,}
ϕ
N
+
1
=
{
x
−
x
N
h
for
x
∈
[
x
N
,
x
N
+
1
]
0
otherwise
{\displaystyle \phi _{N+1}={\begin{cases}{\frac {x-x_{N}}{h}}&{\mbox{ for }}x\in [x_{N},x_{N+1}]\\0&{\mbox{ otherwise }}\end{cases}}}
Also
ϕ
0
=
0
{\displaystyle \phi _{0}=0\!\,}
since
u
(
0
)
=
0
{\displaystyle u(0)=0\!\,}
Then
{
ϕ
i
}
i
=
0
N
+
1
{\displaystyle \{\phi _{i}\}_{i=0}^{N+1}\!\,}
forms a basis for the discrete space
U
h
=
{
u
∈
H
1
[
0
,
1
]
:
u
(
0
)
=
0
,
u
piecewise linear
}
{\displaystyle U_{h}=\{u\in H^{1}[0,1]:u(0)=0,u{\mbox{ piecewise linear }}\}\!\,}
Problem 5b
edit
Derive the matrix equations for this Galerkin method. Write out explicitly that equation of the linear system which involves
α
{\displaystyle \alpha \!\,}
Discrete Weak Formulation
edit
Find
u
h
∈
U
h
{\displaystyle u_{h}\in U_{h}\!\,}
such that for all
v
∈
U
h
{\displaystyle v\in U_{h}\!\,}
∫
0
1
u
h
′
v
h
′
=
∫
0
1
f
v
h
−
α
u
(
1
)
v
(
1
)
{\displaystyle \int _{0}^{1}u_{h}'v_{h}'=\int _{0}^{1}fv_{h}-\alpha u(1)v(1)\!\,}
Since
{
ϕ
i
}
i
=
0
N
+
1
{\displaystyle \{\phi _{i}\}_{i=0}^{N+1}\!\,}
forms a basis, we have
u
h
=
∑
i
=
0
N
+
1
u
h
i
ϕ
i
{\displaystyle u_{h}=\sum _{i=0}^{N+1}u_{hi}\phi _{i}\!\,}
Also for
j
=
1
,
…
,
N
+
1
{\displaystyle j=1,\ldots ,N+1\!\,}
∑
i
=
0
N
+
1
u
h
i
∫
0
1
ϕ
i
′
ϕ
j
′
=
∫
0
1
f
ϕ
j
+
α
∑
i
=
0
N
+
1
u
h
i
ϕ
i
(
1
)
ϕ
j
(
1
)
{\displaystyle \sum _{i=0}^{N+1}u_{hi}\int _{0}^{1}\phi _{i}'\phi _{j}'=\int _{0}^{1}f\phi _{j}+\alpha \sum _{i=0}^{N+1}u_{hi}\phi _{i}(1)\phi _{j}(1)\!\,}
In matrix form
[
2
h
−
1
h
−
1
h
2
h
−
1
h
⋱
⋱
⋱
−
1
h
2
h
+
α
]
[
u
h
1
u
h
2
⋮
u
h
N
+
1
]
=
[
∫
0
1
f
ϕ
1
∫
0
1
f
ϕ
2
⋮
∫
0
1
f
ϕ
N
+
1
]
{\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}}+\alpha \end{bmatrix}}{\begin{bmatrix}u_{h_{1}}\\u_{h_{2}}\\\vdots \\u_{h_{N+1}}\end{bmatrix}}={\begin{bmatrix}\int _{0}^{1}f\phi _{1}\\\int _{0}^{1}f\phi _{2}\\\vdots \\\int _{0}^{1}f\phi _{N+1}\end{bmatrix}}\!\,}
Problem 6
edit
Consider the linear multistep method
y
n
+
1
=
4
3
y
n
−
1
3
y
n
−
1
+
2
3
h
f
(
x
n
+
1
,
y
n
+
1
)
{\displaystyle y_{n+1}={\frac {4}{3}}y_{n}-{\frac {1}{3}}y_{n-1}+{\frac {2}{3}}hf(x_{n+1},y_{n+1})\!\,}
for the solution of the initial value problem
y
′
(
x
)
=
f
(
x
,
y
(
x
)
)
,
y
(
0
)
=
y
0
{\displaystyle y'(x)=f(x,y(x)),y(0)=y_{0}\!\,}
Problem 6a
edit
Show that the truncation error is of order 2.
Problem 6b
edit
State the condition for consistency of a linear multistep method and verify it for the scheme in this problem.
Solution 6b
edit
y
n
+
1
=
∑
j
=
0
p
a
j
y
n
−
j
+
h
∑
j
=
−
1
p
b
j
f
(
t
n
−
j
,
y
n
−
j
)
=
a
0
y
n
+
a
1
y
n
−
1
+
…
+
a
p
y
n
−
p
+
h
[
b
−
1
f
(
t
n
+
1
,
y
n
+
1
)
+
b
0
f
(
t
n
,
y
n
)
+
b
1
f
(
t
n
−
1
,
y
n
−
1
)
+
…
+
b
p
f
(
t
n
−
p
,
y
n
−
p
)
]
{\displaystyle {\begin{aligned}y_{n+1}&=\sum _{j=0}^{p}a_{j}y_{n-j}+h\sum _{j=-1}^{p}b_{j}f(t_{n-j},y_{n-j})\\&=a_{0}y_{n}+a_{1}y_{n-1}+\ldots +a_{p}y_{n-p}+h[b_{-1}f(t_{n+1},y_{n+1})+b_{0}f(t_{n},y_{n})+b_{1}f(t_{n-1},y_{n-1})+\ldots +b_{p}f(t_{n-p},y_{n-p})]\end{aligned}}\!\,}
Conditions:
(i)
∑
j
=
0
p
a
j
=
1
{\displaystyle \sum _{j=0}^{p}a_{j}=1\!\,}
4
3
+
−
1
3
=
1
{\displaystyle {\frac {4}{3}}+-{\frac {1}{3}}=1\!\,}
(ii)
∑
j
=
−
1
p
b
j
−
∑
j
=
0
p
j
a
j
=
1
{\displaystyle \sum _{j=-1}^{p}b_{j}-\sum _{j=0}^{p}ja_{j}=1\!\,}
2
3
−
(
0
⋅
4
3
+
1
⋅
−
1
3
)
=
1
{\displaystyle {\frac {2}{3}}-(0\cdot {\frac {4}{3}}+1\cdot -{\frac {1}{3}})=1\!\,}
Problem 6c
edit
Does the scheme satisfy the root condition and or the strong root condition?
The scheme satisfies the root condition but not the strong root condition since the roots are given by
λ
=
4
3
±
16
9
−
4
3
2
{\displaystyle \lambda ={\frac {{\frac {4}{3}}\pm {\sqrt {{\frac {16}{9}}-{\frac {4}{3}}}}}{2}}\!\,}
which implies
λ
1
=
1
{\displaystyle \lambda _{1}=1\!\,}
and
λ
2
=
1
3
{\displaystyle \lambda _{2}={\frac {1}{3}}\!\,}