An optimal eighth order derivative free multiple root finding scheme and its dynamics

1.   Introduction

Let $n$ be an integer number, $N = \{ 1, 2, \ldots, n\}$, and let $C^{n\times n}$ be the set of all complex matrices of order $n$. A matrix $M = (m_{ij}) \in {C^{n \times n}}(n \geq 2)$ is called a strictly diagonally dominant (${SDD}$) matrix ^[1] if

It was shown that an $SDD$ matrix is an $H$-matrix ^[1], where matrix $M = ({m_{ij}}) \in {C^{n \times n}}(n \ge 2)$ is called an $H$-matrix ^{[1, 2, 3]} if and only if there exists a positive diagonal matrix $X$ such that $MX$ is an $SDD$ matrix ^{[1, 2, 4]}. $H$-matrices are widely applied in many fields, such as computational mathematics, economics, mathematical physics and dynamical system theory, see ^{[1, 4, 5, 6]}. Meanwhile, upper bounds for the infinity norm of the inverse matrices of $H$-matrices can be used in the convergence analysis of matrix splitting and matrix multi-splitting iterative methods for solving the large sparse of linear equations ^[7], as well as linear complementarity problems. Moreover, upper bounds of the infinity norm of the inverse for different classes of matrices have been widely studied, such as $CKV$-type matrices ^[8], $S$-$SDDS$ matrices ^[9], $DZ$ and $DZ$-type matrices ^{[10, 11]}, $Nekrasov$ matrices ^{[12, 13, 14, 15]}, $S$-$Nekrasov$ matrices ^[16], $Q$-$Nekrasov$ matrices ^[17], $GSDD_1$ matrices ^[18] and so on.

In 2011, Peňa ^[19] proposed a new subclass of $H$-matrices called ${SDD_1}$ matrices, whose definition is listed below. A matrix $M = (m_{ij}) \in {C^{n \times n}}(n \geq 2)$ is called an ${SDD_1}$ matrix if

where

In 2023, Dai et al. ^[18] gave a new subclass of $H$-matrices named generalized $SDD_1$ ($GSDD_1$) matrices, which extends the class of $SDD_1$ matrices. Here, a matrix $M = (m_{ij}) \in {C^{n \times n}}(n \geq 2)$ is said a $GSDD_1$ matrix if

and

where

Subsequently, some upper bounds for the infinite norm of the inverse matrices of ${SDD}$ matrices, ${SDD_1}$ matrices and $GSDD_1$ matrices are presented, see ^{[18, 20, 21]}. For example, the following results that will be used later are listed.

Theorem 1. (Varah bound) ^[21] Let matrix $M = (m_{ij}) \in {C^{n \times n}}(n \geq 2)$ be an ${SDD}$ matrix. Then

Theorem 2. ^[20] Let matrix $M = (m_{ij}) \in {C^{n \times n}}(n \geq 2)$ be an ${SDD}$ matrix. Then

where

Theorem 3. ^[20] Let matrix $M = (m_{ij}) \in {C^{n \times n}}(n \geq 2)$ be an ${SDD}$ matrix. If ${r_i}(M) > 0(\forall i \in N)$, then

Theorem 4. ^[18] Let $M = (m_{ij})\in {C^{n \times n}}$ be a $GSDD_1$ matrix. Then

where

and

On the basis of the above articles, we continue to study special structured matrices and introduce a new subclass of $H$-matrices called ${SDD_k}$ matrices, and provide some new upper bounds for the infinite norm of the inverse matrices for ${SDD}$ matrices and ${SDD_k}$ matrices, which improve the previous results. The remainder of this paper is organized as follows: In Section 2, we propose a new subclass of $H$-matrices called ${SDD_k}$ matrices, which include ${SDD}$ matrices and ${SDD_1}$ matrices, and derive some properties of ${SDD_k}$ matrices. In Section 3, we present some upper bounds for the infinity norm of the inverse matrices for ${SDD}$ matrices and ${SDD_k}$ matrices, and provide some comparisons with the well-known Varah bound. Moreover, some numerical examples are given to illustrate the corresponding results.

