Newton’s Approach to General Algebraic Equations over Clifford Algebras

Abstract

There is a short section describing how Newton’s method works for algebraic problems over Clifford algebras. There are two applications. Zeros of unilateral polynomials over a Clifford algebra in $\mathbb {R}^8$ and solutions of a Riccati equation over all eight Clifford algebras in $\mathbb {R}^4$.

Dedicated to Wolfgang Sprößig on the occasion of his 70th birthday

1 Introduction

Let $p:\mathbb {R}^N\rightarrow \mathbb {R}^N$ be a mapping, where $\mathbb {R}^N$ stands for any Clifford algebra. For introduction to Clifford Algebras, see [1], for algebraic and analytic properties of coquaternion algebra, see [6]. Examples for p are polynomials of a general type, including unilateral and bilateral polynomials. Other examples are matrix equations like the Riccati equation

$$\displaystyle \begin{aligned} p(\mathbf{X}):=\mathbf{A}+\mathbf{B}\mathbf{X}+\mathbf{X}\mathbf{C}+\mathbf{X}\mathbf{D}\mathbf{X}=\mathbf{0},\end{aligned} $$

(13.1.1)

where the matrix entries are elements from a Clifford algebra in $\mathbb {R}^N$. If X is a matrix of size m × n, then, in this case, $p:\mathbb {R}^{mnN}\rightarrow \mathbb {R}^{mnN}$. The Riccati equation will be treated separately in the last section. For other examples see also [2]. In order to find the solutions of p(z) = 0 by Newton’s method, the linear system for h

$$\displaystyle \begin{aligned} p(z)+p'(z)h=\mathbf{0}\end{aligned} $$

(13.1.2)

has to be solved where in the beginning, z has to be replaced by an arbitrary guess $z\in \mathbb {R}^N$ and after having found h as the solution of (13.1.2) the guess has to be replaced by z := z + h. In a paper by Lauterbach and Opfer [5], it was shown that p′(z)h is the linear part of p(z + h) with respect to h. To mention an example let p(z) = z ² + a ₁ z + a ₀. Then,

$$\displaystyle \begin{aligned}p(z+h)=(z+h)^2+a_1(z+h)+a_0=z^2+hz+zh+h^2+a_1z+a_1h+a_0\end{aligned}$$

and the linear part of this expression with respect to h is

$$\displaystyle \begin{aligned} p'(z)h=hz+zh+a_1h.\end{aligned} $$

(13.1.3)

In all cases and independent of the algebra the linear part always consist of a sum with terms of the form ahb. Since, by definition, p′(z)h is a real, linear mapping $\mathbb {R}^N\rightarrow \mathbb {R}^N$ in h, the linear part must have a matrix representation

$$\displaystyle \begin{aligned} p'(z)h={\mathbf{M}}_zh \end{aligned} $$

(13.1.4)

where M _z is a real N × N matrix and h is now a real column vector of length N. The matrix M _z is called the Jacobi matrix of (13.1.2). In comparison with the numerical Jacobi matrix which is constructed by replacing p′(z)h by partial derivatives, the Jacobi matrix we use is exact and in addition easy to compute. Even for general, nonunilateral polynomials the matrix representation of p′(z)h is given in [5, Section 4]. And the underlying algebra is not of large importance. In the MATLAB program given in Table 13.4 one can see how to compute the matrix M _z given in (13.1.4) for the linear term ahb. Let y = p(z). We call the euclidean $\mathbb {R}^N$ norm ||y|| the error of z. Thus, our aim is to find all z with error zero.

Table 13.4 MATLAB program for computing zeros of polynomials over coefficients from ℝ⁸ algebra C ₄ by Newton’s method

2 Application of Newton’s Method to Polynomials with Clifford Coefficients

Let p now be a unilateral polynomial in any $\mathbb {R}^N$ algebra. In order to find zeros of p we have to use (13.1.2) together with (13.1.4). As an example we use a Clifford algebra in $\mathbb {R}^8$ which we call C ₄ and as examples we will be looking for zeros of a quadratic polynomial and a polynomials of degree 7.

In order to describe the multiplication rules of the algebra C ₄ we abbreviate the eight unit vectors units(k) in $\mathbb {R}^8$ also by u _k,  k = 1, 2, …, 8, and the multiplication rules are listed in Table 13.1.

Table 13.1 Multiplication table of C ₄ for the canonical unit vectors u _k in $\mathbb {R}^8,\>1\le k\le 8$

The elements in the C ₄ algebra for use in the MATLAB program, which is printed at the end of this section as Table 13.4, page 7, will have the name

$$\displaystyle \begin{aligned} a=c4([a_1,a_2,a_3,a_4,a_5,a_6,a_7,a_8]), a_j\in \mathbb{R},j=1,2,\ldots,8 \end{aligned} $$

(13.2.1)

or in short

$$\displaystyle \begin{aligned}a=c4(h), h\in \mathbb{R}^8.\end{aligned}$$

In order to apply the program, an initial guess xold is needed. For a systematic search a random guess is very practical. We always used random integer values as components of xold. This can be done by the MATLAB command xold=c4( round( 40*( rand( 1,8) -0.5) ) ) , where rand is the MATLAB command for random (uniformly distributed) numbers in [0, 1]. The given expression for xold produces an integer row vector with eight entries in [−20, 20]. We have applied the program to two examples, a quadratic polynomial and a polynomial of degree 7. In all cases there are several solutions.

