Definitions and Basics
edit
Definition of a Vector Norm
edit
The most ordinary kind of vectors are those consisting of
ordered n-tuples of real or complex numbers. They may be written
in row
<
x
y
z
>
,
{\displaystyle <\;x\quad y\quad z\;>,}
[
x
y
z
]
,
{\displaystyle {\begin{bmatrix}x&y&z\\\end{bmatrix}},}
(
x
,
y
,
z
)
,
{\displaystyle (\;x,\quad y,\quad z\;),}
or column
[
x
y
z
]
{\displaystyle {\begin{bmatrix}x\\y\\z\\\end{bmatrix}}}
forms. Commas or other seperators of components or coordinates
may or may not be used. When a vector has many elements, notations like
[
x
1
x
2
⋯
x
n
]
{\displaystyle {\begin{bmatrix}x_{1}&x_{2}&\cdots &x_{n}\\\end{bmatrix}}}
or
[
x
1
x
2
⋯
x
n
]
T
{\displaystyle {\begin{bmatrix}x_{1}&x_{2}&\cdots &x_{n}\\\end{bmatrix}}^{T}}
are often used. A most popular notation to indicate a
vector is
v
→
=
<
v
1
v
2
⋯
v
n
>
{\displaystyle {\vec {v}}\;=\;<v_{1}\;v_{2}\;\cdots \;v_{n}>}
.
Vectors are usually added component-wise, for
v
→
=
<
v
1
v
2
⋯
v
n
>
{\displaystyle {\vec {v}}\;=\;<v_{1}\;v_{2}\;\cdots \;v_{n}>}
and
w
→
=
<
w
1
w
2
⋯
w
n
>
{\displaystyle {\vec {w}}\;=\;<w_{1}\;w_{2}\;\cdots \;w_{n}>}
,
v
→
+
w
→
=
<
(
v
1
+
w
1
)
(
v
2
+
w
2
)
⋯
(
v
n
+
w
n
)
>
{\displaystyle {\vec {v}}+{\vec {w}}\;=\;<(v_{1}+w_{1})\;\;(v_{2}+w_{2})\;\cdots \;(v_{n}+w_{n})>}
.Scalar multiplication is defined by
α
v
→
=
<
α
v
1
α
v
2
⋯
α
v
n
>
{\displaystyle \alpha \,{\vec {v}}\;=\;<\alpha \,v_{1}\;\,\alpha \,v_{2}\;\cdots \;\alpha \,v_{n}>}
.
A vector norm is a generalization of ordinary absolute value
|
x
|
{\displaystyle \left\vert x\right\vert }
of a real or complex number.
For
u
→
{\displaystyle {\vec {u}}}
and
v
→
{\displaystyle {\vec {v}}}
,
vectors , and
α
{\displaystyle \alpha }
, a scalar , a vector norm is a real
value
‖
⋅
‖
{\displaystyle \lVert \cdot \rVert }
associated with a vector for which the following
properties hold.
(
i
)
‖
v
→
‖
≥
0
(
i
i
)
‖
v
→
‖
=
0
⟺
v
→
=
0
(
i
i
i
)
‖
α
v
→
‖
=
|
α
|
‖
v
→
‖
(
i
v
)
‖
v
→
+
w
→
‖
≤
‖
v
→
‖
+
‖
w
→
‖
{\displaystyle {\begin{aligned}(i)\;\;\;\quad &\lVert \,{\vec {v}}\,\rVert \;\geq \;0\\(ii)\;\;\quad &\lVert \,{\vec {v}}\,\rVert \;=\;0\iff \;{\vec {v}}\;=\;0\\(iii)\;\quad &\lVert \,\alpha \,{\vec {v}}\,\rVert \;=\;\left\vert \alpha \right\vert \,\lVert \,{\vec {v}}\,\rVert \\(iv)\;\;\quad &\lVert \,{\vec {v}}+{\vec {w}}\,\rVert \;\;\leq \;\;\lVert \,{\vec {v}}\,\rVert \;+\;\lVert \,{\vec {w}}\,\rVert \;\end{aligned}}}
.
The most commonly used norms are:
‖
v
→
‖
2
=
|
v
1
|
2
+
|
v
2
|
2
+
…
+
|
v
n
|
2
‖
v
→
‖
1
=
|
v
1
|
+
|
v
2
|
+
…
+
|
v
n
|
‖
v
→
‖
∞
=
max
|
v
i
|
1
≤
i
≤
n
‖
v
→
‖
p
=
(
|
v
1
|
p
+
|
v
2
|
p
+
…
+
|
v
n
|
p
)
1
p
{\displaystyle {\begin{aligned}\quad &\lVert \,{\vec {v}}\,\rVert _{2}\;=\;{\sqrt {{\left\vert v_{1}\right\vert }^{2}+{\left\vert v_{2}\right\vert }^{2}+\ldots +{\left\vert v_{n}\right\vert }^{2}}}\\\quad &\lVert \,{\vec {v}}\,\rVert _{1}\;=\;\left\vert v_{1}\right\vert +\left\vert v_{2}\right\vert +\ldots +\left\vert v_{n}\right\vert \\\quad &\lVert \,{\vec {v}}\,\rVert _{\infty }\;=\;{\underset {1\,\leq \,i\,\leq \,n}{\max \left\vert v_{i}\right\vert }}\\\quad &\lVert \,{\vec {v}}\,\rVert _{p}\;=\;(\left\vert v_{1}\right\vert ^{p}+\left\vert v_{2}\right\vert ^{p}+\ldots +\left\vert v_{n}\right\vert ^{p})^{\frac {1}{p}}\\\end{aligned}}}
.
Any two norms on
n
{\displaystyle n}
dimensional vectors of complex numbers
are topologically equivalent in the sense that, if
‖
⋅
‖
a
{\displaystyle \lVert \cdot \rVert _{a}}
and
‖
⋅
‖
b
{\displaystyle \lVert \cdot \rVert _{b}}
are two different norms, then there exist positive constants
c
1
{\displaystyle c_{1}}
and
c
2
{\displaystyle c_{2}}
such that
c
1
‖
⋅
‖
a
≤
‖
⋅
‖
b
≤
c
2
‖
⋅
‖
a
{\displaystyle c_{1}\,\lVert \cdot \rVert _{a}\;\leq \;\lVert \cdot \rVert _{b}\;\leq \;c_{2}\,\lVert \cdot \rVert _{a}}
.
Inner Product of Vectors
edit
The inner product (or dot product), of two vectors
v
→
=
<
v
1
v
2
⋯
v
n
>
{\displaystyle {\vec {v}}\;=\;<v_{1}\;v_{2}\;\cdots \;v_{n}>}
and
w
→
=
<
w
1
w
2
⋯
w
n
>
{\displaystyle {\vec {w}}\;=\;<w_{1}\;w_{2}\;\cdots \;w_{n}>}
,
is defined by
v
→
⋅
w
→
=
v
1
w
1
+
v
2
w
2
+
⋯
+
v
n
w
n
{\displaystyle {\vec {v}}\,\cdot \,{\vec {w}}\;=\;v_{1}\,w_{1}+v_{2}\,w_{2}+\;\cdots \;+v_{n}\,w_{n}}
,
or when
v
→
{\displaystyle {\vec {v}}}
and
w
→
{\displaystyle {\vec {w}}}
are complex valued, by
v
→
⋅
w
→
=
v
1
w
¯
1
+
v
2
w
¯
2
+
⋯
+
v
n
w
¯
n
{\displaystyle {\vec {v}}\,\cdot \,{\vec {w}}\;=\;v_{1}\,{\overline {w}}_{1}+v_{2}\,{\overline {w}}_{2}+\;\cdots \;+v_{n}\,{\overline {w}}_{n}}
.
It is often indicated by any one of several notations:
v
→
⋅
w
→
,
v
→
T
w
→
,
<
v
→
,
w
→
>
,
{\displaystyle {\vec {v}}\,\cdot \,{\vec {w}}\,,\quad {\vec {v}}^{\,T}{\vec {w}}\,,\quad <{\vec {v}}\,,\;{\vec {w}}>,}
or
(
v
→
,
w
→
)
{\displaystyle ({\vec {v}}\,,\;{\vec {w}})}
.
Besides the dot product, other inner products are defined to be a rule that sssigns to each pair of vectors
v
→
,
w
→
{\displaystyle {\vec {v}}\,,\;{\vec {w}}}
, a complex number with the following properties.
<
α
v
→
,
w
→
>
=
α
<
v
→
,
w
→
>
{\displaystyle <\alpha \,{\vec {v}}\,,\;{\vec {w}}>\;=\;\alpha \,<{\vec {v}}\,,\;{\vec {w}}>}
<
v
→
,
w
→
>
=
<
w
→
,
v
→
>
¯
{\displaystyle <{\vec {v}}\,,\;{\vec {w}}>\;=\;{\overline {<{\vec {w}}\,,\;{\vec {v}}>}}}
<
v
1
→
+
v
2
→
,
w
→
>
=
<
v
1
→
,
w
→
>
+
<
v
2
→
,
w
→
>
{\displaystyle <{\vec {v_{1}}}+{\vec {v_{2}}}\,,\;{\vec {w}}>\;=\;<{\vec {v_{1}}}\,,\;{\vec {w}}>+<{\vec {v_{2}}}\,,\;{\vec {w}}>}
for
v
→
≠
0
{\displaystyle {\vec {v}}\;\neq \;0}
,
<
v
→
,
v
→
>
{\displaystyle <{\vec {v}}\,,\;{\vec {v}}>}
is real valued and positive
<
v
→
,
v
→
>
>
0
{\displaystyle <{\vec {v}}\,,\;{\vec {v}}>\;>\;0}
and
|
<
v
→
,
w
→
>
|
2
≤
<
v
→
,
v
→
><
w
→
,
w
→
>
{\displaystyle \left\vert <{\vec {v}}\,,\;{\vec {w}}>\right\vert ^{2}\;\leq \;<{\vec {v}}\,,\;{\vec {v}}><{\vec {w}}\,,\;{\vec {w}}>}
An inner product defines a norm by
‖
v
→
‖
=
<
v
→
,
v
→
>
{\displaystyle \lVert \,{\vec {v}}\,\rVert \;=\;{\sqrt {<{\vec {v}}\,,\;{\vec {v}}>}}}
.
Inequalities Involving Norms
edit
The Cauchy Schwarz and Holder's inequalities are commonly
employed.
|
v
→
⋅
w
→
|
≤
‖
v
→
‖
2
‖
w
→
‖
2
{\displaystyle \left\vert \,{\vec {v}}\,\cdot \,{\vec {w}}\,\right\vert \;\leq \;\lVert \,{\vec {v}}\,\rVert _{2}\,\lVert \,{\vec {w}}\,\rVert _{2}}
|
v
→
⋅
w
→
|
≤
‖
v
→
‖
p
‖
w
→
‖
q
{\displaystyle \left\vert \,{\vec {v}}\,\cdot \,{\vec {w}}\,\right\vert \;\leq \;\lVert \,{\vec {v}}\,\rVert _{p}\,\lVert \,{\vec {w}}\,\rVert _{q}}
for
1
p
+
1
q
=
1
{\displaystyle {\tfrac {1}{p}}+{\tfrac {1}{q}}\;=\;1}
Definition of a Matrix Norm
edit
The most ordinary kind of matices are those consisting of
rectangular arrays of real or complex numbers. They may be written
in element form
A
=
(
a
i
j
)
,
1
≤
m
,
1
≤
n
{\displaystyle A\;=\;(a_{i\,j}),\;1\;\leq \;m\,,\;\;1\;\leq \;n}
and be considered as collections of column or row vectors.
Matrices are usually added element-wise, for
A
=
(
a
i
j
)
,
B
=
(
b
i
j
)
,
A
+
B
=
(
a
i
j
+
b
i
j
)
{\displaystyle A\;=\;(a_{i\,j}),\;B\;=\;(b_{i\,j}),\quad \;A+B\;=\;(a_{i\,j}+b_{i\,j})}
Scalar multiplication is defined by
α
A
=
(
α
a
i
j
)
{\displaystyle \alpha \,A\;=\;(\alpha \,a_{i\,j})}
.
The notation
A
=
0
{\displaystyle A\;=\;0}
means that all elements
of
A
{\displaystyle A}
are identically zero .
A matrix norm is a generalization of ordinary absolute value
|
x
|
{\displaystyle \left\vert x\right\vert }
of a real or complex number, and can be considered a type of a vector norm .
For
A
{\displaystyle A}
and
B
{\displaystyle B}
,
matrices , and
α
{\displaystyle \alpha }
, a scalar , a matrix norm is a real
value
‖
⋅
‖
{\displaystyle \lVert \cdot \rVert }
associated with a matrix for which the following
properties hold.
(
i
)
‖
A
‖
≥
0
(
i
i
)
‖
A
‖
=
0
⟺
A
=
0
(
i
i
i
)
‖
α
A
‖
=
|
α
|
‖
A
‖
(
i
v
)
‖
A
+
B
‖
≤
‖
A
‖
+
‖
B
‖
{\displaystyle {\begin{aligned}(i)\;\;\;\quad &\lVert \,A\,\rVert \;\geq \;0\\(ii)\;\;\quad &\lVert \,A\,\rVert \;=\;0\iff \;A\;=\;0\\(iii)\;\quad &\lVert \,\alpha \,A\,\rVert \;=\;\left\vert \alpha \right\vert \,\lVert \,A\,\rVert \\(iv)\;\;\quad &\lVert \,A+B\,\rVert \;\;\leq \;\;\lVert \,A\,\rVert \;+\;\lVert \,B\,\rVert \;\end{aligned}}}
.
The most commonly used norms are:
‖
A
‖
F
=
∑
i
=
1
m
∑
j
=
1
n
|
a
i
j
|
2
‖
A
‖
∞
=
max
1
≤
i
≤
m
(
|
a
i
1
|
+
|
a
i
2
|
+
…
+
|
a
i
n
|
)
‖
A
‖
1
=
max
1
≤
j
≤
n
(
|
a
1
j
|
+
|
a
2
j
|
+
…
+
|
a
m
j
|
)
‖
A
‖
max
=
max
{
|
a
i
j
|
}
1
≤
i
≤
m
,
1
≤
j
≤
n
‖
A
‖
p
=
(
∑
i
=
1
m
∑
j
=
1
n
|
a
i
j
|
p
)
1
p
‖
A
‖
2
=
max
‖
x
‖
2
=
1
‖
A
x
‖
2
{\displaystyle {\begin{aligned}\quad &\lVert \,A\,\rVert _{F}\;=\;{\sqrt {\textstyle \sum _{i\,=\,1}^{m}\textstyle \sum _{j\,=\,1}^{n}{\left\vert a_{i\,j}\right\vert }^{2}}}\\\quad &\lVert \,A\,\rVert _{\infty }\;=\;{\underset {1\;\leq \;i\;\leq \;m}{\max \;}}(\left\vert a_{i\,1}\right\vert +\left\vert a_{i\,2}\right\vert +\ldots +\left\vert a_{i\,n}\right\vert )\\\quad &\lVert \,A\,\rVert _{1}\;=\;{\underset {1\;\leq \;j\;\leq \;n}{\max \;}}(\left\vert a_{1\,j}\right\vert +\left\vert a_{2\,j}\right\vert +\ldots +\left\vert a_{m\,j}\right\vert )\\\quad &\lVert \,A\,\rVert _{\max }\;=\;{\underset {1\,\leq \,i\,\leq \,m,\;1\,\leq \,j\,\leq \,n}{\max {\{\left\vert a_{i\,j}\right\vert \}}}}\\\quad &\lVert \,A\,\rVert _{p}\;=\;(\textstyle \sum _{i\,=\,1}^{m}\textstyle \sum _{j\,=\,1}^{n}\left\vert a_{i\,j}\right\vert ^{p})^{\frac {1}{p}}\\\quad &\lVert \,A\,\rVert _{2}\;=\;{\underset {\lVert \,x\,\rVert _{2}\;=\;1}{\max }}\;\lVert \,A\,x\,\rVert _{2}\\\end{aligned}}}
.
Like vector norms any two matrix norms on
m
×
n
{\displaystyle m\times n}
matrices of complex numbers are topologically equivalent in the sense that, if
‖
⋅
‖
a
{\displaystyle \lVert \cdot \rVert _{a}}
and
‖
⋅
‖
b
{\displaystyle \lVert \cdot \rVert _{b}}
are two different norms, then there exist positive constants
c
1
{\displaystyle c_{1}}
and
c
2
{\displaystyle c_{2}}
such that
c
1
‖
⋅
‖
a
≤
‖
⋅
‖
b
≤
c
2
‖
⋅
‖
a
{\displaystyle c_{1}\,\lVert \cdot \rVert _{a}\;\leq \;\lVert \cdot \rVert _{b}\;\leq \;c_{2}\,\lVert \cdot \rVert _{a}}
.
The norm
‖
A
‖
2
{\displaystyle \lVert \,A\,\rVert _{2}}
on matrices
A
{\displaystyle A}
is an example of an induced norm. An induced norm is for a vector norm
‖
x
‖
b
{\displaystyle \lVert \,x\,\rVert _{b}}
defined by
‖
A
‖
b
=
max
‖
x
‖
b
=
1
‖
A
x
‖
b
{\displaystyle \lVert \,A\,\rVert _{b}\;=\;{\underset {\lVert \,x\,\rVert _{b}\;=\;1}{\max }}\;\lVert \,A\,x\,\rVert _{b}}
.
This could cause the same subscript notation to be used fot two different norms, sometimes.
Positive definite matrices
edit
A
n
×
n
{\displaystyle n\times n}
matrix
A
{\displaystyle A}
is said to be positive definite if for any vector
x
{\displaystyle x}
x
T
A
x
≥
α
x
T
x
{\displaystyle x^{T}A\,x\;\geq \;\alpha \,x^{T}x}
for some positive constant
α
{\displaystyle \alpha }
,
not depending on
x
{\displaystyle x}
.
The property of being positive definite insures the numerical stability of a variety of common numerical techniques used to solve the equation
A
x
=
y
{\displaystyle A\,x\;=\;y}
.
Taking
x
=
A
−
1
y
{\displaystyle x\;=\;A^{-1}y}
then
(
A
−
1
y
)
T
A
(
A
−
1
y
)
≥
α
(
A
−
1
y
)
T
A
−
1
y
{\displaystyle (A^{-1}y)^{T}A\,(A^{-1}y)\;\geq \;\alpha \,(A^{-1}y)^{T}A^{-1}y}
.
so that
(
A
−
1
y
)
T
y
≥
α
‖
A
−
1
y
‖
2
2
{\displaystyle (A^{-1}y)^{T}y\;\geq \;\alpha \,\lVert A^{-1}y\rVert _{2}^{2}}
and
α
‖
A
−
1
y
‖
2
2
≤
‖
A
−
1
y
‖
2
‖
y
‖
2
{\displaystyle \alpha \,\lVert A^{-1}y\rVert _{2}^{2}\;\leq \;\lVert A^{-1}y\rVert _{2}\,\lVert y\rVert _{2}}
.
This gives
α
‖
A
−
1
y
‖
2
≤
‖
y
‖
2
{\displaystyle \alpha \,\lVert A^{-1}y\rVert _{2}\;\leq \;\lVert y\rVert _{2}}
and
‖
A
−
1
‖
2
≤
α
−
1
{\displaystyle \lVert A^{-1}\rVert _{2}\;\leq \;\alpha ^{-1}}
.
Consistency of Norms
edit
A matrix norm
‖
⋅
‖
M
{\displaystyle \lVert \,\cdot \,\rVert _{M}}
and a
vector norm
‖
⋅
‖
V
{\displaystyle \lVert \,\cdot \,\rVert _{V}}
are said
to be consistent when
‖
A
x
‖
M
≤
‖
A
‖
M
‖
x
‖
V
{\displaystyle \lVert \,A\,x\,\rVert _{M}\;\leq \;\lVert \,A\,\rVert _{M}\,\lVert \,x\,\rVert _{V}}
.
When
‖
⋅
‖
M
{\displaystyle \lVert \,\cdot \,\rVert _{M}}
is the matrix norm induced by the vector norm
‖
⋅
‖
V
{\displaystyle \lVert \,\cdot \,\rVert _{V}}
then the two norms will be consistent .
When the two norms are not consistent there will still be a
positive constant
α
{\displaystyle \alpha }
such that
‖
A
x
‖
M
≤
α
‖
A
‖
M
‖
x
‖
V
{\displaystyle \lVert \,A\,x\,\rVert _{M}\;\leq \;\alpha \,\lVert \,A\,\rVert _{M}\,\lVert \,x\,\rVert _{V}}
.
Finite Difference Operators
edit
approximation of a first derivative
edit
The defition of the derivative of a function gives the first and simplest
finite difference .
f
′
(
x
0
)
=
lim
x
1
→
x
0
f
(
x
1
)
−
f
(
x
0
)
x
1
−
x
0
or
f
′
(
x
0
)
=
lim
h
→
0
f
(
x
0
+
h
)
−
f
(
x
0
)
h
{\displaystyle f^{\prime }(x_{0})\;=\;\lim _{x_{1}\to x_{0}}{\frac {f(x_{1})-f(x_{0})}{x_{1}-x_{0}}}\quad {\text{or}}\quad f^{\prime }(x_{0})\;=\;\lim _{h\to 0}{\frac {f(x_{0}+h)-f(x_{0})}{h}}}
.
So the finite difference
d
h
d
h
x
f
(
x
)
=
f
(
x
+
h
)
−
f
(
x
)
h
=
h
−
1
(
f
(
x
+
h
)
−
f
(
x
)
)
{\displaystyle {\frac {d_{h}}{d_{h}x}}\,f(x)\;=\;{\frac {f(x+h)-f(x)}{h}}\;=\;h^{-1}\,(f(x+h)-f(x))}
can be defined. It is an approximation to
f
′
(
x
)
{\displaystyle f^{\prime }(x)}
when
h
{\displaystyle h}
is near
0
{\displaystyle 0}
.
The finite difference approximation
d
h
n
d
h
x
n
f
(
x
)
{\displaystyle {\frac {d_{h}^{\,n}}{d_{h}x^{n}}}\,f(x)}
for
f
(
n
)
(
x
)
{\displaystyle f^{(\,n)}(x)}
is said to be of order
k
{\displaystyle k}
, if there exists
M
>
0
{\displaystyle M\;>\;0}
such
that
|
d
h
n
d
h
x
n
f
(
x
)
−
f
(
n
)
(
x
)
|
≤
M
h
k
{\displaystyle \left\vert {\frac {d_{h}^{\,n}}{d_{h}x^{n}}}\,f(x)-f^{(\,n)}(x)\right\vert \;\leq \;M\,h^{k}}
,
when
h
{\displaystyle h}
is near
0
{\displaystyle 0}
.
For practical reasons the order of a finite difference will be
described under the assumption that
f
(
x
)
{\displaystyle f(x)}
is sufficiently smooth so that it's Taylor's expansion up to
some order exists. For example, if
f
(
x
+
h
)
=
f
(
x
)
+
f
′
(
x
)
h
+
1
2
f
′
′
(
z
h
)
h
2
{\displaystyle f(x+h)\;=\;f(x)+f^{\prime }(x)\,h+{\tfrac {1}{2}}\,f^{\prime \prime }(z_{h})\,h^{2}}
then
f
(
x
+
h
)
−
f
(
x
)
h
=
f
′
(
x
)
+
1
2
f
′
′
(
z
h
)
h
{\displaystyle {\frac {f(x+h)-f(x)}{h}}\;=\;f^{\prime }(x)+{\tfrac {1}{2}}\,f^{\prime \prime }(z_{h})\,h}
so that
d
h
d
h
x
f
(
x
)
−
f
′
(
x
)
=
1
2
f
′
′
(
z
h
)
h
{\displaystyle {\frac {d_{h}}{d_{h}x}}\,f(x)-f^{\prime }(x)\;=\;{\tfrac {1}{2}}\,f^{\prime \prime }(z_{h})\,h}
,
meaning that the order of the approximation of
f
′
(
x
)
{\displaystyle f^{\prime }(x)}
by
d
h
d
h
x
f
(
x
)
{\displaystyle {\frac {d_{h}}{d_{h}x}}\,f(x)}
is
1
{\displaystyle 1}
.
The finite difference so far defined is a 2-point
operator , since it requires 2 evaluations of
f
(
x
)
{\displaystyle f(x)}
. If
f
(
x
+
h
)
=
f
(
x
)
+
f
′
(
x
)
h
+
1
2
f
′
′
(
x
)
h
2
+
1
6
f
′
′
′
(
z
h
)
h
3
{\displaystyle f(x+h)\;=\;f(x)+f^{\prime }(x)\,h+{\tfrac {1}{2}}\,f^{\prime \prime }(x)\,h^{2}+{\tfrac {1}{6}}\,f^{\prime \prime \prime }(z_{h})\,h^{3}}
then another 2-point operator
d
h
d
h
x
f
(
x
)
=
f
(
x
+
h
)
−
f
(
x
−
h
)
2
h
=
(
2
h
)
−
1
(
f
(
x
+
h
)
−
f
(
x
−
h
)
)
{\displaystyle {\frac {d_{h}}{d_{h}x}}\,f(x)\;=\;{\frac {f(x+h)-f(x-h)}{2\,h}}\;=\;(2\,h)^{-1}\,(f(x+h)-f(x-h))}
can be defined. Since
f
(
x
+
h
)
−
f
(
x
−
h
)
2
h
=
f
′
(
x
)
+
1
2
(
1
6
f
′
′
′
(
z
h
)
+
1
6
f
′
′
′
(
z
−
h
)
)
h
2
{\displaystyle {\frac {f(x+h)-f(x-h)}{2\,h}}\;=\;f^{\prime }(x)+{\tfrac {1}{2}}\,({\tfrac {1}{6}}\,f^{\prime \prime \prime }(z_{h})+{\tfrac {1}{6}}\,f^{\prime \prime \prime }(z_{-h}))\,h^{2}}
,
this
d
h
d
h
x
f
(
x
)
{\displaystyle {\frac {d_{h}}{d_{h}x}}\,f(x)}
is of order
2 , and is referred to as a centered difference operator. Centered difference operators are usually one
order of accuracy higher than un-centered operators for the same number
of points.
More generally, for
m
{\displaystyle m}
points
x
+
α
1
h
,
x
+
α
2
h
,
…
,
x
+
α
m
h
{\displaystyle x+\alpha _{1}\,h\,,\;x+\alpha _{2}\,h\,,\;\ldots \;,\;x+\alpha _{m}\,h}
a finite difference operator
d
h
d
h
x
f
(
x
)
=
h
−
1
(
a
1
f
(
x
+
α
1
h
)
+
a
2
f
(
x
+
α
2
h
)
+
…
+
a
m
f
(
x
+
α
m
h
)
)
{\displaystyle {\frac {d_{h}}{d_{h}x}}\,f(x)\;=\;h^{-1}\,(a_{1}\,f(x+\alpha _{1}\,h)+a_{2}\,f(x+\alpha _{2}\,h)+\;\ldots \;+a_{m}\,f(x+\alpha _{m}\,h))}
is usually defined by choosing the coefficients
a
1
,
a
2
,
…
,
a
m
{\displaystyle a_{1}\,,\;a_{2}\,,\;\ldots ,\;a_{m}}
so that
d
h
d
h
x
f
(
x
)
{\displaystyle {\frac {d_{h}}{d_{h}x}}\,f(x)}
has as high of an
order of accuracy as possible. Considering
f
(
x
+
h
)
=
f
(
x
)
+
f
′
(
x
)
h
+
1
2
f
′
′
(
x
)
h
2
+
1
6
f
′
′
′
(
x
)
h
3
+
…
+
1
(
m
−
1
)
!
f
(
m
−
1
)
(
x
)
h
m
−
1
+
1
m
!
f
(
m
)
(
z
h
)
h
m
{\displaystyle {\begin{aligned}f(x+h)\;&=\;f(x)+f^{\prime }(x)\,h+{\tfrac {1}{2}}\,f^{\prime \prime }(x)\,h^{2}+{\tfrac {1}{6}}\,f^{\prime \prime \prime }(x)\,h^{3}\\&+\;\ldots \;+{\tfrac {1}{(m-1)!}}\,f^{(m-1)}(x)\,h^{m-1}+{\tfrac {1}{m!}}\,f^{(m)}(z_{h})\,h^{m}\\\end{aligned}}}
.
Then
d
h
d
h
x
f
(
x
)
=
h
−
1
(
c
1
f
(
x
)
+
c
2
f
′
(
x
)
h
+
1
2
c
3
f
′
′
(
x
)
h
2
+
1
6
c
4
f
′
′
′
(
x
)
h
3
+
…
+
1
(
m
−
1
)
!
c
m
f
(
m
−
1
)
(
x
)
h
m
−
1
+
1
m
!
R
m
h
m
)
{\displaystyle {\begin{aligned}{\frac {d_{h}}{d_{h}x}}\,f(x)\;&=\;h^{-1}\,(c_{1}\,f(x)+c_{2}\,f^{\prime }(x)\,h+{\tfrac {1}{2}}\,c_{3}\,f^{\prime \prime }(x)\,h^{2}+{\tfrac {1}{6}}\,c_{4}\,f^{\prime \prime \prime }(x)\,h^{3}\\&+\;\ldots \;+{\tfrac {1}{(m-1)!}}\,c_{m}\,f^{(m-1)}(x)\,h^{m-1}+{\tfrac {1}{m!}}\,R_{m}\,h^{m})\\\end{aligned}}}
.
where the
c
1
,
c
2
,
…
,
c
m
{\displaystyle c_{1}\,,\;c_{2}\,,\;\ldots ,\;c_{m}}
are the
right hand side of the Vandermonde system
[
1
1
⋯
1
1
α
1
α
2
⋯
α
m
−
1
α
m
α
1
2
α
2
2
⋯
α
m
−
1
2
α
m
2
⋮
⋮
⋯
⋮
⋮
α
1
m
−
2
α
2
m
−
2
⋯
α
m
−
1
m
−
2
α
m
m
−
2
α
1
m
−
1
α
2
m
−
1
⋯
α
m
−
1
m
−
1
α
m
m
−
1
]
[
a
1
a
2
a
3
⋮
a
m
−
1
a
m
]
=
[
c
1
c
2
c
3
⋮
c
m
−
1
c
m
]
{\displaystyle {\begin{bmatrix}1&1&\cdots &1&1\\\alpha _{1}&\alpha _{2}&\cdots &\alpha _{m-1}&\alpha _{m}\\\alpha _{1}^{2}&\alpha _{2}^{2}&\cdots &\alpha _{m-1}^{2}&\alpha _{m}^{2}\\\vdots &\vdots &\cdots &\vdots &\vdots \\\alpha _{1}^{m-2}&\alpha _{2}^{m-2}&\cdots &\alpha _{m-1}^{m-2}&\alpha _{m}^{m-2}\\\alpha _{1}^{m-1}&\alpha _{2}^{m-1}&\cdots &\alpha _{m-1}^{m-1}&\alpha _{m}^{m-1}\\\end{bmatrix}}{\begin{bmatrix}a_{1}\\a_{2}\\a_{3}\\\vdots \\a_{m-1}\\a_{m}\\\end{bmatrix}}\quad =\quad {\begin{bmatrix}c_{1}\\c_{2}\\c_{3}\\\vdots \\c_{m-1}\\c_{m}\\\end{bmatrix}}}
and
R
m
=
a
1
α
1
m
f
(
m
)
(
z
α
1
h
)
+
a
2
α
2
m
f
(
m
)
(
z
α
2
h
)
+
a
3
α
3
m
f
(
m
)
(
z
α
3
h
)
+
…
+
a
m
−
1
α
m
−
1
m
f
(
m
)
(
z
α
m
−
1
h
)
+
a
m
α
m
m
f
(
m
)
(
z
α
m
h
)
{\displaystyle {\begin{aligned}R_{m}\;=&\;a_{1}\,\alpha _{1}^{m}\,f^{(m)}(z_{\,\alpha _{1}\,h})+a_{2}\,\alpha _{2}^{m}\,f^{(m)}(z_{\,\alpha _{2}\,h})+a_{3}\,\alpha _{3}^{m}\,f^{(m)}(z_{\,\alpha _{3}\,h})\\&+\;\ldots \;+a_{m-1}\,\alpha _{m-1}^{m}\,f^{(m)}(z_{\,\alpha _{m-1}\,h})+a_{m}\,\alpha _{m}^{m}\,f^{(m)}(z_{\,\alpha _{m}\,h})\\\end{aligned}}}
.
When the
a
i
's
{\displaystyle a_{i}\,{\text{'s}}}
are chosen so that
c
1
=
0
,
c
2
=
1
,
c
3
=
…
=
c
m
=
0
{\displaystyle c_{1}\;=\;0\,,\;\;c_{2}\;=\;1\,,\;\;c_{3}\;=\;\ldots \;=\;c_{m}\;=\;0}
then
d
h
d
h
x
f
(
x
)
=
f
′
(
x
)
+
1
m
!
R
m
h
m
−
1
{\displaystyle {\frac {d_{h}}{d_{h}x}}\,f(x)\;=\;f^{\prime }(x)+{\tfrac {1}{m!}}\,R_{m}\,h^{m-1}}
.
so that the operator is of order
m
−
1
{\displaystyle m-1}
.
At the end of the section a table for the first several values of
m
{\displaystyle m}
, the number of points, will be provided. The discussion
will move on to the approximation of the second derivative .
approximation of a second derivative
edit
The definition of the second derivative of a function
f
′
′
(
x
)
=
lim
h
→
0
f
′
(
x
+
h
)
−
f
′
(
x
)
h
{\displaystyle f^{\prime \prime }(x)\;=\;\lim _{h\to 0}{\frac {f^{\prime }(x+h)-f^{\prime }(x)}{h}}}
.
used together with the finite difference approximation for the first derivative
d
h
d
h
x
f
(
x
)
=
f
(
x
+
h
)
−
f
(
x
)
h
=
h
−
1
(
f
(
x
+
h
)
−
f
(
x
)
)
{\displaystyle {\frac {d_{h}}{d_{h}x}}\,f(x)\;=\;{\frac {f(x+h)-f(x)}{h}}\;=\;h^{-1}\,(f(x+h)-f(x))}
gives the finite difference
d
h
2
d
h
x
2
f
(
x
)
=
h
−
1
(
h
−
1
(
f
(
x
+
2
h
)
−
f
(
x
+
h
)
)
−
h
−
1
(
f
(
x
+
h
)
−
f
(
x
)
)
)
=
h
−
2
(
f
(
x
+
2
h
)
−
2
f
(
x
+
h
)
+
f
(
x
)
)
)
{\displaystyle {\begin{aligned}{\frac {d_{h}^{2}}{d_{h}x^{2}}}\,f(x)\;=&\;h^{-1}\,{\big (}h^{-1}\,(f(x+2\,h)-f(x+h))-h^{-1}\,(f(x+h)-f(x)){\big )}\\=&\;h^{-2}\,(f(x+2\,h)-2\,f(x+h)+f(x)))\\\end{aligned}}}
In view of
f
(
x
+
h
)
=
f
(
x
)
+
f
′
(
x
)
h
+
1
2
f
′
′
(
x
)
h
2
+
1
6
f
′
′
′
(
z
h
)
h
3
{\displaystyle f(x+h)\;=\;f(x)+f^{\prime }(x)\,h+{\tfrac {1}{2}}\,f^{\prime \prime }(x)\,h^{2}+{\tfrac {1}{6}}\,f^{\prime \prime \prime }(z_{h})\,h^{3}}
for the operator just defined
d
h
2
d
h
x
2
f
(
x
)
=
f
′
′
(
x
)
+
(
4
3
f
′
′
′
(
z
2
h
)
−
1
3
f
′
′
′
(
z
h
)
)
h
{\displaystyle {\frac {d_{h}^{2}}{d_{h}x^{2}}}\,f(x)\;=\;f^{\prime \prime }(x)+({\tfrac {4}{3}}\,f^{\prime \prime \prime }(z_{\,2\,h})-{\tfrac {1}{3}}\,f^{\prime \prime \prime }(z_{h}))\,h}
.
If instead, the difference operator
d
h
d
h
x
f
(
x
)
=
(
2
h
)
−
1
(
f
(
x
+
h
)
−
f
(
x
−
h
)
)
{\displaystyle {\frac {d_{h}}{d_{h}x}}\,f(x)\;=\;(2\,h)^{-1}\,(f(x+h)-f(x-h))}
is used
d
h
2
d
h
x
2
f
(
x
)
=
h
−
1
(
(
2
h
)
−
1
(
f
(
x
+
2
h
)
−
f
(
x
)
)
−
(
2
h
)
−
1
(
f
(
x
+
h
)
−
f
(
x
−
h
)
)
)
=
1
2
h
−
2
(
f
(
x
+
2
h
)
−
f
(
x
+
h
)
−
f
(
x
)
+
f
(
x
−
h
)
)
=
f
′
′
(
x
)
+
(
2
3
f
′
′
′
(
z
2
h
)
−
1
12
f
′
′
′
(
z
h
)
−
1
12
f
′
′
′
(
z
−
h
)
)
h
{\displaystyle {\begin{aligned}{\frac {d_{h}^{2}}{d_{h}x^{2}}}\,f(x)\;=&\;h^{-1}\,{\big (}(2\,h)^{-1}\,(f(x+2\,h)-f(x))-(2\,h)^{-1}\,(f(x+h)-f(x-h)){\big )}\\=&\;{\tfrac {1}{2}}\,h^{-2}\,(f(x+2\,h)-f(x+h)-f(x)+f(x-h))\\&\;\\=&\;f^{\prime \prime }(x)+({\tfrac {2}{3}}\,f^{\prime \prime \prime }(z_{\,2\,h})-{\tfrac {1}{12}}\,f^{\prime \prime \prime }(z_{h})-{\tfrac {1}{12}}\,f^{\prime \prime \prime }(z_{-h}))\,h\\\end{aligned}}}
If the other obvious possibility is tried
d
h
2
d
h
x
2
f
(
x
)
=
h
−
1
(
h
−
1
(
f
(
x
+
h
)
−
f
(
x
)
)
−
h
−
1
(
f
(
x
)
−
f
(
x
−
h
)
)
)
=
h
−
2
(
f
(
x
+
h
)
−
2
f
(
x
)
+
f
(
x
−
h
)
)
{\displaystyle {\begin{aligned}{\frac {d_{h}^{2}}{d_{h}x^{2}}}\,f(x)\;=&\;h^{-1}\,{\big (}h^{-1}\,(f(x+h)-f(x))-h^{-1}\,(f(x)-f(x-h)){\big )}\\=&\;h^{-2}\,(f(x+h)-2\,f(x)+f(x-h))\\\end{aligned}}}
In view of
f
(
x
+
h
)
=
f
(
x
)
+
f
′
(
x
)
h
+
1
2
f
′
′
(
x
)
h
2
+
1
6
f
′
′
′
(
x
)
h
3
+
1
24
f
(
i
v
)
(
z
h
)
h
4
{\displaystyle f(x+h)\;=\;f(x)+f^{\prime }(x)\,h+{\tfrac {1}{2}}\,f^{\prime \prime }(x)\,h^{2}+{\tfrac {1}{6}}\,f^{\prime \prime \prime }(x)\,h^{3}+{\tfrac {1}{24}}\,f^{(iv)}(z_{h})\,h^{4}}
,
d
h
2
d
h
x
2
f
(
x
)
=
f
′
′
(
x
)
+
(
1
24
f
(
i
v
)
(
z
h
)
+
1
24
f
(
i
v
)
(
z
−
h
)
)
h
2
{\displaystyle {\frac {d_{h}^{2}}{d_{h}x^{2}}}\,f(x)\;=\;f^{\prime \prime }(x)+({\tfrac {1}{24}}\,f^{(iv)}(z_{h})+{\tfrac {1}{24}}\,f^{(iv)}(z_{-h}))\,h^{2}}
.
So
d
h
2
d
h
x
2
f
(
x
)
=
h
−
2
(
f
(
x
+
h
)
−
2
f
(
x
)
+
f
(
x
−
h
)
)
{\displaystyle {\frac {d_{h}^{2}}{d_{h}x^{2}}}\,f(x)\;=\;h^{-2}\,(f(x+h)-2\,f(x)+f(x-h))}
is a second order centered finite difference approximation for
f
′
′
(
x
)
{\displaystyle f^{\prime \prime }(x)}
.
The reasoning applied to the approximation of a first derivative can be used for
the second derivative with only a few modifications.
For
m
{\displaystyle m}
points
x
+
α
1
h
,
x
+
α
2
h
,
…
,
x
+
α
m
h
{\displaystyle x+\alpha _{1}\,h\,,\;x+\alpha _{2}\,h\,,\;\ldots \;,\;x+\alpha _{m}\,h}
a finite difference operator
d
h
2
d
h
x
2
f
(
x
)
=
h
−
2
(
a
1
f
(
x
+
α
1
h
)
+
a
2
f
(
x
+
α
2
h
)
+
…
+
a
m
f
(
x
+
α
m
h
)
)
{\displaystyle {\frac {d_{h}^{2}}{d_{h}x^{2}}}\,f(x)\;=\;h^{-2}\,(a_{1}\,f(x+\alpha _{1}\,h)+a_{2}\,f(x+\alpha _{2}\,h)+\;\ldots \;+a_{m}\,f(x+\alpha _{m}\,h))}
is usually defined by choosing the coefficients
a
1
,
a
2
,
…
,
a
m
{\displaystyle a_{1}\,,\;a_{2}\,,\;\ldots ,\;a_{m}}
so that
d
h
2
d
h
x
2
f
(
x
)
{\displaystyle {\frac {d_{h}^{2}}{d_{h}x^{2}}}\,f(x)}
has as high of an
order of accuracy as possible. Considering
f
(
x
+
h
)
=
f
(
x
)
+
f
′
(
x
)
h
+
1
2
f
′
′
(
x
)
h
2
+
1
6
f
′
′
′
(
x
)
h
3
+
…
+
1
(
m
−
1
)
!
f
(
m
−
1
)
(
x
)
h
m
−
1
+
1
m
!
f
(
m
)
(
z
h
)
h
m
{\displaystyle {\begin{aligned}f(x+h)\;&=\;f(x)+f^{\prime }(x)\,h+{\tfrac {1}{2}}\,f^{\prime \prime }(x)\,h^{2}+{\tfrac {1}{6}}\,f^{\prime \prime \prime }(x)\,h^{3}\\&+\;\ldots \;+{\tfrac {1}{(m-1)!}}\,f^{(m-1)}(x)\,h^{m-1}+{\tfrac {1}{m!}}\,f^{(m)}(z_{h})\,h^{m}\\\end{aligned}}}
.
Then
d
h
2
d
h
x
2
f
(
x
)
=
h
−
2
(
c
1
f
(
x
)
+
c
2
f
′
(
x
)
h
+
1
2
c
3
f
′
′
(
x
)
h
2
+
1
6
c
4
f
′
′
′
(
x
)
h
3
+
…
+
1
(
m
−
1
)
!
c
m
f
(
m
−
1
)
(
x
)
h
m
−
1
+
1
m
!
R
m
h
m
)
{\displaystyle {\begin{aligned}{\frac {d_{h}^{2}}{d_{h}x^{2}}}\,f(x)\;&=\;h^{-2}\,(c_{1}\,f(x)+c_{2}\,f^{\prime }(x)\,h+{\tfrac {1}{2}}\,c_{3}\,f^{\prime \prime }(x)\,h^{2}+{\tfrac {1}{6}}\,c_{4}\,f^{\prime \prime \prime }(x)\,h^{3}\\&+\;\ldots \;+{\tfrac {1}{(m-1)!}}\,c_{m}\,f^{(m-1)}(x)\,h^{m-1}+{\tfrac {1}{m!}}\,R_{m}\,h^{m})\\\end{aligned}}}
.
where the
c
1
,
c
2
,
…
,
c
m
{\displaystyle c_{1}\,,\;c_{2}\,,\;\ldots ,\;c_{m}}
are the
right hand side of the Vandermonde system
[
1
1
⋯
1
1
α
1
α
2
⋯
α
m
−
1
α
m
α
1
2
α
2
2
⋯
α
m
−
1
2
α
m
2
⋮
⋮
⋯
⋮
⋮
α
1
m
−
2
α
2
m
−
2
⋯
α
m
−
1
m
−
2
α
m
m
−
2
α
1
m
−
1
α
2
m
−
1
⋯
α
m
−
1
m
−
1
α
m
m
−
1
]
[
a
1
a
2
a
3
⋮
a
m
−
1
a
m
]
=
[
c
1
c
2
c
3
⋮
c
m
−
1
c
m
]
{\displaystyle {\begin{bmatrix}1&1&\cdots &1&1\\\alpha _{1}&\alpha _{2}&\cdots &\alpha _{m-1}&\alpha _{m}\\\alpha _{1}^{2}&\alpha _{2}^{2}&\cdots &\alpha _{m-1}^{2}&\alpha _{m}^{2}\\\vdots &\vdots &\cdots &\vdots &\vdots \\\alpha _{1}^{m-2}&\alpha _{2}^{m-2}&\cdots &\alpha _{m-1}^{m-2}&\alpha _{m}^{m-2}\\\alpha _{1}^{m-1}&\alpha _{2}^{m-1}&\cdots &\alpha _{m-1}^{m-1}&\alpha _{m}^{m-1}\\\end{bmatrix}}{\begin{bmatrix}a_{1}\\a_{2}\\a_{3}\\\vdots \\a_{m-1}\\a_{m}\\\end{bmatrix}}\quad =\quad {\begin{bmatrix}c_{1}\\c_{2}\\c_{3}\\\vdots \\c_{m-1}\\c_{m}\\\end{bmatrix}}}
and
R
m
=
a
1
α
1
m
f
(
m
)
(
z
α
1
h
)
+
a
2
α
2
m
f
(
m
)
(
z
α
2
h
)
+
a
3
α
3
m
f
(
m
)
(
z
α
3
h
)
+
…
+
a
m
−
1
α
m
−
1
m
f
(
m
)
(
z
α
m
−
1
h
)
+
a
m
α
m
m
f
(
m
)
(
z
α
m
h
)
{\displaystyle {\begin{aligned}R_{m}\;=&\;a_{1}\,\alpha _{1}^{m}\,f^{(m)}(z_{\,\alpha _{1}\,h})+a_{2}\,\alpha _{2}^{m}\,f^{(m)}(z_{\,\alpha _{2}\,h})+a_{3}\,\alpha _{3}^{m}\,f^{(m)}(z_{\,\alpha _{3}\,h})\\&+\;\ldots \;+a_{m-1}\,\alpha _{m-1}^{m}\,f^{(m)}(z_{\,\alpha _{m-1}\,h})+a_{m}\,\alpha _{m}^{m}\,f^{(m)}(z_{\,\alpha _{m}\,h})\\\end{aligned}}}
.
When the
a
i
's
{\displaystyle a_{i}\,{\text{'s}}}
are chosen so that
c
1
=
0
,
c
2
=
0
,
c
3
=
2
,
c
4
=
…
=
c
m
=
0
{\displaystyle c_{1}\;=\;0\,,\;\;c_{2}\;=\;0\,,\;\;c_{3}\;=\;2\,,\;\;c_{4}\;=\;\ldots \;=\;c_{m}\;=\;0}
then
d
h
2
d
h
x
2
f
(
x
)
=
f
′
′
(
x
)
+
1
m
!
R
m
h
m
−
2
{\displaystyle {\frac {d_{h}^{2}}{d_{h}x^{2}}}\,f(x)\;=\;f^{\prime \prime }(x)+{\tfrac {1}{m!}}\,R_{m}\,h^{m-2}}
.
so that the operator is of order
m
−
2
{\displaystyle m-2}
.
The effect of centering the points will be covered somewhere below.
approximation of higher derivatives
edit
Although approximations to higher derivatives can be defined recursively from
those for derivatives of lower order, the end result is the same finite difference operators. The Vandermonde type system will be used again for this purpose.
f
(
n
)
(
x
)
=
lim
h
→
0
f
(
n
−
1
)
(
x
+
h
)
−
f
(
n
−
1
)
(
x
)
h
{\displaystyle f^{(\,n)}(x)\;=\;\lim _{h\to 0}{\frac {f^{\,(n-1)}(x+h)-f^{\,(n-1)}(x)}{h}}}
.
The number of points needed to approximate
f
(
n
)
(
x
)
{\displaystyle f^{(\,n)}(x)}
by finite differences is
at least
n
+
1
{\displaystyle n+1}
.
For
m
{\displaystyle m}
points
x
+
α
1
h
,
x
+
α
2
h
,
…
,
x
+
α
m
h
{\displaystyle x+\alpha _{1}\,h\,,\;x+\alpha _{2}\,h\,,\;\ldots ,\;x+\alpha _{m}\,h}
a finite difference operator
d
h
n
d
h
x
n
f
(
x
)
=
h
−
n
(
a
1
f
(
x
+
α
1
h
)
+
a
2
f
(
x
+
α
2
h
)
+
…
+
a
m
f
(
x
+
α
m
h
)
)
{\displaystyle {\frac {d_{h}^{\,n}}{d_{h}x^{n}}}\,f(x)\;=\;h^{-n}\,(a_{1}\,f(x+\alpha _{1}\,h)+a_{2}\,f(x+\alpha _{2}\,h)+\;\ldots \;+a_{m}\,f(x+\alpha _{m}\,h))}
is usually defined by choosing the coefficients
a
1
,
a
2
,
…
,
a
m
{\displaystyle a_{1}\,,\;a_{2}\,,\;\ldots ,\;a_{m}}
so that
d
h
n
d
h
x
n
f
(
x
)
{\displaystyle {\frac {d_{h}^{\,n}}{d_{h}x^{n}}}\,f(x)}
approximates
f
(
n
)
(
x
)
{\displaystyle f^{(\,n)}(x)}
to as high of an
order of accuracy as possible. Considering
f
(
x
+
h
)
=
f
(
x
)
+
f
′
(
x
)
h
+
1
2
f
′
′
(
x
)
h
2
+
1
6
f
′
′
′
(
x
)
h
3
+
…
+
1
(
m
−
1
)
!
f
(
m
−
1
)
(
x
)
h
m
−
1
+
1
m
!
f
(
m
)
(
z
h
)
h
m
{\displaystyle {\begin{aligned}f(x+h)\;=&\;f(x)+f^{\prime }(x)\,h+{\tfrac {1}{2}}\,f^{\prime \prime }(x)\,h^{2}+{\tfrac {1}{6}}\,f^{\prime \prime \prime }(x)\,h^{3}\\&+\;\ldots \;+{\tfrac {1}{(m-1)!}}\,f^{(m-1)}(x)\,h^{m-1}+{\tfrac {1}{m!}}\,f^{(m)}(z_{h})\,h^{m}\\\end{aligned}}}
.
Then
d
h
n
d
h
x
n
f
(
x
)
=
h
−
n
(
c
1
f
(
x
)
+
c
2
f
′
(
x
)
h
+
1
2
c
3
f
′
′
(
x
)
h
2
+
1
6
c
4
f
′
′
′
(
x
)
h
3
+
…
+
1
n
!
c
n
+
1
f
(
n
)
(
x
)
h
n
+
…
+
1
(
m
−
1
)
!
c
m
f
(
m
−
1
)
(
x
)
h
m
−
1
+
1
m
!
R
m
h
m
)
{\displaystyle {\begin{aligned}&{\frac {d_{h}^{\,n}}{d_{h}x^{n}}}\,f(x)\;=\;h^{-n}\,(c_{1}\,f(x)+c_{2}\,f^{\prime }(x)\,h+{\tfrac {1}{2}}\,c_{3}\,f^{\prime \prime }(x)\,h^{2}+{\tfrac {1}{6}}\,c_{4}\,f^{\prime \prime \prime }(x)\,h^{3}+\\&\ldots +{\tfrac {1}{n!}}\,c_{n+1}\,f^{(\,n)}(x)\,h^{n}+\;\ldots \;+{\tfrac {1}{(m-1)!}}\,c_{m}\,f^{(m-1)}(x)\,h^{m-1}+{\tfrac {1}{m!}}\,R_{m}\,h^{m})\\\end{aligned}}}
.
where the
c
1
,
c
2
,
…
,
c
m
{\displaystyle c_{1}\,,\;c_{2}\,,\;\ldots ,\;c_{m}}
are the
right hand side of the Vandermonde system
[
1
1
⋯
1
1
α
1
α
2
⋯
α
m
−
1
α
m
α
1
2
α
2
2
⋯
α
m
−
1
2
α
m
2
⋮
⋮
⋯
⋮
⋮
α
1
m
−
2
α
2
m
−
2
⋯
α
m
−
1
m
−
2
α
m
m
−
2
α
1
m
−
1
α
2
m
−
1
⋯
α
m
−
1
m
−
1
α
m
m
−
1
]
[
a
1
a
2
a
3
⋮
a
m
−
1
a
m
]
=
[
c
1
c
2
c
3
⋮
c
m
−
1
c
m
]
{\displaystyle {\begin{bmatrix}1&1&\cdots &1&1\\\alpha _{1}&\alpha _{2}&\cdots &\alpha _{m-1}&\alpha _{m}\\\alpha _{1}^{2}&\alpha _{2}^{2}&\cdots &\alpha _{m-1}^{2}&\alpha _{m}^{2}\\\vdots &\vdots &\cdots &\vdots &\vdots \\\alpha _{1}^{m-2}&\alpha _{2}^{m-2}&\cdots &\alpha _{m-1}^{m-2}&\alpha _{m}^{m-2}\\\alpha _{1}^{m-1}&\alpha _{2}^{m-1}&\cdots &\alpha _{m-1}^{m-1}&\alpha _{m}^{m-1}\\\end{bmatrix}}{\begin{bmatrix}a_{1}\\a_{2}\\a_{3}\\\vdots \\a_{m-1}\\a_{m}\\\end{bmatrix}}\quad =\quad {\begin{bmatrix}c_{1}\\c_{2}\\c_{3}\\\vdots \\c_{m-1}\\c_{m}\\\end{bmatrix}}}
and
R
m
=
a
1
α
1
m
f
(
m
)
(
z
α
1
h
)
+
a
2
α
2
m
f
(
m
)
(
z
α
2
h
)
+
a
3
α
3
m
f
(
m
)
(
z
α
3
h
)
+
…
+
a
m
−
1
α
m
−
1
m
f
(
m
)
(
z
α
m
−
1
h
)
+
a
m
α
m
m
f
(
m
)
(
z
α
m
h
)
{\displaystyle {\begin{aligned}R_{m}\;=&\;a_{1}\,\alpha _{1}^{m}\,f^{(m)}(z_{\,\alpha _{1}\,h})+a_{2}\,\alpha _{2}^{m}\,f^{(m)}(z_{\,\alpha _{2}\,h})+a_{3}\,\alpha _{3}^{m}\,f^{(m)}(z_{\,\alpha _{3}\,h})\\&+\;\ldots \;+a_{m-1}\,\alpha _{m-1}^{m}\,f^{(m)}(z_{\,\alpha _{m-1}\,h})+a_{m}\,\alpha _{m}^{m}\,f^{(m)}(z_{\,\alpha _{m}\,h})\\\end{aligned}}}
.
When the
a
i
's
{\displaystyle a_{i}\,{\text{'s}}}
are chosen so that
c
n
+
1
=
n
!
,
and
c
i
=
0
,
for
i
≠
n
+
1
{\displaystyle c_{n+1}\;=\;n!\,,\;\;{\text{and}}\;\;c_{i}\;=\;0\,,\quad {\text{for}}\;\;i\;\neq \;n+1}
then
d
h
n
d
h
x
n
f
(
x
)
=
f
(
n
)
(
x
)
+
1
m
!
R
m
h
m
−
n
{\displaystyle {\frac {d_{h}^{\,n}}{d_{h}x^{n}}}\,f(x)\;=\;f^{(\,n)}(x)+{\tfrac {1}{m!}}\,R_{m}\,h^{m-n}}
.
so that the operator is of order
m
−
n
{\displaystyle m-n}
.
An alternative analysis is to require that the finite difference
operator differentiates powers of
x
{\displaystyle x}
exactly, up
to the highest power possible.
effect of the placement of points
edit
Usually the
α
i
's
{\displaystyle \alpha _{i}{\text{'s}}}
are taken to be
integer valued, since the points are intended to coincide with those
of some division of an interval or 2 or 3
dimensional domain . If these points and hence
α
i
's
{\displaystyle \alpha _{i}{\text{'s}}}
are chosen with only accuracy
in mind, then a higher accuracy of only one order can be achieved.
So start by seeing how high is the accuracy that
f
′
(
x
)
{\displaystyle f^{\prime }(x)}
can be approximated with three points .
d
h
d
h
x
f
(
x
)
=
h
−
1
(
a
1
f
(
x
+
α
1
h
)
+
a
2
f
(
x
+
α
2
h
)
+
a
3
f
(
x
+
α
3
h
)
)
{\displaystyle {\frac {d_{h}}{d_{h}x}}\,f(x)\;=\;h^{-1}\,(a_{1}\,f(x+\alpha _{1}\,h)+a_{2}\,f(x+\alpha _{2}\,h)+a_{3}\,f(x+\alpha _{3}\,h))}
Then accuracy of order 4 can not be achieved,
because it would require the solution of
[
1
1
1
α
1
α
2
α
3
α
1
2
α
2
2
α
3
2
α
1
3
α
2
3
α
3
3
α
1
4
α
2
4
α
3
4
]
[
a
1
a
2
a
3
]
=
[
0
1
0
0
0
]
{\displaystyle {\begin{bmatrix}1&1&1\\\alpha _{1}&\alpha _{2}&\alpha _{3}\\\alpha _{1}^{2}&\alpha _{2}^{2}&\alpha _{3}^{2}\\\alpha _{1}^{3}&\alpha _{2}^{3}&\alpha _{3}^{3}\\\alpha _{1}^{4}&\alpha _{2}^{4}&\alpha _{3}^{4}\\\end{bmatrix}}{\begin{bmatrix}a_{1}\\a_{2}\\a_{3}\\\end{bmatrix}}\quad =\quad {\begin{bmatrix}0\\1\\0\\0\\0\\\end{bmatrix}}}
which can not be solved since the matrix
[
α
1
2
α
2
2
α
3
2
α
1
3
α
2
3
α
3
3
α
1
4
α
2
4
α
3
4
]
{\displaystyle {\begin{bmatrix}\alpha _{1}^{2}&\alpha _{2}^{2}&\alpha _{3}^{2}\\\alpha _{1}^{3}&\alpha _{2}^{3}&\alpha _{3}^{3}\\\alpha _{1}^{4}&\alpha _{2}^{4}&\alpha _{3}^{4}\\\end{bmatrix}}}
is non-singular . The possibility of an
α
i
{\displaystyle \alpha _{i}}
being
0
{\displaystyle 0}
can be ruled out otherwise.
For accuracy of order 3
[
1
1
1
α
1
α
2
α
3
α
1
2
α
2
2
α
3
2
α
1
3
α
2
3
α
3
3
]
[
a
1
a
2
a
3
]
=
[
0
1
0
0
]
{\displaystyle {\begin{bmatrix}1&1&1\\\alpha _{1}&\alpha _{2}&\alpha _{3}\\\alpha _{1}^{2}&\alpha _{2}^{2}&\alpha _{3}^{2}\\\alpha _{1}^{3}&\alpha _{2}^{3}&\alpha _{3}^{3}\\\end{bmatrix}}{\begin{bmatrix}a_{1}\\a_{2}\\a_{3}\\\end{bmatrix}}\quad =\quad {\begin{bmatrix}0\\1\\0\\0\\\end{bmatrix}}}
So the matrix
[
1
1
1
α
1
2
α
2
2
α
3
2
α
1
3
α
2
3
α
3
3
]
{\displaystyle {\begin{bmatrix}1&1&1\\\alpha _{1}^{2}&\alpha _{2}^{2}&\alpha _{3}^{2}\\\alpha _{1}^{3}&\alpha _{2}^{3}&\alpha _{3}^{3}\\\end{bmatrix}}}
is singular and
α
1
,
α
2
,
α
3
{\displaystyle \alpha _{1}\,,\;\alpha _{2}\,,\;\alpha _{3}}
are the roots of some polynomial
p
(
α
)
=
α
3
+
b
1
α
2
+
b
0
{\displaystyle p(\alpha )\;=\;\alpha ^{3}+b_{1}\,\alpha ^{2}+b_{0}}
.
Two examples are next.
d
h
d
h
x
f
(
x
)
=
h
−
1
(
−
(
3
3
+
1
2
)
f
(
x
+
(
3
3
−
1
)
h
)
+
2
3
3
f
(
x
+
3
3
h
)
−
(
3
3
−
1
2
)
f
(
x
+
(
3
3
+
1
)
h
)
)
{\displaystyle {\frac {d_{h}}{d_{h}x}}\,f(x)\;=\;h^{-1}\,(-({\tfrac {\sqrt {3}}{3}}+{\tfrac {1}{2}})\,f(x+({\tfrac {\sqrt {3}}{3}}-1)\,h)+2\,{\tfrac {\sqrt {3}}{3}}\,f(x+{\tfrac {\sqrt {3}}{3}}\,h)-({\tfrac {\sqrt {3}}{3}}-{\tfrac {1}{2}})\,f(x+({\tfrac {\sqrt {3}}{3}}+1)\,h))}
d
h
d
h
x
f
(
x
)
=
h
−
1
(
−
9
2
f
(
x
−
1
2
h
)
+
16
3
f
(
x
+
3
4
h
)
−
5
6
f
(
x
+
3
2
h
)
)
{\displaystyle {\frac {d_{h}}{d_{h}x}}\,f(x)\;=\;h^{-1}\,(-{\tfrac {9}{2}}\,f(x-{\tfrac {1}{2}}\,h)+{\tfrac {16}{3}}\,f(x+{\tfrac {3}{4}}\,h)-{\tfrac {5}{6}}\,f(x+{\tfrac {3}{2}}\,h))}
To see what the accuracy that
f
′
′
(
x
)
{\displaystyle f^{\prime \prime }(x)}
can be approximated to with three points .
d
h
2
d
h
x
2
f
(
x
)
=
h
−
2
(
a
1
f
(
x
+
α
1
h
)
+
a
2
f
(
x
+
α
2
h
)
+
a
3
f
(
x
+
α
3
h
)
)
{\displaystyle {\frac {d_{h}^{2}}{d_{h}x^{2}}}\,f(x)\;=\;h^{-2}\,(a_{1}\,f(x+\alpha _{1}\,h)+a_{2}\,f(x+\alpha _{2}\,h)+a_{3}\,f(x+\alpha _{3}\,h))}
Then accuracy of order 3 can not be achieved,
because it would require the solution of
[
1
1
1
α
1
α
2
α
3
α
1
2
α
2
2
α
3
2
α
1
3
α
2
3
α
3
3
α
1
4
α
2
4
α
3
4
]
[
a
1
a
2
a
3
]
=
[
0
0
2
0
0
]
{\displaystyle {\begin{bmatrix}1&1&1\\\alpha _{1}&\alpha _{2}&\alpha _{3}\\\alpha _{1}^{2}&\alpha _{2}^{2}&\alpha _{3}^{2}\\\alpha _{1}^{3}&\alpha _{2}^{3}&\alpha _{3}^{3}\\\alpha _{1}^{4}&\alpha _{2}^{4}&\alpha _{3}^{4}\\\end{bmatrix}}{\begin{bmatrix}a_{1}\\a_{2}\\a_{3}\\\end{bmatrix}}\quad =\quad {\begin{bmatrix}0\\0\\2\\0\\0\\\end{bmatrix}}}
which can not be solved since the matrices
[
1
1
1
α
1
α
2
α
3
α
1
3
α
2
3
α
3
3
]
{\displaystyle {\begin{bmatrix}1&1&1\\\alpha _{1}&\alpha _{2}&\alpha _{3}\\\alpha _{1}^{3}&\alpha _{2}^{3}&\alpha _{3}^{3}\\\end{bmatrix}}}
and
[
1
1
1
α
1
α
2
α
3
α
1
4
α
2
4
α
3
4
]
{\displaystyle {\begin{bmatrix}1&1&1\\\alpha _{1}&\alpha _{2}&\alpha _{3}\\\alpha _{1}^{4}&\alpha _{2}^{4}&\alpha _{3}^{4}\\\end{bmatrix}}}
would both need to be singular .
If the matrix
[
1
1
1
α
1
α
2
α
3
α
1
3
α
2
3
α
3
3
]
{\displaystyle {\begin{bmatrix}1&1&1\\\alpha _{1}&\alpha _{2}&\alpha _{3}\\\alpha _{1}^{3}&\alpha _{2}^{3}&\alpha _{3}^{3}\\\end{bmatrix}}}
is singular , then
α
1
,
α
2
,
α
3
{\displaystyle \alpha _{1}\,,\;\alpha _{2}\,,\;\alpha _{3}}
are the roots of some polynomial
p
(
α
)
=
α
3
+
b
1
α
+
b
0
{\displaystyle p(\alpha )\;=\;\alpha ^{3}+b_{1}\,\alpha +b_{0}}
,
implying
[
α
1
4
α
2
4
α
3
4
]
=
−
b
1
[
α
1
2
α
2
2
α
3
2
]
−
b
0
[
α
1
α
2
α
3
]
{\displaystyle {\begin{bmatrix}\alpha _{1}^{4}&\alpha _{2}^{4}&\alpha _{3}^{4}\\\end{bmatrix}}\;\;=\;\;-b_{1}\,{\begin{bmatrix}\alpha _{1}^{2}&\alpha _{2}^{2}&\alpha _{3}^{2}\\\end{bmatrix}}\;-\;b_{0}\,{\begin{bmatrix}\alpha _{1}&\alpha _{2}&\alpha _{3}\\\end{bmatrix}}}
meaning that elementary row operations can transform
[
1
1
1
α
1
α
2
α
3
α
1
4
α
2
4
α
3
4
]
{\displaystyle {\begin{bmatrix}1&1&1\\\alpha _{1}&\alpha _{2}&\alpha _{3}\\\alpha _{1}^{4}&\alpha _{2}^{4}&\alpha _{3}^{4}\\\end{bmatrix}}}
to
[
1
1
1
α
1
α
2
α
3
α
1
2
α
2
2
α
3
2
]
{\displaystyle {\begin{bmatrix}1&1&1\\\alpha _{1}&\alpha _{2}&\alpha _{3}\\\alpha _{1}^{2}&\alpha _{2}^{2}&\alpha _{3}^{2}\\\end{bmatrix}}}
which is non-singular .
Conversely, if
α
1
,
α
2
,
α
3
{\displaystyle \alpha _{1}\,,\;\alpha _{2}\,,\;\alpha _{3}}
are the roots of some polynomial
p
(
α
)
=
α
3
+
b
1
α
+
b
0
{\displaystyle p(\alpha )\;=\;\alpha ^{3}+b_{1}\,\alpha +b_{0}}
, then
[
1
1
1
α
1
α
2
α
3
α
1
2
α
2
2
α
3
2
α
1
3
α
2
3
α
3
3
]
[
a
1
a
2
a
3
]
=
[
0
0
2
0
]
{\displaystyle {\begin{bmatrix}1&1&1\\\alpha _{1}&\alpha _{2}&\alpha _{3}\\\alpha _{1}^{2}&\alpha _{2}^{2}&\alpha _{3}^{2}\\\alpha _{1}^{3}&\alpha _{2}^{3}&\alpha _{3}^{3}\\\end{bmatrix}}{\begin{bmatrix}a_{1}\\a_{2}\\a_{3}\\\end{bmatrix}}\quad =\quad {\begin{bmatrix}0\\0\\2\\0\\\end{bmatrix}}}
can be solved and
f
′
′
(
x
)
{\displaystyle f^{\prime \prime }(x)}
approximated
to an order of 2 accuracy .
See how high is the accuracy that
f
′
(
x
)
{\displaystyle f^{\prime }(x)}
can be approximated with
m
{\displaystyle m}
points .
d
h
d
h
x
f
(
x
)
=
h
−
1
(
a
1
f
(
x
+
α
1
h
)
+
a
2
f
(
x
+
α
2
h
)
+
…
+
a
m
f
(
x
+
α
m
h
)
)
{\displaystyle {\frac {d_{h}}{d_{h}x}}\,f(x)\;=\;h^{-1}\,(a_{1}\,f(x+\alpha _{1}\,h)+a_{2}\,f(x+\alpha _{2}\,h)+\;\ldots \;+a_{m}\,f(x+\alpha _{m}\,h))}
Then accuracy of order
m
+
1
{\displaystyle m+1}
can not be achieved, because it would require the solution of
[
1
1
1
⋯
1
α
1
α
2
α
3
⋯
α
m
α
1
2
α
2
2
α
3
2
⋯
α
m
2
α
1
3
α
2
3
α
3
3
⋯
α
m
3
⋮
⋮
⋮
⋯
⋮
α
1
m
α
2
m
α
3
m
⋯
α
m
m
α
1
m
+
1
α
2
m
+
1
α
3
m
+
1
⋯
α
m
m
+
1
]
[
a
1
a
2
a
3
⋮
a
m
]
=
[
0
1
0
⋮
0
]
{\displaystyle {\begin{bmatrix}1&1&1&\cdots &1\\\alpha _{1}&\alpha _{2}&\alpha _{3}&\cdots &\alpha _{m}\\\alpha _{1}^{2}&\alpha _{2}^{2}&\alpha _{3}^{2}&\cdots &\alpha _{m}^{2}\\\alpha _{1}^{3}&\alpha _{2}^{3}&\alpha _{3}^{3}&\cdots &\alpha _{m}^{3}\\\vdots &\vdots &\vdots &\cdots &\vdots \\\alpha _{1}^{m}&\alpha _{2}^{m}&\alpha _{3}^{m}&\cdots &\alpha _{m}^{m}\\\alpha _{1}^{m+1}&\alpha _{2}^{m+1}&\alpha _{3}^{m+1}&\cdots &\alpha _{m}^{m+1}\\\end{bmatrix}}{\begin{bmatrix}a_{1}\\a_{2}\\a_{3}\\\vdots \\a_{m}\\\end{bmatrix}}\quad =\quad {\begin{bmatrix}0\\1\\0\\\vdots \\0\\\end{bmatrix}}}
which can not be solved since the matrix
[
α
1
2
α
2
2
α
3
2
⋯
α
m
2
α
1
3
α
2
3
α
3
3
⋯
α
m
3
⋮
⋮
⋮
⋯
⋮
α
1
m
α
2
m
α
3
m
⋯
α
m
m
α
1
m
+
1
α
2
m
+
1
α
3
m
+
1
⋯
α
m
m
+
1
]
{\displaystyle {\begin{bmatrix}\alpha _{1}^{2}&\alpha _{2}^{2}&\alpha _{3}^{2}&\cdots &\alpha _{m}^{2}\\\alpha _{1}^{3}&\alpha _{2}^{3}&\alpha _{3}^{3}&\cdots &\alpha _{m}^{3}\\\vdots &\vdots &\vdots &\cdots &\vdots \\\alpha _{1}^{m}&\alpha _{2}^{m}&\alpha _{3}^{m}&\cdots &\alpha _{m}^{m}\\\alpha _{1}^{m+1}&\alpha _{2}^{m+1}&\alpha _{3}^{m+1}&\cdots &\alpha _{m}^{m+1}\\\end{bmatrix}}}
is non-singular . The possibility of an
α
i
{\displaystyle \alpha _{i}}
being
0
{\displaystyle 0}
can be ruled out otherwise, because, for
example, if
α
1
=
0
{\displaystyle \alpha _{1}\;=\;0}
, then the non-singularity of the block
[
α
2
2
α
3
2
⋯
α
m
2
α
2
3
α
3
3
⋯
α
m
3
⋮
⋮
⋯
⋮
α
2
m
α
3
m
⋯
α
m
m
]
{\displaystyle {\begin{bmatrix}\alpha _{2}^{2}&\alpha _{3}^{2}&\cdots &\alpha _{m}^{2}\\\alpha _{2}^{3}&\alpha _{3}^{3}&\cdots &\alpha _{m}^{3}\\\vdots &\vdots &\cdots &\vdots \\\alpha _{2}^{m}&\alpha _{3}^{m}&\cdots &\alpha _{m}^{m}\\\end{bmatrix}}}
would force
a
2
=
a
3
…
=
a
m
=
0
{\displaystyle a_{2}\;=\;a_{3}\;\ldots \;=\;a_{m}\;=\;0}
.
For accuracy of order
m
{\displaystyle m}
[
1
1
1
⋯
1
α
1
α
2
α
3
⋯
α
m
α
1
2
α
2
2
α
3
2
⋯
α
m
2
α
1
3
α
2
3
α
3
3
⋯
α
m
3
⋮
⋮
⋮
⋯
⋮
α
1
m
α
2
m
α
3
m
⋯
α
m
m
]
[
a
1
a
2
a
3
⋮
a
m
]
=
[
0
1
0
⋮
0
]
{\displaystyle {\begin{bmatrix}1&1&1&\cdots &1\\\alpha _{1}&\alpha _{2}&\alpha _{3}&\cdots &\alpha _{m}\\\alpha _{1}^{2}&\alpha _{2}^{2}&\alpha _{3}^{2}&\cdots &\alpha _{m}^{2}\\\alpha _{1}^{3}&\alpha _{2}^{3}&\alpha _{3}^{3}&\cdots &\alpha _{m}^{3}\\\vdots &\vdots &\vdots &\cdots &\vdots \\\alpha _{1}^{m}&\alpha _{2}^{m}&\alpha _{3}^{m}&\cdots &\alpha _{m}^{m}\\\end{bmatrix}}{\begin{bmatrix}a_{1}\\a_{2}\\a_{3}\\\vdots \\a_{m}\\\end{bmatrix}}\quad =\quad {\begin{bmatrix}0\\1\\0\\\vdots \\0\\\end{bmatrix}}}
So the matrix
[
1
1
1
⋯
1
α
1
2
α
2
2
α
3
2
⋯
α
m
2
α
1
3
α
2
3
α
3
3
⋯
α
m
3
⋮
⋮
⋮
⋯
⋮
α
1
m
α
2
m
α
3
m
⋯
α
m
m
]
{\displaystyle {\begin{bmatrix}1&1&1&\cdots &1\\\alpha _{1}^{2}&\alpha _{2}^{2}&\alpha _{3}^{2}&\cdots &\alpha _{m}^{2}\\\alpha _{1}^{3}&\alpha _{2}^{3}&\alpha _{3}^{3}&\cdots &\alpha _{m}^{3}\\\vdots &\vdots &\vdots &\cdots &\vdots \\\alpha _{1}^{m}&\alpha _{2}^{m}&\alpha _{3}^{m}&\cdots &\alpha _{m}^{m}\\\end{bmatrix}}}
is singular and
α
1
,
α
2
,
α
3
,
…
,
α
m
{\displaystyle \alpha _{1}\,,\;\alpha _{2}\,,\;\alpha _{3}\,,\;\ldots ,\;\alpha _{m}}
are the roots of some polynomial
p
(
α
)
=
α
m
+
b
m
−
2
α
m
−
1
+
…
+
b
2
α
3
+
b
1
α
2
+
b
0
{\displaystyle p(\alpha )\;=\;\alpha ^{m}+b_{m-2}\,\alpha ^{m-1}+\ldots +b_{2}\,\alpha ^{3}+b_{1}\,\alpha ^{2}+b_{0}}
.
The progression for the second, third, ... derivatives goes as follows.
If
α
1
,
α
2
,
α
3
,
…
,
α
m
{\displaystyle \alpha _{1}\,,\;\alpha _{2}\,,\;\alpha _{3}\,,\;\ldots ,\;\alpha _{m}}
are the roots of some polynomial
p
(
α
)
=
α
m
+
b
m
−
2
α
m
−
1
+
…
+
b
2
α
3
+
b
1
α
+
b
0
{\displaystyle p(\alpha )\;=\;\alpha ^{m}+b_{m-2}\,\alpha ^{m-1}+\ldots +b_{2}\,\alpha ^{3}+b_{1}\,\alpha +b_{0}}
then the system
[
1
1
1
⋯
1
α
1
α
2
α
3
⋯
α
m
α
1
2
α
2
2
α
3
2
⋯
α
m
2
α
1
3
α
2
3
α
3
3
⋯
α
m
3
⋮
⋮
⋮
⋯
⋮
α
1
m
α
2
m
α
3
m
⋯
α
m
m
]
[
a
1
a
2
a
3
a
4
⋮
a
m
]
=
[
0
0
2
0
⋮
0
]
{\displaystyle {\begin{bmatrix}1&1&1&\cdots &1\\\alpha _{1}&\alpha _{2}&\alpha _{3}&\cdots &\alpha _{m}\\\alpha _{1}^{2}&\alpha _{2}^{2}&\alpha _{3}^{2}&\cdots &\alpha _{m}^{2}\\\alpha _{1}^{3}&\alpha _{2}^{3}&\alpha _{3}^{3}&\cdots &\alpha _{m}^{3}\\\vdots &\vdots &\vdots &\cdots &\vdots \\\alpha _{1}^{m}&\alpha _{2}^{m}&\alpha _{3}^{m}&\cdots &\alpha _{m}^{m}\\\end{bmatrix}}{\begin{bmatrix}a_{1}\\a_{2}\\a_{3}\\a_{4}\\\vdots \\a_{m}\\\end{bmatrix}}\quad =\quad {\begin{bmatrix}0\\0\\2\\0\\\vdots \\0\\\end{bmatrix}}}
can be solved, and
d
h
2
d
h
x
2
f
(
x
)
=
h
−
2
(
a
1
f
(
x
+
α
1
h
)
+
a
2
f
(
x
+
α
2
h
)
+
…
+
a
m
f
(
x
+
α
m
h
)
)
{\displaystyle {\frac {d_{h}^{2}}{d_{h}x^{2}}}\,f(x)\;=\;h^{-2}\,(a_{1}\,f(x+\alpha _{1}\,h)+a_{2}\,f(x+\alpha _{2}\,h)+\;\ldots \;+a_{m}\,f(x+\alpha _{m}\,h))}
approximates
f
′
′
(
x
)
{\displaystyle f^{\prime \prime }(x)}
to an order
of accuracy of
m
−
1
{\displaystyle m-1}
.
If
α
1
,
α
2
,
α
3
,
…
,
α
m
{\displaystyle \alpha _{1}\,,\;\alpha _{2}\,,\;\alpha _{3}\,,\;\ldots ,\;\alpha _{m}}
are the roots of some polynomial
p
(
α
)
=
α
m
+
b
m
−
2
α
m
−
1
+
…
+
b
3
α
4
+
b
2
α
2
+
b
1
α
+
b
0
{\displaystyle p(\alpha )\;=\;\alpha ^{m}+b_{m-2}\,\alpha ^{m-1}+\ldots +b_{3}\,\alpha ^{4}+b_{2}\,\alpha ^{2}+b_{1}\,\alpha +b_{0}}
then the system
[
1
1
1
⋯
1
α
1
α
2
α
3
⋯
α
m
α
1
2
α
2
2
α
3
2
⋯
α
m
2
α
1
3
α
2
3
α
3
3
⋯
α
m
3
α
1
4
α
2
4
α
3
4
⋯
α
m
4
⋮
⋮
⋮
⋯
⋮
α
1
m
α
2
m
α
3
m
⋯
α
m
m
]
[
a
1
a
2
a
3
a
4
a
5
⋮
a
m
]
=
[
0
0
0
6
0
⋮
0
]
{\displaystyle {\begin{bmatrix}1&1&1&\cdots &1\\\alpha _{1}&\alpha _{2}&\alpha _{3}&\cdots &\alpha _{m}\\\alpha _{1}^{2}&\alpha _{2}^{2}&\alpha _{3}^{2}&\cdots &\alpha _{m}^{2}\\\alpha _{1}^{3}&\alpha _{2}^{3}&\alpha _{3}^{3}&\cdots &\alpha _{m}^{3}\\\alpha _{1}^{4}&\alpha _{2}^{4}&\alpha _{3}^{4}&\cdots &\alpha _{m}^{4}\\\vdots &\vdots &\vdots &\cdots &\vdots \\\alpha _{1}^{m}&\alpha _{2}^{m}&\alpha _{3}^{m}&\cdots &\alpha _{m}^{m}\\\end{bmatrix}}{\begin{bmatrix}a_{1}\\a_{2}\\a_{3}\\a_{4}\\a_{5}\\\vdots \\a_{m}\\\end{bmatrix}}\quad =\quad {\begin{bmatrix}0\\0\\0\\6\\0\\\vdots \\0\\\end{bmatrix}}}
can be solved, and
d
h
3
d
h
x
3
f
(
x
)
=
h
−
3
(
a
1
f
(
x
+
α
1
h
)
+
a
2
f
(
x
+
α
2
h
)
+
…
+
a
m
f
(
x
+
α
m
h
)
)
{\displaystyle {\frac {d_{h}^{3}}{d_{h}x^{3}}}\,f(x)\;=\;h^{-3}\,(a_{1}\,f(x+\alpha _{1}\,h)+a_{2}\,f(x+\alpha _{2}\,h)+\;\ldots \;+a_{m}\,f(x+\alpha _{m}\,h))}
approximates
f
′
′
′
(
x
)
{\displaystyle f^{\prime \prime \prime }(x)}
to an order
of accuracy of
m
−
2
{\displaystyle m-2}
.
Now, the analysis is not quite done yet. Returning to the approximation of
f
′
′
(
x
)
{\displaystyle f^{\prime \prime }(x)}
. If for the polynomial
p
(
α
)
=
α
m
+
b
m
−
2
α
m
−
1
+
…
+
b
2
α
3
+
b
1
α
+
b
0
{\displaystyle p(\alpha )\;=\;\alpha ^{m}+b_{m-2}\,\alpha ^{m-1}+\ldots +b_{2}\,\alpha ^{3}+b_{1}\,\alpha +b_{0}}
it were that
b
1
=
0
{\displaystyle b_{1}\;=\;0}
, then the system can be solved
for one more order of accuracy. So the question arises as to whether polynomials
of the form
p
(
α
)
=
α
m
+
b
m
−
2
α
m
−
1
+
…
+
b
2
α
3
+
b
0
{\displaystyle p(\alpha )\;=\;\alpha ^{m}+b_{m-2}\,\alpha ^{m-1}+\ldots +b_{2}\,\alpha ^{3}+b_{0}}
exist that have
m
{\displaystyle m}
distinct real roots. When
m
=
3
{\displaystyle m\;=\;3}
there is not. So consider
m
=
4
{\displaystyle m\;=\;4}
.
p
(
α
)
=
α
4
+
b
2
α
3
+
b
0
{\displaystyle p(\alpha )\;=\;\alpha ^{4}+b_{2}\,\alpha ^{3}+b_{0}}
If
p
(
α
)
{\displaystyle p(\alpha )}
has 4 distinct real roots , then
p
′
(
α
)
=
4
α
3
+
3
b
2
α
2
{\displaystyle p^{\prime }(\alpha )\;=\;4\,\alpha ^{3}+3\,b_{2}\,\alpha ^{2}}
has 3 distinct real roots , which it does not. So the
order of approximation can not be improved. This is generally
the case.
Returning to the approximation of
f
′
′
′
(
x
)
{\displaystyle f^{\prime \prime \prime }(x)}
. If for the polynomial
p
(
α
)
=
α
m
+
b
m
−
2
α
m
−
1
+
…
+
b
3
α
4
+
b
2
α
2
+
b
1
α
+
b
0
{\displaystyle p(\alpha )\;=\;\alpha ^{m}+b_{m-2}\,\alpha ^{m-1}+\ldots +b_{3}\,\alpha ^{4}+b_{2}\,\alpha ^{2}+b_{1}\,\alpha +b_{0}}
it were that
b
2
=
0
{\displaystyle b_{2}\;=\;0}
, then the system can be solved
for one more order of accuracy. So the question arises as to whether polynomials
of the form
p
(
α
)
=
α
m
+
b
m
−
2
α
m
−
1
+
…
+
b
3
α
4
+
b
1
α
+
b
0
{\displaystyle p(\alpha )\;=\;\alpha ^{m}+b_{m-2}\,\alpha ^{m-1}+\ldots +b_{3}\,\alpha ^{4}+b_{1}\,\alpha +b_{0}}
exist that have
m
{\displaystyle m}
distinct real roots.
If
p
(
α
)
{\displaystyle p(\alpha )}
has
m
{\displaystyle m}
distinct real roots , then
p
′
′
(
α
)
=
m
(
m
−
1
)
α
m
−
2
+
(
m
−
1
)
(
m
−
2
)
b
m
−
2
α
m
−
3
+
…
+
12
b
3
α
2
{\displaystyle p^{\prime \prime }(\alpha )\;=\;m(m-1)\,\alpha ^{m-2}+(m-1)(m-2)\,b_{m-2}\,\alpha ^{m-3}+\ldots +12\,b_{3}\,\alpha ^{2}}
has
m
−
2
{\displaystyle m-2}
distinct real roots , which it does not. So the order of approximation can not be improved.
For functions of a complex variable using roots of unity , for example, may obtain higher orders of approximation, since complex roots are allowed.
centered difference operators
edit
For
m
{\displaystyle m}
points
x
+
α
1
h
,
x
+
α
2
h
,
…
,
x
+
α
m
h
{\displaystyle x+\alpha _{1}\,h\,,\;x+\alpha _{2}\,h\,,\;\ldots ,\;x+\alpha _{m}\,h}
a finite difference operator
d
h
n
d
h
x
n
f
(
x
)
=
h
−
n
(
a
1
f
(
x
+
α
1
h
)
+
a
2
f
(
x
+
α
2
h
)
+
…
+
a
m
f
(
x
+
α
m
h
)
)
{\displaystyle {\frac {d_{h}^{\,n}}{d_{h}x^{n}}}\,f(x)\;=\;h^{-n}\,(a_{1}\,f(x+\alpha _{1}\,h)+a_{2}\,f(x+\alpha _{2}\,h)+\;\ldots \;+a_{m}\,f(x+\alpha _{m}\,h))}
is said to be centered when the points are symmetrically placed about
x
{\displaystyle x}
.
α
i
=
−
α
m
−
i
+
1
for
i
=
1
,
2
,
…
,
[
m
/
2
]
{\displaystyle \alpha _{i}\;=\;-\alpha _{m-i+1}\quad {\text{for}}\;\;i\;=\;1\,,\;2\,,\;\ldots ,\;\left[m\,/\,2\right]}
When
m
{\displaystyle m}
is odd
α
[
m
/
2
]
+
1
=
0
{\displaystyle \alpha _{\left[m\,/\,2\right]+1}\;=\;0}
.
To find the centered difference operators , consider
f
(
x
+
h
)
=
f
(
x
)
+
f
′
(
x
)
h
+
1
2
f
′
′
(
x
)
h
2
+
1
6
f
′
′
′
(
x
)
h
3
+
…
+
1
m
!
f
(
m
)
(
x
)
h
m
+
1
(
m
+
1
)
!
f
(
m
+
1
)
(
z
h
)
h
m
+
1
{\displaystyle {\begin{aligned}f(x+h)\;&=\;f(x)+f^{\prime }(x)\,h+{\tfrac {1}{2}}\,f^{\prime \prime }(x)\,h^{2}+{\tfrac {1}{6}}\,f^{\prime \prime \prime }(x)\,h^{3}\\&+\;\ldots \;+{\tfrac {1}{m!}}\,f^{(m)}(x)\,h^{m}+{\tfrac {1}{(m+1)!}}\,f^{(m+1)}(z_{h})\,h^{m+1}\\\end{aligned}}}
.
Then
d
h
n
d
h
x
n
f
(
x
)
=
h
−
n
(
c
1
f
(
x
)
+
c
2
f
′
(
x
)
h
+
1
2
c
3
f
′
′
(
x
)
h
2
+
1
6
c
4
f
′
′
′
(
x
)
h
3
+
…
+
1
(
m
−
1
)
!
c
m
f
(
m
−
1
)
(
x
)
h
m
−
1
+
1
m
!
c
m
+
1
f
(
m
)
(
x
)
h
m
+
1
(
m
+
1
)
!
R
m
+
1
h
m
+
1
)
{\displaystyle {\begin{aligned}&{\frac {d_{h}^{n}}{d_{h}x^{n}}}\,f(x)\;=\;h^{-n}\,(c_{1}\,f(x)+c_{2}\,f^{\prime }(x)\,h+{\tfrac {1}{2}}\,c_{3}\,f^{\prime \prime }(x)\,h^{2}+{\tfrac {1}{6}}\,c_{4}\,f^{\prime \prime \prime }(x)\,h^{3}\\&+\;\ldots \;+{\tfrac {1}{(m-1)!}}\,c_{m}\,f^{(m-1)}(x)\,h^{m-1}+{\tfrac {1}{m!}}\,c_{m+1}f^{(m)}(x)\,h^{m}+{\tfrac {1}{(m+1)!}}\,R_{m+1}\,h^{m+1})\\\end{aligned}}}
.
where the
c
1
,
c
2
,
…
,
c
m
,
c
m
+
1
{\displaystyle c_{1}\,,\;c_{2}\,,\;\ldots ,\;c_{m}\,,\;c_{m+1}}
are the
right hand side of the over-determined system
[
1
1
⋯
1
1
α
1
α
2
⋯
α
m
−
1
α
m
α
1
2
α
2
2
⋯
α
m
−
1
2
α
m
2
⋮
⋮
⋯
⋮
⋮
α
1
m
−
2
α
2
m
−
2
⋯
α
m
−
1
m
−
2
α
m
m
−
2
α
1
m
−
1
α
2
m
−
1
⋯
α
m
−
1
m
−
1
α
m
m
−
1
α
1
m
α
2
m
⋯
α
m
−
1
m
α
m
m
]
[
a
1
a
2
a
3
⋮
a
m
−
1
a
m
]
=
[
c
1
c
2
c
3
⋮
c
m
−
1
c
m
c
m
+
1
]
{\displaystyle {\begin{bmatrix}1&1&\cdots &1&1\\\alpha _{1}&\alpha _{2}&\cdots &\alpha _{m-1}&\alpha _{m}\\\alpha _{1}^{2}&\alpha _{2}^{2}&\cdots &\alpha _{m-1}^{2}&\alpha _{m}^{2}\\\vdots &\vdots &\cdots &\vdots &\vdots \\\alpha _{1}^{m-2}&\alpha _{2}^{m-2}&\cdots &\alpha _{m-1}^{m-2}&\alpha _{m}^{m-2}\\\alpha _{1}^{m-1}&\alpha _{2}^{m-1}&\cdots &\alpha _{m-1}^{m-1}&\alpha _{m}^{m-1}\\\alpha _{1}^{m}&\alpha _{2}^{m}&\cdots &\alpha _{m-1}^{m}&\alpha _{m}^{m}\\\end{bmatrix}}{\begin{bmatrix}a_{1}\\a_{2}\\a_{3}\\\vdots \\a_{m-1}\\a_{m}\\\end{bmatrix}}\quad =\quad {\begin{bmatrix}c_{1}\\c_{2}\\c_{3}\\\vdots \\c_{m-1}\\c_{m}\\c_{m+1}\\\end{bmatrix}}}
and
R
m
+
1
=
a
1
α
1
m
+
1
f
(
m
+
1
)
(
z
α
1
h
)
+
a
2
α
2
m
+
1
f
(
m
+
1
)
(
z
α
2
h
)
+
a
3
α
3
m
+
1
f
(
m
+
1
)
(
z
α
3
h
)
+
…
+
a
m
−
1
α
m
−
1
m
+
1
f
(
m
+
1
)
(
z
α
m
−
1
h
)
+
a
m
α
m
m
+
1
f
(
m
+
1
)
(
z
α
m
h
)
{\displaystyle {\begin{aligned}R_{m+1}\;=&\;a_{1}\,\alpha _{1}^{m+1}\,f^{(m+1)}(z_{\,\alpha _{1}\,h})+a_{2}\,\alpha _{2}^{m+1}\,f^{(m+1)}(z_{\,\alpha _{2}\,h})+a_{3}\,\alpha _{3}^{m+1}\,f^{(m+1)}(z_{\,\alpha _{3}\,h})\\&+\;\ldots \;+a_{m-1}\,\alpha _{m-1}^{m+1}\,f^{(m+1)}(z_{\,\alpha _{m-1}\,h})+a_{m}\,\alpha _{m}^{m+1}\,f^{(m+1)}(z_{\,\alpha _{m}\,h})\\\end{aligned}}}
.
When the
a
i
's
{\displaystyle a_{i}\,{\text{'s}}}
are chosen so that
c
n
+
1
=
n
!
,
c
i
=
0
,
for
i
≠
n
+
1
{\displaystyle c_{n+1}\;=\;n!\,,\;\;c_{i}\;=\;0\,,\;\;{\text{for}}\;\;i\;\neq \;n+1}
then
d
h
n
d
h
x
n
f
(
x
)
=
f
(
n
)
(
x
)
+
1
(
m
+
1
)
!
R
m
+
1
h
m
−
n
+
1
{\displaystyle {\frac {d_{h}^{n}}{d_{h}x^{n}}}\,f(x)\;=\;f^{(n)}(x)+{\tfrac {1}{(m+1)!}}\,R_{m+1}\,h^{m-n+1}}
.
so that the operator is of order
m
−
n
+
1
{\displaystyle m-n+1}
.
Since, for the centered case, the system is over-determined , some restriction is needed for the system to have a solution. A solution occurs when the
α
1
,
α
2
,
…
,
α
m
{\displaystyle \alpha _{1},\;\alpha _{2},\ldots ,\alpha _{m}}
are the roots of a
polynomial
p
(
α
)
=
α
m
+
b
m
−
1
α
m
−
1
+
…
+
b
2
α
2
+
b
1
α
+
b
0
{\displaystyle p(\alpha )\;=\;\alpha ^{m}+b_{m-1}\,\alpha ^{m-1}+\ldots +b_{2}\,\alpha ^{2}+b_{1}\,\alpha +b_{0}}
with
b
n
=
0
{\displaystyle b_{n}\;=\;0}
.
Observing that when
m
{\displaystyle m}
is even
p
(
α
)
=
∏
i
=
1
m
2
(
α
2
−
α
i
2
)
{\displaystyle p(\alpha )\;=\;\prod _{i=1}^{\tfrac {m}{2}}(\alpha ^{2}-\alpha _{i}^{2})}
and when
m
{\displaystyle m}
is odd
p
(
α
)
=
α
∏
i
=
1
[
m
2
]
(
α
2
−
α
i
2
)
{\displaystyle p(\alpha )\;=\;\alpha \,\prod _{i=1}^{\left[{\tfrac {m}{2}}\right]}(\alpha ^{2}-\alpha _{i}^{2})}
.
So when
m
{\displaystyle m}
is even
p
(
α
)
{\displaystyle p(\alpha )}
has
b
n
=
0
{\displaystyle b_{n}\;=\;0}
for all odd
n
{\displaystyle n}
and when
m
{\displaystyle m}
is odd
p
(
α
)
{\displaystyle p(\alpha )}
has
b
n
=
0
{\displaystyle b_{n}\;=\;0}
for all even
n
{\displaystyle n}
.
So a centered difference operator will achieve the one order extra of accuracy when the number of points
m
{\displaystyle m}
is even and the order of the derivative
n
{\displaystyle n}
is odd or when the number of points
m
{\displaystyle m}
is odd and the order of the derivative
n
{\displaystyle n}
is even .
Trigometric polynomials
edit
Let
p
(
x
)
=
a
0
+
∑
k
=
1
m
(
a
k
cos
(
k
π
x
)
+
b
k
sin
(
k
π
x
)
)
{\displaystyle p(x)\;=\;a_{0}+\textstyle \sum _{\,k\,=\,1}^{m}(a_{k}\,\cos(k\,\pi \,x)+b_{k}\,\sin(k\,\pi \,x))}
be trigometric polynomial defined on
−
1
≤
x
≤
1
{\displaystyle -1\;\leq \;x\;\leq \;1}
.
Define the inner product on such trigometric polynomials by
<
p
1
(
x
)
,
p
2
(
x
)
>
=
∫
−
1
1
p
1
(
x
)
p
2
(
x
)
¯
d
x
{\displaystyle <p_{1}(x)\,,\;p_{2}(x)>\;=\;\int _{-1}^{1}p_{1}(x){\overline {p_{2}(x)}}\,dx}
.
In light of the orthogonalities
<
sin
(
k
π
x
)
,
sin
(
r
π
x
)
>
=
0
,
<
cos
(
k
π
x
)
,
cos
(
r
π
x
)
>
=
0
{\displaystyle <\sin(k\,\pi \,x)\,,\;\sin(r\,\pi \,x)>\;=\;0\,,\quad <\cos(k\,\pi \,x)\,,\;\cos(r\,\pi \,x)>\;=\;0}
,
and
<
sin
(
k
π
x
)
,
cos
(
r
π
x
)
>
=
0
,
{\displaystyle <\sin(k\,\pi \,x)\,,\;\cos(r\,\pi \,x)>\;=\;0\,,}
when
k
≠
r
{\displaystyle k\;\neq \;r}
,
inner products can be calculated easily.
‖
p
(
x
)
‖
2
=
<
p
(
x
)
,
p
(
x
)
>
=
|
a
0
|
2
+
∑
k
=
1
m
(
|
a
k
|
2
+
|
b
k
|
2
)
{\displaystyle \lVert \,p(x)\,\rVert ^{2}\;=\;<p(x)\,,\;p(x)>\;=\;\left\vert a_{0}\right\vert ^{2}+\textstyle \sum _{\,k\,=\,1}^{m}(\left\vert a_{k}\right\vert ^{2}+\left\vert b_{k}\right\vert ^{2})}
.
and for
p
1
(
x
)
=
a
0
,
1
+
∑
k
=
1
m
(
a
k
,
1
cos
(
k
π
x
)
+
b
k
,
1
sin
(
k
π
x
)
)
{\displaystyle p_{1}(x)\;=\;a_{0\,,\,1}+\textstyle \sum _{\,k\,=\,1}^{m}(a_{k\,,\,1}\,\cos(k\,\pi \,x)+b_{k\,,\,1}\,\sin(k\,\pi \,x))}
p
2
(
x
)
=
a
0
,
2
+
∑
k
=
1
m
(
a
k
,
2
cos
(
k
π
x
)
+
b
k
,
2
sin
(
k
π
x
)
)
{\displaystyle p_{2}(x)\;=\;a_{0\,,\,2}+\textstyle \sum _{\,k\,=\,1}^{m}(a_{k\,,\,2}\,\cos(k\,\pi \,x)+b_{k\,,\,2}\,\sin(k\,\pi \,x))}
the inner product is given by
<
p
1
(
x
)
,
p
2
(
x
)
>
=
a
0
,
1
a
0
,
2
¯
+
∑
k
=
1
m
(
a
k
,
1
a
k
,
2
¯
+
b
k
,
1
b
k
,
2
¯
)
{\displaystyle <p_{1}(x)\,,\;p_{2}(x)>\;=\;a_{0\,,\,1}\,{\overline {a_{0\,,\,2}}}+\textstyle \sum _{\,k\,=\,1}^{m}(a_{k\,,\,1}\,{\overline {a_{k\,,\,2}}}+b_{k\,,\,1}\,{\overline {b_{k\,,\,2}}})}
.
Definition of a shift operator
edit
Define the shift operator
(
s
f
t
)
h
{\displaystyle (sft)_{h}}
on
p
(
x
)
{\displaystyle p(x)}
by
(
s
f
t
)
h
p
(
x
)
=
p
(
x
−
h
)
=
a
0
+
∑
k
=
1
m
(
a
k
cos
(
k
π
(
x
−
h
)
)
+
b
k
sin
(
k
π
(
x
−
h
)
)
)
{\displaystyle (sft)_{h}\,p(x)\;=\;p(x-h)\;=\;a_{0}+\textstyle \sum _{\,k\,=\,1}^{m}(a_{k}\,\cos(k\,\pi \,(x-h))+b_{k}\,\sin(k\,\pi \,(x-h)))}
.
Since
sin
(
k
π
(
x
−
h
)
)
=
cos
(
k
π
h
)
sin
(
k
π
x
)
−
sin
(
k
π
h
)
cos
(
k
π
x
)
{\displaystyle \sin(k\,\pi (x-h))\;=\;\cos(k\,\pi \,h)\sin(k\,\pi \,x)-\sin(k\,\pi \,h)\cos(k\,\pi \,x)}
and
cos
(
k
π
(
x
−
h
)
)
=
cos
(
k
π
h
)
cos
(
k
π
x
)
+
sin
(
k
π
h
)
sin
(
k
π
x
)
{\displaystyle \cos(k\,\pi (x-h))\;=\;\cos(k\,\pi \,h)\cos(k\,\pi \,x)+\sin(k\,\pi \,h)\sin(k\,\pi \,x)}
,
so that
(
s
f
t
)
h
p
(
x
)
=
a
0
+
∑
k
=
1
m
(
(
a
k
cos
(
k
π
h
)
−
b
k
sin
(
k
π
h
)
)
cos
(
k
π
x
)
+
(
a
k
sin
(
k
π
h
)
+
b
k
cos
(
k
π
h
)
)
sin
(
k
π
x
)
)
{\displaystyle {\begin{aligned}(sft)_{h}p(x)\;=\;a_{0}+\textstyle \sum _{\,k\,=\,1}^{m}&{\big (}(a_{k}\,\cos(k\,\pi \,h)-b_{k}\,\sin(k\,\pi \,h))\,\cos(k\,\pi \,x)\\&+(a_{k}\,\sin(k\,\pi \,h)+b_{k}\,\cos(k\,\pi \,h))\,\sin(k\,\pi \,x){\big )}\\\end{aligned}}}
.
Approximation by trigometric polynomials
edit
Let
f
(
x
)
{\displaystyle f(x)}
be a function defined on and periodic with respect to the interval
−
1
≤
x
≤
1
{\displaystyle -1\;\leq \;x\;\leq \;1}
. That is
f
(
x
+
2
)
=
f
(
x
)
{\displaystyle f(x+2)\;=\;f(x)}
.
The
m
th
{\displaystyle m\,{\text{th}}}
degree trigometric polynomial approximation to
f
(
x
)
{\displaystyle f(x)}
is given by
p
(
x
)
=
a
0
+
∑
k
=
1
m
(
a
k
cos
(
k
π
x
)
+
b
k
sin
(
k
π
x
)
)
{\displaystyle p(x)\;=\;a_{0}+\textstyle \sum _{\,k\,=\,1}^{m}(a_{k}\,\cos(k\,\pi \,x)+b_{k}\,\sin(k\,\pi \,x))}
where
a
k
=
∫
−
1
1
f
(
x
)
cos
(
k
π
x
)
d
x
{\displaystyle a_{k}\,=\;\int _{-1}^{1}\,f(x)\,\cos(k\,\pi \,x)\,dx}
and
b
k
=
∫
−
1
1
f
(
x
)
sin
(
k
π
x
)
d
x
{\displaystyle b_{k}\,=\;\int _{-1}^{1}\,f(x)\,\sin(k\,\pi \,x)\,dx}
.
p
(
x
)
{\displaystyle p(x)}
approximates
f
(
x
)
{\displaystyle f(x)}
in the sense that
∫
−
1
1
|
f
(
x
)
−
p
(
x
)
|
2
d
x
{\displaystyle \int _{-1}^{1}\left\vert f(x)-p(x)\right\vert ^{2}\,dx}
is minimized over all trigometric polynomials , of degree
m
{\displaystyle m}
or less, by
p
(
x
)
{\displaystyle p(x)}
.
In fact
∫
−
1
1
|
f
(
x
)
−
p
(
x
)
|
2
d
x
=
∫
−
1
1
(
f
(
x
)
−
p
(
x
)
)
(
f
(
x
)
¯
−
p
(
x
)
¯
)
d
x
{\displaystyle \int _{-1}^{1}\left\vert f(x)-p(x)\right\vert ^{2}\,dx\;=\;\int _{-1}^{1}(f(x)-p(x))({\overline {f(x)}}-{\overline {p(x)}})\,dx}
=
∫
−
1
1
(
|
f
(
x
)
|
2
−
2
ℜ
(
f
(
x
)
p
(
x
)
¯
)
+
|
p
(
x
)
|
2
)
d
x
{\displaystyle =\;\int _{-1}^{1}(\left\vert f(x)\right\vert ^{2}-2\,\Re (f(x){\overline {p(x)}})+\left\vert p(x)\right\vert ^{2})\,dx}
.
The term in the center
∫
−
1
1
ℜ
f
(
x
)
p
(
x
)
¯
d
x
{\displaystyle \int _{-1}^{1}\Re f(x){\overline {p(x)}}\,dx}
=
a
0
¯
∫
−
1
1
f
(
x
)
d
x
+
∑
k
=
1
m
(
a
k
¯
∫
−
1
1
f
(
x
)
cos
(
k
π
x
)
d
x
+
b
k
¯
∫
−
1
1
f
(
x
)
s
i
n
(
k
π
x
)
)
d
x
{\displaystyle =\;{\overline {a_{0}}}\int _{-1}^{1}f(x)\,dx+\textstyle \sum _{\,k\,=\,1}^{m}({\overline {a_{k}}}\,\int _{-1}^{1}f(x)\cos(k\,\pi \,x)\,dx+{\overline {b_{k}}}\,\int _{-1}^{1}f(x)sin(k\,\pi \,x))\,dx}
=
|
a
0
|
2
+
∑
k
=
1
m
(
|
a
k
|
2
+
|
b
k
|
2
)
=
∫
−
1
1
|
p
(
x
)
|
2
d
x
{\displaystyle =\;\left\vert a_{0}\right\vert ^{2}+\textstyle \sum _{\,k\,=\,1}^{m}(\left\vert a_{k}\right\vert ^{2}+\left\vert b_{k}\right\vert ^{2})\;=\;\int _{-1}^{1}\left\vert p(x)\right\vert ^{2}\,dx}
,
so that
∫
−
1
1
|
f
(
x
)
−
p
(
x
)
|
2
d
x
=
∫
−
1
1
|
f
(
x
)
|
2
d
x
−
∫
−
1
1
|
p
(
x
)
|
2
d
x
{\displaystyle \int _{-1}^{1}\left\vert f(x)-p(x)\right\vert ^{2}\,dx\;=\;\int _{-1}^{1}\left\vert f(x)\right\vert ^{2}\,dx-\int _{-1}^{1}\left\vert p(x)\right\vert ^{2}\,dx}
=
‖
f
(
x
)
‖
2
−
‖
p
(
x
)
‖
2
{\displaystyle =\;\lVert \,f(x)\,\rVert ^{2}-\lVert \,p(x)\,\rVert ^{2}}
.
If
p
(
x
)
{\displaystyle p(x)}
and
q
(
x
)
{\displaystyle q(x)}
are the
m
th
{\displaystyle m\,{\text{th}}}
degree trigometric polynomial approximations to
f
(
x
)
{\displaystyle f(x)}
and
g
(
x
)
{\displaystyle g(x)}
, then the
m
th
{\displaystyle m\,{\text{th}}}
degree trigometric polynomial approximation to
f
(
x
)
+
α
g
(
x
)
{\displaystyle f(x)+\alpha \,g(x)}
is given by
p
(
x
)
+
α
q
(
x
)
{\displaystyle p(x)+\alpha \,q(x)}
.
This follows immediately from (3.4.0) since
∫
−
1
1
(
f
(
x
)
+
α
g
(
x
)
)
cos
(
k
π
x
)
d
x
=
∫
−
1
1
f
(
x
)
cos
(
k
π
x
)
d
x
+
α
∫
−
1
1
g
(
x
)
cos
(
k
π
x
)
d
x
{\displaystyle \int _{-1}^{1}\,(f(x)+\alpha \,g(x))\,\cos(k\,\pi \,x)\,dx\;=\;\int _{-1}^{1}\,f(x)\,\cos(k\,\pi \,x)\,dx+\alpha \int _{-1}^{1}\,g(x)\,\cos(k\,\pi \,x)\,dx}
and
∫
−
1
1
(
f
(
x
)
+
α
g
(
x
)
)
sin
(
k
π
x
)
d
x
=
∫
−
1
1
f
(
x
)
sin
(
k
π
x
)
d
x
+
α
∫
−
1
1
g
(
x
)
sin
(
k
π
x
)
d
x
{\displaystyle \int _{-1}^{1}\,(f(x)+\alpha \,g(x))\,\sin(k\,\pi \,x)\,dx\;=\;\int _{-1}^{1}\,f(x)\,\sin(k\,\pi \,x)\,dx+\alpha \int _{-1}^{1}\,g(x)\,\sin(k\,\pi \,x)\,dx}
.
Fundamental Property
edit
Generally if
p
(
x
)
{\displaystyle p(x)}
is the
m
th
{\displaystyle m\,{\text{th}}}
degree trigometric polynomial approximation to a
function
f
(
x
)
{\displaystyle f(x)}
, periodic on
−
1
≤
x
≤
1
{\displaystyle -1\;\leq \;x\;\leq \;1}
, then
(
s
f
t
)
h
p
(
x
)
{\displaystyle (sft)_{h}\,p(x)}
is the
m
th
{\displaystyle m\,{\text{th}}}
degree trigometric polynomial approximation to
f
(
x
−
h
)
{\displaystyle f(x-h)}
.
To see this calculate the trigometric polynomial approximations for
f
(
x
−
h
)
{\displaystyle f(x-h)}
.
∫
−
1
1
f
(
x
−
h
)
cos
(
k
π
x
)
d
x
=
∫
−
1
−
h
1
−
h
f
(
x
)
cos
(
k
π
(
x
+
h
)
)
d
x
{\displaystyle \int _{-1}^{1}\,f(x-h)\,\cos(k\,\pi \,x)\,dx\;=\;\int _{-1-h}^{1-h}\,f(x)\,\cos(k\,\pi \,(x+h))\,dx}
=
∫
−
1
−
h
1
−
h
f
(
x
)
(
cos
(
k
π
h
)
cos
(
k
π
x
)
−
sin
(
k
π
h
)
sin
(
k
π
x
)
)
d
x
{\displaystyle =\;\int _{-1-h}^{1-h}\,f(x)\,(\cos(k\,\pi \,h)\cos(k\,\pi \,x)-\sin(k\,\pi \,h)\sin(k\,\pi \,x))\,dx}
=
cos
(
k
π
h
)
∫
−
1
−
h
1
−
h
f
(
x
)
cos
(
k
π
x
)
d
x
−
sin
(
k
π
h
)
∫
−
1
−
h
1
−
h
f
(
x
)
sin
(
k
π
x
)
d
x
{\displaystyle =\;\cos(k\,\pi \,h)\,\int _{-1-h}^{1-h}\,f(x)\,\cos(k\,\pi \,x)\,dx-\sin(k\,\pi \,h)\int _{-1-h}^{1-h}\,f(x)\,\sin(k\,\pi \,x)\,dx}
=
cos
(
k
π
h
)
∫
−
1
1
f
(
x
)
cos
(
k
π
x
)
d
x
−
sin
(
k
π
h
)
∫
−
1
1
f
(
x
)
sin
(
k
π
x
)
d
x
{\displaystyle =\;\cos(k\,\pi \,h)\,\int _{-1}^{1}\,f(x)\,\cos(k\,\pi \,x)\,dx-\sin(k\,\pi \,h)\int _{-1}^{1}\,f(x)\,\sin(k\,\pi \,x)\,dx}
=
a
k
cos
(
k
π
h
)
−
b
k
sin
(
k
π
h
)
{\displaystyle =\;a_{k}\,\cos(k\,\pi \,h)\,-\,b_{k}\,\sin(k\,\pi \,h)}
,
where
a
k
=
∫
−
1
1
f
(
x
)
cos
(
k
π
x
)
d
x
{\displaystyle a_{k}\,=\;\int _{-1}^{1}\,f(x)\,\cos(k\,\pi \,x)\,dx}
and
b
k
=
∫
−
1
1
f
(
x
)
sin
(
k
π
x
)
d
x
{\displaystyle b_{k}\,=\;\int _{-1}^{1}\,f(x)\,\sin(k\,\pi \,x)\,dx}
.
∫
−
1
1
f
(
x
−
h
)
sin
(
k
π
x
)
d
x
=
∫
−
1
−
h
1
−
h
f
(
x
)
sin
(
k
π
(
x
+
h
)
)
d
x
{\displaystyle \int _{-1}^{1}\,f(x-h)\,\sin(k\,\pi \,x)\,dx\;=\;\int _{-1-h}^{1-h}\,f(x)\,\sin(k\,\pi \,(x+h))\,dx}
=
∫
−
1
−
h
1
−
h
f
(
x
)
(
cos
(
k
π
h
)
sin
(
k
π
x
)
+
sin
(
k
π
h
)
cos
(
k
π
x
)
)
d
x
{\displaystyle =\;\int _{-1-h}^{1-h}\,f(x)\,(\cos(k\,\pi \,h)\sin(k\,\pi \,x)+\sin(k\,\pi \,h)\cos(k\,\pi \,x))\,dx}
=
cos
(
k
π
h
)
∫
−
1
−
h
1
−
h
f
(
x
)
sin
(
k
π
x
)
d
x
+
sin
(
k
π
h
)
∫
−
1
−
h
1
−
h
f
(
x
)
cos
(
k
π
x
)
d
x
{\displaystyle =\;\cos(k\,\pi \,h)\,\int _{-1-h}^{1-h}\,f(x)\,\sin(k\,\pi \,x)\,dx+\sin(k\,\pi \,h)\int _{-1-h}^{1-h}\,f(x)\,\cos(k\,\pi \,x)\,dx}
=
cos
(
k
π
h
)
∫
−
1
1
f
(
x
)
sin
(
k
π
x
)
d
x
+
sin
(
k
π
h
)
∫
−
1
1
f
(
x
)
cos
(
k
π
x
)
d
x
{\displaystyle =\;\cos(k\,\pi \,h)\,\int _{-1}^{1}\,f(x)\,\sin(k\,\pi \,x)\,dx+\sin(k\,\pi \,h)\int _{-1}^{1}\,f(x)\,\cos(k\,\pi \,x)\,dx}
=
a
k
sin
(
k
π
h
)
+
b
k
cos
(
k
π
h
)
{\displaystyle =\;a_{k}\,\sin(k\,\pi \,h)\,+\,b_{k}\,\cos(k\,\pi \,h)}
.
Comparing the results with (3.3.1) finishes the observation.
Another detail of use is
∫
−
1
1
|
f
(
x
−
h
)
−
(
s
f
t
)
h
p
(
x
)
|
2
d
x
{\displaystyle \int _{-1}^{1}\left\vert f(x-h)-(sft)_{h}\,p(x)\right\vert ^{2}\,dx}
=
∫
−
1
−
h
1
−
h
|
f
(
x
)
−
p
(
x
)
|
2
d
x
=
∫
−
1
1
|
f
(
x
)
−
p
(
x
)
|
2
d
x
{\displaystyle =\;\int _{-1-h}^{1-h}\left\vert f(x)-p(x)\right\vert ^{2}\,dx\;=\;\int _{-1}^{1}\left\vert f(x)-p(x)\right\vert ^{2}\,dx}
which is
‖
f
(
x
−
h
)
−
(
s
f
t
)
h
p
(
x
)
‖
=
‖
f
(
x
)
−
p
(
x
)
‖
{\displaystyle \lVert f(x-h)-(sft)_{h}\,p(x)\rVert \;=\;\lVert f(x)-p(x)\rVert }
.
A result used in error estimation is
p
(
x
)
−
(
s
f
t
)
h
p
(
x
)
=
a
0
+
∑
k
=
1
m
(
(
a
k
(
1
−
cos
(
k
π
h
)
)
+
b
k
sin
(
k
π
h
)
)
cos
(
k
π
x
)
+
(
−
a
k
sin
(
k
π
h
)
+
b
k
(
1
−
cos
(
k
π
h
)
)
)
sin
(
k
π
x
)
)
{\displaystyle {\begin{aligned}&p(x)-(sft)_{h}p(x)\;=\;\\&a_{0}+\textstyle \sum _{\,k\,=\,1}^{m}{\big (}(a_{k}\,(1-\cos(k\,\pi \,h))+b_{k}\,\sin(k\,\pi \,h))\,\cos(k\,\pi \,x)\\&\quad \quad \quad \quad \quad +(-a_{k}\,\sin(k\,\pi \,h)+b_{k}\,(1-\cos(k\,\pi \,h)))\,\sin(k\,\pi \,x){\big )}\\\end{aligned}}}
.
When
s
(
x
)
{\displaystyle s(x)}
is a sine polynomial
s
(
x
)
=
∑
k
=
1
m
b
k
sin
(
k
π
x
)
{\displaystyle s(x)\;=\;\textstyle \sum _{\,k\,=\,1}^{\,m}\,b_{k}\,\sin(k\,\pi \,x)}
then
s
(
x
)
−
(
s
f
t
)
h
s
(
x
)
=
∑
k
=
1
m
(
b
k
sin
(
k
π
h
)
cos
(
k
π
x
)
+
b
k
(
1
−
cos
(
k
π
h
)
)
sin
(
k
π
x
)
)
{\displaystyle {\begin{aligned}&s(x)-(sft)_{h}s(x)\;=\;\\&\textstyle \sum _{\,k\,=\,1}^{m}{\big (}b_{k}\,\sin(k\,\pi \,h)\,\cos(k\,\pi \,x)+b_{k}\,(1-\cos(k\,\pi \,h))\,\sin(k\,\pi \,x){\big )}\\\end{aligned}}}
and
‖
s
(
x
)
−
(
s
f
t
)
h
s
(
x
)
‖
2
=
∑
k
=
1
m
2
|
b
k
|
2
(
1
−
cos
(
k
π
h
)
)
{\displaystyle \lVert s(x)-(sft)_{h}s(x)\rVert ^{2}\;=\;\textstyle \sum _{\,k\,=\,1}^{\,m}\,2\,\left\vert b_{k}\right\vert ^{2}\,(1-\cos(k\,\pi \,h))}
.
Let
0
=
x
0
<
x
1
<
x
2
<
…
<
x
n
−
1
<
x
n
=
1
{\displaystyle 0\;=\;x_{0}\;<\;x_{1}\;<\;x_{2}\;<\;\ldots \;\;<\;x_{n-1}\;<\;x_{n}\;=\;1}
so that
{
[
x
0
,
x
1
]
,
(
x
2
,
x
2
]
,
…
,
(
x
n
−
2
,
x
n
−
1
]
,
(
x
n
−
1
,
x
n
]
}
{\displaystyle \{\;[x_{0}\,,\;x_{1}]\,,\;(x_{2}\,,\;x_{2}]\,,\;\ldots ,\;(x_{n-2}\,,\;x_{n-1}]\,,\;(x_{n-1}\,,\;x_{n}]\;\}}
is a partition of
0
≤
x
≤
1
{\displaystyle 0\;\leq \;x\;\leq \;1}
.
The function
f
(
x
)
{\displaystyle f(x)}
is said to be simple
on
0
≤
x
≤
1
{\displaystyle 0\;\leq \;x\;\leq \;1}
, if
f
(
x
)
=
{
f
0
,
when
x
∈
[
x
0
,
x
1
]
f
i
,
when
x
∈
(
x
i
,
x
i
+
1
]
,
1
≤
i
≤
n
−
1
{\displaystyle f(x)\;=\;{\begin{cases}f_{0}\,,\quad {\text{when}}\quad x\in [x_{0}\,,\;x_{1}]\\f_{i}\,,\quad {\text{when}}\quad x\in (x_{i}\,,\;x_{i+1}]\,,\quad 1\;\leq \;i\;\leq \;n-1\\\end{cases}}}
Of particular interest is when the points have equal spacing
x
i
−
x
i
−
1
=
1
n
{\displaystyle x_{i}-x_{i-1}\;=\;{\tfrac {1}{n}}}
.
The intent is to make estimates of
∫
0
1
|
f
(
x
)
−
f
(
x
−
h
)
|
2
d
x
{\displaystyle \int _{0}^{1}\,\left\vert f(x)-f(x-h)\right\vert ^{2}\,dx}
.
Begin by making an odd extension of
f
(
x
)
{\displaystyle f(x)}
to
−
1
≤
x
≤
1
{\displaystyle -1\;\leq \;x\;\leq \;1}
by setting
f
(
−
x
)
=
−
f
(
x
)
{\displaystyle f(-x)\;=\;-f(x)}
and continue the definition by extending
f
(
x
)
{\displaystyle f(x)}
periodically .
Then approximate
f
(
x
)
{\displaystyle f(x)}
with a sine polynomial
s
(
x
)
=
∑
k
=
1
m
b
k
sin
(
k
π
x
)
{\displaystyle s(x)\;=\;\textstyle \sum _{\,k\,=\,1}^{\,m}\,b_{k}\,\sin(k\,\pi \,x)}
where
b
k
=
2
∫
0
1
f
(
x
)
sin
(
k
π
x
)
d
x
{\displaystyle b_{k}\,=\;2\,\int _{0}^{1}\,f(x)\,\sin(k\,\pi \,x)\,dx}
.
When
m
{\displaystyle m}
is large enough so that some
k
{\displaystyle k}
are divided by
2
n
{\displaystyle 2\,n}
then,
for
k
=
2
n
r
{\displaystyle k\;=\;2\,n\,r}
b
k
=
2
∑
i
=
1
n
∫
x
i
−
1
x
i
f
(
x
)
sin
(
k
π
x
)
d
x
=
2
∑
i
=
1
n
f
i
−
1
∫
(
i
−
1
)
1
n
i
1
n
sin
(
k
π
x
)
d
x
{\displaystyle {\begin{aligned}b_{k}\,=&\;2\,\textstyle \sum _{i\,=\,1}^{n}\int _{x_{i-1}}^{x_{i}}\,f(x)\,\sin(k\,\pi \,x)\,dx\\=&\;2\,\textstyle \sum _{i\,=\,1}^{n}\,f_{i-1}\int _{(i-1){\tfrac {1}{n}}}^{i\,{\tfrac {1}{n}}}\,\sin(k\,\pi \,x)\,dx\\\end{aligned}}}
,
and letting
x
=
1
n
r
u
{\displaystyle x\;=\;{\tfrac {1}{n\,r}}\,u}
,
∫
(
i
−
1
)
1
n
i
1
n
sin
(
k
π
x
)
d
x
=
∫
(
i
−
1
)
r
i
r
sin
(
2
π
u
)
d
u
=
0
{\displaystyle \int _{(i-1){\tfrac {1}{n}}}^{\,i\,{\tfrac {1}{n}}}\,\sin(k\,\pi \,x)\,dx\;=\;\int _{(i-1)\,r}^{\,i\,r}\,\sin(2\,\pi \,u)\,du\;=\;0}
,
so that
b
k
=
b
2
n
r
=
0
{\displaystyle b_{k}\;=\;b_{\,2\,n\,r}\;=\;0}
.
Now, return to the sum
‖
s
(
x
)
−
(
s
f
t
)
h
s
(
x
)
‖
2
=
∑
k
=
1
m
2
|
b
k
|
2
(
1
−
cos
(
k
π
h
)
)
{\displaystyle \lVert s(x)-(sft)_{h}s(x)\rVert ^{2}\;=\;\textstyle \sum _{\,k\,=\,1}^{\,m}\,2\,\left\vert b_{k}\right\vert ^{2}\,(1-\cos(k\,\pi \,h))}
with
b
2
n
r
=
0
{\displaystyle b_{\,2\,n\,r}\;=\;0}
for
r
=
1
,
2
,
3
,
…
{\displaystyle r\;=\;1\,,\;2\,,\;3\,,\ldots }
.
If
gcd
(
j
,
2
n
)
=
1
{\displaystyle \gcd(\,j,2\,n)\,=\,1}
and
(
2
n
)
⧸
∖
k
{\displaystyle (2\,n)\not \!\backslash \;k}
, then
(
2
n
)
⧸
∖
k
j
{\displaystyle (2\,n)\not \!\backslash \;k\,j}
, and in this case
cos
(
k
π
j
1
n
)
≠
0
{\displaystyle \cos(k\,\pi \,j\,{\tfrac {1}{n}})\;\neq \;0}
and
(
1
−
cos
(
k
π
j
1
n
)
)
≥
(
1
−
cos
(
π
1
n
)
)
{\displaystyle (1-\cos(k\,\pi \,j\,{\tfrac {1}{n}}))\;\geq \;(1-\cos(\pi \,{\tfrac {1}{n}}))}
.
So for
h
=
j
1
n
{\displaystyle h\;=\;j\,{\tfrac {1}{n}}}
with
gcd
(
j
,
2
n
)
=
1
{\displaystyle \gcd(\,j,2\,n)\,=\,1}
,
‖
s
(
x
)
−
(
s
f
t
)
h
s
(
x
)
‖
2
≥
∑
k
=
1
m
2
|
b
k
|
2
(
1
−
cos
(
π
1
n
)
)
{\displaystyle \lVert s(x)-(sft)_{h}s(x)\rVert ^{2}\;\geq \;\textstyle \sum _{\,k\,=\,1}^{\,m}\,2\,\left\vert b_{k}\right\vert ^{2}\,(1-\cos(\pi \,{\tfrac {1}{n}}))}
=
(
1
−
cos
(
π
1
n
)
)
∑
k
=
1
m
2
|
b
k
|
2
=
2
(
1
−
cos
(
π
1
n
)
)
‖
s
(
x
)
‖
2
{\displaystyle =\;(1-\cos(\pi \,{\tfrac {1}{n}}))\,\textstyle \sum _{\,k\,=\,1}^{\,m}\,2\,\left\vert b_{k}\right\vert ^{2}\;=\;2\,(1-\cos(\pi \,{\tfrac {1}{n}}))\,\lVert s(x)\rVert ^{2}}
.
Next observe that if
s
(
x
)
{\displaystyle s(x)}
is the
m
th
{\displaystyle m\,{\text{th}}}
degree sine polynomial approximation to
f
(
x
)
{\displaystyle f(x)}
then
(
s
f
t
)
h
s
(
x
)
{\displaystyle (sft)_{h}\,s(x)}
is the
m
th
{\displaystyle m\,{\text{th}}}
degree trigometric polynomial approximation to
f
(
x
−
h
)
{\displaystyle f(x-h)}
. The assumption that
f
(
x
)
{\displaystyle f(x)}
is odd and periodic is still in effect.
Finally the intended results follow.
‖
s
(
x
)
−
(
s
f
t
)
h
s
(
x
)
‖
{\displaystyle \lVert s(x)-(sft)_{h}\,s(x)\rVert }
=
‖
(
f
(
x
)
−
f
(
x
−
h
)
)
+
(
s
(
x
)
−
f
(
x
)
)
−
(
(
s
f
t
)
h
s
(
x
)
−
f
(
x
−
h
)
)
‖
{\displaystyle =\;\lVert (f(x)-f(x-h))+(s(x)-f(x))-((sft)_{h}\,s(x)-f(x-h))\rVert }
≤
‖
f
(
x
)
−
f
(
x
−
h
)
‖
+
‖
f
(
x
)
−
s
(
x
)
‖
+
‖
f
(
x
−
h
)
−
(
s
f
t
)
h
s
(
x
)
‖
{\displaystyle \leq \;\lVert f(x)-f(x-h)\rVert +\lVert f(x)-s(x)\rVert +\lVert f(x-h)-(sft)_{h}\,s(x)\rVert }
=
‖
f
(
x
)
−
f
(
x
−
h
)
‖
+
2
‖
f
(
x
)
−
s
(
x
)
‖
{\displaystyle =\;\lVert f(x)-f(x-h)\rVert +2\,\lVert f(x)-s(x)\rVert }
so that
‖
f
(
x
)
−
f
(
x
−
h
)
‖
≥
‖
s
(
x
)
−
(
s
f
t
)
h
s
(
x
)
‖
−
2
‖
f
(
x
)
−
s
(
x
)
‖
{\displaystyle \lVert f(x)-f(x-h)\rVert \;\geq \;\lVert s(x)-(sft)_{h}\,s(x)\rVert -2\,\lVert f(x)-s(x)\rVert }
.
Making use of (3.7.1)
‖
f
(
x
)
−
f
(
x
−
h
)
‖
≥
2
(
1
−
cos
(
π
1
n
)
)
‖
s
(
x
)
‖
−
2
‖
f
(
x
)
−
s
(
x
)
‖
{\displaystyle \lVert f(x)-f(x-h)\rVert \;\geq \;{\sqrt {2\,(1-\cos(\pi \,{\tfrac {1}{n}}))}}\,\lVert s(x)\rVert -2\,\lVert f(x)-s(x)\rVert }
.
Being that simple functions can be approximated by trigometric polynomials to arbitrary accuracy,
‖
f
(
x
)
−
f
(
x
−
h
)
‖
≥
2
(
1
−
cos
(
π
1
n
)
)
‖
f
(
x
)
‖
{\displaystyle \lVert f(x)-f(x-h)\rVert \;\geq \;{\sqrt {2\,(1-\cos(\pi \,{\tfrac {1}{n}}))}}\,\lVert f(x)\rVert }
.
Now, for
h
=
1
n
{\displaystyle h\;=\;{\tfrac {1}{n}}}
, and using the definition of the simple function
f
(
x
)
{\displaystyle f(x)}
‖
f
(
x
)
‖
2
=
2
n
∑
i
=
0
n
−
1
|
f
i
|
2
{\displaystyle \lVert f(x)\rVert ^{2}\;=\;{\frac {2}{n}}\textstyle \sum _{\,i\,=\,0}^{\,n-1}\left\vert f_{i}\right\vert ^{2}}
To find the sum for
‖
f
(
x
)
−
f
(
x
−
h
)
‖
2
{\displaystyle \lVert f(x)-f(x-h)\rVert ^{2}}
list tthe values of
f
(
x
)
{\displaystyle f(x)}
over the values of
f
(
x
−
h
)
{\displaystyle f(x-h)}
on the whole interval
−
1
≤
x
≤
1
{\displaystyle -1\;\leq \;x\;\leq \;1}
.
−
f
n
−
1
−
f
n
−
2
…
−
f
1
−
f
0
f
0
f
1
f
2
…
f
n
−
2
f
n
−
1
f
n
−
1
−
f
n
−
1
…
−
f
2
−
f
1
−
f
0
f
0
f
1
…
f
n
−
3
f
n
−
2
{\displaystyle {\begin{aligned}-f_{n-1}&-f_{n-2}&\ldots &-f_{1}&-f_{0}&\;&f_{0}&\;&f_{1}&\;&f_{2}&\ldots &f_{n-2}&\;&f_{n-1}\\f_{n-1}&-f_{n-1}&\ldots &-f_{2}&-f_{1}&\;&-f_{0}&\;&f_{0}&\;&f_{1}&\ldots &f_{n-3}&\;&f_{n-2}\end{aligned}}}
This gives
‖
f
(
x
)
−
f
(
x
−
h
)
‖
2
=
2
n
(
2
|
f
0
|
2
+
∑
i
=
1
n
−
1
|
f
i
−
f
i
−
1
|
2
+
2
|
f
n
−
1
|
2
)
{\displaystyle \lVert f(x)-f(x-h)\rVert ^{2}\;=\;{\frac {2}{n}}{\big (}2\,\left\vert f_{0}\right\vert ^{2}+\textstyle \sum _{\,i\,=\,1}^{\,n-1}\left\vert f_{i}-f_{i-1}\right\vert ^{2}+2\,\left\vert f_{n-1}\right\vert ^{2}{\big )}}
.
So the inequality follows
2
|
f
0
|
2
+
∑
i
=
1
n
−
1
|
f
i
−
f
i
−
1
|
2
+
2
|
f
n
−
1
|
2
≥
2
(
1
−
cos
(
π
1
n
)
)
∑
i
=
0
n
−
1
|
f
i
|
2
{\displaystyle 2\,\left\vert f_{0}\right\vert ^{2}+\textstyle \sum _{\,i\,=\,1}^{\,n-1}\left\vert f_{i}-f_{i-1}\right\vert ^{2}+2\,\left\vert f_{n-1}\right\vert ^{2}\;\geq \;2\,(1-\cos(\pi \,{\tfrac {1}{n}}))\textstyle \sum _{\,i\,=\,0}^{\,n-1}\left\vert f_{i}\right\vert ^{2}}
.
Energy and Heat Norms
edit
There are a number of less well known, but important norms . These norms
are important in the analysis of many physical problems and are used
in error estimation for finite difference and finite element methods. Examples are the energy and heat norms.
These norms are usually expressed in an integral form.
‖
y
‖
E
=
∫
a
b
(
1
2
k
y
2
(
t
)
+
1
2
m
(
y
′
)
2
(
t
)
)
d
t
{\displaystyle \lVert y\rVert _{E}\;=\;{\sqrt {\int _{a}^{b}{\big (}{\tfrac {1}{2}}\,k\,y^{2}(t)+{\tfrac {1}{2}}\,m\,(y^{\prime })^{2}(t){\big )}\,dt}}}
‖
y
‖
H
=
∫
a
b
(
y
2
(
t
)
+
(
y
′
)
2
(
t
)
+
(
y
′
′
)
2
(
t
)
+
…
+
(
y
(
k
)
)
2
(
t
)
)
d
t
{\displaystyle \lVert y\rVert _{H}\;=\;{\sqrt {\int _{a}^{b}{\big (}\,y^{2}(t)+\,(y^{\prime })^{2}(t)+\,(y^{\prime \prime })^{2}(t)\,+\ldots +\,(y^{(k)})^{2}(t){\big )}\,dt}}}
When
y
(
a
)
=
y
(
b
)
=
0
{\displaystyle y(a)\;=\;y(b)\;=\;0}
the inequality below holds.
∫
a
b
(
y
′
)
2
(
t
)
d
t
≥
4
3
(
b
−
a
)
∫
a
b
y
2
(
t
)
d
t
{\displaystyle {\sqrt {\int _{a}^{b}\,(y^{\prime })^{2}(t)\,dt}}\;\geq \;{\frac {\sqrt[{3}]{\,4\,}}{(b-a)}}\,{\sqrt {\int _{a}^{b}\,y^{2}(t)\,dt}}}
This follows from a completely elementary, but lengthy calculation, as shown
in appendix a). When additional assumptions on
y
{\displaystyle y}
are made this inequality can be improved somewhat.
∫
a
b
(
y
′
)
2
(
t
)
d
t
≥
π
(
b
−
a
)
∫
a
b
y
2
(
t
)
d
t
{\displaystyle {\sqrt {\int _{a}^{b}\,(y^{\prime })^{2}(t)\,dt}}\;\geq \;{\frac {\pi }{(b-a)}}\,{\sqrt {\int _{a}^{b}\,y^{2}(t)\,dt}}}
See appendix b) for an explanation.
In the analysis of finite difference methods for partial differential equations it is useful to have discrete analogs of norms like the
energy and heat norms.
In an attempt not to have notation too cumbersome some indices are suppressed
when from the discussion it is clear what they refer to. When
v
→
=
<
v
1
v
2
⋯
v
n
>
{\displaystyle {\vec {v}}\;=\;<v_{1}\;v_{2}\;\cdots \;v_{n}>}
is a
n
{\displaystyle n}
dimensional vector of complex numbers ,
finite difference operators are defined as discrete approximations
or analogs of derivatives .
The most appropriate definition of a discrete energy or heat
norm may vary due to differences in the handling of initial or
boudary conditions . So for this reason the reader should make
appropriate adjustments, when needed, to apply the same reasoning to another
problem.
Before the discrete versions of energy or heat norms
can be defined, finite differece operations need to be defined and
explained. This was done in the section on finite difference
operators .
The next discrete version of the preceding inequality has important applications to the estimation of the error when approximating a second
derivative with a finite difference operator.
If
v
0
=
v
n
+
1
=
0
{\displaystyle v_{0}\,=\,v_{n+1}\,=\,0}
then
∑
i
=
1
n
+
1
(
v
i
−
v
i
−
1
)
2
≥
β
n
n
+
1
∑
i
=
1
n
v
i
2
{\displaystyle {\sqrt {\textstyle \sum _{\,i\,=\,1}^{\,n+1}(v_{i}-v_{i-1})^{2}}}\geq \,{\frac {\beta _{n}}{n+1}}\,{\sqrt {\textstyle \sum _{\,i\,=\,1}^{\,n}\,v_{i}^{2}}}}
with
β
1
=
2
2
,
β
2
=
3
,
{\displaystyle \beta _{1}\,=\,2\,{\sqrt {2}}\,,\,\,\,\beta _{2}\,=\,3,\;}
and generally the following under-estimate holds.
β
n
≥
2
n
+
1
n
+
3
{\displaystyle \beta _{n}\;\geq \;{\sqrt {2}}\,{\sqrt {\tfrac {n+1}{n+3}}}}
See appendix c) for a proof.
The inequality can be improved for general
n
{\displaystyle n}
by using
(3.7.3) with
n
{\displaystyle n}
increased by 2 .
2
|
f
0
|
2
+
∑
i
=
1
n
−
1
|
f
i
−
f
i
−
1
|
2
+
2
|
f
n
−
1
|
2
≥
2
(
1
−
cos
(
π
1
n
)
)
∑
i
=
0
n
−
1
|
f
i
|
2
{\displaystyle 2\,\left\vert f_{0}\right\vert ^{2}+\textstyle \sum _{\,i\,=\,1}^{\,n-1}\left\vert f_{i}-f_{i-1}\right\vert ^{2}+2\,\left\vert f_{n-1}\right\vert ^{2}\;\geq \;2\,(1-\cos(\pi \,{\tfrac {1}{n}}))\textstyle \sum _{\,i\,=\,0}^{\,n-1}\left\vert f_{i}\right\vert ^{2}}
If
v
0
=
v
n
+
1
=
0
{\displaystyle v_{0}\,=\,v_{n+1}\,=\,0}
then
∑
i
=
1
n
+
1
(
v
i
−
v
i
−
1
)
2
≥
2
(
1
−
cos
(
π
1
n
+
2
)
)
∑
i
=
1
n
v
i
2
{\displaystyle {\sqrt {\textstyle \sum _{\,i\,=\,1}^{\,n+1}(v_{i}-v_{i-1})^{2}}}\geq \,{\sqrt {2\,(1-\cos(\pi \,{\tfrac {1}{n+2}}))}}\,{\sqrt {\textstyle \sum _{\,i\,=\,1}^{\,n}\,v_{i}^{2}}}}
and
2
(
1
−
cos
(
π
1
n
+
2
)
)
→
π
n
+
2
{\displaystyle {\sqrt {2\,(1-\cos(\pi \,{\tfrac {1}{n+2}}))}}\;\to \;{\frac {\pi }{n+2}}}
.
When
y
(
a
)
=
y
(
b
)
=
0
{\displaystyle y(a)\;=\;y(b)\;=\;0}
the inequality below holds.
∫
a
b
(
y
′
)
2
(
t
)
d
t
≥
4
3
(
b
−
a
)
∫
a
b
y
2
(
t
)
d
t
{\displaystyle {\sqrt {\int _{a}^{b}\,(y^{\prime })^{2}(t)\,dt}}\;\geq \;{\frac {\sqrt[{3}]{\,4\,}}{(b-a)}}\,{\sqrt {\int _{a}^{b}\,y^{2}(t)\,dt}}}
First apply the Cauchy Schwarz inequality.
1
2
y
2
(
x
)
=
∫
a
x
y
(
t
)
y
′
(
t
)
d
t
≤
∫
a
x
y
2
(
t
)
d
t
∫
a
x
(
y
′
)
2
(
t
)
d
t
{\displaystyle {\begin{aligned}{\tfrac {1}{2}}\,y^{2}(x)\;=&\;\int _{a}^{x}\,y(t)\,y^{\prime }(t)\,dt\;\leq \;{\sqrt {\int _{a}^{x}\,y^{2}(t)\,dt}}\;{\sqrt {\int _{a}^{x}\,(y^{\prime })^{2}(t)\,dt}}\\\end{aligned}}}
,
Next observe the integrals on the right are increasing with
x
{\displaystyle x}
.
1
2
y
2
(
u
)
≤
∫
a
x
y
2
(
t
)
d
t
∫
a
x
(
y
′
)
2
(
t
)
d
t
,
for
a
≤
u
≤
x
{\displaystyle {\begin{aligned}{\tfrac {1}{2}}\,y^{2}(u)\;&\;\leq \;{\sqrt {\int _{a}^{x}\,y^{2}(t)\,dt}}\;{\sqrt {\int _{a}^{x}\,(y^{\prime })^{2}(t)\,dt}}\,,\quad {\text{for}}\;\;a\;\leq \;u\;\leq \;x\\\end{aligned}}}
Integrate, make cancellations, and reapply the first inequality.
1
2
∫
a
x
y
2
(
t
)
d
t
≤
(
x
−
a
)
∫
a
x
y
2
(
t
)
d
t
∫
a
x
(
y
′
)
2
(
t
)
d
t
{\displaystyle {\frac {1}{2}}\,\int _{a}^{x}\,y^{2}(t)\,dt\;\leq \;(x-a)\;{\sqrt {\int _{a}^{x}\,y^{2}(t)\,dt}}\;{\sqrt {\int _{a}^{x}\,(y^{\prime })^{2}(t)\,dt}}}
.
∫
a
x
y
2
(
t
)
d
t
≤
2
(
x
−
a
)
∫
a
x
(
y
′
)
2
(
t
)
d
t
{\displaystyle {\sqrt {\int _{a}^{x}\,y^{2}(t)\,dt}}\;\leq \;2\,(x-a)\;{\sqrt {\int _{a}^{x}\,(y^{\prime })^{2}(t)\,dt}}}
.
y
2
(
x
)
≤
4
(
x
−
a
)
∫
a
x
(
y
′
)
2
(
t
)
d
t
{\displaystyle y^{2}(x)\;\leq \;4\,(x-a)\,\int _{a}^{x}\,(y^{\,\prime })^{2}(t)\,dt}
.
After integrating again the inequality is improved.
∫
a
x
y
2
(
t
)
d
t
≤
4
∫
a
x
(
t
−
a
)
d
t
∫
a
x
(
y
′
)
2
(
t
)
d
t
=
2
(
x
−
a
)
2
∫
a
x
(
y
′
)
2
(
t
)
d
t
{\displaystyle {\begin{aligned}\int _{a}^{x}\,y^{2}(t)\,dt\;\leq &\;4\,\int _{a}^{x}(t-a)\,dt\,\int _{a}^{x}\,(y^{\,\prime })^{2}(t)\,dt\\=&\;2\,(x-a)^{2}\,\int _{a}^{x}\,(y^{\,\prime })^{2}(t)\,dt\\\end{aligned}}}
.
∫
a
x
y
2
(
t
)
d
t
≤
2
(
x
−
a
)
∫
a
x
(
y
′
)
2
(
t
)
d
t
{\displaystyle {\sqrt {\int _{a}^{x}\,y^{2}(t)\,dt}}\;\leq \;{\sqrt {\,2}}\,(x-a)\,{\sqrt {\int _{a}^{x}\,(y^{\,\prime })^{2}(t)\,dt}}}
.
Now, assume the inequality immediately below holds for some
α
{\displaystyle \alpha }
.
∫
a
x
y
2
(
t
)
d
t
≤
α
(
x
−
a
)
∫
a
x
(
y
′
)
2
(
t
)
d
t
{\displaystyle {\sqrt {\int _{a}^{x}\,y^{2}(t)\,dt}}\;\leq \;\alpha \,(x-a)\,{\sqrt {\int _{a}^{x}\,(y^{\,\prime })^{2}(t)\,dt}}}
After substituting the inequality above into the next
1
2
∫
a
x
y
2
(
t
)
d
t
≤
(
x
−
a
)
∫
a
x
y
2
(
t
)
d
t
∫
a
x
(
y
′
)
2
(
t
)
d
t
{\displaystyle {\frac {1}{2}}\,\int _{a}^{x}\,y^{2}(t)\,dt\;\leq \;(x-a)\;{\sqrt {\int _{a}^{x}\,y^{2}(t)\,dt}}\;{\sqrt {\int _{a}^{x}\,(y^{\prime })^{2}(t)\,dt}}}
.
the following observations are made.
∫
a
x
y
2
(
t
)
d
t
≤
2
α
(
x
−
a
)
2
∫
a
x
(
y
′
)
2
(
t
)
d
t
{\displaystyle \int _{a}^{x}\,y^{2}(t)\,dt\;\leq \;2\,\alpha \,(x-a)^{2}\;\int _{a}^{x}\,(y^{\prime })^{2}(t)\,dt}
.
∫
a
x
y
2
(
t
)
d
t
≤
2
α
(
x
−
a
)
∫
a
x
(
y
′
)
2
(
t
)
d
t
{\displaystyle {\sqrt {\int _{a}^{x}\,y^{2}(t)\,dt}}\;\leq \;{\sqrt {2\,\alpha }}\,(x-a)\;{\sqrt {\int _{a}^{x}\,(y^{\prime })^{2}(t)\,dt}}}
.
y
2
(
x
)
≤
2
2
α
(
x
−
a
)
∫
a
x
(
y
′
)
2
(
t
)
d
t
{\displaystyle y^{2}(x)\;\leq \;2\,{\sqrt {2\,\alpha }}\,(x-a)\,\int _{a}^{x}\,(y^{\,\prime })^{2}(t)\,dt}
.
∫
a
x
y
2
(
t
)
d
t
≤
2
2
α
∫
a
x
(
t
−
a
)
d
t
∫
a
x
(
y
′
)
2
(
t
)
d
t
=
2
α
(
x
−
a
)
2
∫
a
x
(
y
′
)
2
(
t
)
d
t
{\displaystyle {\begin{aligned}\int _{a}^{x}\,y^{2}(t)\,dt\;\leq &\;2\,{\sqrt {2\,\alpha }}\,\int _{a}^{x}(t-a)\,dt\,\int _{a}^{x}\,(y^{\,\prime })^{2}(t)\,dt\\=&\;{\sqrt {2\,\alpha }}\,(x-a)^{2}\,\int _{a}^{x}\,(y^{\,\prime })^{2}(t)\,dt\\\end{aligned}}}
.
∫
a
x
y
2
(
t
)
d
t
≤
2
α
4
(
x
−
a
)
∫
a
x
(
y
′
)
2
(
t
)
d
t
{\displaystyle {\sqrt {\int _{a}^{x}\,y^{2}(t)\,dt}}\;\leq \;{\sqrt[{4}]{2\,\alpha }}\,(x-a)\;{\sqrt {\int _{a}^{x}\,(y^{\prime })^{2}(t)\,dt}}}
.
Repeating this iteration leads to a sequence
α
n
+
1
=
2
α
n
4
{\displaystyle \alpha _{n+1}\;=\;{\sqrt[{4}]{2\,\alpha _{n}}}}
which converges to
α
=
2
3
{\displaystyle \alpha \;=\;{\sqrt[{3}]{\,2}}}
, the solution of
α
=
2
α
4
{\displaystyle \alpha \;=\;{\sqrt[{4}]{2\,\alpha }}}
.
So:
∫
a
x
y
2
(
t
)
d
t
≤
2
3
(
x
−
a
)
∫
a
x
(
y
′
)
2
(
t
)
d
t
{\displaystyle {\sqrt {\int _{a}^{x}\,y^{2}(t)\,dt}}\;\leq \;{\sqrt[{3}]{\,2}}\,(x-a)\,{\sqrt {\int _{a}^{x}\,(y^{\,\prime })^{2}(t)\,dt}}}
and
y
2
(
x
)
≤
2
2
2
3
(
x
−
a
)
∫
a
x
(
y
′
)
2
(
t
)
d
t
{\displaystyle y^{2}(x)\;\leq \;2\,{\sqrt {2\,{\sqrt[{3}]{\,2}}}}\,(x-a)\,\int _{a}^{x}\,(y^{\,\prime })^{2}(t)\,dt}
.
For
c
=
(
a
+
b
)
/
2
{\displaystyle c=(a+b)\,/\,2}
,
∫
a
c
y
2
(
t
)
d
t
≤
2
2
2
3
∫
a
c
(
t
−
a
)
d
t
∫
a
c
(
y
′
)
2
(
t
)
d
t
=
2
2
3
(
c
−
a
)
2
∫
a
c
(
y
′
)
2
(
t
)
d
t
=
2
2
3
4
(
b
−
a
)
2
∫
a
c
(
y
′
)
2
(
t
)
d
t
{\displaystyle {\begin{aligned}\int _{a}^{c}\,y^{2}(t)\,dt\;\leq &\;2\,{\sqrt {2\,{\sqrt[{3}]{\,2}}}}\,\int _{a}^{c}(t-a)\,dt\,\int _{a}^{c}\,(y^{\,\prime })^{2}(t)\,dt\\=&\;{\sqrt {2\,{\sqrt[{3}]{\,2}}}}\,(c-a)^{2}\,\int _{a}^{c}\,(y^{\,\prime })^{2}(t)\,dt\\=&\;{\frac {\sqrt {2\,{\sqrt[{3}]{\,2}}}}{4}}\,(b-a)^{2}\,\int _{a}^{c}\,(y^{\,\prime })^{2}(t)\,dt\\\end{aligned}}}
.
∫
a
c
y
2
(
t
)
d
t
≤
4
3
4
(
b
−
a
)
2
∫
a
c
(
y
′
)
2
(
t
)
d
t
{\displaystyle \int _{a}^{c}\,y^{2}(t)\,dt\;\leq \;{\frac {\sqrt[{3}]{\,4}}{4}}\,(b-a)^{2}\,\int _{a}^{c}\,(y^{\,\prime })^{2}(t)\,dt}
.
To handle the part
∫
c
b
y
2
(
t
)
d
t
{\displaystyle \int _{c}^{b}\,y^{2}(t)\,dt}
1
2
y
2
(
x
)
=
∫
x
b
−
y
(
t
)
y
′
(
t
)
d
t
≤
∫
x
b
y
2
(
t
)
d
t
∫
x
b
(
y
′
)
2
(
t
)
d
t
{\displaystyle {\begin{aligned}{\tfrac {1}{2}}\,y^{2}(x)\;=&\;\int _{x}^{b}\,-y(t)\,y^{\prime }(t)\,dt\;\leq \;{\sqrt {\int _{x}^{b}\,y^{2}(t)\,dt}}\;{\sqrt {\int _{x}^{b}\,(y^{\prime })^{2}(t)\,dt}}\\\end{aligned}}}
,
1
2
y
2
(
u
)
≤
∫
x
b
y
2
(
t
)
d
t
∫
x
b
(
y
′
)
2
(
t
)
d
t
,
for
x
≤
u
≤
b
{\displaystyle {\begin{aligned}{\tfrac {1}{2}}\,y^{2}(u)\;&\;\leq \;{\sqrt {\int _{x}^{b}\,y^{2}(t)\,dt}}\;{\sqrt {\int _{x}^{b}\,(y^{\prime })^{2}(t)\,dt}}\,,\quad {\text{for}}\;\;x\;\leq \;u\;\leq \;b\\\end{aligned}}}
1
2
∫
x
b
y
2
(
t
)
d
t
≤
(
b
−
x
)
∫
x
b
y
2
(
t
)
d
t
∫
x
b
(
y
′
)
2
(
t
)
d
t
{\displaystyle {\frac {1}{2}}\,\int _{x}^{b}\,y^{2}(t)\,dt\;\leq \;(b-x)\;{\sqrt {\int _{x}^{b}\,y^{2}(t)\,dt}}\;{\sqrt {\int _{x}^{b}\,(y^{\prime })^{2}(t)\,dt}}}
.
∫
x
b
y
2
(
t
)
d
t
≤
2
(
b
−
x
)
∫
x
b
(
y
′
)
2
(
t
)
d
t
{\displaystyle {\sqrt {\int _{x}^{b}\,y^{2}(t)\,dt}}\;\leq \;2\,(b-x)\;{\sqrt {\int _{x}^{b}\,(y^{\prime })^{2}(t)\,dt}}}
.
y
2
(
x
)
≤
4
(
b
−
x
)
∫
x
b
(
y
′
)
2
(
t
)
d
t
{\displaystyle y^{2}(x)\;\leq \;4\,(b-x)\,\int _{x}^{b}\,(y^{\,\prime })^{2}(t)\,dt}
.
Reasoning as before this inequality can be strengthend to
y
2
(
x
)
≤
2
2
2
3
(
b
−
x
)
∫
x
b
(
y
′
)
2
(
t
)
d
t
{\displaystyle y^{2}(x)\;\leq \;2\,{\sqrt {2\,{\sqrt[{3}]{\,2}}}}\,(b-x)\,\int _{x}^{b}\,(y^{\,\prime })^{2}(t)\,dt}
.
∫
c
b
y
2
(
t
)
d
t
≤
2
2
2
3
∫
c
b
(
b
−
t
)
d
t
∫
c
b
(
y
′
)
2
(
t
)
d
t
=
2
2
3
(
b
−
c
)
2
∫
c
b
(
y
′
)
2
(
t
)
d
t
=
2
2
3
4
(
b
−
a
)
2
∫
c
b
(
y
′
)
2
(
t
)
d
t
{\displaystyle {\begin{aligned}\int _{c}^{b}\,y^{2}(t)\,dt\;\leq &\;2\,{\sqrt {2\,{\sqrt[{3}]{\,2}}}}\,\int _{c}^{b}(b-t)\,dt\,\int _{c}^{b}\,(y^{\,\prime })^{2}(t)\,dt\\=&\;{\sqrt {2\,{\sqrt[{3}]{\,2}}}}\,(b-c)^{2}\,\int _{c}^{b}\,(y^{\,\prime })^{2}(t)\,dt\\=&\;{\frac {\sqrt {2\,{\sqrt[{3}]{\,2}}}}{4}}\,(b-a)^{2}\,\int _{c}^{b}\,(y^{\,\prime })^{2}(t)\,dt\\\end{aligned}}}
.
∫
c
b
y
2
(
t
)
d
t
≤
4
3
4
(
b
−
a
)
2
∫
c
b
(
y
′
)
2
(
t
)
d
t
{\displaystyle \int _{c}^{b}\,y^{2}(t)\,dt\;\leq \;{\frac {\sqrt[{3}]{\,4}}{4}}\,(b-a)^{2}\,\int _{c}^{b}\,(y^{\,\prime })^{2}(t)\,dt}
.
Adding the results of the two main calculations
∫
a
b
y
2
(
t
)
d
t
=
∫
a
c
y
2
(
t
)
d
t
+
∫
c
b
y
2
(
t
)
d
t
≤
4
3
4
(
b
−
a
)
2
∫
a
c
(
y
′
)
2
(
t
)
d
t
+
4
3
4
(
b
−
a
)
2
∫
c
b
(
y
′
)
2
(
t
)
d
t
=
4
3
4
(
b
−
a
)
2
∫
a
b
(
y
′
)
2
(
t
)
d
t
{\displaystyle {\begin{aligned}&\int _{a}^{b}\,y^{2}(t)\,dt\;=\;\int _{a}^{c}\,y^{2}(t)\,dt\;+\;\int _{c}^{b}\,y^{2}(t)\,dt\\\leq &\;{\frac {\sqrt[{3}]{\,4}}{4}}\,(b-a)^{2}\,\int _{a}^{c}\,(y^{\,\prime })^{2}(t)\,dt+\;{\frac {\sqrt[{3}]{\,4}}{4}}\,(b-a)^{2}\,\int _{c}^{b}\,(y^{\,\prime })^{2}(t)\,dt\\=&\;{\frac {\sqrt[{3}]{\,4}}{4}}\,(b-a)^{2}\,\int _{a}^{b}\,(y^{\,\prime })^{2}(t)\,dt\\\end{aligned}}}
.
When
y
(
a
)
=
y
(
b
)
=
0
{\displaystyle y(a)\;=\;y(b)\;=\;0}
the inequality below holds.
∫
a
b
(
y
′
)
2
(
t
)
d
t
≥
π
(
b
−
a
)
∫
a
b
y
2
(
t
)
d
t
{\displaystyle {\sqrt {\int _{a}^{b}\,(y^{\prime })^{2}(t)\,dt}}\;\geq \;{\frac {\pi }{(b-a)}}\,{\sqrt {\int _{a}^{b}\,y^{2}(t)\,dt}}}
Assume the conditions that
y
(
x
)
{\displaystyle y(x)}
can be approximated by a trigometric polynomial
s
(
x
)
=
a
1
sin
(
π
(
b
−
a
)
x
)
+
a
2
sin
(
π
(
b
−
a
)
2
x
)
+
a
3
sin
(
π
(
b
−
a
)
3
x
)
+
…
+
a
n
sin
(
π
(
b
−
a
)
n
x
)
{\displaystyle {\begin{aligned}s(x)\;=&\;a_{1}\,\sin {({\frac {\pi }{(b-a)}}\,x)}+a_{2}\,\sin {({\frac {\pi }{(b-a)}}\,2\,x)}+a_{3}\,\sin {({\frac {\pi }{(b-a)}}\,3\,x)}\\&+\;\ldots \;+a_{n}\,\sin {({\frac {\pi }{(b-a)}}\,n\,x)}\\\end{aligned}}}
.
such that
y
′
(
x
)
{\displaystyle y^{\prime }(x)}
is also approximated by the
polynomials derivative
s
′
(
x
)
=
a
1
π
(
b
−
a
)
cos
(
π
(
b
−
a
)
x
)
+
2
a
2
π
(
b
−
a
)
cos
(
π
(
b
−
a
)
2
x
)
+
3
a
3
π
(
b
−
a
)
cos
(
π
(
b
−
a
)
3
x
)
+
…
+
n
a
n
π
(
b
−
a
)
cos
(
π
(
b
−
a
)
n
x
)
{\displaystyle {\begin{aligned}&s^{\prime }(x)\;=\;a_{1}\,{\frac {\pi }{(b-a)}}\,\cos {({\frac {\pi }{(b-a)}}\,x)}+2\,a_{2}\,{\frac {\pi }{(b-a)}}\,\cos {({\frac {\pi }{(b-a)}}\,2\,x)}\\&+3\,a_{3}\,{\frac {\pi }{(b-a)}}\,\cos {({\frac {\pi }{(b-a)}}\,3\,x)}+\;\ldots \;+n\,a_{n}\,{\frac {\pi }{(b-a)}}\,\cos {({\frac {\pi }{(b-a)}}\,n\,x)}\\\end{aligned}}}
That is to say, given
ϵ
>
0
{\displaystyle \epsilon \;>\;0}
, there exixts
a trigometric sine polynomial
s
(
x
)
{\displaystyle s(x)}
, such that
∫
a
b
|
f
(
x
)
−
s
(
x
)
|
2
d
x
<
ϵ
{\displaystyle \int _{a}^{b}{\left\vert f(x)-s(x)\right\vert }^{2}\,dx\;<\;\epsilon }
and
∫
a
b
|
f
′
(
x
)
−
s
′
(
x
)
|
2
d
x
<
ϵ
{\displaystyle \int _{a}^{b}{\left\vert f^{\prime }(x)-s^{\prime }(x)\right\vert }^{2}\,dx\;<\;\epsilon }
.
Now,
2
b
−
a
∫
a
b
|
s
(
x
)
|
2
d
x
=
|
a
1
|
2
+
|
a
2
|
2
+
|
a
3
|
2
+
…
+
|
a
n
|
2
{\displaystyle {\frac {2}{b-a}}\,\int _{a}^{b}{\left\vert s(x)\right\vert }^{2}\,dx\;=\;{\left\vert a_{1}\right\vert }^{2}+{\left\vert a_{2}\right\vert }^{2}+{\left\vert a_{3}\right\vert }^{2}+\;\ldots \;+{\left\vert a_{n}\right\vert }^{2}}
and
2
b
−
a
∫
a
b
|
s
′
(
x
)
|
2
d
x
=
π
2
(
b
−
a
)
2
|
a
1
|
2
+
2
2
π
2
(
b
−
a
)
2
|
a
2
|
2
+
3
2
π
2
(
b
−
a
)
2
|
a
3
|
2
+
…
+
n
2
π
2
(
b
−
a
)
2
|
a
n
|
2
{\displaystyle {\begin{aligned}{\frac {2}{b-a}}\,\int _{a}^{b}{\left\vert s^{\prime }(x)\right\vert }^{2}\,dx\;&=\;{\frac {\pi ^{2}}{(b-a)^{2}}}\,{\left\vert a_{1}\right\vert }^{2}+2^{2}\,{\frac {\pi ^{2}}{(b-a)^{2}}}\,{\left\vert a_{2}\right\vert }^{2}+3^{2}\,{\frac {\pi ^{2}}{(b-a)^{2}}}\,{\left\vert a_{3}\right\vert }^{2}\\&+\;\ldots \;+n^{2}\,{\frac {\pi ^{2}}{(b-a)^{2}}}\,{\left\vert a_{n}\right\vert }^{2}\\\end{aligned}}}
.
So it is easy to see that
∫
a
b
|
s
′
(
x
)
|
2
d
x
≥
π
2
(
b
−
a
)
2
∫
a
b
|
s
(
x
)
|
2
d
x
{\displaystyle \int _{a}^{b}{\left\vert s^{\prime }(x)\right\vert }^{2}\,dx\;\geq \;{\frac {\pi ^{2}}{(b-a)^{2}}}\,\int _{a}^{b}{\left\vert s(x)\right\vert }^{2}\,dx}
.
In this case the inequality is sharp , since it holds with equality for
f
(
x
)
=
sin
(
π
(
b
−
a
)
x
)
{\displaystyle f(x)\;=\;\sin {({\frac {\pi }{(b-a)}}\,x)}}
.
Since
∫
a
b
|
s
(
x
)
|
2
d
x
−
ϵ
<
∫
a
b
|
f
(
x
)
|
2
d
x
<
∫
a
b
|
s
(
x
)
|
2
d
x
+
ϵ
{\displaystyle {\sqrt {\int _{a}^{b}{\left\vert s(x)\right\vert }^{2}\,dx}}-{\sqrt {\epsilon }}\;<\;{\sqrt {\int _{a}^{b}{\left\vert f(x)\right\vert }^{2}\,dx}}\;<\;{\sqrt {\int _{a}^{b}{\left\vert s(x)\right\vert }^{2}\,dx}}+{\sqrt {\epsilon }}}
,
and
∫
a
b
|
s
′
(
x
)
|
2
d
x
−
ϵ
<
∫
a
b
|
f
′
(
x
)
|
2
d
x
<
∫
a
b
|
s
′
(
x
)
|
2
d
x
+
ϵ
{\displaystyle {\sqrt {\int _{a}^{b}{\left\vert s^{\prime }(x)\right\vert }^{2}\,dx}}-{\sqrt {\epsilon }}\;<\;{\sqrt {\int _{a}^{b}{\left\vert f^{\prime }(x)\right\vert }^{2}\,dx}}\;<\;{\sqrt {\int _{a}^{b}{\left\vert s^{\prime }(x)\right\vert }^{2}\,dx}}\;+{\sqrt {\epsilon }}}
,
the inequality holds for
y
(
x
)
{\displaystyle y(x)}
and
y
′
(
x
)
{\displaystyle y^{\prime }(x)}
.
If
v
0
=
v
n
+
1
=
0
{\displaystyle v_{0}\,=\,v_{n+1}\,=\,0}
then
∑
i
=
1
n
+
1
(
v
i
−
v
i
−
1
)
2
≥
β
n
n
+
1
∑
i
=
1
n
v
i
2
{\displaystyle {\sqrt {\textstyle \sum _{\,i\,=\,1}^{\,n+1}(v_{i}-v_{i-1})^{2}}}\geq \,{\frac {\beta _{n}}{n+1}}\,{\sqrt {\textstyle \sum _{\,i\,=\,1}^{\,n}\,v_{i}^{2}}}}
with
β
1
=
2
2
,
β
2
=
3
,
{\displaystyle \beta _{1}\,=\,2\,{\sqrt {2}}\,,\,\,\,\beta _{2}\,=\,3,\;}
and generally the following under-estimate holds.
β
n
≥
2
n
+
1
n
+
3
{\displaystyle \beta _{n}\;\geq \;{\sqrt {2}}\,{\sqrt {\tfrac {n+1}{n+3}}}}
The cases for 1 and 2 are simple.
(
v
1
−
v
0
)
2
+
(
v
2
−
v
1
)
2
=
2
v
1
2
{\displaystyle (v_{1}-v_{0})^{2}+(v_{2}-v_{1})^{2}\;=\;2\,v_{1}^{2}}
and
(
v
1
−
v
0
)
2
+
(
v
2
−
v
1
)
2
+
(
v
2
−
v
1
)
2
=
v
1
2
+
(
v
2
−
v
1
)
2
+
v
2
2
≥
v
1
2
+
v
2
2
{\displaystyle {\begin{aligned}(v_{1}-v_{0})^{2}+(v_{2}-v_{1})^{2}+(v_{2}-v_{1})^{2}\;=&\;v_{1}^{2}+(v_{2}-v_{1})^{2}+v_{2}^{2}\\\;\geq &\;v_{1}^{2}+v_{2}^{2}\\\end{aligned}}}
with equality, when
v
1
=
v
2
{\displaystyle v_{1}\;=\;v_{2}}
.
To prove the general under-estimate do as follows.
Use
v
0
=
0
{\displaystyle v_{0}\;=\;0}
and apply the Cauchy Schwartz inequality together with inequality ( ).
v
k
2
=
∑
i
=
1
k
(
v
i
2
−
v
i
−
1
2
)
=
∑
i
=
1
k
(
v
i
+
v
i
−
1
)
(
v
i
−
v
i
−
1
)
{\displaystyle v_{k}^{2}\,=\,\textstyle \sum _{i\,=\,1}^{k}(v_{i}^{2}-v_{i-1}^{2})\,=\,\textstyle \sum _{i\,=\,1}^{k}(v_{i}+v_{i-1})(v_{i}-v_{i-1})}
≤
∑
i
=
1
k
(
v
i
+
v
i
−
1
)
2
∑
i
=
1
k
(
v
i
−
v
i
−
1
)
2
{\displaystyle \leq \,{\sqrt {\textstyle \sum _{i\,=\,1}^{k}(v_{i}+v_{i-1})^{2}}}\,{\sqrt {\textstyle \sum _{i\,=\,1}^{k}(v_{i}-v_{i-1})^{2}}}}
≤
2
∑
i
=
1
k
v
i
2
∑
i
=
1
k
(
v
i
−
v
i
−
1
)
2
{\displaystyle \leq \,2\,{\sqrt {\textstyle \sum _{i\,=\,1}^{k}\,v_{i}^{2}\;}}\,{\sqrt {\textstyle \sum _{i\,=\,1}^{k}(v_{i}-v_{i-1})^{2}}}}
So for
i
≤
k
{\displaystyle i\;\leq \;k}
,
v
i
2
≤
2
∑
j
=
1
i
v
j
2
∑
j
=
1
i
(
v
j
−
v
j
−
1
)
2
{\displaystyle v_{i}^{2}\leq \,2\,{\sqrt {\textstyle \sum _{j\,=\,1}^{\,i}\,v_{j}^{2}\;}}\,{\sqrt {\textstyle \sum _{j\,=\,1}^{\,i}(v_{j}-v_{j-1})^{2}}}}
and
∑
i
=
1
k
v
i
2
≤
2
k
∑
i
=
1
k
(
v
i
−
v
i
−
1
)
2
{\displaystyle {\sqrt {\textstyle \sum _{i\,=\,1}^{k}\,v_{i}^{2}}}\leq \,2\,k\,{\sqrt {\textstyle \sum _{i\,=\,1}^{k}(v_{i}-v_{i-1})^{2}}}}
.
After inserting the inequality above into (1)
v
k
2
≤
4
k
∑
i
=
1
k
(
v
i
−
v
i
−
1
)
2
{\displaystyle v_{k}^{2}\;\leq \,4\,k\,\textstyle \sum _{i\,=\,1}^{k}(v_{i}-v_{i-1})^{2}}
.
So for
i
≤
k
{\displaystyle i\;\leq \;k}
,
v
i
2
≤
4
i
∑
j
=
1
i
(
v
j
−
v
j
−
1
)
2
{\displaystyle v_{i}^{2}\;\leq \,4\,i\,\textstyle \sum _{j\,=\,1}^{i}(v_{j}-v_{j-1})^{2}}
∑
i
=
1
k
v
i
2
≤
4
(
∑
i
=
1
k
i
)
∑
j
=
1
k
(
v
j
−
v
j
−
1
)
2
{\displaystyle \textstyle \sum _{i\,=\,1}^{k}\,v_{i}^{2}\;\leq \,4\,(\textstyle \sum _{i\,=\,1}^{k}\,i)\,\textstyle \sum _{j\,=\,1}^{k}(v_{j}-v_{j-1})^{2}}
and after using formula ()
∑
i
=
1
k
v
i
2
≤
2
k
(
k
+
1
)
∑
i
=
1
k
(
v
i
−
v
i
−
1
)
2
{\displaystyle \textstyle \sum _{i\,=\,1}^{k}\,v_{i}^{2}\;\leq \,2\,\,k(k+1)\,\textstyle \sum _{i\,=\,1}^{k}(v_{i}-v_{i-1})^{2}}
.
Using
v
n
+
1
=
0
{\displaystyle v_{n+1}\;=\;0}
the right end of the sum is
estimated using nearly the same procedure.
v
k
2
=
∑
i
=
k
n
(
v
i
2
−
v
i
+
1
2
)
=
∑
i
=
k
n
(
v
i
+
v
i
+
1
)
(
v
i
−
v
i
+
1
)
{\displaystyle v_{k}^{2}\,=\,\textstyle \sum _{i\,=\,k}^{n}(v_{i}^{2}-v_{i+1}^{2})\,=\,\textstyle \sum _{i\,=\,k}^{n}(v_{i}+v_{i+1})(v_{i}-v_{i+1})}
≤
∑
i
=
k
+
1
n
+
1
(
v
i
+
v
i
−
1
)
2
∑
i
=
k
+
1
n
+
1
(
v
i
−
v
i
−
1
)
2
{\displaystyle \leq \,{\sqrt {\textstyle \sum _{\,i\,=\,k+1}^{n+1}(v_{i}+v_{i-1})^{2}}}\,{\sqrt {\textstyle \sum _{\,i\,=\,k+1}^{n+1}(v_{i}-v_{i-1})^{2}}}}
≤
2
∑
i
=
k
n
v
i
2
∑
i
=
k
+
1
n
+
1
(
v
i
−
v
i
−
1
)
2
{\displaystyle \leq \,2\,{\sqrt {\textstyle \sum _{\,i\,=\,k}^{n}\,v_{i}^{2}\;}}\,{\sqrt {\textstyle \sum _{\,i\,=\,k+1}^{n+1}(v_{i}-v_{i-1})^{2}}}}
So for
i
≥
k
{\displaystyle i\;\geq \;k}
,
v
i
2
≤
2
∑
j
=
i
n
v
j
2
∑
j
=
i
+
1
n
+
1
(
v
j
−
v
j
−
1
)
2
{\displaystyle v_{i}^{2}\leq \,2\,{\sqrt {\textstyle \sum _{j\,=\,i}^{\,n}\,v_{j}^{2}\;}}\,{\sqrt {\textstyle \sum _{j\,=\,i+1}^{\,n+1}(v_{j}-v_{j-1})^{2}}}}
,
∑
i
=
k
n
v
i
2
≤
2
(
n
−
k
+
1
)
∑
i
=
k
+
1
n
+
1
(
v
i
−
v
i
−
1
)
2
{\displaystyle {\sqrt {\textstyle \sum _{i\,=\,k}^{n}\,v_{i}^{2}}}\leq \,2\,(n-k+1)\,{\sqrt {\textstyle \sum _{i\,=\,k+1}^{n+1}(v_{i}-v_{i-1})^{2}}}}
,
and
v
k
2
≤
4
(
n
−
k
+
1
)
∑
i
=
k
+
1
n
+
1
(
v
i
−
v
i
−
1
)
2
{\displaystyle v_{k}^{2}\;\leq \,4\,(n-k+1)\,\textstyle \sum _{i\,=\,k+1}^{n+1}(v_{i}-v_{i-1})^{2}}
.
So for
i
≥
k
{\displaystyle i\;\geq \;k}
,
v
i
2
≤
4
(
n
−
i
+
1
)
∑
j
=
i
+
1
n
+
1
(
v
j
−
v
j
−
1
)
2
{\displaystyle v_{i}^{2}\;\leq \,4\,(n-i+1)\,\textstyle \sum _{j\,=\,i+1}^{n+1}(v_{j}-v_{j-1})^{2}}
,
∑
i
=
k
n
v
i
2
≤
4
(
(
n
+
1
)
(
n
−
k
+
1
)
−
(
∑
i
=
k
n
i
)
)
∑
i
=
k
+
1
n
+
1
(
v
i
−
v
i
−
1
)
2
{\displaystyle \textstyle \sum _{i\,=\,k}^{n}\,v_{i}^{2}\;\leq \,4\,((n+1)(n-k+1)-(\textstyle \sum _{i\,=\,k}^{n}\,i))\,\textstyle \sum _{i\,=\,k+1}^{n+1}(v_{i}-v_{i-1})^{2}}
=
2
(
2
(
n
+
1
)
(
n
−
k
+
1
)
−
(
n
(
n
+
1
)
−
(
k
−
1
)
k
)
)
∑
i
=
k
+
1
n
+
1
(
v
i
−
v
i
−
1
)
2
{\displaystyle =\,2\,\,(2\,(n+1)(n-k+1)-(n(n+1)-(k-1)k))\,\textstyle \sum _{i\,=\,k+1}^{n+1}(v_{i}-v_{i-1})^{2}}
=
2
(
(
n
−
2
k
+
3
)
n
+
(
k
−
1
)
(
k
−
2
)
)
∑
i
=
k
+
1
n
+
1
(
v
i
−
v
i
−
1
)
2
{\displaystyle =\,2\,\,((n-2\,k+3)n+(k-1)(k-2))\,\textstyle \sum _{i\,=\,k+1}^{n+1}(v_{i}-v_{i-1})^{2}}
.
Combining the two results:
∑
i
=
1
n
v
i
2
=
∑
i
=
1
k
v
i
2
+
∑
i
=
k
+
1
n
v
i
2
{\displaystyle \textstyle \sum _{i\,=\,1}^{n}\,v_{i}^{2}\;=\;\textstyle \sum _{i\,=\,1}^{k}\,v_{i}^{2}\;+\;\textstyle \sum _{i\,=\,k+1}^{n}\,v_{i}^{2}}
≤
2
k
(
k
+
1
)
∑
i
=
1
k
(
v
i
−
v
i
−
1
)
2
{\displaystyle \leq \,2\,\,k(k+1)\,\textstyle \sum _{i\,=\,1}^{k}(v_{i}-v_{i-1})^{2}}
+
2
(
(
n
−
2
k
+
1
)
n
+
k
(
k
−
1
)
)
∑
i
=
k
+
2
n
+
1
(
v
i
−
v
i
−
1
)
2
{\displaystyle +\,2\,\,((n-2\,k+1)n+k(k-1))\,\textstyle \sum _{i\,=\,k+2}^{n+1}(v_{i}-v_{i-1})^{2}}
.
When
n
{\displaystyle n}
is odd , use
k
=
(
n
+
1
)
/
2
{\displaystyle k\;=\;(n+1)\,/\,2}
so that the inequality becomes
≤
2
n
+
1
2
n
+
3
2
∑
i
=
1
k
(
v
i
−
v
i
−
1
)
2
{\displaystyle \leq \,2\,\,{\frac {n+1}{2}}{\frac {n+3}{2}}\,\textstyle \sum _{i\,=\,1}^{k}(v_{i}-v_{i-1})^{2}}
+
2
(
n
+
1
2
n
−
1
2
)
∑
i
=
k
+
2
n
+
1
(
v
i
−
v
i
−
1
)
2
{\displaystyle +\,2\,\,({\frac {n+1}{2}}{\frac {n-1}{2}})\,\textstyle \sum _{i\,=\,k+2}^{n+1}(v_{i}-v_{i-1})^{2}}
≤
(
n
+
1
)
(
n
+
3
)
2
∑
i
=
1
n
+
1
(
v
i
−
v
i
−
1
)
2
{\displaystyle \leq \,{\frac {(n+1)(n+3)}{2}}\,\textstyle \sum _{i\,=\,1}^{n+1}(v_{i}-v_{i-1})^{2}}
.
When
n
{\displaystyle n}
is even , use
k
=
n
/
2
{\displaystyle k\;=\;n\,/\,2}
so that the inequality becomes
≤
2
n
2
n
+
2
2
∑
i
=
1
k
(
v
i
−
v
i
−
1
)
2
{\displaystyle \leq \,2\,\,{\frac {n}{2}}{\frac {n+2}{2}}\,\textstyle \sum _{i\,=\,1}^{k}(v_{i}-v_{i-1})^{2}}
+
2
(
n
2
n
+
2
2
)
∑
i
=
k
+
2
n
+
1
(
v
i
−
v
i
−
1
)
2
{\displaystyle +\,2\,\,({\frac {n}{2}}{\frac {n+2}{2}})\,\textstyle \sum _{i\,=\,k+2}^{n+1}(v_{i}-v_{i-1})^{2}}
≤
(
n
)
(
n
+
2
)
2
∑
i
=
1
n
+
1
(
v
i
−
v
i
−
1
)
2
{\displaystyle \leq \,{\frac {(n)(n+2)}{2}}\,\textstyle \sum _{i\,=\,1}^{n+1}(v_{i}-v_{i-1})^{2}}
.
The rule named L´Hospital's Rule named by a French math teacher who published it without proof, because he said you need to be taken to the hospital if you can't prove it yourself, states.
If
lim
x
→
a
f
(
x
)
=
0
{\displaystyle {\underset {x\to a}{\lim }}\;f(x)\,=\,0}
and
lim
x
→
a
g
(
x
)
=
0
{\displaystyle {\underset {x\to a}{\lim }}\;g(x)\,=\,0}
then,
lim
x
→
a
f
(
x
)
g
(
x
)
=
lim
x
→
a
f
′
(
x
)
g
′
(
x
)
{\displaystyle {\underset {x\to a}{\lim }}\;{\frac {f(x)}{g(x)}}\,=\,{\underset {x\to a}{\lim }}\;{\frac {f^{\prime }(x)}{g^{\prime }(x)}}}
.
The rule named Leibniz's Rule states how to differentiate a product of two functions
n
{\displaystyle n}
times.
(
u
v
)
(
n
)
=
∑
k
=
0
n
(
n
k
)
u
(
k
)
v
(
n
−
k
)
{\displaystyle (u\,v)^{(n)}\;=\;\textstyle \sum _{k\,=\,0}^{n}{\binom {n}{k}}u^{(k)}v^{(n-k)}}
There are a number of ways to find the formulas for the sums of the powers of the first
n
{\displaystyle n}
integers. One of the most convenient is as follows. Begin with the geometric formula.
1
−
x
n
+
1
1
−
x
=
(
1
−
x
n
+
1
)
(
1
−
x
)
−
1
=
∑
k
=
0
n
x
k
{\displaystyle {\frac {1-x^{n+1}}{1-x}}\;=\;(1-x^{n+1})(1-x)^{-1}\;=\;\textstyle \sum _{\,k\,=\,0}^{n}x^{k}}
By convention
x
0
=
1
{\displaystyle x^{0}\;=\;1}
.
Apply Leibniz's Rule rule to the right hand side of the equivalent identity
(
1
−
x
n
+
1
)
=
(
1
−
x
)
∑
k
=
0
n
x
k
{\displaystyle (1-x^{n+1})\;=\;(1-x)\textstyle \sum _{\,k\,=\,0}^{n}x^{k}}
to differentiate both sides
m
{\displaystyle m}
times.
−
(
n
+
1
)
n
…
(
n
−
m
+
2
)
x
n
−
m
+
1
=
∑
j
=
0
m
(
m
j
)
(
1
−
x
)
(
j
)
(
∑
k
=
0
n
x
k
)
(
m
−
j
)
{\displaystyle -(n+1)n\ldots (n-m+2)x^{n-m+1}\;=\;\textstyle \sum _{j\,=\,0}^{m}{\binom {m}{j}}(1-x)^{(j)}(\textstyle \sum _{\,k\,=\,0}^{n}x^{k})^{(m-j)}}
Upon noticing that only the first two terms of the sum on the right are non-zero
−
(
n
+
1
)
n
…
(
n
−
m
+
2
)
x
n
−
m
+
1
=
(
1
−
x
)
(
∑
k
=
0
n
x
k
)
(
m
)
−
m
(
∑
k
=
0
n
x
k
)
(
m
−
1
)
{\displaystyle -(n+1)n\ldots (n-m+2)x^{n-m+1}\;=\;(1-x)(\textstyle \sum _{\,k\,=\,0}^{n}x^{k})^{(m)}-m(\textstyle \sum _{\,k\,=\,0}^{n}x^{k})^{(m-1)}}
.
Now take the limit as
x
→
1
{\displaystyle x\to 1}
to establish the formula
(
n
+
1
)
n
…
(
n
−
m
+
2
)
=
lim
x
→
1
m
(
∑
k
=
0
n
x
k
)
(
m
−
1
)
{\displaystyle (n+1)n\ldots (n-m+2)\;=\;{\underset {x\,\to \,1}{\lim }}m(\textstyle \sum _{\,k\,=\,0}^{n}x^{k})^{(m-1)}}
.
From term by term differentiation.
(
∑
k
=
0
n
x
k
)
′
=
∑
k
=
1
n
k
x
k
−
1
{\displaystyle (\textstyle \sum _{\,k\,=\,0}^{n}x^{k})^{\prime }\;=\;\textstyle \sum _{\,k\,=\,1}^{n}k\,x^{k-1}}
and
(
n
+
1
)
n
=
2
∑
k
=
1
n
k
{\displaystyle (n+1)n\;=\;2\textstyle \sum _{\,k\,=\,1}^{n}k}
.
More generally
(
∑
k
=
0
n
x
k
)
(
j
)
=
∑
k
=
j
n
k
(
k
−
1
)
…
(
k
−
j
+
1
)
x
k
−
j
{\displaystyle (\textstyle \sum _{\,k\,=\,0}^{n}x^{k})^{(j)}\;=\;\textstyle \sum _{\,k\,=\,j}^{n}k(k-1)\ldots (k-j+1)\,x^{k-j}}
.
and thus
(
n
+
1
)
n
…
(
n
−
m
+
2
)
=
m
∑
k
=
m
−
1
n
k
(
k
−
1
)
…
(
k
−
m
+
2
)
{\displaystyle (n+1)n\ldots (n-m+2)\;=\;m\textstyle \sum _{\,k\,=\,m-1}^{n}k(k-1)\ldots (k-m+2)}
.
A progression of formulas follow by setting
m
=
3
,
4
,
…
{\displaystyle m\,=\,3,\;4,\;\ldots }
.
∑
k
=
1
n
k
=
n
(
n
+
1
)
2
{\displaystyle {\textstyle \sum _{\,k\,=\,1}^{n}k}\;=\;\;{\frac {n(n+1)}{2}}}
(
n
+
1
)
n
(
n
−
1
)
=
3
∑
k
=
2
n
k
(
k
−
1
)
=
3
∑
k
=
1
n
−
1
(
k
+
1
)
k
{\displaystyle (n+1)n(n-1)\;=\;3\textstyle \sum _{\,k\,=\,2}^{n}k(k-1)\;=\;3\textstyle \sum _{\,k\,=\,1}^{n-1}(k+1)k}
.
=
3
∑
k
=
1
n
−
1
k
2
+
3
∑
k
=
1
n
−
1
k
{\displaystyle =\;3\textstyle \sum _{\,k\,=\,1}^{\,n-1}k^{2}+3\textstyle \sum _{\,k\,=\,1}^{\,n-1}k}
.
and
(
n
+
2
)
(
n
+
1
)
n
=
3
∑
k
=
1
n
k
2
+
3
∑
k
=
1
n
k
{\displaystyle (n+2)(n+1)n\;=\;3\textstyle \sum _{\,k\,=\,1}^{\,n}k^{2}+3\textstyle \sum _{\,k\,=\,1}^{\,n}k}
.
∑
k
=
1
n
k
2
=
n
(
n
+
1
)
(
n
+
2
)
3
−
n
(
n
+
1
)
2
{\displaystyle {\textstyle \sum _{\,k\,=\,1}^{\,n}k^{2}}\;=\;{\frac {n(n+1)(n+2)}{3}}-{\frac {n(n+1)}{2}}}
After adjusting the index of summation and increasing
n
{\displaystyle n}
by
m
−
2
{\displaystyle m-2}
the progression has the form
(
n
+
m
−
1
)
(
n
+
m
−
2
)
…
(
n
+
1
)
n
=
m
∑
k
=
1
n
(
k
+
m
−
2
)
(
k
+
m
−
3
)
…
(
k
+
1
)
k
{\displaystyle (n+m-1)(n+m-2)\ldots (n+1)n\;=\;m\textstyle \sum _{\,k\,=\,1}^{\,n}(k+m-2)(k+m-3)\ldots (k+1)k}
.
Letting
m
=
4
{\displaystyle m\;=\;4}
(
n
+
3
)
(
n
+
2
)
(
n
+
1
)
n
=
4
(
∑
k
=
1
n
k
3
+
3
∑
k
=
1
n
k
2
+
2
∑
k
=
1
n
k
)
{\displaystyle (n+3)(n+2)(n+1)n\;=\;4(\textstyle \sum _{\,k\,=\,1}^{\,n}k^{3}+3\,\textstyle \sum _{\,k\,=\,1}^{\,n}k^{2}+2\,\textstyle \sum _{\,k\,=\,1}^{\,n}k)}
.
∑
k
=
1
n
k
3
=
n
(
n
+
1
)
(
n
+
2
)
(
n
+
3
)
4
−
n
(
n
+
1
)
(
n
+
2
)
+
n
(
n
+
1
)
2
{\displaystyle {\textstyle \sum _{\,k\,=\,1}^{\,n}k^{3}}\;=\;{\frac {n(n+1)(n+2)(n+3)}{4}}-n(n+1)(n+2)+{\frac {n(n+1)}{2}}}
The formula called summation by parts is a discrete analog of integration by parts . It is verified simply by inspection.
∑
i
=
1
m
w
i
(
v
i
−
v
i
−
1
)
=
w
m
v
m
−
w
0
v
0
−
∑
i
=
0
m
−
1
v
i
(
w
i
+
1
−
w
i
)
{\displaystyle \sum _{i=1}^{m}w_{i}\,(v_{i}-v_{i-1})=w_{m}\,v_{m}-w_{0}\,v_{0}-\sum _{i=0}^{m-1}v_{i}\,(w_{i+1}-w_{i})}
One form of the statement of the Fundamental Theorem of Integral Calculus is
For
F
(
x
)
=
∫
a
x
f
(
t
)
d
t
{\displaystyle F(x)\;=\;\int _{a}^{x}f(t)\,dt}
it holds
F
′
(
x
)
=
f
(
x
)
{\displaystyle F^{\,\prime }(x)\;=\;f(x)}
.
Another rule which slightly generalizes the Fundamental Theorem of Integral Calculus says
d
d
x
∫
a
x
f
(
x
,
t
)
d
t
=
f
(
x
,
x
)
+
∫
a
x
∂
∂
x
f
(
x
,
t
)
d
t
{\displaystyle {\frac {d}{dx}}\int _{a}^{x}f(x,t)\,dt\;=\;f(x,x)+\int _{a}^{x}{\tfrac {\partial }{\partial x}}f(x,\,t)\,dt}
.
The following simple inequality can be used to bound sums of products.
(
a
−
b
)
2
=
a
2
−
2
a
b
+
b
2
≥
0
2
a
b
≤
a
2
+
b
2
a
b
≤
1
2
(
a
2
+
b
2
)
{\displaystyle {\begin{aligned}(a-b)^{2}&=a^{2}-2\,a\,b+b^{2}\,\geq \,0\\2\,a\,b\,&\leq \,a^{2}+b^{2}\\a\,b\,&\leq \,{\frac {1}{2}}\,(a^{2}+b^{2})\\\end{aligned}}}
and also
a
b
=
(
α
a
)
(
b
/
α
)
≤
1
2
(
α
2
a
2
+
b
2
/
α
2
)
{\displaystyle a\,b\;=\;(\alpha \,a)\,(b\,/\,\alpha )\;\leq \;{\frac {1}{2}}\,(\alpha ^{2}\,a^{2}+b^{2}\,/\,\alpha ^{2})}
,
so that
∑
i
=
1
n
a
i
b
i
≤
1
2
∑
i
=
1
n
(
α
i
2
a
i
2
+
b
i
2
/
α
i
2
)
{\displaystyle \textstyle \sum _{\,i\,=\,1}^{\,n}a_{i}\,b_{i}\;\leq \;{\frac {1}{2}}\textstyle \sum _{\,i\,=\,1}^{\,n}\,(\alpha _{i}^{2}\,a_{i}^{2}+b_{i}^{2}\,/\,\alpha _{i}^{2})}
.
Letting
b
i
=
b
{\displaystyle b_{i}\,=\,b}
and
α
i
2
=
n
{\displaystyle \alpha _{i}^{2}\,=\,{\sqrt {n}}}
∑
i
=
1
n
a
i
b
≤
1
2
n
(
(
∑
i
=
1
n
a
i
2
)
+
b
2
)
{\displaystyle \textstyle \sum _{\,i\,=\,1}^{\,n}a_{i}\,b\,\leq \,{\frac {1}{2}}{\sqrt {n}}((\textstyle \sum _{\,i\,=\,1}^{\,n}\,a_{i}^{2})+b^{2})}
.
The particular case with
n
=
4
{\displaystyle n\,=\,4}
gives
(
c
1
+
c
2
+
c
3
+
c
4
)
c
0
≤
(
c
0
2
+
c
1
2
+
c
2
2
+
c
3
2
+
c
4
2
)
{\displaystyle (c_{1}+c_{2}+c_{3}+c_{4})\,c_{0}\;\leq \;(c_{0}^{2}+c_{1}^{2}+c_{2}^{2}+c_{3}^{2}+c_{4}^{2})}
.
∑
i
=
1
k
v
i
2
≤
2
∑
i
=
1
k
∑
j
=
1
i
v
j
2
∑
j
=
1
i
(
v
j
−
v
j
−
1
)
2
{\displaystyle \textstyle \sum _{i\,=\,1}^{k}\,v_{i}^{2}\leq \,2\,\textstyle \sum _{i\,=\,1}^{k}\,{\sqrt {\textstyle \sum _{j\,=\,1}^{\,i}\,v_{j}^{2}\;}}\,{\sqrt {\textstyle \sum _{j\,=\,1}^{\,i}(v_{j}-v_{j-1})^{2}}}}
≤
2
∑
i
=
1
k
∑
j
=
1
i
v
j
2
∑
i
=
1
k
∑
j
=
1
i
(
v
j
−
v
j
−
1
)
2
{\displaystyle \leq \,2\,{\sqrt {\textstyle \sum _{i\,=\,1}^{k}\,\textstyle \sum _{j\,=\,1}^{\,i}\,v_{j}^{2}\;}}\,{\sqrt {\textstyle \sum _{i\,=\,1}^{k}\,\textstyle \sum _{j\,=\,1}^{\,i}(v_{j}-v_{j-1})^{2}}}}
=
2
∑
i
=
1
k
(
k
−
i
+
1
)
v
i
2
∑
i
=
1
k
(
k
−
i
+
1
)
(
v
i
−
v
i
−
1
)
2
{\displaystyle =\,2\,{\sqrt {\textstyle \sum _{i\,=\,1}^{k}\,(k-i+1)\,v_{i}^{2}\;}}\,{\sqrt {\textstyle \sum _{i\,=\,1}^{k}\,(k-i+1)(v_{i}-v_{i-1})^{2}}}}
∑
i
=
1
k
v
i
2
≤
2
k
∑
i
=
1
k
v
i
2
∑
i
=
1
k
(
v
i
−
v
i
−
1
)
2
{\displaystyle \textstyle \sum _{i\,=\,1}^{k}\,v_{i}^{2}\leq \,2\,k\,{\sqrt {\textstyle \sum _{i\,=\,1}^{k}\,v_{i}^{2}\;}}\,{\sqrt {\textstyle \sum _{i\,=\,1}^{k}(v_{i}-v_{i-1})^{2}}}}
Now, suppose for some
α
{\displaystyle \alpha }
∑
i
=
1
k
v
i
2
≤
α
k
∑
i
=
1
k
(
v
i
−
v
i
−
1
)
2
{\displaystyle {\sqrt {\textstyle \sum _{i\,=\,1}^{k}\,v_{i}^{2}}}\leq \,\alpha \,k\,{\sqrt {\textstyle \sum _{i\,=\,1}^{k}(v_{i}-v_{i-1})^{2}}}}
v
k
2
≤
2
α
k
∑
i
=
1
k
(
v
i
−
v
i
−
1
)
2
{\displaystyle v_{k}^{2}\;\leq \,2\,\alpha \,k\,\textstyle \sum _{i\,=\,1}^{k}(v_{i}-v_{i-1})^{2}}
So for
i
≤
k
{\displaystyle i\;\leq \;k}
v
i
2
≤
2
α
i
∑
j
=
1
i
(
v
j
−
v
j
−
1
)
2
{\displaystyle v_{i}^{2}\;\leq \,2\,\alpha \,i\,\textstyle \sum _{j\,=\,1}^{i}(v_{j}-v_{j-1})^{2}}
∑
i
=
1
k
v
i
2
≤
2
α
(
∑
i
=
1
k
i
)
∑
j
=
1
k
(
v
j
−
v
j
−
1
)
2
{\displaystyle \textstyle \sum _{i\,=\,1}^{k}\,v_{i}^{2}\;\leq \,2\,\alpha \,(\textstyle \sum _{i\,=\,1}^{k}\,i)\,\textstyle \sum _{j\,=\,1}^{k}(v_{j}-v_{j-1})^{2}}
∑
i
=
1
k
v
i
2
≤
α
k
(
k
+
1
)
∑
i
=
1
k
(
v
i
−
v
i
−
1
)
2
{\displaystyle \textstyle \sum _{i\,=\,1}^{k}\,v_{i}^{2}\;\leq \,\alpha \,\,k(k+1)\,\textstyle \sum _{i\,=\,1}^{k}(v_{i}-v_{i-1})^{2}}
∑
i
=
1
k
v
i
2
≤
α
(
1
+
1
k
)
k
∑
i
=
1
k
(
v
i
−
v
i
−
1
)
2
{\displaystyle {\sqrt {\textstyle \sum _{i\,=\,1}^{k}\,v_{i}^{2}\,}}\;\leq \,{\sqrt {\alpha }}\,{\sqrt {(1+{\tfrac {1}{k}})}}\;k\,{\sqrt {\textstyle \sum _{i\,=\,1}^{k}(v_{i}-v_{i-1})^{2}}}}
∑
i
=
1
k
v
i
2
≤
2
k
∑
i
=
1
k
(
k
−
i
+
1
)
(
v
i
−
v
i
−
1
)
2
{\displaystyle {\sqrt {\textstyle \sum _{i\,=\,1}^{k}\,v_{i}^{2}\;}}\leq \,2\,{\sqrt {k}}\,{\sqrt {\textstyle \sum _{i\,=\,1}^{k}\,(k-i+1)(v_{i}-v_{i-1})^{2}}}}
zzzzzzzzzz
So for
i
≤
k
{\displaystyle i\;\leq \;k}
∑
j
=
1
i
v
j
2
≤
2
∑
j
=
1
i
(
i
−
j
+
1
)
v
j
2
∑
j
=
1
i
(
i
−
j
+
1
)
(
v
j
−
v
j
−
1
)
2
{\displaystyle \textstyle \sum _{j\,=\,1}^{\,i}\,v_{j}^{2}\leq \,2\,{\sqrt {\textstyle \sum _{j\,=\,1}^{\,i}\,(i-j+1)\,v_{j}^{2}\;}}\,{\sqrt {\textstyle \sum _{j\,=\,1}^{\,i}\,(i-j+1)(v_{j}-v_{j-1})^{2}}}}
∑
i
=
1
k
∑
j
=
1
i
v
j
2
≤
2
∑
i
=
1
k
∑
j
=
1
i
(
i
−
j
+
1
)
v
j
2
∑
j
=
1
i
(
i
−
j
+
1
)
(
v
j
−
v
j
−
1
)
2
{\displaystyle \textstyle \sum _{i\,=\,1}^{k}\,\textstyle \sum _{j\,=\,1}^{\,i}\,v_{j}^{2}\leq \,2\,\textstyle \sum _{i\,=\,1}^{k}\,{\sqrt {\textstyle \sum _{j\,=\,1}^{\,i}\,(i-j+1)\,v_{j}^{2}\;}}\,{\sqrt {\textstyle \sum _{j\,=\,1}^{\,i}\,(i-j+1)(v_{j}-v_{j-1})^{2}}}}
∑
i
=
1
k
(
k
−
i
+
1
)
v
i
2
≤
2
k
∑
i
=
1
k
(
k
−
i
+
1
)
v
i
2
∑
i
=
1
k
(
k
−
i
+
1
)
(
v
i
−
v
i
−
1
)
2
{\displaystyle \textstyle \sum _{i\,=\,1}^{k}\,(k-i+1)v_{i}^{2}\leq \,2\,k\,{\sqrt {\textstyle \sum _{i\,=\,1}^{k}\,(k-i+1)\,v_{i}^{2}\;}}\,{\sqrt {\textstyle \sum _{i\,=\,1}^{k}\,(k-i+1)(v_{i}-v_{i-1})^{2}}}}
∑
i
=
1
k
(
k
−
i
+
1
)
v
i
2
≤
2
k
∑
i
=
1
k
(
k
−
i
+
1
)
(
v
i
−
v
i
−
1
)
2
{\displaystyle {\sqrt {\textstyle \sum _{i\,=\,1}^{k}\,(k-i+1)v_{i}^{2}\;}}\leq \,2\,k\,{\sqrt {\textstyle \sum _{i\,=\,1}^{k}\,(k-i+1)(v_{i}-v_{i-1})^{2}}}}
∑
i
=
1
k
v
i
2
≤
4
k
∑
i
=
1
k
(
k
−
i
+
1
)
(
v
i
−
v
i
−
1
)
2
{\displaystyle \textstyle \sum _{i\,=\,1}^{k}\,v_{i}^{2}\leq \,4\,k\,\textstyle \sum _{i\,=\,1}^{k}\,(k-i+1)(v_{i}-v_{i-1})^{2}}
∑
i
=
1
k
v
i
2
≤
2
k
∑
i
=
1
k
(
k
−
i
+
1
)
(
v
i
−
v
i
−
1
)
2
{\displaystyle {\sqrt {\textstyle \sum _{i\,=\,1}^{k}\,v_{i}^{2}\;}}\leq \,2\,{\sqrt {k}}\,{\sqrt {\textstyle \sum _{i\,=\,1}^{k}\,(k-i+1)(v_{i}-v_{i-1})^{2}}}}
xxxxxxxxxxxxxxxx
∑
i
=
1
k
(
k
−
i
+
1
)
v
i
2
≤
2
∑
i
=
1
k
∑
j
=
1
i
(
i
−
j
+
1
)
v
j
2
∑
i
=
1
k
∑
j
=
1
i
(
i
−
j
+
1
)
(
v
j
−
v
j
−
1
)
2
{\displaystyle \textstyle \sum _{i\,=\,1}^{k}\,(k-i+1)v_{i}^{2}\leq \,2\,{\sqrt {\textstyle \sum _{i\,=\,1}^{k}\,\textstyle \sum _{j\,=\,1}^{\,i}\,(i-j+1)\,v_{j}^{2}\;}}\,{\sqrt {\textstyle \sum _{i\,=\,1}^{k}\,\textstyle \sum _{j\,=\,1}^{\,i}\,(i-j+1)(v_{j}-v_{j-1})^{2}}}}
∑
i
=
1
k
(
k
−
i
+
1
)
v
i
2
≤
2
∑
i
=
1
k
∑
j
=
1
i
(
i
−
j
+
1
)
v
j
2
∑
i
=
1
k
∑
j
=
1
i
(
i
−
j
+
1
)
(
v
j
−
v
j
−
1
)
2
{\displaystyle \textstyle \sum _{i\,=\,1}^{k}\,(k-i+1)v_{i}^{2}\leq \,2\,{\sqrt {\textstyle \sum _{i\,=\,1}^{k}\,\textstyle \sum _{j\,=\,1}^{\,i}\,(i-j+1)\,v_{j}^{2}\;}}\,{\sqrt {\textstyle \sum _{i\,=\,1}^{k}\,\textstyle \sum _{j\,=\,1}^{\,i}\,(i-j+1)(v_{j}-v_{j-1})^{2}}}}
≤
2
k
∑
i
=
1
k
(
k
−
i
+
1
)
v
i
2
∑
i
=
1
k
(
v
i
−
v
i
−
1
)
2
{\displaystyle \leq \,2\,{\sqrt {k}}{\sqrt {\textstyle \sum _{i\,=\,1}^{k}\,(k-i+1)\,v_{i}^{2}\;}}\,{\sqrt {\textstyle \sum _{i\,=\,1}^{k}\,(v_{i}-v_{i-1})^{2}}}}
∑
i
=
1
k
v
i
2
≤
2
k
∑
i
=
1
k
v
i
2
∑
i
=
1
k
(
v
i
−
v
i
−
1
)
2
{\displaystyle \textstyle \sum _{i\,=\,1}^{k}\,v_{i}^{2}\leq \,2\,k\,{\sqrt {\textstyle \sum _{i\,=\,1}^{k}\,v_{i}^{2}\;}}\,{\sqrt {\textstyle \sum _{i\,=\,1}^{k}(v_{i}-v_{i-1})^{2}}}}
∑
i
=
1
k
v
i
2
≤
2
k
∑
i
=
1
k
(
v
i
−
v
i
−
1
)
2
{\displaystyle {\sqrt {\textstyle \sum _{i\,=\,1}^{k}\,v_{i}^{2}\;}}\leq \,2\,k\,{\sqrt {\textstyle \sum _{i\,=\,1}^{k}(v_{i}-v_{i-1})^{2}}}}