2.   ${SDD_k}$ matrices

In this section, we propose a new subclass of $H$-matrices called ${SDD_k}$ matrices, which include ${SDD}$ matrices and ${SDD_1}$ matrices, and derive some new properties.

Definition 1. A matrix $M = (m_{ij}) \in {C^{n \times n}}(n \geq 2)$ is called an ${SDD_k}$ matrix if there exists ${\rm{ }}k \in {N}$ such that

where

Immediately, we know that ${SDD_k}$ matrices contain ${SDD}$ matrices and ${SDD_1}$ matrices, so

Lemma 1. A matrix $M = (m_{ij}) \in {C^{n \times n}}(n \geq 2)$ is an ${SDD_k}(k \geq 2)$ matrix if and only if for $\forall i \in N$, $|{m_{ii}}| > p_i^{(k - 1)}(M)$.

Proof. For $\forall i \in N_1(M)$, from Definition 1, it holds that $|{m_{ii}}| > p_i^{(k - 1)}(M)$.

For $\forall i \in N_2(M)$, we have that $|{m_{ii}}| > {r_i}(M)$. When $k = 2$, it follows that

Suppose that $|{m_{ii}}| > p_i^{(k-1)}(M)(k\leq l, l > 2)$ holds for $\forall i \in N_2(M)$. When $k = l+1$, we have

By induction, we obtain that for $\forall i \in N_2(M)$, $|{m_{ii}}| > p_i^{(k - 1)}(M)$. Consequently, it holds that matrix $M$ is an $SDD_k$ matrix if and only if $|{m_{ii}}| > p_i^{(k - 1)}(M)$ for $\forall i \in N$. The proof is completed. □

Lemma 2. If $M = (m_{ij}) \in {C^{n \times n}}(n \geq 2)$ is an ${SDD_k}(k \geq 2)$ matrix, then $M$ is an $H$-matrix.

Proof. Let $X$ be the diagonal matrix $diag\{ {x_1}, {x_2}, \cdots, {x_n}\}$, where

and

If $\sum\limits_{j \in {N_2}(M)\backslash \{ i\} } {|{m_{ij}}|} = 0$, then the corresponding fraction is defined to be ${\infty}$. Next we consider the following two cases.

Case 1: For each $i \in {N_1}(M)$, it is not difficult to see that $|{{{(MX}})_{ii}}| = |{m_{ii}}|$, and

Case 2: For each $i \in {N_2}(M)$, we can obtain that

and

Based on Cases 1 and 2, we have that $MX$ is an ${SDD}$ matrix, and consequently, $M$ is an $H$-matrix. The proof is completed. □

According to the definition of ${SDD_k}$ matrix and Lemma 1, we obtain some properties of ${SDD_k}$ matrices as follows:

Theorem 5. If $M = (m_{ij}) \in {C^{n \times n}}(n \geq 2)$ is an ${SDD_k}$ matrix and $N_1(M) \ne \emptyset$, then for $\forall i \in {N_1}(M)$, $\sum\limits_{j \ne i, j \in {N_2}(M)} {|{m_{ij}}|} > 0$.

Proof. Suppose that for $\forall i \in N_1(M)$, $\sum\limits_{j \ne i, j \in N_2(M)} {|{m_{ij}}|} = 0$. By Definition 1, we have that $p_i^{(k - 1)}(M) = {r_i}(M)$, $\forall i \in {N_1}{\rm{(}}M{\rm{)}}$. Thus, it is easy to verify that $|{m_{ii}}| > p_i^{(k - 1)}(M) = {r_i}(M) \ge |{m_{ii}}|$, which is a contradiction. Thus for $\forall i \in N_1(M)$, $\sum\limits_{j \ne i, j \in N_2(M)} {|{m_{ij}}|} > 0$. The proof is completed. □

