The schur decomposition of an n times n matrix is A QTQT wh

The schur decomposition of an n times n matrix is A = QTQ^T where Q is orthogonal and T is upper triangular. The schur decomposition always exists (though it is not unique) and the eigenvalues a A are all on the diagonal of T. The QR method of computing a Schur factorization consists of the following iteration, which converges to the upper triangular matrix T. Show that each iteration is a similarity transformation A rightarrow Q^T AQ. If QR factorization costs 4/3 n^3 flops, how much does each iteration in schur.qr cost?

Solution

Answer:

1. Similarity transformation: As per the definition of similarity transformation, a matrix A is said to be similar to another matrix B, iff there exists another nonsingular, suppose C, such that

C^-1AC=B.

Then we can write the similarity transformation as:

A -> C^-1AC

In case of Schur decomposition, Q is orthogonal, it means Q^T=Q^-1

Hence QQ^T=Q^TQ = I

Hence, we can say that each iteration in calculation is a similarity transformation A -> Q^TAQ. Moreover, similarity transformation are used to reduce complexity and we can see that A is converging during each iteration.

2. As QR factorization is being performed during each iteration, hence each iteration of schur_qr will cost at least 4/3*n^3 plus the cost of calculating A from Q and R.

3. The cost of QR factorization using Householder algorithm is given by 2mn² - 2/3n³. As here A is an n X n order matrix, cost of factorization will be 2n³ - 2/3n³ = (6-2)/3n³ = (4/3)n³ which is the same as previous. Hence, in this case also each iteration of schur_qr will cost the same.