Householder method : Which α do we take?

• MHB
• mathmari
In summary, the conversation discusses the process of calculating the QR factorisation of a matrix using the Householder method. The first step involves finding the first column of the matrix, then determining the value of alpha and taking the sign to make the norm of the difference large. This is followed by finding the matrix H1 and using it to find the new matrix A^(1). The next step involves finding the first column of a 2x2 submatrix and determining the value of alpha. If the norms are equal, then it does not matter which one is chosen as the impact on calculation errors will be the same. The conversation ends with the understanding that the results may be different, but the impact of calculation errors will be minimized to the
mathmari
Gold Member
MHB
Hey!

We have the matrix $A=\begin{pmatrix}1 & 4 & -1 \\ 2 & 2 & 7 \\ 2 & -4 & 7\end{pmatrix}$ and we want to calculate the $QR$ factorisation using the Householder method.

First we take the first column of the matrix $a_0=\begin{pmatrix}1 \\ 2 \\ 2\end{pmatrix}$.
We have that $\alpha=\pm \|a_0\|=\pm \sqrt{9}\pm 3$.
Then we take the sign of that so that $\|a_0-\alpha e_1\|_2$ is big.
We have $$\|a_0-\alpha e_1\|_2=\begin{cases}\|\begin{pmatrix}1 \\ 2 \\ 2\end{pmatrix}-\begin{pmatrix}3 \\ 0 \\ 0\end{pmatrix}\|_2 =\|\begin{pmatrix}-2 \\ 2 \\ 2\end{pmatrix} =\sqrt{12}\\ \|\begin{pmatrix}1 \\ 2 \\ 2\end{pmatrix}-\begin{pmatrix}-3 \\ 0 \\ 0\end{pmatrix}\|_2 =\|\begin{pmatrix}4 \\ 2 \\ 2\end{pmatrix}\end{cases} =\sqrt{20}$$
So we take $\alpha=-3$.
Then $u=\frac{1}{\|a_0-\alpha e_1\|_2}\begin{pmatrix}4 \\ 2 \\ 2\end{pmatrix}=\begin{pmatrix}\frac{4}{\sqrt{20}} \\ \frac{2}{\sqrt{20}} \\ \frac{2}{\sqrt{20}}\end{pmatrix}$.
Then $$H_1=I-2uu^T=\cdots =\begin{pmatrix}-1/3 & -2/3 & -2/3 \\ -2/3 & 2/3 & -1/3 \\ -2/3 & -1/3 & 2/3\end{pmatrix}$$
Then $A^{(1)}=H_1\cdot A=\begin{pmatrix}-3 & 0 & -9 \\ 0 & 0 & 3 \\ 0 & -6 & 3\end{pmatrix}$.
Then we consider the first column of the $2\times 2$-submatrix, $a_1=\begin{pmatrix}0 \\ -6\end{pmatrix}$.
Then $\alpha=\pm \|a_1\|=\pm 6$.
We have $$\|a_1-\alpha e_1\|_2=\begin{cases}\|\begin{pmatrix}0 \\ -6\end{pmatrix}-\begin{pmatrix}6\\ 0\end{pmatrix}\|_2 =\|\begin{pmatrix}-6 \\ -6\end{pmatrix} =6\sqrt{2}\\ \|\begin{pmatrix}0\\ -6\end{pmatrix}-\begin{pmatrix}-6 \\ 0\end{pmatrix}\|_2 =\|\begin{pmatrix}6 \\ 0\end{pmatrix}\end{cases} =6\sqrt{2}$$
In this case the norms are equal, which $\alpha$ do we take then?

:unsure:

mathmari said:
In this case the norms are equal, which $\alpha$ do we take then?
Since the norms are equal, the impact on the calculation error is the same.
So it doesn't matter which one we pick. You can choose.

Klaas van Aarsen said:
Since the norms are equal, the impact on the calculation error is the same.
So it doesn't matter which one we pick. You can choose.

But the result that we get will be different, or not? :unsure:

mathmari said:
But the result that we get will be different, or not?
We may find a different QR decomposition, but the impact of calculation errors will have been minimized to the same extent.

Klaas van Aarsen said:
We may find a different QR decomposition, but the impact of calculation errors will have been minimized to the same extent.

Ok! Thank you!

1. What is the Householder method?

The Householder method is a numerical algorithm used to find the eigenvalues and eigenvectors of a square matrix. It is named after Alston Scott Householder, who first described the method in 1958.

2. How does the Householder method work?

The Householder method works by using a series of elementary reflections to transform a given matrix into a tridiagonal form, which is easier to work with. The eigenvalues and eigenvectors can then be calculated from this tridiagonal matrix.

3. What is the significance of α in the Householder method?

α (alpha) is a parameter used in the Householder method to determine the direction of the elementary reflections. It is typically chosen to be the first element in the column or row being transformed, but other values can also be used.

4. How do we choose the value of α in the Householder method?

The value of α in the Householder method can be chosen in various ways, such as the first element in the column or row being transformed, the maximum element in the column or row, or a random value. The choice of α can affect the efficiency and accuracy of the method, so it is important to consider the properties of the matrix being worked on.

5. What happens if we choose the wrong value of α in the Householder method?

If the wrong value of α is chosen in the Householder method, it can lead to inaccurate results or a slower convergence of the algorithm. It is important to choose a value of α that will result in a more efficient and accurate calculation of the eigenvalues and eigenvectors.

• General Math
Replies
2
Views
1K
• General Math
Replies
2
Views
1K
• General Math
Replies
9
Views
2K
• General Math
Replies
10
Views
2K
• General Math
Replies
5
Views
2K
• General Math
Replies
21
Views
4K
• General Math
Replies
13
Views
3K
• Linear and Abstract Algebra
Replies
2
Views
867