Epsilon Algorithm

Epsilon Algorithm

The epsilon algorithm is an all-purpose algorithm used to accelerate mathematical and engineering series that converge too slowly. Wynn discovered the algorithm, and he applied it in weakly diverging sequences that he used a fixed operator point as desired limit (Dahlquist & Björck, 2007). However, there are exceptions to Wynn’s application of the epsilon algorithm. For instance, in quantum well oscillators, the epsilon algorithm is not robust enough to obtain a solution. The aim of this paper is to discuss various attributes including the basis of its foundation, mathematical attributes and examples.

Chapter 1: Practical Applications of the QR algorithm

The QR algorithm is used to determine all the values of a full Eigen matrix. Initially, the algorithm required a shift of the origin among other minor changes to make it competitive (Graves, Roberts & Salam, 2000). The QR matrix can be seen as an implementation of simultaneous iteration, and such a perception presents an easier way of understanding the algorithm. This section seeks to discuss practical QR algorithm. In handling the practical QR algorithm, it is necessary to discuss the unsymmetrical Eigen problem as well as the symmetric Eigen problem.

The Unsymmetrical Eigen value Problem

 In computing the eigen values of an m x m matrix M, the efficiency of computing iteration is improved by reducing M to Hessenberg matrix H with the aim of reducing the number of iteration from O(m3)Image removed. to Om2Image removed.(Mathias & Stewart, (1993). However, the convergence of the iteration can be slower than expected. As such, there is need to modify the QR iteration to improve its practicality in computation of general matrix Eigen values. The rate of convergence of the pth sub diagonal entry of the Hessenberg matrix is given as γp+1γpImage removed. where  γpImage removed. denotes the largest Eigen of M in magnitude. If the magnitude of the Eigen values of Matrix are close to each other, then convergence will be slow (Mathias & Stewart, (1993). Shifting the Hessenberg matrix by scalar µ means that the QR factorization that will be computed is H- µI instead of merely H. H is then updated to obtain the new Hessenberg matrix through multiplication of QR orders as before but adding µI. As such, we obtain the matrices shown below.


HImage removed.=RQ + µI

=QTH-µIQ+µIImage removed.

=QTHQ-µQTQ+µIImage removed.

=QTHQ-µI+µIImage removed.

=QTHQImage removed. (Mathias & Stewart, (1993)

The implication of the above equation is that the factorization involves orthogonal similarity transformation of the Hessenberg matrix although only difference is Q. The convergence rate is given by

γp+1-µγp-µImage removed.

The convergence of a sub diagonal entry is rapid if µ is close of one of the Eigen values. If supposing the H cannot be reduced and µ is an Eigen value, the QR factorization of the update H matrix is singular. Then, the first m-1 columns of the updated H matrix becomes linearly independent and also the first m-1 columns R becomes linearly independent. Consequently, the last row of R is zero and hence the last row of RQ. Adding µIImage removed. affects only the diagonal components, and the conclusion is that deflation occurred in one step and H is the unreduced Hessenberg matrix.

For matrices with real Eigen values, it is a common practice to use single shift strategy. However, such a strategy is not effective when computing complex Eigen values (Zhang, 2006). The double shift strategy is effective when dealing with two Eigen values μ1 and μ2Image removed.of the lower right of H matrix are complex. Quadratic convergence of the Eigen values is achieved by shifting the values in consecutive iterations. 

Now supposing that µImage removed. is not an Eigen value but close to the Eigen values, then the updated Hessenberg matrix is near singular and hence the columns are near dependent (Watkins, 1982). Only a few similarity transformations are necessary to achieve decoupling because TmmImage removed.and hm,m-1Image removed.are small. In fact hm,mµImage removed.. Such estimation causes hm,m-1Image removed.to quadratically converge to zero. Apparently, change in shifting causes linear convergence rate. Some applications of the QR decomposition are not practical. For instance, assuming U1U2 is an orthogonal matrix being used to implement similarity transformation of Hessenberg matrix H (Watkins, 1982). The first step entails forming a real arithmetic equation M= H2-μ1+μ2H+μ1μ2IImage removed.. The next step entails computing the QR factorization to obtain M= ZR and then calculating the H2=ZTHZImage removed.. But Z= μ1μ2Image removed. with regards to QR decomposition uniqueness. In this case squaring H results in M, but such an computation requires Om3Image removed. operations, and this makes QR decomposition impractical.    

The Implicit Q Theorem can be used to solve the above problem (Mathias & Stewart, (1993). The approach in the theory is forming M in the first column instead of forming in its entirety. The M formed in this case has three non zero entries since it is second-degree polynomial of the H matrix. We first step of this approach is computing the Householder transformation Po since it makes the first column a e2 multiple. The next step involves computing PoHPo that is relatively shorter than the H matrix since it is derived from the first three rows and columns of the H matrix. The last step involves applying the a Householder reflections P1, P2…..Pn-2 with the aim of restoring the Hessenberg form. However, such reflections are not applicable in the first row and therefore ZImage removed.=PoP1P2…Pn-2 and hence Z and  ZImage removed. have the same first column. According to the Implicit Q theorem, the two matrices are equal because they implement similar transformations and preserve similar form of Hessenberg matrix H. Also, the two matrices produce a similar updated form of the Hessenberg matrix. Such variation of the QR algorithm is call the Francis QR step (Watkins, 1982).


In many practical computations, a Francis step needs 1Om2Image removed.decomposition operations but an additional 1Om2Image removed. operations are necessary in case of orthogonal transformations where the real Schur transformation is being computed from the accumulated transformations (Zhang, 2006). The QR algorithm initial Hessenberg reduction requires 1Om3Image removed. operations but there are 15m3Image removed. additional operations required for an orthogonal matrix Q such that the real Schur decomposition of M is given by M=QTQTImage removed.(Watkins, 1982) (Zhang, 2006).


The Symmetric Eigen value Problem

In the of symmetric Eigen values, the values are real, and therefore double shifting is not required. However, the implicit Q theorem is applied in computing the similarity transformation that is used in each iteration without the need for explicit calculation of T- µIImage removed.. In this case T denotes the tri diagonal matrix that needs to be reduced to diagonal form (Watkins, 1982). However, the first column of T- µIImage removed. is computed and a Householder transformation is performed to make the equation a multiple of e1. Applying the Householder transformation to matrix T results in a series of rotations that can restore the tri diagonal form. From an Implicit Q Theorem, the effect is similar to the computation of the QR factorization and UR=T- µIImage removed. and computing TImage removed.=RU + µI. While the shift Tmm=µImage removed. can be effectively used, Wilkinson shift is more efficient and it is given by µ=Tmm+d-sign(2d2+tm,m-1)Image removed.; d=tm-1,m-1-tmm2Image removed. (Watkins, 1982)


The result of the above expression is 2x2 block matrix T with Eigen values closer to TmmImage removed.. This shifting also leads to cubic convergence of tm-1,mImage removed.to zero.

From the above discussion, it is evident that symmetric QR algorithm is faster than unsymmetrical QR algorithm. A QR algorithm decomposition step for m×mImage removed. matrix requires 30(m)Image removed. decomposition operations because it is computed on tri diagonal matrix instead of the Hessenberg matrix, and it requires 6m2Image removed. operations for cumulative orthogonal operations. Most of the symmetric operations require 4m33Image removed. operations to calculate the Eigen values and an additional 8m3Image removed. operations to accumulate transformations (Watkins, 1982).

Applications of the QR Algorithm

QR factorization is applied in multiple input and multiple output (MIMO) radio through the use of multiple antennas at both the transmitter and receiver since it improve the performance of the communication systems (Watkins, 1982). MIMO significantly improves data throughput and coverage without the need for additional power or bandwidth. The transmitter sends the signal to multiple receivers, and the transmission streams are passed through a matrix channel that contains both  transmission and receiving paths. When the receiving gets the transmitted signal vectors, it decodes the signal into its original information. QR decomposition is numerically stable, and it is used in estimation applications where there a mixing matrix A experiences white noise (Zhang, 2006).