Difference between revisions of "Scilab/C4/Linear-equations-Iterative-Methods/English"

From Script | Spoken-Tutorial
Jump to: navigation, search
 
Line 61: Line 61:
  
  
Here '''e '''denotes the answer should be in '''scientific notation''' and twenty specifies the number of digits to be displayed.
+
Here '''e '''denotes the answer should be in '''scientific notation'''.
 +
 
 +
And '''twenty''' specifies the number of digits to be displayed.
  
 
|-
 
|-
Line 86: Line 88:
  
 
'''<nowiki>[m, n] = size( A )</nowiki>'''
 
'''<nowiki>[m, n] = size( A )</nowiki>'''
| style="border-top:none;border-bottom:1pt solid #000000;border-left:1pt solid #000000;border-right:1pt solid #000000;padding:0.097cm;"|Then we use''' size '''function to check if '''A matrix is a square matrix.'''
+
| style="border-top:none;border-bottom:1pt solid #000000;border-left:1pt solid #000000;border-right:1pt solid #000000;padding:0.097cm;"|Then we use''' size '''function to check if '''A matrix''' is a '''square matrix.'''
  
  
Line 114: Line 116:
 
* We then check if '''matrix A''' is '''diagonally dominant'''.
 
* We then check if '''matrix A''' is '''diagonally dominant'''.
 
* The first half calculates the sum of each row of the '''matrix'''.
 
* The first half calculates the sum of each row of the '''matrix'''.
* Then it checks if twice the product of the diagonal element is greater than the sum of the elements of that row.
+
* Then it checks if twice the product of the '''diagonal element''' is greater than the sum of the elements of that row.
 
