tests/conjugate_gradient_method_tests.m

   1 ## Used throughout. The CGM uses the infinity norm as the stopping
   2 ## condition, so we had better also.
   3 max_iterations = 10000;
   4 tolerance = 1e-10;
   5
   6 A = [5,1,2; ...
   7      1,6,3;
   8      2,3,7];
   9
  10 b = [1;2;3];
  11
  12 x0 = [1;1;1];
  13
  14 ## Solved over the rationals.
  15 expected = [2/73; 11/73; 26/73];
  16 actual = conjugate_gradient_method(A, b, x0, tolerance, max_iterations);
  17 diff = norm(actual - expected, 'inf');
  18
  19 unit_test_equals("CGM works on an example", ...
  20                  true, ...
  21                  diff < tolerance);
  22
  23
  24 # Let's test Octave's pcg() against our method on some easy matrices.
  25
  26 for n = [ 5, 10, 25, 50, 100 ]
  27   A = random_positive_definite_matrix(n, 100);
  28
  29   # Assumed by Octave's implementation when you don't supply a
  30   # preconditioner.
  31   x0 = zeros(n, 1);
  32   b  = unifrnd(-100, 100, n, 1);
  33   g = @(x) A*x - b;
  34
  35   ## pcg() stops when the /relative/ norm falls below tolerance. To
  36   ## eliminate the relativity, we divide the tolerance by the
  37   ## quantity that pcg() will divide by.
  38   [o_x, o_flag, o_relres, o_iter] = pcg(A, b, tolerance/norm(g(x0)), ...
  39                                         max_iterations);
  40   [x, k] = conjugate_gradient_method(A, b, x0, tolerance, ...
  41                                      max_iterations);
  42
  43   diff = norm(o_x - x, 'inf');
  44   msg = sprintf("Our CGM agrees with Octave's, n=%d.", n);
  45
  46   ## There's no good way to choose the tolerance here, since each
  47   ## individual algorithm terminates based on the (2,infinity)-norm of
  48   ## the gradient. So we use two orders of magnitude.
  49   unit_test_equals(msg, true, diff <= sqrt(tolerance));
  50 end