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

Affiliation(s)

^{1}
Department of Management, ‘VNIIEM Corporation’ JC, Moscow, Russia.

^{2}
Department of Ship Electricity and Automatics, Northern (Arctic) Federal University, Severodvinsk, Russia.

Abstract

An exact solution of a linear difference equation in a finite number of steps
has been obtained. This refutes the conventional wisdom that a simple iterative
method for solving a system of linear algebraic equations is approximate.
The nilpotency of the iteration matrix is the necessary and sufficient condition
for getting an exact solution. The examples of iterative equations providing an
exact solution to the simplest algebraic system are presented.

Keywords

Linear Difference Equation, Exact Iterative Solution of a System of Linear Algebraic Equations, Nilpotent Matrix

Linear Difference Equation, Exact Iterative Solution of a System of Linear Algebraic Equations, Nilpotent Matrix

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] .

Cite this paper

Iskhakov, A. and Skovpen, S. (2018) Exact Solution of a Linear Difference Equation in a Finite Number of Steps.*Applied Mathematics*, **9**, 287-290. doi: 10.4236/am.2018.93022.

Iskhakov, A. and Skovpen, S. (2018) Exact Solution of a Linear Difference Equation in a Finite Number of Steps.

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