The schur decomposition of an n times n matrix is A = QTQ^T where Q is orthogona

Question

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?

Explanation / Answer

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 QT=Q-1

Hence QQT=QTQ = I

Hence, we can say that each iteration in calculation is a similarity transformation A -> QTAQ. 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 2mn2 - 2/3n3. As here A is an n X n order matrix, cost of factorization will be 2n3 - 2/3n3 = (6-2)/3n3 = (4/3)n3 which is the same as previous. Hence, in this case also each iteration of schur_qr will cost the same.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.