Theorem 6. Let $M = (m_{ij}) \in {C^{n \times n}}(n \geq 2)$ be an ${SDD_k}(k \geq 2)$ matrix. It holds that $\sum\limits_{j \ne i, j \in N_2(M)} {|{m_{ij}}|} > 0$, $\forall i \in N_2(M)$. Then

and

Proof. By Lemma 1 and the known conditions that for $\forall i \in {N_2}{\rm{(}}M{\rm{)}}$, $\sum\limits_{j \ne i, j \in N_2(M)} {|{m_{ij}}|} > 0$, it holds that

and

We now prove that $|{m_{ii}}| > p_i^{(k - 1)}(M) > 0(\forall i \in {N})$ and consider the following two cases.

Case 1: If ${N_1}{\rm{(}}M{\rm{) = }}\emptyset$, then $M$ is an ${SDD}$ matrix. It is easy to verify that $|{m_{ii}}| > p_i^{(k - 1)}(M) > 0$, $\forall i \in {N_2}{\rm{(}}M{\rm{)}} = N$.

Case 2: If ${N_1}{\rm{(}}M{\rm{)}} \ne \emptyset$, by Theorem 5 and the known condition that for $\forall i \in {N_2}{\rm{(}}M{\rm{)}}$, $\sum\limits_{j \ne i, j \in N_2(M)} {|{m_{ij}}|} > 0$, then it is easy to obtain that $|{m_{ii}}| > p_i^{(k - 1)}(M) > 0(\forall i \in N)$.

From Cases 1 and 2, we have that $|{m_{ii}}| > p_i^{(k - 1)}(M) > 0(\forall i \in N)$. The proof is completed. □

Theorem 7. Let $M = (m_{ij}) \in {C^{n \times n}}(n \geq 2)$ be an ${SDD_k}(k \geq 2)$ matrix and for $\forall i \in {N_2}{\rm{(}}M{\rm{)}}$, $\sum\limits_{j \ne i, j \in N_2(M)} {|{m_{ij}}|} > 0$. Then there exists a diagonal matrix $X = diag\{ {x_1}, {x_2}, \cdots, {x_n}\}$ such that $MX$ is an ${SDD}$ matrix. Elements ${x_1}, {x_2}, \ldots, {x_n}$ are determined by

Proof. We need to prove that matrix $MX$ satisfies the following inequalities:

From Theorem 6 and the known condition that for $\forall i \in {N_2}{\rm{(}}M{\rm{)}}$, $\sum\limits_{j \ne i, j \in N_2(M)} {|{m_{ij}}|} > 0$, it is easy to verify that

For each $i \in N$, we have that $|{{\rm{(}}MX)_{ii}}| = p_i^{(k - 1)}(M)$ and

that is,

Therefore, $MX$ is an $SDD$ matrix. The proof is completed. □

3.   Infinity norm upper bounds for the inverse of ${SDD}$ and ${SDD_k}$ matrices

In this section, by Lemma 2 and Theorem 7, we provide some new upper bounds of the infinity norm of the inverse matrices for ${SDD_k}$ matrices and ${SDD}$ matrices, respectively. We also present some comparisons with the Varah bound. Some numerical examples are presented to illustrate the corresponding results. Specially, when the involved matrices are ${SDD_1}$ matrices as subclass of ${SDD_k}$ matrices, these new bounds are in line with that provided by Chen et al. ^[20].

Theorem 8. Let $M = (m_{ij})\in {C^{n \times n}}(n \geq 2)$ be an ${SDD_k}(k \geq 2)$ matrix. Then

where

and

Proof. By Lemma 2, we have that there exists a positive diagonal matrix $X$ such that $MX$ is an ${SDD}$ matrix, where $X$ is defined as Lemma 2. Thus,

and

Notice that $MX$ is an ${SDD}$ matrix. Hence, by Theorem 1, we have

Thus, for any $i \in {N_1}{\rm{(}}M{\rm{)}}$, it holds that

For any $i \in {N_2}{\rm{(}}M{\rm{)}}$, it holds that

Therefore, we get

The proof is completed. □

