# Convergence of Iterations

VerifiedAdded on 2019/09/13

|8

|4115

|281

Report

AI Summary

The provided content appears to be a series of numerical values, likely representing the results of an iterative process. The numbers are grouped into 50 sets (It=1 to It=50) with each set having four values (x[0], x[1], x[2], and x[3]). The purpose of this data is unclear, but it may be related to a mathematical or computational problem.

## Contribute Materials

Your contribution can guide someone’s learning journey. Share your
documents today.

U08079 Coursework 2017

Optimizing a solution to a modelling problem

For the coursework you are required to design, implement and optimise a

program to solve resistor networks.

A basic example Jacobi program is provided but this program is inefficient and

you are required to improve it. You should make use of a range of code

optimisation techniques and verify their effectiveness using benchmarking.

You may need to create and solve some reasonably large resistor networks to

demonstrate the effectiveness of some of the optimisations.

In addition to optimising the program on a single PC, you are also required to

implement a version of your program on the department HAC cluster using

message passing with MPI in order to investigate possible speedup and other

optimisations by employing multiple processes running on multiple

processors.

The Problem

A resistor is an electronic component that reduces the current and voltage of

an electrical signal. The diagram below shows a number of resistors forming

an electronic circuit. The green boxes represent resistors and the lines

represent wires (or nodes) connecting them together. Each resistor has a

value, in ohms, showing how powerful a resistor it is. More ohms means a

more powerful resistor, which resists more, and thus lowers voltage further.

The problem is to calculate the voltages at nodes v2 and v3. Note the left

node is connected to a fixed 6 volt supply and the right node is connected to

fixed 0 volts. There are two relevant electrical laws we can use to solve this

problem:

Kirchhoff’s Law: the net current at a node is zero, so current in must equal

current out at each circuit node. (Note that current is not the same as voltage.)

Ohm’s Law: If a resistor has a resistance of R ohms, and the voltage across

the resistor (i.e. the difference between the input and output voltages) is V

volts, then the current flowing through the resistor is I=V/R amps.

You can also utilise the fact that current flows from points of high voltage to

points of low voltage.

C Cox 21.2.2017

1 6

3

36v V2 V3 0v

Optimizing a solution to a modelling problem

For the coursework you are required to design, implement and optimise a

program to solve resistor networks.

A basic example Jacobi program is provided but this program is inefficient and

you are required to improve it. You should make use of a range of code

optimisation techniques and verify their effectiveness using benchmarking.

You may need to create and solve some reasonably large resistor networks to

demonstrate the effectiveness of some of the optimisations.

In addition to optimising the program on a single PC, you are also required to

implement a version of your program on the department HAC cluster using

message passing with MPI in order to investigate possible speedup and other

optimisations by employing multiple processes running on multiple

processors.

The Problem

A resistor is an electronic component that reduces the current and voltage of

an electrical signal. The diagram below shows a number of resistors forming

an electronic circuit. The green boxes represent resistors and the lines

represent wires (or nodes) connecting them together. Each resistor has a

value, in ohms, showing how powerful a resistor it is. More ohms means a

more powerful resistor, which resists more, and thus lowers voltage further.

The problem is to calculate the voltages at nodes v2 and v3. Note the left

node is connected to a fixed 6 volt supply and the right node is connected to

fixed 0 volts. There are two relevant electrical laws we can use to solve this

problem:

Kirchhoff’s Law: the net current at a node is zero, so current in must equal

current out at each circuit node. (Note that current is not the same as voltage.)

Ohm’s Law: If a resistor has a resistance of R ohms, and the voltage across

the resistor (i.e. the difference between the input and output voltages) is V

volts, then the current flowing through the resistor is I=V/R amps.

You can also utilise the fact that current flows from points of high voltage to

points of low voltage.

C Cox 21.2.2017

1 6

3

36v V2 V3 0v

## Secure Best Marks with AI Grader

Need help grading? Try our AI Grader for instant feedback on your assignments.

Using these laws, we can derive a system of equations which we can then

solve to give the voltages v2 and v3.

Hand calculation for the above example:

Node v2 has an input from the 1 ohm resistor.

By Ohm’s law the current in from this resistor is (6-v2)/1 (6 is the input

voltage, v2 is the node voltage which we want to find, and 1 is the ohm rating

of the resistor.)

Node V2 outputs to the 6 ohm and the 3 ohm resistor.

By Ohm’s law the current out to the 6 ohm resistor is (v2-v3)/6,

and the current out to the 3 ohm resistor is (v2-v3)/3.

By Kirchhoff’s law the current at the inputs and outputs of V2 must be the

same, so (6-v2)/1 = (v2-v3)/6 + (v2-v3)/3

At node v3 we consider the inputs and outputs similarly:

The two input resistors will have currents of (v2-v3)/6 and (v2-v3)/3

and the output resistor will have a current of (v3-0)/3.

So (v2-v3)/6 + (v2-v3)/3 = (v3-0)/3.

Now we have two equations to solve simultaneously:

(6-v2)/1 = (v2-v3)/6 + (v2-v3)/3

