Exact Solution of a Linear Difference Equation in a Finite Number of Steps

Show more

1. Introduction

To solve a system of linear algebraic equations (SLAE)

$Ax=b$ , (1)

where x and b are the unknown and known vectors of k size, respectively, $A=\left[{a}_{ij}\right]$ is a nonsingular matrix, $i,\text{\hspace{0.17em}}j\in \stackrel{\xaf}{1,\text{\hspace{0.17em}}k}$ , the entries of matrices and vectors are considered to be real, a simple iterative method reduces (1) to the form

$x=Cx+d$ (2)

with the matrix C and vector d. The indexed form of (2) is given by

${x}_{n+1}=C{x}_{n}+d$ , (3)

where $n=1,2,3,\cdots $ . Equation (3) is called a linear difference equation (LDE) or an iterative equation.

The mathematical community considers that this method is approximate and it does not give an exact solution of (1) in a finite number of steps:

$x={A}^{-1}b={\left(I-C\right)}^{-1}d$ , (4)

where I is the identity matrix. This opinion is unreasonable and it is assumed as a postulate. In numerous literature on mathematics, for example in [1] [2] [3] [4] , there are particular statements given by mathematicians about the fact that a simple iterative method is approximate. The objective of the work is to disprove the established opinion.

2. The Inconsistency of the Postulate for a Homogeneous System

In control theory, the case d = 0 describes a linear discrete system with respect to deviation from a given state. The reduction of the matrix C to the Frobenius form containing a row of coefficients of the characteristic polynomial and the additive feedback in the form of a row vector with the opposite sign make a row of the matrix equal to zero wherein the matrix becomes nilpotent. We denote such a matrix by N and recall its properties

${N}^{k}=0,\text{\hspace{1em}}\sigma \left(N\right)=0$ , (5)

where σ is the spectrum.

The resulting system goes into an equilibrium state and the derivation is eliminated in a finite number of steps. Such a process may be naturally called finite. This property distinguishes it from the process with a theoretically infinite number of steps in a stable system with the spectrum of the matrix inside the unit circle. This means that a simple iterative method for (1) with respect to the error

${x}_{n+1}=C{x}_{n}$ ,

with С = N, is exact.

3. The Inconsistency of the Postulate for a Non-Homogeneous System

We pose the question about the nature of the process generated by the non-homogeneous Equation (3)

${x}_{n+1}=N{x}_{n}+d$ , (6)

with the nilpotent matrix.

First, we single out such a process in solving the system (1) in which the matrix is reduced to the triangular form. This approach is used in a number of direct methods, for example, in the well-known Gauss elimination method. The triangular matrix is split into the identity matrix and strictly triangular matrix that is nilpotent. Therefore, the back substitution is a formally iterative process with a nilpotent matrix of a special form.

We write the solution of (6) as

${x}_{n}={x}_{n\left(h\right)}+{x}_{n\left(p\right)}$ , (7)

where
${x}_{n\left(h\right)}={N}^{n}{x}_{0}$ is the common solution of the homogeneous equation, x_{0} is an initial vector,
${x}_{n\left(p\right)}={\displaystyle \underset{i=0}{\overset{n}{\sum}}{N}^{i}d}$ is the particular solution of the non-homogeneous equation. The vector x_{n}(h) becomes zero at the step n = k by virtue of (5). This proves the necessity of a nilpotent matrix for a finite process.

An unexpected fact is that this condition is also sufficient. Indeed, in the expression

${x}_{n\left(p\right)}=\left(I+N+{N}^{2}+\cdots +{N}^{k-1}+0+\cdots \right)d$ , (8)

the sum

$\left(I+N+{N}^{2}+\cdots +{N}^{k-1}\right)={\left(I-N\right)}^{-1}$

defines the inverse matrix in (4), with C = N, and establishes finally

${x}_{n\left(p\right)}=x={\left(I-N\right)}^{-1}d$ . (9)

This result indicates that an exact solution of the LDE (6) is obtained after performing the iteration with the number equal to the dimension, which completely refutes the postulate that a simple iterative method is approximate.

Next, we needed to answer the question: “Is it possible to transform (1) to (6) without zeroing the elements in advance?” An affirmative answer was received in 2001 for a system with k = 2. Let us show this transformation, for which we represent the system (1) in the form (2)

$\begin{array}{l}{x}_{1}={a}_{11}{x}_{1}+{a}_{12}{x}_{2}-{b}_{1}+{x}_{1}+{h}_{1}\left({x}_{1}-{x}_{1}\right)+{h}_{2}\left({x}_{2}-{x}_{2}\right),\\ {x}_{2}={a}_{21}{x}_{1}+{a}_{22}{x}_{2}-{b}_{2}+{x}_{2},\end{array}$ (10)

where h_{1} and h_{2} are coefficients. We transfer the term h_{1}x_{1} to the left hand-side, substitute x_{2} from the second equation, and divide both sides by a factor of x_{1}. As a result, (10) takes the form (3):

