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