- #1
Mathmos6
- 81
- 0
Hey there all!
I'm a little confused by the concept of Givens rotations and was hoping someone could help elaborate a little bit with the following problem for me - if i could get some help understanding how to approach the problem it would be a really great help to me.
'Let A be an n x n matrix, and for i = 1, 2, ..., n let k(i) be the number of zero elements in the i-th row of A that come before all nonzero elements in this row and before the diagonal element [tex]a_{ii}[/tex]. Show that the QR factorization of A can be calculated by using at most [tex]\frac{1}{2}n(n-1)-\sum k(i)[/tex] Givens rotations. Hence show that, if A is an upper triangular matrix except that there are nonzero elements in its first column, i.e. [tex]a_{ij} = 0[/tex] when [tex]2 \leq k < i \leq n[/tex], then its QR factorisation can be calculated using only 2n-3 Givens rotations: you should try finding the order of the first (n-2) rotations that brings your matrix to the form considered above.'
Now the first part seems almost too obvious for me to be understanding it properly; I know that there always exists a Givens rotation to zero out any element we choose in A, and so essentially the problem comes down to making the matrix upper-triangular by removing all the non-zero elements below the diagonal; there are [tex]n(n-1)/2[/tex] elements down there in total, and at least [tex]\sum k(i)[/tex] of those are zero, so at most [tex]\frac{1}{2}n(n-1)-\sum k(i)[/tex] non-zero elements below the diagonal, so then at most that many rotations, right? I'm not sure if perhaps the problem lies in showing that by zeroing out one element, we don't make a previously zeroed element nonzero (or is that not necessarily true?), or if I'm missing something else about the problem. I don't feel like I've actually done anything mathematical rather than simply heuristic so far with the problem, which does concern me.
For the second part, it seems logical that we want to use our Givens rotations to maximize the k(i) in each row, in order to minimize the overall sum - in which case presumably we want each of our n-1 nonzero elements below the diagonal to be '''immediately''' below the diagonal (as one of the elements in the column already is), so is it simply a case of shifting the other n-2 elements in the first column so they're below the diagonal by using some specific order of Givens rotations? In which case, I suspect the rotations I need to use are the ones which simply switch two rows (since we're left multiplying by the rotation matrices; the matrices I'm referring to are the ones corresponding to the elementary row operation of row-switching). My thoughts are to shift every row down one position, which effectively shifts our diagonal one place lower, except for the very top-row which is now empty except for the first and last elements; still, that doesn't really seem to solve my problem, because no matter what way I permute the rows, there will always be an element in the left-hand and right-hand column, as is the case for every row. If I could switch columns around, then I think this approach would work, but that would correspond to right-multiplication by the Givens rotation matrices, and I'm fairly sure that wouldn't give you a 'QR' factorisation - I'm very confused!
I'd hugely appreciate any light you could shed on the problem - I'm not a huge fan of numerical analysis and I just want to get this work done and get on to something like complex analysis, far more enjoyable! :) Thanks to all very much in advance, and I'll try and respond to everything ASAP if I can get to a computer.
I'm a little confused by the concept of Givens rotations and was hoping someone could help elaborate a little bit with the following problem for me - if i could get some help understanding how to approach the problem it would be a really great help to me.
'Let A be an n x n matrix, and for i = 1, 2, ..., n let k(i) be the number of zero elements in the i-th row of A that come before all nonzero elements in this row and before the diagonal element [tex]a_{ii}[/tex]. Show that the QR factorization of A can be calculated by using at most [tex]\frac{1}{2}n(n-1)-\sum k(i)[/tex] Givens rotations. Hence show that, if A is an upper triangular matrix except that there are nonzero elements in its first column, i.e. [tex]a_{ij} = 0[/tex] when [tex]2 \leq k < i \leq n[/tex], then its QR factorisation can be calculated using only 2n-3 Givens rotations: you should try finding the order of the first (n-2) rotations that brings your matrix to the form considered above.'
Now the first part seems almost too obvious for me to be understanding it properly; I know that there always exists a Givens rotation to zero out any element we choose in A, and so essentially the problem comes down to making the matrix upper-triangular by removing all the non-zero elements below the diagonal; there are [tex]n(n-1)/2[/tex] elements down there in total, and at least [tex]\sum k(i)[/tex] of those are zero, so at most [tex]\frac{1}{2}n(n-1)-\sum k(i)[/tex] non-zero elements below the diagonal, so then at most that many rotations, right? I'm not sure if perhaps the problem lies in showing that by zeroing out one element, we don't make a previously zeroed element nonzero (or is that not necessarily true?), or if I'm missing something else about the problem. I don't feel like I've actually done anything mathematical rather than simply heuristic so far with the problem, which does concern me.
For the second part, it seems logical that we want to use our Givens rotations to maximize the k(i) in each row, in order to minimize the overall sum - in which case presumably we want each of our n-1 nonzero elements below the diagonal to be '''immediately''' below the diagonal (as one of the elements in the column already is), so is it simply a case of shifting the other n-2 elements in the first column so they're below the diagonal by using some specific order of Givens rotations? In which case, I suspect the rotations I need to use are the ones which simply switch two rows (since we're left multiplying by the rotation matrices; the matrices I'm referring to are the ones corresponding to the elementary row operation of row-switching). My thoughts are to shift every row down one position, which effectively shifts our diagonal one place lower, except for the very top-row which is now empty except for the first and last elements; still, that doesn't really seem to solve my problem, because no matter what way I permute the rows, there will always be an element in the left-hand and right-hand column, as is the case for every row. If I could switch columns around, then I think this approach would work, but that would correspond to right-multiplication by the Givens rotation matrices, and I'm fairly sure that wouldn't give you a 'QR' factorisation - I'm very confused!
I'd hugely appreciate any light you could shed on the problem - I'm not a huge fan of numerical analysis and I just want to get this work done and get on to something like complex analysis, far more enjoyable! :) Thanks to all very much in advance, and I'll try and respond to everything ASAP if I can get to a computer.