(v2-v3)/6 + (v2-v3)/3 = (v3-0)/3.

Simplifying the first equation:

Start with (6-v2)/1 = (v2-v3)/6 + (v2-v3)/3

Dividing by one does nothing (6-v2) = (v2-v3)/6 + (v2-v3)/3

Multiply all by 6 to remove /6 6(6-v2) = (v2-v3) + 2(v2-v3)

Carry out multiplications 36 – 6v2 = v2-v3 + 2v2 – 2v3

Collect terms 36 – 6v2 = 3v2 – 3v3

Add 6v2 to both sides, to move it 36 = 9v2 – 3v3

Divide through by 3 to lower numbers 12 = 3v2 – v3

Same with the second equation:

Start with (v2-v3)/6 + (v2-v3)/3 = (v3-0)/3

Subtracting 0 does nothing (v2-v3)/6 + (v2-v3)/3 = v3/3

Multiply all by 6 to remove /6 (v2-v3) + 2(v2-v3) = 2v3

Carry out multiplications v2-v3 + 2v2 – 2v3 = 2v3

Collect terms 3v2 – 3v3 = 2v3

Subtract 2v3 from both sides 3v2 – 5v3 = 0

We now have two equations of the form:

3v2 – 1v3 = 12

3v2 – 5v3 = 0

Which we can easily solve as a simultaneous equation as v2=5 and v3=3

Notice that for a general resister network:

We will end up with one equation per node;

Each of these equations will have one v term for each node voltage.

C Cox 21.2.2017

solve to give the voltages v2 and v3.

Hand calculation for the above example:

Node v2 has an input from the 1 ohm resistor.

By Ohm’s law the current in from this resistor is (6-v2)/1 (6 is the input

voltage, v2 is the node voltage which we want to find, and 1 is the ohm rating

of the resistor.)

Node V2 outputs to the 6 ohm and the 3 ohm resistor.

By Ohm’s law the current out to the 6 ohm resistor is (v2-v3)/6,

and the current out to the 3 ohm resistor is (v2-v3)/3.

By Kirchhoff’s law the current at the inputs and outputs of V2 must be the

same, so (6-v2)/1 = (v2-v3)/6 + (v2-v3)/3

At node v3 we consider the inputs and outputs similarly:

The two input resistors will have currents of (v2-v3)/6 and (v2-v3)/3

and the output resistor will have a current of (v3-0)/3.

So (v2-v3)/6 + (v2-v3)/3 = (v3-0)/3.

Now we have two equations to solve simultaneously:

(6-v2)/1 = (v2-v3)/6 + (v2-v3)/3

(v2-v3)/6 + (v2-v3)/3 = (v3-0)/3.

Simplifying the first equation:

Start with (6-v2)/1 = (v2-v3)/6 + (v2-v3)/3

Dividing by one does nothing (6-v2) = (v2-v3)/6 + (v2-v3)/3

Multiply all by 6 to remove /6 6(6-v2) = (v2-v3) + 2(v2-v3)

Carry out multiplications 36 – 6v2 = v2-v3 + 2v2 – 2v3

Collect terms 36 – 6v2 = 3v2 – 3v3

Add 6v2 to both sides, to move it 36 = 9v2 – 3v3

Divide through by 3 to lower numbers 12 = 3v2 – v3

Same with the second equation:

Start with (v2-v3)/6 + (v2-v3)/3 = (v3-0)/3

Subtracting 0 does nothing (v2-v3)/6 + (v2-v3)/3 = v3/3

Multiply all by 6 to remove /6 (v2-v3) + 2(v2-v3) = 2v3

Carry out multiplications v2-v3 + 2v2 – 2v3 = 2v3

Collect terms 3v2 – 3v3 = 2v3

Subtract 2v3 from both sides 3v2 – 5v3 = 0

We now have two equations of the form:

3v2 – 1v3 = 12

3v2 – 5v3 = 0

Which we can easily solve as a simultaneous equation as v2=5 and v3=3

Notice that for a general resister network:

We will end up with one equation per node;

Each of these equations will have one v term for each node voltage.

C Cox 21.2.2017

So if we had 4 nodes, we would obtain four equations, each of the form

?v2 + ?v3 + ?v4 + ?v5 = ?.

This would be much more difficult to solve manually, hence the need for the

Jacobi algorithm.

Thus the complexity of solving the equations increases with each extra node

in the system, which is why this problem requires optimization.

The Jacobi algorithm can be used to solve sets of equations of this type. To

use it we first represent the equations as a matrix multiplication, actually to

multiply an nxn matrix by a vector of size n. In our example n=2:

Note that the elements of the matrix correspond to the coefficients in the

equations.

3v2 – 1v3 = 12

3v2 – 5v3 = 0

The Jacobi algorithm is based on guessing an initial solution (all nodes set to

1 volt in the example program) and then refining it over a number of iterations.

Here is the C source code for a simple implementation. Note the coefficients

from the above equations as values of matrix m and vector b:

Note we use a 2-D n x n array for the matrix m and a 1-D array size n for the

vector b.

