Solving linear systems with the QR factorisation

The QR factorization (function qr) can be used to solve linear systems, say of order n, as an alternative of " \ ", but it induces a considerable increasing errors for the high order unknowns for a large n.

Any explanation for this?

Thank you.

[Matt J]

What illustration of this do you have?

Answer 1

[John D'Errico]

The problem is that a simple QR, WITHOUT column pivoting can yield an unstable solution. You need the pivoting to make it work, and work well.

Is PINV better than a QR, even with pivoting? Better is a difficult thing to pin down, since there are several factors one must consider. In fact, I would argue that you don't really get better performance as Jakub has claimed. But PINV does have some virtues, as does QR.

If the linear system is singular, then a QR based solution will end up with some zero elements. On the same system, PINV will create a solution that has minimum norm. A subtly different solution, but since the system was singular, who knows what the true solution is?

The one difference that may be significant though is the QR will often be faster than a PINV based solution. So if you want speed, then you may care about the difference.

Yes, it is true that I tend to recommend pinv(A)*b to people with singular or nearly singular problems, if only for the reason that it is a lot easier to write. :)

Answer 2

[Jakub Rysanek]

[1] If the solution of Ax=b is believed to be unique:

    [qq,rr] = qr(A);
    x = rr\qq.'*b;

[2] If the system Ax=b has multiple solutions - you can use QR factorization with column pivoting:

    [qq,rr,pp] = qr(A);
    df = abs(diag(rr))<singularity_thresh;
    btilde = qq.';
    Ainv = zeros(length(b));
    Ainv(~df,:) = rr(~df,~df)\btilde(~df,:);
    x = Ainv.'*pp.'*b;

The thing is that you usually get better performance using x=pinv(A)*b;