Power method and deflation techniques

Question

I wrote a python code to find largest eigen value n corresponding eigen vector using power method for a NON-SYMMETRIC matrix. I could get correct answer with this.

Now, I want to find the 2nd largest eigen value and corresponding eigen vector for the same NON-SYMMETRIC matrix..I tried deflation technique but couldn't get correct answer. How to apply deflation techniques for NON-SYMMETRIC matrices?

Answer 1

There is an example on here of the QR iteration with deflation.

In general the QR algorithm without shifts takes a matrix $A$

$$A^{0} = A \tag{1} $$

$$ \textrm{ for k = 1,2 } \cdots $$

$$Q^{k}R^{k} = A^{k-1} \tag{2} \textrm{ QR factorization } $$

$$ A^{k} = R^{k}Q^{k} \tag{3} \textrm{ recombine in reverse} $$

This is a matlab implementation it requires two other scripts.

function H = qritrsse(A,numitr)
%QRITRSSE Explicit single-shift QR iteration
%H = qritrsse(A,numitr) returns an upper Hessenberg matrix H, starting
%from an arbitrary matrix A, using single-shift explicit QR iteration.
%numitr is the user-supplied number of iterations.  See Section 8.9.4 of
%the book.
%input  : Matrix A and integer numitr
%output : Matrix H
    [m,n] = size(A);
        if m~=n
            disp('matrix A  is not square')  ;
            return;
        end;
        [H,PP] = givhess(A);
        for k = 0 : numitr
         Hnn = H(n,n);
         [Q,R] = qr(H - Hnn*eye(n,n));
         H = R * Q + Hnn*eye(n,n);
        end;
        end;

This script is the givens hessenberg reduction

function [H,P] = givhess(A)
%GIVHS  Givens Hessenberg reduction 
%[H,P] = givhess(A) produces an upper Hessenberg matrix H
%and an orthogonal matrix P using the Givens
%method so that H is orthogonally similar to A.  PAP' = H.
%P is the product of (n-i+1) Givens rotations.
%This program implements Algorithm 5.5.4 of the book.
%input  : Matrix A
%output : Matrices H and P 
        [m,n] = size(A);
        P = eye(m,m);
        for p= 1: n-2
         for  q = p+2:n
           x=[A(p+1,p) A(q,p)]';
           [c,s] = givzero(x);
           k = p+1;
           l = q;
           p1 =  c * P(k,:) + s*P(l,:);
           p2 = -s * P(k,:) + c*P(l,:);
           P(k,:) = p1;
           P(l,:) = p2;
           a1 = c * A(k,:) + s*A(l,:);
           a2 =-s * A(k,:) + c *A(l,:);
           A(k,:) = a1;
           A(l,:) = a2;
           a3 = c * A(:,k) + s*A(:,l);
           a4 = -s * A(:,k) + c *A(:,l);
           A(:,k) = a3;
           A(:,l) = a4;
         end
        end 
        H = A;
        end;

This script zeros it.

  function [c,s] = givzero(x)
%GIVZERO Givens zeroing in a vector x.
%[c,s] = givzero(x) produces the Givens parameters c and s
%for a 2-vector x such that J(1,2,theta)x has a zero 
%in the second place. c = cos(theta), s = sin(theta).
%This program implements Algorithm 5.5.1 of the book.
%input   : Vector x 
%output  : Scalars c and s 
        if abs(x(2)) > abs(x(1))
           t = x(1)/x(2);
            s = 1/((1+t*t)^.5);
            c = s*t ;
        else
           t = x(2)/x(1);
            c = 1/((1+t*t)^.5);
            s = c*t ;
        end


        end;

Most of what you have to do is change the arrays with numpy.