#include <stdio.h>

// Number of nodes

#define n 2

int main()

{ // Matrix of coefficients

const double m[n][n]={{3.0,-1.0}, {3.0,-5.0}};

// Vector of results

const double b[n]={12.0,0.0};

// Arrays used for storing guesses

double x[n], new_x[n];

double sum;

// How many iterations to do – the more the better the answer

const int MaxIts=30;

int Its,i,j;

// Start with all guesses at 1

for(i=0;i<n;i++) x[i]=1.0;

// Perform MaxIts iterations

for(Its=1;Its<=MaxIts;Its++)

{ // Print out the iteration we are on

printf("Its=%d",Its);

// This is the actual Jacobi algorithm

// Calculate our next round of guesses in max_i[]

for(i=0; i<n; i++)

{ sum=0.0;

for(j=0;j<n;j++)

C Cox 21.2.2017

?v2 + ?v3 + ?v4 + ?v5 = ?.

This would be much more difficult to solve manually, hence the need for the

Jacobi algorithm.

Thus the complexity of solving the equations increases with each extra node

in the system, which is why this problem requires optimization.

The Jacobi algorithm can be used to solve sets of equations of this type. To

use it we first represent the equations as a matrix multiplication, actually to

multiply an nxn matrix by a vector of size n. In our example n=2:

Note that the elements of the matrix correspond to the coefficients in the

equations.

3v2 – 1v3 = 12

3v2 – 5v3 = 0

The Jacobi algorithm is based on guessing an initial solution (all nodes set to

1 volt in the example program) and then refining it over a number of iterations.

Here is the C source code for a simple implementation. Note the coefficients

from the above equations as values of matrix m and vector b:

Note we use a 2-D n x n array for the matrix m and a 1-D array size n for the

vector b.

#include <stdio.h>

// Number of nodes

#define n 2

int main()

{ // Matrix of coefficients

const double m[n][n]={{3.0,-1.0}, {3.0,-5.0}};

// Vector of results

const double b[n]={12.0,0.0};

// Arrays used for storing guesses

double x[n], new_x[n];

double sum;

// How many iterations to do – the more the better the answer

const int MaxIts=30;

int Its,i,j;

// Start with all guesses at 1

for(i=0;i<n;i++) x[i]=1.0;

// Perform MaxIts iterations

for(Its=1;Its<=MaxIts;Its++)

{ // Print out the iteration we are on

printf("Its=%d",Its);

// This is the actual Jacobi algorithm

// Calculate our next round of guesses in max_i[]

for(i=0; i<n; i++)

{ sum=0.0;

for(j=0;j<n;j++)

C Cox 21.2.2017

if(i!=j)sum+=m[i][j]*x[j];

new_x[i]=(b[i]-sum)/m[i][i];

}

// Update current guesses for the new round and print them out

for(i=0;i<n;i++)

{ x[i]=new_x[i];

printf(" x[%d]=%12.8f",i,x[i]);

}

printf("\n");

}

return 0;

}

Here is an example of this program running on the problem above:

Its=1 x[0]= 4.33333333 x[1]= 0.60000000

Its=2 x[0]= 4.20000000 x[1]= 2.60000000

Its=3 x[0]= 4.86666667 x[1]= 2.52000000

Its=4 x[0]= 4.84000000 x[1]= 2.92000000

Its=5 x[0]= 4.97333333 x[1]= 2.90400000

Its=6 x[0]= 4.96800000 x[1]= 2.98400000

Its=7 x[0]= 4.99466667 x[1]= 2.98080000

Its=8 x[0]= 4.99360000 x[1]= 2.99680000

Its=9 x[0]= 4.99893333 x[1]= 2.99616000

Its=10 x[0]= 4.99872000 x[1]= 2.99936000

Its=11 x[0]= 4.99978667 x[1]= 2.99923200

Its=12 x[0]= 4.99974400 x[1]= 2.99987200

Its=13 x[0]= 4.99995733 x[1]= 2.99984640

Its=14 x[0]= 4.99994880 x[1]= 2.99997440

Its=15 x[0]= 4.99999147 x[1]= 2.99996928

Its=16 x[0]= 4.99998976 x[1]= 2.99999488

Its=17 x[0]= 4.99999829 x[1]= 2.99999386

Its=18 x[0]= 4.99999795 x[1]= 2.99999898

Its=19 x[0]= 4.99999966 x[1]= 2.99999877

Its=20 x[0]= 4.99999959 x[1]= 2.99999980

Its=21 x[0]= 4.99999993 x[1]= 2.99999975

Its=22 x[0]= 4.99999992 x[1]= 2.99999996

Its=23 x[0]= 4.99999999 x[1]= 2.99999995

Its=24 x[0]= 4.99999998 x[1]= 2.99999999

Its=25 x[0]= 5.00000000 x[1]= 2.99999999

Its=26 x[0]= 5.00000000 x[1]= 3.00000000

Its=27 x[0]= 5.00000000 x[1]= 3.00000000

Its=28 x[0]= 5.00000000 x[1]= 3.00000000

Its=29 x[0]= 5.00000000 x[1]= 3.00000000

Its=30 x[0]= 5.00000000 x[1]= 3.00000000

Note that a reasonably accurate solution is obtained here within 30 iterations.

This basic program simply limits the number of iterations, but it would be

preferable to loop until a specified convergence accuracy level is achieved.

You should also be aware of the limited precision of floating point or double

precision values stored on a computer.

Coursework Specification

Your program should solve resistor networks using the Jacobi algorithm. It

must be written in C++ and should demonstrate good software development

and programming practice. It should also be optimised as far as possible to

give fast but reliable performance.

C Cox 21.2.2017

new_x[i]=(b[i]-sum)/m[i][i];

}

// Update current guesses for the new round and print them out

for(i=0;i<n;i++)

{ x[i]=new_x[i];

printf(" x[%d]=%12.8f",i,x[i]);

}

printf("\n");

}

return 0;

}

