Research article

Numerical differentiation for two-dimensional scattered data on arbitrary domain base on Hermite extension with an implicit iteration process

  • In this paper, we develop a method for numerical differentiation of two-dimensional scattered input data on arbitrary domain. A Hermite extension approach is used to realize the approximation and a modified implicit iteration method is proposed to stabilize the approximation process. For functions with various smooth conditions, the numerical solution process of the method is uniform. The error estimates are obtained and numerical results show that the new method is effective. The advantage of the method is that it can solve the problem in any domain.

    Citation: Benxue Gong, Zhenyu Zhao, Tiao Bian, Yingmei Wang. Numerical differentiation for two-dimensional scattered data on arbitrary domain base on Hermite extension with an implicit iteration process[J]. AIMS Mathematics, 2022, 7(4): 5991-6015. doi: 10.3934/math.2022334

    Related Papers:

    [1] Tao Ma, Jianzhong Lu, Xia Wu . Martingale transforms in martingale Hardy spaces with variable exponents. AIMS Mathematics, 2024, 9(8): 22041-22056. doi: 10.3934/math.20241071
    [2] Meijiao Wang, Qiuhong Shi, Maoning Tang, Qingxin Meng . Stochastic differential equations in infinite dimensional Hilbert space and its optimal control problem with Lévy processes. AIMS Mathematics, 2022, 7(2): 2427-2455. doi: 10.3934/math.2022137
    [3] Mingquan Wei, Xiaoyu Liu . Sharp weak bounds for discrete Hardy operator on discrete central Morrey spaces. AIMS Mathematics, 2023, 8(2): 5007-5015. doi: 10.3934/math.2023250
    [4] Pengyan Wang, Jiahao Wang . Hardy type identities and inequalities with divergence type operators on smooth metric measure spaces. AIMS Mathematics, 2024, 9(6): 16354-16375. doi: 10.3934/math.2024792
    [5] Tohru Nakamura . Asymptotic stability of degenerate stationary solution to a system of viscousconservation laws in half line. AIMS Mathematics, 2018, 3(1): 35-43. doi: 10.3934/Math.2018.1.35
    [6] Suriyakamol Thongjob, Kamsing Nonlaopon, Sortiris K. Ntouyas . Some (p, q)-Hardy type inequalities for (p, q)-integrable functions. AIMS Mathematics, 2021, 6(1): 77-89. doi: 10.3934/math.2021006
    [7] Muhammad Sheraz, Vasile Preda, Silvia Dedu . Non-extensive minimal entropy martingale measures and semi-Markov regime switching interest rate modeling. AIMS Mathematics, 2020, 5(1): 300-310. doi: 10.3934/math.2020020
    [8] Rabha W. Ibrahim, Dumitru Baleanu . Fractional operators on the bounded symmetric domains of the Bergman spaces. AIMS Mathematics, 2024, 9(2): 3810-3835. doi: 10.3934/math.2024188
    [9] Mohammed Shehu Shagari, Saima Rashid, Fahd Jarad, Mohamed S. Mohamed . Interpolative contractions and intuitionistic fuzzy set-valued maps with applications. AIMS Mathematics, 2022, 7(6): 10744-10758. doi: 10.3934/math.2022600
    [10] Wenjuan Liu, Zhouyu Li . Global weighted regularity for the 3D axisymmetric non-resistive MHD system. AIMS Mathematics, 2024, 9(8): 20905-20918. doi: 10.3934/math.20241017
  • In this paper, we develop a method for numerical differentiation of two-dimensional scattered input data on arbitrary domain. A Hermite extension approach is used to realize the approximation and a modified implicit iteration method is proposed to stabilize the approximation process. For functions with various smooth conditions, the numerical solution process of the method is uniform. The error estimates are obtained and numerical results show that the new method is effective. The advantage of the method is that it can solve the problem in any domain.



    A problem that occurs frequently in a variety of mathematical contexts, is to find the common invariant subspaces of a single matrix or set of matrices. In the case of a single endomorphism or matrix, it is relatively easy to find all the invariant subspaces by using the Jordan normal form. Also, some theoretical results are given only for the invariant subspaces of two matrices. However, when there are more than two matrices, the problem becomes much harder, and unexpected invariant subspaces may occur. No systematic method is known. In a recent article [1], we have provided a new algorithms to determine common invariant subspaces of a single matrix or of a set of matrices systematically.

    In the present article we consider a more general version of this problem, that is, providing two algorithms for simultaneous block triangularization and block diagonalization of sets of matrices. One of the main steps in the first two proposed algorithms, consists of finding the common invariant subspaces of matrices using the new method proposed in the recent article [1]. It is worth mentioning that an efficient algorithm to explicitly compute a transfer matrix which realizes the simultaneous block diagonalization of unitary matrices whose decomposition in irreducible blocks (common invariant subspaces) is known from elsewhere is given in [2]. An application of simultaneous block-diagonalization of normal matrices in quantum theory is presented in [3].

    In this article we shall be concerned with finite dimensions only. Of course the fact that a single complex matrix can always be put into triangular form follows readily from the Jordan normal form theorem [4]. For a set of matrices, Jacobson in [5] introduced the notion of a composition series for a collection of matrices. The idea of a composition series for a group is quite familiar. The Jordan-Hölder Theorem [4] states that any two composition series of the same group have the same length and the same composition factors (up to permutation). Jacobson in [5] characterized the simultaneous block triangularization of a set of matrices by the existence of a chain {0}=V0V1...Vt=Cn of invariant subspaces with dimension dim(Vi/Vi1)=ni. Therefore, in the context of a collection of matrices Ω={Ai}Ni=1, the idea is to locate a common invariant subspace V of minimal dimension d of a set of matrices Ω. Assume V is generated by the (linearly independent) set B1={u1,u2,...,ud}, and let B={u1,u2,...,ud,ud+1,ud+2,...,un} be a basis of Cn containing B1. Upon setting S=(u1,u2,...,ud,ud+1,ud+2,...,un), S1AiS has the block triangular form

    S1AiS=(Bi1,1Bi1,20Bi2,2),

    for i=1,...,n. Thereafter, one may define a quotient of the ambient vector space, and each of the matrices in the given collection will pass to this quotient. As such, one defines

    Ti=Bi2,2=(0(nd)×dInd)S1AiS(0d×(nd)Ind).

    Then one may begin again the process of looking for a common invariant subspace of minimal dimension of a set of matrices {Ti}Ni=1 and iterate the procedure. Since all spaces and matrices are of finite dimension, the procedure must terminate at some point. Again, any two such composition series will be isomorphic. When the various quotients and submatrices are lifted back to the original vector space, one obtains precisely the block-triangular form for the original set of matrices. It is important to find a composition series in the construction in order to make the set of matrices as "block-triangular as possible."

    Dubi [6] gave an algorithmic approach to simultaneous triangularization of a set of matrices based on the idea of Jacobson in [5]. In the case of simultaneous triangularization, it can be understood as the existence of a chain {0}=V0V1...Vt=Cn of invariant subspaces with dimension dim(Vi)=i. We generalize his study to cover simultaneous block triangularization of a set of matrices. The generalized algorithm depends on the novel algorithm for constructing invariant subspaces of a set of matrices given in the recent article [1].

    Specht [7] (see also [8]) proved that if the associative algebra L generated by a set of matrices Ω over C satisfies L=L, then Ω admits simultaneous block triangularization if and only if it admits simultaneous block diagonalization, in both cases via a unitary matrix. Following a result of Specht, we prove that a set of matrices Ω admits simultaneous block diagonalization if and only if the set Γ=ΩΩ admits simultaneous block triangularization. Finally, an algorithmic approach to simultaneous block diagonalization of a set of matrices based on this fact is proposed.

    The latter part of this paper presents an alternate approach for simultaneous block diagonalization of a set of n×n matrices {As}Ns=1 by an invertible matrix that does not require finding the common invariant subspaces. Maehara et al. [9] introduced an algorithm for simultaneous block diagonalization of a set of matrices by a unitary matrix based on the existence of a Hermitian commuting matrix. Here, we extend their algorithm to simultaneous block diagonalization of a set of matrices by an invertible matrix based on the existence of a commuting matrix which is not necessarily Hermitian. For example, consider the set of matrices Ω={Ai}2i=1 where

    A1=(100220111),A2=(000210010). (1.1)

    The only Hermitian matrix commuting with the set Ω is the identity matrix. Therefore, we cannot apply the proposed algorithm given in [9]. However, one can verify that the following non Hermitian matrix C commutes with all the matrices {Ai}2i=1

    C=(000210010). (1.2)

    The matrix C has distinct eigenvalues λ1=0,λ2=1 with algebraic multiplicities n1=2,n2=1, respectively. Moreover, the matrix C is not diagonalizable. Therefore, we cannot construct the eigenvalue decomposition for the matrix C. However, one can decompose the matrix C by its generalized eigen vectors as follows:

    S1CS=(010000001)=(0100)(1), (1.3)

    where

    S=(0120011101). (1.4)

    Initially, it is noted that the matrices {Ai}2i=1 can be decomposed into two diagonal blocks by the constructed invertible matrix S where

    S1A1S=(11201)(2),S1A2S=(0100)(1). (1.5)

    Then, a new algorithm is developed for simultaneous block diagonalization by an invertible matrix based on the generalized eigenvectors of a commuting matrix. Moreover, a new characterization is presented by proving that the existence of a commuting matrix that possesses at least two distinct eigenvalues is the necessary and sufficient condition to guarantee the simultaneous block diagonalization by an invertible matrix.

    An outline of the paper is as follows. In Section 2 we review several definitions pertaining to block-triangular and block-diagonal matrices and state several elementary consequences that follow from them. In Section 3, following a result of Specht [7] (see also [8]), we provide conditions for putting a set of matrices into block-diagonal form simultaneously. Furthermore, we apply the theoretical results to provide two algorithms that enable a collection of matrices to be put into block-triangular form or block-diagonal form simultaneously by a unitary matrix based on the existence of invariant subspaces. In Section 4, a new characterization is presented by proving that the existence of a commuting matrix that possesses at least two distinct eigenvalues is the necessary and sufficient condition to guarantee the simultaneous block diagonalization by an invertible matrix. Furthermore, we apply the theoretical results to provide an algorithm that enables a collection of matrices to be put into block-diagonal form simultaneously by an invertible matrix based on the existence of a commuting matrix. Sections 3 and 4 also provide concrete examples using the symbolic manipulation system Maple.

    Let Ω be a set of n×n matrices over an algebraically closed field F, and let L denote the algebra generated by Ω over F. Similarly, let Ω be the set of the conjugate transpose of each matrix in Ω and L denote the algebra generated by Ω over F.

    Definition 2.1. An n×n matrix A is given the notation BT(n1,...,nt) provided A is block upper triangular with t square blocks on the diagonal, of sizes n1,...,nt, where t2 and n1+...+nt=n. That is, a block upper triangular matrix A has the form

    A=(A1,1A1,2A1,t0A2,2A2,t00At,t) (2.1)

    where Ai,j is a square matrix for all i=1,...,t and j=i,...,t.

    Definition 2.2. A set of n×n matrices Ω is BT(n1,...,nt) if all of the matrices in Ω are BT(n1,...,nt).

    Remark 2.3. A set of n×n matrices Ω admits a simultaneous triangularization if it is BT(n1,...,nt) with ni=1 for i=1,...,t.

    Remark 2.4. A set of n×n matrices Ω is BT(n1,...,nt) if and only if the algebra L generated by Ω is BT(n1,...,nt).

    Proposition 2.5. [7] (see also [8]) Let Ω be a nonempty set of complex n×n matrices. Then, there is a nonsingular matrix S such that SΩS1 is BT(n1,...,nt) if and only if there is a unitary matrix U such that UΩU is BT(n1,...,nt).

    Theorem 2.6. [5,Chapter Ⅳ] Let Ω be a nonempty set of complex n×n matrices. Then, there is a unitary matrix U such that UΩU is BT(n1,...,nt) if and only if the set Ω has a chain {0}=V0V1...Vt=Cn of invariant subspaces with dimension dim(Vi/Vi1)=ni.

    Definition 2.7. An n×n matrix A is given the notation BD(n1,...,nt) provided A is block diagonal with t square blocks on the diagonal, of sizes n1,...,nt, where t2, n1+...+nt=n, and the blocks off the diagonal are the zero matrices. That is, a block diagonal matrix A has the form

    A=(A1000A2000At) (2.2)

    where Ak is a square matrix for all k=1,...,t. In other words, matrix A is the direct sum of A1,...,At. It can also be indicated as A1A2...At.

    Definition 2.8. A set of n×n matrices Ω is BD(n1,...,nt) if all of the matrices in Ω are BD(n1,...,nt).

    Remark 2.9. A set of n×n matrices Ω admits a simultaneous diagonalization if it is BD(n1,...,nt) with ni=1 for i=1,...,t.

    Remark 2.10. A set of n×n matrices Ω is BD(n1,...,nt) if and only if the algebra L generated by Ω is BD(n1,...,nt).

    Proposition 2.11. [7] (see also [8]) Let Ω be a nonempty set of complex n×n matrices and let L be the algebra generated by Ω over C. Suppose L=L. Then, there is a nonsingular matrix S such that SLS1 is BT(n1,...,nt) if and only if there is a unitary matrix U such that ULU is BD(n1,...,nt).

    Dubi [6] gave an algorithmic approach to simultaneous triangularization of a set of n×n matrices. In this section, we will generalize his study to cover simultaneous block triangularization and simultaneous block diagonalization of a set of n×n matrices. The generalized algorithms depend on the novel algorithm for constructing invariant subspaces of a set of matrices given in the recent article [1] and Theorem 3.3.

    Lemma 3.1. Let Ω be a nonempty set of complex n×n matrices, Ω be the set of the conjugate transpose of each matrix in Ω and L be the algebra generated by Γ=ΩΩ. Then, L=L.

    Proof. Let A be a matrix in L. Then, A=P(B1,...,Bm) for some multivariate noncommutative polynomial P(x1,...,xm) and matrices {Bi}mi=1Γ. Therefore, A=P(B1,...,Bm)=Q(B1,...,Bm) for some multivariate noncommutative polynomial Q(x1,...,xm) where the matrices {Bi}mi=1Γ=Γ. Hence, the matrix AL

    Lemma 3.2. Let Ω be a nonempty set of complex n×n matrices and Ω be the set of the conjugate transpose of each matrix in Ω, and Γ=ΩΩ. Then, there is a unitary matrix U such that UΓU is BD(n1,...,nt) if and only if there is a unitary matrix U such that UΩU is BD(n1,...,nt).

    Proof. Assume that there exists a unitary matrix U such that UΩU is BD(n1,...,nt). Then, (UΩU)=UΩU is BD(n1,...,nt). Hence, UΓU is BD(n1,...,nt).

    Theorem 3.3. Let Ω be a nonempty set of complex n×n matrices and Ω be the set of the conjugate transpose of each matrix in Ω, and Γ=ΩΩ. Then, there is a unitary matrix U such that UΩU is BD(n1,...,nt) if and only if there is a unitary matrix U such that UΓU is BT(n1,...,nt).

    Proof. Let L be the algebra generated by Γ. Then, L=L using Lemma 3.1. Now, by applying Proposition 2.11 and Lemma 3.2, the following statements are equivalent :

    There is a unitary matrix U such that UΓU is BT(n1,...,nt).

    There is a unitary matrix U such that ULU is BT(n1,...,nt).

    There is a unitary matrix U such that ULU is BD(n1,...,nt).

    There is a unitary matrix U such that UΓU is BD(n1,...,nt).

    There is a unitary matrix U such that UΩU is BD(n1,...,nt).

    (1) Input: the set Ω={Ai}Ni=1.

    (2) Set k=0,B=ϕ,s=n,Ti=Ai,S2=I.

    (3) Search for a d-dimensional invariant subspace V=v1,v2,...,vd of a set of matrices {Ti}Ni=1 starting from d=1 up to d=s1. If one does not exist and k=0, abort and print "no simultaneous block triangularization". Else, if one does not exist and k0, go to step (8). Else, go to next step.

    (4) Set Vk+1=(S2v1S2v2...S2vd),B=B{S2v1,S2v2,...,S2vd},S1=(V1V2...Vk+1).

    (5) Find a basis {u1,u2,...,ul} for the orthogonal complement of B.

    (6) Set S2=(u1u2...ul),S=(S1S2), and

    Ti=(0(sd)×dIsd)S1AiS(0d×(sd)Isd).

    (7) Set k=k+1,s=sd, and return to step (3).

    (8) Compute the QR decomposition of the invertible matrix S, by means of the Gram–Schmidt process, to convert it to a unitary matrix Q.

    (9) Output: a unitary matrix U as the conjugate transpose of the resulting matrix Q.

    Remark 3.4. If one uses any non-orthogonal complement in step 5 of Algorithm A, then the matrix S is invertible such that S1ΩS is BT(n1,...,nt). However, in such a case, one cannot guarantee that UΩU is BT(n1,...,nt).

    Example 3.5. The set of matrices Ω={Ai}2i=1 admits simultaneous block triangularization where

    A1=(321011050000014012131113020025010006),A2=(441244840360001012320444168524404102880400040). (3.1)

    Applying Algorithm A to the set Ω can be summarized as follows:

    Input: Ω.

    Initiation step:

    We have k=0,B=ϕ,s=6,T1=A1,T2=A2,S2=I.

    In the first iteration:

    We found two-dimensional invariant subspace V=e1,e4 of a set of matrices {Ti}2i=1. Therefore, B={e1,e4},S1=(e1,e4),S2=(e2,e3,e5,e6),

    T1=(5000141220251006),T2=(360011232444128840040), (3.2)

    k=1, and s=4.

    In the second iteration: We found two-dimensional invariant subspace V=e2,e3 of a set of matrices {Ti}2i=1. Therefore, B={e1,e4,e3,e5},S1=(e1,e4,e3,e5),S2=(e2,e6),

    T1=(5016),T2=(361440), (3.3)

    k=2, and s=2.

    In the third iteration: There is no one-dimensional invariant subspace of a set of matrices {Ti}2i=1. Therefore, S=(e1e4e3e5e2e6), and the corresponding unitary matrix is

    U=(100000000100001000000010010000000001)

    such that the set UΩU={UAiU}2i=1 is BT(2,2,2) where

    UA1U=(301121111133004112000225000050000016),UA2U=(444481244528416400324124001284800003610000440). (3.4)

    (1) Input: the set Ω={Ai}Ni=1.

    (2) Construct the set Γ=ΩΩ.

    (3) Find a unitary matrix U such that UΓU is BT(n1,...,nt) using Algorithm A.

    (4) Output: a unitary matrix U.

    Remark 3.6. Algorithm B provides the finest block-diagonalization. Moreover, the number of the blocks equals the number the of the invariant subspaces, and the size of each block is ni×ni, where ni is the dimension of the invariant subspace.

    Example 3.7. The set of matrices Ω={Ai}2i=1 admits simultaneous block diagonalization where

    A1=(3000000020000000200000001000000010000000100000003),A2=(0000000000000001000000000000000000000010001000000). (3.5)

    Applying Algorithm B to the set Ω can be summarized as follows:

    Input: Γ=ΩΩ.

    Initiation step:

    We have k=0,B=ϕ,s=7,T1=A1,T2=A2,T3=AT2,S2=I.

    In the first iteration:

    We found one-dimensional invariant subspace V=e5 of a set of matrices {Ti}3i=1. Therefore, B={e5},S1=(e5),S2=(e1,e2,e3,e4,e6,e7),

    T1=(300000020000002000000100000010000003),T2=(000000000000010000000000000100100000),T3=TT2, (3.6)

    k=1, and s=6.

    In the second iteration: We found two-dimensional invariant subspace V=e4,e5 of a set of matrices {Ti}3i=1. Therefore, B={e5,e4,e6},S1=(e5e4e6),S2=(e1,e2,e3,e7),

    T1=(3000020000200003),T2=(0000000001001000),T3=TT2, (3.7)

    k=2, and s=4.

    In the third iteration: We found two-dimensional invariant subspace V=e2,e3 of a set of matrices {Ti}3i=1. Therefore, B={e5,e4,e6,e2,e3},S1=(e5e4e6e2e3),S2=(e1,e7),

    T1=(3003),T2=(0010),T3=(0100), (3.8)

    k=3, and s=2.

    In the fourth iteration: There is no one-dimensional invariant subspace of a set of matrices {Ti}3i=1. Therefore, S=(e5e4e6e2e3e1e7), and the corresponding unitary matrix is

    U=(0000100000100000000100100000001000010000000000001)

    such that the set UΩU={UAiU}2i=1 is BD(1,2,2,2) where

    UA1U=(1)(1001)(2002)(3003),UA2U=(0)(0010)(0010)(0010). (3.9)

    Example 3.8. The set of matrices Ω={Ai}2i=1 admits simultaneous block diagonalization where

    A1=(3000000020000000200000001000000010000000100000003),A2=(0000000000100001000000000000000010000001001000000). (3.10)

    Similarly, applying Algorithm B to the set Ω provides the matrix S=(e6e5e7e1e3e2e4). Therefore, the corresponding unitary matrix is

    U=(0000010000010000000011000000001000001000000001000)

    such that the set UΩU={UAiU}2i=1 is BD(2,2,3) where

    UA1U=(1001)(3003)(200020001),UA2U=(0101)(0100)(010001000). (3.11)

    Example 3.9. The set of matrices Ω={Ai}3i=1 admits simultaneous block diagonalization where

    A1=(000000000020000000001000000000200000000000000000001000000000100000000010000000000),A2=(000100000100010000000001000000000000000100000000000000000000000000000100000000000),A3=(010000000000000000000000000100010000010000000001000000000000010000000000000000000). (3.12)

    Similarly, applying Algorithm B to the set Ω provides the matrix S=(e1+e5e9e3e6e8e7e1e5,e2e4). Therefore, the corresponding unitary matrix is

    U=(12200012200000000000010010000000000010000000000100000001001220001220000010000000000100000)

    such that the set UΩU={UAiU}3i=1 is BD(1,1,2,2,3) where

    UA1U=(0)(0)(1001)(1001)(000020002),UA2U=(0)(0)(0100)(0100)(002200000),UA3U=(0)(0)(0010)(0010)(020000200). (3.13)

    This section focuses on an alternate approach for simultaneous block diagonalization of a set of n×n matrices {As}Ns=1 by an invertible matrix that does not require finding the common invariant subspaces as Algorithm B given in the previous section. Maehara et al. [9] introduced an algorithm for simultaneous block diagonalization of a set of matrices by a unitary matrix based on the eigenvalue decomposition of a Hermitian commuting matrix. Here, we extend their algorithm to be applicable for a non-Hermitian commuting matrix by considering its generalized eigen vectors. Moreover, a new characterization is presented by proving that the existence of a commuting matrix that possesses at least two distinct eigenvalues is the necessary and sufficient condition to guarantee the simultaneous block diagonalization by an invertible matrix.

    Proposition 4.1. Let V be a vector space, and let T:VV be a linear operator. Let λ1,...,λk be distinct eigenvalues of T. Then, each generalized eigenspace Gλi(T) is T-invariant, and we have the direct sum decomposition

    V=Gλ1(T)Gλ2(T)...Gλk(T).

    Lemma 4.2. Let V be a vector space, and let T:VV, L:VV be linear commuting operators. Let λ1,...,λk be distinct eigenvalues of T. Then, each generalized eigenspace Gλi(T) is L-invariant.

    Proof. Let V be a vector space and λ1,...,λk be distinct eigenvalues of T with the minimal polynomial μ(x)=(xλ1)n1(xλ2)n2...(xλk)nk. Then, we have the direct sum decomposition V=Gλ1(T)Gλ2(T)...Gλk(T).

    For each i=1,..,k, let xGλi(T), and then (TλiI)nix=0. Then, (TλiI)niLx=L(TλiI)nix=0. Hence, LxGλi(T).

    Theorem 4.3. Let {As}Ns=1 be a set of n×n matrices. Then, the set {As}Ns=1 admits simultaneous block diagonalization by an invertible matrix S if and only if the set {As}Ns=1 commutes with a matrix C that possesses two distinct eigenvalues.

    Proof. Assume that the set {As}Ns=1 admits simultaneous block diagonalization by the an invertible matrix S such that

    S1AsS=Bs,1Bs,2...Bs,k,

    where the number of blocks k2, and the matrices Bs,1,Bs,2,...,Bs,k have sizes n1×n1,n2×n2,...,nk×nk, respectively, for all s=1,..,N.

    Now, define the matrix C as

    C=S(λ1In1×n1λ2In2×n2...λkInk×nk)S1,

    where λ1,λ2,...,λk are any distinct numbers.

    Clearly, the matrix C commutes with the set {As}Ns=1. Moreover, it has the distinct eigenvalues λ1,λ2,...,λk.

    Assume that the set {As}Ns=1 commutes with a matrix C that posseses distinct eigenvalues λ1,λ2,...,λk.

    Using Proposition 4.1, one can use the generalized eigenspace Gλi(C) of the matrix C associated to these distinct eigenvalues to decompose the matrix C as a direct sum of k matrices. This can be achieved by restricting the matrix C on the invariant subspaces Gλi(C) as follows:

    S1CS=[C]Gλ1(C)[C]Gλ2(C)...[C]Gλk(C)

    where

    S=(Gλ1(C),Gλ2(C),...,Gλk(C)).

    Using Lemma 4.2, one can restrict each matrix As on the invariant subspaces Gλi(C) to decompose the matrix As as a direct sum of k matrices as follows:

    S1AsS=[As]Gλ1(C)[As]Gλ2(C)...[As]Gλk(C).

    Remark 4.4. For a given set of n×n matrices {As}Ns=1, if the set {As}Ns=1 commutes only with the matrices having only one eigenvalue, then it does not admit a simultaneous block diagonalization by an invertible matrix.

    Algorithm C:

    (1) Input: the set Ω={As}Ns=1.

    (2) Construct the the following matrix:

    X=(IA1AT1IIA2AT2I...IANATNI).

    (3) Compute the null space of the matrix X and reshape the obtained vectors as n×n matrices. These matrices commute with all the matrices {As}Ns=1.

    (4) Choose a matrix C from the obtained matrices that possesses two distinct eigenvalues.

    (5) Find the distinct eigenvalues λ1,...,λk of the matrix C and the corresponding algebraic multiplicity n1,n2,...,nk.

    (6) Find each generalized eigenspace Gλi(C) of the matrix C associated to the eigenvalue λi by computing the null space of (CλiI)ni.

    (7) Construct the invertible matrix S as

    S=(Gλ1(C),Gλ2(C),...,Gλk(C)).

    (8) Verify that

    S1AsS=Bs,1Bs,2...Bs,k,

    where the matrices Bs,1,Bs,2,...,Bs,k have sizes n1×n1,n2×n2,...,nk×nk, respectively, for all s=1,..,N.

    (9) Output: an invertible matrix S.

    Remark 4.5. Algorithm C provides the finest block-diagonalization if one chooses a matrix C with maximum number of distinct eigenvalues. Moreover, the number of the blocks equals the number the of the distinct eigenvalues, and the size of each block is ni×ni, where ni is the algebraic multiplicity of the eigenvalue λi.

    Example 4.6. Consider the set of matrices Ω={Ai}6i=1 where

    A1=(000000000100000010010000001000000000),A2=(000100000000000001100000000000001000),A3=(000010000001000000000000100000010000),A4=(010000100000000000000000000001000010),A5=(001000000000100000000001000000000100),A6=(000000001000010000000010000100000000). (4.1)

    The set Ω admits simultaneous block diagonalization by an invertible matrix. An invertible matrix can be obtained by applying algorithm C to the set Ω as summarized below:

    A matrix C that commutes with all the matrices {Ai}6i=1 can be obtained as

    C=(000001000010000100001000010000100000). (4.2)

    .

    The distinct eigenvalues of the matrix C are λ1=1,λ2=1 with algebraic multiplicities n1=3,n2=3, respectively..

    The generalized eigenspaces of the matrix C associated to the distinct eigenvalues are

    Gλ1(C)=N(Cλ1I)3=e6e1,e2+e5,e4e3,Gλ2(C)=N(Cλ2I)3=e1+e6,e5e2,e3+e4. (4.3)

    The invertible matrix S=(Gλ1(C),Gλ2(C)) is

    S=(100100010010001001001001010010100100). (4.4)

    The set S1ΩS={S1AiS}6i=1 contains block diagonal matrices where

    S1A1S=(000001010)(000001010),S1A2S=(001000100)(001000100),S1A3S=(010100000)(010100000),S1A4S=(010100000)(010100000),S1A5S=(001000100)(001000100),S1A6S=(000001010)(000001010). (4.5)

    It is well known that a set of non-defective matrices can be simultaneously diagonalized if and only if the matrices commute. In the case of non-commuting matrices, the best that can be achieved is simultaneous block diagonalization. Both Algorithm B and the Maehara et al. [9] algorithm are applicable for simultaneous block diagonalization of a set of matrices by a unitary matrix. Algorithm C can be applied for block diagonalization by an invertible matrix when finding a unitary matrix is not possible. In case block diagonalization of a set of matrices is not possible by a unitary or an invertible matrix, then one may utilize block triangularization by Algorithm A. Algorithms A and B are based on the existence of invariant subspaces; however, Algorithm C is based on the existence of a commuting matrix which is not necessarily Hermitian, unlike the Maehara et al. algorithm.

    The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

    Ahmad Y. Al-Dweik and M. T. Mustafa would like to thank Qatar University for its support and excellent research facilities. R. Ghanam and G. Thompson are grateful to VCU Qatar and Qatar Foundation for their support.

    The authors declare that they have no conflicts of interest.

    Figure Listing 1.  Step 5 in Algorithm A.
    Figure Listing 2.  Step 6 in Algorithm A.
    Figure Listing 3.  Steps 8 & 9 in Algorithm A.
    Figure Listing 4.  Steps 2 & 3 in Algorithm C.
    Figure Listing 5.  Steps 6 & 7 in Algorithm C.


    [1] A. Ramm, A. Smirnova, On stable numerical differentiation, Math. Comp., 70 (2001), 1131–1153. https://dx.doi.org/10.1090/S0025-5718-01-01307-2 doi: 10.1090/S0025-5718-01-01307-2
    [2] R. S. Anderssen, P. Bloomfield, Numerical differentiation procedures for non-exact data, Numer. Math., 22 (1974), 157–182. https://dx.doi.org/10.1007/BF01436965 doi: 10.1007/BF01436965
    [3] S. Lu, V. Naumova, S. V. Pereverzev, Legendre polynomials as a recommended basis for numerical differentiation in the presence of stochastic white noise, J. Inverse Ill-Posed Probl., 21 (2013), 193–216. https://dx.doi.org/10.1515/jip-2012-0050 doi: 10.1515/jip-2012-0050
    [4] H. N. Mhaskar, V. Naumova, S. V. Pereverzyev, Filtered Legendre expansion method for numerical differentiation at the boundary point with application to blood glucose predictions, Appl. Math. Comput., 224 (2013), 835–847. https://dx.doi.org/10.1016/j.amc.2013.09.015 doi: 10.1016/j.amc.2013.09.015
    [5] D. A. Murio, C. E. Mejía, S. Zhan, Discrete mollification and automatic numerical differentiation, Comput. Math. Appl., 35 (1998), 1–16. https://dx.doi.org/10.1016/S0898-1221(98)00001-7 doi: 10.1016/S0898-1221(98)00001-7
    [6] Z. Y. Zhao, A truncated Legendre spectral method for solving numerical differentiation, Int. J. Comput. Math., 87 (2010), 3209–3217. https://dx.doi.org/10.1080/00207160902974404 doi: 10.1080/00207160902974404
    [7] Z. Y. Zhao, J. F. Liu, Hermite spectral and pseudospectral methods for numerical differentiation, Appl. Numer. Math., 61 (2011), 1322–1330. https://dx.doi.org/10.1016/j.apnum.2011.09.006 doi: 10.1016/j.apnum.2011.09.006
    [8] G. W. Groetsch, Lanczo's generalized derivative, Am. Math. Mon., 105 (1998), 320–326. https://dx.doi.org/10.2307/2589707 doi: 10.2307/2589707
    [9] Z. W. Wang, R. S. Wen, Numerical differentiation for high orders by an integration method, J. Comput. Appl. Math., 234 (2010), 941–948. https://dx.doi.org/10.1016/j.cam.2010.01.056 doi: 10.1016/j.cam.2010.01.056
    [10] B. Q. Chen, Z. Y. Zhao, Z. Li, Z. H. Meng, Numerical differentiation by a Fourier extension method with super-order regularization, Appl. Math. Comput., 334 (2018), 1–10. https://dx.doi.org/10.1016/j.amc.2018.04.005 doi: 10.1016/j.amc.2018.04.005
    [11] J. Cullum, Numerical differentiation and regularization, SIAM J. Numer. Anal., 8 (1971), 254–265. https://dx.doi.org/10.1137/0708026 doi: 10.1137/0708026
    [12] M. Hanke, O. Scherzer, Inverse problems light: Numerical differentiation, Am. Math. Mon., 108 (2001), 512–521. https://dx.doi.org/10.2307/2695705 doi: 10.2307/2695705
    [13] B. Hu, S. Lu, Numerical differentiation by a Tikhonov regularization method based on the discrete cosine transform, Appl. Anal., 91 (2012), 719–736. https://dx.doi.org/10.1080/00036811.2011.598862 doi: 10.1080/00036811.2011.598862
    [14] T. Wei, Y. C. Hon, Y. B. Wang, Reconstruction of numerical derivatives from scattered noisy data, Inverse Probl., 21 (2005), 657. https://dx.doi.org/10.1088/0266-5611/21/2/013 doi: 10.1088/0266-5611/21/2/013
    [15] T. Wei, Y. C. Hon, Numerical differentiation by radial basis functions approximation, Adv. Comput. Math., 27 (2007), 247–272. https://dx.doi.org/10.1007/s10444-005-9001-0 doi: 10.1007/s10444-005-9001-0
    [16] S. Lu, S. V. Pereverzev, Numerical differentiation from a viewpoint of regularization theory, Math. Comp., 75 (2006), 1853–1870. https://dx.doi.org/10.1090/S0025-5718-06-01857-6 doi: 10.1090/S0025-5718-06-01857-6
    [17] Z. H. Meng, Z. Y. Zhao, D. Mei, Y. X. Zhou, Numerical differentiation for two-dimensional functions by a Fourier extension method, Inverse Probl. Sci. En., 28 (2020), 126–143. https://dx.doi.org/10.1080/17415977.2019.1661410 doi: 10.1080/17415977.2019.1661410
    [18] Y. B. Wang, T. Wei, Numerical differentiation for two-dimensional scattered data, J. Math. Anal. Appl., 312 (2005), 121–137. https://dx.doi.org/10.1016/j.jmaa.2005.03.025 doi: 10.1016/j.jmaa.2005.03.025
    [19] S. Riachy, M. Mboup, J. Richard, Multivariate numerical differentiation, J. Comput. Appl. Math., 236 (2011), 1069–1089. https://dx.doi.org/10.1016/j.cam.2011.07.031 doi: 10.1016/j.cam.2011.07.031
    [20] S. Qiu, Z. W. Wang, A. Xie, Multivariate numerical derivative by solving an inverse heat source problem, Inverse Probl. Sci. En., 26 (2018), 1178–1197. https://dx.doi.org/10.1080/17415977.2017.1386187 doi: 10.1080/17415977.2017.1386187
    [21] R. Adams, Sobolev spaces, New York: Academic press, 1975.
    [22] H. Whitney, Analytic extensions of differentiable functions defined in closed sets, Trans. Amer. Math. Soc., 36 (1934), 63–89. https://dx.doi.org/10.2307/1989708 doi: 10.2307/1989708
    [23] C. Fefferman, Interpolation and extrapolation of smooth functions by linear operators, Rev. Mat. Iberoam., 21 (2005), 313–348. https://dx.doi.org/10.4171/RMI/424 doi: 10.4171/RMI/424
    [24] C. Fefferman, Whitney's extension problems and interpolation of data, Bull. Amer. Math. Soc., 46 (2008), 207–220. https://dx.doi.org/10.1090/S0273-0979-08-01240-8 doi: 10.1090/S0273-0979-08-01240-8
    [25] C. Fefferman, A. Israel, G. K. Luli, Sobolev extension by linear operators, J. Amer. Math. Soc., 27 (2014), 69–145. https://dx.doi.org/10.1090/S0894-0347-2013-00763-8 doi: 10.1090/S0894-0347-2013-00763-8
    [26] Z. Y. Zhao, A Hermite extension method for numerical differentiation, Appl. Numer. Math., 159 (2021), 46–60. https://dx.doi.org/10.1016/j.apnum.2020.08.016 doi: 10.1016/j.apnum.2020.08.016
    [27] Q. N. Jin, U. Tautenhahn, Implicit iteration methods in Hilbert scales under general smoothness conditions, Inverse Probl., 27 (2011), 045012. https://dx.doi.org/10.1088/0266-5611/27/4/045012 doi: 10.1088/0266-5611/27/4/045012
    [28] S. Thangavelu, Lectures on Hermite and Laguerre expansions, New Jersey: Princeton University Press, 1993. https://dx.doi.org/10.1515/9780691213927
    [29] T. Tao, The Hermite spectral method for gaussian-type functions, SIAM J. Sci. Comput., 14 (1993), 594–606. https://dx.doi.org/10.1137/0914038 doi: 10.1137/0914038
  • Reader Comments
  • © 2022 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(2014) PDF downloads(58) Cited by(1)

Figures and Tables

Figures(5)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog