Exact Solution of a Linear Difference Equation in a Finite Number of Steps
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.

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{¯}{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     , 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{ }\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, x0 is an initial vector, ${x}_{n\left(p\right)}=\underset{i=0}{\overset{n}{\sum }}{N}^{i}d$ is the particular solution of the non-homogeneous equation. The vector xn(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 h1 and h2 are coefficients. We transfer the term h1x1 to the left hand-side, substitute x2 from the second equation, and divide both sides by a factor of x1. 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 c11 and c12 contain the coefficients h1 and h2, 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 g1 = 0, g2 = 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 x0 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\left(1+{q}_{1}\right)}{{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 x0 = 0, the first iteration of (6) yields d, hence the choice of x0 = 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 x0, and the choice of x0 = 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   .

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

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

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

   Demmel, W.D. (1997) Applied Numerical Linear Algebra. Society for Industrial and Applied Mathematics, Philadelphia.
https://doi.org/10.1137/1.9781611971446

   Watkins, D.S. (2002) Fundamentals of Matrix Computations. 2nd Edition, John Wiley & Sons, Inc., New York.
https://doi.org/10.1002/0471249718

   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

   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

Top