Here is an example of this program running on the problem above:

Its=1 x[0]= 4.33333333 x[1]= 0.60000000

Its=2 x[0]= 4.20000000 x[1]= 2.60000000

Its=3 x[0]= 4.86666667 x[1]= 2.52000000

Its=4 x[0]= 4.84000000 x[1]= 2.92000000

Its=5 x[0]= 4.97333333 x[1]= 2.90400000

Its=6 x[0]= 4.96800000 x[1]= 2.98400000

Its=7 x[0]= 4.99466667 x[1]= 2.98080000

Its=8 x[0]= 4.99360000 x[1]= 2.99680000

Its=9 x[0]= 4.99893333 x[1]= 2.99616000

Its=10 x[0]= 4.99872000 x[1]= 2.99936000

Its=11 x[0]= 4.99978667 x[1]= 2.99923200

Its=12 x[0]= 4.99974400 x[1]= 2.99987200

Its=13 x[0]= 4.99995733 x[1]= 2.99984640

Its=14 x[0]= 4.99994880 x[1]= 2.99997440

Its=15 x[0]= 4.99999147 x[1]= 2.99996928

Its=16 x[0]= 4.99998976 x[1]= 2.99999488

Its=17 x[0]= 4.99999829 x[1]= 2.99999386

Its=18 x[0]= 4.99999795 x[1]= 2.99999898

Its=19 x[0]= 4.99999966 x[1]= 2.99999877

Its=20 x[0]= 4.99999959 x[1]= 2.99999980

Its=21 x[0]= 4.99999993 x[1]= 2.99999975

Its=22 x[0]= 4.99999992 x[1]= 2.99999996

Its=23 x[0]= 4.99999999 x[1]= 2.99999995

Its=24 x[0]= 4.99999998 x[1]= 2.99999999

Its=25 x[0]= 5.00000000 x[1]= 2.99999999

Its=26 x[0]= 5.00000000 x[1]= 3.00000000

Its=27 x[0]= 5.00000000 x[1]= 3.00000000

Its=28 x[0]= 5.00000000 x[1]= 3.00000000

Its=29 x[0]= 5.00000000 x[1]= 3.00000000

Its=30 x[0]= 5.00000000 x[1]= 3.00000000

Note that a reasonably accurate solution is obtained here within 30 iterations.

This basic program simply limits the number of iterations, but it would be

preferable to loop until a specified convergence accuracy level is achieved.

You should also be aware of the limited precision of floating point or double

precision values stored on a computer.

Coursework Specification

Your program should solve resistor networks using the Jacobi algorithm. It

must be written in C++ and should demonstrate good software development

and programming practice. It should also be optimised as far as possible to

give fast but reliable performance.

C Cox 21.2.2017

## Paraphrase This Document

Need a fresh take? Get an instant paraphrase of this document with our AI Paraphraser

The Jacobi algorithm can be implemented as a stand-alone program, as a

single program which creates multiple threads, or as a distributed program in

which the processing is shared between several computers as follows.

A basic implementation is suggested first. This will:

Input, or create, data for a resistor network to obtain a matrix of

coefficients and a vector of target values. It is allowed to have the data

hard-wired into your program, or input from a file, or the data could be

computed as needed.

Implement the Jacobi algorithm as a single process. You should

confirm that it returns the correct solution and you should also add a

method to detect convergence as well as confirm its effectiveness.

There is no need, or extra marks awarded, for a graphical user

interface. Therefore a command line interface is acceptable.

A locally parallel implementation should then be implemented, which uses

threading and messaging to make optimal use of multiple processor cores on

a single machine.

A distributed implementation should then be implemented using MPI on the

department HAC cluster. Initially as a single process, then as a multiprocess

implementation in which the processing of matrix rows is distributed between

several processes across several processors.

An distributed optimised version should consider optimising:

1. The Jacobi code itself

2. The number of processes and processors

3. Message passing to optimise speedup

4. Finally by devising a sparse data structure to store matrix data the

performance as well as memory requirements could be improved.

What is required?

In Week 9 you must demonstrate a basic implementation and a single

computer version using threads during the practical session. You will also be

interviewed about your code and about how it works, and how well you have

