|
6212
|
1 ## Copyright (C) 2006 David Bateman |
|
|
2 ## Copyright (C) 2006 Marco Caliari |
|
|
3 ## |
|
|
4 ## This program is free software; you can redistribute it and/or modify |
|
|
5 ## it under the terms of the GNU General Public License as published by |
|
|
6 ## the Free Software Foundation; either version 2 of the License, or |
|
|
7 ## (at your option) any later version. |
|
|
8 ## |
|
|
9 ## This program is distributed in the hope that it will be useful, |
|
|
10 ## but WITHOUT ANY WARRANTY; without even the implied warranty of |
|
|
11 ## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
|
|
12 ## GNU General Public License for more details. |
|
|
13 ## |
|
|
14 ## You should have received a copy of the GNU General Public License |
|
|
15 ## along with this program; if not, write to the Free Software |
|
|
16 ## Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA |
|
|
17 ## 02110-1301 USA |
|
|
18 |
|
|
19 ## -*- texinfo -*- |
|
|
20 ## @deftypefn {Function File} {[@var{n}, @var{c}] =} normest (@var{a}, @var{tol}) |
|
|
21 ## |
|
|
22 ## Estimates the 2-norm of the matrix @var{a} using a power series |
|
|
23 ## analysis. This is typically used for large matrices, where the cost |
|
|
24 ## of calculating the @code{norm{@var{a})} is prohibitive and an approximation |
|
|
25 ## to the 2-norm is acceptable. |
|
|
26 ## |
|
|
27 ## @var{tol} is the tolerance to which the 2-norm is calculated. By default |
|
|
28 ## @var{tol} is 1e-6. @var{c} returns the number of iterations needed for |
|
|
29 ## @code{normest} to converge. |
|
|
30 ## @end deftypefn |
|
|
31 |
|
|
32 function [e1, c] = normest(A, tol) |
|
|
33 if (nargin < 2) |
|
|
34 tol = 1e-6; |
|
|
35 endif |
|
|
36 if (tol < eps) |
|
|
37 tol = eps |
|
|
38 endif |
|
|
39 if (ndims(A) != 2) |
|
|
40 error("A must be a matrix"); |
|
|
41 endif |
|
|
42 maxA = max(max(abs(A))); |
|
|
43 c = 0; |
|
|
44 if (maxA == 0) |
|
|
45 e1 = 0 |
|
|
46 else |
|
|
47 [m, n] = size(A); |
|
|
48 B = A / maxA; |
|
|
49 Bt = B'; |
|
|
50 if (m > n) |
|
|
51 tmp = B; |
|
|
52 B = Bt; |
|
|
53 Bt = tmp; |
|
|
54 endif |
|
|
55 e0 = 0; |
|
|
56 x = randn(min(m,n),1); |
|
|
57 e1 = norm(x); |
|
|
58 x = x / e1; |
|
|
59 e1 = sqrt(e1); |
|
|
60 if (issparse(A)) |
|
|
61 while (abs(e1 - e0) > tol * e1) |
|
|
62 e0 = e1; |
|
|
63 x = B * (Bt * x); |
|
|
64 e1 = norm(x); |
|
|
65 x = x / e1; |
|
|
66 e1 = sqrt(e1); |
|
|
67 c = c + 1; |
|
|
68 endwhile |
|
|
69 else |
|
|
70 B = B * Bt |
|
|
71 while (abs(e1 - e0) > tol * e1) |
|
|
72 e0 = e1; |
|
|
73 x = B * x; |
|
|
74 e1 = norm(x); |
|
|
75 x = x / e1; |
|
|
76 e1 = sqrt(e1); |
|
|
77 c = c + 1; |
|
|
78 endwhile |
|
|
79 endif |
|
|
80 e1 = e1 * maxA; |
|
|
81 endif |
|
|
82 endfunction |
