The mathematical community considers that a simple-iteration method expressed as a linear difference equation with a stationary matrix for solving a system of linear algebraic equations (SLAE) is approximate because it does not give the exact answer for a finite number of iterations.
Examples of direct statements are:
“Iterative methods give a tool to obtain an approximate solution of a system of linear equations” (Faddeev D.K., Faddeeva V.N.)  .
“… iterative methods that allow the roots of a system to be obtained with a given accuracy via converging infinite processes” (Demidovich B.P., Maron I.A.)  .
“The main difference of iteration methods from direct ones consists that iteration methods give an exact solution to Equation (1) only as a limit of sequence of iterative approximations” Samarskii A.A.  .
“Application of iterative method does not allow an exact solution to be reached …” (Strang G.)  .
“Iterative methods for solving (1) are infinite methods which find only approximate solutions” (Rice J.R.)  .
“… iterative methods do not frequently give an exact solution in a finite number of steps” (Demmel W.J.)  .
“Iterative methods do not give strictly exact solution, as it is attained as a limit of a sequence of vectors” (Pirumov U.G.)  .
“For iterative methods, i.e. for methods in which an exact solution can be obtained only as a result of an infinite repetition of uniform (as a rule, simple) operations …” (Verzhbitskii V.M.)  .
“… iterative methods give a sequence of approximations which (one can hope) converges to the genuine solutions of the problem” (Watkins D.S.)  .
“Iterative methods are approximate methods which find solutions of systems by means of infinite converging processes” (Shevtsov G.S., Kryukova O.G., Myznikova B.E.)  .
The above statement taken from  has the following continuation: “The exception is methods of ‘finite’ iterations, which include methods of conjugate directions that, theoretically, enable the exact solution to be found in a finite number of operations for any initial guess …”. This only emphasizes the authors’ viewpoint that the exact solution of an SLAE cannot be obtained via iterations with a stationary matrix. In this way, these methods are contrasted with non-stationary methods that provide the exact solution in a finite number of steps. Similar reasoning can be found in other publications, for example, in  we read: “… the conjugate gradient method being essentially iterative should actually be referred to direct methods, because it is proved that with its help … the solution of a linear system is achieved in no more than n steps for any initial vector”.
Indeed, as it can be found in numerous schoolbooks and monographs as well as in Internet, it is generally accepted to divide methods for solving SLAE into direct and iterative ones and to match them with exact and approximate methods with stationary matrix. This reflects the point of view on approximation nature of iterative methods.
These opinions can be briefly and clearly expressed for a wide audience as follows: for an analytically given second-order SLAE, the solution in the form of Cramer’s formulas cannot be obtained by a simple-iteration method.
For an arbitrary SLAE, we call this thesis the postulate about approximation nature.
2. Problem Statement
The paradox is that the postulate, which denies the possibility of obtaining a finite iterative process in a system with a stationary matrix, does not reflect the real situation for a very long time.
The fact is that in control theory, where for a linear discrete system characterized by the same equation, the method of achieving a given state in a finite number of steps has been known since the middle of the last century  -  . A brief history on finite processes, which have been called “deadbeat”, is presented in  . For a system described in the input-output relations, the finite processes are achieved if the coefficients of the characteristic polynomial are equal to zero. For a control system defined in the state space and characterized by a matrix of coefficients, the process of moving terminates in a finite number of steps if the matrix is nilpotent. Such a matrix is obtained by transformation of the original system matrix into Frobenius form and then the row with characteristic polynomial coefficients is reduced to zero (except for sign) by adding a row of coefficients having the same values with opposite signs. These coefficients are produced in the system’s feedback loop.
Generally, this method can be applied to iterative solution of an SLAE, but only in a homogeneous case, i.e. to reduce the error to zero for a finite number of iterations that probably was the reason of his unknown for algebraists.
Thus, it should be assumed that from the standpoint of control theory, for a homogeneous SLAE, the postulate is refuted, while for a non-homogeneous one there is no proof.
The aim of this work is to refute the postulate about approximation nature of a simple-iteration method applied to a non-homogeneous SLAE. The proof is given and accompanied by an example of obtaining an exact solution of a second-order SLAE in the form of Cramer’s formulas in two iterations.
To achieve the goal, we have developed an alternative method for controlling the spectrum of a matrix without transforming the matrix to the Frobenius form for which the row of the characteristic polynomial coefficients needs to be obtained except for sign. The main advantage of the method is the possibility to produce the spectrum equal to a given set of eigenvalues not only by perturbation of an autonomous matrix, but also in the case when the matrix is multiplied by a vector and added to another vector in the composition of algebraic, difference and differential equations.
Setting a zero spectrum for a difference equation gives a nilpotent matrix. The back conversion of an iterative system to algebraic one forms a unipotent matrix. The direct link between those matrix means that the condition for solving an SLAE for a finite number of iterations is the transformation of system matrix to the form, in which all eigenvalues are equal to 1. An example is the Gauss method, where a triangular matrix with a unit diagonal (or unitriangular) is split into an identity matrix and strictly triangular matrix, which is nilpotent. In this regard, the solution process known as back substitution can be formally considered as an iterative process with a sparse matrix, which is not required to be multiplied by a vector. At each step, only one component of the solution vector is determined. In practice, this is done without any mention about the iterative nature of the process.
In the proposed method, the transformation gives a nilpotent matrix but does not change the density of the matrix of an original SLAE. Actually, the iterative procedure of solution (it may also be considered as back substitution) contains the operation of multiplying a matrix by a vector, and all the entries of the solution vector are obtained at the final step. The maximum number of steps does not exceed the order of the matrix.
4. Brief Background
The method evolution is described in more detail in  . The first result in the form of a two-step converging process in a second-order linear discrete system was obtained in 2001 when we were developing an advanced deadbeat control algorithm for a technical device. The purpose of the algorithm was to eliminate the transformation of the matrix to the Frobenius form, which is necessary in the well-known method and requires extra time or additional hardware. This was accomplished through a special type of a feedback in which the first difference of the state vector was used instead of the vector itself. The equation of motion expressed in such form has been formally representing a particular case of the canonical form of a two-layer iterative method.
To find eigenvalues of a matrix, a novel transformation based on the dependencies between the elements of the matrix and its spectrum has been developed. This transformation enabled the elements of the feedback vector to be found for setting desired spectrum. This was how the engineering problem of synthesizing a deadbeat controller was solved for a wide class of technical devices such as semiconductor power converters that are widely used in almost all areas of human activity.
Later it turned out that new methods allowed us to use them not only in control theory to implement control algorithms for technical systems, but also to obtain a qualitatively new effect in mathematics, which refutes the postulate about the approximation nature of a simple-iteration method for solving SLAE.
The basics of the method for transforming a matrix spectrum were expounded in   . The method for solving a linear difference equation in a finite number of steps was presented in several journals, for example, in  . In this way, the possibility to find the exact solution of an SLAE by using iterative procedure with a stationary matrix has been confirmed.
In this paper, the possibility of obtaining the exact solution of an SLAE in a finite number of iterations is demonstrated for the first time. A theorem is formulated and proved. For a wide audience without a special mathematical background, the example of solving the simplest SLAE is presented for clarity and understanding. In addition, for the sake of clarity, two types of transformation are given. The first type of transformation provides a unite spectrum of the algebraic equation matrix, while the second type derives the nilpotent matrix from the canonical form of a two-layer iterative method. The result of the iterations is represented in the form of Cramer’s formulas known in the school course of mathematics. This directly denies the above opinions about the impossibility of obtaining an exact solution of SLAE in a finite number of iterations.
5. Theorem and Proof
Theorem. To find a solution of an SLAE
where х and b are the unknown and known vectors of k size, respectively, А is a square nonsingular matrix of k size, in a finite number of iterations, it is necessary and sufficient to reduce (1) to the form
where E is a unipotent matrix with unit spectrum. Then the iterative equation
where , I is the identity matrix, for an arbitrary initial vector х0, generates the exact solution (excluding round-off errors)
no more than for m ≤ k iterations.
Proof. The matrix Е is split into the identity matrix I and the nilpotent matrix N with the intrinsic property
A non-unipotent matrix does not form a nilpotent one, and, with с = 0, the solution to (3) given by
depends on х(0). This proves the necessity.
The sufficiency follows from the solution of (3) by using (5) for n = k:
Remark 1. The simple-iteration method is approximate due to the extension of the condition det(A) ¹ 0 to the matrix of the iteration equation, as follows from control theory and this statement is confirmed here, but this is not necessary.
Remark 2. The transformation of the difference equation to the form with nilpotent matrix, used in control theory, with c = 0, results in to zero in a finite number of steps, and, with c ¹ 0, it gives the shifted vector (as it was named in  ) instead of the solution.
Remark 3. The specified spectrum is formed by changing the elements of a row of the matrix A itself, while in control theory, a row of the elements of the characteristic polynomial of the Frobenius matrix is changed, which is obtained by the transformation of A.
Remark 4. There exist values х0 such that the number m equals to , in particular, m = k – 1 for х(0) = с.
Remark 5. There exists a variety of unipotent matrices satisfying (2) so the solution (7) can be obtained by using different nilpotent matrices.
The iterative method for exact solution of an SLAE in a finite number of steps has the computational procedure of iterative methods, in the conventional sense, like the Jacobi and Seidel methods, can be called a finite-iterative method. As in control theory, it is based on setting a unit spectrum for the SLAE matrix or a zero spectrum for the matrix of the iteration equation. The main difference is the possibility to solve not only a homogeneous equation, but also a non-homogeneous one.
According to the control theory terminology, the transformation of an SLAE into the form with a unipotent matrix is provided via feedback on the first difference of the desired vector. Such a transformation is mathematically a special case of the canonical form of a one-step two-layer iterative method.
It should be emphasized that the theorem specifies only the possibility of solving SLAE in a finite number of iterations but it does not provide an algorithm for obtaining a nilpotent matrix. As noted above, the algorithm was developed in the context of solving the eigenvalue assignment problem for control the spectrum of the matrix of equation describing a specific technical device. Here, we demonstrate the application of the method that distinctly demonstrates a result in the form of an analytical solution of an SLAE in an iterative way, refuting the statements above.
6. Examples of Solving a System of Two Linear Equations
Consider (1) for k = 2,
, , (8)
and write the system in standard form
6.1. Transformation of an SLAE to the form with a Unipotent Matrix
The objective is to transform the system (9) and obtain the equivalent system (2) with a unipotent matrix E. We write the first Equation of (9) in the form
where h2 is a constant coefficient. Substituting the second unknown
into the right-hand side of (9) results in
After dividing (12) by the constant coefficient h1, we obtain an SLAE in the form (2),
with two (not yet known) coefficients h1 and h2, which are used to control the spectrum, that is, to specify two characteristic numbers λ1 and λ2. According to the theorem, they must be equal to 1. In this case, the matrix E = [ei,j] of (2) satisfies the following conditions
which leads to the following linear system
We rewrite it in the normal form
and find the first coefficient h1 as the determinant of A. The second coefficient h2 is
Substituting h1 and h2 into (13) makes the matrix
unipotent and defines the right-hand side of the first equation of (9).
Let us summarize the above. For the original SLAE Ax = b we obtained the equivalent system of the form Ex = c with the unit spectrum of E. The preparatory stage called a forward elimination in the Gauss method is completed. According to the theorem, the iterative process, with a nilpotent matrix
should provide the exact solution no more than in two iterations. We have to show it.
First, we make sure the matrix (19) is nilpotent. To do this, we use (14) to calculate
so the matrix (19) is really nilpotent. In the next place, using the expression (3) we execute two iterations
, . (21)
Due to the property (5), the first summand in (21) is zero. This mathematical statement says that the result does not depend on x(0). The matrix factor in the second summand, due to the equality
is the inverse matrix of the equivalent system (2), which either has the unite spectrum. Therefore, the second iteration actually representing the product of E-1 by c,
after simplifications gives an analytical solution of the SLAE in the form of Cramer’s formulas
where , , .
The expression (24) represents the solution of a system known as Cramer’s formulas (or Cramer’s rule) in a school course of mathematics. This confirms the possibility to obtain an exact solution of an SLAE in iterative way with stationary matrix and evidently proves that the postulate is false. The form of (24) suggests that this expression can be generalized to an SLAE of an arbitrary order k and the exact solution can be found at the k-th iteration,
In accordance with Remark 4, the exact solution can be obtained for a number of iterations not exceeding the order of the system. In this example, the exact solution is found after one iteration if we choose the initial vector x(0) equal to the right-hand side c of the equivalent system. Then the solution (24) follows at the first iteration,
The same results can be gained by transformation of the second equation in (9) instead of the first one as it shown in  .
6.2. Transformation of an SLAE to the Form with a Nilpotent Matrix Obtained from Canonical Form of Two-Layer Iterative Method
The transformation is that any one row of the iterative system is changed and coefficients are determined in order to obtain a given spectrum of a matrix, in this case, to be a zero spectrum. We write (1) in canonical two-layer form  with a single iteration parameter,
and recall that the second summand in (27) plays a role of the feedback in control theory.
Taking a rank-one matrix
whose elements play the same role as in the first example, we expand the first equation
We write the second Equation of (9) as
and then represent it in the indexed form
Substituting (31) into (29) leads to an iterative equation with two coefficients h1 and h2,
Here, h1 and h2 are determined from the nilpotency condition (20). Substituting the elements of (32) into (20) gives a linear system
expressed in normal form
whose solution is
where h1 is the determinant (except for sign) like in the first type of transformation.
Substituting (35) into (32) make the matrix nilpotent (it is easy to check),
while the matrix of algebraic system becomes unipotent,
As a result, for х(0) = c, iterative equation with the matrix (30) gives the solution of the SLAE in the form of Cramer’s formulas
after the first iteration.
In this paper, the possibility of exact solution of an SLAE by iterations with a stationary matrix has been demonstrated. Two examples are given to illustrate different approaches for finding the exact solution of a simplest SLAE by using the transformation of an original system to the form with unipotent or nilpotent matrix. It is shown that an exact solution of an SLAE is obtained in the form of Cramer’s formulas. The fallacy of the postulate about the approximation nature of a simple-iteration method has been proved. Therefore, there is a need to prepare appropriate corrections in order to include them in educational programs on methods for solving linear systems.