Department of Mathematics, Faculty of Science, Ferhat Abbas-Sétif University 1

Numerical analysis 1
R. Z

𝜑1
ℎ1 =
∥ 𝜑1 ∥

𝑘−1
𝑢𝑘
ℎ𝑘 = , 𝑘 = 2, 3, … , 𝑛 𝑜ù 𝑢𝑘 = 𝜑𝑘 − ∑ < 𝜑𝑘 , ℎ𝑖 > ℎ𝑖 .
{ ∥ 𝑢𝑘 ∥
𝑖=1

This algorithm is called the Gram-Schmidt process (orthogonality).

3.6 Continuous Least Squares Approximation

Let’s take the Pre-Hilbert space 𝐸 = 𝐶([𝑎, 𝑏] ) and

𝑏
∀ 𝑓, 𝑔 ∈ 𝐸 ∶ < 𝑓, 𝑔 > = ∫ 𝜔(𝑥)𝑓(𝑥)𝑔(𝑥)𝑑𝑥
𝑎

𝑏
2 2
∀ 𝑓 ∈ 𝐸 ∶ ∥ 𝑓 ∥ = ∫ 𝜔(𝑥)𝑓 (𝑥)𝑑𝑥
𝑎

Where 𝜔(𝑥) ≥ 0, ∀𝑥 ∈ [𝑎, 𝑏], the function 𝜔 is called “Weight function”. In practice,
we take 𝜔 ≡ 1.

Let 𝐸𝑛 be a vector subspace of 𝐸 with dim 𝐸𝑛 = 𝑛 and let {𝜑1 , 𝜑2 , … , 𝜑𝑛 } be a basis

of 𝐸𝑛 . So the best approximation 𝜑 ∗ ∈ 𝐸𝑛 of an element 𝑓 ∈ 𝐸 exists and it is unique
(according to theorem 3.2). Let 𝜑 ∗ = ∑𝑛𝑖=1 𝑎𝑖∗ 𝜑𝑖 .

We have < 𝑓 − 𝜑 ∗ , 𝜑𝑘 > = 0, ∀ 𝑘 = 1, 2, … , 𝑛.

𝑏 𝑛

⟺ ∫ 𝜔(𝑥) [𝑓 − ∑ 𝑎𝑖∗ 𝜑𝑖 ] (𝑥)𝜑𝑘 (𝑥)𝑑𝑥 = 0 ∀ 𝑘 = 1, 2, … , 𝑛 (𝟏)

𝑎 𝑖=1

Remark 3.3

Pose ∥ 𝑓 − 𝜑 ∗ ∥2 = min ∥ 𝑓 − 𝜑 ∥2 = min ∥ 𝑓 − ∑𝑛𝑖=1 𝑎𝑖 𝜑𝑖 ∥2

𝜑∈𝐹 𝑎𝑖

𝑏 𝑛 2

= min ∫ 𝜔(𝑥) [𝑓(𝑥) − ∑ 𝑎𝑖 𝜑𝑖 (𝑥)] 𝑑𝑥

𝑎𝑖
𝑎 𝑖=1

9
 Department of Mathematics, Faculty of Science, Ferhat Abbas-Sétif University 1
Numerical analysis 1
R. Z

= min Ψ(𝑎1 , 𝑎2 , … , 𝑎𝑛 )
𝑎𝑖

= Ψ(𝑎1∗ , 𝑎2∗ , … , 𝑎𝑛∗ )

The quadratic function Ψ is convex then, a necessary and sufficient condition for it to
admit a minimum in a point (𝑎1 , 𝑎2 , … , 𝑎𝑛 ) is:
𝜕Ψ
(𝑎 , 𝑎 , … , 𝑎𝑛 ) = 0, ∀ 𝑖 = 1, 2, … , 𝑛.
𝜕𝑎𝑖 1 2
Note that this last relationship is equivalent to the condition (𝟏).

Special case and matrix representation of the relationship (𝟏):

Let 𝐸𝑛 = ℙ𝑛 [𝑥] (the vector space of polynomials of degree ≤ 𝑛 ) and let

𝐵 = {1, 𝑥, 𝑥 2 , … , 𝑥 𝑛 } be the canonical base of 𝐸𝑛 (dim 𝐸𝑛 = 𝑛 + 1). So the best

polynomial approximation 𝜑 ∗ = 𝑃𝑛∗ ∈ 𝐸𝑛 of an element 𝑓 ∈ 𝐸𝑛 exists and it is unique

(according to theorem 3.2).

Let 𝑃𝑛∗ (𝑥) = ∑𝑛𝑖=0 𝑎𝑖∗ 𝑥 𝑖 , 𝑥 ∈ [𝑎, 𝑏]. If we take 𝜔 ≡ 1 into the relationship (𝟏) then,

we determine 𝑃𝑛∗ by the resolution of the following equivalent system (𝑆) :

𝑏 𝑏 𝑏 𝑏 𝑏
∫𝑎 1𝑑𝑥 ∫𝑎 𝑥𝑑𝑥 ∫𝑎 𝑥 2 𝑑𝑥 ∫𝑎 𝑥 𝑛 𝑑𝑥 𝑎0∗ ∫𝑎 𝑓(𝑥)𝑑𝑥
𝑏 𝑏 𝑏 𝑏 𝑏
∫𝑎 𝑥𝑑𝑥 ∫𝑎 𝑥 2 𝑑𝑥 ∫𝑎 𝑥 3 𝑑𝑥 ⋯ ∫𝑎 𝑥 𝑛+1 𝑑𝑥 𝑎∗
( 1) = ∫𝑎 𝑥𝑓(𝑥)𝑑𝑥
⋮ ⋮ ⋮ ⋮ ⋮ ⋮
𝑏 𝑛 𝑏 𝑛+1 𝑏 𝑛+2 𝑏 2𝑛 𝑎𝑛∗ 𝑏 𝑛
∫
(𝑎 𝑥 𝑑𝑥 ∫𝑎
𝑥 𝑑𝑥 ∫𝑎
𝑥 𝑑𝑥 ∫𝑎
𝑥 𝑑𝑥 ) (∫𝑎 𝑥 𝑓(𝑥)𝑑𝑥)

This system admits a unique solution: (𝑎0∗ , 𝑎1∗ , … , 𝑎𝑛∗ )𝑇 ∈ ℝ𝑛+1 .

Example 3.1
Determine the best polynomial approximation of degree 1 in the least squares sense of

the function 𝑓 defined by 𝑓(𝑥) = √𝑥 in [0,1].

10
 Department of Mathematics, Faculty of Science, Ferhat Abbas-Sétif University 1
Numerical analysis 1
R. Z

Method 1:
Let us take 𝑃1 (𝑥) = 𝑎𝑥 + 𝑏, we have {𝜑1 = 1, 𝜑2 = 𝑥} the canonical basis of the space
of polynomials of degree1.

𝑃1 Best approximation of 𝑓 ⟺ < 𝑓 − 𝑃1 , 𝜑𝑖 > = 0, ∀ 𝑖 = 1, 2

< √𝑥 − 𝑎𝑥 − 𝑏, 1 > = 0
⟺{ (∎)
< √𝑥 − 𝑎𝑥 − 𝑏, 𝑥 > = 0
1

∫(√𝑥 − 𝑎𝑥 − 𝑏)(1)𝑑𝑥 = 0
0
⟺ 1

∫(√𝑥 − 𝑎𝑥 − 𝑏)(𝑥)𝑑𝑥 = 0
{0
2 𝑥2
[ 𝑥√𝑥 − 𝑎 − 𝑏𝑥]10 = 0
⟺ 3 2
2 2 𝑥3 𝑥2 1
{[5 𝑥 √𝑥 − 𝑎 3 − 𝑏 2 ]0 = 0
2 𝑎
− −𝑏 =0
⟺{ 3 2
2 𝑎 𝑏
− − =0
5 3 2
3𝑎 + 6𝑏 = 4
⟺{
10𝑎 + 15𝑏 = 12
4
𝑎=
⟺{ 5
4
𝑏=
15
So the best polynomial approximation of degree 1 of 𝑓 in the least squares sense of
4 4
the function 𝑓 defined by 𝑓(𝑥) = √𝑥 in [0,1] is 𝑃1 (𝑥) = 𝑥 + .
5 15

Method 2
1
Let’s pose Ψ(𝑎, 𝑏) =∥ 𝑓 − 𝑃1 ∥2 =∥ √𝑥 − 𝑎𝑥 − 𝑏 ∥2 = ∫0 (√𝑥 − 𝑎𝑥 − 𝑏)2 𝑑𝑥

=< √𝑥 − 𝑎𝑥 − 𝑏, √𝑥 − 𝑎𝑥 − 𝑏 >
11
 Department of Mathematics, Faculty of Science, Ferhat Abbas-Sétif University 1
Numerical analysis 1
R. Z

We have
𝜕Ψ
(𝑎, 𝑏) = 0 ⟺ −2 < √𝑥 − 𝑎𝑥 + 𝑏, 𝑥 > = 0
𝜕𝑎
and
𝜕Ψ
(𝑎, 𝑏) = 0 ⟺ −2 < √𝑥 − 𝑎𝑥 + 𝑏, 1 > = 0
𝜕𝑏
𝜕Ψ 𝜕Ψ
i.e., (𝑎, 𝑏) = 0 and (𝑎, 𝑏) = 0 ⟺(∎)
𝜕𝑎 𝜕𝑏

Continuing the calculation, we find the same previous result.

Note: In an interval of the form [−𝒂, 𝒂] (symmetric to the origin), if 𝒇 is an even (odd)
function then the polynomial approximation of 𝒇 is even (odd).

3.7 Discrete Least Squares Approximation

Let 𝐸 be a Pre-Hilbert space of functions defined in [𝑎, 𝑏] and let 𝐹𝑛+1 be a vector
subspace of 𝐸 such that dim 𝐹𝑛+1 = 𝑛 + 1 and {𝜑0 , 𝜑1 , … , 𝜑𝑛 } is a basis of 𝐹𝑛+1 .

Let 𝑓 be an element of 𝐸 defined at (𝑚 + 1) points 𝑥𝑖 ∈ [𝑎, 𝑏] with 𝑚 > 𝑛.

Then the element 𝜑 ∗ = ∑𝑛𝑖=0 𝑎𝑖∗ 𝜑𝑖 is the best approximation in 𝐹𝑛+1 of 𝑓 if and
only if < 𝑓 − 𝜑 ∗ , 𝜑ℓ > = 0, ∀ ℓ = 0, 1, … , 𝑛.

But 𝑓 is only defined in (𝑚 + 1) points 𝑥𝑖 in [𝑎, 𝑏] then, the image vector

𝑢 = (𝑓(𝑥0 ), 𝑓(𝑥2 ), … 𝑓(𝑥𝑚 ))𝑇 ∈ ℝ𝑚+1 . Hence the problem becomes as follows:

Find the element 𝜑 ∗ ∈ 𝐹𝑛+1 which is the best approximation of the vector
𝑢 ∈ ℝ𝑚+1 .

We define the inner (scalar) product and the Euclidean norm in 𝐸 as follows:
𝑚
∀ 𝑓, 𝑔 ∈ 𝐸 ∶ < 𝑓, 𝑔 > = ∑ 𝜔(𝑥𝑖 )𝑓(𝑥𝑖 )𝑔(𝑥𝑖 )
𝑖=0
𝑚

∥ 𝑔 ∥2 = ∑ 𝜔(𝑥𝑖 )𝑔2 (𝑥𝑖 )

𝑖=0

12
 Department of Mathematics, Faculty of Science, Ferhat Abbas-Sétif University 1
Numerical analysis 1
R. Z

Therefore 𝜑 ∗ = ∑𝑛𝑖=0 𝑎𝑖∗ 𝜑𝑖 is the best approximation in 𝐹𝑛+1 of 𝑓 ⟺

𝑛 𝑚 𝑛

<𝑓− ∑ 𝑎𝑖∗ 𝜑𝑖 , 𝜑ℓ > = ∑ 𝜔(𝑥𝑘 ) [𝑓(𝑥𝑘 ) − ∑ 𝑎𝑖∗ 𝜑𝑖 (𝑥𝑘 )] 𝜑ℓ (𝑥𝑘 ) = 0, ∀ ℓ = 0,1, … , 𝑛. (𝟐)
𝑖=1 𝑘=0 𝑖=0

Remark 3.4
The condition (𝟐) can be found using the following equivalent condition
𝜕Ψ
(𝑎 , 𝑎 , … , 𝑎𝑛 ) = 0, ∀ 𝑖 = 0, 1, … , 𝑛
𝜕𝑎𝑖 0 1
Such as Ψ(𝑎0 , 𝑎1 , … , 𝑎𝑛 ) =∥ 𝑓 − 𝜑 ∥2 , 𝜑 ∈ 𝐹𝑛+1

i.e., by posing Ψ(𝑎0 , 𝑎1 , … , 𝑎𝑛 ) =∥ 𝑓 − 𝜑 ∥2 then,

𝑚 𝑛 2

∥ 𝑓 − 𝜑 ∗ ∥2 = ∑ 𝜔(𝑥𝑘 ) [𝑓(𝑥𝑘 ) − ∑ 𝑎∗𝑖 𝜑𝑖 (𝑥𝑘 )] = min ∥ 𝑓 − 𝜑 ∥2

𝜑∈𝐹𝑛+1
𝑘=0 𝑖=0

𝑛 𝑛 2

= min ∑ 𝜔(𝑥𝑘 ) [𝑓(𝑥𝑘 ) − ∑ 𝑎𝑖 𝜑𝑖 (𝑥𝑘 )]

𝑎𝑖
𝑖=1 𝑖=0

= min Ψ(𝑎0 , 𝑎1 , … , 𝑎𝑛 )
𝑎𝑖

= Ψ(𝑎0∗ , 𝑎1∗ , … , 𝑎𝑛∗ ).

Special case and matrix representation of the relationship (𝟐)

Let 𝐹𝑛+1 = ℙ𝑛 [𝑥] with 𝐵 = {1, , 𝑥, 𝑥 2 , … , 𝑥 𝑛 } the canonical basis of 𝐹𝑛+1 .

As in the continuous case, if we take 𝜔 ≡ 1 into the relationship (𝟐) then we

determine 𝑃𝑛∗ by the resolution of the following equivalent system (𝑆′):

13
 Department of Mathematics, Faculty of Science, Ferhat Abbas-Sétif University 1
Numerical analysis 1
R. Z

∑𝑚
𝑘=0 1
∑𝑚
𝑘=0 𝑥𝑘 ∑𝑚𝑘=0 𝑥𝑘
2 ∑𝑚𝑘=0 𝑥𝑘
𝑛
𝑎0∗ ∑𝑚𝑘=0 𝑓(𝑥𝑘 )
𝑚
∑𝑘=0 𝑥𝑘 ∑𝑘=0 𝑥𝑘2
𝑚 𝑚 3 𝑚
∑𝑘=0 𝑥𝑘 ⋯ ∑𝑘=0 𝑥𝑘𝑛+1
𝑎 ∗ ∑ 𝑚
𝑥 𝑓(𝑥𝑘 )
( 1 ) = ( 𝑘=0 𝑘 )
⋮ ⋮ ⋮ ⋮ ⋮ ⋮
𝑚 𝑛
(∑𝑘=0 𝑥𝑘 ∑𝑘=0 𝑥𝑘𝑛+1
𝑚
∑𝑚
𝑘=0 𝑥𝑘
𝑛+2 ∑𝑚 2𝑛
𝑘=0 𝑥𝑘 )
𝑎𝑛∗ ∑𝑚 𝑛
𝑘=0 𝑥𝑘 𝑓(𝑥𝑘 )

This system admits also a unique solution: (𝑎0∗ , 𝑎1∗ , … , 𝑎𝑛∗ )𝑇 ∈ ℝ𝑛+1 .

Example 3.2
Determine the best least squares polynomial approximation of degree 1 of the function
𝑓 defined by:
𝑘 0 1 2
𝑥𝑘 −1 0 2
𝑓(𝑥𝑘 ) 1 2 4

Take 𝑃1 (𝑥) = 𝑎𝑥 + 𝑏, we have {𝜑0 = 1, 𝜑1 = 𝑥} the canonical basis of the

polynomials of degree 1 vector space.

Method 1:
We have 𝑃1 is the Best approximation of 𝑓 ⟺ < 𝑓 − 𝑃1 , 𝜑𝑙 > = 0, ∀ 𝑙 = 0, 1.
< 𝑓(𝑥) − 𝑃1 (𝑥), 1 > = 0
⟺{
< 𝑓(𝑥) − 𝑃1 (𝑥), 𝑥 > = 0
2

∑ (𝑓(𝑥𝑘 ) − 𝑎𝑥𝑘 − 𝑏)(1) = 0

𝑘=0
⟺ 2 (∴)
∑ (𝑓(𝑥𝑘 ) − 𝑎𝑥𝑘 − 𝑏)(𝑥𝑘 ) = 0
{𝑘=0
(1 + 𝑎 − 𝑏)(1) + (2 − 0 − 𝑏)(1) + (4 − 2𝑎 − 𝑏)(1) = 0
⟺{
(1 + 𝑎 − 𝑏)(−1) + (2 − 0 − 𝑏)(0) + (4 − 2𝑎 − 𝑏)(2) = 0

𝑎 + 3𝑏 = 7
⟺{
3𝑎 + 𝑏 = 7
7
⟺𝑎 =𝑏=
4

14
 Department of Mathematics, Faculty of Science, Ferhat Abbas-Sétif University 1
Numerical analysis 1
R. Z

7 7
Then 𝑃1 (𝑥) = 𝑥 + is the best least squares approximation of degree 1 of the
4 4
function 𝑓.

Method 2: (using the remark 3.4)

Let us consider Ψ(𝑎, 𝑏) =∥ 𝑓 − 𝑃1 ∥2
2

= ∑ [𝑓(𝑥𝑘 ) − 𝑎𝑥𝑘 − 𝑏]2

𝑘=0
𝜕Ψ 𝜕Ψ
Taking (𝑎, 𝑏) = 0 and (𝑎, 𝑏) = 0, we obtain exactly the condition (∴).
𝜕𝑎 𝜕𝑏

15