1

First of all, i have to admit that i am really knew to this numeric stuff.

I have to detect two complex Eigenvalues of a Matrix and therefor i implemented some easy QR-Algorithm with MatLab. I am using the Wilkinson-Shift - i think. My Code Looks like this:

function [lambda, errors, iterations] = QRAlgo(A, precision, angle)
    AB = A;
    iterations = 0;
    errors = zeros(1, length(A));

    lambdaMatlab = eig(A);

    for i = 1:1000
        [Q, R] = qr(AB);

        l = diag(AB);
        if (abs(l(1) - AB(4)) < abs(l(2) - AB(4))) % Use the shift which is closer to a_{nn}
           p = l(1);
        else
            p = l(2);
        end

        if (iterations > 25) % QR-Algorithm is stagnating (Need new detector for this Scenario)
            p = rand + i*rand;
        end

        AB = R*Q - (p*eye(2));   % Wilkinson-Shift


        iterations = iterations + 1;

        lambda = diag(AB);
        if (abs(lambda(1) - lambdaMatlab(1)) < abs(lambda(2) - lambdaMatlab(1)))
            errors(1) = abs(lambda(1) - lambdaMatlab(1));
            errors(2) = abs(lambda(2) - lambdaMatlab(2));
            %disp(sprintf('%f -- %f / %f -- %f', lambda(1), lambdaMatlab(1), lambda(2), lambdaMatlab(2)));
        else
            errors(1) = abs(lambda(1) - lambdaMatlab(2));
            errors(2) = abs(lambda(2) - lambdaMatlab(1));
            %disp(sprintf('%f -- %f / %f -- %f', lambda(1), lambdaMatlab(2), lambda(2), lambdaMatlab(1)));
        end

        if (errors(1) < precision && errors(2) < precision)
           break; 
        end
    end

    disp(sprintf('%d°: 1. Error: %f; 2. Error: %f; Iterations: %i; Precision: %f', angle, errors(1), errors(2), iterations, precision));

end

For some Kind of imput data that algorithm works quite fine, although its definitively not the best one. For some other cases the algorithm quits with 1000 iterations which is the same as it was not able to find a solution. One of those bad Input data is this Matrix:

   0.0000 - 0.0000i   0.9981 + 0.0488i
   0.9996 + 0.0000i   0.0001 - 0.0484i

Its obvious that a(1) and a(4) are really bad choices for using as a Wilkinson-Shift. But how to handle those Scenarios?

The above Matrix is build of real data. So it is not one test case which will mostly never occure - it WILL come to those matrices.

Sorry for my bad english.

I am looking Forward to your help :-)

Roland
  • 49
  • You appear to be missing a line in which you shift back. Once you subtract p * I you have to add it back in the next loop. – Christopher A. Wong Jun 08 '15 at 16:52
  • Sorry, i did not get what you mean. Can you provide some pseudo-code to clarify this issue? – Roland Jun 08 '15 at 16:59
  • You write AB = R*Q - (p*eye(2)); which means you just subtracted pI from the matrix. Therefore the subsequent matrix is not going to be similar to the original matrix unless you add back pI. The usual pseudocode looks something like... `p = AB(n,n); [Q,R] = qr(AB - pI);AB = RQ + pI` – Christopher A. Wong Jun 08 '15 at 17:02
  • Great! Thank you a lot Christopher A. Wong! You just solved my Problem :-)

    I literally love the StackExchangeCommunity :-)

    – Roland Jun 08 '15 at 17:23

0 Answers0