State Newton's method for the approximate solution of
f
(
x
)
=
0
{\displaystyle f(x)=0\!\,}
f
(
x
)
{\displaystyle f(x)\!\,}
x
{\displaystyle x\!\,}
x
k
+
1
=
x
k
−
f
(
x
k
)
f
′
(
x
k
)
{\displaystyle x_{k+1}=x_{k}-{\frac {f(x_{k})}{f'(x_{k})}}\!\,}
State and prove a convergence result for the method.
x
k
+
1
=
x
k
−
f
′
(
x
k
)
−
1
f
(
x
k
)
x
k
+
1
−
x
∗
⏟
e
k
+
1
=
x
k
−
x
∗
⏟
e
k
−
f
′
(
x
k
)
−
1
f
(
x
k
)
=
f
′
(
x
k
)
−
1
[
f
′
(
x
k
)
e
k
−
(
f
(
x
k
)
−
f
(
x
∗
)
⏟
0
)
)
=
f
′
(
x
k
)
−
1
[
f
′
(
x
k
)
e
k
−
e
k
∫
0
1
f
′
(
s
x
k
+
(
1
−
s
)
x
∗
)
d
s
]
=
f
′
(
x
k
)
−
1
[
f
′
(
x
k
)
e
k
−
f
′
(
x
∗
)
e
k
−
e
k
∫
0
1
(
f
′
(
s
x
k
+
(
1
−
s
)
x
∗
)
−
f
′
(
x
∗
)
)
d
s
]
‖
e
k
+
1
‖
≤
‖
f
′
(
x
k
)
−
1
‖
[
L
‖
e
k
‖
2
+
L
2
‖
e
k
‖
2
]
where L is Lipschitz constant of
f
′
=
‖
f
′
(
x
k
)
−
1
‖
3
2
L
‖
e
k
‖
2
{\displaystyle {\begin{aligned}x_{k+1}&=x_{k}-f'(x_{k})^{-1}f(x_{k})\\\underbrace {x_{k+1}-x_{*}} _{e_{k+1}}&=\underbrace {x_{k}-x_{*}} _{e_{k}}-f'(x_{k})^{-1}f(x_{k})\\&=f'(x_{k})^{-1}[f'(x_{k})e_{k}-(f(x_{k})-\underbrace {f(x_{*})} _{0}))\\&=f'(x_{k})^{-1}\left[f'(x_{k})e_{k}-e_{k}\int _{0}^{1}f'(sx_{k}+(1-s)x_{*})ds\right]\\&=f'(x_{k})^{-1}\left[f'(x_{k})e_{k}-f'(x_{*})e_{k}-e_{k}\int _{0}^{1}(f'(sx_{k}+(1-s)x_{*})-f'(x_{*}))ds\right]\\\|e_{k+1}\|&\leq \|f'(x_{k})^{-1}\|\left[L\|e_{k}\|^{2}+{\frac {L}{2}}\|e_{k}\|^{2}\right]{\mbox{ where L is Lipschitz constant of }}f'\\&=\|f'(x_{k})^{-1}\|{\frac {3}{2}}L\|e_{k}\|^{2}\end{aligned}}\!\,}
What is the typical order of convergence? Are there situations in which the order of convergence is higher? Explain your answers to these questions.
The typical order of local convergence is quadratic.
x
k
+
1
=
x
k
−
f
(
x
k
)
f
′
(
x
k
)
⏟
g
(
x
k
)
{\displaystyle x_{k+1}=\underbrace {x_{k}-{\frac {f(x_{k})}{f'(x_{k})}}} _{g(x_{k})}\!\,}
g
′
(
x
k
)
=
1
−
f
′
(
x
k
)
2
−
f
′
(
x
k
)
f
(
x
k
)
f
′
(
x
k
)
2
{\displaystyle g'(x_{k})=1-{\frac {f'(x_{k})^{2}-f'(x_{k})f(x_{k})}{f'(x_{k})^{2}}}\!\,}
g
′
(
x
∗
)
=
0
{\displaystyle g'(x_{*})=0\!\,}
g
(
x
k
)
{\displaystyle g(x_{k})\!\,}
x
∗
{\displaystyle x_{*}\!\,}
g
(
x
k
)
⏟
x
k
+
1
=
g
(
x
∗
)
⏟
x
∗
+
g
′
(
x
∗
)
⏟
0
e
k
+
g
″
(
x
∗
)
2
e
k
2
+
g
‴
(
ξ
)
6
e
k
3
{\displaystyle \underbrace {g(x_{k})} _{x_{k+1}}=\underbrace {g(x_{*})} _{x_{*}}+\underbrace {g'(x_{*})} _{0}e_{k}+{\frac {g''(x_{*})}{2}}e_{k}^{2}+{\frac {g'''(\xi )}{6}}e_{k}^{3}\!\,}
g
″
(
x
∗
)
=
0
{\displaystyle g''(x_{*})=0\!\,}
{
−
u
″
(
x
)
+
u
(
x
)
=
f
(
x
)
,
0
≤
x
≤
1
u
′
(
0
)
=
2
,
u
(
1
)
=
0
(
1
)
{\displaystyle {\begin{cases}-u''(x)+u(x)=f(x),0\leq x\leq 1\\u'(0)=2,u(1)=0\end{cases}}\qquad (1)\!\,}
Derive a variational formulation for (1).
Find
u
∈
H
{\displaystyle u\in H\!\,}
v
∈
H
=
{
v
∈
H
1
[
0
,
1
]
:
v
(
1
)
=
0
}
{\displaystyle v\in H=\{v\in H^{1}[0,1]:v(1)=0\}\!\,}
∫
0
1
u
′
v
′
d
x
+
∫
0
1
u
v
⏟
a
(
u
,
v
)
=
∫
0
1
f
v
−
2
v
(
0
)
⏟
f
(
v
)
{\displaystyle \underbrace {\int _{0}^{1}u'v'dx+\int _{0}^{1}uv} _{a(u,v)}=\underbrace {\int _{0}^{1}fv-2v(0)} _{f(v)}\!\,}
What do we mean by Finite Element Approximation
u
h
{\displaystyle u_{h}\!\,}
u
{\displaystyle u\!\,}
Let
P
=
{
x
i
}
i
=
0
N
{\displaystyle P=\{x_{i}\}_{i=0}^{N}\!\,}
[
0
,
1
]
{\displaystyle [0,1]\!\,}
V
h
{\displaystyle V_{h}\!\,}
{
ϕ
i
}
i
=
0
N
{\displaystyle \{\phi _{i}\}_{i=0}^{N}\!\,}
u
h
=
∑
i
=
0
N
u
h
i
ϕ
i
{\displaystyle u_{h}=\sum _{i=0}^{N}u_{hi}\phi _{i}\!\,}
u
h
i
{\displaystyle u_{hi}\!\,}
j
=
0
,
1
,
…
,
N
{\displaystyle j=0,1,\ldots ,N\!\,}
∑
i
=
0
N
u
h
i
∫
0
1
ϕ
i
′
ϕ
j
′
d
x
+
∑
i
=
0
N
u
h
i
∫
0
1
ϕ
i
ϕ
j
d
x
=
∫
0
1
f
ϕ
j
−
2
ϕ
j
(
0
)
{\displaystyle \sum _{i=0}^{N}u_{hi}\int _{0}^{1}\phi _{i}'\phi _{j}'dx+\sum _{i=0}^{N}u_{hi}\int _{0}^{1}\phi _{i}\phi _{j}dx=\int _{0}^{1}f\phi _{j}-2\phi _{j}(0)\!\,}
State and prove an estimate for
‖
u
−
u
h
‖
1
≡
(
∫
0
1
|
u
(
x
)
−
u
h
(
x
)
|
2
d
x
+
∫
0
1
|
u
′
(
x
)
−
u
h
′
(
x
)
|
2
d
x
)
1
2
{\displaystyle \|u-u_{h}\|_{1}\equiv \left(\int _{0}^{1}|u(x)-u_{h}(x)|^{2}dx+\int _{0}^{1}|u'(x)-u_{h}'(x)|^{2}dx\right)^{\frac {1}{2}}\!\,}
Cea's Lemma:
‖
u
−
u
h
‖
1
≤
inf
v
∈
V
h
C
‖
u
−
v
‖
1
{\displaystyle \|u-u_{h}\|_{1}\leq \inf _{v\in V_{h}}C\|u-v\|_{1}\!\,}
v
I
{\displaystyle v_{I}\!\,}
u
{\displaystyle u\!\,}
‖
u
−
u
h
‖
≤
C
‖
u
″
‖
∞
h
{\displaystyle \|u-u_{h}\|\leq C\|u''\|_{\infty }h\!\,}
Alternative Solution 6c
edit
Let
{
x
k
}
0
n
{\displaystyle \{x_{k}\}_{0}^{n}}
[
0
,
1
]
{\displaystyle [0,1]}
h
{\displaystyle h}
∫
x
k
x
k
+
1
|
u
(
x
)
−
u
h
(
x
)
|
2
d
x
{\displaystyle \int _{x_{k}}^{x_{k+1}}|u(x)-u_{h}(x)|^{2}dx}
For some
ξ
k
∈
[
x
k
,
x
k
+
1
]
{\displaystyle \xi _{k}\in [x_{k},x_{k+1}]}
u
(
x
)
−
u
h
(
x
)
=
u
′
(
ξ
k
)
∗
h
{\displaystyle u(x)-u_{h}(x)=u'(\xi _{k})*h}
u
h
{\displaystyle u_{h}}
∫
x
k
x
k
+
1
|
u
(
x
)
−
u
h
(
x
)
|
2
d
x
=
∫
x
k
x
k
+
1
h
2
u
′
(
ξ
k
)
2
d
x
=
h
3
u
′
(
ξ
k
)
2
≤
h
3
|
|
u
′
|
|
∞
{\displaystyle \int _{x_{k}}^{x_{k+1}}|u(x)-u_{h}(x)|^{2}dx=\int _{x_{k}}^{x_{k+1}}h^{2}u'(\xi _{k})^{2}dx=h^{3}u'(\xi _{k})^{2}\leq h^{3}||u'||_{\infty }}
Similarly, we can bound the
L
2
(
x
k
,
x
k
+
h
)
{\displaystyle L_{2}(x_{k},x_{k}+h)}
h
3
|
|
u
″
|
|
∞
{\displaystyle h^{3}||u''||_{\infty }}
n
=
1
/
h
{\displaystyle n=1/h}
|
|
u
−
u
h
‖
|
2
≤
2
n
h
3
max
(
|
|
u
′
|
|
∞
2
,
|
|
u
″
|
|
∞
2
)
=
2
h
2
max
(
|
|
u
′
|
|
∞
2
,
|
|
u
″
|
|
∞
2
)
.
{\displaystyle \ ||u-u_{h}\||^{2}\leq 2nh^{3}\max(||u'||_{\infty }^{2},||u''||_{\infty }^{2})=2h^{2}\max(||u'||_{\infty }^{2},||u''||_{\infty }^{2}).}
Prove the formula
‖
u
−
u
h
‖
1
2
=
‖
u
‖
1
2
−
‖
u
h
‖
1
2
{\displaystyle \|u-u_{h}\|_{1}^{2}=\|u\|_{1}^{2}-\|u_{h}\|_{1}^{2}\!\,}
a
(
u
−
u
h
,
u
−
u
h
)
⏟
‖
u
−
u
h
‖
1
2
+
2
a
(
u
−
u
h
,
u
h
)
⏟
0
=
a
(
u
,
u
)
−
2
a
(
u
,
u
h
)
+
a
(
u
h
,
u
h
)
+
2
a
(
u
,
u
h
)
−
2
a
(
u
h
,
u
h
)
=
a
(
u
,
u
)
−
a
(
u
h
,
u
h
)
=
‖
u
‖
1
2
−
‖
u
h
‖
1
2
{\displaystyle {\begin{aligned}\underbrace {a(u-u_{h},u-u_{h})} _{\|u-u_{h}\|_{1}^{2}}+2\underbrace {a(u-u_{h},u_{h})} _{0}&=a(u,u)-2a(u,u_{h})+a(u_{h},u_{h})+2a(u,u_{h})-2a(u_{h},u_{h})\\&=a(u,u)-a(u_{h},u_{h})\\&=\|u\|_{1}^{2}-\|u_{h}\|_{1}^{2}\end{aligned}}\!\,}
Consider the initial value problem
y
′
=
f
(
t
,
y
)
,
y
(
t
0
)
=
y
0
{\displaystyle y'=f(t,y),\quad y(t_{0})=y_{0}\!\,}
f
{\displaystyle f\!\,}
|
f
(
t
,
y
)
−
f
(
t
,
z
)
|
≤
L
|
y
−
z
|
{\displaystyle |f(t,y)-f(t,z)|\leq L|y-z|\!\,}
t
,
y
,
z
{\displaystyle t,y,z\!\,}
y
n
+
1
=
y
n
−
1
+
2
h
f
(
t
n
,
y
n
)
{\displaystyle y_{n+1}=y_{n-1}+2hf(t_{n},y_{n})\!\,}
h
{\displaystyle h\!\,}
y
n
≈
y
(
t
n
)
{\displaystyle y_{n}\approx y(t_{n})\!\,}
t
n
=
t
0
+
n
h
{\displaystyle t_{n}=t_{0}+nh\!\,}
y
0
{\displaystyle y_{0}\!\,}
y
1
{\displaystyle y_{1}\!\,}
Suppose the problem is posed on a finite interval
t
0
≤
t
≤
b
{\displaystyle t_{0}\leq t\leq b\!\,}
h
=
(
b
−
t
0
)
M
{\displaystyle h={\frac {(b-t_{0})}{M}}\!\,}
y
0
^
{\displaystyle {\hat {y_{0}}}\!\,}
y
1
^
{\displaystyle {\hat {y_{1}}}\!\,}
|
y
0
−
y
0
^
|
≤
ϵ
,
|
y
1
−
y
1
^
|
≤
ϵ
{\displaystyle |y_{0}-{\hat {y_{0}}}|\leq \epsilon ,\quad |y_{1}-{\hat {y_{1}}}|\leq \epsilon \!\,}
C
{\displaystyle C\!\,}
h
{\displaystyle h\!\,}
|
y
n
−
y
n
^
|
≤
C
ϵ
{\displaystyle |y_{n}-{\hat {y_{n}}}|\leq C\epsilon \!\,}
0
≤
n
≤
M
{\displaystyle 0\leq n\leq M\!\,}
y
n
+
1
=
y
n
−
1
+
2
h
f
(
t
n
,
y
n
)
y
^
n
+
1
=
y
^
n
−
1
+
2
h
f
(
t
n
,
y
^
n
)
{\displaystyle {\begin{aligned}y_{n+1}&=y_{n-1}+2hf(t_{n},y_{n})\\{\hat {y}}_{n+1}&={\hat {y}}_{n-1}+2hf(t_{n},{\hat {y}}_{n})\end{aligned}}}
e
n
≡
y
n
−
y
^
n
{\displaystyle e_{n}\equiv y_{n}-{\hat {y}}_{n}\!\,}
e
n
+
1
≤
e
n
−
1
+
2
h
L
e
n
≤
(
1
+
2
h
L
)
max
{
e
n
,
e
n
−
1
}
{\displaystyle {\begin{aligned}e_{n+1}&\leq e_{n-1}+2hLe_{n}\\&\leq (1+2hL)\max\{e_{n},e_{n-1}\}\end{aligned}}\!\,}
e
n
≤
(
1
+
2
h
L
)
n
−
1
ϵ
≤
(
1
+
2
h
L
)
n
ϵ
≤
e
2
L
h
n
ϵ
≤
e
2
L
(
t
n
−
t
0
)
ϵ
{\displaystyle {\begin{aligned}e_{n}&\leq (1+2hL)^{n-1}\epsilon \\&\leq (1+2hL)^{n}\epsilon \\&\leq e^{2Lhn}\epsilon \\&\leq e^{2L(t_{n}-t_{0})}\epsilon \end{aligned}}\!\,}
Substituting into the midpoint rule we have,
y
n
+
1
=
y
n
−
1
+
2
h
λ
y
n
{\displaystyle y_{n+1}=y_{n-1}+2h\lambda y_{n}\!\,}
y
n
+
1
−
2
h
λ
y
n
−
y
n
−
1
=
0
{\displaystyle y_{n+1}-2h\lambda y_{n}-y_{n-1}=0\!\,}
y
n
=
C
1
z
1
n
+
C
2
z
2
n
{\displaystyle y_{n}=C_{1}z_{1}^{n}+C_{2}z_{2}^{n}\!\,}
z
1
,
z
2
{\displaystyle z_{1},z_{2}\!\,}
z
2
−
2
h
λ
z
−
1
{\displaystyle z^{2}-2h\lambda z-1\!\,}
z
=
h
λ
(
1
±
1
+
4
4
h
2
λ
2
)
{\displaystyle z=h\lambda \left(1\pm {\sqrt {1+{\frac {4}{4h^{2}\lambda ^{2}}}}}\right)\!\,}
λ
{\displaystyle \lambda \!\,}
y
n
→
∞
{\displaystyle y_{n}\rightarrow \infty \!\,}
n
→
∞
{\displaystyle n\rightarrow \infty \!\,}
y
(
t
)
=
e
λ
t
{\displaystyle y(t)=e^{\lambda t}\!\,}
![{\displaystyle {\begin{aligned}x_{k+1}&=x_{k}-f'(x_{k})^{-1}f(x_{k})\\\underbrace {x_{k+1}-x_{*}} _{e_{k+1}}&=\underbrace {x_{k}-x_{*}} _{e_{k}}-f'(x_{k})^{-1}f(x_{k})\\&=f'(x_{k})^{-1}[f'(x_{k})e_{k}-(f(x_{k})-\underbrace {f(x_{*})} _{0}))\\&=f'(x_{k})^{-1}\left[f'(x_{k})e_{k}-e_{k}\int _{0}^{1}f'(sx_{k}+(1-s)x_{*})ds\right]\\&=f'(x_{k})^{-1}\left[f'(x_{k})e_{k}-f'(x_{*})e_{k}-e_{k}\int _{0}^{1}(f'(sx_{k}+(1-s)x_{*})-f'(x_{*}))ds\right]\\\|e_{k+1}\|&\leq \|f'(x_{k})^{-1}\|\left[L\|e_{k}\|^{2}+{\frac {L}{2}}\|e_{k}\|^{2}\right]{\mbox{ where L is Lipschitz constant of }}f'\\&=\|f'(x_{k})^{-1}\|{\frac {3}{2}}L\|e_{k}\|^{2}\end{aligned}}\!\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5f6f55b65fc3eadd56e58a8d680e56788e7c6137)
![{\displaystyle v\in H=\{v\in H^{1}[0,1]:v(1)=0\}\!\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/944b769d3268a571131ca656ea7fcf2dc14a0085)
![{\displaystyle [0,1]\!\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b26fc5fee30dada6f15cc080115cae582606d7f3)
![{\displaystyle [0,1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/738f7d23bb2d9642bab520020873cccbef49768d)
![{\displaystyle \xi _{k}\in [x_{k},x_{k+1}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d1ba08c76abca76c84c6a51368615f33f4430cc2)