* If it isn't, an error is displayed using '''error function'''.
 
* If it isn't, an error is displayed using '''error function'''.
  
Line 121: Line 123:
  
 
'''<nowiki>function [ solution ] = JacobiIteration( A, b, x0, MaxIter, tol )</nowiki>'''
 
'''<nowiki>function [ solution ] = JacobiIteration( A, b, x0, MaxIter, tol )</nowiki>'''
| style="border-top:none;border-bottom:1pt solid #000000;border-left:1pt solid #000000;border-right:1pt solid #000000;padding:0.097cm;"|Then we define the function '''Jacobi Iteration''' with input arguments '''A, b , x zero, maximum iteration and tolerance level'''.
+
| style="border-top:none;border-bottom:1pt solid #000000;border-left:1pt solid #000000;border-right:1pt solid #000000;padding:0.097cm;"|Then we define the function '''Jacobi Iteration''' with input arguments  
 +
'''A, b , x zero,'''
 +
 
 +
''' maximum iteration and tolerance level'''.
  
  
Line 171: Line 176:
 
'''endfunction'''
 
'''endfunction'''
 
| style="border-top:none;border-bottom:1pt solid #000000;border-left:1pt solid #000000;border-right:1pt solid #000000;padding:0.097cm;"|
 
| style="border-top:none;border-bottom:1pt solid #000000;border-left:1pt solid #000000;border-right:1pt solid #000000;padding:0.097cm;"|
* We calculate the value for''' x k p one''' and then check if the '''relative error is lesser than tolerance level.'''
+
* We calculate the value for''' x k p one''' and then check if the '''relative error''' is lesser than '''tolerance level.'''
 
* If it is lesser than '''tolerance level''', we break the iteration and the solution is returned.
 
* If it is lesser than '''tolerance level''', we break the iteration and the solution is returned.
 
* Finally we end the function.
 
* Finally we end the function.
 +
 +
 +
 +
 +
 +
 +
 +
 +
  
 
|-
 
|-
Line 207: Line 221:
  
 
Initial approximation nx1: '''<nowiki>[1;1]</nowiki>'''
 
Initial approximation nx1: '''<nowiki>[1;1]</nowiki>'''
| style="border-top:none;border-bottom:1pt solid #000000;border-left:1pt solid #000000;border-right:1pt solid #000000;padding:0.097cm;"| * The '''initial values matrix''' is '''open square bracket one semi colon one close square bracket'''
+
| style="border-top:none;border-bottom:1pt solid #000000;border-left:1pt solid #000000;border-right:1pt solid #000000;padding:0.097cm;"| The '''initial values matrix''' is '''open square bracket one semi colon one close square bracket'''
  
 
Press '''Enter'''.
 
Press '''Enter'''.
Line 241: Line 255:
  
 
The values for '''x one''' and '''x two''' are shown on the '''console'''.  
 
The values for '''x one''' and '''x two''' are shown on the '''console'''.  
 +
 +
The number of iterations are also shown.
  
 
|-
 
|-
Line 375: Line 391:
 
* At each iteration, the value of '''x k p one''' gets updated.
 
* At each iteration, the value of '''x k p one''' gets updated.
 
* Also, we check if '''relative error''' is lesser than specified '''tolerance level'''.
 
* Also, we check if '''relative error''' is lesser than specified '''tolerance level'''.
* If it is, we '''break the iteration'''.
+
* If it is, we break the iteration.
* Then equate '''x k p one''' to the variable solution.
+
* Then equate '''x k p one''' to the variable '''solution'''.
 
* Finally, we end the function.
 
* Finally, we end the function.
  
Line 447: Line 463:
  
  
| style="border-top:none;border-bottom:1pt solid #000000;border-left:1pt solid #000000;border-right:1pt solid #000000;padding:0.097cm;"| * Finally we call the function by typing
+
| style="border-top:none;border-bottom:1pt solid #000000;border-left:1pt solid #000000;border-right:1pt solid #000000;padding:0.097cm;"|Finally we call the function by typing
  
 
''' G a u s s S e i d e l open paranthesis A comma b comma x zero comma M a x I t e r comma t o l close paranthesis'''
 
''' G a u s s S e i d e l open paranthesis A comma b comma x zero comma M a x I t e r comma t o l close paranthesis'''

Latest revision as of 22:21, 1 February 2014

Title of script: Solving System of Linear Equations using Iterative Methods

Author: Shamika

Keywords: System of linear equations, Iterative Methods


Visual Cue
Narration
Slide 1 Dear friends, welcome to the Spoken Tutorial on “Solving System of Linear Equations using Iterative Methods
Slide 2 -Learning Objective Slide At the end of this tutorial, you will learn how to:
  • Solve system of linear equations using iterative methods
  • Develop Scilab code to solve linear equations
Slide 3-System Requirement slide To record this tutorial, I am using
  • Ubuntu 12.04 as the operating system
  • and Scilab 5.3.3 version
Slide 4- Prerequisites slide Before practising this tutorial, a learner should have basic knowledge of
  • Scilab
  • and Solving Linear Equations


For Scilab, please refer to the relevant tutorials available on the Spoken Tutorial website.

Slide 5- Jacobi Method * The first iterative method we will be studying is Jacobi method.
  • Given a system of linear equations, with n equations and n unknowns
  • We rewrite the equations such that x of i k plus one is equal to b i minus summation of a i j x j k from j equal to one to n divided by a i i where i is from one to n
  • We assume values for each x of i
  • Then we substitute the values in the equations obtained in the previous step.
  • We continue the iteration until the solution converges.
Slide 6- Example Let us solve this example using Jacobi Method
Switch to Scilab and open JacobiIteration_final.sci Let us look at the code for Jacobi Method.
Highlight

format('e',20)

We use format method to specify the format of the displayed answers on the Scilab console.


Here e denotes the answer should be in scientific notation.

And twenty specifies the number of digits to be displayed.

Highlight

A=input("Enter the coeffiecient matrix of nxn: ")

b=input("Enter the right-hand side matrix nx1: ")

x0=input("Initial approximation nx1: ")

MaxIter=input("Maximum no. of iterations: ")

tol=input("Enter the convergence tolerance :")//stop if norm change in x < tol

Then we use input function to get the values for
  • the matrices coefficient matrix,
  • right hand side matrix,
  • initial values matrix,
  • maximum number of iteration and
  • convergence tolerance
Highlight

[m, n] = size( A )

Then we use size function to check if A matrix is a square matrix.


If it isn't, we use error function to display an error.

Highlight

for i=1:1:m

sum=0;

for j=1:1:m

sum=sum+abs(A(i,j));

end

if 2*abs(A(i,i))<sum then

error("the matrix is not diagonally dominant")

end

end

  • We then check if matrix A is diagonally dominant.
  • The first half calculates the sum of each row of the matrix.
  • Then it checks if twice the product of the diagonal element is greater than the sum of the elements of that row.
  • If it isn't, an error is displayed using error function.
Highlight

function [ solution ] = JacobiIteration( A, b, x0, MaxIter, tol )

Then we define the function Jacobi Iteration with input arguments

A, b , x zero,

maximum iteration and tolerance level.


Here x zero is the initial values matrix.

Highlight

if ( length(x0) ~= n )

error( "Sizes of input matrix and input vector do not match" )

end

We check if the size of A matrix and initial values matrix are compatible with each other.
Highlight

xk = x0

for k = 1 : 1 : MaxIter

for i = 1 : n

xkp1( i ) = (b(i) - A(i, 1:i-1)*xk(1:i-1) - A(i, i+1:n)*xk(i+1:n)) / A(i,i) //Computes the jacobian updates

end


RelativeError = norm( xkp1 - xk, 'inf' ) / norm( xkp1, 'inf' )

printf( "iter = %d, Relative Error = %g\n", k, RelativeError )

xk = xkp1


if ( RelativeError < tol )

break

end

end


solution = xkp1


endfunction

  • We calculate the value for x k p one and then check if the relative error is lesser than tolerance level.
  • If it is lesser than tolerance level, we break the iteration and the solution is returned.
  • Finally we end the function.






Click on Execute and select Save and Execute Let us save and execute the function.
Switch to Scilab console Switch to Scilab console.
Enter these values on Scilab console for each prompt

Enter the coeffiecient matrix of nxn: [2 1;5 7]

Let us enter the values at each prompt.

The coefficient matrix A is open square bracket two space one semi colon five space seven close square bracket


Press Enter.

Type

Enter the right-hand side matrix nx1: [11; 13]

Then we type open square bracket eleven semicolon thirteen

Press Enter.

Type

Initial approximation nx1: [1;1]

The initial values matrix is open square bracket one semi colon one close square bracket

Press Enter.

Type

Maximum no. of iterations: 25

The maximum number of iterations is twenty five.

Press Enter.

Type

Enter the convergence tolerance :0.00001


Let the convergence tolerance level be zero point zero zero zero zero one

Press Enter.

Type:

JacobiIteration( A, b, x0, MaxIter, tol )

We call the function by typing

Jacobi Iteration open paranthesis A comma b comma x zero comma M a x I t e r comma t o l close paranthesis

Press Enter.


The values for x one and x two are shown on the console.

The number of iterations are also shown.

Slide 7- Gauss Seidel Method Let us now study Gauss Seidel method.
  • Given a system of linear equations, with n equations and n unknowns
  • We rewrite the equations for each unknown
    • by subtracting the other variables and their coefficients
    • from the corresponding right hand side element.
  • Then we divide this by the coefficient a i i of the unknown variable' for that variable.


This is done for every given equation.

Slide 8- Gauss Seidel In Jacobi method, for the computation of x of i k plus one, every element of x of i k is used except x of i k plus one


In Gauss Seidel method, we over write the value of x of i k with x of i k plus one

Slide 9- Example Let us solve this example using Gauss Seidel Method
Switch to Scilab editor and open GaussSeidel.sci Let us look at the code for Gauss Seidel Method
Highlight

format('e',20)

The first line specifies the format of the displayed answer on the console using format function.
Highlight

A=input("Enter the coeffiecient matrix of nxn: ")

b=input("Enter the right-hand side matrix nx1: ")

x0=input("Initial approximation nx1: ")

MaxIter=input("Maximum no. of iterations: ")

tol=input("Enter the convergence tolerance :")//stop if norm change in x < tol

Then we use input function to get the values of
  • coefficient matrix,
  • right hand side matrix,
  • initial values of the variables matrix,
  • maximum number of iterations and
  • tolerance level
Highlight

function [ solution ] = GaussSeidel( A, b, x0, MaxIter, tol )

Then we define the function Gauss Seidel with input arguments A comma b comma x zero comma max iterations and tolerance level and output argument solution


Highlight

// Check that the matrix is square

[m, n] = size( A )

if ( m ~= n )

error( "The input matrix is not square" )

end


// Check that the initial vector is of the same size

if ( length(x0) ~= n )

error( "Sizes of input matrix and input vector do not match" )

end

We check if matrix A is square and the sizes of initial vector and matrix A are compatible using size and length function.
Highlight

xk = x0

xkp1 = zeros( xk )

Then we start the iterations.
  • We equate the initial values vector x zero to x k.
  • We create a matrix of zeros with the same size of x k and call it x k p one.
Highlight

for k = 1 : 1 : MaxIter


// Computes the Gauss-Seidel update

for i = 1 : n

xkp1( i ) = (b(i) - A(i, 1:i-1)*xkp1(1:i-1) - A(i,i+1:n)*xk(i+1:n)) / A(i,i)

// x^{k+1}

end

// Applies the relaxation

RelativeError = norm( xkp1 - xk, 'inf' ) / norm( xkp1, 'inf' )

printf( "iter = %d, Relative Error = %g\n", k, RelativeError )

xk = xkp1

if ( RelativeError < tol )

break

end

end


solution = xkp1


endfunction

We solve for each equation to get the value of the unknown variable for that equation using x k p one.
  • At each iteration, the value of x k p one gets updated.
  • Also, we check if relative error is lesser than specified tolerance level.
  • If it is, we break the iteration.
  • Then equate x k p one to the variable solution.
  • Finally, we end the function.
Click on Execute and select Save and Execute Let us save and execute the function.
Switch to Scilab console Switch to Scilab console
Type the following on Scilab console:

For first prompt

[2 1;5 7]

For the first prompt, we type matrix A.

Type open square bracket two space one semi colon five space seven close square bracket

Press Enter.


Second prompt

[11; 13]

For the next prompt,

type left square bracket eleven semi colon thirteen right square bracket

Press Enter.

For third prompt

[1;1]

We provide the values of initial value vector by typing

open square bracket one semicolon one close square bracket


Press Enter.

For fourth prompt

25

Then we specify the maximum number of iterations to be twenty five


Press Enter.

For fifth prompt

0.00001

Let us define tolerance level to be zero point zero zero zero zero one


Press Enter.

Then type:

GaussSeidel( A, b, x0, MaxIter, tol )


Finally we call the function by typing

G a u s s S e i d e l open paranthesis A comma b comma x zero comma M a x I t e r comma t o l close paranthesis


Press Enter.


The values of x one and x two are displayed.


The number of iterations to solve the same problem are lesser than Jacobi method.

Slide 13- Solve Solve this problem on your own using Jacobi and Gauss Seidel methods
Slide 14- Summary In this tutorial, we have learnt to:
  • Develop Scilab code for solving system of linear equations
  • Find the value of the unknown variables of a system of linear equations


Show Slide 15

Title: About the Spoken Tutorial Project

  • It summarises the Spoken Tutorial project
  • If you do not have good bandwidth, you can download and watch it


* About the Spoken Tutorial Project
  • Watch the video available at the following link
  • It summarises the Spoken Tutorial project
  • If you do not have good bandwidth, you can download and watch it
Show Slide 16

Title: Spoken Tutorial Workshops

The Spoken Tutorial Project Team

  • Conducts workshops using spoken tutorials
  • Gives certificates for those who pass an online test
  • For more details, please write to contact@spoken-tutorial.org


The Spoken Tutorial Project Team
  • Conducts workshops using spoken tutorials
  • Gives certificates for those who pass an online test
  • For more details, please write to contact at spoken hyphen tutorial dot org


Show Slide 17

Title: Acknowledgement

  • Spoken Tutorial Project is a part of the Talk to a Teacher project
  • It is supported by the National Mission on Education through ICT, MHRD, Government of India
  • More information on this Mission is available at


* Spoken Tutorial Project is a part of the Talk to a Teacher project
  • It is supported by the National Mission on Education through ICT, MHRD, Government of India
  • More information on this Mission is available at
  • spoken hyphen tutorial dot org slash NMEICT hyphen Intro


This is Ashwini Patil signing off. Thank you for joining.


Contributors and Content Editors

Lavitha Pereira, Nancyvarkey