-This paper illustrates comparison of two methods, which are used for solving systems of linear equations . The aim of the research is to analyze, which method is faster solve this equations and how many iteration required each method for solving. This paper presents some ways to deal with this problem. Also there are analyzed two methods. The first of them minimizes the standard deviation of the next iteration of the solution, the other constructs orthogonal vectors and is theoretically finite method.
Index Terms—conjugate gradient method, steepest descent method, comparison, analysis
Computer algorithms are important methods for numerical processing. In all implementations it is important to make them more efficient and decrease complexity but without loss of efficiency. Cryptographic algorithms are one of most important methods for computer science therefore efficiency and complexity of these is crucial for optimal processing [14]. Knowledge systems demand fast and precise methods for information processing [4], [6]. Similarly decision support models need devoted techniques for lower complexity [12].
This publication present comparison of steepest descent method and conjugate gradient method. These methods are used for solving systems of linear equations. In our publication, we analyze, which method is faster and how many iteration required each method. First, we describe these methods, than we compare them and make conclusions.
II. THE STEEPEST DESCENT METHOD
The steepest descent method formulated by Stiefel. We will present the mathematical description of the method of steepest descent and we will make implementation in the form of code. Consider the system linear equations in the general form
Ax = B
We suppose that matrix A is symmetric and positive definite.
With x we denote solution of the system equations 1, i.e.:
Ax = b. The methods of gradient constructed a sequence of
successive approximations to determine the solutions x with
using formula:
x(k+1) = x(k) + ckr(k)
(
Occurring in the equation 2 vector r(k) is called residuum of system and takes the following form: r(k) = b
Ax(k); or r(k+1) = r(k) ckAr(k) = (I ckA)r(k):
In iterative process this vector can be determined in each iteration of the algorithm as a suitable combination of the previous values, as described is in next formula: r(k+1) = r(k) ckAr(k) The coefficients ck iterations occurring in the equation 3 are determined on the basis of the following equality: kx x(k+1)kB = icnkf kx x(k) ckr(k)kB In contrast, norm k kB is defined as
def pxT Bx kxkB = Matrix B occurring in formula 7 is symmetric and positive definite. At the same time it fulfills the condition the alternation of the matrix A, i.e.: A B = b A. It is not difficult to show that searched coefficients ck are described by the equation: ck = (r(k); B(x
x(k))) (r(k); Br(k)) : Just for some matrix B, you can determine the value of B(x x(k)). For example, if B = A(p), p 2 N then there is following equality:
A(p)(x x(k)) = A(p 1)(b
Ax(k)) = A(p 1)r(k): (
III. CONJUGATE GRADIENT METHOD
We use conjugate gradient method to solve the system of linear equations given in the form of
Ax = b;
(
u rk := DF (xk)T = b
Axk: However, in the case of conjugate gradient method, we must to carry out the minimization of the k dimensions: xk+1 : F (xk+1) =
min F (xk + u1r1 + u1;:::;uk
+ ukrk);
ri := b Axi f or i k:
(
Rk := (r1; r2; : : : ; rk): With the k-dimensional minimilizing point in formula 11 are allowed all vectors from z being in the form of z = xk + Rku; u 2 Rk; where r = rk + ARku is residual vector. Hence, F (z) = 1 rT A 1r = 21 rkT A 1rk + uT RkT rk + 1 uT RkT ARku: 2 2 Differentiating our functional by u, functional adopts a minimum for where ue 2 Rk is solution to the equation We introduce the following designations xk+1 = xk + Rkue; RkT ARkue =
RkT rk: 2 0 3 66 ... 77 66 0 77 RT ARvk = 66 77 6 7 6 7 664 ... 775
R := (r1; : : : ; rk; : : : ; rn); Then we get Rvk = Rkue, and
xk+1 = xk + Rkue = xk + Rvk;
rk+1 = rk + ARkue = rk + ARvk:
From the above fact follows that: 1. RkT rk+1 = 0 by (
F (xk+1) = 21 rkT+1A 1rk+1 = 21 rkT A 1rk + ueT RkT rk+ + 1 uT RkT ARkue = F (xk) 2 e 1 uT RkT ARkue = 2 e 1 = F (xk) 2 (xk+1 xk)T A 1(xk+1 xk): This formula explains the extend of decrease value of functional F in k-th step xk ! xk+1
5. If vector vk = (v1; : : : ; vk; 0; : : : ; 0)rk 6= 0 has k
components, where rk 6= 0 is negative. From formula (
rk) rj+1); (e1 := 0) (18) then
Ark = ((rk+1
rk) Ark = qk+1(rk k 2 X cj (rj j=1 Applying induction we get description for Ark in following form where qk+1, ek are constans and additionally qk+1 = 1=vk > 0. By solving the above equation due tork+1 we get the equality: k 2 rk+1 = rk +[ Ark +ek(rk rk 1)+X cj (rj+1 rj )]=qk+1: j=1 (19) If we take into account orthogonality of vectors r1; : : : ; rk; rk+1, then we can easily demonstrate that all the constants cj disappear. Thus, we obtain formulas for qk+1 i ek. Then, for k 2 1 we get r1T rk+1 = 0 ) 0 = r1T Ark + c1r1T r1 = rkT (Ar1) + c1r1T r1: (20)
By using the formula (17), we can conclude that vector Ar1 also is a linear combination of vectors r1 and r2, then rkT Ar1 = 0 providing that k > 2. Thus, from equality (18) implies that c1 = 0.
We assume, that for some j 1, which satisfying the following inequality 1 j k 2, there is equality c1 = c2 = = cj 1 = 0. Therefore, by using formula(18) as before, we obtain: rjT rk+1 = 0 ) 0 = rkT Arj + cj rjT rj = = rkT (linear combination of vectors rj+1; rj ; : : : ; r1) + cj rjT rj =
cj rjT rj ) cj = 0, vectors r1; : : : ; rk are linearly independent, as is apparent from the fact that r0 6= 0. In this connection, in particular, we have rj 6= 0. Therefore, all solid cj , where j = 1; : : : ; k 2 disappear in equations (17) and (18). Due to the fact, we get rkT 1rk+1 = 0 ) ek = rkT rk+1 = 0 ) qk+1 = rkT Ark 1 = qk rTrkT rk rkT 1rk 1 k 1rk 1 rkT Ark
This gives us an algorithm conjugate gradient method. Initial data: x1 is intended, r1 := b Ax1; e1 := 0. For k = 1; 2; : : : ; n: ]1) If rk = 0, stop; xk is sought for solution. 2) Otherwise, we must to calculate: qk+1 :=
ek; rkT Ark
There is a big difference between presented methods. The steepest descent method is several times faster than conjugate gradient method. But, if we look on iteration of this methods in Table.1, we see, that conjugate method converge after less number of iteration. For example, for n = 20, number of iterations of conjugate gradient method equals 65, and achieve the desired accuracy - 1413.
B. Analysis of time
On graph of time, we can see that, for example, for n = 15 time in ms of conjugate gradient method equals 286 and time in ti of steepst descent method equals 271. After that, we could see, that when number of n increases there is substantial difference between methods. For example, when n = 20, time in ms of conjugate gradient method is equals 1680, time in ti of achieve the desired accuracy - 1621 iterations.
We have compared two method implemented to solve systems of linear equations. The steepest descent method is faster method, because it solve equations in less amount of time. Conjugate gradient method is slower, but more productive, because, it converges after less iterations. So, we can see, that one method can be used, when we want to find solution very fast and another can be converge to maximum in less iteration.