optimised it. This demonstration is worth 20% of the coursework mark. You

will be given feedback in the session. The marks will be assigned as:

successful compilation and demonstration 5 marks, software design 5 marks,

explanation of code 5 marks, and code optimisation 5 marks.

In week 11 you must demonstrate a distributed version running on the cluster

using MPI. You will also be interviewed about your code, and about how it

works, and how well you have optimised it. This demonstration is worth 20%

of the coursework mark.

You may also demonstrate your single computer version again at this time, if

you have improved it based on your feedback from week 9. If your mark is

C Cox 21.2.2017

single program which creates multiple threads, or as a distributed program in

which the processing is shared between several computers as follows.

A basic implementation is suggested first. This will:

Input, or create, data for a resistor network to obtain a matrix of

coefficients and a vector of target values. It is allowed to have the data

hard-wired into your program, or input from a file, or the data could be

computed as needed.

Implement the Jacobi algorithm as a single process. You should

confirm that it returns the correct solution and you should also add a

method to detect convergence as well as confirm its effectiveness.

There is no need, or extra marks awarded, for a graphical user

interface. Therefore a command line interface is acceptable.

A locally parallel implementation should then be implemented, which uses

threading and messaging to make optimal use of multiple processor cores on

a single machine.

A distributed implementation should then be implemented using MPI on the

department HAC cluster. Initially as a single process, then as a multiprocess

implementation in which the processing of matrix rows is distributed between

several processes across several processors.

An distributed optimised version should consider optimising:

1. The Jacobi code itself

2. The number of processes and processors

3. Message passing to optimise speedup

4. Finally by devising a sparse data structure to store matrix data the

performance as well as memory requirements could be improved.

What is required?

In Week 9 you must demonstrate a basic implementation and a single

computer version using threads during the practical session. You will also be

interviewed about your code and about how it works, and how well you have

optimised it. This demonstration is worth 20% of the coursework mark. You

will be given feedback in the session. The marks will be assigned as:

successful compilation and demonstration 5 marks, software design 5 marks,

explanation of code 5 marks, and code optimisation 5 marks.

In week 11 you must demonstrate a distributed version running on the cluster

using MPI. You will also be interviewed about your code, and about how it

works, and how well you have optimised it. This demonstration is worth 20%

of the coursework mark.

You may also demonstrate your single computer version again at this time, if

you have improved it based on your feedback from week 9. If your mark is

C Cox 21.2.2017

higher than the mark from week 9 you will be awarded the higher mark.

However you cannot be awarded more than double the mark you were given

in week 9. If you did not demonstrate the single computer version in week 9

you will be unable to gain any marks by demonstrating it in week 11.

By the end of week 11 you should submit a final report containing the

following sections:

Description of the problem and design, especially discussing how you

broke it into parts for parallelism (10%)

Description of message passing and MPI distributed program design

(10%)

Discussion of the locally parallel and distributed implementations (10%

each, total 20%)

Testing and test results including timed benchmarks for both versions

(5%)

Analysis of the optimisations implemented showing how effective they

have been based on your testing (15%)

You should submit a printed copy of your report to the lecturer or to the

U08079 postbox and an electronic copy uploaded to the Turnitin link.

Additionally all your documentation, code and data should be uploaded as a

single zip file to U08079 Moodle.

The deadline is 5pm Friday 28th April 2017.

A second worked example

Resistor network (a linear chain of 1 ohm resistors)

Equations

At v1: 5-v1 = v1-v2 so -2v1 + v2 = -5

At v2: v1-v2 = v2-v3 so v1 – 2v2 +v3 = 0

At v3: v2-v3 = v3-v4 so v2 – 2v3 + v4 = 0

At v4: v3-v4 = v4-0 so v3 – 2v4 = 0

Matrix and vector

C Cox 21.2.2017

15v V1

1 1 1 1

V2 V3 V4 0v

However you cannot be awarded more than double the mark you were given

in week 9. If you did not demonstrate the single computer version in week 9

you will be unable to gain any marks by demonstrating it in week 11.

By the end of week 11 you should submit a final report containing the

following sections:

Description of the problem and design, especially discussing how you

broke it into parts for parallelism (10%)

Description of message passing and MPI distributed program design

(10%)

Discussion of the locally parallel and distributed implementations (10%

each, total 20%)

Testing and test results including timed benchmarks for both versions

(5%)

Analysis of the optimisations implemented showing how effective they

have been based on your testing (15%)

You should submit a printed copy of your report to the lecturer or to the

U08079 postbox and an electronic copy uploaded to the Turnitin link.

Additionally all your documentation, code and data should be uploaded as a

single zip file to U08079 Moodle.

The deadline is 5pm Friday 28th April 2017.

A second worked example

Resistor network (a linear chain of 1 ohm resistors)

Equations

At v1: 5-v1 = v1-v2 so -2v1 + v2 = -5

At v2: v1-v2 = v2-v3 so v1 – 2v2 +v3 = 0

At v3: v2-v3 = v3-v4 so v2 – 2v3 + v4 = 0

