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-Schwartz in L2)
≤
(
‖
u
‖
0
2
+
‖
u
′
‖
0
2
)
1
2
(
‖
v
‖
0
2
+
‖
v
′
‖
2
)
1
2
( Cauchy-Schwartz 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-Schwartz in L2) }}\\&\leq (\|u\|_{0}^{2}+\|u'\|_{0}^{2})^{\frac {1}{2}}(\|v\|_{0}^{2}+\|v'\|^{2})^{\frac {1}{2}}{\mbox{ ( Cauchy-Schwartz 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-Schwartz 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-Schwartz 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)
