首页 >
> 详细

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:

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-23:00
- 微信：codinghelp2

- Tsp课程作业代写、代做algorithms留学生作业、代做java，C/C 2020-06-23
- Kit107留学生作业代做、C++编程语言作业调试、Data课程作业代写、代 2020-06-23
- Sta302h1f作业代做、代写r课程设计作业、代写r编程语言作业、代做da 2020-06-22
- 代写seng 474作业、代做data Mining作业、Python，Ja 2020-06-22
- Cmpsci 187 Binary Search Trees 2020-06-21
- Comp226 Assignment 2: Strategy 2020-06-21
- Math 504 Homework 12 2020-06-21
- Math4007 Assessed Coursework 2 2020-06-21
- Optimization In Machine Learning Assig... 2020-06-21
- Homework 1 – Math 104B 2020-06-20
- Comp1000 Unix And C Programming 2020-06-20
- General Specifications Use Python In T... 2020-06-20
- Comp-206 Mini Assignment 6 2020-06-20
- Aps 105 Lab 9: Search And Link 2020-06-20
- Aps 105 Lab 9: Search And Link 2020-06-20
- Mech 203 – End-Of-Semester Project 2020-06-20
- Ms980 Business Analytics 2020-06-20
- Cs952 Database And Web Systems Develop... 2020-06-20
- Homework 4 Using Data From The China H... 2020-06-20
- Assignment 1 Build A Shopping Cart 2020-06-20