File:Conjugate gradient illustration.svg

From Wikimedia Commons, the free media repository

• File
• File history
• File links

Description	Conjugate gradient illustration.svg Illustration of en:Conjugate gradient method
Date	01:49, 20 June 2007 (UTC)
Source	self-made, with en:Matlab, and then tweaked in en:Inkscape
Author	Oleg Alexandrov
Permission (Reusing this image)	See below.

I, the copyright holder of this work, hereby release it into the public domain. This applies worldwide. In case this is not legally possible: I grant anyone the right to use this work for any purpose, without any conditions, unless such conditions are required by law. Afrikaans | Alemannisch | Aragonés | العربية | Asturianu | Azərbaycan | Беларуская (тарашкевіца) | Български | Català | Cebuano | Soranî / کوردی | Česky | Cymraeg | Dansk | Deutsch | Ελληνικά | English | Esperanto | Español | Eesti | Euskara | Estremeñu | فارسی | Suomi | Français | Galego | עברית | हिन्दी | Hrvatski | Magyar | Հայերեն | Bahasa Indonesia | Ido | Íslenska | Italiano | 日本語 | ქართული | ភាសាខ្មែរ | 한국어 | Ripoarisch | Kurdî / كوردی | Latina | Lietuvių | Latviešu | 文言 | Македонски | Bahasa Melayu | Plattdüütsch | Nederlands | ‪Norsk (nynorsk)‬ | ‪Norsk (bokmål)‬ | Polski | Português | Română | Русский | Slovenčina | Slovenščina | Shqip | Српски / Srpski | Svenska | ไทย | Tagalog | Türkçe | Українська | Vèneto | Tiếng Việt | Walon | 吴语 | 中文 | ‪中文(简体)‬ | ‪中文(繁體)‬ | 粵語 | +/−

[edit] Source code

% A comparision of gradient descent and conjugate gradient (guess who wins)

function main()

   % data
   A=[17, 2; 2, 7];  % the matrix 
   b=[2, 2]';        % right-hand side
   x0=[0, 0]';       % the initial guess  

   % linewidth and font size
   lw= 2; 
   fs = 25;

% colors
   red=[0.867 0.06 0.14];
   blue = [0, 129, 205]/256;
   green = [0, 200,  70]/256;
   black = [0, 0, 0];
   white = 0.99*[1, 1, 1];

   % Set up the plotting window
   figure(1); clf; set(gca, 'fontsize', fs); hold on; axis equal; axis off; 
   s = 0.16; x = A\b;
   Ax = x(1)-s; Bx = x(1)+s; Ay = x(2)-2.0*s; By =  x(2)+s;
   plot([Ax Bx Bx Ax Ax], [Ay Ay By By Ay], 'color', blue, 'linewidth', lw/2); % plot a blue box
   s=0.005; plot(Ax-s, Ay-s, '*', 'color', white); plot(Bx+0.5*s, By+0.5*s, '*', 'color', white); %markers
   Box = [Ax Bx Ay By];
   axis (Box);
   
   % plot the contours of the quadratic form associated with A and b
   plot_contours(A, b, Box, lw, blue);

% Do conjugate gradient and gradient descent.
% For the first one, start a bit shifted so that the two graphs don't overlap.
   shift = 0.0015*[1, -1];
   small_rad=0.002;
   tol = eps;
   x = conj_gradient(A, b, x0, tol, lw, red,   small_rad,  shift);
   x = grad_descent (A, b, x0, tol, lw, green, small_rad);

% text
   small = 0.015;
   text(x0(1)-2*small, x0(2)-1.6*small, 'x', 'fontsize', fs); 
   text(x0(1)-0.5*small, x0(2)-3*small, '0', 'fontsize', floor(0.7*fs)); 
   text(x(1)+small, x(2)+small, 'x', 'fontsize', fs);

% some balls for beauty
   small_rad = 0.003;
   ball(x0(1)+shift(1)/2, x0(2)+shift(2)/2, small_rad, blue)
   ball(x(1), x(2), small_rad, blue)