From Theorem 8, it is easy to obtain the following result.

Corollary 1. Let $M = (m_{ij}) \in {C^{n \times n}}(n \geq 2)$ be an ${SDD}$ matrix. Then

where $k\geq 2$,

and

Example 1. Consider the $n\times n$ matrix:

Take that $n = 20$. It is easy to verify that $M$ is an ${SDD}$ matrix.

By calculations, we have that for $k = 2$,

For $k = 4$,

For $k = 6$,

For $k = 8$,

So, when $k = 2, 4, 6, 8$, by Corollary 1 and Theorem 1, we can get the upper bounds for $||{M^{ - 1}}|{|_\infty }$, see Table 1. Thus,

and

Moreover, when $k = 1$, by Theorem 2, we have

The following Theorem 9 shows that the bound in Corollary 1 is better than that in Theorem 1 of ^[20] in some cases.

Theorem 9. Let matrix $M = (m_{ij}) \in {C^{n \times n}}(n \geq 2)$ be an ${SDD}$ matrix. If there exists $k \geq 2$ such that

then

where ${Z_i}$ and $\varepsilon$ are defined as in Corollary 1, respectively.

Proof. From the given condition, we have that there exists $k \geq 2$ such that

then

Thus, we get

Since $M$ is an ${SDD}$ matrix, then

It's easy to verify that

Thus, by Corollary 1, it holds that

The proof is completed. □

We illustrate Theorem 9 by the following Example 2.

Example 2. This is the previous Example 1. For $k = 4$, we have

Thus, by Theorem 8, we obtain that for each $0 < {\varepsilon _2} < 0.7034$,

However, we find that the upper bounds in Theorems 8 and 9 contain the parameter ${\varepsilon}$. Next, based on Theorem 7, we will provide new upper bounds for the infinity norm of the inverse matrices of ${SDD_k}$ matrices, which only depend on the elements of the given matrices.

Theorem 10. Let $M = (m_{ij}) \in {C^{n \times n}}(n \geq 2)$ be an ${SDD_k}(k \geq 2)$ matrix and for each $i \in {N_2}{\rm{(}}M{\rm{)}}$, $\sum\limits_{j \ne i, j \in N_2(M)} {|{m_{ij}}|} > 0$. Then

Proof. By Theorems 7 and 8, we have that there exists a positive diagonal matrix $X$ such that $MX$ is an ${SDD}$ matrix, where $X$ is defined as in Theorem 7. Thus, it holds that

and

Notice that $MX$ is an ${SDD}$ matrix. Thus, by Theorem 1, we get

Therefore, we have that

The proof is completed. □

Since $SDD$ matrices are a subclass of $SDD_{k}$ matrices, by Theorem 10, we can obtain the following result.

Corollary 2. Let $M = (m_{ij}) \in {C^{n \times n}}(n \geq 2)$ be an ${SDD}$ matrix. If ${r_i}(M) > 0(\forall i \in N)$, then there exists $k \geq 2$ such that

Two examples are given to show the advantage of the bound in Theorem 10.

Example 3. Consider the following matrix:

It is easy to verify that $M$ is not an $SDD$ matrix, an $SDD_1$ matrix, a $GSDD_1$ matrix, an $S$-$SDD$ matrix, nor a $CKV$-type matrix. Therefore, we cannot use the error bounds in ^{[1, 8, 9, 18, 20]} to estimate $||{M^{ - 1}}|{|_\infty }$. But, $M$ is an $SDD_2$ matrix. So by the bound in Theorem 10, we have that $\|{M^{ - 1}}\|_\infty \leq 0.5820$.

Example 4. Consider the tri-diagonal matrix $M\in R^{n\times n}$ arising from the finite difference method for free boundary problems ^[18], where

Take that $n = 4$, $a = 1$, $b = 0$, $c = 3.7$ and $\alpha = 10$. It is easy to verify that $M$ is neither an $SDD$ matrix nor an $SDD_1$ matrix. However, we can get that $M$ is a $GSDD_1$ matrix and an $SDD_3$ matrix. By the bound in Theorem 10, we have

