CSC336F Assignment 2

CSC336F Assignment 2
Please write your family and given names and underline your family name on the front page of your paper.
All answers must be typed (preferably in latex), and compiled to a single pdf. All code, output and plots/spy of Q1 should be
embedded in latex/pdf. Code and output should be embedded with fixed-width fonts, e.g. Courier. Font size of all
fonts must be 12. Linespacing set to 1.1 or close. Do not use dark background anywhere.
What to submit:
(1) The single pdf file 00A2.pdf (with embedded code, output, plots, spy).
(2) Any source code you wrote (for computation, etc).
(3) Any plot file embedded in the latex/pdf.
Thus, the code and plots will be available within latex/pdf, as well as separately.
See course website for example of latex, embedding plots, code, using fixed width fonts, etc.
Some points will be given for the quality of presentation.
1. Consider an electrical circuit with n loops, and 2(n − 1) nodes, positioned as in the picture below. (The picture is an
example, for n = 4.) Note that the leftmost loop has 3 resistances and a voltage source, while the rightmost loop has
only 3 resistances (with two of them corresponding to a common intensity). Every other loop in between has 4 resistances. The nodes are denoted by (small) circles. Each resistance is equal to 1Ω, while the voltage source is 100 Volts.
The intensities (currents) at each wire are unknown. (Intensities are often denoted by i*
, but, here, we denote them by
x*
.) Kirchhoff’s current law states that the sum of intensities at each node (taking proper signs) must be zero. Kirchhoff’s voltage law states that the sum of voltages (recall: for each wire, voltage = intensity ⋅ resistance) along each loop
must be zero. Writing the equations arising from Kirchhoff’s laws for all loops and nodes, we get a linear system of
N = 3n − 2 equations with respect to the 3n − 2 unknown intensities.
V
x1
x2
x3
x4
x5
x6
x7
x8
x9
x10
x10
x10
For the example figure, the equations are:
Left loop: x1 + x2 + x3 = V
Top left node: x1 − x2 − x4 = 0
Bot left node: x2 − x3 + x6 = 0
Mid-left loop: −x2 + x4 + x5 + x6 = 0
Top mid node: x4 − x5 − x7 = 0
Bot mid node: x5 − x6 + x9 = 0
Mid-right loop: −x5 + x7 + x8 + x9 = 0
Top right node: x7 − x8 − x10 = 0
Bot right node: x8 − x9 + x10 = 0
Right loop: −x8 + 2x10 = 0
Generalizing the above for n loops, the general loop equation is of the form −xi−2 + xi + xi+1 + xi+2 = 0,
i = 4, 7, 10, ... , 3n − 3, the general top node equation is of the form xi − xi+1 − xi+3 = 0, i = 1, 4, 7, 10, ... , 3n − 5, the
general bottom node equation is of the form xi+1 − xi+2 + xi+5 = 0, i = 1, 4, 7, 10, ... , 3n − 5. Note that the leftmost and
rightmost loops, as well as the rightmost bottom node do not follow exactly the general equations. Also note that the
matrix of the system is very sparse; it has at most 4 non-zero entries per row, independently of the size of n.
(a) [23 points] Write a MATLAB script which, for n = 4, 8, 16, 32, generates the matrix and right-hand side vector of the
linear system, then solves the linear system (using backslash). For each n, the script also calculates and outputs the
maximum and minimum intensities, the sum of intensities, as well as the condition number of the matrix. After the
loop of n, the script plots the top line intensities (xi
, i = 1, 4, 7, ... , 3n − 2) versus their normalized (by the respective n)
index, in one plot (four lines plotted).
Because the matrix A is sparse, we use sparse matrix techniques to generate it and store it. E.g N=3*n-2;
A=speye(N, N); A(1, 1:3) = [1 1 1]; A(2, 1:4) = [1 -1 0 -1];
Typical loop equ: A(k, k-2:k+2) = [-1 0 1 1 1];
Typical top node equ: A(k+1, k:k+3) = [ 1 -1 0 -1];
Typical bot node equ: A(k-1, k-2:k+2) = [ 1 -1 0 0 1]; (incl. left bottom) etc.
(In the above, you have find what values k takes.)
Note that you can visualize the sparsity pattern of a sparse matrix A by spy(A).
To get (an estimate of) the condition number of a sparse matrix A, use condest.
If you have four vectors of ni
, i = 1, ... , 4, components respectively, stored as columns of a matrix t, to plot their components versus their normalized index use
CSC336 Assignment 2 C. Christara
-2-
plot([1:ni(1)]/ni(1), t(1:ni(1), 1), ’r-’, ...
[1:ni(2)]/ni(2), t(1:ni(2), 2), ’g--’, ...
[1:ni(3)]/ni(3), t(1:ni(3), 3), ’b-.’, ...
[1:ni(4)]/ni(4), t(1:ni(4), 4), ’k.’);
For the case n = 8, also calculate the LU factorization (using the lu function in matlab) of A, and plot (using spy), the
sparsity patterns of A, L and U. You must keep an ordering of the equations and unknowns as in the example, otherwise, the sparsity patterns will not be easy to study. Starting from the left and proceeding to the right, for the equations
go: loop, top node, bottom node, loop, top node, bottom node, etc; for unknowns, for each loop, go clockwise. Do not
output more than requested.
(b) [27 points] What are the lower, upper and total bandwidths of A for any n? Explain. What is the (exact) number of
nonzero entries in A in terms of n? Explain.
What can you (mathematically) say about the permutation matrix P (for any n) arising from the LU factorization with
partial pivoting? How can you computationally verify the form of P (for any n)? (You are welcome to use normest
and speye in matlab.)
What are the lower, upper and total bandwidths of L and what of U for any n? Explain. What is the (exact) number of
nonzero entries in L in terms of n, and what in U? Explain. (Count the main diagonal entries in both L and U.)
Based on the numerical results, how does the condition number of A behave approximately in terms of n?
Based on the numerical results, how do the values of the intensities of the top line behave as we go from left to right?
Do the maximum and minimum values depend on n and how? How does the sum of intensities vary with n? Make
any other comment you see as interesting.
Notes: speye(A), normest(A) and condest(A) are the sparse matrix equivalent MATLAB functions to eye(A),
norm(A) and cond(A), respectively.
For the output, you should use a nice format that tabulates the results (with a reasonable number of significant digits), one
line for each n.
For any plot, use appropriate legend, labels, etc.
2. [20 points] Consider the linear system
0. 03x1 + 58. 9x2 = 59. 2
5. 31x1 − 6. 1x2 = 47. 0
Solve the system using Gauss elimination and applying 3-decimal-digits floating-point arithmetic with rounding. The
results of each operation (addition, multiplication, division) of GE must be stored using 3-decimal-digits floating-point
representation, before proceeding to the next operation. (Thus, the elimination is carried out as
aij = fl(aij − fl( fl(
aik
akk
)akj)), assuming all past entries are already stored in 3-decimal-digits floating-point representation.) Do this three times: (a) without pivoting, (b) with partial pivoting, (c) with complete pivoting.
What is the relative error for x in the infinity norm in each of the cases? Exact solution is (10, 1)T
.
3. Let A be a square matrix, with ||A|| < 1 for some matrix norm || ⋅ ||. Show that
(a) [6 points] (II − A)
−1
exists (where II is the identity matrix of the same size as A)
(b) [12 points] ||(II − A)
−1
|| ≤
1
1 − ||A||
(c) [12 points] ||(II − A)
−1
− (II + A)|| ≤
||A||2
1 − ||A||
(Note: (c) indicates that (II − A)
−1
can be approximated by II + A, with accuracy O(||A||2
).)
CSC336 Assignment 2 C. Christara