Math 449 - Homework  4 - Solutions

1) Exercise 7, section 3.4, p. 138.

The conditions on the cubic lead to the following linear equations for

A, B, C, D:

1) A + 0B + 0C +  0D = 0
2) A + 1B + 1C +  1D = 1
3) A + 2B + 4C +  8D = 2
4) A + 3B + 9C + 27D = 2

Equation 1 immediately gives A=0. To solve for B, C and D, write

the system in matrix form:

|1 1  1 |1|
|2 4  8 |2| is equivalent to
|3 9 27 |2|

|1 1  1 | 1|
|0 2  6 | 0| is equivalent to
|0 6 24 |-1|

|1 1 1 |  1 | 
|0 1 3 |  0 | is equivalent to
|0 1 4 |-1/6|

|1 1 1 |  1 | 
|0 1 3 |  0 | 
|0 0 1 |-1/6|

Solving by back substitution, we obtain D = -1/6, C = 1/2, B = 2/3, A = 0.


************************************************************************** 
 
2)  Exercise 12 of section 3.4, page 138.


The augmented matrix is:

|1  1  0 0 | 5|
|2 -1  5 0 |-9|
|0  3 -4 2 |19|
|0  0  2 6 | 2|

This is equivalent to 

|1  1  0 0 |  5|
|0 -3  5 0 |-19|
|0  3 -4 2 | 19|, which is equivalent to 
|0  0  2 6 |  2|

|1  1 0 0 |  5|
|0 -3 5 0 |-19|
|0  0 1 2 |  0|, which is equivalent to 
|0  0 1 3 |  1|

|1  1 0 0 |  5|
|0 -3 5 0 |-19|
|0  0 1 2 |  0|
|0  0 0 1 |  1|

Back substitution gives: x_4 = 1, x_3 = -2, x_2 = 3, and x_1 = 2.

************************************************************************** 
 
3)  Algorithms and Programs 6, section 3.4, page 140.


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

function X = multisystem(A,B)
%Input  - A is an N x N nonsingular matrix
%       - B is an N x M matrix (one column for each linear system
%Output - X is an N x M matrix containing the solutions on columns.
%This obtains the solution vectors for the systems AX=B_i, i=1, ..., M
%simultaneously. The method is Gaussian elimination
%followed by back substitution.

%Initialize X and the temporary storage matrix C
   [N N] = size(A);
   [N M] = size(B);
       X = zeros(N,M);
       C = zeros(1,N+M);
%Form the augmented matrix: Aug = [A|B]
     Aug = [A B];
     
for p=1:N-1
    %Partial pivoting for column p
    [Y,j] = max(abs(Aug(p:N,p)));
    %Interchange rows p and j
    C = Aug(p,:);
    Aug(p,:) = Aug(j+p-1,:);
    Aug(j+p-1,:) = C;
    if Aug(p,p)==0
        'A is a singular matrix. This method does not apply'
         break
    end
    %Elimination process for column p
    for k=p+1:N
        %Calculate the multiplier and do row replacement
        m = Aug(k,p)/Aug(p,p);
        Aug(k,p:N+M) = Aug(k,p:N+M)-m*Aug(p,p:N+M);
    end
end

%We now take the resulting matrix Aug and apply back substitution to it.
%First, redefine the matrix A and B from Aug
Anew=Aug(1:N,1:N);
Bnew=Aug(1:N,N+1:N+M);

%Now find X by back substitution
X(N,:) = Bnew(N,:)/Anew(N,N);
for k=N-1:-1:1
    X(k,:) = (Bnew(k,:)-Anew(k,k+1:N)*X(k+1:N,:))/Anew(k,k);
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
 
 
 
 Applying this program to the matrix 
 
 
     | 1     1     0     0|
 A = | 2    -1     5     0|
     | 0     3    -4     2|
     | 0     0     2     6|
 
 and 
 
 
     | 1     0     0     0|
 B = | 0     1     0     0|
     | 0     0     1     0|
     | 0     0     0     1|
     
gives 


    |10.3333   -4.6667   -5.0000    1.6667|
X = |-9.3333    4.6667    5.0000   -1.6667|
    |-6.0000    3.0000    3.0000   -1.0000|
    | 2.0000   -1.0000   -1.0000    0.5000|    
    
  =

  | 31/3  -14/3  -5    5/3|
  |-28/3   14/3   5   -5/3|
  |-6        3    3   -1  |
  | 2       -1   -1    1/2|    
   
 Since A*X=I, this X is the inverse of A.  
     
************************************************************************** 

4) Exercise 4 (b) of section 3.5, page 153.

To get a factorization of A rather then of a matrix obtained from A by

permutations of rows, we avoid transposing rows in the Gauss elimination 

process. Recall the process: write A = IA, then do the row reduction 

operations on the second matrix of the right-hand side, and register the

multipliers on the corresponding entry of the first matrix, beginning with

the identity matrix.

    |1 -2  7|   |1 0 0| |1 -2  7|
A = |4  2  1| = |0 1 0|.|4  2  1|
    |2  5 -2|   |0 0 1| |2  5 -2|
    
                |1 0 0| |1 -2   7|
              = |4 1 0|.|0 10 -27|
                |2 0 1| |2  9 -16|
                
                |1  0   0| |1 -2    7 |
              = |4  1   0|.|0 10  -27 |
                |2 9/10 1| |0  0 83/10|
                
Thus A = L*U, where


        |1  0   0|           |1 -2    7 |
    L = |4  1   0|  and  U = |0 10  -27 |
        |2 9/10 1|           |0  0 83/10|
        
        

************************************************************************** 

5) Exercise 2 (a, b) of section 3.6, page 165.

The matrix A = | 8 -3| is easily seen to be strictly diagonally dominant.
               |-1  4| 
Therefore, both the Jacobi and the Gauss-Seidel iterations will converge

to the unique solution of AX=B, for any B and any initial P_0.

Set B = |10| and P_0 = |0|.
        | 6|           |0|

For comparison, the exact solution is x=2, y=2.

a) Jacobi iteration:

x(k+1) = (10 + 3*y(k))/8
y(k+1) = ( 6 + x(k))/4  


p_1=|1.25|, p_2=|1.8125|, p_3=|1.9297|
    |1.50|      |1.8125|      |1.9531|

b) Gauss-Seidel iteration:

x(k+1) = (10 + 3*y(k))/8
y(k+1) = ( 6 + x(k+1))/4         

p_1=|1.2500|, p_2=|1.9297|, p_3=|1.9934|
    |1.8125|      |1.9824|      |1.9984|      

**************************************************************************