Mercurial > hg > octave-nkf
annotate scripts/sparse/pcr.m @ 13175:8aaaef4a69aa
maint: periodic merge of stable to default
| author | John W. Eaton <jwe@octave.org> |
|---|---|
| date | Tue, 20 Sep 2011 15:38:24 -0400 |
| parents | c792872f8942 |
| children | 050bc580cb60 |
| rev | line source |
|---|---|
| 11523 | 1 ## Copyright (C) 2004-2011 Piotr Krzyzanowski |
| 5837 | 2 ## |
| 3 ## This file is part of Octave. | |
| 4 ## | |
| 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 | |
| 7016 | 7 ## the Free Software Foundation; either version 3 of the License, or (at |
| 8 ## your option) any later version. | |
| 5837 | 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. | |
| 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/>. | |
| 5837 | 18 |
| 19 ## -*- texinfo -*- | |
|
11471
994e2a93a8e2
Use uppercase 'A' to refer to matrix inputs in m-files.
Rik <octave@nomad.inbox5.com>
parents:
10793
diff
changeset
|
20 ## @deftypefn {Function File} {@var{x} =} pcr (@var{A}, @var{b}, @var{tol}, @var{maxit}, @var{m}, @var{x0}, @dots{}) |
| 5837 | 21 ## @deftypefnx {Function File} {[@var{x}, @var{flag}, @var{relres}, @var{iter}, @var{resvec}] =} pcr (@dots{}) |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
22 ## |
|
11563
3c6e8aaa9555
Grammarcheck m-files before 3.4 release.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
23 ## Solves the linear system of equations @code{@var{A} * @var{x} = @var{b}} |
|
3c6e8aaa9555
Grammarcheck m-files before 3.4 release.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
24 ## by means of the Preconditioned Conjugate Residuals iterative |
|
9051
1bf0ce0930be
Grammar check TexInfo in all .m files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
25 ## method. The input arguments are |
| 5837 | 26 ## |
| 27 ## @itemize | |
| 28 ## @item | |
|
11471
994e2a93a8e2
Use uppercase 'A' to refer to matrix inputs in m-files.
Rik <octave@nomad.inbox5.com>
parents:
10793
diff
changeset
|
29 ## @var{A} can be either a square (preferably sparse) matrix or a |
| 5837 | 30 ## function handle, inline function or string containing the name |
|
11471
994e2a93a8e2
Use uppercase 'A' to refer to matrix inputs in m-files.
Rik <octave@nomad.inbox5.com>
parents:
10793
diff
changeset
|
31 ## of a function which computes @code{@var{A} * @var{x}}. In principle |
|
994e2a93a8e2
Use uppercase 'A' to refer to matrix inputs in m-files.
Rik <octave@nomad.inbox5.com>
parents:
10793
diff
changeset
|
32 ## @var{A} should be symmetric and non-singular; if @code{pcr} |
|
994e2a93a8e2
Use uppercase 'A' to refer to matrix inputs in m-files.
Rik <octave@nomad.inbox5.com>
parents:
10793
diff
changeset
|
33 ## finds @var{A} to be numerically singular, you will get a warning |
| 5837 | 34 ## message and the @var{flag} output parameter will be set. |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
35 ## |
| 5837 | 36 ## @item |
| 37 ## @var{b} is the right hand side vector. | |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
38 ## |
| 5837 | 39 ## @item |
| 40 ## @var{tol} is the required relative tolerance for the residual error, | |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
41 ## @code{@var{b} - @var{A} * @var{x}}. The iteration stops if |
|
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
42 ## @code{norm (@var{b} - @var{A} * @var{x}) <= |
|
11563
3c6e8aaa9555
Grammarcheck m-files before 3.4 release.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
43 ## @var{tol} * norm (@var{b} - @var{A} * @var{x0})}. |
|
3c6e8aaa9555
Grammarcheck m-files before 3.4 release.
Rik <octave@nomad.inbox5.com>
parents:
11523
diff
changeset
|
44 ## If @var{tol} is empty or is omitted, the function sets |
| 5837 | 45 ## @code{@var{tol} = 1e-6} by default. |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
46 ## |
| 5837 | 47 ## @item |
| 48 ## @var{maxit} is the maximum allowable number of iterations; if | |
| 49 ## @code{[]} is supplied for @code{maxit}, or @code{pcr} has less | |
| 50 ## arguments, a default value equal to 20 is used. | |
| 51 ## | |
| 52 ## @item | |
| 5838 | 53 ## @var{m} is the (left) preconditioning matrix, so that the iteration is |
| 5837 | 54 ## (theoretically) equivalent to solving by @code{pcr} @code{@var{P} * |
|
11471
994e2a93a8e2
Use uppercase 'A' to refer to matrix inputs in m-files.
Rik <octave@nomad.inbox5.com>
parents:
10793
diff
changeset
|
55 ## @var{x} = @var{m} \ @var{b}}, with @code{@var{P} = @var{m} \ @var{A}}. |
| 5837 | 56 ## Note that a proper choice of the preconditioner may dramatically |
|
9051
1bf0ce0930be
Grammar check TexInfo in all .m files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
57 ## improve the overall performance of the method. Instead of matrix |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
58 ## @var{m}, the user may pass a function which returns the results of |
| 5838 | 59 ## applying the inverse of @var{m} to a vector (usually this is the |
|
9051
1bf0ce0930be
Grammar check TexInfo in all .m files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
60 ## preferred way of using the preconditioner). If @code{[]} is supplied |
| 5838 | 61 ## for @var{m}, or @var{m} is omitted, no preconditioning is applied. |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
62 ## |
| 5837 | 63 ## @item |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
64 ## @var{x0} is the initial guess. If @var{x0} is empty or omitted, the |
| 5837 | 65 ## function sets @var{x0} to a zero vector by default. |
| 66 ## @end itemize | |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
67 ## |
| 5837 | 68 ## The arguments which follow @var{x0} are treated as parameters, and |
|
11471
994e2a93a8e2
Use uppercase 'A' to refer to matrix inputs in m-files.
Rik <octave@nomad.inbox5.com>
parents:
10793
diff
changeset
|
69 ## passed in a proper way to any of the functions (@var{A} or @var{m}) |
|
9051
1bf0ce0930be
Grammar check TexInfo in all .m files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
70 ## which are passed to @code{pcr}. See the examples below for further |
|
1bf0ce0930be
Grammar check TexInfo in all .m files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
71 ## details. The output arguments are |
| 5837 | 72 ## |
| 73 ## @itemize | |
| 74 ## @item | |
| 75 ## @var{x} is the computed approximation to the solution of | |
|
11471
994e2a93a8e2
Use uppercase 'A' to refer to matrix inputs in m-files.
Rik <octave@nomad.inbox5.com>
parents:
10793
diff
changeset
|
76 ## @code{@var{A} * @var{x} = @var{b}}. |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
77 ## |
| 5837 | 78 ## @item |
|
9051
1bf0ce0930be
Grammar check TexInfo in all .m files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
79 ## @var{flag} reports on the convergence. @code{@var{flag} = 0} means |
| 5837 | 80 ## the solution converged and the tolerance criterion given by @var{tol} |
|
9051
1bf0ce0930be
Grammar check TexInfo in all .m files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
81 ## is satisfied. @code{@var{flag} = 1} means that the @var{maxit} limit |
|
1bf0ce0930be
Grammar check TexInfo in all .m files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
82 ## for the iteration count was reached. @code{@var{flag} = 3} reports t |
| 5837 | 83 ## @code{pcr} breakdown, see [1] for details. |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
84 ## |
| 5837 | 85 ## @item |
| 86 ## @var{relres} is the ratio of the final residual to its initial value, | |
| 87 ## measured in the Euclidean norm. | |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
88 ## |
| 5837 | 89 ## @item |
| 90 ## @var{iter} is the actual number of iterations performed. | |
| 91 ## | |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
92 ## @item |
| 5837 | 93 ## @var{resvec} describes the convergence history of the method, |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
94 ## so that @code{@var{resvec} (i)} contains the Euclidean norms of the |
| 7001 | 95 ## residual after the (@var{i}-1)-th iteration, @code{@var{i} = |
| 5838 | 96 ## 1,2, @dots{}, @var{iter}+1}. |
| 5837 | 97 ## @end itemize |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
98 ## |
| 5837 | 99 ## Let us consider a trivial problem with a diagonal matrix (we exploit the |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
100 ## sparsity of A) |
|
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
101 ## |
| 5837 | 102 ## @example |
| 103 ## @group | |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
104 ## n = 10; |
|
11471
994e2a93a8e2
Use uppercase 'A' to refer to matrix inputs in m-files.
Rik <octave@nomad.inbox5.com>
parents:
10793
diff
changeset
|
105 ## A = sparse (diag (1:n)); |
| 10549 | 106 ## b = rand (N, 1); |
| 5837 | 107 ## @end group |
| 108 ## @end example | |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
109 ## |
| 5837 | 110 ## @sc{Example 1:} Simplest use of @code{pcr} |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
111 ## |
| 5837 | 112 ## @example |
| 113 ## x = pcr(A, b) | |
| 114 ## @end example | |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
115 ## |
| 5837 | 116 ## @sc{Example 2:} @code{pcr} with a function which computes |
|
11471
994e2a93a8e2
Use uppercase 'A' to refer to matrix inputs in m-files.
Rik <octave@nomad.inbox5.com>
parents:
10793
diff
changeset
|
117 ## @code{@var{A} * @var{x}}. |
| 5837 | 118 ## |
| 119 ## @example | |
| 120 ## @group | |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
121 ## function y = apply_a (x) |
|
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
122 ## y = [1:10]'.*x; |
| 5837 | 123 ## endfunction |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
124 ## |
| 8507 | 125 ## x = pcr ("apply_a", b) |
| 5837 | 126 ## @end group |
| 127 ## @end example | |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
128 ## |
|
9051
1bf0ce0930be
Grammar check TexInfo in all .m files
Rik <rdrider0-list@yahoo.com>
parents:
8920
diff
changeset
|
129 ## @sc{Example 3:} Preconditioned iteration, with full diagnostics. The |
| 5837 | 130 ## preconditioner (quite strange, because even the original matrix |
|
11471
994e2a93a8e2
Use uppercase 'A' to refer to matrix inputs in m-files.
Rik <octave@nomad.inbox5.com>
parents:
10793
diff
changeset
|
131 ## @var{A} is trivial) is defined as a function |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
132 ## |
| 5837 | 133 ## @example |
| 134 ## @group | |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
135 ## function y = apply_m (x) |
|
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
136 ## k = floor (length(x)-2); |
|
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
137 ## y = x; |
|
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
138 ## y(1:k) = x(1:k)./[1:k]'; |
| 5837 | 139 ## endfunction |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
140 ## |
| 7031 | 141 ## [x, flag, relres, iter, resvec] = ... |
|
11471
994e2a93a8e2
Use uppercase 'A' to refer to matrix inputs in m-files.
Rik <octave@nomad.inbox5.com>
parents:
10793
diff
changeset
|
142 ## pcr (A, b, [], [], "apply_m") |
| 5837 | 143 ## semilogy([1:iter+1], resvec); |
| 144 ## @end group | |
| 145 ## @end example | |
| 146 ## | |
| 147 ## @sc{Example 4:} Finally, a preconditioner which depends on a | |
| 148 ## parameter @var{k}. | |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
149 ## |
| 5837 | 150 ## @example |
| 151 ## @group | |
| 8507 | 152 ## function y = apply_m (x, varargin) |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
153 ## k = varargin@{1@}; |
|
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
154 ## y = x; y(1:k) = x(1:k)./[1:k]'; |
| 5837 | 155 ## endfunction |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
156 ## |
| 7031 | 157 ## [x, flag, relres, iter, resvec] = ... |
|
11471
994e2a93a8e2
Use uppercase 'A' to refer to matrix inputs in m-files.
Rik <octave@nomad.inbox5.com>
parents:
10793
diff
changeset
|
158 ## pcr (A, b, [], [], "apply_m"', [], 3) |
| 5837 | 159 ## @end group |
| 160 ## @end example | |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
161 ## |
|
10791
3140cb7a05a1
Add spellchecker scripts for Octave and run spellcheck of documentation
Rik <octave@nomad.inbox5.com>
parents:
10549
diff
changeset
|
162 ## References: |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
163 ## |
|
10791
3140cb7a05a1
Add spellchecker scripts for Octave and run spellcheck of documentation
Rik <octave@nomad.inbox5.com>
parents:
10549
diff
changeset
|
164 ## [1] W. Hackbusch, @cite{Iterative Solution of Large Sparse Systems of |
|
3140cb7a05a1
Add spellchecker scripts for Octave and run spellcheck of documentation
Rik <octave@nomad.inbox5.com>
parents:
10549
diff
changeset
|
165 ## Equations}, section 9.5.4; Springer, 1994 |
| 5837 | 166 ## |
| 167 ## @seealso{sparse, pcg} | |
| 168 ## @end deftypefn | |
| 169 | |
| 5838 | 170 ## Author: Piotr Krzyzanowski <piotr.krzyzanowski@mimuw.edu.pl> |
| 5837 | 171 |
|
11471
994e2a93a8e2
Use uppercase 'A' to refer to matrix inputs in m-files.
Rik <octave@nomad.inbox5.com>
parents:
10793
diff
changeset
|
172 function [x, flag, relres, iter, resvec] = pcr (A, b, tol, maxit, m, x0, varargin) |
| 5837 | 173 |
| 174 breakdown = false; | |
| 175 | |
| 5838 | 176 if (nargin < 6 || isempty (x0)) |
| 177 x = zeros (size (b)); | |
| 5837 | 178 else |
| 179 x = x0; | |
| 180 endif | |
| 181 | |
| 182 if (nargin < 5) | |
| 8507 | 183 m = []; |
| 5837 | 184 endif |
| 185 | |
| 5838 | 186 if (nargin < 4 || isempty (maxit)) |
| 5837 | 187 maxit = 20; |
| 188 endif | |
| 189 | |
| 5838 | 190 maxit += 2; |
| 5837 | 191 |
| 5838 | 192 if (nargin < 3 || isempty (tol)) |
| 5837 | 193 tol = 1e-6; |
| 194 endif | |
| 195 | |
| 196 if (nargin < 2) | |
| 5838 | 197 print_usage (); |
| 5837 | 198 endif |
| 199 | |
| 200 ## init | |
|
11471
994e2a93a8e2
Use uppercase 'A' to refer to matrix inputs in m-files.
Rik <octave@nomad.inbox5.com>
parents:
10793
diff
changeset
|
201 if (isnumeric (A)) # is A a matrix? |
|
994e2a93a8e2
Use uppercase 'A' to refer to matrix inputs in m-files.
Rik <octave@nomad.inbox5.com>
parents:
10793
diff
changeset
|
202 r = b - A*x; |
| 10549 | 203 else # then A should be a function! |
|
11471
994e2a93a8e2
Use uppercase 'A' to refer to matrix inputs in m-files.
Rik <octave@nomad.inbox5.com>
parents:
10793
diff
changeset
|
204 r = b - feval (A, x, varargin{:}); |
| 5837 | 205 endif |
| 206 | |
| 10549 | 207 if (isnumeric (m)) # is M a matrix? |
| 208 if (isempty (m)) # if M is empty, use no precond | |
| 5837 | 209 p = r; |
| 10549 | 210 else # otherwise, apply the precond |
| 8507 | 211 p = m \ r; |
| 5837 | 212 endif |
| 10549 | 213 else # then M should be a function! |
| 8507 | 214 p = feval (m, r, varargin{:}); |
| 5837 | 215 endif |
| 216 | |
| 217 iter = 2; | |
| 218 | |
| 219 b_bot_old = 1; | |
| 5838 | 220 q_old = p_old = s_old = zeros (size (x)); |
| 5837 | 221 |
|
11471
994e2a93a8e2
Use uppercase 'A' to refer to matrix inputs in m-files.
Rik <octave@nomad.inbox5.com>
parents:
10793
diff
changeset
|
222 if (isnumeric (A)) # is A a matrix? |
|
994e2a93a8e2
Use uppercase 'A' to refer to matrix inputs in m-files.
Rik <octave@nomad.inbox5.com>
parents:
10793
diff
changeset
|
223 q = A * p; |
| 10549 | 224 else # then A should be a function! |
|
11471
994e2a93a8e2
Use uppercase 'A' to refer to matrix inputs in m-files.
Rik <octave@nomad.inbox5.com>
parents:
10793
diff
changeset
|
225 q = feval (A, p, varargin{:}); |
| 5837 | 226 endif |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
227 |
|
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
228 resvec(1) = abs (norm (r)); |
| 5837 | 229 |
| 230 ## iteration | |
| 5838 | 231 while (resvec(iter-1) > tol*resvec(1) && iter < maxit) |
| 232 | |
| 10549 | 233 if (isnumeric (m)) # is M a matrix? |
| 234 if (isempty (m)) # if M is empty, use no precond | |
| 235 s = q; | |
| 236 else # otherwise, apply the precond | |
| 237 s = m \ q; | |
| 5837 | 238 endif |
| 10549 | 239 else # then M should be a function! |
| 8507 | 240 s = feval (m, q, varargin{:}); |
| 5837 | 241 endif |
| 5838 | 242 b_top = r' * s; |
| 243 b_bot = q' * s; | |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
244 |
| 5837 | 245 if (b_bot == 0.0) |
| 246 breakdown = true; | |
| 247 break; | |
| 248 endif | |
| 5838 | 249 lambda = b_top / b_bot; |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
250 |
| 5838 | 251 x += lambda*p; |
| 252 r -= lambda*q; | |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
253 |
|
11471
994e2a93a8e2
Use uppercase 'A' to refer to matrix inputs in m-files.
Rik <octave@nomad.inbox5.com>
parents:
10793
diff
changeset
|
254 if (isnumeric(A)) # is A a matrix? |
|
994e2a93a8e2
Use uppercase 'A' to refer to matrix inputs in m-files.
Rik <octave@nomad.inbox5.com>
parents:
10793
diff
changeset
|
255 t = A*s; |
| 10549 | 256 else # then A should be a function! |
|
11471
994e2a93a8e2
Use uppercase 'A' to refer to matrix inputs in m-files.
Rik <octave@nomad.inbox5.com>
parents:
10793
diff
changeset
|
257 t = feval (A, s, varargin{:}); |
| 5837 | 258 endif |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
259 |
| 5838 | 260 alpha0 = (t'*s) / b_bot; |
| 261 alpha1 = (t'*s_old) / b_bot_old; | |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
262 |
| 5838 | 263 p_temp = p; |
| 264 q_temp = q; | |
| 265 | |
| 5837 | 266 p = s - alpha0*p - alpha1*p_old; |
| 267 q = t - alpha0*q - alpha1*q_old; | |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
268 |
| 5837 | 269 s_old = s; |
| 270 p_old = p_temp; | |
| 271 q_old = q_temp; | |
| 272 b_bot_old = b_bot; | |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
273 |
| 5838 | 274 resvec(iter) = abs (norm (r)); |
| 275 iter++; | |
| 5837 | 276 endwhile |
| 277 | |
| 278 flag = 0; | |
| 5838 | 279 relres = resvec(iter-1) ./ resvec(1); |
| 280 iter -= 2; | |
| 281 if (iter >= maxit-2) | |
| 5837 | 282 flag = 1; |
| 283 if (nargout < 2) | |
| 6498 | 284 warning ("pcr: maximum number of iterations (%d) reached\n", iter); |
| 285 warning ("the initial residual norm was reduced %g times.\n", 1.0/relres); | |
| 5837 | 286 endif |
| 5838 | 287 elseif (nargout < 2 && ! breakdown) |
| 6498 | 288 fprintf (stderr, "pcr: converged in %d iterations. \n", iter); |
| 289 fprintf (stderr, "the initial residual norm was reduced %g times.\n", | |
| 10549 | 290 1.0 / relres); |
| 5837 | 291 endif |
| 5838 | 292 |
| 5837 | 293 if (breakdown) |
| 294 flag = 3; | |
| 295 if (nargout < 2) | |
| 7001 | 296 warning ("pcr: breakdown occurred:\n"); |
| 6498 | 297 warning ("system matrix singular or preconditioner indefinite?\n"); |
| 5837 | 298 endif |
| 299 endif | |
| 300 | |
| 301 endfunction | |
| 302 | |
| 303 %!demo | |
| 304 %! | |
| 10549 | 305 %! # Simplest usage of PCR (see also 'help pcr') |
| 5837 | 306 %! |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
307 %! N = 20; |
| 10549 | 308 %! A = diag(linspace(-3.1,3,N)); b = rand(N,1); y = A\b; #y is the true solution |
| 309 %! x = pcr(A,b); | |
| 310 %! printf('The solution relative error is %g\n', norm(x-y)/norm(y)); | |
| 5837 | 311 %! |
| 10549 | 312 %! # You shouldn't be afraid if PCR issues some warning messages in this |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
313 %! # example: watch out in the second example, why it takes N iterations |
| 10549 | 314 %! # of PCR to converge to (a very accurate, by the way) solution |
| 5837 | 315 %!demo |
| 316 %! | |
| 10549 | 317 %! # Full output from PCR |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
318 %! # We use this output to plot the convergence history |
| 5837 | 319 %! |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
320 %! N = 20; |
| 10549 | 321 %! A = diag(linspace(-3.1,30,N)); b = rand(N,1); X = A\b; #X is the true solution |
| 322 %! [x, flag, relres, iter, resvec] = pcr(A,b); | |
| 323 %! printf('The solution relative error is %g\n', norm(x-X)/norm(X)); | |
| 324 %! title('Convergence history'); xlabel('Iteration'); ylabel('log(||b-Ax||/||b||)'); | |
| 325 %! semilogy([0:iter],resvec/resvec(1),'o-g;relative residual;'); | |
| 5837 | 326 %!demo |
| 327 %! | |
| 10549 | 328 %! # Full output from PCR |
| 329 %! # We use indefinite matrix based on the Hilbert matrix, with one | |
| 330 %! # strongly negative eigenvalue | |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
331 %! # Hilbert matrix is extremely ill conditioned, so is ours, |
| 10549 | 332 %! # and that's why PCR WILL have problems |
| 5837 | 333 %! |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
334 %! N = 10; |
| 10549 | 335 %! A = hilb(N); A(1,1)=-A(1,1); b = rand(N,1); X = A\b; #X is the true solution |
| 336 %! printf('Condition number of A is %g\n', cond(A)); | |
| 337 %! [x, flag, relres, iter, resvec] = pcr(A,b,[],200); | |
| 338 %! if (flag == 3) | |
| 339 %! printf('PCR breakdown. System matrix is [close to] singular\n'); | |
| 340 %! end | |
| 341 %! title('Convergence history'); xlabel('Iteration'); ylabel('log(||b-Ax||)'); | |
| 342 %! semilogy([0:iter],resvec,'o-g;absolute residual;'); | |
| 5837 | 343 %!demo |
| 344 %! | |
| 10549 | 345 %! # Full output from PCR |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
346 %! # We use an indefinite matrix based on the 1-D Laplacian matrix for A, |
| 10549 | 347 %! # and here we have cond(A) = O(N^2) |
| 348 %! # That's the reason we need some preconditioner; here we take | |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
349 %! # a very simple and not powerful Jacobi preconditioner, |
| 10549 | 350 %! # which is the diagonal of A |
| 5837 | 351 %! |
| 10549 | 352 %! # Note that we use here indefinite preconditioners! |
| 5837 | 353 %! |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
354 %! N = 100; |
| 10549 | 355 %! A = zeros(N,N); |
| 356 %! for i=1:N-1 # form 1-D Laplacian matrix | |
| 357 %! A(i:i+1,i:i+1) = [2 -1; -1 2]; | |
| 358 %! endfor | |
| 359 %! A = [A, zeros(size(A)); zeros(size(A)), -A]; | |
| 360 %! b = rand(2*N,1); X = A\b; #X is the true solution | |
| 361 %! maxit = 80; | |
| 362 %! printf('System condition number is %g\n',cond(A)); | |
| 363 %! # No preconditioner: the convergence is very slow! | |
| 5837 | 364 %! |
| 10549 | 365 %! [x, flag, relres, iter, resvec] = pcr(A,b,[],maxit); |
| 366 %! title('Convergence history'); xlabel('Iteration'); ylabel('log(||b-Ax||)'); | |
| 367 %! semilogy([0:iter],resvec,'o-g;NO preconditioning: absolute residual;'); | |
| 5837 | 368 %! |
| 10549 | 369 %! pause(1); |
| 370 %! # Test Jacobi preconditioner: it will not help much!!! | |
| 5837 | 371 %! |
| 10549 | 372 %! M = diag(diag(A)); # Jacobi preconditioner |
| 373 %! [x, flag, relres, iter, resvec] = pcr(A,b,[],maxit,M); | |
| 374 %! hold on; | |
| 375 %! semilogy([0:iter],resvec,'o-r;JACOBI preconditioner: absolute residual;'); | |
| 5837 | 376 %! |
| 10549 | 377 %! pause(1); |
| 378 %! # Test nonoverlapping block Jacobi preconditioner: this one should give | |
| 379 %! # some convergence speedup! | |
| 5837 | 380 %! |
| 10549 | 381 %! M = zeros(N,N);k=4; |
| 382 %! for i=1:k:N # get k x k diagonal blocks of A | |
| 383 %! M(i:i+k-1,i:i+k-1) = A(i:i+k-1,i:i+k-1); | |
| 384 %! endfor | |
| 385 %! M = [M, zeros(size(M)); zeros(size(M)), -M]; | |
| 386 %! [x, flag, relres, iter, resvec] = pcr(A,b,[],maxit,M); | |
| 387 %! semilogy([0:iter],resvec,'o-b;BLOCK JACOBI preconditioner: absolute residual;'); | |
| 388 %! hold off; | |
| 5837 | 389 %!test |
| 390 %! | |
| 10549 | 391 %! #solve small indefinite diagonal system |
| 5837 | 392 %! |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
393 %! N = 10; |
| 10549 | 394 %! A = diag(linspace(-10.1,10,N)); b = ones(N,1); X = A\b; #X is the true solution |
| 395 %! [x, flag] = pcr(A,b,[],N+1); | |
| 396 %! assert(norm(x-X)/norm(X)<1e-10); | |
| 397 %! assert(flag,0); | |
| 5837 | 398 %! |
| 399 %!test | |
| 400 %! | |
| 10549 | 401 %! #solve tridiagonal system, do not converge in default 20 iterations |
| 402 %! #should perform max allowable default number of iterations | |
| 5837 | 403 %! |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
404 %! N = 100; |
| 10549 | 405 %! A = zeros(N,N); |
| 406 %! for i=1:N-1 # form 1-D Laplacian matrix | |
| 407 %! A(i:i+1,i:i+1) = [2 -1; -1 2]; | |
| 408 %! endfor | |
| 409 %! b = ones(N,1); X = A\b; #X is the true solution | |
| 410 %! [x, flag, relres, iter, resvec] = pcr(A,b,1e-12); | |
| 411 %! assert(flag,1); | |
| 412 %! assert(relres>0.6); | |
| 413 %! assert(iter,20); | |
| 5837 | 414 %! |
| 415 %!test | |
| 416 %! | |
| 10549 | 417 %! #solve tridiagonal system with 'prefect' preconditioner |
| 418 %! #converges in one iteration | |
| 5837 | 419 %! |
|
11587
c792872f8942
all script files: untabify and strip trailing whitespace
John W. Eaton <jwe@octave.org>
parents:
11563
diff
changeset
|
420 %! N = 100; |
| 10549 | 421 %! A = zeros(N,N); |
| 422 %! for i=1:N-1 # form 1-D Laplacian matrix | |
| 423 %! A(i:i+1,i:i+1) = [2 -1; -1 2]; | |
| 424 %! endfor | |
| 425 %! b = ones(N,1); X = A\b; #X is the true solution | |
| 426 %! [x, flag, relres, iter] = pcr(A,b,[],[],A,b); | |
| 427 %! assert(norm(x-X)/norm(X)<1e-6); | |
| 428 %! assert(relres<1e-6); | |
| 429 %! assert(flag,0); | |
| 430 %! assert(iter,1); #should converge in one iteration | |
| 5837 | 431 %! |