% save to disk as eps and svg
   saveas(gcf, 'Conjugate_gradient_illustration.eps', 'psc2');
   plot2svg('Conjugate_gradient_illustration.svg');
   
   
function x = conj_gradient(A, b, x, tol, lw, color, small_rad, shift)

   r=A*x - b;
   d=-r;

   while norm(r) > tol

      % a pretty ball for beauty, to cover imperfections when two segments are joined
      ball(x(1)+shift(1), x(2)+shift(2), small_rad, color);

      alpha = -dot(r, d)/dot(A*d, d);
      x0 = x;
      x = x + alpha*d;
      
      r=A*x - b;
      beta = dot(A*r, d)/dot(A*d, d);
      d0 = d;
      d = -r + beta*d;

      plot([x0(1), x(1)]+shift(1), [x0(2), x(2)]+shift(2), 'color', color, 'linewidth', lw)

   end

function x = grad_descent(A, b, x, tol, lw, color, small_rad)

   r=A*x - b;
   d=-r;

   while norm(r) > tol

      % a pretty ball for beauty, to cover imperfections when two segments are joined
      ball(x(1), x(2), small_rad, color);
      
      alpha = -dot(r, d)/dot(A*d, d);
      x0 = x;
      x = x + alpha*d;
      
      r=A*x - b;
      beta = 0; %beta = dot(A*r, d)/dot(A*d, d);
      d0 = d;
      d = -r + beta*d;

      plot([x0(1), x(1)], [x0(2), x(2)], 'color', color, 'linewidth', lw)

   end

   

function plot_contours (A, b, Box, lw, color);

   N=200;  % number of points (don't make it big, code will be slow)

   E = A\b; % the exact solution, around which we will draw the contours
   B = 0.12;
   [X, Y]=meshgrid(linspace(Box(1)-B, Box(2)+B, N), linspace(Box(3)-B, Box(4)+B, N));     % X and Y coordinates

% the quadratic form f= (1/2)*x'*A*X-b'*x;
   f = inline('0.5*A(1, 1)*X.*X + A(1, 2)*X.*Y+0.5*A(2, 2)*Y.*Y-b(1)*X-b(2)*Y', 'X', 'Y', 'A', 'b');
   Z = 0.5*A(1, 1)*X.*X + A(1, 2)*X.*Y+0.5*A(2, 2)*Y.*Y-b(1)*X-b(2)*Y;

   
   % prepare to draw the contours
   x0 = A\b; f0 = f(x0(1), x0(2), A, b);
   No = 25; % number of contours
   Levels = (linspace(f0, 1, No)-f0).^2+f0;

% Plot the contours with 'contour' in figure(2), and then with 'plot' in figure(1).
% This is to avoid a bug in plot2svg, it can't save output of 'contour'.
   figure(2); clf; hold on;
   for i=1:length(Levels)

      figure(2);
      [c, stuff] = contour(X, Y, Z, [Levels(i), Levels(i)]);

      [m, n]=size(c);
      if m > 1 & n > 0

	 % extract the contour from the contour matrix and plot in figure(1)
	 l=c(2, 1);
	 x=c(1,2:(l+1));  y=c(2,2:(l+1)); 
	 figure(1); plot(x, y, 'color', color, 'linewidth', lw/2);

      end
   end
   figure(1);

function ball(x, y, r, color)
   Theta=0:0.1:2*pi;
   X=r*cos(Theta)+x;
   Y=r*sin(Theta)+y;
   H=fill(X, Y, color);
   set(H, 'EdgeColor', 'none');

File history

• Edit this file using an external application (See the setup instructions for more information)

File links

Global file usage

The following other wikis use this file:

• Usage of Conjugate gradient illustration.svg on dewiki
  • CG-Verfahren
• Usage of Conjugate gradient illustration.svg on enwiki
  • Conjugate gradient method
  • User:Oleg Alexandrov/Pictures
• Usage of Conjugate gradient illustration.svg on jawiki
  • 共役勾配法
• Usage of Conjugate gradient illustration.svg on ptwiki
  • Método do gradiente conjugado