Question

For this project, each part will be in its oun matlab script. You will be uploading a total 3 m files. Be sure to make your variable names descriptive, and add comments regularly to describe what your code is doing and hou your code aligns with the assignment 1 Iterative Methods: Conjugate Gradient In most software applications, row reduction is rarely used to solve a linear system Ar-b instead, an iterative algorithm like the one presented below is used. 1.1 Set up Linear System ● Create an N × N matrix M. Set A = M1 M, A will be the matrix we work with. N can be any value for this step Create a vector b with all values equal to some constant (your choice). This will be the right hand side of the linear system. Create a vector ro of all zeros. This will be our "initial guess 1.2 Implement Algorithm In the same script, implement the following algorithm: Given: A, ro.b,e 10- while oldl E do Told n end while Result: Here k ← k + 1 means that we are assigning the value k + 1 to the variable k. You can test that your script is correct by checking that Ar b. 1.3 Rewrite as Function Once, you have completed the above section, rewrite the algorithm as a function (in a separate file) so that the following command will solve the linear system Ar-bin your original script: x-ConjugateGradient (A, o, b) I will run this exact command to check that your function is correct. Remember that the file name needs to be the same as the function name. In your original script, display the error lr- Al after solving the linear system. 1.4 Bonus: Count Iterations Modify the function to count the number of iterations needed for the loop to finish and return as a second argument. The following command should work in your original script: x, iter ConjugateGradient (A, ro. b) In your original script, use a for-loop to run your script for N-2,26,27,2,2,2o. Create a vector that stores the ratio of #iterations/N for each value of N. Also create a vector that stores the error which is computed as r-Abll for each N. Display both of these vectors after all of the values have been computed. Tip: Loop through the values i-1:5, and use i to compute N 2 Linear Transformations: Computer Graphics Linear Transformations play a very important part in computer graphics due to the fact that they can be used to represent rotation, scaling, as well as translation of vectors. For this problem, we will think of points in a plane, as a vectors in R2 2.1 Summary In this part, you will create a figure, and use linear transformations (matrices) to move the figure around the screen. In the end, your figure should move up 8 steps, then turn and face left. Reference material for this part can be found in Linear Algebra, and its applications, David Lay, Section 2.7starting at the beginning of the section up to, but not including, 3D Graphics. Also, this poster presentation does a pretty good job explaining the same concepts http://web.csulb.edu/~jchang9/m247/m247-sp12 Daniel.Kris James.Walter.pdf 2.2 Create Figure in Plane Recreate the image below by creating a matrix whose first row is the x-coordinates of the vertices in clockwise order, and whose second row are the corresponding y-coordinates. Place the following function at the bottom of your script to plot the points in the matrix function plot-points(points) figure(1) fill(points(1, :), points(2, set (gca,'color". [0, o, o)); axis ([-10, 10, -10, 10]); :),'g'); end You can then use this function in your script by using the command plot-points(P) Where P is the matrix created above. (It will look a bit different than shown). 1.8 1.6 1A 1.2 08 0.4 02 1 08 06 04 02 0 02 04 06 8 2.3 Homogeneous Coordinates Convert the points stored in your matrix to homogeneous coordinates by adding a row of all ones to the bottom of your matrix of coordinates 2.4 Translation Create a matrix that represents the following transformation i.e. Translation in the y direction by one unit. You can test that you have the correct matrix by applying the transformation to each column in the matrix of homogeneous coordinates and then plotting the new points using the function from above. Use a for-loop to apply this transformation 8 times and plot the result each iteration using the function from part 1 2.5 Find Center Write a function (at the bottom of your script) that will compute the center of your figure The x-coordinate of the center is just the average of each of the x-coordinates (of the vertices) similarly the y-coordinate of the center is the average of each of the y-coordinates. You should be able to use the function in the following way [centerx, center-y] -FindCenter (P) Where P is the matrix of homogeneous coordinates. 2.6 Translate to Origin Create a matrix that represents the following transformation Tender(x, y, y cy, Where c,y are the coordinates of the center found in the previous part. You can test that you have the correct matrix by applying the transformation to each column in the matrix of homogeneous coordinates and then plotting the new points using the function from part 1 you should see the figure move to be centered at the origin. Comment out any tests, before moving on to the next section 2.7 Rotation Create a matrix (Linear Transformation) that has the effect of rotating the figure by 90 Apply the following transformation to cach of the columns in the matrix of homogeneous coordinates and then plot the new points TwnterTwy Tornter Aside: Check what happens if only Too is used. The above transformation is used so that the center is kept in the same place 2.8 Bonus Make the figure travel in a complete square

Answer 1

Matlab code for conjugate gradient method clear all close all Running the program with given parameters All A, x0, b and epsilon values A-I4 3 0;3 4 -1;0-1 41i epsi-10-8; x0-0:0:0] fprintfExample code for Conjugate gradient \n' fprintf( The A matrix is In') disp (A) fprintf( The b matrix is \n) disp(b) x-x0 r-old-b-A*x; p-r old; epsi-epsi norm (r_old); cnt-0; %loop for conjugate gradient method while norm (r_old)>epsi cnt-cnt+l; alpha-(r_old' *r_old)/(p A*p); x x+alpha p; r_new-r_old-alpha*A*p; beta-(r new(r new-r old))(r old'*r old) p-r_new+beta*p; r old-r new; fprintf( The solution matrix using manual code is \n') disp(x) Running the program with conjugate gradient function [x,iter]-conjugategradient (A, x0, b) fprintf The solution matrix using con jugategradient function is \n') disp(x) fprint f ("Error in conjugate gradient method is %e.in.,norm(x-Ab)) Running program for iteration count r-4;

fprintf nSolution using conjugate gradient method for different n for i= 1:6 n-2* (rti); %creating tridiagonal matrix A A-full (gallery('tridiag' ,n,-1,2,-1)) considering exact solution value as 1 x-ones (n,1); creating b vector of length n %initial guess :0-zeros ( n , 1 ); %finding solution using conjugategradient solution [ x1 , iter ]=conjugategradient ( A, x0, b ) ; fprint f ( '\tFor n=2"%d the iteration count is 2d.\n', (r+1),iter) tprint f ( "\tError in conjugate gradient method is %e.\n\n', norm (x1- A\b)) end 8888옹옹옹옹옹옹88%옹88888888888888888888옹%88옹%88%%888888옹옹8888888888888 Function for Conjugate Gradient method function [x,iter1-conjugategradient (A, x0,b) epsi=10^-8 ; x-x0 r old-b-A*x; p-r_old; epsi-epsi norm(r old); cnt-0 while norm (r_old)>eps:i cnt=cnt+1; alpha-(r_old' *r_old)/(p A*p); x=x+alpha*p; r_new r_old-alpha*A*p; beta-(r ne(r new-r_old)) (r old'*r old); p-r_new+beta*p; r_ old-r_new; end iter cnt; end 용음음응용음음응용음음응용음음응용음음용용음음용용음음응용음음용용음응용용음응용욤음응용욤응응용욤응응용욤응응용욤응응욤욤응응욤욤응응 용%욤욤응용음음%%욤욤%용음 End of Code 용용음응용욤욤응용욤욤응용욤

Example code for Con jugate gradient The A matrix is The b matrix is The solution matrix using manual code is 0.75 -0.333333333333333 -0.0833333333333333 The solution matrix using conjugategradient function is 0. 75 -0.333333333333333 -0. 0833333333333333 Error in conjugate gradient method is 1.118863e-16. Solution using conjugate gradient method for different rn For n 25 the iterationcount is 16. Error in conjugate gradient method is 1.849413e-14 For n=2 ^6 the iteration count is 32. Error in conjugate gradient method is 3.575453e-14 For n-2 7 the iteration count is 64 Error in conjugate gradient method is 7.489604e-14. For n=2 ^8 the iteration count is 128 Error in conjugate gradient method is 1.186086e-13. For n-29 the iteration count is 256 Error in conjugate gradient method is 3.622280e-12. For n 2 10 the iteration count is 512 Error in conjugate gradient method is 1.203831e-11. Published with MATLAB R2018a

%%Matlab code for conjugate gradient method
clear all
close all

%Running the program with given parameters
%All A, x0, b and epsilon values

A=[4 3 0;3 4 -1;0 -1 4];
b=[2;1;0];
epsi=10^-8;
x0=[0;0;0];

fprintf('Example code for Conjugate gradient \n')
fprintf('The A matrix is \n')
disp(A)

fprintf('The b matrix is \n')
disp(b)

x=x0;
r_old=b-A*x;
p=r_old;
epsi=epsi*norm(r_old);
cnt=0;

%loop for conjugate gradient method
while norm(r_old)>epsi
  
    cnt=cnt+1;
    alpha=(r_old'*r_old)/(p'*A*p);
    x=x+alpha*p;
    r_new=r_old-alpha*A*p;
    beta=(r_new'*(r_new-r_old))/(r_old'*r_old);
    p=r_new+beta*p;
    r_old=r_new;
  
end

fprintf('The solution matrix using manual code is \n')
disp(x)

%Running the program with conjugate gradient function
[x,iter]=conjugategradient(A,x0,b);

fprintf('The solution matrix using conjugategradient function is \n')
disp(x)

fprintf('Error in conjugate gradient method is %e.\n',norm(x-A\b))

%Running program for iteration count
r=4;
fprintf('\nSolution using conjugate gradient method for different n.\n')

for i=1:6
  
    n=2^(r+i);
    %creating tridiagonal matrix A
    A=full(gallery('tridiag',n,-1,2,-1));
    %considering exact solution value as 1
    x=ones(n,1);
    %creating b vector of length n
    b=A*x;
    %initial guess
    x0=zeros(n,1);
  
    %finding solution using conjugategradient solution
    [x1,iter]=conjugategradient(A,x0,b);
    fprintf('\tFor n=2^%d the iteration count is %d.\n',(r+i),iter)
    fprintf('\tError in conjugate gradient method is %e.\n\n',norm(x1-A\b))
  
end
  
  
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%Function for Conjugate Gradient method
function [x,iter]=conjugategradient(A,x0,b)
    epsi=10^-8;
    x=x0;
    r_old=b-A*x;
    p=r_old;
    epsi=epsi*norm(r_old);
    cnt=0;
    while norm(r_old)>epsi

        cnt=cnt+1;
        alpha=(r_old'*r_old)/(p'*A*p);
        x=x+alpha*p;
        r_new=r_old-alpha*A*p;
        beta=(r_new'*(r_new-r_old))/(r_old'*r_old);
        p=r_new+beta*p;
        r_old=r_new;

    end
    iter=cnt;
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

       %%%%%%%%%%%%%%% End of Code %%%%%%%%%%%%%%