Describe Newton's method for finding a root of a smooth function
f
:
R
→
R
{\displaystyle f:R\rightarrow R\!\,}
Newton's method:
x
k
+
1
=
x
k
−
f
(
x
k
)
f
′
(
x
k
)
{\displaystyle x_{k+1}=x_{k}-{\frac {f(x_{k})}{f'(x_{k})}}\!\,}
Assume that
f
:
R
→
R
{\displaystyle f:R\rightarrow R\!\,}
f
′
(
x
)
>
0
,
f
″
(
x
)
>
0
,
for all
x
∈
R
{\displaystyle f'(x)>0,\quad f''(x)>0,\quad {\mbox{ for all }}x\in R\!\,}
x
∗
{\displaystyle x^{*}\!\,}
x
∗
{\displaystyle x^{*}\!\,}
x
0
∈
R
{\displaystyle x_{0}\in R\!\,}
From the picture, notice that if
x
k
<
x
∗
{\displaystyle x_{k}<x_{*}\!\,}
x
k
+
1
{\displaystyle x_{k+1}\!\,}
x
∗
{\displaystyle x_{*}\!\,}
x
k
>
x
∗
{\displaystyle x_{k}>x_{*}\!\,}
x
∗
{\displaystyle x_{*}\!\,}
x
k
+
1
−
x
∗
⏟
e
k
+
1
=
x
k
−
x
∗
⏟
e
k
−
f
(
x
k
)
f
′
(
x
k
)
(
∗
)
{\displaystyle \underbrace {x_{k+1}-x_{*}} _{e_{k+1}}=\underbrace {x_{k}-x_{*}} _{e_{k}}-{\frac {f(x_{k})}{f'(x_{k})}}\qquad (*)\!\,}
f
(
x
k
)
{\displaystyle f(x_{k})\!\,}
f
(
x
∗
)
{\displaystyle f(x_{*})\!\,}
f
(
x
k
)
=
f
(
x
∗
)
⏟
0
+
f
′
(
ξ
)
(
x
k
−
x
∗
)
⏟
e
k
{\displaystyle f(x_{k})=\underbrace {f(x_{*})} _{0}+f'(\xi )\underbrace {(x_{k}-x_{*})} _{e_{k}}\!\,}
ξ
∈
[
x
∗
,
x
k
]
{\displaystyle \xi \in [x_{*},x_{k}]\!\,}
e
k
+
1
=
(
1
−
f
′
(
ξ
)
f
′
(
x
k
)
⏟
M
)
e
k
{\displaystyle e_{k+1}=(1-\underbrace {\frac {f'(\xi )}{f'(x_{k})}} _{M})e_{k}\!\,}
f
′
(
x
)
>
0
{\displaystyle f'(x)>0\!\,}
M
{\displaystyle M\!\,}
k
{\displaystyle k\!\,}
The goal of this problem is to solve the boundary value problem
−
u
″
=
f
on
(
0
,
1
)
,
u
(
0
)
=
0
,
u
(
1
)
=
0
{\displaystyle -u''=f{\mbox{ on }}(0,1),\quad u(0)=0,u(1)=0\!\,}
For
N
∈
N
{\displaystyle N\in \mathbb {N} \!\,}
x
i
=
i
/
N
,
i
=
0
,
…
,
N
{\displaystyle x_{i}=i/N,i=0,\ldots ,N\!\,}
N
−
1
{\displaystyle N-1\!\,}
V
N
{\displaystyle V_{N}\!\,}
H
0
1
{\displaystyle H_{0}^{1}\!\,}
x
i
{\displaystyle x_{i}\!\,}
ϕ
1
,
…
,
ϕ
N
−
1
{\displaystyle \phi _{1},\ldots ,\phi _{N-1}\!\,}
V
N
{\displaystyle V_{N}\!\,}
u
i
{\displaystyle u_{i}\!\,}
u
N
=
∑
i
=
1
N
−
1
u
i
ϕ
i
{\displaystyle u_{N}=\sum _{i=1}^{N-1}u_{i}\phi _{i}\!\,}
Define Suitable Subspace
edit
V
N
=
{
v
∈
H
0
1
[
0
,
1
]
:
v
piecewise linear
}
{\displaystyle V_{N}=\{v\in H_{0}^{1}[0,1]:v{\mbox{ piecewise linear}}\}\!\,}
{
ϕ
i
}
i
=
1
N
−
1
{\displaystyle \{\phi _{i}\}_{i=1}^{N-1}\!\,}
ϕ
i
(
x
)
=
{
x
−
x
i
−
1
h
for
x
∈
[
x
i
−
1
,
x
i
]
x
i
+
1
−
x
h
for
x
∈
[
x
i
,
x
i
+
1
]
0
otherwise
{\displaystyle \phi _{i}(x)={\begin{cases}{\frac {x-x_{i-1}}{h}}&{\mbox{ for }}x\in [x_{i-1},x_{i}]\\{\frac {x_{i+1}-x}{h}}&{\mbox{ for }}x\in [x_{i},x_{i+1}]\\0&{\mbox{ otherwise}}\end{cases}}\!\,}
How to Determine Coefficients
edit
The discrete weak variational form is given as such:
u
N
∈
V
N
{\displaystyle u_{N}\in V_{N}\!\,}
v
∈
V
N
{\displaystyle v\in V_{N}\!\,}
∫
0
1
u
N
′
v
N
′
⏟
a
(
u
N
,
v
N
)
=
∫
0
1
f
v
N
⏟
F
(
v
N
)
{\displaystyle \underbrace {\int _{0}^{1}u_{N}'v_{N}'} _{a(u_{N},v_{N})}=\underbrace {\int _{0}^{1}fv_{N}} _{F(v_{N})}\!\,}
{
ϕ
i
}
i
=
1
N
−
1
{\displaystyle \{\phi _{i}\}_{i=1}^{N-1}\!\,}
j
=
1
,
2
,
…
,
N
−
1
{\displaystyle j=1,2,\ldots ,N-1\!\,}
∑
i
=
1
N
−
1
u
i
∫
0
1
ϕ
i
ϕ
j
=
∫
0
1
f
ϕ
j
{\displaystyle \sum _{i=1}^{N-1}u_{i}\int _{0}^{1}\phi _{i}\phi _{j}=\int _{0}^{1}f\phi _{j}\!\,}
Existence of Unique Solution
edit
The existence of a unique solution follows from Lax-Milgram.
bilinear form continuous (bounded) e.g.
a
(
u
N
,
v
N
)
≤
‖
u
N
‖
1
‖
v
N
‖
1
{\displaystyle a(u_{N},v_{N})\leq \|u_{N}\|_{1}\|v_{N}\|_{1}\!\,}
a
(
u
,
v
)
=
∫
u
′
v
′
≤
|
u
|
1
|
v
|
1
Cauchy Schwartz in L2
≤
‖
u
‖
1
‖
v
‖
1
dominance of spaces
{\displaystyle {\begin{aligned}a(u,v)&=\int u'v'\\&\leq |u|_{1}|v|_{1}{\mbox{ Cauchy Schwartz in L2 }}\\&\leq \|u\|_{1}\|v\|_{1}{\mbox{ dominance of spaces }}\end{aligned}}\!\,}
bilinear form coercive e.g.
a
(
u
N
,
u
N
)
≥
C
‖
u
N
‖
1
2
{\displaystyle a(u_{N},u_{N})\geq C\|u_{N}\|_{1}^{2}\!\,}
a
(
v
,
v
)
=
∫
v
′
2
=
|
v
|
1
2
≥
C
‖
v
‖
1
2
Poincare inequality
{\displaystyle {\begin{aligned}a(v,v)&=\int v'^{2}\\&=|v|_{1}^{2}\\&\geq C\|v\|_{1}^{2}{\mbox{ Poincare inequality}}\end{aligned}}\!\,}
‖
v
‖
0
≤
‖
v
‖
1
≤
C
|
v
|
1
{\displaystyle \|v\|_{0}\leq \|v\|_{1}\leq C|v|_{1}\!\,}
F
(
v
N
)
≤
C
‖
v
N
‖
1
{\displaystyle F(v_{N})\leq C\|v_{N}\|_{1}\!\,}
∫
f
v
≤
‖
f
‖
0
‖
v
‖
0
≤
‖
f
‖
1
‖
v
‖
1
{\displaystyle {\begin{aligned}\int fv&\leq \|f\|_{0}\|v\|_{0}\\&\leq \|f\|_{1}\|v\|_{1}\end{aligned}}\!\,}
Show that
a
(
u
,
v
)
=
∫
0
1
u
′
v
′
d
x
{\displaystyle a(u,v)=\int _{0}^{1}u'v'dx\!\,}
H
0
1
{\displaystyle H_{0}^{1}\!\,}
H
0
1
{\displaystyle H_{0}^{1}\!\,}
a
(
u
,
v
)
=
a
(
v
,
u
)
{\displaystyle a(u,v)=a(v,u)\!\,}
a
(
α
u
,
v
)
=
∫
α
u
′
v
′
=
α
∫
u
′
v
′
=
α
a
(
u
,
v
)
{\displaystyle a(\alpha u,v)=\int \alpha u'v'=\alpha \int u'v'=\alpha a(u,v)\!\,}
a
(
u
+
w
,
v
)
=
∫
(
u
′
+
w
′
)
v
′
=
∫
u
′
v
′
+
∫
w
′
v
′
=
a
(
u
,
v
)
+
a
(
w
,
v
)
{\displaystyle a(u+w,v)=\int (u'+w')v'=\int u'v'+\int w'v'=a(u,v)+a(w,v)\!\,}
a
(
u
,
u
)
=
∫
u
′
2
≠
0
if
u
≠
0
{\displaystyle a(u,u)=\int u'^{2}\neq 0{\mbox{ if }}u\neq 0\!\,}
ϕ
1
=
{
2
x
for
x
∈
[
0
,
1
2
]
2
−
2
x
for
x
∈
[
1
2
,
1
]
{\displaystyle \phi _{1}={\begin{cases}2x&{\mbox{ for }}x\in [0,{\frac {1}{2}}]\\2-2x&{\mbox{ for }}x\in [{\frac {1}{2}},1]\end{cases}}\!\,}
ϕ
2
=
{
8
x
for
x
∈
[
0
,
1
4
]
−
8
(
x
−
1
2
)
for
x
∈
[
1
4
,
1
2
]
0
otherwise
{\displaystyle \phi _{2}={\begin{cases}8x&{\mbox{ for }}x\in [0,{\frac {1}{4}}]\\-8(x-{\frac {1}{2}})&{\mbox{ for }}x\in [{\frac {1}{4}},{\frac {1}{2}}]\\0&{\mbox{ otherwise }}\end{cases}}\!\,}
ϕ
3
=
{
8
(
x
−
1
2
)
for
x
∈
[
1
2
,
3
4
]
−
8
(
x
−
1
)
for
x
∈
[
1
4
,
1
]
0
otherwise
{\displaystyle \phi _{3}={\begin{cases}8(x-{\frac {1}{2}})&{\mbox{ for }}x\in [{\frac {1}{2}},{\frac {3}{4}}]\\-8(x-1)&{\mbox{ for }}x\in [{\frac {1}{4}},1]\\0&{\mbox{ otherwise }}\end{cases}}\!\,}
Define a new hat function on each new pair of adjoining subintervals. The hat functions should have all have the same height as the previous basis's hat functions.
What is the structure of the linear system in (a) for this special basis?
For our system in (a), this system yields a diagonal matrix.
For solving the equation
y
′
=
f
(
x
,
y
)
{\displaystyle y'=f(x,y)\!\,}
y
n
+
1
=
y
n
+
h
2
(
y
n
′
+
y
n
+
1
′
)
+
h
2
12
(
y
n
″
−
y
n
+
1
″
)
{\displaystyle y_{n+1}=y_{n}+{\frac {h}{2}}(y_{n}'+y'_{n+1})+{\frac {h^{2}}{12}}(y''_{n}-y''_{n+1})\!\,}
y
n
′
=
f
(
x
n
,
y
n
)
{\displaystyle y_{n}'=f(x_{n},y_{n})\!\,}
y
n
″
=
f
x
(
x
n
,
y
n
)
+
f
(
x
n
,
y
n
)
f
y
(
x
n
,
y
n
)
{\displaystyle y_{n}''=f_{x}(x_{n},y_{n})+f(x_{n},y_{n})f_{y}(x_{n},y_{n})\!\,}
Show that this scheme is fourth-order accurate.
Order
y
(
t
+
h
)
−
y
(
t
)
−
h
2
y
′
(
t
)
−
h
2
y
′
(
t
+
h
)
−
h
2
12
y
″
(
t
)
h
2
12
y
″
(
t
+
h
)
Σ
0
y
(
t
)
−
y
(
t
)
0
0
0
0
0
1
y
′
(
t
)
h
0
−
h
2
y
′
(
t
)
−
h
2
y
′
(
t
)
0
0
0
2
y
″
(
t
)
h
2
2
0
0
−
h
2
y
″
(
t
)
h
−
h
2
12
y
″
(
t
)
h
2
12
y
″
(
t
)
0
3
y
‴
(
t
)
h
3
6
0
0
−
h
2
y
‴
(
t
)
2
h
2
0
h
2
12
y
‴
(
t
)
h
0
4
y
⁗
(
t
)
h
4
24
0
0
−
h
2
y
⁗
(
t
)
h
3
6
0
h
2
12
y
⁗
(
t
)
h
2
2
0
5
O
(
h
5
)
0
0
O
(
h
5
)
0
O
(
h
5
)
O
(
h
5
)
{\displaystyle {\begin{array}{|c|c|c|c|c|c|c|c|}{\mbox{Order}}&y(t+h)&-y(t)&-{\frac {h}{2}}y'(t)&-{\frac {h}{2}}y'(t+h)&-{\frac {h^{2}}{12}}y''(t)&{\frac {h^{2}}{12}}y''(t+h)&\Sigma \\\hline &&&&&&&\\0&y(t)&-y(t)&0&0&0&0&0\\1&y'(t)h&0&-{\frac {h}{2}}y'(t)&-{\frac {h}{2}}y'(t)&0&0&0\\2&{\frac {y''(t)h^{2}}{2}}&0&0&-{\frac {h}{2}}y''(t)h&-{\frac {h^{2}}{12}}y''(t)&{\frac {h^{2}}{12}}y''(t)&0\\3&{\frac {y'''(t)h^{3}}{6}}&0&0&-{\frac {h}{2}}{\frac {y'''(t)}{2}}h^{2}&0&{\frac {h^{2}}{12}}y'''(t)h&0\\4&y''''(t){\frac {h^{4}}{24}}&0&0&-{\frac {h}{2}}y''''(t){\frac {h^{3}}{6}}&0&{\frac {h^{2}}{12}}y''''(t){\frac {h^{2}}{2}}&0\\5&O(h^{5})&0&0&O(h^{5})&0&O(h^{5})&O(h^{5})\\\hline \end{array}}}
For stability analysis, one takes
f
(
x
,
y
)
=
λ
y
{\displaystyle f(x,y)=\lambda y\!\,}
λ
¯
=
h
λ
{\displaystyle {\overline {\lambda }}=h\lambda \!\,}
y
n
″
=
d
d
x
λ
y
+
λ
y
d
d
y
λ
y
=
λ
2
y
{\displaystyle y_{n}''={\frac {d}{dx}}\lambda y+\lambda y{\frac {d}{dy}}\lambda y=\lambda ^{2}y\!\,}
y
n
+
1
=
y
n
+
h
2
λ
y
n
+
h
2
λ
y
n
+
1
+
h
2
12
[
λ
2
y
n
−
λ
2
y
n
+
1
]
{\displaystyle y_{n+1}=y_{n}+{\frac {h}{2}}\lambda y_{n}+{\frac {h}{2}}\lambda y_{n+1}+{\frac {h^{2}}{12}}[\lambda ^{2}y_{n}-\lambda ^{2}y_{n+1}]\!\,}
z
=
h
λ
{\displaystyle z=h\lambda \!\,}
y
n
+
1
=
(
1
+
z
2
+
z
2
12
1
−
z
2
+
z
2
12
)
⏟
M
y
n
{\displaystyle y_{n+1}=\underbrace {\left({\frac {1+{\frac {z}{2}}+{\frac {z^{2}}{12}}}{1-{\frac {z}{2}}+{\frac {z^{2}}{12}}}}\right)} _{M}y_{n}\!\,}
z
{\displaystyle z\!\,}
M
<
1
{\displaystyle M<1\!\,}
![{\displaystyle \xi \in [x_{*},x_{k}]\!\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c9631a072ad0f9b52174f728c2aa53c088f3d00b)
![{\displaystyle V_{N}=\{v\in H_{0}^{1}[0,1]:v{\mbox{ piecewise linear}}\}\!\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/acc41b308034867ced52a9a72ebe3e685e7772e9)
![{\displaystyle \phi _{i}(x)={\begin{cases}{\frac {x-x_{i-1}}{h}}&{\mbox{ for }}x\in [x_{i-1},x_{i}]\\{\frac {x_{i+1}-x}{h}}&{\mbox{ for }}x\in [x_{i},x_{i+1}]\\0&{\mbox{ otherwise}}\end{cases}}\!\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7ed397828b41f11801339e31ab93d1d298c52dbb)
![{\displaystyle \phi _{1}={\begin{cases}2x&{\mbox{ for }}x\in [0,{\frac {1}{2}}]\\2-2x&{\mbox{ for }}x\in [{\frac {1}{2}},1]\end{cases}}\!\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3d41a144fe028f0f52d6ba3e170049a0e2f2a668)
![{\displaystyle \phi _{2}={\begin{cases}8x&{\mbox{ for }}x\in [0,{\frac {1}{4}}]\\-8(x-{\frac {1}{2}})&{\mbox{ for }}x\in [{\frac {1}{4}},{\frac {1}{2}}]\\0&{\mbox{ otherwise }}\end{cases}}\!\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/932d28ec6e783384df93f6f0565ac6aa75be7adc)
![{\displaystyle \phi _{3}={\begin{cases}8(x-{\frac {1}{2}})&{\mbox{ for }}x\in [{\frac {1}{2}},{\frac {3}{4}}]\\-8(x-1)&{\mbox{ for }}x\in [{\frac {1}{4}},1]\\0&{\mbox{ otherwise }}\end{cases}}\!\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eb1ae880f592399a249e693dd1632d46f7a0ed8e)
![{\displaystyle y_{n+1}=y_{n}+{\frac {h}{2}}\lambda y_{n}+{\frac {h}{2}}\lambda y_{n+1}+{\frac {h^{2}}{12}}[\lambda ^{2}y_{n}-\lambda ^{2}y_{n+1}]\!\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c9aef13f63558227a5793e97cfae9d833ff935c6)
