Project 3, Numerical Analysis

Solutions project 3 sostegni 996088

Accuracy of the LU factorization

LU factorization is a method used to decompose a matrix into a lower triangular matrix L, an upper triangular matrix U, and a permutation matrix P. In this section, we will discuss the accuracy of this factorization.

  1 0 0 0 1 0 0 0 1/3 1 0 0 1/3 1 0 0   L = 21   1/2 1 1 0 1/2 1 1 0   −3/5 −3/5 1/4 9/10 11/4 9/10 1   1 1/2 1/3 1/4 1 1/2 1/3 1/4 0 1/12 4/45 1/120 1/12 4/45 1/12   U = 21   −1/180 −1/120 −1/180 −1/120 0 0 0 0   0 0 0 1/28000 0 0 1/2800   1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0   P = 21   0 1 0 0 0 1 0 0   0 0 0 1 0 0 0 1

Computing the norm (to inf) of the differences between the matrices:

• X = L 1-L 2;
• Y = U 1-U 2;
• Z = P 1-P 2;
• normX = norm(X,inf);
• normY = norm(Y,inf);
• normZ = norm(Z,inf);

−16||X|| ·= 2.220446049250313 10∞ −18||Y|| ·= 1.734723475976807 10∞||Z|| = 0∞

Comparing the value of the norms with the value of machine epsilon, we can see that ||X|| ||Y|| is equal to ε and is lower. From the mathematical point of view, since MA satisfies the hypothesis, we expect the solution to be unique and therefore, the three norms to be null. From a computational point of view, even if the norms are different from zero, the two values are below the machine precision. Therefore, we can consider the results null and the theorem for existence and uniqueness of the LU factorization with pivoting numerically satisfied. This statement is also proved by comparing the values of the three matrices in rational format, which are exactly the same for each pair.

Cost of LU factorization

∗ 0·c = 7.442278142268356 100∗ −2·= 3.782389536262116 10c

Comparison between direct and iterative methods

As we can see from the graph, as n increases, the difference in time taken by the two functions also drastically increases. For a large number of operations, the numerical implementation becomes crucial to obtain results in the shortest possible time.

• %LU factorization with pivoting
• n = zeros(40,1); %initializing variables
• tel LU user = zeros(40,1);
• for i=3:42
• n(i-2) = (i-2)ˆ2; %vector which