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) to Om2(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γp where γp 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.
H=RQ + µI
=QTHQ (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
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 µI 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 μ2of 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 µ 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 Tmmand hm,m-1are small. In fact hm,m≈µ. Such estimation causes hm,m-1to 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μ2I. The next step entails computing the QR factorization to obtain M= ZR and then calculating the H2=ZTHZ. But Z= μ1μ2 with regards to QR decomposition uniqueness. In this case squaring H results in M, but such an computation requires Om3 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 Z=PoP1P2…Pn-2 and hence Z and Z 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 1Om2decomposition operations but an additional 1Om2 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 1Om3 operations but there are 15m3 additional operations required for an orthogonal matrix Q such that the real Schur decomposition of M is given by M=QTQT(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- µI. 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- µI 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- µI and computing T=RU + µI. While the shift Tmm=µ can be effectively used, Wilkinson shift is more efficient and it is given by µ=Tmm+d-sign(2d2+tm,m-1); d=tm-1,m-1-tmm2 (Watkins, 1982)
The result of the above expression is 2x2 block matrix T with Eigen values closer to Tmm. This shifting also leads to cubic convergence of tm-1,mto 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×m matrix requires 30(m) decomposition operations because it is computed on tri diagonal matrix instead of the Hessenberg matrix, and it requires 6m2 operations for cumulative orthogonal operations. Most of the symmetric operations require 4m33 operations to calculate the Eigen values and an additional 8m3 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).