EEEN10036
2019-20
C Programming Mini Assignment
Please read carefully - this assignment is assessed and is worth up to 10% of
the overall course unit mark. You may choose between two versions which are
worth different percentages of the available marks: a simplified version ("A1",
worth 40%, see Appendix 1) and a full version ("A2", worth 80%, see Appendix
2). A 'skeleton' program of each version is provided on Blackboard to help you
get started. In addition there are some unseen questions based on the
assignment which must be answered at the time of the assessment. These
questions are worth 20%, thus the maximum mark available for A1 is 60%, and
the maximum available for A2 is 100%. The mark schemes are at the end of
this document.
Introduction
Kirchhoff’s current and voltage laws produce a set of linear equations for the currents
and voltages in resistor circuits. When the circuits are small, they can be solved by
hand, however for larger circuits it is more convenient to use a program. The set of
linear equations which result from Kirchhoff’s current and voltage laws can be
represented mathematically in matrix – vector1
form and there are a number of
different methods for solving them. In this assignment, you’ll investigate how to
represent a circuit as a set of linear equations in matrix–vector form and solve them
using a technique known as Jacobi iteration.
Problem Description2
A 'track' circuit (Figure 1) feeds current to a relay, and consists of ten sections. It has
a 10V supply, in which the wires to/from the supply have a resistance of 5 ohms. The
resistance of the feed wires to each section is 0.03 ohms, and the resistance across
each section is 40 ohms. The relay and its feed wires have a total resistance of 10
ohms. The problem is to determine the currents i0,i1,…i10 in the circuit.
Figure 1. 'Track' circuit.
A simple guide to the matrix mathematics needed for this assignment ("A2" version) is provided in Appendix 3.
This problem has been adapted from "detecting a train on a track":
Set of Linear Equations Description
Kirchhoff’s laws can be used in several ways to solve this problem, but one that
gives a simple set of linear equations is now described. Let 𝑖0, 𝑖1, … , 𝑖9
, be the current
in the successive sections and 𝑖10 the current to the relay. The current between the
first and second sections is 𝑖0 − 𝑖1 so that the voltage drop across the sections is
40(𝑖0 − 𝑖1) volts. The first equation below uses this and the voltage drop in the feed
wires. The remaining nine equations compare the voltage drop across successive
sections with the drop in the two feed wires, and the last equation compares the
voltage drop across the last section with that in the relay.
40(𝑖0 − 𝑖1) + 5.06𝑖0 = 10
40(𝑖0 − 𝑖1) = 0.06𝑖1 + 40(𝑖1 − 𝑖2)
40(𝑖1 − 𝑖2) = 0.06𝑖2 + 40(𝑖2 − 𝑖3)⋮
40(𝑖8 − 𝑖9) = 0.06𝑖9 + 40(𝑖9 − 𝑖10)
40(𝑖9 − 𝑖10) = 10𝑖10
It is convenient to rearrange and write these 11 equations as follows:
45.06𝑖0 − 40𝑖1 = 10
40𝑖0 − 80.06𝑖1 + 40𝑖2 = 0
40𝑖1 − 80.06𝑖2 + 40𝑖3 = 0⋮
40𝑖8 − 80.06𝑖9 + 40𝑖10 = 0
40𝑖9 − 50𝑖10 = 0
The coefficients can then be represented mathematically by an 11-row x 11-column
matrix A and an 11x1 column vector v:
In the above, 𝑨 is the (11x11) matrix of resistance values and 𝒗 is the (11x1) column
vector where the first entry is 10 (the supply voltage) and the other entries are zero.
Each row of 𝑨 represents a section and will have, at most, 3 non-zero values. These
represent the interactions with the immediate neighbouring sections.
Vector v is produced by multiplying 𝑨 with a second column vector 𝒙 as follows:
where 𝒙 contains the unknown currents with entries 𝑖0, 𝑖1, … 𝑖10. The elements of v
are produced by multiplying each element of A with x as described in Appendix 3
(matrix-vector multiplication). Computationally, A can be represented by a 2-D array,
and v and x by 1-D arrays, where row and column numbers always start at 0.
Jacobi Method Description
The Jacobi method is a relatively simple iterative technique for solving a set of linear
equations represented in the matrix–vector form: 𝑨𝒙 = 𝒗.
With the Jacobi method we start with an initial estimate of the current vector 𝒙, and
then iteratively try and improve upon it. For the 𝑘
𝑡ℎ
iteration of the Jacobi method,
the estimates (vector 𝒙𝑘) are updated as
𝑥𝑖𝑘 =(𝑣𝑖 − ∑𝑎𝑖𝑗𝑥𝑗𝑘−1𝑛𝑗=1,𝑗≠𝑖 )/𝑎𝑖𝑖
where 𝑎𝑖𝑗 is the 𝑖,𝑗
𝑡ℎ element of the matrix 𝑨, 𝑣𝑖
is the 𝑖
𝑡ℎ element of the
vector 𝒗 and 𝑥𝑖𝑘
is the current (𝑘𝑡ℎ) estimate of the value of 𝑥𝑖. Generally, Jacobi's
method begins with a zero vector (𝑥0 = 0) and iterates until the estimated value of
the unknown parameter vector, 𝑥𝑘, doesn't change significantly on successive
iterations. One way to measure how much the vector changes is with the following
expression:
𝑑𝑘 = √∑ (𝑥𝑖𝑘 − 𝑥𝑖𝑘−1)2𝑛𝑖=0
which measures the "distance" between successive Jacobi estimates. With the
Jacobi iteration convergence can be slow, requiring several hundred steps. For this
assignment, convergence is achieved when the differences between steps is less
than or equal to a value defined as the "tolerance".
Several other explanations of the Jacobi method can be found online, for example:
https://en.wikipedia.org/wiki/Jacobi_method
Assignment Details
In this assignment you will write a C program which calculates the currents in the
circuit using the Jacobi method. There are two versions: A1 and A2 which are
detailed in Appendix 1 and 2, respectively.
For both A1 and A2, a 'skeleton' of the final program is provided to help you get
started. In each case you must follow the instructions in the comments to:
Construct the arrays and vectors which represent the set of linear equations.
Use the Jacobi method to determine the unknown current vector. continued..
4
Monitor the convergence of the iterative scheme. The test for convergence
must use the expression for 𝑑
𝑘 given above in the previous section 'Jacobi
Method Description'.
Print out the matrix A and the final values of the current vector, including the
number of iterations needed to converge upon the solution for a given
tolerance. Examples of the expected output are provided in the Appendices.
In version A2 the circuit data is read from a file called "input.txt" which has the
following format:
𝑣0, 𝑣1, … , … , … , … , … , … , … , 𝑣(𝑁−2)
, 𝑣(𝑁−1)
𝑎00, 𝑎01, … , … , … , … , … , … , 𝑎1(𝑁−2)
, 𝑎0(𝑁−1)
𝑎10, 𝑎11, … , … , … , … , … , … , 𝑎1(𝑁−2)
, 𝑎1(𝑁−1)
… , … , … , … , … , … , … , … , … , … , … , … , … , …
… , … , … , … , … , … , … , … , … , … , … , … , … , …
𝑎(𝑁−2)0, 𝑎(𝑁−2)1, … , 𝑎(𝑁−2)(𝑁−2)
, 𝑎(𝑁−2)(𝑁−1)
𝑎(𝑁−1)0, 𝑎(𝑁−1)1, … , 𝑎(𝑁−1)(𝑁−2)
, 𝑎(𝑁−1)(𝑁−1)
where each line is a comma-separated list of N values (with no spaces anywhere on
the line) such that the first line contains the voltage vector v data, and the remaining
lines are the matrix A coefficients. A function read_data_from_file() is provided in the
skeleton for reading the data. In the assignment N=11, however you will be asked to
show that your program works with different sized data.
Deadlines and Marking Schemes
a) The assessment will take place at the start of your 2-hour lab session in week
10 (i.e. w/c Monday 20th April 2020), and at no other time.
b) The assignment is individual and will be conducted under exam conditions.
Plagiarism or collusion will result in zero marks and the matter will be reported
for academic malpractice.
c) The assessment will consist of demonstrating your solution to an examiner.
Afterwards you will be asked to upload your solution to Blackboard and then
answer one or more previously unseen questions based on the assignment.
d) Important: you are expected to have completed the assignment before you
arrive. You must be able demonstrate your program when asked. You are not
permitted to use the lab time to work on the assignment.
e) This is a closed-book assessment, taken under examination conditions.
f) You must implement the program as described. If not, marks may be
deducted. See the marking scheme below.
g) The examination will take place during your usual lab session, which will have
tasks that you should aim to complete (there might also be an assessed quiz
to complete on the day).
h) There may be some waiting on the day due to the limited number of
examiners and your patience is appreciated.
5
Marking Schemes
"A1"
"A1" Version Mark
Does the program correctly calculate and print out the data
as expected? 2
Fully able to explain how the program works? 1
The program correctly implements and uses the
magnitudeVectorDiff function.
1
Answers previously unseen question(s). 2
Total 6
"A2"
Item Mark
Does the program correctly calculate and print out the data
as expected? 3
Fully able to explain how the program works? 1
The program correctly implements and uses the
magnitudeVectorDiff function.
1
The program correctly implements and uses the
JacobiMethod function.
2
Does the program work with an alternative data set? 1
Answers previously unseen questions. 2
Total 10
Marks will be deducted for both "A1" and "A2" versions as follows:
Item Mark
One or more compiler warnings. 1
The appearance of the program is poor, for
example is poorly structured, or is not
indented, or has very few comments.
1
The program uses one or more global
variables other than those provided in the
'skeleton'.
1
6
Appendix 1: Version "A1"
Starting with the given set of linear equations
45.06𝑖0 − 40𝑖1 = 10
40𝑖0 − 80.06𝑖1 + 40𝑖2 = 0
40𝑖1 − 80.06𝑖2 + 40𝑖3 = 0
⋮
40𝑖8 − 80.06𝑖9 + 40𝑖10 = 0
40𝑖9 − 50𝑖10 = 0
re-write them as:
Then make an initial guess of the solution: x
(0) = (x0(0),x1(0),x2(0) ,…xn(0)). Substitute
these values into the right hand side the of the rewritten equations to obtain the first
approximation:
(1)
. This accomplishes one iteration.
Similarly, the second approximation (x(2)= (x0(2),x1
(2),x2(2),…xn(2)) is computed by
substituting the first approximation’s values into the right hand side. By repeated
iterations, we form a sequence of approximations x,
k=0,1,2,..n. Two 1-D arrays can be used to store the data values of x
(k+1)and x(k).
Example
Consider a simpler example with a set of 3 equations:
4x0 + 2x1 + 3x2 = 8
3x0 - 5x1 + 2x2 = -14
- 2x0 + 3x1 + 8x2 = 27
Expressing this in a form suitable for iteration, we have:
x0 = (8 – 2x1 – 3x2) / 4
x1 = (-14 – 3x0 – 2x2) / (-5)
x2 = (27 + 2x0 – 3x1) / 8
Beginning with x0 = x1 = x2 = 0 the first iteration gives
x0 = (8 – 2x0 - 3x0) / 4 = 2.0
x1 = (-14 – 3x0 - 2x0) / (-5) = 2.8
x2 = (27 + 2x0 - 3x0) / 8 = 3.375
The second iteration gives
x0 = (8 – 2x2.8 - 3x3.375) / 4 = -1.931
x1 = (-14 – 3x2.0 - 2x3.375) / (-5) = 5.350
x2 = (27 + 2x2.0 - 3x2.8) / 8 = 2.825
etc. After around 45 iterations the values settle down to x0=-1.000, x1=3.000 and
x2=2.000 (to 3 decimal places), which can be verified by substitution.
7
Finally, for the data used in the assignment, the expected output is shown below:
Appendix 2: Version "A2"
In this version everything is expressed in matrix-vector form. Recall that a set of
linear equations can be represented in matrix–vector form as 𝐀𝐱 = 𝐯. Recall that A
is an NxN matrix and x and v are Nx1 column vectors. The approach in this method
requires that A be split into a diagonal matrix D and two triangular matrices L and U.
As an example, consider the following 3x3 matrix A, where the elements arowcol are
subscripted according to their row-column position. A is split into a diagonal matrix
D, and two further matrices L ("lower") and U ("upper"):
a00 a01 A02 a00 0 0 0 0 0 0 a01 a02
A = a10 a11 a12 = 0 a11 0 + a10 0 0 + 0 0 a12
a20 a21 a22 0 0 a22 a20 a21 0 0 0 0
i.e. A = D + L + U
Next rewrite Ax = v as (D + L + U)x = v and re-arrange to give
Dxn+1 = v − (L + U)xn
-thus new values of xn+1 are generated from values xn obtained in the previous step.
By taking the inverse D
-1
of D we can write
xn+1 = −D−1
(L + U)xn + D−1
v
where D
-1
is simply the diagonal matrix of the inverse of the diagonal elements of A.
Using as an example a 3x3 matrix, this last expression is represented as follows:
x0(n+1) = 1/a00 0 0 0 a01 a02 x0(n) 1/a00 0 0 v0
x1(n+1) = – 0 1/a11 0 . a10 0 a12 . x1(n) + 0 1/a11 0 . v1
x2(n+1) = 0 0 1/a22 a20 a21 0 x2(n) 0 0 1/a22 v2
v. This is now in a convenient form for Jacobi
iteration.
8
Example: Starting with
4 2 3 x0 8
3 -5 2 . x1 = -14
-2 3 8 x2 27
i.e. A . x = v
Splitting A into D, L and U and taking the inverse of D:
x0(n+1) = 1/4 0 0 0 2 3 x0(n) 1/4 0 0 8
x1(n+1) = – 0 -1/5 0 . 3 0 2 . x1(n) + 0 -1/5 0 . -14
x2(n+1) = 0 0 1/8 -2 3 0 x2(n) 0 0 1/8 27
xn+1 = -D
−1
(L + U) x + D
−1
v
After obtaining T and c and ~80 iterations, we find that x = -1.000
3.000
Finally, for the data used in the assignment, 2.000
the expected output is shown below:
9
Appendix 3 A simple guide to matrix maths.
The mathematical operations involving matrices are straightforward, and examples
of matrix-vector and matrix-matrix multiplication are shown below. If you prefer a
video explanation, there are plenty of examples online, for example Khan Academy.
In a matrix, data is organised into n rows by m columns (in this assignment n=m). It
is natural to represent a matrix in a program by a 2-D array, and process the data
with a pair of nested for-loops.
(i) Matrix-vector multiplication: this is accomplished by multiplying each
element of each row of a matrix A with the corresponding element in a
column vector x; this produces a new vector:
(ii) Matrix-matrix addition: elements in corresponding positions are added to
produce a new matrix. Consider the addition of two matrices A and B:
(iii) Matrix-matrix multiplication: this operation is similar to (i), if one views B
as a collection of column vectors. Consider multiplying A and B
-as shown below, this produces a new matrix: