File:Conjugate gradient illustration.svg
From Justapedia, unleashing the power of collective wisdom
Jump to navigation
Jump to search
![File:Conjugate gradient illustration.svg](https://upload.wikimedia.org/wikipedia/commons/thumb/b/bf/Conjugate_gradient_illustration.svg/398px-Conjugate_gradient_illustration.svg.png)
Size of this PNG preview of this SVG file: 398 × 600 pixels. Other resolutions: 159 × 240 pixels | 318 × 480 pixels | 509 × 768 pixels | 679 × 1,024 pixels | 1,358 × 2,048 pixels | 804 × 1,212 pixels.
Original file (SVG file, nominally 804 × 1,212 pixels, file size: 2 KB)
![]() | This is a file from the Wikimedia Commons. Information from its description page there is shown below. Commons is a freely licensed media file repository. You can help. |
DescriptionConjugate gradient illustration.svg | Illustration of en:Conjugate gradient method |
Date | (UTC) |
Source | self-made, with en:Matlab, and then tweaked in en:Inkscape |
Author | Oleg Alexandrov |
Public domainPublic domainfalsefalse |
![]() |
I, the copyright holder of this work, release this work into the public domain. This applies worldwide. In some countries this may not be legally possible; if so: I grant anyone the right to use this work for any purpose, without any conditions, unless such conditions are required by law. |
Source code (MATLAB)
% 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');
Captions
Add a one-line explanation of what this file represents
Items portrayed in this file
depicts
some value
20 June 2007
image/svg+xml
b601e2dd29a34e29c82a4a382175e7b54cee3cc2
1,754 byte
1,212 pixel
804 pixel
File history
Click on a date/time to view the file as it appeared at that time.
Date/Time | Thumbnail | Dimensions | User | Comment | |
---|---|---|---|---|---|
current | 02:49, 24 March 2024 | ![]() | 804 × 1,212 (2 KB) | wikimediacommons>Д.Ильин | Optimization |
File usage
No pages on the Justapedia use this file (pages on other projects are not listed).
Metadata
This file contains additional information, probably added from the digital camera or scanner used to create or digitize it.
If the file has been modified from its original state, some details may not fully reflect the modified file.
Width | 227mm |
---|---|
Height | 342mm |
Retrieved from "https://justapedia.org/wiki/File:Conjugate_gradient_illustration.svg"