At v4: v3-v4 = v4-0 so v3 – 2v4 = 0

Matrix and vector

C Cox 21.2.2017

15v V1

1 1 1 1

V2 V3 V4 0v

Notice the regular structure of this matrix. This may provide a clue to

automatically generating matrix data for large networks.

Unoptimized program

(This is the same as the previous program with different data loaded)

#include <stdio.h>

#define n 4

int main()

{ const double m[n][n]={{-2.0,1.0,0.0,0.0}, {1.0,-2.0,1.0,0.0},

{0.0,1.0,-2.0,1.0}, {0.0,0.0,1.0,-2.0}};

const double b[n]={-5.0,0.0,0.0,0.0};

double x[n], new_x[n];

double sum;

const int MaxIts=50;

int Its,i,j;

for(i=0;i<n;i++) x[i]=1.0; /* initialise */

for(Its=1;Its<=MaxIts;Its++)

{ printf("It=%d",Its);

for(i=0; i<n; i++)

{ sum=0.0;

for(j=0;j<n;j++)

if(i!=j)sum+=m[i][j]*x[j];

new_x[i]=(b[i]-sum)/m[i][i];

}

for(i=0;i<n;i++)

{ x[i]=new_x[i];

printf(" x[%d]=%9.7f",i,x[i]);

}

printf("\n");

}

return 0;

}

Result (note v1 is x[0] through to v4 is x[3])

$ ./jacobi

It=1 x[0]=3.0000000 x[1]=1.0000000 x[2]=1.0000000 x[3]=0.5000000

It=2 x[0]=3.0000000 x[1]=2.0000000 x[2]=0.7500000 x[3]=0.5000000

It=3 x[0]=3.5000000 x[1]=1.8750000 x[2]=1.2500000 x[3]=0.3750000

It=4 x[0]=3.4375000 x[1]=2.3750000 x[2]=1.1250000 x[3]=0.6250000

It=5 x[0]=3.6875000 x[1]=2.2812500 x[2]=1.5000000 x[3]=0.5625000

It=6 x[0]=3.6406250 x[1]=2.5937500 x[2]=1.4218750 x[3]=0.7500000

It=7 x[0]=3.7968750 x[1]=2.5312500 x[2]=1.6718750 x[3]=0.7109375

It=8 x[0]=3.7656250 x[1]=2.7343750 x[2]=1.6210938 x[3]=0.8359375

It=9 x[0]=3.8671875 x[1]=2.6933594 x[2]=1.7851562 x[3]=0.8105469

It=10 x[0]=3.8466797 x[1]=2.8261719 x[2]=1.7519531 x[3]=0.8925781

It=11 x[0]=3.9130859 x[1]=2.7993164 x[2]=1.8593750 x[3]=0.8759766

It=12 x[0]=3.8996582 x[1]=2.8862305 x[2]=1.8376465 x[3]=0.9296875

It=13 x[0]=3.9431152 x[1]=2.8686523 x[2]=1.9079590 x[3]=0.9188232

It=14 x[0]=3.9343262 x[1]=2.9255371 x[2]=1.8937378 x[3]=0.9539795

It=15 x[0]=3.9627686 x[1]=2.9140320 x[2]=1.9397583 x[3]=0.9468689

It=16 x[0]=3.9570160 x[1]=2.9512634 x[2]=1.9304504 x[3]=0.9698792

It=17 x[0]=3.9756317 x[1]=2.9437332 x[2]=1.9605713 x[3]=0.9652252

It=18 x[0]=3.9718666 x[1]=2.9681015 x[2]=1.9544792 x[3]=0.9802856

It=19 x[0]=3.9840508 x[1]=2.9631729 x[2]=1.9741936 x[3]=0.9772396

It=20 x[0]=3.9815865 x[1]=2.9791222 x[2]=1.9702063 x[3]=0.9870968

It=21 x[0]=3.9895611 x[1]=2.9758964 x[2]=1.9831095 x[3]=0.9851031

It=22 x[0]=3.9879482 x[1]=2.9863353 x[2]=1.9804997 x[3]=0.9915547

C Cox 21.2.2017

automatically generating matrix data for large networks.

Unoptimized program

(This is the same as the previous program with different data loaded)

#include <stdio.h>

#define n 4

int main()

{ const double m[n][n]={{-2.0,1.0,0.0,0.0}, {1.0,-2.0,1.0,0.0},

{0.0,1.0,-2.0,1.0}, {0.0,0.0,1.0,-2.0}};

const double b[n]={-5.0,0.0,0.0,0.0};

double x[n], new_x[n];

double sum;

const int MaxIts=50;

int Its,i,j;

for(i=0;i<n;i++) x[i]=1.0; /* initialise */

for(Its=1;Its<=MaxIts;Its++)

{ printf("It=%d",Its);

for(i=0; i<n; i++)

{ sum=0.0;

for(j=0;j<n;j++)

if(i!=j)sum+=m[i][j]*x[j];

new_x[i]=(b[i]-sum)/m[i][i];

}

for(i=0;i<n;i++)

{ x[i]=new_x[i];

printf(" x[%d]=%9.7f",i,x[i]);

}

printf("\n");

}

return 0;

}

