COSC2500/COSC7500—Semester 2, 2022 Exercises

Required

The grade of 1–5 awarded for these exercises is based on the required exercises. If all of the required exercises are completed correctly, a grade of 5 will be obtained.

R3.1 Sauer computer problems 2.1 (pg 79 in 2E, 83 in 1E):

a) Computer problem 1 is to assemble a naive Gaussian elimination pro- gram from the code in the preceding pages. Ideally, make this a Matlab function, not just a script. One of the reasons for doing this is to have a naive Gaussian elimination function to be able to compare the Matlab backslash operator against.  Test your Gaussian elimination program by solving the systems

.

2x − 2y − z   =   −2

4x + y − 2z   =   1

−2x + y − z   =   −3

ii.

x + 2y − z   =   2

2x − y + z   =   2

iii.

2x + y − 4z   =   − 7

x − y + z   =   −2

−x + 3y − 2z   =   6

b) Use your Gaussian elimination program to solve Hx = b where H is

the n × n Hilbert matrix, with Hij = 1/(i+ j − 1), and b is a vector of all

function hilb() to generate the Hilbert matrix.  The function hilb()

might also be a good starting point for generating similar matrices—

just type hilb to see the code.

Checklist

R3.2 From Sauer computer problems 2.3 (pg 94 in 2E, 101 in 1E):

a) For the n × n matrix Aij  = 5/(i + 2j − 1), x being a vector of all ones,

computed solution, using either your Gaussian elimination program

or Matlab’s backslash operation. Find the ininity norm of the forward error and the error magniication factor of the problem Ax = b (see next page for deinitions and details), and compare with the condition number of A. Do this for n = 6 and n = 10.

The inhnity norm of a vector is the largest absolute value of the elements. In Matlab, you can use either norm(x,Inf) or max(abs(x)) to ind the ininity norm of a vector x, ||x||∞ . The forward error is the ininity norm of the dif- ference between the actual solution x and your computed solution xc . The backward error is the error in the constant vector b; we will assume that the relative backward error in the machine epsilon e (Sauer uses a different def- inition for the backward error). The error magnihcation factor is the ratio of the relative forward error to the relative backward error, so

error magniication factor = ||x − xc||∞ /||x||∞

The error magniication factor tells us how errors in our constant vector b will affect our computed solution xc .

Checklist

Did you show the results for each case?

Did you explain what you did?

Did you compare your errors with the condition number?

If you couldn’t reach a size which gives zero correct digits, did you state the largest size you tried?

Did you discuss any dificulties or unusual results?

Did you include code where appropriate?

Did you reference the source of any code you didn’t write?

R3.3 Make a table or list comparing iterative methods for solving systems of lin-

ear equations. This should provide information such as restriction on the types of coeficient matrices, e.g., if the coeficient matrix needs to be sym- metric, square, real, etc. Also include any available information on the ex- pected speed and likelihood of convergence.

Checklist

R3.4 The time required to solve a linear system depends on the size of the matrix.

It will also depend on the method of solution, and whether or not the matrix is sparse.  Find the dependence of the time on the size of the matrix by solving linear systems of different sizes (you can use tic and toc to time each case).  Compare naive Gaussian elimination, the backslash operator and inv(), and two or more iterative methods.  Do this for both sparse and non-sparse matrices. You could use the systems from Sauer computer problems 2.5 1 & 2, and the Matlab code from the chapter. Note that it’s easy to convert a sparse matrix to a full matrix, using full(). Plot the times on a log–log graph. What do the slopes of the lines tell you? For what size full matrix do we want to use iterative methods? For what size sparse matrix do we need to store it as a sparse matrix? Do we need to use iterative methods for sparse matrices? Are these choices due to memory or execution time?

Note that different methods and different types of matrices will be able to reach different sizes before becoming too slow.  This makes it dificult to have a single loop over sizes covering all cases. It is easier to use separate loops, to different maximum sizes, for different cases.

