Scilab/C4/Linear-equations-Iterative-Methods/English

From Script | Spoken-Tutorial
Revision as of 05:02, 18 December 2013 by Lavitha Pereira (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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 with 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 the 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.


Slide 7- Gauss Seidel Method * Let us now study Gauss Seidel method.
  • Given a system of linear equations, with n equations and n unknows
  • 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 iteration 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