while by the bound in Theorem 4, it holds that

The following two theorems show that the bound in Corollary 2 is better than that in Theorem 1 in some cases.

Theorem 11. Let $M = (m_{ij}) \in {C^{n \times n}}(n \geq 2)$ be an ${SDD}$ matrix. If ${r_i}(M) > 0(\forall i \in N)$ and there exists $k \geq 2$ such that

then

Proof. Since $M$ is an ${SDD}$ matrix, then $N_1(M) = \emptyset$ and $M$ is an ${SDD_k}$ matrix. By the given condition that ${r_i}(M) > 0(\forall i \in N)$, it holds that

Similarly, we can obtain that

that is,

Since there exists $k \geq 2$ such that

then we have

Thus, from Corollary 2, we get

The proof is completed. □

We illustrate the Theorem 11 by following Example 5.

Example 5. Consider the matrix $M = (m_{ij}) \in {C^{n \times n}}(n \geq 2)$, where

Take that $n = 20$. It is easy to check that $M$ is an ${SDD}$ matrix. Let

By calculations, we have

Thus, when $k = 2, 3, 4, 5, 6$, the matrix $M$ satisfies the conditions of Theorem 11. By Theorems 1 and 11, we can derive the upper bounds for $||{M^{ - 1}}|{|_\infty }$, see Table 2. Meanwhile, when $k = 1$, by Theorem 3, we get that $||{M^{ - 1}}|{|_\infty } \leq 1.6976.$

From Table 2, we can see that the bounds in Theorem 11 are better than that in Theorems 1 and 3 in some cases.

Theorem 12. Let $M = (m_{ij}) \in {C^{n \times n}}(n \geq 2)$ be an ${SDD}$ matrix. If ${r_i}(M) > 0(\forall i \in N)$ and there exists $k \geq 2$ such that

then

Proof. By Theorem 7 and the given condition that ${r_i}(M) > 0(\forall i \in N)$, it is easy to get that

From the condition that there exists $k \geq 2$ such that

we have

Thus, from Corollary 2, it holds that

The proof is completed. □

Next, we illustrate Theorem 12 by the following Example 6.

Example 6. Consider the tri-diagonal matrix $M = (m_{ij}) \in {C^{n \times n}}(n \geq 2)$, where

Take that $n = 20$. It is easy to verify that $M$ is an ${SDD}$ matrix.

By calculations, we have that for $k = 2$,

For $k = 5$, we get

For $k = 10$, it holds that

Thus, for $k = 2, 5, 10$, the matrix $M$ satisfies the conditions of Theorem 12. Thus, from Theorems 12 and 1, we get the upper bounds for $||{M^{ - 1}}|{|_\infty }$, see Table 3. Meanwhile, when $k = 1$, by Theorem 3, we have that $||{M^{ - 1}}|{|_\infty } \leq 1.7170.$

From Table 3, we can see that the bound in Theorem 12 is sharper than that in Theorems 1 and 3 in some cases.

4.   Conclusions

${SDD_k}$ matrices as a new subclass of $H$-matrices are proposed, which include ${SDD}$ matrices and ${SDD_1}$ matrices, and some properties of ${SDD_k}$ matrices are obtained. Meanwhile, some new upper bounds of the infinity norm of the inverse matrices for ${SDD}$ matrices and ${SDD_k}$ matrices are presented. Furthermore, we prove that the new bounds are better than some existing bounds in some cases. Some numerical examples are also provided to show the validity of new results. In the future, based on the proposed infinity norm bound, we will explore the computable error bounds of the linear complementarity problems for $SDD_k$ matrices.

Use of AI tools declaration

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

Acknowledgments

This research is supported by Guizhou Provincial Science and Technology Projects (20191161), and the Natural Science Research Project of Department of Education of Guizhou Province (QJJ2023062, QJJ2023063).

Conflict of interest

The authors declare that they have no competing interests.