Problem 5a Edit
State Newton's method for the approximate solution of
f
(
x
)
=
0
{\displaystyle f(x)=0\!\,}
f
(
x
)
{\displaystyle f(x)\!\,}
x
{\displaystyle x\!\,}
Solution 5a Edit
x
k
+
1
=
x
k
−
f
(
x
k
)
f
′
(
x
k
)
{\displaystyle x_{k+1}=x_{k}-{\frac {f(x_{k})}{f'(x_{k})}}\!\,}
Problem 5b Edit
State and prove a convergence result for the method.
Solution 5b Edit
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}}\!\,}
Problem 5c Edit
What is the typical order of convergence? Are there situations in which the order of convergence is higher? Explain your answers to these questions.
Solution 5c Edit
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\!\,}
Problem 6 Edit
{
−
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)\!\,}
Problem 6a Edit
Derive a variational formulation for (1).
Solution 6a Edit
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)}\!\,}
Problem 6b Edit
What do we mean by Finite Element Approximation
u
h
{\displaystyle u_{h}\!\,}
u
{\displaystyle u\!\,}
Solution 6b Edit
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)\!\,}
Problem 6c Edit
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}}\!\,}
Solution 6c Edit
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}).}
Problem 6d Edit
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}\!\,}
Solution 6d Edit
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}}\!\,}
Problem 7 Edit
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}\!\,}
Problem 7a Edit
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\!\,}
Solution 7a Edit
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}}\!\,}
Problem 7b Edit
Solution 7b Edit
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)