Result (note v1 is x[0] through to v4 is x[3])

$ ./jacobi

It=1 x[0]=3.0000000 x[1]=1.0000000 x[2]=1.0000000 x[3]=0.5000000

It=2 x[0]=3.0000000 x[1]=2.0000000 x[2]=0.7500000 x[3]=0.5000000

It=3 x[0]=3.5000000 x[1]=1.8750000 x[2]=1.2500000 x[3]=0.3750000

It=4 x[0]=3.4375000 x[1]=2.3750000 x[2]=1.1250000 x[3]=0.6250000

It=5 x[0]=3.6875000 x[1]=2.2812500 x[2]=1.5000000 x[3]=0.5625000

It=6 x[0]=3.6406250 x[1]=2.5937500 x[2]=1.4218750 x[3]=0.7500000

It=7 x[0]=3.7968750 x[1]=2.5312500 x[2]=1.6718750 x[3]=0.7109375

It=8 x[0]=3.7656250 x[1]=2.7343750 x[2]=1.6210938 x[3]=0.8359375

It=9 x[0]=3.8671875 x[1]=2.6933594 x[2]=1.7851562 x[3]=0.8105469

It=10 x[0]=3.8466797 x[1]=2.8261719 x[2]=1.7519531 x[3]=0.8925781

It=11 x[0]=3.9130859 x[1]=2.7993164 x[2]=1.8593750 x[3]=0.8759766

It=12 x[0]=3.8996582 x[1]=2.8862305 x[2]=1.8376465 x[3]=0.9296875

It=13 x[0]=3.9431152 x[1]=2.8686523 x[2]=1.9079590 x[3]=0.9188232

It=14 x[0]=3.9343262 x[1]=2.9255371 x[2]=1.8937378 x[3]=0.9539795

It=15 x[0]=3.9627686 x[1]=2.9140320 x[2]=1.9397583 x[3]=0.9468689

It=16 x[0]=3.9570160 x[1]=2.9512634 x[2]=1.9304504 x[3]=0.9698792

It=17 x[0]=3.9756317 x[1]=2.9437332 x[2]=1.9605713 x[3]=0.9652252

It=18 x[0]=3.9718666 x[1]=2.9681015 x[2]=1.9544792 x[3]=0.9802856

It=19 x[0]=3.9840508 x[1]=2.9631729 x[2]=1.9741936 x[3]=0.9772396

It=20 x[0]=3.9815865 x[1]=2.9791222 x[2]=1.9702063 x[3]=0.9870968

It=21 x[0]=3.9895611 x[1]=2.9758964 x[2]=1.9831095 x[3]=0.9851031

It=22 x[0]=3.9879482 x[1]=2.9863353 x[2]=1.9804997 x[3]=0.9915547

C Cox 21.2.2017

## Secure Best Marks with AI Grader

Need help grading? Try our AI Grader for instant feedback on your assignments.

It=23 x[0]=3.9931676 x[1]=2.9842240 x[2]=1.9889450 x[3]=0.9902499

It=24 x[0]=3.9921120 x[1]=2.9910563 x[2]=1.9872369 x[3]=0.9944725

It=25 x[0]=3.9955282 x[1]=2.9896744 x[2]=1.9927644 x[3]=0.9936185

It=26 x[0]=3.9948372 x[1]=2.9941463 x[2]=1.9916465 x[3]=0.9963822

It=27 x[0]=3.9970731 x[1]=2.9932418 x[2]=1.9952642 x[3]=0.9958232

It=28 x[0]=3.9966209 x[1]=2.9961687 x[2]=1.9945325 x[3]=0.9976321

It=29 x[0]=3.9980843 x[1]=2.9955767 x[2]=1.9969004 x[3]=0.9972663

It=30 x[0]=3.9977884 x[1]=2.9974924 x[2]=1.9964215 x[3]=0.9984502

It=31 x[0]=3.9987462 x[1]=2.9971049 x[2]=1.9979713 x[3]=0.9982107

It=32 x[0]=3.9985525 x[1]=2.9983587 x[2]=1.9976578 x[3]=0.9989856

It=33 x[0]=3.9991794 x[1]=2.9981052 x[2]=1.9986722 x[3]=0.9988289

It=34 x[0]=3.9990526 x[1]=2.9989258 x[2]=1.9984670 x[3]=0.9993361

It=35 x[0]=3.9994629 x[1]=2.9987598 x[2]=1.9991309 x[3]=0.9992335

It=36 x[0]=3.9993799 x[1]=2.9992969 x[2]=1.9989967 x[3]=0.9995655

It=37 x[0]=3.9996485 x[1]=2.9991883 x[2]=1.9994312 x[3]=0.9994983

It=38 x[0]=3.9995941 x[1]=2.9995398 x[2]=1.9993433 x[3]=0.9997156

It=39 x[0]=3.9997699 x[1]=2.9994687 x[2]=1.9996277 x[3]=0.9996717

