qr - QR decomposition - MATLAB (original) (raw)

Syntax

Description

[R](#mw%5F8d61d75e-1db6-4a92-bdc1-7dcd43a83aae) = qr([A](#mw%5Faf5047ca-84ac-455a-950b-a6247b2be381)) returns the upper-triangular R factor of the QR decomposition A = Q*R.

example

[[Q](#mw%5Fb041736f-1440-4410-8cd8-02b3547afaa5),[R](#mw%5F8d61d75e-1db6-4a92-bdc1-7dcd43a83aae)] = qr([A](#mw%5Faf5047ca-84ac-455a-950b-a6247b2be381)) performs a QR decomposition on m-by-n matrixA such that A = Q*R. The factorR is an m-by-n upper-triangular matrix, and the factor Q is anm-by-m orthogonal matrix.

example

[[Q](#mw%5Fb041736f-1440-4410-8cd8-02b3547afaa5),[R](#mw%5F8d61d75e-1db6-4a92-bdc1-7dcd43a83aae),[P](#mw%5Fc2df7407-8d9e-49d5-a8d7-37b7fc9da977)] = qr([A](#mw%5Faf5047ca-84ac-455a-950b-a6247b2be381)) additionally returns a permutation matrix P such that A*P = Q*R. If A is full, the permutation matrix is chosen so thatabs(diag(R)) is decreasing.

example

[___] = qr([A](#mw%5Faf5047ca-84ac-455a-950b-a6247b2be381),"econ") produces an economy-size decomposition using any of the previous output argument combinations. The size of the outputs depends on the size of m-by-n matrix A:

If m > n, then qr computes only the first n columns of Q and the firstn rows of R.
If m <= n, then the economy-size decomposition is the same as the regular decomposition.

example

[[Q](#mw%5Fb041736f-1440-4410-8cd8-02b3547afaa5),[R](#mw%5F8d61d75e-1db6-4a92-bdc1-7dcd43a83aae),[P](#mw%5Fc2df7407-8d9e-49d5-a8d7-37b7fc9da977)] = qr([A](#mw%5Faf5047ca-84ac-455a-950b-a6247b2be381),[outputForm](#mw%5F8c2178dc-8ca0-43a1-8640-c3c1be7a2541)) specifies whether to return the permutation information P as a matrix or a vector. For example, if outputForm is "vector", then A(:,P) = Q*R. The default value of outputForm is "matrix" such that A*P = Q*R.

example

[___] = qr([A](#mw%5Faf5047ca-84ac-455a-950b-a6247b2be381),0) is equivalent toqr(A,"econ","vector"). The use of this syntax is not recommended. Use the "econ" option instead.

[[C](#mw%5F4bb3c935-8115-4c5e-b82c-78db3f2d05da),[R](#mw%5F8d61d75e-1db6-4a92-bdc1-7dcd43a83aae)] = qr([S](#mw%5Fd9066d85-7337-4168-a93d-7784697c519d),[B](#mw%5Fa1e55b64-29f5-41ea-bbd1-0bc05782d303)) computes C = Q'*B and the upper-triangular factor R. You can use C and R to compute a least-squares solution to the sparse linear system S*X = B with X = R\C.

example

[[C](#mw%5F4bb3c935-8115-4c5e-b82c-78db3f2d05da),[R](#mw%5F8d61d75e-1db6-4a92-bdc1-7dcd43a83aae),[P](#mw%5Fc2df7407-8d9e-49d5-a8d7-37b7fc9da977)] = qr([S](#mw%5Fd9066d85-7337-4168-a93d-7784697c519d),[B](#mw%5Fa1e55b64-29f5-41ea-bbd1-0bc05782d303)) additionally returns a permutation matrix P that is chosen to reduce fill-in in R. You can use C, R, and P to compute a least-squares solution to the sparse linear systemS*X = B with X = P*(R\C).

example

[___] = qr([S](#mw%5Fd9066d85-7337-4168-a93d-7784697c519d),[B](#mw%5Fa1e55b64-29f5-41ea-bbd1-0bc05782d303),"econ") produces an economy-size decomposition using any of the previous output argument combinations. The size of the outputs depends on the size ofm-by-n sparse matrix S:

If m > n, then qr computes only the first n rows of C andR.
If m <= n, then the economy-size decomposition is the same as the regular decomposition.

example

[[C](#mw%5F4bb3c935-8115-4c5e-b82c-78db3f2d05da),[R](#mw%5F8d61d75e-1db6-4a92-bdc1-7dcd43a83aae),[P](#mw%5Fc2df7407-8d9e-49d5-a8d7-37b7fc9da977)] = qr([S](#mw%5Fd9066d85-7337-4168-a93d-7784697c519d),[B](#mw%5Fa1e55b64-29f5-41ea-bbd1-0bc05782d303),[outputForm](#mw%5F8c2178dc-8ca0-43a1-8640-c3c1be7a2541)) specifies whether to return the permutation information P as a matrix or vector. For example, if outputForm is "vector", then the least-squares solution to S*X = B is X(P,:) = R\C. The default value of outputForm is"matrix" such that the least-squares solution to S*X = B is X = P*(R\C).

example

[___] = qr([S](#mw%5Fd9066d85-7337-4168-a93d-7784697c519d),[B](#mw%5Fa1e55b64-29f5-41ea-bbd1-0bc05782d303),0) is equivalent to qr(S,B,"econ","vector"). The use of this syntax is not recommended. Use the "econ" option instead.

Examples

collapse all

Find the QR decomposition of the 5-by-5 magic square matrix. Specify one output argument to return just the upper-triangular factor.

R = 5×5

-32.4808 -26.6311 -21.3973 -23.7063 -25.8615 0 19.8943 12.3234 1.9439 4.0856 0 0 -24.3985 -11.6316 -3.7415 0 0 0 -20.0982 -9.9739 0 0 0 0 -16.0005

Compute the full QR decomposition of a magic square test matrix by specifying two output arguments.

A = magic(5); [Q,R] = qr(A)

Q = 5×5

-0.5234 0.5058 0.6735 -0.1215 -0.0441 -0.7081 -0.6966 -0.0177 0.0815 -0.0800 -0.1231 0.1367 -0.3558 -0.6307 -0.6646 -0.3079 0.1911 -0.4122 -0.4247 0.7200 -0.3387 0.4514 -0.4996 0.6328 -0.1774

R = 5×5

-32.4808 -26.6311 -21.3973 -23.7063 -25.8615 0 19.8943 12.3234 1.9439 4.0856 0 0 -24.3985 -11.6316 -3.7415 0 0 0 -20.0982 -9.9739 0 0 0 0 -16.0005

Verify that A=QR, within machine precision.

Specify three output arguments to return a permutation matrix or vector that reduces fill-in in the R factor of the QR decomposition.

Compute the QR decomposition of the west0479 sparse matrix. Specify three outputs to return a permutation matrix that satisfies AP=QR.

load west0479 A = west0479; [Q,R,P] = qr(A);

Verify that A*P = Q*R for the permutation matrix P, within machine precision.

Now specify the "vector" option to return p as a permutation vector.

[Q,R,p] = qr(A,"vector");

Verify that A(:,p) = Q*R for the permutation vector p, within machine precision.

Verify that the use of a permutation matrix or permutation vector in the decomposition results in an R factor with fewer nonzeros for sparse inputs compared to a nonpermuted decomposition.

Figure contains an axes object. The axes object with xlabel nz = 59808 contains a line object which displays its values using only markers.

Figure contains an axes object. The axes object with xlabel nz = 6753 contains a line object which displays its values using only markers.

The results show that the permuted decomposition produces an R factor with substantially fewer nonzeros.

Use the economy-size QR decomposition of a coefficient matrix to solve the linear system Ax=b.

Create a 10-by-5 coefficient matrix by using the first five columns of magic(10). For the right-hand side of the linear equation Ax=b, use the row sums of the matrix. With this setup, the solution to the equation x should be a vector of ones.

A = magic(10); A = A(:,1:5)

A = 10×5

92    99     1     8    15
98    80     7    14    16
 4    81    88    20    22
85    87    19    21     3
86    93    25     2     9
17    24    76    83    90
23     5    82    89    91
79     6    13    95    97
10    12    94    96    78
11    18   100    77    84

b = 10×1

215 215 215 215 215 290 290 290 290 290

Compute the economy-size QR decomposition of A. Then solve the linear system QRx=b with x(p,:) = R\(Q'*b). Because Q is orthogonal, this equation is the same as x(p,:) = R\(Q\b) but is computed faster.

[Q,R,p] = qr(A,"econ","vector")

Q = 10×5

-0.0050 -0.4775 -0.0504 0.5193 0.0399 -0.0349 -0.5001 -0.0990 -0.1954 -0.2006 -0.4384 0.1059 -0.4660 0.4464 0.0628 -0.0947 -0.4151 -0.2923 -0.2542 0.5274 -0.1246 -0.4117 -0.2812 -0.1326 -0.4130 -0.3787 0.0209 0.2702 0.4697 0.0390 -0.4085 -0.0017 0.2217 -0.2450 -0.2015 -0.0648 -0.3925 0.6939 0.0669 0.1225 -0.4683 0.0833 0.0283 -0.3038 0.5265 -0.4982 0.0867 0.0394 -0.1822 -0.4138

R = 5×5

-200.7112 -55.5026 -167.6040 -84.7237 -168.7997 0 -192.1053 -40.3557 -152.4040 -39.2814 0 0 101.3180 -89.4254 96.0172 0 0 0 41.0248 -14.9083 0 0 0 0 24.6386

x = 5×1

Make a semilog plot of the diagonal of R to confirm that the permuted decomposition produces an R factor with abs(diag(R)) decreasing. Plot the singular values of A in the same plot for comparison. In practice, the diagonal values of R behave in a similar way to the singular values of A. Therefore, you can use the diagonal values of R as a measure for how close to singular the matrix A is.

semilogy(abs(diag(R)),"-o") hold on semilogy(svd(A),"r-o") legend("Diagonal of R","Singular Values of A")

Figure contains an axes object. The axes object contains 2 objects of type line. These objects represent Diagonal of R, Singular Values of A.

Solve a sparse linear system and use the results to see how much of vector b lies in the column space of S.

Create a random 500-by-20 sparse matrix with 10% density and a vector of ones. Use qr to factorize the matrix into the factors R and C = Q'*b.

S = sprand(500,20,0.1); b = ones(500,1); [C,R] = qr(S,b,"econ");

Use the results to solve Sx=b with x = R\C.

Consider the identity‖b‖2=‖Sx-b‖2+‖C‖2.

Dividing through by the norm of b, you get a new identity that shows how much of b lies in the column space of S:

‖Sx-b‖2‖b‖2+‖C‖2‖b‖2=1.

The first term tells how much of b does not lie in the column space of S, while the second term tells how much of b does lie in the column space of S.

t1 = norm(S*x-b)^2/norm(b)^2

Use qr to solve the matrix equation Sx=B with a rectangular sparse coefficient matrix S.

Load the west0479 sparse matrix and use the first 200 columns as the rectangular coefficient matrix in a linear system. For the right-hand side of the equation, use the row sums of S. With this setup, the solution to Sx=B is a vector of ones.

load west0479 S = west0479(:,1:200); B = sum(S,2);

Solve Sx=B using qr with two inputs and three outputs. The solution to the linear system is x = P*(R\C).

[C,R,P] = qr(S,B); x = P*(R\C);

Verify that Sx-B=0, within machine precision.

Note: To calculate the upper-triangular factor R and permutation matrix P, but avoid computing the orthogonal matrix Q (which is often the most computationally expensive part of a call to qr), you can specify B as an empty matrix:

emptyB = zeros(size(S,1),0); [~,R,P] = qr(S,emptyB);

Input Arguments

collapse all

Input matrix, specified as a full or sparse matrix.

Data Types: single | double
Complex Number Support: Yes

Input coefficient matrix, specified as a sparse matrix. With two input matrices,qr computes a least-squares solution to the linear systemS*X = B.

Data Types: single | double
Complex Number Support: Yes

Right-hand side matrix, specified as a full or sparse matrix. With two input matrices, qr computes C = Q'*B, which you can use to solve the linear system S*X = B.

Data Types: single | double
Complex Number Support: Yes

Shape of permutation output, specified as "matrix" or"vector". This flag controls whether the permutation outputP is returned as a permutation matrix or permutation vector. You must specify three output arguments to qr to use this option.

If outputForm is "vector", thenP is a permutation vector that satisfies A(:,P) = Q*R.
The default value of outputForm is"matrix" such that A*P = Q*R.

Example: [Q,R,P] = qr(A,"vector")

Output Arguments

collapse all

Orthogonal factor, returned as a matrix that satisfies A = Q*R for an m-by-n matrix A.

For full decompositions, qr(A) returns Q as an m-by-m orthogonal matrix satisfying QHQ=QQH=Im.
For rectangular A with m > n, the economy-sized decomposition qr(A,"econ") computes only the firstn columns of Q and firstn rows of R. The columns ofQ form an orthonormal basis for the column space ofA.

Different machines and releases of MATLAB® can produce different columns in Q that are still numerically accurate. Corresponding rows and columns in Q andR can flip their signs, since this does not affect the value of the expression A = Q*R.

Upper-triangular factor, returned as a matrix that satisfies A = Q*R. The diagonal of R is in decreasing order whenA is full and three outputs are specified, [Q,R,P] = qr(A).

Permutation information, returned as a matrix or vector. The shape ofP depends on the value of outputForm. Also,qr selects P to satisfy different criteria depending on whether the first input matrix is full or sparse:

Full — qr selects P so thatabs(diag(R)) is decreasing.
Sparse — qr selects P to reduce fill-in in R.

Linear system factor, returned as a matrix that satisfies C = Q'*B. The least-squares solution to S*X = B is X = R\C. If the permutation output P is specified, then the solution is either X = P*(R\C) or X(P,:) = R\C, depending on the value of outputForm:

If outputForm is "vector", then the least-squares solution to S*X = B is X(P,:) = R\C.
The default value of outputForm is"matrix" such that the least-squares solution to S*X = B is X = P*(R\C).

Tips

To solve multiple linear systems involving the same coefficient matrix, use decomposition objects.
For the syntax [C,R] = qr(S,B), the value of X = R\C is a least-squares solution to S*X = B only whenS does not have low rank.

References

[1] Anderson, E., ed. LAPACK Users’ Guide. 3rd ed. Software, Environments, Tools. Philadelphia: Society for Industrial and Applied Mathematics, 1999. https://doi.org/10.1137/1.9780898719604.

[2] Davis, Timothy A. “Algorithm 915, SuiteSparseQR: Multifrontal Multithreaded Rank-Revealing Sparse QR Factorization.”ACM Transactions on Mathematical Software 38, no. 1 (November 2011): 1–22. https://doi.org/10.1145/2049662.2049670.

Extended Capabilities

expand all

Usage notes and limitations:

Code generation does not support sparse matrix inputs for this function.

Usage notes and limitations:

Code generation does not support sparse matrix inputs for this function.
Code generation might return a different QR factorization than MATLAB. You can verify the Q and R values by using the equation Q*R = A.

The qr function supports GPU array input with these usage notes and limitations:

Sparse inputs are not supported.

For more information, see Run MATLAB Functions on a GPU (Parallel Computing Toolbox).

Version History

Introduced before R2006a

expand all

You can specify the input coefficient matrix S as single precision. If S is single, the output arguments are alsosingle except those that are related to indexing, such as ordering and permutation vectors.

The syntaxes [___] = qr(A,0) and [___] = qr(S,B,0) will continue to be supported, but are no longer recommended. Use the"econ" option to perform economy-size decompositions instead.

Use the "econ" option to calculate economy-size decompositions withqr. The functionality is the same as qr(A,0) unless a third output is specified.

The syntax R = qr(A) always returns R as an upper-triangular matrix, regardless of whether A is full or sparse. Previously, for full A, the one-output syntax returned anR matrix with Householder vectors located in the lower-triangular portion of the matrix. These vectors partially defined the Q matrix.