$\begin{array}{l}{x}_{1}={c}_{11}{x}_{1}+{c}_{12}{x}_{2}-{d}_{1},\\ {x}_{2}={c}_{21}{x}_{1}+{c}_{22}{x}_{2}-{d}_{2},\end{array}$ (11)

where ${c}_{11}=\left({a}_{11}+{h}_{1}-{a}_{21}{h}_{2}\right)/\left(1+{h}_{1}\right)$ , ${c}_{12}=\left({a}_{12}-{a}_{22}{h}_{2}\right)/\left(1+{h}_{1}\right)$ , ${d}_{1}=\left({b}_{1}-{b}_{2}{h}_{2}\right)/\left(1+{h}_{1}\right)$ , ${c}_{21}={a}_{21}$ , ${c}_{22}={a}_{22}+1$ , ${d}_{2}={b}_{1}$ .

The elements c_{11} and c_{12} contain the coefficients h_{1} and h_{2}, by which the spectrum can be changed. To make a zero spectrum, the coefficients of the characteristic polynomial

${\lambda}^{2}-{g}_{1}\lambda +{g}_{2}=0$

must satisfy the conditions g_{1} = 0, g_{2} = 0, i.e.

$\begin{array}{l}{c}_{11}+{c}_{22}=0,\\ {c}_{11}{c}_{22}-{c}_{12}{c}_{21}=0.\end{array}$ (12)

Substituting the elements of the matrix C from (11) into (12) gives a linear system

$\begin{array}{l}\left(2+{a}_{22}\right){h}_{1}-{a}_{21}{h}_{2}=-1-{a}_{11}-{a}_{22},\\ \left(1+{a}_{22}\right){h}_{1}-{a}_{21}{h}_{2}=-{a}_{11}{a}_{22}+{a}_{12}{a}_{21}-{a}_{11}.\end{array}$ (13)

The solution (13) substituted into (11) gives a nilpotent matrix and the right-hand side

${N}_{1}=\left[\begin{array}{cc}-{q}_{2}& \frac{-{q}_{2}^{2}}{{a}_{21}}\\ {a}_{21}& {q}_{2}\end{array}\right]$ , ${D}_{1}=\left[\begin{array}{c}\frac{{b}_{2}\left(\frac{{a}_{11}+d\left(1+{q}_{2}\right)}{{a}_{21}}\right)-{b}_{1}}{c}\\ -{b}_{2}\end{array}\right]$ , (14)

where ${q}_{\text{2}}={a}_{\text{22}}+\text{1}$ , $c={a}_{\text{11}}{a}_{\text{22}}-{a}_{\text{11}}{a}_{\text{22}}$ , with which the equation

${x}_{n+1}={N}_{1}{x}_{n}+{D}_{1}$ , (15)

generates an exact answer (4) for an arbitrary x_{0} after the second iteration.

The same difference equation

${x}_{n+1}={N}_{2}{x}_{n}+{D}_{2}$ , (16)

where ${N}_{2}=\left[\begin{array}{cc}{q}_{1}& {a}_{12}\\ \frac{-{q}_{1}^{2}}{{a}_{12}}& -{q}_{1}\end{array}\right]$ , ${D}_{2}=\left[\begin{array}{c}-{b}_{1}\\ \frac{{b}_{1}\left(\frac{{a}_{22}+d(1+{q}_{1})}{{a}_{12}}\right)-{b}_{2}}{c}\end{array}\right]$ , ${q}_{\text{1}}={a}_{\text{11}}+\text{1}$ ,

can be obtained from a system of the form (10) with the differences in the second row.

When x_{0} = 0, the first iteration of (6) yields d, hence the choice of x_{0} = d gives an exact answer after the first iteration of (15) and (16).

The generalization of the transformation to SLAE of an arbitrary size made it possible to create a theory of finite iterative processes with the derivation of linear difference equations, with different nilpotent matrices, that generate an exact solution after k iterations for any x_{0}, and the choice of x_{0} = d reduces the number of iterations by one. The theory has been developed on the basis of a direct method for controlling the spectrum of a matrix [5] [6] .

References

[1] Strang, G. (1976) Linear Algebra and Its Applications. Academic Press, New York.

[2] Rice, J.R. (1981) Matrix Computations and Mathematical Software. McGraw-Hill, Inc., New York.

[3] Demmel, W.D. (1997) Applied Numerical Linear Algebra. Society for Industrial and Applied Mathematics, Philadelphia.

https://doi.org/10.1137/1.9781611971446

[4] Watkins, D.S. (2002) Fundamentals of Matrix Computations. 2nd Edition, John Wiley & Sons, Inc., New York.

https://doi.org/10.1002/0471249718

[5] Iskhakov, A., Pospelov, V. and Skovpen, S. (2012) Non-Frobenius Spectrum-Transformation Method. Applied Mathematics, 3, 1471-1479.

https://doi.org/10.4236/am.2012.330206

[6] Iskhakov, A. and Skovpen, S. (2015) A Direct Transformation of a Matrix Spectrum. Journal of Progressive Research in Mathematics, 5, 463-481.

https://doi.org/10.4236/alamt.2015.53011