1) Write a script that solves the linear system Ax=b for x using Matlab\'s LU co

Question

1) Write a script that solves the linear system Ax=b for x using Matlab's LU command to perform LU decomposition. Please state the order of complexity in terms of the number of multiplications required.

2)Let A and B be NXN matrices with different eigenvalues but the same eigenvectors (ie [V,D]=eig(A) and [V,Λ]=eig(B)). Derive the formula for the product of A&B to the 100th power, that us (AB)^100 using V,D,Λ.

a) Is the matrix A strictly diagonal dominant? Why?

b) If your answer to the previous question is YES, will Jacobi's method converge for any initial condition? If your answer to the previous question is NO, how can this system be modified so that Jacobi's method will converge?

4) Consider solving Ax=b by iterative method

x^(k+1)=T(^-1) S X^(k) + T^(-1) b

where T^(-1)S is the iteration matrix. Let B,C, and D be the iteration matrices corresponding to 3 different iterative methods. The eigenvalues of B (method 1) are 0.01, 0.05, & -1.01. The eigenvalues of C (method 2) are 0.1, 0.1, -0.9. The eigenvalues of D (method 3) are -0.4, -0.5, & -0.6.

a) Which method(s) converge(s) to the solution? Why?

b) Which method do you think converges fastest? Why?

Explanation / Answer

function [L,U]=ludec(A)

% Computes the LU decomposition of A using Gauss elimination

% without pivoting

% Input:

% A: square matrix

% Output:

% L: lower triangular matrix with 1 on the diagonal

% U: upper triangular matrix

[m,n]=size(A);

if(n~=m)

error('The matrix must be square')

end

% Forward Elimination with partial pivoting

for j=1:n, %Loop on the columns of A

% Test if the pivot coefficient vanishes

if(abs(A(j,j))<1e-6)

error('One of the pivot coefficient is zero - Pivoting is necessary')

end

for k=j+1:n, % Loop on the rows, elements below the diagonal

A(k,j)=A(k,j)/A(j,j); % A(k,j) now contains the factor

%of elimination

A(k,j+1:n)=A(k,j+1:n)-A(k,j)*A(j,j+1:n); % Row operation

end

end

% At the end of this loop, the elements below the diagonal in A are

% the elimination factors (elements of L that are located below the diagonal)

% U consists of the elements of A located on or above the main diagonal

U=triu(A); % Extracts U from A

L=tril(A); % Extracts L from A

for j=1:n,

L(j,j)=1; % Sets the diagonal elements of L to 1

end

Note that the previous function stores both L and U in the array A until the very end: after

elimination the subdiagonal elements of A are zeros and their value does not need to be stored.

Instead we use the storage space to store the corresponding elements of L (elimination factor ij).

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.