Example

Let the quadratic polynomial p be defined by

$$\displaystyle \begin{aligned} p(z)=z^2+c4([2,3,5,7,11,13,17,19])z+u_8. \end{aligned} $$

(13.2.2)

We found the following four zeros (see Table 13.2) all in less than 20 steps by applying Newton’s method.

Table 13.2 Zeros of p, a quadratic polynomial defined in (13.2.2)

We never found a singular Jacobi matrix. Whether there are more solutions as given, it is an open question.

Example

We selected the following polynomial

$$\displaystyle \begin{aligned} p(z)=u_1z^7+u_2z^6+u_3z^5+u_4z^4+u_5z^3+u_6z^2+u_7z+u_8. \end{aligned} $$

(13.2.3)

We can guess already one solution, namely z = u ₄. If we look at Table 13.1 we see that $u_4^2=-1\Rightarrow u_4^4=1\Rightarrow u_4^5=u_4\Rightarrow u_4^6=u_4^2=-1\Rightarrow u_4^7=u_4^3=-u_4,$ thus,

$$\displaystyle \begin{aligned} \begin{array}{rcl} p(u_4)&\displaystyle =&\displaystyle -u_4-u_2+u_3u_4+u_4-u_5u_4-u_6+u_7u_4+u_8=\\ &\displaystyle =&\displaystyle -u_4-u_2+u_2+u_4-u_8-u_6+u_6+u_8=0. \end{array} \end{aligned} $$

We applied the given program to (13.2.3) and in less than 40 Newton iterations for each zero we found the solutions given in Table 13.3. It contains 18 zeros of p. These are found by using random integer guesses. Whether there are more zeros than indicated, it is an open problem. We did not encounter one example which did not converge. The convergence behavior was typical for Newton’s method. If the error was under a certain limit, say 10⁻², then there were only few remaining steps so that almost machine precision was reached. Therefore, in the two Tables 13.2, 13.3 the original MATLAB results are presented. The advantage of using Newton’s method for finding zeros of polynomials with arbitrary algebra coefficients is its easy use and its high precision. There is another advantage. If with some other method a zero is computed it is easy to apply few additional Newton steps in order to reduce the error. The disadvantage is, that we do not know whether there are still other, nondiscovered zeros. We note, that the frequently appearing number 0.353553390593274 in Table 13.3 is $\frac {\strut \sqrt {2}}{\strut 4}$ (Table 13.4).

Table 13.3 Table of zeros of p, a polynomial of degree 7, defined in (13.2.3)

3 Application to Riccati Equation

In the Riccati equation over a Clifford algebra in $\mathbb {R}^N$, given in (13.1.1), we can choose the sizes of the corresponding matrices as follows:

$$\displaystyle \begin{aligned}\mathbf{X}: m\times n\Rightarrow \mathbf{A}: m\times n,\> \mathbf{B}: m\times m,\>\mathbf{C}: n\times n,\>\mathbf{D}: n\times m. \end{aligned}$$

The linear part of p(X + H) is easy to compute:

$$\displaystyle \begin{aligned}p'(\mathbf{X})\mathbf{H}=\mathbf{H}(\mathbf{C}+\mathbf{D})+(\mathbf{B}+\mathbf{X}\mathbf{D})\mathbf{H}={\mathbf{M}}_1\mathbf{H}+{\mathbf{M}}_2\mathbf{ H}=({\mathbf{M}}_1+{\mathbf{M}}_2)\mathbf{H}.\end{aligned}$$

In this case the matrices M ₁, M ₂ are of order mnN and H is a column vector of dimension mnN. For more details see also [5], Theorem 8.1 and [3]. In [5], also quotations to the relevant literature is given. We will use an example defined in all eight $\mathbb {R}^4$ algebras which have the names and notations:

• 1. Quaternions, $\mathbb {H}$,

• 2. Coquaternions, $\mathbb {H}_{\mathrm {coq}}$,

• 3. Tessarines, $\mathbb {H}_{\mathrm {tes}}$,

• 4. Cotessarines, $\mathbb {H}_{\mathrm {cotes}}$,

• 5. Nectarines, $\mathbb {H}_{\mathrm {nec}}$,

• 6. Conectarines, $\mathbb {H}_{\mathrm {con}}$,

• 7. Tangerines, $\mathbb {H}_{\mathrm {tan}}$,

• 8. Cotangerines, $\mathbb {H}_{\mathrm {cotan}}$.

It should be noted, that the algebras numbered 3, 4, 7, 8 are commutative. About the names and the multiplication rules see [4, 7]. We quote an example from [5].

Example

We choose m = 2, n = 3 and define the algebraic Riccati equation by $\mathbf {A}\in {\mathcal {A}}^{2\times 3},\mathbf {B}\in {\mathcal {A}}^{2\times 2},\mathbf {C}\in {\mathcal {A}}^{3\times 3},\mathbf {D}\in {\mathcal {A}}^{3\times 2}$, where the matrix entries are given in Table 13.5.

Table 13.5 Definition of the coefficients of algebraic Riccati equation

The data of Table 13.5 are randomly chosen integers in [−5, 5]. We choose X = 0 as initial guess with the exception of Algebra 6, where another guess is used. Newton’s method converges then in all 8 cases. The solutions are given in Table 13.6. These solutions are not necessarily the only solutions.

Table 13.6 Solutions X ∈ A^2×3 of the algebraic Riccati equation in all eight ℝ⁴ algebras