1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
|
<html lang="en">
<head>
<title>LU Decomposition - GNU Scientific Library -- Reference Manual</title>
<meta http-equiv="Content-Type" content="text/html">
<meta name="description" content="GNU Scientific Library -- Reference Manual">
<meta name="generator" content="makeinfo 4.8">
<link title="Top" rel="start" href="index.html#Top">
<link rel="up" href="Linear-Algebra.html" title="Linear Algebra">
<link rel="next" href="QR-Decomposition.html" title="QR Decomposition">
<link href="http://www.gnu.org/software/texinfo/" rel="generator-home" title="Texinfo Homepage">
<!--
Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007 The GSL Team.
Permission is granted to copy, distribute and/or modify this document
under the terms of the GNU Free Documentation License, Version 1.2 or
any later version published by the Free Software Foundation; with the
Invariant Sections being ``GNU General Public License'' and ``Free Software
Needs Free Documentation'', the Front-Cover text being ``A GNU Manual'',
and with the Back-Cover Text being (a) (see below). A copy of the
license is included in the section entitled ``GNU Free Documentation
License''.
(a) The Back-Cover Text is: ``You have freedom to copy and modify this
GNU Manual, like GNU software.''-->
<meta http-equiv="Content-Style-Type" content="text/css">
<style type="text/css"><!--
pre.display { font-family:inherit }
pre.format { font-family:inherit }
pre.smalldisplay { font-family:inherit; font-size:smaller }
pre.smallformat { font-family:inherit; font-size:smaller }
pre.smallexample { font-size:smaller }
pre.smalllisp { font-size:smaller }
span.sc { font-variant:small-caps }
span.roman { font-family:serif; font-weight:normal; }
span.sansserif { font-family:sans-serif; font-weight:normal; }
--></style>
</head>
<body>
<div class="node">
<p>
<a name="LU-Decomposition"></a>
Next: <a rel="next" accesskey="n" href="QR-Decomposition.html">QR Decomposition</a>,
Up: <a rel="up" accesskey="u" href="Linear-Algebra.html">Linear Algebra</a>
<hr>
</div>
<h3 class="section">13.1 LU Decomposition</h3>
<p><a name="index-LU-decomposition-1222"></a>
A general square matrix A has an LU decomposition into
upper and lower triangular matrices,
<pre class="example"> P A = L U
</pre>
<p class="noindent">where P is a permutation matrix, L is unit lower
triangular matrix and U is upper triangular matrix. For square
matrices this decomposition can be used to convert the linear system
A x = b into a pair of triangular systems (L y = P b,
U x = y), which can be solved by forward and back-substitution.
Note that the LU decomposition is valid for singular matrices.
<div class="defun">
— Function: int <b>gsl_linalg_LU_decomp</b> (<var>gsl_matrix * A, gsl_permutation * p, int * signum</var>)<var><a name="index-gsl_005flinalg_005fLU_005fdecomp-1223"></a></var><br>
— Function: int <b>gsl_linalg_complex_LU_decomp</b> (<var>gsl_matrix_complex * A, gsl_permutation * p, int * signum</var>)<var><a name="index-gsl_005flinalg_005fcomplex_005fLU_005fdecomp-1224"></a></var><br>
<blockquote><p>These functions factorize the square matrix <var>A</var> into the LU
decomposition PA = LU. On output the diagonal and upper
triangular part of the input matrix <var>A</var> contain the matrix
U. The lower triangular part of the input matrix (excluding the
diagonal) contains L. The diagonal elements of L are
unity, and are not stored.
<p>The permutation matrix P is encoded in the permutation
<var>p</var>. The j-th column of the matrix P is given by the
k-th column of the identity matrix, where k = p_j the
j-th element of the permutation vector. The sign of the
permutation is given by <var>signum</var>. It has the value (-1)^n,
where n is the number of interchanges in the permutation.
<p>The algorithm used in the decomposition is Gaussian Elimination with
partial pivoting (Golub & Van Loan, <cite>Matrix Computations</cite>,
Algorithm 3.4.1).
</p></blockquote></div>
<p><a name="index-linear-systems_002c-solution-of-1225"></a>
<div class="defun">
— Function: int <b>gsl_linalg_LU_solve</b> (<var>const gsl_matrix * LU, const gsl_permutation * p, const gsl_vector * b, gsl_vector * x</var>)<var><a name="index-gsl_005flinalg_005fLU_005fsolve-1226"></a></var><br>
— Function: int <b>gsl_linalg_complex_LU_solve</b> (<var>const gsl_matrix_complex * LU, const gsl_permutation * p, const gsl_vector_complex * b, gsl_vector_complex * x</var>)<var><a name="index-gsl_005flinalg_005fcomplex_005fLU_005fsolve-1227"></a></var><br>
<blockquote><p>These functions solve the square system A x = b using the LU
decomposition of A into (<var>LU</var>, <var>p</var>) given by
<code>gsl_linalg_LU_decomp</code> or <code>gsl_linalg_complex_LU_decomp</code>.
</p></blockquote></div>
<div class="defun">
— Function: int <b>gsl_linalg_LU_svx</b> (<var>const gsl_matrix * LU, const gsl_permutation * p, gsl_vector * x</var>)<var><a name="index-gsl_005flinalg_005fLU_005fsvx-1228"></a></var><br>
— Function: int <b>gsl_linalg_complex_LU_svx</b> (<var>const gsl_matrix_complex * LU, const gsl_permutation * p, gsl_vector_complex * x</var>)<var><a name="index-gsl_005flinalg_005fcomplex_005fLU_005fsvx-1229"></a></var><br>
<blockquote><p>These functions solve the square system A x = b in-place using the
LU decomposition of A into (<var>LU</var>,<var>p</var>). On input
<var>x</var> should contain the right-hand side b, which is replaced
by the solution on output.
</p></blockquote></div>
<p><a name="index-refinement-of-solutions-in-linear-systems-1230"></a><a name="index-iterative-refinement-of-solutions-in-linear-systems-1231"></a><a name="index-linear-systems_002c-refinement-of-solutions-1232"></a>
<div class="defun">
— Function: int <b>gsl_linalg_LU_refine</b> (<var>const gsl_matrix * A, const gsl_matrix * LU, const gsl_permutation * p, const gsl_vector * b, gsl_vector * x, gsl_vector * residual</var>)<var><a name="index-gsl_005flinalg_005fLU_005frefine-1233"></a></var><br>
— Function: int <b>gsl_linalg_complex_LU_refine</b> (<var>const gsl_matrix_complex * A, const gsl_matrix_complex * LU, const gsl_permutation * p, const gsl_vector_complex * b, gsl_vector_complex * x, gsl_vector_complex * residual</var>)<var><a name="index-gsl_005flinalg_005fcomplex_005fLU_005frefine-1234"></a></var><br>
<blockquote><p>These functions apply an iterative improvement to <var>x</var>, the solution
of A x = b, using the LU decomposition of A into
(<var>LU</var>,<var>p</var>). The initial residual r = A x - b is also
computed and stored in <var>residual</var>.
</p></blockquote></div>
<p><a name="index-inverse-of-a-matrix_002c-by-LU-decomposition-1235"></a><a name="index-matrix-inverse-1236"></a>
<div class="defun">
— Function: int <b>gsl_linalg_LU_invert</b> (<var>const gsl_matrix * LU, const gsl_permutation * p, gsl_matrix * inverse</var>)<var><a name="index-gsl_005flinalg_005fLU_005finvert-1237"></a></var><br>
— Function: int <b>gsl_linalg_complex_LU_invert</b> (<var>const gsl_matrix_complex * LU, const gsl_permutation * p, gsl_matrix_complex * inverse</var>)<var><a name="index-gsl_005flinalg_005fcomplex_005fLU_005finvert-1238"></a></var><br>
<blockquote><p>These functions compute the inverse of a matrix A from its
LU decomposition (<var>LU</var>,<var>p</var>), storing the result in the
matrix <var>inverse</var>. The inverse is computed by solving the system
A x = b for each column of the identity matrix. It is preferable
to avoid direct use of the inverse whenever possible, as the linear
solver functions can obtain the same result more efficiently and
reliably (consult any introductory textbook on numerical linear algebra
for details).
</p></blockquote></div>
<p><a name="index-determinant-of-a-matrix_002c-by-LU-decomposition-1239"></a><a name="index-matrix-determinant-1240"></a>
<div class="defun">
— Function: double <b>gsl_linalg_LU_det</b> (<var>gsl_matrix * LU, int signum</var>)<var><a name="index-gsl_005flinalg_005fLU_005fdet-1241"></a></var><br>
— Function: gsl_complex <b>gsl_linalg_complex_LU_det</b> (<var>gsl_matrix_complex * LU, int signum</var>)<var><a name="index-gsl_005flinalg_005fcomplex_005fLU_005fdet-1242"></a></var><br>
<blockquote><p>These functions compute the determinant of a matrix A from its
LU decomposition, <var>LU</var>. The determinant is computed as the
product of the diagonal elements of U and the sign of the row
permutation <var>signum</var>.
</p></blockquote></div>
<p><a name="index-logarithm-of-the-determinant-of-a-matrix-1243"></a>
<div class="defun">
— Function: double <b>gsl_linalg_LU_lndet</b> (<var>gsl_matrix * LU</var>)<var><a name="index-gsl_005flinalg_005fLU_005flndet-1244"></a></var><br>
— Function: double <b>gsl_linalg_complex_LU_lndet</b> (<var>gsl_matrix_complex * LU</var>)<var><a name="index-gsl_005flinalg_005fcomplex_005fLU_005flndet-1245"></a></var><br>
<blockquote><p>These functions compute the logarithm of the absolute value of the
determinant of a matrix A, \ln|\det(A)|, from its LU
decomposition, <var>LU</var>. This function may be useful if the direct
computation of the determinant would overflow or underflow.
</p></blockquote></div>
<p><a name="index-sign-of-the-determinant-of-a-matrix-1246"></a>
<div class="defun">
— Function: int <b>gsl_linalg_LU_sgndet</b> (<var>gsl_matrix * LU, int signum</var>)<var><a name="index-gsl_005flinalg_005fLU_005fsgndet-1247"></a></var><br>
— Function: gsl_complex <b>gsl_linalg_complex_LU_sgndet</b> (<var>gsl_matrix_complex * LU, int signum</var>)<var><a name="index-gsl_005flinalg_005fcomplex_005fLU_005fsgndet-1248"></a></var><br>
<blockquote><p>These functions compute the sign or phase factor of the determinant of a
matrix A, \det(A)/|\det(A)|, from its LU decomposition,
<var>LU</var>.
</p></blockquote></div>
<hr>The GNU Scientific Library - a free numerical library licensed under the GNU GPL<br>Back to the <a href="/software/gsl/">GNU Scientific Library Homepage</a></body></html>
|
