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})\!\,}
Show that if the parameter
h
>
0
{\displaystyle h>0\!\,}
(
x
∗
,
y
∗
)
{\displaystyle (x^{*},y^{*})\!\,}
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\!\,}
Derive a fixed point iteration scheme for solving the system and show that it converges.
{\displaystyle \!\,}
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\!\,}
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}.\!\,}
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}\!\,}
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)\!\,}
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)\!\,}
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]\!\,}
Analyze the method (1). To be specific, find the local truncation error, prove convergence and find the order of convergence.
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.
It is easy to show that the method is zero stable as it satisfies the root condition. So stable.
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.
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)}
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).
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\}\!\,}
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)\!\,}
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}}\!\,}
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}\!\,}
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\!\,}
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}}
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}}\!\,}
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}}\!\,}
‖
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)}\!\,}
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\!\,}
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)
