One wants to solve the equation
x
+
ln
x
=
0
{\displaystyle x+\ln x=0\!\,}
r
≈
0.5
{\displaystyle r\approx 0.5\!\,}
x
k
+
1
=
−
ln
x
k
{\displaystyle x_{k+1}=-\ln x_{k}\!\,}
x
k
+
1
=
e
−
x
k
{\displaystyle x_{k+1}=e^{-x_{k}}\!\,}
x
k
+
1
=
x
k
+
e
−
x
k
2
{\displaystyle x_{k+1}={\frac {x_{k}+e^{-x_{k}}}{2}}\!\,}
Which of the three methods can be used?
Methods {ii} and {iii} are appropriate fixed point iterations for
x
+
ln
(
x
)
=
0
{\displaystyle x+\ln(x)=0\!\,}
edit
To be a suitable fixed point iteration, the range of each iteration must be within the domain of the next iteration. In the case of {i},
x
k
+
1
=
−
ln
x
k
{\displaystyle x_{k+1}=-\ln x_{k}\!\,}
(
−
∞
,
∞
)
{\displaystyle (-\infty ,\infty )\!\,}
(
0
,
∞
)
{\displaystyle (0,\infty )\!\,}
edit
Let
f
(
x
)
:=
e
−
x
{\displaystyle f(x):=e^{-x}\!\,}
g
(
x
)
:=
x
+
e
−
x
2
{\displaystyle g(x):={\frac {x+e^{-x}}{2}}\!\,}
f
:
(
−
∞
,
∞
)
→
(
0
,
∞
)
{\displaystyle f:(-\infty ,\infty )\to (0,\infty )\!\,}
and
g
:
(
−
∞
,
∞
)
→
(
0
,
∞
)
{\displaystyle g:(-\infty ,\infty )\to (0,\infty )\!\,}
D
=
(
0
,
1
)
{\displaystyle D=(0,1)}
|
f
(
x
)
−
f
(
y
)
|
≤
|
f
′
(
η
)
|
|
x
−
y
|
{\displaystyle |f(x)-f(y)|\leq |f'(\eta )||x-y|\!\,}
η
∈
D
{\displaystyle \eta \in D\!\,}
where
max
η
∈
D
|
f
′
(
η
)
|
=
max
η
∈
D
|
e
−
x
|
≤
1
{\displaystyle \max _{\eta \in D}|f'(\eta )|=\max _{\eta \in D}|e^{-x}|\leq 1\!\,}
|
g
(
x
)
−
g
(
y
)
|
≤
|
g
′
(
η
)
|
|
x
−
y
|
{\displaystyle |g(x)-g(y)|\leq |g'(\eta )||x-y|\!\,}
η
∈
D
{\displaystyle \eta \in D\!\,}
where
max
η
∈
D
|
g
′
(
η
)
|
=
max
η
∈
D
|
1
2
(
1
−
e
−
x
)
|
≈
0.316060279
{\displaystyle \max _{\eta \in D}|g'(\eta )|=\max _{\eta \in D}|{\frac {1}{2}}(1-e^{-x})|\approx 0.316060279\!\,}
Which method should be used?
For the interval (0,1), {iii} is a better fixed point iteration than {ii} since its Lipschitz constant is smaller.
Give an even better iterative formula.
Newton's method gives an iterative formula that has quadratic convergence, compared to {iii}'s linear convergence.
Consider the boundary value problem
{
−
u
″
+
e
u
=
0
0
<
x
<
1
u
(
0
)
=
u
(
1
)
=
0
{\displaystyle {\begin{cases}-u''+e^{u}=0&0<x<1\\u(0)=u(1)=0&\end{cases}}\!\,}
A
U
h
+
F
h
(
U
h
)
=
0
{\displaystyle AU_{h}+F_{h}(U_{h})=0\!\,}
U
h
∈
R
m
{\displaystyle U_{h}\in \mathbb {R} ^{m}\!\,}
A
{\displaystyle A\!\,}
m
×
m
{\displaystyle m\times m\!\,}
h
{\displaystyle h\!\,}
F
h
:
R
m
→
R
m
{\displaystyle F_{h}:\mathbb {R} ^{m}\rightarrow \mathbb {R} ^{m}\!\,}
Let
V
=
H
0
1
(
0
,
1
)
:=
{
v
∈
H
1
:
v
(
0
)
=
v
(
1
)
=
0
}
{\displaystyle V=H_{0}^{1}(0,1):=\{v\in H^{1}:v(0)=v(1)=0\}\!\,}
Multiplying by a test function
v
∈
V
{\displaystyle v\in V\!\,}
∫
0
1
(
−
u
″
v
)
d
x
=
∫
0
1
u
′
v
′
d
x
−
u
′
v
|
0
1
=
∫
0
1
u
′
v
′
d
x
{\displaystyle \int _{0}^{1}(-u''v)dx=\int _{0}^{1}u'v'dx-\left.u'v\right|_{0}^{1}=\int _{0}^{1}u'v'dx\!\,}
Then the Variational formulation is: Find
u
∈
V
{\displaystyle u\in V\!\,}
a
(
u
,
v
)
=
∫
0
1
u
′
v
′
d
x
+
∫
0
1
e
u
v
d
x
=
l
(
v
)
=
0
{\displaystyle a(u,v)=\int _{0}^{1}u'v'dx+\int _{0}^{1}e^{u}vdx=l(v)=0\!\,}
v
∈
V
{\displaystyle v\in V\!\,}
Define piecewise linear basis functions
edit
Let's consider a partition of the interval
[
0
,
1
]
{\displaystyle [0,1]\!\,}
τ
h
:
0
=
x
0
<
x
1
<
⋯
<
x
m
+
1
=
1
{\displaystyle {\mathcal {\tau }}_{h}:0=x_{0}<x_{1}<\dots <x_{m+1}=1\!\,}
V
h
=
{
v
∈
V
:
v
|
[
x
i
−
1
,
x
i
]
∈
P
1
(
[
x
i
−
1
,
x
i
]
)
,
i
=
1
,
…
,
m
+
1
,
v
(
0
)
=
v
(
1
)
=
0
}
{\displaystyle V_{h}=\{v\in V:\left.v\right|_{[x_{i-1},x_{i}]}\in {\mathcal {P}}_{1}([x_{i-1},x_{i}]),i=1,\dots ,m+1,v(0)=v(1)=0\}\!\,}
V
h
{\displaystyle V_{h}\!\,}
{
ϕ
j
}
j
=
1
m
{\displaystyle \{\phi _{j}\}_{j=1}^{m}\!\,}
j
=
1
,
2
,
…
,
m
{\displaystyle j=1,2,\ldots ,m\!\,}
ϕ
j
(
x
)
=
{
x
−
x
j
−
1
h
for
x
∈
[
x
j
−
1
,
x
j
]
x
j
+
1
−
x
h
for
x
∈
[
x
j
,
x
j
+
1
]
0
otherwise
{\displaystyle \phi _{j}(x)={\begin{cases}{\frac {x-x_{j-1}}{h}}&{\mbox{for }}x\in [x_{j-1},x_{j}]\\{\frac {x_{j+1}-x}{h}}&{\mbox{for }}x\in [x_{j},x_{j+1}]\\0&{\mbox{otherwise}}\end{cases}}\!\,}
Therefore,
ϕ
j
′
(
x
)
=
{
1
h
for
x
∈
[
x
j
−
1
,
x
j
]
−
1
h
for
x
∈
[
x
j
,
x
j
+
1
]
0
otherwise
{\displaystyle \phi _{j}'(x)={\begin{cases}{\frac {1}{h}}&{\mbox{for }}x\in [x_{j-1},x_{j}]\\-{\frac {1}{h}}&{\mbox{for }}x\in [x_{j},x_{j+1}]\\0&{\mbox{otherwise}}\end{cases}}\!\,}
u
h
∈
V
h
{\displaystyle u_{h}\in V_{h}\!\,}
a
(
u
h
,
v
h
)
=
∫
0
1
u
h
′
v
h
′
d
x
+
∫
0
1
e
u
h
v
h
d
x
=
0
,
∀
v
h
∈
V
h
{\displaystyle a(u_{h},v_{h})=\int _{0}^{1}u_{h}'v_{h}'dx+\int _{0}^{1}e^{u_{h}}v_{h}dx=0,\forall v_{h}\in V_{h}\!\,}
{
ϕ
j
}
j
=
1
m
{\displaystyle \{\phi _{j}\}_{j=1}^{m}\!\,}
V
h
{\displaystyle V_{h}\!\,}
u
h
=
∑
j
=
1
n
u
h
j
ϕ
j
{\displaystyle u_{h}=\sum _{j=1}^{n}u_{hj}\phi _{j}\!\,}
u
h
=
(
u
h
1
,
…
,
u
h
m
)
t
{\displaystyle u_{h}=(u_{h1},\ldots ,u_{hm})^{t}\!\,}
a
(
u
h
,
ϕ
i
)
=
∑
j
=
1
m
u
h
j
∫
x
i
−
1
x
i
+
1
ϕ
j
′
ϕ
i
′
d
x
+
∫
x
i
−
1
x
i
+
1
e
∑
j
=
1
m
u
h
j
ϕ
j
ϕ
i
d
x
=
0
for
i
=
1
,
…
,
m
{\displaystyle a(u_{h},\phi _{i})=\sum _{j=1}^{m}u_{hj}\int _{x_{i-1}}^{x_{i+1}}\phi _{j}'\phi _{i}'dx+\int _{x_{i-1}}^{x_{i+1}}e^{\sum _{j=1}^{m}u_{hj}\phi _{j}}\phi _{i}dx=0{\mbox{ for }}i=1,\dots ,m\!\,}
The equivalent discrete problem for
i
=
1
,
2
,
…
,
m
{\displaystyle i=1,2,\ldots ,m\!\,}
∑
j
=
1
m
u
h
j
∫
x
i
−
1
x
i
+
1
ϕ
j
′
ϕ
i
′
d
x
+
∫
x
i
−
1
x
i
+
1
e
∑
j
=
1
m
u
h
j
ϕ
j
ϕ
i
d
x
=
0
{\displaystyle \sum _{j=1}^{m}u_{hj}\int _{x_{i-1}}^{x_{i+1}}\phi _{j}'\phi _{i}'dx+\int _{x_{i-1}}^{x_{i+1}}e^{\sum _{j=1}^{m}u_{hj}\phi _{j}}\phi _{i}dx=0\!\,}
[
2
h
−
1
h
…
⋱
⋱
⋱
−
1
h
2
h
−
1
h
−
1
h
2
h
]
⏟
A
[
u
h
1
⋮
⋮
u
h
m
]
⏟
U
h
+
h
[
e
u
h
1
e
u
h
2
⋮
e
u
h
m
]
⏟
F
h
(
U
h
)
{\displaystyle \underbrace {\begin{bmatrix}{\frac {2}{h}}&-{\frac {1}{h}}&&\ldots \\\ddots &\ddots &\ddots &\\&-{\frac {1}{h}}&{\frac {2}{h}}&-{\frac {1}{h}}\\&&-{\frac {1}{h}}&{\frac {2}{h}}\end{bmatrix}} _{A}\underbrace {\begin{bmatrix}u_{h1}\\\vdots \\\vdots \\u_{hm}\end{bmatrix}} _{U_{h}}+\underbrace {h{\begin{bmatrix}e^{u_{h1}}\\e^{u_{h2}}\\\vdots \\e^{u_{hm}}\end{bmatrix}}} _{F_{h}(U_{h})}\!\,}
∫
0
1
ϕ
j
′
ϕ
i
′
=
{
2
h
for
i
=
j
−
1
h
for
|
i
−
j
|
=
1
0
otherwise
{\displaystyle {\begin{aligned}\int _{0}^{1}\phi _{j}'\phi _{i}'&={\begin{cases}{\frac {2}{h}}&{\mbox{for }}i=j\\-{\frac {1}{h}}&{\mbox{for }}|i-j|=1\\0&{\mbox{otherwise}}\end{cases}}\end{aligned}}\!\,}
∫
x
i
−
1
x
i
+
1
e
u
h
ϕ
i
(
x
)
=
∫
x
i
−
1
x
i
e
u
h
ϕ
i
(
x
)
+
∫
x
i
x
i
+
1
e
u
h
ϕ
i
(
x
)
≈
(
e
u
h
(
x
i
−
1
)
ϕ
i
(
x
i
−
1
)
⏞
0
+
e
u
h
(
x
i
)
ϕ
i
(
x
i
)
2
)
h
+
(
e
u
h
(
x
i
)
ϕ
i
(
x
i
)
+
e
u
h
(
x
i
+
1
)
ϕ
i
(
x
i
+
1
)
⏞
0
2
)
h
=
h
e
u
h
(
x
i
)
ϕ
i
(
x
i
)
⏞
1
=
h
e
u
h
(
x
i
)
=
h
e
∑
j
=
1
m
u
h
j
ϕ
j
(
x
i
)
=
h
e
u
h
i
{\displaystyle {\begin{aligned}\int _{x_{i-1}}^{x_{i+1}}e^{u_{h}}\phi _{i}(x)&=\int _{x_{i-1}}^{x_{i}}e^{u_{h}}\phi _{i}(x)+\int _{x_{i}}^{x_{i+1}}e^{u_{h}}\phi _{i}(x)\\&\approx \left({\frac {e^{u_{h}(x_{i-1})}\overbrace {\phi _{i}(x_{i-1})} ^{0}+e^{u_{h}(x_{i})}\phi _{i}(x_{i})}{2}}\right)h+\left({\frac {e^{u_{h}(x_{i})}\phi _{i}(x_{i})+e^{u_{h}(x_{i+1})}\overbrace {\phi _{i}(x_{i+1})} ^{0}}{2}}\right)h\\&=he^{u_{h}(x_{i})}\overbrace {\phi _{i}(x_{i})} ^{1}\\&=he^{u_{h}(x_{i})}\\&=he^{\sum _{j=1}^{m}u_{hj}\phi _{j}(x_{i})}\\&=he^{u_{hi}}\end{aligned}}\!\,}
u
h
0
=
u
h
(
m
+
1
)
=
0
{\displaystyle u_{h0}=u_{h(m+1)}=0\!\,}
Determine the local order of accuracy and the stability properties of the two-step scheme
x
i
+
2
−
3
x
i
+
1
+
2
x
i
=
Δ
t
⋅
[
13
12
f
(
t
i
+
2
,
x
i
+
2
)
−
5
3
f
(
t
i
+
1
,
x
i
+
1
)
−
5
12
f
(
t
i
,
x
i
)
]
{\displaystyle x_{i+2}-3x_{i+1}+2x_{i}=\Delta t\cdot \left[{\frac {13}{12}}f(t_{i+2},x_{i+2})-{\frac {5}{3}}f(t_{i+1},x_{i+1})-{\frac {5}{12}}f(t_{i},x_{i})\right]\!\,}
x
′
(
t
)
=
f
(
t
,
x
)
{\displaystyle x'(t)=f(t,x)\!\,}
Local Order of Accuracy
edit
Note that
x
i
≈
x
(
t
i
)
{\displaystyle x_{i}\approx x(t_{i})\!\,}
Δ
t
{\displaystyle \Delta t\!\,}
t
i
+
1
=
t
i
+
h
{\displaystyle t_{i+1}=t_{i}+h\!\,}
t
i
+
2
=
t
i
+
2
h
{\displaystyle t_{i+2}=t_{i}+2h\!\,}
x
(
t
i
+
2
h
)
−
3
x
(
t
i
+
h
)
+
2
x
(
t
i
)
≈
h
[
13
12
x
′
(
t
i
+
2
h
)
−
5
3
x
′
(
t
i
+
h
)
−
5
12
x
′
(
t
i
)
]
{\displaystyle x(t_{i}+2h)-3x(t_{i}+h)+2x(t_{i})\approx h\left[{\frac {13}{12}}x'(t_{i}+2h)-{\frac {5}{3}}x'(t_{i}+h)-{\frac {5}{12}}x'(t_{i})\right]\!\,}
Expand Left Hand Side Using Taylor Expansion
edit
Expanding about
t
i
{\displaystyle t_{i}\!\,}
Order
x
(
t
i
+
2
h
)
−
3
x
(
t
i
+
h
)
2
x
(
t
i
)
Σ
0
x
(
t
i
)
−
3
x
(
t
i
)
2
x
(
t
i
)
0
1
2
x
′
(
t
i
)
h
−
3
x
′
(
t
i
)
h
0
−
x
′
(
t
i
)
h
2
4
2
!
x
″
(
t
i
)
h
2
−
3
2
!
x
″
(
t
i
)
h
2
0
1
2
x
″
(
t
i
)
h
2
3
8
3
!
x
‴
(
t
i
)
h
3
−
3
3
!
x
‴
(
t
i
)
h
3
0
5
6
x
‴
(
t
i
)
h
3
4
O
(
h
4
)
O
(
h
4
)
0
O
(
h
4
)
{\displaystyle {\begin{array}{|c|c|c|c|c|}{\mbox{Order}}&x(t_{i}+2h)&-3x(t_{i}+h)&2x(t_{i})&\Sigma \\\hline &&&&\\0&x(t_{i})&-3x(t_{i})&2x(t_{i})&0\\&&&&\\1&2x'(t_{i})h&-3x'(t_{i})h&0&-x'(t_{i})h\\&&&&\\2&{\frac {4}{2!}}x''(t_{i})h^{2}&-{\frac {3}{2!}}x''(t_{i})h^{2}&0&{\frac {1}{2}}x''(t_{i})h^{2}\\&&&&\\3&{\frac {8}{3!}}x'''(t_{i})h^{3}&-{\frac {3}{3!}}x'''(t_{i})h^{3}&0&{\frac {5}{6}}x'''(t_{i})h^{3}\\&&&&\\4&{\mathcal {O}}(h^{4})&{\mathcal {O}}(h^{4})&0&{\mathcal {O}}(h^{4})\\&&&&\\\hline \end{array}}}
Expand Right Hand Side Using Taylor Expansion
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}}}
Compare Terms to Determine Order
edit
Taking the difference of the left and right hand side Taylor expansions show that the two step equation is of order two since the terms match up to order 2.
x
i
+
2
−
3
x
i
+
1
+
2
x
i
−
Δ
t
⋅
[
13
12
f
(
t
i
+
2
,
x
i
+
2
)
−
5
3
f
(
t
i
+
1
,
x
i
+
1
)
−
5
12
f
(
t
i
,
x
i
)
]
=
O
(
Δ
t
3
)
{\displaystyle x_{i+2}-3x_{i+1}+2x_{i}-\Delta t\cdot \left[{\frac {13}{12}}f(t_{i+2},x_{i+2})-{\frac {5}{3}}f(t_{i+1},x_{i+1})-{\frac {5}{12}}f(t_{i},x_{i})\right]={\mathcal {O}}(\Delta t^{3})\!\,}
5
6
≠
4
3
{\displaystyle {\frac {5}{6}}\neq {\frac {4}{3}}\!\,}
Our two-step equation is stable if the roots of the equation
λ
2
−
3
λ
+
2
=
0
{\displaystyle \lambda ^{2}-3\lambda +2=0\!\,}
|
λ
j
|
≤
1
{\displaystyle |\lambda _{j}|\leq 1\!\,}
|
λ
j
|
=
1
{\displaystyle |\lambda _{j}|=1\!\,}
λ
2
−
3
λ
+
2
=
(
λ
−
1
)
(
λ
−
2
)
=
0
{\displaystyle \lambda ^{2}-3\lambda +2=(\lambda -1)(\lambda -2)=0\!\,}
A multi-step method is convergent if and only if it is stable and consistent. Our two-step equation is not stable, hence not guaranteed to converge.
![{\displaystyle [0,1]\!\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b26fc5fee30dada6f15cc080115cae582606d7f3)
![{\displaystyle V_{h}=\{v\in V:\left.v\right|_{[x_{i-1},x_{i}]}\in {\mathcal {P}}_{1}([x_{i-1},x_{i}]),i=1,\dots ,m+1,v(0)=v(1)=0\}\!\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a8b81ea4266098e485c27de3c2878513ee2ecac2)
![{\displaystyle \phi _{j}(x)={\begin{cases}{\frac {x-x_{j-1}}{h}}&{\mbox{for }}x\in [x_{j-1},x_{j}]\\{\frac {x_{j+1}-x}{h}}&{\mbox{for }}x\in [x_{j},x_{j+1}]\\0&{\mbox{otherwise}}\end{cases}}\!\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1e560654509e1fde1e76a33b04b42c4d8dc1c90d)
![{\displaystyle \phi _{j}'(x)={\begin{cases}{\frac {1}{h}}&{\mbox{for }}x\in [x_{j-1},x_{j}]\\-{\frac {1}{h}}&{\mbox{for }}x\in [x_{j},x_{j+1}]\\0&{\mbox{otherwise}}\end{cases}}\!\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ce07be9836a28d50878c62470d828ee9128d3e7c)
![{\displaystyle x_{i+2}-3x_{i+1}+2x_{i}=\Delta t\cdot \left[{\frac {13}{12}}f(t_{i+2},x_{i+2})-{\frac {5}{3}}f(t_{i+1},x_{i+1})-{\frac {5}{12}}f(t_{i},x_{i})\right]\!\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d38745bdaf8a8d151ca4d7f9423c5ef07c414c93)
![{\displaystyle x(t_{i}+2h)-3x(t_{i}+h)+2x(t_{i})\approx h\left[{\frac {13}{12}}x'(t_{i}+2h)-{\frac {5}{3}}x'(t_{i}+h)-{\frac {5}{12}}x'(t_{i})\right]\!\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a4cfef726050f99bd552051e47004cecba8fde56)
![{\displaystyle x_{i+2}-3x_{i+1}+2x_{i}-\Delta t\cdot \left[{\frac {13}{12}}f(t_{i+2},x_{i+2})-{\frac {5}{3}}f(t_{i+1},x_{i+1})-{\frac {5}{12}}f(t_{i},x_{i})\right]={\mathcal {O}}(\Delta t^{3})\!\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/689447336d26a301b7d764908c0cb4ee00c85ccf)
