Suppose that
f
:
R
→
R
{\displaystyle f:R\rightarrow R\!\,}
u
″
=
f
(
u
)
on
(
0
,
1
)
,
u
(
0
)
=
(
1
)
=
0
{\displaystyle u''=f(u){\mbox{ on }}(0,1),\quad u(0)=(1)=0\!\,}
For
N
∈
N
{\displaystyle N\in \mathbb {N} \!\,}
x
i
=
1
N
,
i
=
0
,
…
,
N
{\displaystyle x_{i}={\frac {1}{N}},i=0,\ldots ,N\!\,}
N
+
1
{\displaystyle N+1\!\,}
u
i
{\displaystyle u_{i}\!\,}
u
{\displaystyle u\!\,}
x
i
{\displaystyle x_{i}\!\,}
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)\!\,}
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}\!\,}
Write the system of equations in the form
F
(
U
)
=
0
{\displaystyle F(U)=0\!\,}
F
{\displaystyle F\!\,}
U
{\displaystyle U\!\,}
Formulate Newton's method for the solution of the system in (b) with
U
(
0
)
=
0
{\displaystyle U^{(0)}=0\!\,}
U
(
k
)
{\displaystyle U^{(k)}\!\,}
U
(
k
)
{\displaystyle U^{(k)}\!\,}
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)})\!\,}
J
(
A
)
{\displaystyle J(A)\!\,}
A
{\displaystyle A\!\,}
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}\!\,}
U
(
k
)
{\displaystyle U^{(k)}\!\,}
Convergence of sequence
edit
We cannot decide if the sequence converges since Newton's method only guarantees local convergence.
F
{\displaystyle F\!\,}
D
(
F
(
U
∗
)
)
{\displaystyle D(F(U^{*}))\!\,}
D
(
F
)
{\displaystyle D(F)\!\,}
U
(
0
)
{\displaystyle U^{(0)}\!\,}
U
∗
{\displaystyle U^{*}\!\,}
Consider the boundary value problem
−
u
″
=
f
,
0
<
x
<
1
{\displaystyle -u''=f,\quad 0<x<1\!\,}
u
(
0
)
=
0
{\displaystyle u(0)=0\!\,}
u
′
(
1
)
+
α
u
(
1
)
=
0
{\displaystyle u'(1)+\alpha u(1)=0\!\,}
α
{\displaystyle \alpha \!\,}
Describe a Galerkin method to solve this problem using piecewise linear functions with respect to a uniform mesh.
Find
u
∈
U
=
{
u
∈
H
1
:
u
(
0
)
=
0
}
{\displaystyle u\in U=\{u\in H^{1}:u(0)=0\}\!\,}
v
∈
U
{\displaystyle v\in U\!\,}
∫
0
1
−
u
″
v
=
∫
0
1
f
v
{\displaystyle \int _{0}^{1}-u''v=\int _{0}^{1}fv\!\,}
∫
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)\!\,}
{
x
i
}
i
=
0
N
+
1
{\displaystyle \{x_{i}\}_{i=0}^{N+1}\!\,}
[
0
,
1
]
{\displaystyle [0,1]\!\,}
x
0
=
0
{\displaystyle x_{0}=0\!\,}
x
i
=
i
h
{\displaystyle x_{i}=ih\!\,}
{
ϕ
i
}
i
=
0
N
+
1
{\displaystyle \{\phi _{i}\}_{i=0}^{N+1}\!\,}
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}}}
ϕ
0
=
0
{\displaystyle \phi _{0}=0\!\,}
u
(
0
)
=
0
{\displaystyle u(0)=0\!\,}
{
ϕ
i
}
i
=
0
N
+
1
{\displaystyle \{\phi _{i}\}_{i=0}^{N+1}\!\,}
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 }}\}\!\,}
Derive the matrix equations for this Galerkin method. Write out explicitly that equation of the linear system which involves
α
{\displaystyle \alpha \!\,}
Find
u
h
∈
U
h
{\displaystyle u_{h}\in U_{h}\!\,}
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)\!\,}
{
ϕ
i
}
i
=
0
N
+
1
{\displaystyle \{\phi _{i}\}_{i=0}^{N+1}\!\,}
u
h
=
∑
i
=
0
N
+
1
u
h
i
ϕ
i
{\displaystyle u_{h}=\sum _{i=0}^{N+1}u_{hi}\phi _{i}\!\,}
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)\!\,}
[
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}}\!\,}
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})\!\,}
y
′
(
x
)
=
f
(
x
,
y
(
x
)
)
,
y
(
0
)
=
y
0
{\displaystyle y'(x)=f(x,y(x)),y(0)=y_{0}\!\,}
Show that the truncation error is of order 2.
State the condition for consistency of a linear multistep method and verify it for the scheme in this problem.
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}}\!\,}
∑
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\!\,}
∑
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\!\,}
Does the scheme satisfy the root condition and or the strong root condition?
λ
=
4
3
±
16
9
−
4
3
2
{\displaystyle \lambda ={\frac {{\frac {4}{3}}\pm {\sqrt {{\frac {16}{9}}-{\frac {4}{3}}}}}{2}}\!\,}
λ
1
=
1
{\displaystyle \lambda _{1}=1\!\,}
λ
2
=
1
3
{\displaystyle \lambda _{2}={\frac {1}{3}}\!\,}
![{\displaystyle [0,1]\!\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b26fc5fee30dada6f15cc080115cae582606d7f3)
![{\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}}\!\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b9b9e6d5911470776f77d41c90fbed8b46355e3a)
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1b18f0eb797936782217d092b825396d9801d1e7)
![{\displaystyle U_{h}=\{u\in H^{1}[0,1]:u(0)=0,u{\mbox{ piecewise linear }}\}\!\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4dc5b920e2f00501e8cbf02b486020a8fe252792)
![{\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}}\!\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e26bb53ae90b116aa37045ea5ec33261e0f43384)