It=40 x[0]=3.9997344 x[1]=2.9996988 x[2]=1.9995702 x[3]=0.9998139

It=41 x[0]=3.9998494 x[1]=2.9996523 x[2]=1.9997563 x[3]=0.9997851

It=42 x[0]=3.9998261 x[1]=2.9998029 x[2]=1.9997187 x[3]=0.9998782

It=43 x[0]=3.9999014 x[1]=2.9997724 x[2]=1.9998405 x[3]=0.9998593

It=44 x[0]=3.9998862 x[1]=2.9998710 x[2]=1.9998159 x[3]=0.9999203

It=45 x[0]=3.9999355 x[1]=2.9998510 x[2]=1.9998956 x[3]=0.9999079

It=46 x[0]=3.9999255 x[1]=2.9999156 x[2]=1.9998795 x[3]=0.9999478

It=47 x[0]=3.9999578 x[1]=2.9999025 x[2]=1.9999317 x[3]=0.9999397

It=48 x[0]=3.9999513 x[1]=2.9999447 x[2]=1.9999211 x[3]=0.9999658

It=49 x[0]=3.9999724 x[1]=2.9999362 x[2]=1.9999553 x[3]=0.9999606

It=50 x[0]=3.9999681 x[1]=2.9999638 x[2]=1.9999484 x[3]=0.9999776

Note that convergence (to more than 5 significant digits) was not reached

within 50 iterations in this case.

C Cox 21.2.2017

It=24 x[0]=3.9921120 x[1]=2.9910563 x[2]=1.9872369 x[3]=0.9944725

It=25 x[0]=3.9955282 x[1]=2.9896744 x[2]=1.9927644 x[3]=0.9936185

It=26 x[0]=3.9948372 x[1]=2.9941463 x[2]=1.9916465 x[3]=0.9963822

It=27 x[0]=3.9970731 x[1]=2.9932418 x[2]=1.9952642 x[3]=0.9958232

It=28 x[0]=3.9966209 x[1]=2.9961687 x[2]=1.9945325 x[3]=0.9976321

It=29 x[0]=3.9980843 x[1]=2.9955767 x[2]=1.9969004 x[3]=0.9972663

It=30 x[0]=3.9977884 x[1]=2.9974924 x[2]=1.9964215 x[3]=0.9984502

It=31 x[0]=3.9987462 x[1]=2.9971049 x[2]=1.9979713 x[3]=0.9982107

It=32 x[0]=3.9985525 x[1]=2.9983587 x[2]=1.9976578 x[3]=0.9989856

It=33 x[0]=3.9991794 x[1]=2.9981052 x[2]=1.9986722 x[3]=0.9988289

It=34 x[0]=3.9990526 x[1]=2.9989258 x[2]=1.9984670 x[3]=0.9993361

It=35 x[0]=3.9994629 x[1]=2.9987598 x[2]=1.9991309 x[3]=0.9992335

It=36 x[0]=3.9993799 x[1]=2.9992969 x[2]=1.9989967 x[3]=0.9995655

It=37 x[0]=3.9996485 x[1]=2.9991883 x[2]=1.9994312 x[3]=0.9994983

It=38 x[0]=3.9995941 x[1]=2.9995398 x[2]=1.9993433 x[3]=0.9997156

It=39 x[0]=3.9997699 x[1]=2.9994687 x[2]=1.9996277 x[3]=0.9996717

It=40 x[0]=3.9997344 x[1]=2.9996988 x[2]=1.9995702 x[3]=0.9998139

It=41 x[0]=3.9998494 x[1]=2.9996523 x[2]=1.9997563 x[3]=0.9997851

It=42 x[0]=3.9998261 x[1]=2.9998029 x[2]=1.9997187 x[3]=0.9998782

It=43 x[0]=3.9999014 x[1]=2.9997724 x[2]=1.9998405 x[3]=0.9998593

It=44 x[0]=3.9998862 x[1]=2.9998710 x[2]=1.9998159 x[3]=0.9999203

It=45 x[0]=3.9999355 x[1]=2.9998510 x[2]=1.9998956 x[3]=0.9999079

It=46 x[0]=3.9999255 x[1]=2.9999156 x[2]=1.9998795 x[3]=0.9999478

It=47 x[0]=3.9999578 x[1]=2.9999025 x[2]=1.9999317 x[3]=0.9999397

It=48 x[0]=3.9999513 x[1]=2.9999447 x[2]=1.9999211 x[3]=0.9999658

It=49 x[0]=3.9999724 x[1]=2.9999362 x[2]=1.9999553 x[3]=0.9999606

It=50 x[0]=3.9999681 x[1]=2.9999638 x[2]=1.9999484 x[3]=0.9999776

Note that convergence (to more than 5 significant digits) was not reached

within 50 iterations in this case.

C Cox 21.2.2017

1 out of 8

### Related Documents

Your All-in-One AI-Powered Toolkit for Academic Success.

##### +13062052269

##### info@desklib.com

Available 24*7 on WhatsApp / Email

Unlock your academic potential

© 2024 | Zucol Services PVT LTD | All rights reserved.