Numerical Analysis/Householder transformation exercises

Householder's method Exercises

Exercise 1

This exercise will help you in introducing how to perform the Householder's method to transform a symmetric matrix A into the tridiagonal form. All of the notations and computations in this Exercise follow from those in Section 9.3, Numerical Analysis, Burden and Faires, 8th Edition. It's recommended that you read that section before solving the problem. It's also recommended that you read the following useful links
1. Householder's method for symmetric matrices, J. H. Wilkinson, Handbook Series Linear Algebra, Volume 4, Number 1 / December, 1962, Springer Berlin / Heidelberg.
2. Module for Householder Transformations, Mathematics Department, California State University, Fullerton.

Problem
Let

$A=\left[\begin{array}{cccc}5& -1& -4& 2\\ -1& 3& 2& 3\\ -4& 2& 4& -3\\ 2& 3& -3& 2\end{array}\right].$

Perform Householder's method to bring A into a tridiagonal form.

Solution

Step 1: k = 1 (Meaning: Making 0's for the third and fourth rows of the first column) <quiz display=simple> { |type="{}"} $\alpha =-sgn(a_{k+1,k})\sqrt{\sum _{j=k+1}^n{a}_{jk}^2}$ is { 4.5825 _10 }.

{ |type="{}"} $r=\sqrt{\frac{1}{2}({\alpha }^2-a_{k+1,k}\alpha )}$ is { 3.5765 5% _10 }.

{ |type="{}"} Now, we are going to find the vector $w^{(1)}=\left[\begin{array}{c}{w}_1^{(1)}\\ w_2^{(1)}\\ w_3^{(1)}\\ w_4^{(1)}\end{array}\right]$ Set $w_1^{(1)}=0$, we need to find $w_2^{(1)},w_3^{(1)},w_4^{(1)}$ $w_2^{(1)}=\frac{a_{2,1}-\alpha }{2r}=$ { -0.7805 5% _10}. $w_j^{(1)}=\frac{a_{j,1}}{2r}$ for j = 3 and 4 gives $w_3^{(1)}=\frac{a_{3,1}}{2r}=$ { -0.5592 5% _10} $w_4^{(1)}=\frac{a_{4,1}}{2r}=$ { 0.2796 5% _10}

{ |type="{}"} The orthogonal matrix $P^1$, defined as $P^1=I-2w^{(1)}(w^{(1)}{)}^t$ is (click Submit to see the answer) || $P^1=\left[\begin{array}{cccc}1& 0& 0& 0\\ 0& -0.2182& -0.8729& 0.4364\\ 0& -0.8729& 0.3746& 0.3127\\ 0& 0.4364& 0.3127& 0.8436\end{array}\right]$.

{ |type="{}"} The new matrix $A^{(1)}$, defined as $A^{(1)}=P^{1}A{P}^1$, should be in the form $A^{(1)}=\left[\begin{array}{cccc}*& *& 0& 0\\ **& *& *& *\\ 0& *& *& *\\ 0& *& *& *\end{array}\right]$ ||$A^{(1)}=\left[\begin{array}{cccc}5& 4.5826& 0& 0\\ 4.5826& 6.0476& -0.1222& 0.2793\\ 0& -0.1222& -0.6059& -3.4068\\ 0& 0.2793& -3.4068& 3.5582\end{array}\right]$ This is the end of Step 1. </quiz>

Step 2: k = 2 (Meaning: Making 0's for the fourth row of the second column)
In Step 2, we redo the computations in Step 1 with the matrix $A=A^{(1)}$ <quiz display=simple> { |type="{}"} $\alpha =-sgn(a_{k+1,k})\sqrt{\sum _{j=k+1}^n{a}_{jk}^2}$ is { 0.3050 _10 }.

{ |type="{}"} $r=\sqrt{\frac{1}{2}({\alpha }^2-a_{k+1,k}\alpha )}$ is { 0.2552 5% _10 }.

{ |type="{}"} Now, find the vector $w^{(2)}=\left[\begin{array}{c}{w}_1^{(2)}\\ w_2^{(2)}\\ w_3^{(2)}\\ w_4^{(2)}\end{array}\right]$ Set $w_1^{(2)}=w_2^{(2)}=0$, we need to find $w_3^{(2)},w_4^{(2)}$ $w_3^{(2)}=\frac{a_{2,1}-\alpha }{2r}=$ { -0.8369 5% _10}. $w_4^{(2)}=\frac{a_{4,1}}{2r}=$ { 0.5473 5% _10}

{ |type="{}"} The orthogonal matrix $P^2$, defined as $P^2=I-2w^{(2)}(w^{(2)}{)}^t$ is (click Submit to see the answer) || $P^2=\left[\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& -0.4009& 0.9161\\ 0& 0& 0.9161& 0.4009\end{array}\right]$.

{ |type="{}"} The new matrix $A^{(2)}$, defined as $A^{(2)}=P^2{A}^{(1)}{P}^2$, should be in the form $A^{(2)}=\left[\begin{array}{cccc}*& *& 0& 0\\ **& *& *& 0\\ 0& *& *& *\\ 0& 0& *& *\end{array}\right]$ ||$A^{(2)}=\left[\begin{array}{cccc}5& 4.5826& 0& 0\\ 4.5826& 6.0476& 0.3049& 0\\ 0& 0.3049& 5.3914& -0.7824\\ 0& 0& -0.7824& -2.4390\end{array}\right]$ This is the end of Step 2. </quiz> Now the matrix $A^{(2)}$ is in a tridiagonal form. The Householder's method is complete.

Exercise 2

<quiz display=simple> {Householder's method is for |type="()"} - Any matrix. - A non-symmetric positive define matrix. + A symmetric matrix. - A non-symmetric diagonally dominant matrix.

{The goal of Householder's method is for |type="()"} - Finding the determinant of a matrix. + Transforming a matrix to tridiagonal form. - Finding eigenvalues of a matrix. - Finding the LU decomposition of a matrix.

{How many steps do we need to perform in Householder's method |type="()"} - n steps (where n is the size of the matrix). - 2n steps. - $\frac{n}{2}$ steps. + n-2 steps.

{What should be performed after Householder's method |type="()"} - LU decomposition. - Support Vector Decomposition (SVD). - Power method. + QR decomposition.

{Will the Householder's method ever fail |type="()"} - Yes + No. </quiz>

Exercise 3

Problem
Based on the computations performed in Exercise 1, write code in Matlab to perform the Householder's method for an input symmetric matrix A.

Solution <quiz display=simple>

||

% Get the size of the matrix A
[n m] = size(A);
% Define the Identity matrix of size of A
I = diag(ones(1,n));
% Householder's method with details
for k = 1 : (n-2)
    % Define the vector w. Initially, w is a zero vector
    w = zeros(n,1);
    % Compute \alpha^2
    alpha_square = sum(A(k+1:n,k)'*A(k+1:n,k))
    % Get \alpha with the appropriate sign
    ap = -sign(A(k+1,k))*sqrt(alpha_square)
    % Find r
    r = sqrt((alpha_square-A(k+1,k)*ap)/2)
    r2 = 2*r;
    % Find w(k+1)
    w(k+1) = (A(k+1,k)-ap)/r2;
    % Find w(j) for j from k+2 to n
    for j = (k+2) : n
        w(j) = A(j,k)/r2;
    end;
    w
    % From the orthogonal matrix P
    P = I - 2*w*w'
    % Update the matrix A
    A = P*A*P
end;

}

</quiz>
132.235.39.18 19:02, 28 May 2009 (UTC) Nam Nguyen