Show that the two-step method
y
n
+
1
=
2
y
n
−
1
−
y
n
+
h
[
5
2
f
(
x
n
,
y
n
)
+
1
2
f
(
x
n
−
1
,
y
n
−
1
)
]
(
1
)
{\displaystyle y_{n+1}=2y_{n-1}-y_{n}+h[{\frac {5}{2}}f(x_{n},y_{n})+{\frac {1}{2}}f(x_{n-1},y_{n-1})]\qquad (1)\!\,}
is of order 2 but does not satisfy the root condition.
Method
(
1
)
{\displaystyle (1)\!\,}
y
{\displaystyle y\!\,}
y
′
=
f
(
x
,
y
)
{\displaystyle y'=f(x,y)\!\,}
x
n
=
a
0
+
h
n
{\displaystyle x_{n}=a_{0}+hn\!\,}
n
{\displaystyle n\!\,}
a
0
{\displaystyle a_{0}\!\,}
h
{\displaystyle h\!\,}
edit
y
′
(
x
n
)
=
y
′
(
a
0
+
h
n
)
=
y
′
(
a
0
)
+
h
n
y
″
(
a
0
)
+
h
2
n
2
y
‴
(
a
0
)
/
2
+
O
(
h
3
)
y
′
(
x
n
−
1
)
=
y
′
(
a
0
+
h
(
n
−
1
)
)
=
y
′
(
a
0
)
+
h
(
n
−
1
)
y
″
(
a
0
)
+
h
2
(
n
−
1
)
2
y
‴
(
a
0
)
/
2
+
O
(
h
3
)
{\displaystyle {\begin{aligned}y'(x_{n})&=y'(a_{0}+hn)\\&=y'(a_{0})+hny''(a_{0})+h^{2}n^{2}y'''(a_{0})/2+{\mathcal {O}}(h^{3})\\\\\\y'(x_{n-1})&=y'(a_{0}+h(n-1))\\&=y'(a_{0})+h(n-1)y''(a_{0})+h^{2}(n-1)^{2}y'''(a_{0})/2+{\mathcal {O}}(h^{3})\end{aligned}}}
(
1
)
{\displaystyle (1)\!\,}
h
[
5
2
y
′
(
x
n
)
+
1
2
y
′
(
x
n
−
1
)
]
=
5
2
[
h
y
′
(
a
0
)
+
h
2
n
y
″
(
a
0
)
+
O
(
h
3
)
]
+
1
2
[
h
y
′
(
a
0
)
+
h
2
(
n
−
1
)
y
″
(
a
0
)
+
O
(
h
3
)
]
=
3
h
y
′
(
a
0
)
+
1
2
(
6
n
−
1
)
y
″
(
a
0
)
+
O
(
h
3
)
{\displaystyle {\begin{aligned}h[{\frac {5}{2}}y'(x_{n})+{\frac {1}{2}}y'(x_{n-1})]&={\frac {5}{2}}[hy'(a_{0})+h^{2}ny''(a_{0})+{\mathcal {O}}(h^{3})]+{\frac {1}{2}}[hy'(a_{0})+h^{2}(n-1)y''(a_{0})+{\mathcal {O}}(h^{3})]\\&=3hy'(a_{0})+{\frac {1}{2}}(6n-1)y''(a_{0})+{\mathcal {O}}(h^{3})\end{aligned}}\!\,}
Taylor Expansion of y about a_0
edit
Since
y
n
≈
y
(
x
n
)
{\displaystyle y_{n}\approx y(x_{n})\!\,}
y
{\displaystyle y\!\,}
a
0
{\displaystyle a_{0}\!\,}
y
(
x
n
+
1
)
=
y
(
a
0
)
+
h
(
n
+
1
)
y
′
(
a
0
)
+
h
2
(
n
+
1
)
2
y
″
(
a
0
)
/
2
+
O
(
h
3
)
y
(
x
n
)
=
y
(
a
0
)
+
h
n
y
′
(
a
0
)
+
h
2
n
2
y
″
(
a
0
)
/
2
+
O
(
h
3
)
y
(
x
n
−
1
)
=
y
(
a
0
)
+
h
(
n
−
1
)
y
′
(
a
0
)
+
h
2
(
n
−
1
)
2
y
″
(
a
0
)
/
2
+
O
(
h
3
)
{\displaystyle {\begin{aligned}y(x_{n+1})&=y(a_{0})+h(n+1)y'(a_{0})+h^{2}(n+1)^{2}y''(a_{0})/2+{\mathcal {O}}(h^{3})\\\\\\y(x_{n})&=y(a_{0})+hny'(a_{0})+h^{2}n^{2}y''(a_{0})/2+{\mathcal {O}}(h^{3})\\\\\\y(x_{n-1})&=y(a_{0})+h(n-1)y'(a_{0})+h^{2}(n-1)^{2}y''(a_{0})/2+{\mathcal {O}}(h^{3})\end{aligned}}}
y
n
+
1
+
y
n
−
2
y
n
−
1
=
3
h
y
′
(
a
0
)
+
1
2
(
6
n
−
1
)
y
″
(
a
0
)
+
O
(
h
3
)
{\displaystyle y_{n+1}+y_{n}-2y_{n-1}=3hy'(a_{0})+{\frac {1}{2}}(6n-1)y''(a_{0})+{\mathcal {O}}(h^{3})\!\,}
Take Difference of Taylor Expansions
edit
Hence
y
n
+
1
+
y
n
−
2
y
n
−
1
−
h
[
5
2
y
′
(
x
n
)
+
1
2
y
′
(
x
n
−
1
)
]
=
O
(
h
3
)
{\displaystyle y_{n+1}+y_{n}-2y_{n-1}-h[{\frac {5}{2}}y'(x_{n})+{\frac {1}{2}}y'(x_{n-1})]={\mathcal {O}}(h^{3})\!\,}
Does Not Satisfy Root Condition
edit
The Characteristic equation of (1) is
λ
2
+
λ
−
2
=
0
{\displaystyle \lambda ^{2}+\lambda -2=0\!\,}
Giving the roots
λ
1
=
1
{\displaystyle \lambda _{1}=1\!\,}
λ
2
=
−
2
{\displaystyle \lambda _{2}=-2\!\,}
λ
2
{\displaystyle \lambda _{2}\!\,}
|
λ
j
|
≤
1
{\displaystyle |\lambda _{j}|\leq 1\!\,}
Give an example to show that the method (1) need not converge when solving
y
′
=
f
(
x
,
y
)
{\displaystyle y'=f(x,y)\!\,}
Let
f
(
x
,
y
)
=
0
,
y
(
0
)
=
y
0
=
1
{\displaystyle f(x,y)=0,y(0)=y_{0}=1\!\,}
y
(
t
)
=
1
{\displaystyle y(t)=1\!\,}
y
n
+
1
+
y
n
−
2
y
n
−
1
=
0
{\displaystyle y_{n+1}+y_{n}-2y_{n-1}=0\!\,}
y
n
=
C
1
(
−
2
)
n
+
C
2
⋅
1
n
{\displaystyle y_{n}=C_{1}(-2)^{n}+C_{2}\cdot 1^{n}\!\,}
C
1
≠
0
{\displaystyle C_{1}\neq 0\!\,}
y
n
→
∞
{\displaystyle y_{n}\rightarrow \infty \!\,}
n
→
∞
{\displaystyle n\rightarrow \infty \!\,}
y
0
=
C
1
+
C
2
{\displaystyle y_{0}=C_{1}+C_{2}\!\,}
y
1
=
−
2
C
1
+
C
2
{\displaystyle y_{1}=-2C_{1}+C_{2}\!\,}
y
0
−
y
1
3
=
C
1
{\displaystyle {\frac {y_{0}-y_{1}}{3}}=C_{1}\!\,}
y
0
≠
y
1
{\displaystyle y_{0}\neq y_{1}\!\,}
C
1
≠
0
{\displaystyle C_{1}\neq 0\!\,}
Consider the boundary value problem
−
u
″
+
(
1
+
x
)
u
=
x
2
u
′
(
0
)
=
1
,
u
(
1
)
=
1
(
2
)
{\displaystyle -u''+(1+x)u=x^{2}\quad u'(0)=1,u(1)=1\qquad (2)\!\,}
Prove that
(
2
)
{\displaystyle (2)\!\,}
Let
u
1
{\displaystyle u_{1}\!\,}
u
2
{\displaystyle u_{2}\!\,}
u
≡
u
1
−
u
2
{\displaystyle u\equiv u_{1}-u_{2}\!\,}
−
u
″
+
(
1
+
x
)
u
=
0
u
′
(
0
)
=
0
,
u
(
1
)
=
0
{\displaystyle -u''+(1+x)u=0\quad u'(0)=0,u(1)=0\!\,}
v
∈
V
=
{
v
∈
H
1
:
v
(
1
)
=
0
}
{\displaystyle v\in V=\{v\in H^{1}:v(1)=0\}\!\,}
u
∈
V
{\displaystyle u\in V\!\,}
v
∈
V
{\displaystyle v\in V\!\,}
∫
0
1
u
′
v
′
+
∫
0
1
(
1
+
x
)
u
v
=
0
{\displaystyle \int _{0}^{1}u'v'+\int _{0}^{1}(1+x)uv=0\!\,}
v
=
u
{\displaystyle v=u\!\,}
∫
0
1
(
u
′
)
2
+
∫
0
1
(
1
+
x
)
u
2
=
0
{\displaystyle \int _{0}^{1}(u')^{2}+\int _{0}^{1}(1+x)u^{2}=0\!\,}
(
u
′
)
2
{\displaystyle (u')^{2}\!\,}
(
1
+
x
)
{\displaystyle (1+x)\!\,}
u
2
{\displaystyle u^{2}\!\,}
>
0
{\displaystyle >0\!\,}
u
2
=
0
{\displaystyle u^{2}=0\!\,}
u
1
=
u
2
{\displaystyle u_{1}=u_{2}\!\,}
Discretize the problem. Take a uniform partition of
[
0
,
1
]
:
{\displaystyle [0,1]:\!\,}
x
i
=
i
h
,
i
=
0
,
1
,
2
,
…
,
n
,
h
=
1
n
{\displaystyle x_{i}=ih,i=0,1,2,\ldots ,n,\quad h={\frac {1}{n}}\!\,}
u
″
{\displaystyle u''\!\,}
x
=
0
{\displaystyle x=0\!\,}
A
x
=
b
{\displaystyle Ax=b\!\,}
x
=
(
u
1
,
u
2
,
⋯
,
u
n
−
1
)
T
{\displaystyle x=(u_{1},u_{2},\cdots ,u_{n-1})^{T}\!\,}
The three point difference formula for
u
″
{\displaystyle u''\!\,}
u
″
(
x
)
=
u
(
x
+
h
)
−
2
u
(
x
)
+
u
(
x
−
h
)
h
2
{\displaystyle u''(x)={\frac {u(x+h)-2u(x)+u(x-h)}{h^{2}}}\!\,}
edit
Substituting into
(
2
)
{\displaystyle (2)\!\,}
[
−
1
h
2
2
h
2
+
(
1
+
i
h
)
−
1
h
2
]
[
u
i
−
1
u
i
u
i
+
1
]
=
(
i
h
)
2
{\displaystyle {\begin{bmatrix}-{\frac {1}{h^{2}}}&&&{\frac {2}{h^{2}}}+(1+ih)&&&-{\frac {1}{h^{2}}}\end{bmatrix}}{\begin{bmatrix}u_{i-1}\\u_{i}\\u_{i+1}\end{bmatrix}}=(ih)^{2}}
We can eliminate the
u
0
{\displaystyle u_{0}\!\,}
u
′
(
0
)
=
u
1
−
u
0
h
=
1
{\displaystyle u'(0)={\frac {u_{1}-u_{0}}{h}}=1\!\,}
u
0
=
u
1
−
h
{\displaystyle u_{0}=u_{1}-h\!\,}
[
1
h
2
+
(
1
+
h
)
−
1
h
2
]
[
u
1
u
2
]
=
h
2
−
1
h
{\displaystyle {\begin{bmatrix}{\frac {1}{h^{2}}}+(1+h)&&&-{\frac {1}{h^{2}}}\end{bmatrix}}{\begin{bmatrix}u_{1}\\u_{2}\end{bmatrix}}=h^{2}-{\frac {1}{h}}\!\,}
Since
u
(
1
)
=
u
n
=
1
{\displaystyle u(1)=u_{n}=1\!\,}
u
n
{\displaystyle u_{n}\!\,}
[
−
1
h
2
2
h
2
+
(
1
+
(
n
−
1
)
h
)
]
[
u
n
−
2
u
n
−
1
]
=
h
2
−
(
(
n
−
1
)
h
)
2
+
1
h
2
{\displaystyle {\begin{bmatrix}-{\frac {1}{h^{2}}}&&&{\frac {2}{h^{2}}}+(1+(n-1)h)\end{bmatrix}}{\begin{bmatrix}u_{n-2}\\u_{n-1}\end{bmatrix}}=h^{2}-((n-1)h)^{2}+{\frac {1}{h^{2}}}}
Prove that the equation found in
(
b
)
{\displaystyle (b)\!\,}
Since the matrix
A
{\displaystyle A\!\,}
A
x
=
b
{\displaystyle Ax=b\!\,}
Transform the problem
(
2
)
{\displaystyle (2)\!\,}
Let
u
{\displaystyle u\!\,}
u
=
w
+
v
{\displaystyle u=w+v\!\,}
−
w
″
+
(
1
+
x
)
w
=
f
(
x
)
w
′
(
0
)
=
0
,
w
(
1
)
=
0
{\displaystyle -w''+(1+x)w=f(x)\quad w'(0)=0,w(1)=0\!\,}
−
v
″
+
(
1
+
x
)
v
=
g
(
x
)
v
′
(
0
)
=
1
,
v
(
1
)
=
1
(
∗
)
{\displaystyle -v''+(1+x)v=g(x)\quad v'(0)=1,v(1)=1\qquad (*)\!\,}
−
u
″
+
(
1
+
x
)
u
=
x
2
=
f
(
x
)
+
g
(
x
)
u
′
(
0
)
=
1
,
u
(
1
)
=
1
{\displaystyle -u''+(1+x)u=x^{2}=f(x)+g(x)\quad u'(0)=1,u(1)=1\!\,}
v
(
x
)
=
a
x
+
b
{\displaystyle v(x)=ax+b\!\,}
v
′
(
0
)
=
a
=
1
{\displaystyle v'(0)=a=1\!\,}
v
(
1
)
=
1
+
b
=
1
{\displaystyle v(1)=1+b=1\!\,}
b
=
0
{\displaystyle b=0\!\,}
v
(
x
)
=
x
{\displaystyle v(x)=x\!\,}
(
∗
)
{\displaystyle (*)\!\,}
−
0
+
(
1
+
x
)
x
=
g
(
x
)
{\displaystyle -0+(1+x)x=g(x)\!\,}
g
(
x
)
=
x
2
+
x
{\displaystyle g(x)=x^{2}+x\!\,}
f
(
x
)
+
g
(
x
)
=
x
2
{\displaystyle f(x)+g(x)=x^{2}\!\,}
f
(
x
)
=
−
x
{\displaystyle f(x)=-x\!\,}
−
w
″
+
(
1
+
x
)
w
=
−
x
w
′
(
0
)
=
0
,
w
(
1
)
=
0
{\displaystyle -w''+(1+x)w=-x\quad w'(0)=0,w(1)=0\!\,}
Using the problem's notation, we want to find
v
∈
H
=
{
w
∈
H
1
:
w
(
1
)
=
0
}
{\displaystyle v\in H=\{w\in H^{1}:w(1)=0\}\!\,}
w
∈
H
{\displaystyle w\in H\!\,}
a
(
v
,
w
)
=
∫
0
1
v
′
w
′
+
∫
0
1
(
1
+
x
)
v
w
=
−
∫
0
1
x
w
=
F
(
w
)
{\displaystyle a(v,w)=\int _{0}^{1}v'w'+\int _{0}^{1}(1+x)vw=-\int _{0}^{1}xw=F(w)\!\,}
To show that
v
{\displaystyle v\!\,}
edit
a
(
v
,
w
)
=
∫
0
1
v
′
w
′
+
∫
0
1
(
1
+
x
)
⏟
≤
2
v
w
≤
2
[
∫
0
1
v
′
w
′
+
∫
0
1
v
w
]
≤
2
[
[
∫
0
1
v
′
2
]
1
2
[
∫
0
1
w
′
2
]
1
2
+
[
∫
0
1
v
2
]
1
2
[
∫
0
1
w
2
]
1
2
]
Cauchy-Schwartz in L2
≤
2
[
[
∫
0
1
v
′
2
+
∫
0
1
v
2
]
1
2
[
∫
0
1
w
′
2
+
∫
0
1
w
2
]
1
2
]
Cauchy-Schwartz in R2
=
2
‖
w
‖
1
‖
v
‖
1
{\displaystyle {\begin{aligned}a(v,w)&=\int _{0}^{1}v'w'+\int _{0}^{1}\underbrace {(1+x)} _{\leq 2}vw\\&\leq 2\left[\int _{0}^{1}v'w'+\int _{0}^{1}vw\right]\\&\leq 2\left[\left[\int _{0}^{1}v'^{2}\right]^{\frac {1}{2}}\left[\int _{0}^{1}w'^{2}\right]^{\frac {1}{2}}+\left[\int _{0}^{1}v^{2}\right]^{\frac {1}{2}}\left[\int _{0}^{1}w^{2}\right]^{\frac {1}{2}}\right]\quad {\mbox{ Cauchy-Schwartz in L2 }}\\&\leq 2\left[\left[\int _{0}^{1}v'^{2}+\int _{0}^{1}v^{2}\right]^{\frac {1}{2}}\left[\int _{0}^{1}w'^{2}+\int _{0}^{1}w^{2}\right]^{\frac {1}{2}}\right]{\mbox{ Cauchy-Schwartz in R2 }}\\&=2\|w\|_{1}\|v\|_{1}\end{aligned}}\!\,}
a
(
v
,
v
)
=
∫
0
1
v
′
2
+
∫
0
1
(
1
+
v
)
⏟
≥
1
v
2
≥
∫
0
1
v
′
2
+
∫
v
2
=
‖
v
‖
1
2
{\displaystyle {\begin{aligned}a(v,v)&=\int _{0}^{1}v'^{2}+\int _{0}^{1}\underbrace {(1+v)} _{\geq 1}v^{2}\\&\geq \int _{0}^{1}v'^{2}+\int v^{2}\\&=\|v\|_{1}^{2}\end{aligned}}}
|
F
(
v
)
|
=
|
−
∫
0
1
x
v
|
≤
|
∫
0
1
v
|
≤
‖
v
‖
1
2
{\displaystyle |F(v)|=|-\int _{0}^{1}xv|\leq |\int _{0}^{1}v|\leq \|v\|_{1}^{2}\!\,}
Consider the approximation of
v
{\displaystyle v\!\,}
Let
f
:
R
→
R
{\displaystyle f:\mathbb {R} \to \mathbb {R} \!\,}
x
∗
{\displaystyle x_{*}\!\,}
f
(
x
,
y
)
=
[
x
2
−
2
x
+
y
2
x
−
y
2
−
1
]
{\displaystyle f(x,y)={\begin{bmatrix}x^{2}-2x+y\\2x-y^{2}-1\end{bmatrix}}\!\,}
x
∗
=
[
1
1
]
{\displaystyle x_{*}={\begin{bmatrix}1\\1\end{bmatrix}}\!\,}
x
n
+
1
=
x
n
−
A
f
(
x
n
)
{\displaystyle x_{n+1}=x_{n}-Af(x_{n})\!\,}
A
=
[
1
1
2
1
0
]
(
4
)
{\displaystyle A={\begin{bmatrix}1&{\frac {1}{2}}\\1&0\end{bmatrix}}\qquad (4)\!\,}
Prove (4) is locally convergent.
ϕ
(
x
n
)
:=
x
n
+
1
=
x
n
−
A
f
(
x
n
)
{\displaystyle \phi (x_{n}):=x_{n+1}=x_{n}-Af(x_{n})\!\,}
ϕ
(
x
)
{\displaystyle \phi (x)\!\,}
x
∗
{\displaystyle x_{*}\!\,}
γ
<
1
{\displaystyle \gamma <1\!\,}
‖
ϕ
(
x
)
−
ϕ
(
y
)
‖
≤
γ
‖
x
−
y
‖
{\displaystyle \|\phi (x)-\phi (y)\|\leq \gamma \|x-y\|\!\,}
‖
ϕ
(
x
)
−
ϕ
(
y
)
‖
≤
‖
D
ϕ
(
ξ
)
‖
‖
x
−
y
‖
{\displaystyle \|\phi (x)-\phi (y)\|\leq \|D\phi (\xi )\|\|x-y\|\!\,}
γ
=
D
ϕ
(
ξ
)
{\displaystyle \gamma =D\phi (\xi )\!\,}
ξ
{\displaystyle \xi \!\,}
x
∗
{\displaystyle x_{*}\!\,}
‖
D
ϕ
(
x
∗
)
‖
=
‖
I
−
A
D
ϕ
(
x
∗
)
‖
=
0
<
1
{\displaystyle \|D\phi (x_{*})\|=\|I-AD\phi (x_{*})\|=0<1\!\,}
ϕ
(
x
)
{\displaystyle \phi (x)\!\,}
Calculating the Jacobian
edit
D
ϕ
=
D
x
−
A
D
f
{\displaystyle D\phi =Dx-ADf\!\,}
D
x
=
I
{\displaystyle Dx=I\!\,}
D
f
=
(
2
x
−
2
1
2
−
2
y
)
{\displaystyle Df={\begin{pmatrix}2x-2&1\\2&-2y\end{pmatrix}}\!\,}
D
ϕ
(
x
∗
)
=
I
−
A
D
ϕ
(
x
∗
)
=
(
1
0
0
1
)
−
(
1
1
2
1
0
)
(
2
(
1
)
−
2
1
2
−
2
(
1
)
)
=
(
1
0
0
1
)
−
(
1
0
0
1
)
=
(
0
0
0
0
)
‖
D
ϕ
(
x
∗
)
‖
=
0
{\displaystyle {\begin{aligned}D\phi (x_{*})&=I-AD\phi (x_{*})\\&={\begin{pmatrix}1&0\\0&1\end{pmatrix}}-{\begin{pmatrix}1&{\frac {1}{2}}\\1&0\end{pmatrix}}{\begin{pmatrix}2(1)-2&1\\2&-2(1)\end{pmatrix}}\\&={\begin{pmatrix}1&0\\0&1\end{pmatrix}}-{\begin{pmatrix}1&0\\0&1\end{pmatrix}}\\&={\begin{pmatrix}0&0\\0&0\end{pmatrix}}\\\|D\phi (x_{*})\|&=0\end{aligned}}}
{\displaystyle \!\,}
Show that the convergence is at least quadratic.
e
n
+
1
=
x
n
+
1
−
x
∗
=
x
n
−
A
f
(
x
n
)
⏟
ϕ
(
x
n
)
−
x
∗
=
ϕ
(
x
n
)
−
x
∗
=
(
ϕ
(
x
∗
)
+
(
x
n
−
x
∗
)
T
D
ϕ
(
x
∗
)
⏟
0
+
(
x
n
−
x
∗
)
T
H
ϕ
(
x
∗
)
2
!
(
x
n
−
x
∗
)
+
R
(
x
n
,
x
∗
)
)
−
x
∗
=
(
x
∗
+
A
f
(
x
∗
)
⏟
0
+
H
ϕ
(
x
∗
)
2
!
(
x
n
−
x
∗
)
T
(
x
n
−
x
∗
)
⏟
e
n
2
+
R
(
x
n
,
x
∗
)
)
−
x
∗
≤
C
e
n
2
+
R
(
x
n
,
x
∗
)
{\displaystyle {\begin{aligned}e_{n+1}&=x_{n+1}-x_{*}\\&=\underbrace {x_{n}-Af(x_{n})} _{\phi (x_{n})}-x_{*}\\&=\phi (x_{n})-x_{*}\\&=\left(\phi (x_{*})+(x_{n}-x_{*})^{T}\underbrace {D_{\phi }(x_{*})} _{0}+(x_{n}-x_{*})^{T}{\frac {H_{\phi }(x_{*})}{2!}}(x_{n}-x_{*})+R(x_{n},x_{*})\right)-x_{*}\\&=\left(x_{*}+A\underbrace {f(x_{*})} _{0}+{\frac {H_{\phi }(x_{*})}{2!}}\underbrace {(x_{n}-x_{*})^{T}(x_{n}-x_{*})} _{e_{n}^{2}}+R(x_{n},x_{*})\right)-x_{*}\\&\leq Ce_{n}^{2}+R(x_{n},x_{*})\end{aligned}}\!\,}
R
(
x
n
,
x
∗
)
{\displaystyle R(x_{n},x_{*})\!\,}
‖
R
(
x
n
,
x
∗
)
‖
‖
x
n
−
x
∗
‖
→
0
{\displaystyle {\frac {\|R(x_{n},x_{*})\|}{\|x_{n}-x_{*}\|}}\rightarrow 0\!\,}
‖
x
n
−
x
∗
‖
→
0
{\displaystyle \|x_{n}-x_{*}\|\rightarrow 0\!\,}
‖
e
n
+
1
‖
≤
C
‖
e
n
‖
2
{\displaystyle \|e_{n+1}\|\leq C\|e_{n}\|^{2}\!\,}
Write the Newton iteration and compare it with (4)
The Newton iteration looks like this:
x
n
+
1
=
x
n
−
B
(
x
n
)
f
(
x
n
)
{\displaystyle x_{n+1}=x_{n}-B(x_{n})f(x_{n})\!\,}
[
x
n
+
1
y
n
+
1
]
=
[
x
n
y
n
]
−
[
2
x
n
−
2
1
2
−
2
y
n
]
−
1
⏟
B
[
x
n
2
−
2
x
n
+
y
n
2
x
n
−
y
n
2
−
1
]
{\displaystyle {\begin{bmatrix}x_{n+1}\\y_{n+1}\end{bmatrix}}={\begin{bmatrix}x_{n}\\y_{n}\end{bmatrix}}-\underbrace {{\begin{bmatrix}2x_{n}-2&1\\2&-2y_{n}\end{bmatrix}}^{-1}} _{B}{\begin{bmatrix}x_{n}^{2}-2x_{n}+y_{n}\\2x_{n}-y_{n}^{2}-1\end{bmatrix}}}
B
(
x
∗
)
=
[
2
(
1
)
−
2
1
2
−
2
(
1
)
]
−
1
=
[
0
1
2
−
2
]
−
1
=
[
1
1
2
1
0
]
=
A
{\displaystyle B(x_{*})={\begin{bmatrix}2(1)-2&1\\2&-2(1)\end{bmatrix}}^{-1}={\begin{bmatrix}0&1\\2&-2\end{bmatrix}}^{-1}={\begin{bmatrix}1&{\frac {1}{2}}\\1&0\end{bmatrix}}=A}
B
(
x
∗
)
{\displaystyle B(x_{*})\!\,}
![{\displaystyle y_{n+1}=2y_{n-1}-y_{n}+h[{\frac {5}{2}}f(x_{n},y_{n})+{\frac {1}{2}}f(x_{n-1},y_{n-1})]\qquad (1)\!\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a9a1631e5fe622c0abef1e78022d20d049550f71)
![{\displaystyle {\begin{aligned}h[{\frac {5}{2}}y'(x_{n})+{\frac {1}{2}}y'(x_{n-1})]&={\frac {5}{2}}[hy'(a_{0})+h^{2}ny''(a_{0})+{\mathcal {O}}(h^{3})]+{\frac {1}{2}}[hy'(a_{0})+h^{2}(n-1)y''(a_{0})+{\mathcal {O}}(h^{3})]\\&=3hy'(a_{0})+{\frac {1}{2}}(6n-1)y''(a_{0})+{\mathcal {O}}(h^{3})\end{aligned}}\!\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6b4e3f34594bfe84b6e79454cbcdd373402000eb)
![{\displaystyle y_{n+1}+y_{n}-2y_{n-1}-h[{\frac {5}{2}}y'(x_{n})+{\frac {1}{2}}y'(x_{n-1})]={\mathcal {O}}(h^{3})\!\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/94572ba9bc0bda642e7a122cc5e9d48ef9046575)
![{\displaystyle [0,1]:\!\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ef49e1b0f610125281fd813aaaabccfbd92bd455)
![{\displaystyle {\begin{aligned}a(v,w)&=\int _{0}^{1}v'w'+\int _{0}^{1}\underbrace {(1+x)} _{\leq 2}vw\\&\leq 2\left[\int _{0}^{1}v'w'+\int _{0}^{1}vw\right]\\&\leq 2\left[\left[\int _{0}^{1}v'^{2}\right]^{\frac {1}{2}}\left[\int _{0}^{1}w'^{2}\right]^{\frac {1}{2}}+\left[\int _{0}^{1}v^{2}\right]^{\frac {1}{2}}\left[\int _{0}^{1}w^{2}\right]^{\frac {1}{2}}\right]\quad {\mbox{ Cauchy-Schwartz in L2 }}\\&\leq 2\left[\left[\int _{0}^{1}v'^{2}+\int _{0}^{1}v^{2}\right]^{\frac {1}{2}}\left[\int _{0}^{1}w'^{2}+\int _{0}^{1}w^{2}\right]^{\frac {1}{2}}\right]{\mbox{ Cauchy-Schwartz in R2 }}\\&=2\|w\|_{1}\|v\|_{1}\end{aligned}}\!\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/381fda54412816c0ca7bee994177c8804dc69016)
