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