Exact stop condition for QR-algorithm I'm trying to implement unshifted QR-algorithm for finding all eigenvalues of matrix. Now I'm doing QR-decomposition with Householder reflections. My program almost works but I'm confused with stop conditions. Now I'm checking if each Aij below the main diagonal is less than eps (by absolute value). But that approach does not work, because for too low epsilon loop might become infinite (some Aij below the main diagonal stops converging to zero at some moment and it's value starts to fluctuate near zero instead). So, I can't set fixed accuracy for my algorithm at the moment. Please, help.
bool isUpperTriangularEnough(const matrix &a)
{
    for(int i=0; i<a.getRows(); i++)
    {
        for(int j=0; j<a.getCols(); j++)
        {
            if(j < i && abs(a.getElemAt(i,j)) > eps)
                return false;
        }
    }
    return true;
}

    while(!isUpperTriangularEnough(A_k))
    {
        matrix R = A_k, A_st,current_v,current_Q,Q=matrix::ident(A_k.getCols());
        for(int i=0; i<(A_k.getCols()-1); i++)
        {
            A_st = R;
            identize(A_st,i);
            current_v = getVectorV(A_st, i);
            current_Q = matrix::ident(A_st.getCols()) + (-2.0)*(current_v ^ current_v.transpose());
            R = current_Q^R;
            Q = Q^current_Q;
        }
        A_k = R ^ Q;
    }

matrix getVectorV(const matrix &A, int colIndex)
{
    matrix x = A.getColumn(colIndex);
    matrix e_i(A.getRows(), 1, false);
    e_i.setElemAt(colIndex, 0, 1.0);
    double alpha = x.get2Norm()*(-getSign(x.getElemAt(colIndex, 0)));
    matrix u = x + (-alpha*e_i);
    return u*(1.0/u.get2Norm());
}

void identize(matrix &A, int n)
{
    for(int i=0; i<A.getRows(); i++)
    {
        for(int j=0; j<A.getCols(); j++)
        {
            if(i<n || j<n)
            {
                A.setElemAt(i,j, j==i ? 1.0 : 0.0);
            }
        }
    }
}

Example: stuck in infinite loop with [[12,-51,4],[6,167,-68],[-4,24,-41]] and eps=10e-9

 A: With the real-number QR algorithm one can obviously not get any complex eigenvalues as diagonal entries. They will manifest as diagonal $2\times2$ blocks. So the convergence criterion should allow for such blocks. In the end this might also result in some blocks that have real eigenvalues.
So in the test if the matrix is sufficiently upper-triangular, set a flag to false.

*

*for the lower sub-diagonal entries $j<i-1$ if $|a_{ij}|>\varepsilon$, then return false.

*for the direct subdiagonal, if the flag is set and $|a_{i,i-1}|>ε$, then return false. If the flag is not set and $|a_{i,i-1}|>ε$, then set the flag to true, else clear the flag to false.

bool isUpperTriangularEnough(const matrix &a) {
  bool flag = false;
  for(int i=0; i<a.getRows(); i++) {
    for(int j=0; j<i; j++) {
      if(abs(a.getElemAt(i,j)) > eps) {
        if(j<i-1 or flag) return false;
        flag = true;
      } else {
      flag = false;
      }
    }
    return true;
  }
}

This assumes that j<i always, the matrix should be square so that this condition can be realized in the inner for loop.

To the detected error: The sign is indeed important. From a purely mathematical point of view the reduced vector $\tilde A_i$ gets reflected into $e_i$ or $-e_i$. The normal $v$ of the mirror plane is one of the two bisectors of the lines through $\tilde A_i$ and $e_i$. The bisector between them is $\frac{\tilde A_i}{\|\tilde A_i\|}\pm e_i$ or $\tilde A_i\pm\|\tilde A_i\|e_i$, then normalized to unit length. If $\tilde A_i$ is nearly dominated by its $i$th element, then the sign choice becomes critical, as one variant gives a cancellation to a near zero vector.
The stable sign choice is in conflict with the theoretically nice goal to have a positive diagonal in $R$, so some sources give the unstable choice also in the critical cancellation situation.
