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 + 2×10 = 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. 03×1 + 58. 9×2 = 59. 2

5. 31×1 − 6. 1×2 = 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

Sale!