Problem 4
edit
Consider the system
x
=
1
+
h
e
−
x
2
1
+
y
2
,
y
=
.5
+
h
arctan
(
x
2
+
y
2
)
{\displaystyle x=1+h{\frac {e^{-x^{2}}}{1+y^{2}}}{\mbox{,}}\qquad y=.5+h\arctan(x^{2}+y^{2})\!\,}
Problem 4a
edit
Show that if the parameter
h
>
0
{\displaystyle h>0\!\,}
(
x
∗
,
y
∗
)
{\displaystyle (x^{*},y^{*})\!\,}
Solution 4a
edit
The system of equations may be expressed in matrix notation.
f
(
x
,
y
)
=
[
1
+
h
e
−
x
2
1
+
y
2
.5
+
h
arctan
(
x
2
+
y
2
)
]
{\displaystyle f(x,y)={\begin{bmatrix}1+h{\frac {e^{-x^{2}}}{1+y^{2}}}\\\\.5+h\arctan(x^{2}+y^{2})\end{bmatrix}}\!\,}
f
(
x
,
y
)
{\displaystyle f(x,y)\!\,}
J
(
f
)
{\displaystyle J(f)\!\,}
J
(
f
)
=
[
h
1
+
y
2
e
−
x
2
(
−
2
x
)
−
h
2
y
e
−
x
2
(
1
+
y
2
)
2
h
⋅
2
x
1
+
(
x
2
+
y
2
)
2
h
⋅
2
y
1
+
(
x
2
+
y
2
)
2
]
{\displaystyle J(f)={\begin{bmatrix}{\frac {h}{1+y^{2}}}e^{-x^{2}}(-2x)&{\frac {-h2ye^{-x^{2}}}{(1+y^{2})^{2}}}\\h\cdot {\frac {2x}{1+(x^{2}+y^{2})^{2}}}&h\cdot {\frac {2y}{1+(x^{2}+y^{2})^{2}}}\end{bmatrix}}\!\,}
h
{\displaystyle h\!\,}
x
,
y
{\displaystyle x,y\!\,}
B
{\displaystyle B\!\,}
‖
J
(
f
)
‖
⏟
C
<
1
{\displaystyle \underbrace {\|J(f)\|} _{C}<1\!\,}
x
1
→
,
x
2
→
∈
B
{\displaystyle {\vec {x_{1}}},{\vec {x_{2}}}\in B\!\,}
ξ
→
{\displaystyle {\vec {\xi }}\!\,}
f
(
x
1
→
)
−
f
(
x
2
→
)
=
J
(
f
(
ξ
→
)
)
(
x
1
→
−
x
2
→
)
{\displaystyle f({\vec {x_{1}}})-f({\vec {x_{2}}})=J(f({\vec {\xi }}))({\vec {x_{1}}}-{\vec {x_{2}}})\!\,}
‖
J
(
f
)
‖
{\displaystyle \|J(f)\|\!\,}
B
{\displaystyle B\!\,}
h
{\displaystyle h\!\,}
‖
f
(
x
1
→
)
−
f
(
x
2
→
)
‖
≤
C
‖
x
1
→
−
x
2
→
‖
{\displaystyle \|f({\vec {x_{1}}})-f({\vec {x_{2}}})\|\leq C\|{\vec {x_{1}}}-{\vec {x_{2}}}\|\!\,}
f
{\displaystyle f\!\,}
Problem 4b
edit
Derive a fixed point iteration scheme for solving the system and show that it converges.
{\displaystyle \!\,}
Solution 4b
edit
Use Newton Method
edit
To solve this problem, we can use the Newton Method. In fact, we want to find the zeros of
g
(
x
,
y
)
=
[
x
y
]
−
[
1
+
h
e
−
x
2
1
+
y
2
.5
+
h
arctan
(
x
2
+
y
2
)
]
{\displaystyle g(x,y)={\begin{bmatrix}x\\\\y\end{bmatrix}}-{\begin{bmatrix}1+h{\frac {e^{-x^{2}}}{1+y^{2}}}\\\\.5+h\arctan(x^{2}+y^{2})\end{bmatrix}}\!\,}
g
(
x
,
y
)
{\displaystyle g(x,y)\!\,}
J
(
g
)
{\displaystyle J(g)\!\,}
J
(
g
)
=
[
1
−
h
1
+
y
2
e
−
x
2
(
−
2
x
)
−
h
e
−
x
2
1
+
y
2
h
⋅
2
x
1
+
(
x
2
+
y
2
)
2
1
−
h
⋅
2
y
1
+
(
x
2
+
y
2
)
2
]
{\displaystyle J(g)={\begin{bmatrix}1-{\frac {h}{1+y^{2}}}e^{-x^{2}}(-2x)&{\frac {-he^{-x^{2}}}{1+y^{2}}}\\h\cdot {\frac {2x}{1+(x^{2}+y^{2})^{2}}}&1-h\cdot {\frac {2y}{1+(x^{2}+y^{2})^{2}}}\end{bmatrix}}\!\,}
[
x
k
+
1
y
k
+
1
]
=
[
x
k
y
k
]
−
1
d
e
t
(
J
(
g
)
)
[
1
−
h
⋅
2
y
1
+
(
x
2
+
y
2
)
2
h
e
−
x
2
1
+
y
2
−
h
⋅
2
x
1
+
(
x
2
+
y
2
)
2
1
−
h
1
+
y
2
e
−
x
2
(
−
2
x
)
]
⏟
J
(
g
)
−
1
g
(
x
k
,
y
k
)
{\displaystyle {\begin{bmatrix}x_{k+1}\\\\y_{k+1}\end{bmatrix}}={\begin{bmatrix}x_{k}\\\\y_{k}\end{bmatrix}}-\underbrace {{\frac {1}{det(J(g))}}{\begin{bmatrix}1-h\cdot {\frac {2y}{1+(x^{2}+y^{2})^{2}}}&{\frac {he^{-x^{2}}}{1+y^{2}}}\\-h\cdot {\frac {2x}{1+(x^{2}+y^{2})^{2}}}&1-{\frac {h}{1+y^{2}}}e^{-x^{2}}(-2x)\end{bmatrix}}} _{J(g)^{-1}}g(x_{k},y_{k})\!\,}
Show convergence by showing Newton hypothesis hold
edit
Jacobian of g is Lipschitz
edit
We want to show that
J
(
g
)
{\displaystyle J(g)\!\,}
‖
J
(
g
)
(
x
1
→
)
−
J
(
g
)
(
x
2
→
)
‖
=
‖
(
I
−
J
(
f
)
)
(
x
1
→
)
−
(
I
−
J
(
f
)
)
(
x
2
→
)
‖
=
‖
x
1
→
−
x
2
→
−
J
(
f
)
x
1
→
+
J
(
f
)
x
2
→
‖
≤
‖
x
1
→
−
x
2
→
‖
+
‖
J
(
f
)
x
2
→
−
J
(
f
)
x
1
→
‖
{\displaystyle {\begin{aligned}\|J(g)({\vec {x_{1}}})-J(g)({\vec {x_{2}}})\|&=\|(I-J(f))({\vec {x_{1}}})-(I-J(f))({\vec {x_{2}}})\|\\&=\|{\vec {x_{1}}}-{\vec {x_{2}}}-J(f){\vec {x_{1}}}+J(f){\vec {x_{2}}}\|\\&\leq \|{\vec {x_{1}}}-{\vec {x_{2}}}\|+\|J(f){\vec {x_{2}}}-J(f){\vec {x_{1}}}\|\end{aligned}}\!\,}
J
(
f
)
{\displaystyle J(f)\!\,}
‖
J
(
g
)
(
x
1
→
)
−
J
(
g
)
(
x
2
→
)
‖
≤
(
1
+
C
)
‖
(
x
1
→
)
−
(
x
2
→
)
‖
{\displaystyle \|J(g)({\vec {x_{1}}})-J(g)({\vec {x_{2}}})\|\leq (1+C)\|({\vec {x_{1}}})-({\vec {x_{2}}})\|\!\,}
Jacobian of g is invertible
edit
Since
J
(
f
)
{\displaystyle J(f)\!\,}
f
{\displaystyle f\!\,}
ρ
(
J
(
f
)
)
<
1
{\displaystyle \rho (J(f))<1\!\,}
J
(
g
)
{\displaystyle J(g)\!\,}
λ
(
J
(
g
)
)
=
1
−
λ
(
J
(
f
)
)
{\displaystyle \lambda (J(g))=1-\lambda (J(f))\!\,}
d
e
t
(
I
−
(
J
(
g
)
)
)
≠
0
{\displaystyle det(I-(J(g)))\neq 0\!\,}
J
(
g
)
{\displaystyle J(g)\!\,}
inverse of Jacobian of g is bounded
edit
1
d
e
t
(
J
(
g
)
)
[
1
−
h
⋅
2
y
1
+
(
x
2
+
y
2
)
2
h
e
−
x
2
1
+
y
2
−
h
⋅
2
x
1
+
(
x
2
+
y
2
)
2
1
−
h
1
+
y
2
e
−
x
2
(
−
2
x
)
]
⏟
J
(
g
)
−
1
{\displaystyle \underbrace {{\frac {1}{det(J(g))}}{\begin{bmatrix}1-h\cdot {\frac {2y}{1+(x^{2}+y^{2})^{2}}}&{\frac {he^{-x^{2}}}{1+y^{2}}}\\-h\cdot {\frac {2x}{1+(x^{2}+y^{2})^{2}}}&1-{\frac {h}{1+y^{2}}}e^{-x^{2}}(-2x)\end{bmatrix}}} _{J(g)^{-1}}\!\,}
J
(
g
)
−
1
{\displaystyle J(g)^{-1}\!\,}
det
(
J
(
g
)
)
≠
0
{\displaystyle {\mbox{det}}(J(g))\neq 0\!\,}
x
,
y
{\displaystyle x,y\!\,}
norm of (Jacobian of g)^-1 (x_0) * g(x_0) bounded
edit
‖
J
(
g
)
−
1
(
x
0
)
∗
g
(
x
0
)
‖
<
∞
{\displaystyle \|J(g)^{-1}(x_{0})*g(x_{0})\|<\infty \!\,}
J
(
g
)
−
1
{\displaystyle J(g)^{-1}\!\,}
g
(
x
)
{\displaystyle g(x)\!\,}
(
x
0
,
y
0
)
{\displaystyle (x_{0},y_{0})\!\,}
‖
(
x
k
−
1
,
y
k
+
1
)
−
(
x
∗
,
y
∗
)
‖
≤
K
‖
(
x
k
,
y
k
)
−
(
x
∗
,
y
∗
)
‖
2
.
{\displaystyle \|(x_{k-1},y_{k+1})-(x^{*},y^{*})\|\leq K\|(x_{k},y_{k})-(x^{*},y^{*})\|^{2}.\!\,}
Problem 5a
edit
Outline the derivation of the Adams-Bashforth methods for the numerical solution of the initial value problem
y
′
=
f
(
x
,
y
)
,
y
(
x
0
)
=
y
0
{\displaystyle y'=f(x,y){\mbox{, }}y(x_{0})=y_{0}\!\,}
Solution 5a
edit
We want to solve the following initial value problem:
y
′
=
f
(
x
,
y
)
,
y
(
x
0
)
=
y
0
{\displaystyle y'=f(x,y){\mbox{, }}y(x_{0})=y_{0}\!\,}
[
t
n
,
t
n
+
1
]
{\displaystyle [t_{n},t_{n+1}]\!\,}
y
(
t
n
+
1
)
=
y
(
t
n
)
+
∫
t
n
t
n
+
1
f
(
t
,
y
(
t
)
)
d
t
{\displaystyle y(t_{n+1})=y(t_{n})+\int _{t_{n}}^{t_{n+1}}f(t,y(t))dt\!\,}
f
(
t
,
y
(
t
)
)
{\displaystyle f(t,y(t))\!\,}
p
{\displaystyle p\!\,}
t
n
,
t
n
−
1
,
.
.
.
,
t
n
−
p
{\displaystyle t_{n},t_{n-1},...,t_{n-p}\!\,}
y
n
+
1
=
y
n
+
∫
t
n
t
n
−
1
∑
k
=
0
p
g
(
t
n
−
k
)
l
k
(
t
)
d
t
{\displaystyle y_{n+1}=y_{n}+\int _{t_{n}}^{t_{n-1}}\sum _{k=0}^{p}g(t_{n-k})l_{k}(t)dt\!\,}
y
n
{\displaystyle y_{n}\!\,}
g
(
t
)
≡
f
(
t
,
y
)
{\displaystyle g(t)\equiv f(t,y)\!\,}
l
k
(
t
)
{\displaystyle l_{k}(t)\!\,}
Problem 5b
edit
Derive the Adams-Bashforth formula
y
i
+
1
=
y
i
+
h
[
−
1
2
f
(
x
i
−
1
,
y
i
−
1
)
+
3
2
f
(
x
i
,
y
i
)
]
(
1
)
{\displaystyle y_{i+1}=y_{i}+h\left[-{\frac {1}{2}}f(x_{i-1},y_{i-1})+{\frac {3}{2}}f(x_{i},y_{i})\right]\qquad \qquad (1)\!\,}
Solution 5b
edit
From (a) we have
y
i
+
1
=
y
i
+
∫
x
i
x
i
+
1
f
d
x
{\displaystyle y_{i+1}=y_{i}+\int _{x_{i}}^{x_{i+1}}fdx\!\,}
∫
x
i
x
i
+
1
f
d
x
≈
∫
x
i
x
i
+
1
[
x
−
x
i
x
i
−
1
−
x
i
f
i
−
1
+
x
−
x
i
−
1
x
i
−
x
i
−
1
f
i
]
d
x
{\displaystyle \int _{x_{i}}^{x_{i+1}}fdx\approx \int _{x_{i}}^{x_{i+1}}\left[{\frac {x-x_{i}}{x_{i-1}-x_{i}}}f_{i-1}+{\frac {x-x_{i-1}}{x_{i}-x_{i-1}}}f_{i}\right]dx\!\,}
x
=
x
i
+
s
h
{\displaystyle x=x_{i}+sh\!\,}
d
x
=
h
d
s
x
−
x
i
=
s
h
x
−
x
i
−
1
=
(
1
+
s
)
h
x
i
−
x
i
−
1
=
h
{\displaystyle {\begin{aligned}dx&=hds\\x-x_{i}&=sh\\x-x_{i-1}&=(1+s)h\\x_{i}-x_{i-1}&=h\end{aligned}}}
h
∫
0
1
[
s
h
−
h
f
i
−
1
+
(
1
+
s
)
h
h
f
i
]
d
s
=
h
[
−
1
2
f
i
−
1
+
3
2
f
i
]
{\displaystyle h\int _{0}^{1}\left[{\frac {sh}{-h}}f_{i-1}+{\frac {(1+s)h}{h}}f_{i}\right]ds=h\left[-{\frac {1}{2}}f_{i-1}+{\frac {3}{2}}f_{i}\right]\!\,}
y
i
+
1
=
y
i
+
h
[
−
1
2
f
(
x
i
−
1
,
y
i
−
1
)
+
3
2
f
(
x
i
,
y
i
)
]
{\displaystyle y_{i+1}=y_{i}+h\left[-{\frac {1}{2}}f(x_{i-1},y_{i-1})+{\frac {3}{2}}f(x_{i},y_{i})\right]\!\,}
Problem 5c
edit
Analyze the method (1). To be specific, find the local truncation error, prove convergence and find the order of convergence.
Solution 5c
edit
Find Local Truncation Error Using Taylor Expansion
edit
Note that
y
i
≈
y
(
t
i
)
{\displaystyle y_{i}\approx y(t_{i})\!\,}
Δ
t
{\displaystyle \Delta t\!\,}
t
i
−
1
=
t
i
−
h
{\displaystyle t_{i-1}=t_{i}-h\!\,}
t
i
+
1
=
t
i
+
h
{\displaystyle t_{i+1}=t_{i}+h\!\,}
y
(
t
i
+
h
)
−
y
(
t
i
)
≈
h
[
−
1
2
y
′
(
t
i
−
h
)
+
3
2
y
′
(
t
i
)
]
{\displaystyle y(t_{i}+h)-y(t_{i})\approx h\left[-{\frac {1}{2}}y'(t_{i}-h)+{\frac {3}{2}}y'(t_{i})\right]\!\,}
Expand Left Hand Side
edit
Expanding about
t
i
{\displaystyle t_{i}\!\,}
Order
y
(
t
i
+
h
)
y
(
t
i
)
Σ
0
y
(
t
i
)
y
(
t
i
)
0
1
−
y
′
(
t
i
)
h
0
−
y
′
(
t
i
)
h
2
1
2
!
y
″
(
t
i
)
h
2
0
1
2
y
″
(
t
i
)
h
2
3
−
1
3
!
y
‴
(
t
i
)
h
3
0
−
1
6
y
‴
(
t
i
)
h
3
4
O
(
h
4
)
0
O
(
h
4
)
{\displaystyle {\begin{array}{|c|c|c|c|}{\mbox{Order}}&y(t_{i}+h)&y(t_{i})&\Sigma \\\hline &&&\\0&y(t_{i})&y(t_{i})&0\\&&&\\1&-y'(t_{i})h&0&-y'(t_{i})h\\&&&\\2&{\frac {1}{2!}}y''(t_{i})h^{2}&0&{\frac {1}{2}}y''(t_{i})h^{2}\\&&&\\3&-{\frac {1}{3!}}y'''(t_{i})h^{3}&0&-{\frac {1}{6}}y'''(t_{i})h^{3}\\&&&\\4&{\mathcal {O}}(h^{4})&0&{\mathcal {O}}(h^{4})\\&&&\\\hline \end{array}}}
Expand Right Hand side
edit
Also expanding about
t
i
{\displaystyle t_{i}\!\,}
Order
13
12
h
x
′
(
t
i
+
2
h
)
−
5
3
h
x
′
(
t
i
+
h
)
−
5
12
h
x
′
(
t
i
)
Σ
0
0
0
0
0
1
13
12
h
x
′
(
t
i
)
−
5
3
h
x
′
(
t
i
)
−
5
12
h
x
′
(
t
i
)
−
1
⋅
h
x
′
(
t
i
)
2
13
12
(
2
h
)
h
x
″
(
t
i
)
−
5
3
h
h
x
″
(
t
i
)
0
1
2
h
2
x
″
(
t
i
)
3
13
12
(
2
h
)
2
h
x
‴
(
t
i
)
2
−
5
3
h
2
h
x
‴
(
t
i
)
2
0
4
3
h
3
x
‴
(
t
i
)
4
O
(
h
4
)
O
(
h
4
)
0
O
(
h
4
)
{\displaystyle {\begin{array}{|c|c|c|c|c|}{\mbox{Order}}&{\frac {13}{12}}hx'(t_{i}+2h)&-{\frac {5}{3}}hx'(t_{i}+h)&-{\frac {5}{12}}hx'(t_{i})&\Sigma \\\hline &&&&\\0&0&0&0&0\\&&&&\\1&{\frac {13}{12}}hx'(t_{i})&-{\frac {5}{3}}hx'(t_{i})&-{\frac {5}{12}}hx'(t_{i})&-1\cdot hx'(t_{i})\\&&&&\\2&{\frac {13}{12}}(2h)hx''(t_{i})&-{\frac {5}{3}}hhx''(t_{i})&0&{\frac {1}{2}}h^{2}x''(t_{i})\\&&&&\\3&{\frac {13}{12}}(2h)^{2}{\frac {hx'''(t_{i})}{2}}&-{\frac {5}{3}}h^{2}{\frac {hx'''(t_{i})}{2}}&0&{\frac {4}{3}}h^{3}x'''(t_{i})\\&&&&\\4&{\mathcal {O}}(h^{4})&{\mathcal {O}}(h^{4})&0&{\mathcal {O}}(h^{4})\\\hline \end{array}}}
Show Convergence by Showing Stability and Consistency
edit
A method is convergent if and only if it is both stable and consistent.
Stability
edit
It is easy to show that the method is zero stable as it satisfies the root condition. So stable.
Consistency
edit
Truncation error is of order 2. Truncation error tends to zero as h tends to zeros. So the method is consistent.
Order of Convergence
edit
Dahlquist principle: consistency + stability = convergent. Order of convergence will be 2.
Problem 6
edit
Consider the problem
−
u
″
+
u
=
f
(
x
)
,
0
≤
x
≤
1
,
u
(
0
)
=
u
(
1
)
=
0.
(
2
)
{\displaystyle -u''+u=f(x),\;\;0\leq x\leq 1,\;\;u(0)=u(1)=0.\qquad \qquad (2)}
Problem 6a
edit
Give a variational formulation of (2), i.e. express (2) as
u
∈
H
,
B
(
x
,
y
)
=
F
(
v
)
,
∀
v
∈
H
(
3
)
{\displaystyle u\in H,\;\;B(x,y)=F(v),\;\;\forall v\in H\qquad \qquad (3)\!\,}
Define the Space H, the bilinear form B and the linear functional F, and state the relation between (2) and (3).
Solution 6a
edit
Multiplying (2) by a test function and using integration by parts we obtain:
−
∫
0
1
u
″
v
d
x
+
∫
0
1
u
v
d
x
=
∫
0
1
f
v
d
x
{\displaystyle -\int _{0}^{1}u''vdx+\int _{0}^{1}uvdx=\int _{0}^{1}fvdx\!\,}
−
u
′
v
|
0
1
⏟
0
+
∫
0
1
u
′
v
′
d
x
+
∫
0
1
u
v
d
x
=
∫
0
1
f
v
d
x
{\displaystyle \underbrace {\left.-u'v\right|_{0}^{1}} _{0}+\int _{0}^{1}u'v'dx+\int _{0}^{1}uvdx=\int _{0}^{1}fvdx\!\,}
u
∈
H
{\displaystyle u\in H\!\,}
B
(
u
,
v
)
=
∫
0
1
u
′
v
′
d
x
+
∫
0
1
u
v
d
x
=
∫
0
1
f
v
d
x
=
F
(
v
)
{\displaystyle B(u,v)=\int _{0}^{1}u'v'dx+\int _{0}^{1}uvdx=\int _{0}^{1}fvdx=F(v)\!\,}
v
∈
H
,
{\displaystyle v\in H,\!\,}
H
:=
H
0
1
(
0
,
1
)
=
{
v
:
v
∈
H
1
,
v
(
0
)
=
v
(
1
)
=
0
}
{\displaystyle H:=H_{0}^{1}(0,1)=\{v:v\in H^{1},v(0)=v(1)=0\}\!\,}
Problem 6b
edit
Let
0
=
x
0
<
x
1
<
⋯
<
x
n
=
1
{\displaystyle 0=x_{0}<x_{1}<\cdots <x_{n}=1\!\,}
[
0
,
1
]
{\displaystyle [0,1]\!\,}
h
=
max
j
=
0
,
1
,
…
,
n
−
1
(
x
j
+
1
−
x
j
)
{\displaystyle h=\max _{j=0,1,\dots ,n-1}(x_{j+1}-x_{j})\!\,}
V
h
=
{
u
:
u
continuous on
[
0
,
1
]
,
u
|
[
x
j
,
x
j
+
1
]
is linear for each
j
,
u
(
0
)
=
u
(
1
)
=
0
}
{\displaystyle V_{h}=\left\{u:u{\mbox{ continuous on }}[0,1],u|_{[x_{j},x_{j+1}]}{\mbox{ is linear for each }}j,u(0)=u(1)=0\right\}\!\,}
Define the finite element approximation,
u
h
to
u
{\displaystyle u_{h}{\mbox{ to }}u\!\,}
V
h
{\displaystyle V_{h}\!\,}
‖
u
−
u
h
‖
1
{\displaystyle \|u-u_{h}\|_{1}\!\,}
H
1
(
0
,
1
)
{\displaystyle H^{1}(0,1)\!\,}
Solution 6b
edit
Define piecewise linear basis
edit
For our basis of
V
h
{\displaystyle V_{h}\!\,}
{
ϕ
j
}
j
=
1
n
−
1
{\displaystyle \{\phi _{j}\}_{j=1}^{n-1}\!\,}
j
=
1
,
2
,
…
,
n
−
1
{\displaystyle j=1,2,\ldots ,n-1\!\,}
ϕ
j
(
x
)
=
{
x
−
x
j
−
1
x
j
−
x
j
−
1
for
x
∈
[
x
j
−
1
,
x
j
]
x
j
+
1
−
x
x
j
+
1
−
x
j
for
x
∈
[
x
j
,
x
j
+
1
]
0
otherwise
{\displaystyle \phi _{j}(x)={\begin{cases}{\frac {x-x_{j-1}}{x_{j}-x_{j-1}}}&{\mbox{for }}x\in [x_{j-1},x_{j}]\\{\frac {x_{j+1}-x}{x_{j+1}-x_{j}}}&{\mbox{for }}x\in [x_{j},x_{j+1}]\\0&{\mbox{otherwise}}\end{cases}}\!\,}
Define u_h
edit
Since
{
ϕ
j
}
j
=
1
n
−
1
{\displaystyle \{\phi _{j}\}_{j=1}^{n-1}\!\,}
V
h
{\displaystyle V_{h}\!\,}
u
h
∈
V
h
{\displaystyle u_{h}\in V_{h}\!\,}
u
h
=
∑
j
=
1
n
−
1
u
h
j
ϕ
j
{\displaystyle u_{h}=\sum _{j=1}^{n-1}u_{hj}\phi _{j}\!\,}
Discrete Problem
edit
Now, we can write the discrete problem: Find
u
h
∈
V
h
{\displaystyle u_{h}\in V_{h}\!\,}
B
(
u
h
,
v
h
)
=
F
(
v
h
)
{\displaystyle B(u_{h},v_{h})=F(v_{h})\!\,}
v
h
∈
V
h
.
{\displaystyle v_{h}\in V_{h}.\!\,}
{
ϕ
j
}
j
=
1
n
−
1
{\displaystyle \{\phi _{j}\}_{j=1}^{n-1}\!\,}
V
h
{\displaystyle V_{h}\!\,}
B
{\displaystyle B\!\,}
F
{\displaystyle F\!\,}
u
h
=
(
u
h
,
1
,
…
,
u
h
,
n
−
1
)
∈
R
n
−
1
{\displaystyle u_{h}=(u_{h,1},\dots ,u_{h,{n-1}})\in \mathbb {R} ^{n-1}\!\,}
∑
j
=
1
n
−
1
u
h
,
j
{
∫
0
1
ϕ
j
′
ϕ
i
′
d
x
+
∫
0
1
ϕ
j
ϕ
i
d
x
}
=
∫
0
1
f
ϕ
i
d
x
,
i
=
1
,
…
,
n
−
1.
{\displaystyle \sum _{j=1}^{n-1}u_{h,j}\left\{\int _{0}^{1}\phi _{j}'\phi _{i}'dx+\int _{0}^{1}\phi _{j}\phi _{i}dx\right\}=\int _{0}^{1}f\phi _{i}dx,\quad i=1,\dots ,n-1.\!\,}
u
h
=
(
u
h
,
1
,
…
,
u
h
,
n
−
1
)
∈
R
n
−
1
{\displaystyle u_{h}=(u_{h,1},\dots ,u_{h,{n-1}})\in \mathbb {R} ^{n-1}\!\,}
A
u
h
=
F
,
{\displaystyle Au_{h}=F,\!\,}
A
i
j
=
∫
0
1
ϕ
j
′
ϕ
i
′
d
x
+
∫
0
1
ϕ
j
ϕ
i
d
x
{\displaystyle A_{ij}=\int _{0}^{1}\phi _{j}'\phi _{i}'dx+\int _{0}^{1}\phi _{j}\phi _{i}dx\!\,}
F
j
=
∫
0
1
f
ϕ
i
d
x
{\displaystyle F_{j}=\int _{0}^{1}f\phi _{i}dx\!\,}
Bound error
edit
In general terms, we can use Cea's Lemma to obtain
‖
u
−
u
h
‖
1
≤
C
inf
v
h
∈
V
h
‖
u
−
v
h
‖
1
{\displaystyle \|u-u_{h}\|_{1}\leq C\inf _{v_{h}\in V_{h}}\|u-v_{h}\|_{1}}
v
h
{\displaystyle v_{h}\!\,}
v
I
{\displaystyle v_{I}\!\,}
‖
u
−
u
h
‖
1
≤
C
‖
u
−
v
I
‖
1
≤
C
h
‖
u
‖
H
2
(
0
,
1
)
{\displaystyle \|u-u_{h}\|_{1}\leq C\|u-v_{I}\|_{1}\leq Ch\|u\|_{H^{2}(0,1)}}
‖
u
(
x
)
−
u
h
(
x
)
‖
L
∞
(
[
x
i
−
1
,
x
i
]
)
≤
max
x
∈
[
x
i
−
1
,
x
i
]
u
(
2
)
(
x
)
(
2
)
!
(
h
2
)
2
{\displaystyle \|u(x)-u_{h}(x)\|_{L^{\infty }([x_{i-1},x_{i}])}\leq \max _{x\in [x_{i-1},x_{i}]}{\frac {u^{(2)}(x)}{(2)!}}\left({\frac {h}{2}}\right)^{2}}
Problem 6c
edit
Derive the estimate for
‖
u
−
u
h
‖
0
{\displaystyle \|u-u_{h}\|_{0}\!\,}
L
2
(
0
,
1
)
{\displaystyle L_{2}(0,1)\!\,}
(#) :
{
−
w
″
+
w
=
u
−
u
h
,
w
(
0
)
=
w
(
1
)
=
0.
{\displaystyle {\begin{cases}-w''+w=u-u_{h},\\w(0)=w(1)=0.\end{cases}}}
We characterize
w
{\displaystyle w\!\,}
w
∈
H
0
1
,
B
(
w
,
v
)
=
∫
(
u
−
u
h
)
v
d
x
,
∀
v
∈
H
0
1
{\displaystyle w\in H_{0}^{1},\;\;B(w,v)=\int (u-u_{h})vdx,\forall v\in H_{0}^{1}\!\,}
Let
v
=
u
−
u
h
{\displaystyle v=u-u_{h}\!\,}
B
(
w
,
u
−
u
h
)
=
∫
(
u
−
u
h
)
2
d
x
=
‖
u
−
u
h
‖
L
2
2
.
(
4
)
{\displaystyle B(w,u-u_{h})=\int (u-u_{h})^{2}dx=\|u-u_{h}\|_{L_{2}}^{2}.\qquad \qquad (4)\!\,}
Use formula (4) to estimate
‖
u
−
u
h
‖
L
2
{\displaystyle \|u-u_{h}\|_{L_{2}}\!\,}
Solution 6c
edit
Continuity of Bilinear Form
edit
B
(
u
,
v
)
=
∫
u
v
+
∫
u
′
v
′
≤
‖
u
‖
0
‖
v
‖
0
+
‖
u
′
‖
0
‖
v
′
‖
0
(Cauchy-Schwarz in L2)
≤
(
‖
u
‖
0
2
+
‖
u
′
‖
0
2
)
1
2
(
‖
v
‖
0
2
+
‖
v
′
‖
2
)
1
2
( Cauchy-Schwarz in R2 )
=
‖
u
‖
1
⋅
‖
v
‖
1
{\displaystyle {\begin{aligned}B(u,v)&=\int uv+\int u'v'\\&\leq \|u\|_{0}\|v\|_{0}+\|u'\|_{0}\|v'\|_{0}{\mbox{ (Cauchy-Schwarz in L2) }}\\&\leq (\|u\|_{0}^{2}+\|u'\|_{0}^{2})^{\frac {1}{2}}(\|v\|_{0}^{2}+\|v'\|^{2})^{\frac {1}{2}}{\mbox{ ( Cauchy-Schwarz in R2 ) }}\\&=\|u\|_{1}\cdot \|v\|_{1}\end{aligned}}\!\,}
Orthogonality of the Error
edit
B
(
u
−
u
h
,
v
h
)
=
0
,
∀
v
h
∈
V
h
{\displaystyle B(u-u_{h},v_{h})=0,\quad \forall v_{h}\in V_{h}\!\,}
Bound for L2 norm of w
edit
‖
w
‖
0
2
≤
‖
w
‖
1
2
=
B
(
w
,
w
)
=
∫
(
u
−
u
h
)
w
≤
‖
u
−
u
h
‖
0
‖
w
‖
0
(Cauchy-Schwarz in L2 )
{\displaystyle {\begin{aligned}\|w\|_{0}^{2}&\leq \|w\|_{1}^{2}\\&=B(w,w)\\&=\int (u-u_{h})w\\&\leq \|u-u_{h}\|_{0}\|w\|_{0}{\mbox{ (Cauchy-Schwarz in L2 ) }}\end{aligned}}\!\,}
(
∗
)
‖
w
‖
0
≤
‖
u
−
u
h
‖
0
{\displaystyle (*)\qquad \|w\|_{0}\leq \|u-u_{h}\|_{0}\!\,}
Bound for L2 norm of w
edit
From
(
#
)
{\displaystyle (\#)\!\,}
−
w
″
+
w
=
u
−
u
h
{\displaystyle -w''+w=u-u_{h}\!\,}
‖
w
″
‖
0
≤
‖
w
‖
0
+
‖
u
−
u
h
‖
0
(triangle inequality)
≤
‖
u
−
u
h
‖
0
+
‖
u
−
u
h
‖
0
(by (*) )
=
2
‖
u
−
u
h
‖
0
{\displaystyle {\begin{aligned}\|w''\|_{0}&\leq \|w\|_{0}+\|u-u_{h}\|_{0}{\mbox{ (triangle inequality) }}\\&\leq \|u-u_{h}\|_{0}+\|u-u_{h}\|_{0}{\mbox{ (by (*) ) }}\\&=2\|u-u_{h}\|_{0}\end{aligned}}\!\,}
Bound L2 Error
edit
‖
u
−
u
h
‖
L
2
2
=
B
(
w
,
u
−
u
h
)
( from equation (4) )
=
B
(
w
,
u
−
u
h
)
−
B
(
w
h
,
u
−
u
h
)
⏟
0
=
B
(
w
−
w
h
,
u
−
u
h
)
≤
‖
w
−
w
h
‖
H
1
(
0
,
1
)
‖
u
−
u
h
‖
H
1
(
0
,
1
)
(Continuity of Bilinear Form)
≤
C
h
‖
w
‖
H
2
(
0
,
1
)
‖
u
−
u
h
‖
H
1
(
0
,
1
)
(Cea Lemma and Polynomial Interpolation Error)
{\displaystyle {\begin{aligned}\|u-u_{h}\|_{L^{2}}^{2}&=B(w,u-u_{h}){\mbox{ ( from equation (4) ) }}\\&=B(w,u-u_{h})-\underbrace {B(w_{h},u-u_{h})} _{0}\\&=B(w-w_{h},u-u_{h})\\&\leq \|w-w_{h}\|_{H^{1}(0,1)}\|u-u_{h}\|_{H^{1}(0,1)}{\mbox{ (Continuity of Bilinear Form) }}\\&\leq Ch\|w\|_{H^{2}(0,1)}\|u-u_{h}\|_{H^{1}(0,1)}{\mbox{ (Cea Lemma and Polynomial Interpolation Error) }}\end{aligned}}}
‖
w
‖
H
2
(
0
,
1
)
≤
C
‖
u
−
u
h
‖
L
2
(
0
,
1
)
{\displaystyle \|w\|_{H^{2}(0,1)}\leq C\|u-u_{h}\|_{L_{2}(0,1)}\!\,}
‖
u
−
u
h
‖
L
2
(
0
,
1
)
2
≤
C
h
‖
u
−
u
h
‖
L
2
(
0
,
1
)
‖
u
−
u
h
‖
H
1
(
0
,
1
)
{\displaystyle \|u-u_{h}\|_{L^{2}(0,1)}^{2}\leq Ch\|u-u_{h}\|_{L_{2}(0,1)}\|u-u_{h}\|_{H^{1}(0,1)}\!\,}
‖
u
−
u
h
‖
L
2
(
0
,
1
)
≤
C
h
‖
u
−
u
h
‖
H
1
(
0
,
1
)
≤
C
h
2
‖
u
‖
H
2
(
0
,
1
)
{\displaystyle \|u-u_{h}\|_{L^{2}(0,1)}\leq Ch\|u-u_{h}\|_{H^{1}(0,1)}\leq Ch^{2}\|u\|_{H^{2}(0,1)}\!\,}
Problem 6d
edit
Suppose
{
ϕ
1
h
,
…
,
ϕ
N
h
h
}
{\displaystyle \{\phi _{1}^{h},\dots ,\phi _{N_{h}}^{h}\}\!\,}
V
h
where
N
h
=
dim
V
h
, so
u
h
=
∑
j
=
1
N
h
c
j
h
ϕ
j
h
, for appropriate coefficients
c
j
h
.
{\displaystyle V_{h}{\mbox{ where }}N_{h}=\dim V_{h}{\mbox{, so }}u_{h}=\sum _{j=1}^{N_{h}}c_{j}^{h}\phi _{j}^{h}{\mbox{, for appropriate coefficients }}c_{j}^{h}.\!\,}
‖
u
−
u
h
‖
1
2
=
‖
u
‖
1
2
−
C
T
A
C
{\displaystyle \|u-u_{h}\|_{1}^{2}=\|u\|_{1}^{2}-C^{T}AC\!\,}
where
C
=
[
c
1
h
,
…
,
c
N
h
h
]
T
and
A
{\displaystyle C=[c_{1}^{h},\dots ,c_{N_{h}}^{h}]^{T}{\mbox{ and }}A\!\,}
Solution 6d
edit
We know that
‖
u
−
u
h
‖
1
2
=
⟨
u
−
u
h
,
u
−
u
h
⟩
H
1
(
0
,
1
)
=
⟨
u
−
u
h
,
u
⟩
H
1
(
0
,
1
)
−
⟨
u
−
u
h
,
u
h
⟩
H
1
(
0
,
1
)
⏟
0
=
‖
u
‖
H
1
(
0
,
1
)
2
−
⟨
u
h
,
u
⟩
H
1
(
0
,
1
)
=
‖
u
‖
H
1
(
0
,
1
)
2
−
‖
u
h
‖
H
1
(
0
,
1
)
2
{\displaystyle {\begin{aligned}\|u-u_{h}\|_{1}^{2}&=\langle u-u_{h},u-u_{h}\rangle _{H^{1}(0,1)}\\&=\langle u-u_{h},u\rangle _{H^{1}(0,1)}-\underbrace {\langle u-u_{h},u_{h}\rangle _{H^{1}(0,1)}} _{0}\\&=\|u\|_{H^{1}(0,1)}^{2}-\langle u_{h},u\rangle _{H^{1}(0,1)}\\&=\|u\|_{H^{1}(0,1)}^{2}-\|u_{h}\|_{H^{1}(0,1)}^{2}\end{aligned}}}
‖
u
h
‖
H
1
(
0
,
1
)
2
=
∑
j
=
1
n
−
1
∑
i
=
1
n
−
1
u
h
,
j
u
h
,
i
(
∫
0
1
ϕ
i
′
ϕ
j
′
d
x
+
∫
0
1
ϕ
i
ϕ
j
d
x
)
=
∑
j
=
1
n
−
1
∑
i
=
1
n
−
1
u
h
,
j
A
i
j
u
h
,
i
=
C
t
A
C
.
{\displaystyle \|u_{h}\|_{H^{1}(0,1)}^{2}=\sum _{j=1}^{n-1}\sum _{i=1}^{n-1}u_{h,j}u_{h,i}\left(\int _{0}^{1}\phi _{i}'\phi _{j}'dx+\int _{0}^{1}\phi _{i}\phi _{j}dx\right)=\sum _{j=1}^{n-1}\sum _{i=1}^{n-1}u_{h,j}A_{ij}u_{h,i}=C^{t}AC.\!\,}
‖
u
−
u
h
‖
1
2
=
‖
u
‖
H
1
(
0
,
1
)
2
−
C
t
A
C
.
{\displaystyle \|u-u_{h}\|_{1}^{2}=\|u\|_{H^{1}(0,1)}^{2}-C^{t}AC.\!\,}
![{\displaystyle [t_{n},t_{n+1}]\!\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/29989780e8a16a1a21ec2dc9993bf01247bc8991)
![{\displaystyle y_{i+1}=y_{i}+h\left[-{\frac {1}{2}}f(x_{i-1},y_{i-1})+{\frac {3}{2}}f(x_{i},y_{i})\right]\qquad \qquad (1)\!\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bdf88b88a6c46efff56063d3ee3d3603e493391a)
![{\displaystyle \int _{x_{i}}^{x_{i+1}}fdx\approx \int _{x_{i}}^{x_{i+1}}\left[{\frac {x-x_{i}}{x_{i-1}-x_{i}}}f_{i-1}+{\frac {x-x_{i-1}}{x_{i}-x_{i-1}}}f_{i}\right]dx\!\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/466e9d3b14eac67a715c9882145ecef47c81744a)
![{\displaystyle h\int _{0}^{1}\left[{\frac {sh}{-h}}f_{i-1}+{\frac {(1+s)h}{h}}f_{i}\right]ds=h\left[-{\frac {1}{2}}f_{i-1}+{\frac {3}{2}}f_{i}\right]\!\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a745514c9f1e97c58dd997ce651e671a8ff8ac9c)
![{\displaystyle y_{i+1}=y_{i}+h\left[-{\frac {1}{2}}f(x_{i-1},y_{i-1})+{\frac {3}{2}}f(x_{i},y_{i})\right]\!\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a99692eb614b14fdae6ae48361c98bc7a03620d1)
![{\displaystyle y(t_{i}+h)-y(t_{i})\approx h\left[-{\frac {1}{2}}y'(t_{i}-h)+{\frac {3}{2}}y'(t_{i})\right]\!\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/243beab488418cd720fb6290434d79760def9918)
![{\displaystyle [0,1]\!\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b26fc5fee30dada6f15cc080115cae582606d7f3)
![{\displaystyle V_{h}=\left\{u:u{\mbox{ continuous on }}[0,1],u|_{[x_{j},x_{j+1}]}{\mbox{ is linear for each }}j,u(0)=u(1)=0\right\}\!\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a95e0f541138310d2f9ce87652cfb0a7efed13d6)
![{\displaystyle \phi _{j}(x)={\begin{cases}{\frac {x-x_{j-1}}{x_{j}-x_{j-1}}}&{\mbox{for }}x\in [x_{j-1},x_{j}]\\{\frac {x_{j+1}-x}{x_{j+1}-x_{j}}}&{\mbox{for }}x\in [x_{j},x_{j+1}]\\0&{\mbox{otherwise}}\end{cases}}\!\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/30aeab13219b8f6987a339e9e52d1011ec1fa9e1)
![{\displaystyle \|u(x)-u_{h}(x)\|_{L^{\infty }([x_{i-1},x_{i}])}\leq \max _{x\in [x_{i-1},x_{i}]}{\frac {u^{(2)}(x)}{(2)!}}\left({\frac {h}{2}}\right)^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7b552127b2bb16415666c670a1694adc52f122ec)
![{\displaystyle C=[c_{1}^{h},\dots ,c_{N_{h}}^{h}]^{T}{\mbox{ and }}A\!\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ced43992ba50e0a5ed770d0cec7899f33c666d88)