Checklist

  Did you plot graphs of the times required to solve systems with the required methods?

Are your graphs and axes properly labelled?

Did you to as large sizes of systems as feasible?

Did you explain how you did it?

Did you compare the methods?

Did you discuss any dificulties or unusual results?

Did you include code where appropriate?

Did you reference the source of any code you didn’t write?

Additional

Attempts at these exercises can earn additional marks, but will not count towards the grade of 1–5 for the exercises.  Completing all of these exercises does not mean that 4 marks will be obtained—the marks depend on the quality of the answers. It is possible to earn all 4 marks without completing all of these additional exercises.

A3.1 Consider the carbon monoxide levels in a restaurant, which consists of a main room (with a volume of 200 m3), with two smaller rooms of volume

100 m3 .   One small room is a smoker’s section, and the other is a chil- dren’s section.  The small rooms are connected to the main room, one at each end, but not to each other. Ventilator fans move air at 200 m3/hr into the smoker’s room, 50 m3 /hr into the children’s room, 150 m3 /hr out of the children’s room, and 100 m3 /hr out of the children’s room end of the main room.  The small rooms exchange 25 m3 /hr with their ends of the main room. We can divide the main room into two parts, one at each end, with air exchanged at 50 m3 /hr.  The outside air has a carbon monoxide concentration of 2 mg/m3 . The smokers add carbon monoxide at the rate of 1000 mg/hr.  A faulty grill at the smoker’s end of the main room adds

2000 mg/hr.

a) What is the equilibrium carbon monoxide concentration in each room?

b) What would the equilibrium concentration be if the faulty grill was not producing carbon monoxide?

c) Explore the possibilities of changing the ventilation system (you might like to write your code in the irst place to make this easy to do). Would you make any recommendations about the ventilation?

(From S. C. Chapra, R. P. Canale, Numerical methods for engineers, 3rd ed, McGraw-Hill 1998, pp 323–324.)

A3.2 On Blackboard, you will ind C code (from the book by M. Pal) that imple-

ments Gaussian elimination. Compare the execution time of the C imple- mentation with the naive Gaussian elimination Matlab code from the Sauer

text, and other methods (that is, include this with the other results in R3.4. There are several things (steps along the way) that you will need to do to complete this exercise (often the case when solving computational prob- lems).

Some hints:

• You will need to make a few simple modiications to the C code. For example, it will currently only handle systems of size up to n = 10.

• The program is set up to read in the matrix and constants (right-hand vector) from the user at runtime. You probably don’t want to type in large matrices(!).  Perhaps you can create the matrices in matlab and cut-and-paste them with the mouse into your C code (declaring the variables), and then remove the code that reads from the user?

• To measure computation time for your C program, you will need to use functions provided in the library time.h (speciically clock() and time())

• Links to descriptions of the time library and examples are available on Blackboard.

A3.3 Consider a system described by

y =  anexp(− bnt).                                (3.11)

If we have a set ym of M measurements of y at times tm, we have a linear system that, if M ≥ N, can be used to ind an if the values of bn are known.

a) Generate and solve a test system of this type, with a random error to simulate measurement errors in ym .

b) How does the solution compare with the actual values of an used to generate the system? How does the accuracy depend on M/N?

c) What happens if 2 values of bn are similar?

A3.4    a) Solve the following sparse system, using Matlab’s backslash and one

or more iterative solvers (from Matlab or Sauer or elsewhere), and compare the errors (as in R3.2) and time taken.

The correct solution is xi = 1. Solve for sizes n = 100 and n = 100000 (and other sizes, if you wish).

b) Do the same for the sparse system with (1, 2, 1) replacing the (− 1, 3, 1)

[1, − 1, 1, − 1, 1, − 1, ...].

These matrices are from Sauer computer problems 2.5 (pg 121– 122 in 3E, 116 in 2E, 122 in 1E). The preceding sections is Sauer will be useful if you use the iterative solvers from Sauer.