Preconditioned finite element method: the Poisson problem on the square Consider the Poisson problem on Ω = [0, 1] × [0, 1]. Let τ 0 be the trian- gulation of Ω obtained by tracing the line through the points (1, 0) and (0,1).
Note that h 0 = √
2. Let τ j , V j , Π j , j = 1, 2, . . ., be the triangulations of Ω, the subspaces of V = H 0 1 (Ω) and the interpolating operators defined starting from τ 0 via the rule indicated in (toe 1f). Note that diam (τ j ) = h j = 2 − j √
2.
Note also that the number of the inner nodes of τ j is n 2 where n = 2 j − 1.
We call them x j,1 = 2 1j(1, 1), . . ., x j,2j− 1 = 2 1
j(2 j − 1, 1), x j,2j = 2 1j(1, 2), . . ., x j,(2j− 1)
2 = 2 1j(2 j − 1, 2 j − 1), and consider the corresponding elements of the Lagrange basis ϕ j,k , k = 1, . . . , (2 j − 1) 2 , of V j .
− 1 = 2 1
j(2 j − 1, 1), x j,2j = 2 1j(1, 2), . . ., x j,(2j− 1)
2 = 2 1j(2 j − 1, 2 j − 1), and consider the corresponding elements of the Lagrange basis ϕ j,k , k = 1, . . . , (2 j − 1) 2 , of V j .
(1, 2), . . ., x j,(2j− 1)
2 = 2 1j(2 j − 1, 2 j − 1), and consider the corresponding elements of the Lagrange basis ϕ j,k , k = 1, . . . , (2 j − 1) 2 , of V j .
(2 j − 1, 2 j − 1), and consider the corresponding elements of the Lagrange basis ϕ j,k , k = 1, . . . , (2 j − 1) 2 , of V j .
Exploiting the Lagrange basis. If u ϕ is fixed in H 1 (Ω) such that u ϕ | ∂Ω = ϕ, then the scalars (w j ) k solving the linear system
(2
j− 1)
2X
k=1
(w j ) k
Z
Ω ∇ϕ j,k ∇ϕ j,i = F (ϕ j,i ) = Z
Ω
f ϕ j,i − Z
Ω ∇u ϕ ∇ϕ j,i , i = 1, . . . , (2 j −1) 2 , define a function w j = P(w j ) k ϕ j,k ∈ V j which approximates w ∈ V = H 0 1 (Ω), a(w, v) = F (v), ∀ v ∈ V, and thus a function u j = u ϕ + w j which approximates the solution u = u ϕ + w of the variational version of the Poisson differential problem −∆u = f, x ∈ Ω, u = ϕ, x ∈ ∂Ω.
Let A be the coefficient matrix of such system. We know that it is positive definite (because R
Ω ∇u∇v is coercive on H 0 1 (Ω)) and that, for each row, there are at most seven nonzero entries (just look at τ j and at the support of the ϕ j,i , i generic). Let us compute its entries a ik ,
a ik = Z
Ω ∇ϕ j,k ∇ϕ j,i = Z
s(ϕ
j,k)∩s(ϕ
j,i) ∇ϕ j,k ∇ϕ j,i .
First, draw a zoom of τ j around the inner node i, so to see only the nodes linked to i, i.e. i − n, i − n + 1, i − 1, i + 1, i + n − 1, i + n. Call T 1 the triangle of τ j
whose verteces are i − 1, i, i + n − 1, and T 2 , T 3 , T 4 , T 5 , T 6 the other triangles of τ j having i as a vertex, in a clockwise order. Here below are reported the values of ∇ϕ j,i (x) on these triangles, unless the factor 1/δ j , δ j := 1/2 j :
T 1 T 2 T 3 T 4 T 5 T 6
(1, 0) (0, −1) (−1, −1) (−1, 0) (0, 1) (1, 1)
.
Observe that the value of ∇ϕ j,i+n−1 on T 1 is equal to the value of ∇ϕ j,i on T 5 ; analogously, the value of ∇ϕ j,i−1 on T 6 is equal to the value of ∇ϕ j,i on T 4 , and so on. Finally, observe that all the triangles T k , k = 1, . . . , 6, have area equal to δ j 2 /2.
It follows that, for i = 1, . . . , n 2 : a ii = R
s(ϕ
j,i) ∇ϕ j,i ∇ϕ j,i = R
∪
6k=1
T
kk∇ϕ j,i k 2
= R
T
1k∇ϕ j,i k 2 + R
T
2k∇ϕ j,i k 2 + R
T
3k∇ϕ j,i k 2 + R
T
4k∇ϕ j,i k 2 + R
T
5k∇ϕ j,i k 2 + R
T
6k∇ϕ j,i k 2
= δ 12 j
δ
2j2 + δ 1
2j
δ
j22 + δ 2
2j
δ
2j2 + δ 1
2j
δ
2j2 + δ 1
2j
δ
2j2 + δ 2
2j
δ
j22 = 4;
for i = 2, . . . , n 2 , i 6= n + 1, . . . , (n − 1)n + 1:
a i,i−1 = R
s(ϕ
j,i−1)∩s(ϕ
j,i) ∇ϕ j,i−1 ∇ϕ j,i = R
T
1∪ T
6∇ϕ j,i−1 ∇ϕ j,i
= R
T
1∇ϕ j,i−1 ∇ϕ j,i + R
T
6∇ϕ j,i−1 ∇ϕ j,i
= δ
2 j
2 1
δ
j(−1, −1) δ 1j(1, 0) + δ
2 j
2 1
δ
j(−1, 0) δ 1j(1, 1) = −1;
for i = n, . . . , n 2 , i 6= n, 2n, . . . , n 2 : a i,i−n+1 = R
s(ϕ
j,i−n+1)∩s(ϕ
j,i) ∇ϕ j,i−n+1 ∇ϕ j,i = R
T
4∪ T
5∇ϕ j,i−n+1 ∇ϕ j,i
= R
T
4∇ϕ j,i−n+1 ∇ϕ j,i + R
T
5∇ϕ j,i−n+1 ∇ϕ j,i
= δ
2 j
2 1
δ
j(0, −1) δ 1j(−1, 0) + δ
2 j
2 1 δ
j(1, 0) δ 1
j
(0, 1) = 0;
for i = n + 1, . . . , n 2 : a i,i−n = R
s(ϕ
j,i−n)∩s(ϕ
j,i) ∇ϕ j,i−n ∇ϕ j,i = R
T
5∪ T
6∇ϕ j,i−n ∇ϕ j,i
= R
T
5∇ϕ j,i−n ∇ϕ j,i + R
T
6∇ϕ j,i−n ∇ϕ j,i
= δ
2 j
2 1
δ
j(−1, −1) δ 1j(0, 1) + δ
2 j
2 1
δ
j(0, −1) δ 1j(1, 1) = −1;
and finally, for i = k + 1, . . . , n 2 : a i,i−k = 0, ∀k 6= 0, 1, n − 1, n, because for such values of k the measure of the set s(ϕ j,i−k ) ∩ s(ϕ j,i ) is zero.
Then, since a ik = a ki , ∀ i, k, we can conclude that A is a n × n block matrix of the form
A =
B −I
−I B −I
−I . .. ...
. .. B −I
−I B
whose diagonal blocks are all equal to the following n × n matrix B,
B =
4 −1
−1 4 −1
−1 . .. ...
. .. 4 −1
−1 4
,
where n = 2 j − 1.
Eigenvalues of A. Now let us compute the eigenvalues of A (we already know that they are real and positive). Let v k be the n × 1 vector whose i-th entry is sin(ikπ/(n + 1)), 1 ≤ i, k ≤ n. Then
Bv k = [4 − 2 cos(kπ/(n + 1))]v k , k = 1, . . . , n.
Moreover, if we set [·] = [4 − 2 cos(kπ/(n + 1))], then
B −I
−I B . ..
. .. ... −I
−I B
α 1 v k
α 2 v k
.. . α n v k
= λ
α 1 v k
α 2 v k
.. . α n v k
iff α 1 Bv k − α 2 v k = λα 1 v k
−α 1 v k + α 2 Bv k − α 3 v k = λα 2 v k
· · ·
−α n−1 v k + α n Bv k = λα n v k
iff α 1 [·]v k − α 2 v k = λα 1 v k
−α 1 v k + α 2 [·]v k − α 3 v k = λα 2 v k
· · ·
−α n−1 v k + α n [·]v k = λα n v k
iff
[·] −1
−1 [·] . ..
. .. ... −1
−1 [·]
α 1
α 2
.. . α n
= λ
α 1
α 2
.. . α n
,
and the latter equation is verified for λ = [·] − 2 cos(sπ/(n + 1)) and α r = sin(rsπ/(n + 1)), r = 1, . . . , n (s = 1, . . . , n). So, the eigenvalues of A are:
4 − 2(cos kπ
n + 1 − cos sπ
n + 1 ) = 4 − 2(cos kπ
2 j + cos sπ
2 j ), 1 ≤ k, s ≤ n = 2 j − 1.
Thus
µ 2 (A) = 1 + cos(π/(n + 1))
1 − cos(π/(n + 1)) = 1 + cos(π/(2 j ))
1 − cos(π/(2 j )) = O(n 2 ) = O((2 j ) 2 ), where µ 2 (A) denotes the condition number of A in the 2-norm. (Recall that, since A is positive definite, µ 2 (A) is simply the ratio of the greatest and the smallest eigenvalues of A).
For example, if j = 2, then A is a 9 × 9 matrix and
µ 2 (A) = 1 + cos(π/4)
1 − cos(π/4) = 2 + √ 2 2 − √
2 = 3 + 2 √ 2.
If j = 3, A is a 49 × 49 matrix, and µ 2 (A) ≈ 25. If j = 4, A is a 225 × 225 matrix, and µ 2 (A) ≈ 103. And so on.
Exploiting the hierarchical basis. Consider now the hierarchical basis ˜ ϕ j,k , k = 1, . . . , (2 j − 1) 2 , of V j . If u ϕ is fixed in H 1 (Ω) such that u ϕ | ∂Ω = ϕ, then the scalars (w ˜ j ) k solving the linear system
(2
j− 1)
2X
k=1
(w ˜ j ) k
Z
Ω ∇ ˜ ϕ j,k ∇ ˜ ϕ j,i = F ( ˜ ϕ j,i ) = Z
Ω
f ˜ ϕ j,i − Z
Ω ∇u ϕ ∇ ˜ ϕ j,i , i = 1, . . . , (2 j −1) 2 ,
define a function w j = P (w ˜ j ) k ϕ ˜ j,k ∈ V j which approximates w ∈ V = H 0 1 (Ω),
a(w, v) = F (v), ∀ v ∈ V, and thus a function u j = u ϕ + w j which approximates
the solution u = u ϕ + w of the variational version of the Poisson differential
problem −∆u = f, x ∈ Ω, u = ϕ, x ∈ ∂Ω.
Let ˜ A be the coefficient matrix of such system. We know that it is positive definite (because R
Ω ∇u∇v is coercive on H 0 1 (Ω)). Let us compute its entries
˜ a ik ,
˜ a ik =
Z
Ω ∇ ˜ ϕ j,k ∇ ˜ ϕ j,i = Z
s( ˜ ϕ
j,k)∩s( ˜ ϕ
j,i) ∇ ˜ ϕ j,k ∇ ˜ ϕ j,i . and, possibly, its eigenvalues.
j = 1: ˜ A is a 1 × 1 matrix.
˜
ϕ 11 = ϕ 11 ⇒ ˜ A = A = [4]. Eigenvalues: 4.
j = 2: ˜ A is a 9 × 9 matrix.
Note that δ 2 = 2 − 1 δ 1 = 2 − 2 δ 0 , δ 0 = 1. Assume ˜ ϕ 2,s = ψ 1,s = ϕ 2,s , s = 1, 2, 3, 4, 6, 7, 8, 9, ˜ ϕ 2,5 = ϕ 1,1 . Then, for r, s ∈ {1, 2, 3, 4, 6, 7, 8, 9}:
˜ a rs =
Z
s(ψ
1,s)∩s(ψ
1,r) ∇ψ 1,s ∇ψ 1,r = Z
s(ϕ
2,s)∩s(ϕ
2,r) ∇ϕ 2,s ∇ϕ 2,r = a rs . Moreover, if ϕ = ϕ 11 :
˜
a 55 = R
s(ϕ
11) ∇ϕ 11 ∇ϕ 11
= R
T
1ϕ1 δ
1(1, 0) δ 1
1
(1, 0) + R
T
2ϕ1
δ
1(0, −1) δ 11(0, −1) + R
T
3ϕ1
δ
1(−1, −1) δ 11(−1, −1) + R
T
4ϕ1
δ
1(−1, 0) δ 11(−1, 0) + R
T
5ϕ1 δ
1(0, 1) δ 1
1
(0, 1) + R
T
6ϕ1 δ
1(1, 1) δ 1
1
(1, 1)
= 4 = a 55 ;
if ϕ = ϕ 11 and ψ = ψ 1,s , s ∈ {1, 2, 3, 4, 6, 7, 8, 9}:
˜ a 5,s =
Z
s(ψ)∩s(ϕ) ∇ψ∇ϕ = s = 1 : = R
T
1ψ1 δ
2(1, 0) δ 1
1
(0, 0) + R
T
2ψ1
δ
2(0, −1) δ 11(1, 1) + R
T
3ψ1
δ
2(−1, −1) δ 11(1, 1) + R
T
4ψ1
δ
2(−1, 0) δ 11(1, 1) + R
T
5ψ1 δ
2(0, 1) δ 1
1
(0, 0) + R
T
6ψ1 δ
2(1, 1) δ 1
1
(0, 0)
= −2δ 2 /δ 1 , s = 2 : = R
T
1ψ1 δ
2(1, 0) δ 1
1
(1, 1) + R
T
2ψ1
δ
2(0, −1) δ 11(1, 1) + R
T
3ψ1
δ
2(−1, −1) δ 11(0, 1) + R
T
4ψ1
δ
2(−1, 0) δ 11(0, 1) + R
T
5ψ1 δ
2(0, 1) δ 1
1
(0, 1) + R
T
6ψ1 δ
2(1, 1) δ 1
1
(1, 1)
= δ 2 /δ 1 , s = 3 : = R
T
1ψ1
δ
2(1, 0) δ 11(0, 1) + R
T
2ψ1
δ
2(0, −1) δ 11(−1, 0) + R
T
3ψ1
δ
2(−1, −1) δ 11(−1, 0) + R
T
4ψ1
δ
2(−1, 0) δ 11(−1, 0) + R
T
5ψ1 δ
2(0, 1) δ 1
1
(0, 1) + R
T
6ψ1 δ
2(1, 1) δ 1
1
(0, 1)
= 2δ 2 /δ 1 , s = 4 : = R
T
1ψ1
δ
2(1, 0) δ 11(1, 0) + R
T
2ψ1
δ
2(0, −1) δ 11(1, 0) + R
T
3ψ1
δ
2(−1, −1) δ 11(1, 0) + R
T
4ψ1
δ
2(−1, 0) δ 11(1, 1) + R
T
5ψ1 δ
2(0, 1) δ 1
1
(1, 1) + R
T
6ψ1 δ
2(1, 1) δ 1
1
(1, 1)
= δ 2 /δ 1 ,
s = 6 : = R
T
1ψ1 δ
2(1, 0) δ 1
1
(−1, −1) + R
T
2ψ1
δ
2(0, −1) δ 11(−1, −1) + R
T
3ψ1
δ
2(−1, −1) δ 11(−1, −1) + R
T
4ψ1
δ
2(−1, 0) δ 11(−1, 0) + R
T
5ψ1
δ
2(0, 1) δ 11(−1, 0) + R
T
6ψ1
δ
2(1, 1) δ 11(−1, 0)
= δ 2 /δ 1 , s = 7 : = R
T
1ψ1 δ
2(1, 0) δ 1
1
(1, 0) + R
T
2ψ1
δ
2(0, −1) δ 11(0, −1) + R
T
3ψ1
δ
2(−1, −1) δ 11(0, −1) + R
T
4ψ1
δ
2(−1, 0) δ 11(0, −1) + R
T
5ψ1 δ
2(0, 1) δ 1
1
(1, 0) + R
T
6ψ1 δ
2(1, 1) δ 1
1
(1, 0)
= 2δ 2 /δ 1 , s = 8 : = R
T
1ψ1 δ
2(1, 0) δ 1
1
(0, −1) + R
T
2ψ1
δ
2(0, −1) δ 11(0, −1) + R
T
3ψ1
δ
2(−1, −1) δ 11(−1, −1) + R
T
4ψ1
δ
2(−1, 0) δ 11(−1, −1) + R
T
5ψ1 δ
2(0, 1) δ 1
1
(−1, −1) + R
T
6ψ1 δ
2(1, 1) δ 1
1
(0, −1)
= δ 2 /δ 1 , s = 9 : = R
T
1ψ1
δ
2(1, 0) δ 11(−1, −1) + R
T
2ψ1
δ
2(0, −1) δ 11(0, 0) + R
T
3ψ1
δ
2(−1, −1) δ 11(0, 0) + R
T
4ψ1
δ
2(−1, 0) δ 11(0, 0) + R
T
5ψ1 δ
2(0, 1) δ 1
1
(−1, −1) + R
T
6ψ1 δ
2(1, 1) δ 1
1
(−1, −1)
= −2δ 2 /δ 1 .
So, for j = 2, the matrix ˜ A differs from A only by the fifth row and the fifth column (note that the submatrix of ˜ A formed by the entry ˜ a 55 is equal to ˜ A, j = 1).
Here below the matrices A and ˜ A, for j = 2, are compared:
4 −1 0 −1 (−2
12)
−1 4 −1 −1 (1
1 2
)
0 −1 4 (2
12) −1
−1 4 −1 (1
1
2
) 0 −1
(−2
12) −1 (1
1
2
) (2
12) −1 (1
1
2
) 4 (4) −1 (1
1
2
) (2
12) −1 (1
1
2
) (−2
12)
−1 0 −1 (1
1
2
) 4 −1
−1 (2
12) 4 −1 0
−1 (1
1
2
) −1 4 −1
(−2
12) −1 0 −1 4
.
Eigenvalues and condition number of ˜ A: ??
Remark. Obviously, a different definition of ˜ ϕ 2,s , s = 1, . . . , 9, yields a different matrix ˜ A, however the spectrum of ˜ A remains unchanged (why?).
j = 3: ˜ A is a 49 × 49 matrix.
Note that δ 3 = 2 − 1 δ 2 = 2 − 2 δ 1 = 2 − 3 δ 0 , δ 0 = 1. Assume ˜ ϕ 3,s = ψ 2,s = ϕ 3,s , s / ∈ {9, 11, 13, 23, 25, 27, 37, 39, 41}, ˜ ϕ 3,s = ψ 1,ks = ϕ 2,ks, s = 9, 11, 13, 23, 27, 37, 39, 41, k s = 1, 2, 3, 4, 6, 7, 8, 9, ˜ ϕ 3,25 = ϕ 1,1 .
, s = 9, 11, 13, 23, 27, 37, 39, 41, k s = 1, 2, 3, 4, 6, 7, 8, 9, ˜ ϕ 3,25 = ϕ 1,1 .
The hierarchical basis for j = 3 ((j = 2) and [j = 1]):
ϕ
3,43ϕ
3,44ϕ
3,45ϕ
3,46ϕ
3,47ϕ
3,48ϕ
3,49ϕ
3,36(ϕ
2,7) ϕ
3,38(ϕ
2,8) ϕ
3,40(ϕ
2,9) ϕ
3,42ϕ
3,29ϕ
3,30ϕ
3,31ϕ
3,32ϕ
3,33ϕ
3,34ϕ
3,35ϕ
3,22(ϕ
2,4) ϕ
3,24[(ϕ
1,1)] ϕ
3,26(ϕ
2,6) ϕ
3,28ϕ
3,15ϕ
3,16ϕ
3,17ϕ
3,18ϕ
3.19ϕ
3,20ϕ
3,21ϕ
38(ϕ
21) ϕ
3,10(ϕ
22) ϕ
3,12(ϕ
2,3) ϕ
3,14ϕ
31ϕ
32ϕ
33ϕ
34ϕ
35ϕ
36ϕ
37
.
For r, s / ∈ {9, 11, 13, 23, 25, 27, 37, 39, 41} we have
˜ a rs =
Z
s(ψ
2,s)∩s(ψ
2,r) ∇ψ 2,s ∇ψ 2,r = Z
s(ϕ
3,s)∩s(ϕ
3,r) ∇ϕ 3,s ∇ϕ 3,r = a rs .
The 9×9 submatrix of ˜ A composed by the entries ˜ a rs , r, s ∈ {9, 11, 13, 23, 25, 27, 37, 39, 41}, is equal to ˜ A, j = 2. The remaining entries of the 25th column (row) of ˜ A are
of type δ δ3
1
(·) = 1 4 (·). The remaining entries of the 9, 11, 13, 23, 27, 37, 39, 41th columns (rows) of ˜ A are of type δ δ3
2
