1 of 67

UNIT - 3

SYSTEM OF LINEAR ALGEBRAIC EQUATIONS

CISE301_Topic3

1

2 of 67

VECTORS

2

3 of 67

MATRICES

3

4 of 67

MATRICES

4

5 of 67

Determinant of a MATRICES

CISE301_Topic3

5

6 of 67

Adding and Multiplying Matrices

CISE301_Topic3

6

7 of 67

Systems of Linear Equations

CISE301_Topic3

7

8 of 67

Solutions of Linear Equations

CISE301_Topic3

8

9 of 67

Solutions of Linear Equations

  • A set of equations is inconsistent if there exists no solution to the system of equations:

CISE301_Topic3

9

10 of 67

Solutions of Linear Equations

  • Some systems of equations may have infinite number of solutions

CISE301_Topic3

10

11 of 67

Graphical Solution of Systems of�Linear Equations

CISE301_Topic3

11

Solution

x1=1, x2=2

12 of 67

Cramer’s Rule is Not Practical

CISE301_Topic3

12

13 of 67

Naive Gaussian Elimination

  • The method consists of two steps:
    • Forward Elimination: the system is reduced to upper triangular form. A sequence of elementary operations is used.
    • Backward Substitution: Solve the system starting from the last variable.

CISE301_Topic3

13

14 of 67

Elementary Row Operations

​

  • Adding a multiple of one row to another

​

  • Multiply any row by a non-zero constant

CISE301_Topic3

14

15 of 67

Example�Forward Elimination

CISE301_Topic3

15

16 of 67

Example�Forward Elimination

CISE301_Topic3

16

17 of 67

Example�Forward Elimination

CISE301_Topic3

17

18 of 67

Example�Backward Substitution

CISE301_Topic3

18

19 of 67

Forward Elimination

CISE301_Topic3

19

20 of 67

Forward Elimination

CISE301_Topic3

20

21 of 67

Backward Substitution

CISE301_Topic3

21

22 of 67

Naive Gaussian Elimination

  • The method consists of two steps
    • Forward Elimination: the system is reduced to upper triangular form. A sequence of elementary operations is used.

​

​

​

​

    • Backward Substitution: Solve the system starting from the last variable. Solve for xn ,xn-1,…x1.

CISE301_Topic3

22

23 of 67

Example 1

CISE301_Topic3

23

24 of 67

Example 1

CISE301_Topic3

24

25 of 67

Example 1�Backward Substitution

CISE301_Topic3

25

26 of 67

Determinant

CISE301_Topic3

26

27 of 67

How Many Solutions Does a System of Equations AX=B Have?

CISE301_Topic3

27

28 of 67

Examples

CISE301_Topic3

28

29 of 67

Pseudo-Code: Forward Elimination

Do k = 1 to n-1

Do i = k+1 to n

factor = ai,k / ak,k

Do j = k+1 to n

ai,j = ai,j – factor * ak,j

End Do

bi = bi – factor * bk

End Do

End Do

CISE301_Topic3

29

30 of 67

Pseudo-Code: Back Substitution

xn = bn / an,n

Do i = n-1 downto 1

sum = bi

Do j = i+1 to n

sum = sum – ai,j * xj

End Do

xi = sum / ai,i

End Do

CISE301_Topic3

30

31 of 67

Problems with Naive Gaussian Elimination

  • The Naive Gaussian Elimination may fail for very simple cases. (The pivoting element is zero).

​

​

​

​

  • Very small pivoting element may result in serious computation errors

CISE301_Topic3

31

32 of 67

Example 2

CISE301_Topic3

32

33 of 67

Example 2�Initialization step

CISE301_Topic3

33

Scale vector:

disregard sign

find largest in magnitude in each row

34 of 67

Why Index Vector?

  • Index vectors are used because it is much easier to exchange a single index element compared to exchanging the values of a complete row.
  • In practical problems with very large N, exchanging the contents of rows may not be practical.

CISE301_Topic3

34

35 of 67

Example 2�Forward Elimination-- Step 1: eliminate x1

CISE301_Topic3

35

36 of 67

Example 2�Forward Elimination-- Step 1: eliminate x1

CISE301_Topic3

36

First pivot equation

37 of 67

Example 2�Forward Elimination-- Step 2: eliminate x2

CISE301_Topic3

37

38 of 67

Example 2�Forward Elimination-- Step 3: eliminate x3

CISE301_Topic3

38

Third pivot equation

39 of 67

Example 2�Backward Substitution

CISE301_Topic3

39

40 of 67

Example 3

CISE301_Topic3

40

41 of 67

Example 3�Initialization step

CISE301_Topic3

41

42 of 67

Example 3�Forward Elimination-- Step 1: eliminate x1

CISE301_Topic3

42

43 of 67

Example 3�Forward Elimination-- Step 1: eliminate x1

CISE301_Topic3

43

44 of 67

Example 3�Forward Elimination-- Step 2: eliminate x2

CISE301_Topic3

44

45 of 67

Example 3�Forward Elimination-- Step 2: eliminate x2

CISE301_Topic3

45

46 of 67

Example 3�Forward Elimination-- Step 3: eliminate x3

CISE301_Topic3

46

47 of 67

Example 3�Forward Elimination-- Step 3: eliminate x3

CISE301_Topic3

47

48 of 67

Example 3�Backward Substitution

CISE301_Topic3

48

49 of 67

How Do We Know If a Solution is Good or Not

Given AX=B

X is a solution if AX-B=0

Compute the residual vector R= AX-B

Due to rounding error, R may not be zero

CISE301_Topic3

49

50 of 67

How Good is the Solution?

CISE301_Topic3

50

51 of 67

Remarks:

  • We use index vector to avoid the need to move the rows which may not be practical for large problems.
  • If we order the equation as in the last value of the index vector, we have a triangular form.
  • Scale vector is formed by taking maximum in magnitude in each row.
  • Scale vector does not change.
  • The original matrices A and B are used in checking the residuals.

CISE301_Topic3

51

52 of 67

Tridiagonal Systems

Tridiagonal Systems:

  • The non-zero elements are in the main diagonal, super diagonal and subdiagonal.
  • aij=0 if |i-j| > 1

​

CISE301_Topic3

52

53 of 67

Tridiagonal Systems

  • Occur in many applications
  • Needs less storage (4n-2 compared to n2 +n for the general cases)
  • Selection of pivoting rows is unnecessary (under some conditions)
  • Efficiently solved by Gaussian elimination

​

CISE301_Topic3

53

54 of 67

Algorithm to Solve Tridiagonal Systems

  • Based on Naive Gaussian elimination.
  • As in previous Gaussian elimination algorithms
    • Forward elimination step
    • Backward substitution step
  • Elements in the super diagonal are not affected.
  • Elements in the main diagonal, and B need updating

​

CISE301_Topic3

54

55 of 67

Tridiagonal System

CISE301_Topic3

55

56 of 67

Diagonal Dominance

CISE301_Topic3

56

57 of 67

Diagonal Dominance

CISE301_Topic3

57

58 of 67

Diagonally Dominant Tridiagonal System

  • A tridiagonal system is diagonally dominant if

​

​

​

​

  • Forward Elimination preserves diagonal dominance

CISE301_Topic3

58

59 of 67

Solving Tridiagonal System

CISE301_Topic3

59

60 of 67

Example

CISE301_Topic3

60

61 of 67

Example

CISE301_Topic3

61

62 of 67

Example�Backward Substitution

  • After the Forward Elimination:

​

  • Backward Substitution:

CISE301_Topic3

62

63 of 67

Gauss-Jordan Method

  • The method reduces the general system of equations AX=B to IX=B where I is an identity matrix.

​

  • Only Forward elimination is done and no backward substitution is needed.

​

  • It has the same problems as Naive Gaussian elimination and can be modified to do partial scaled pivoting.

​

  • It takes 50% more time than Naive Gaussian method.

CISE301_Topic3

63

64 of 67

Gauss-Jordan Method�Example

CISE301_Topic3

64

65 of 67

Gauss-Jordan Method�Example

CISE301_Topic3

65

66 of 67

Gauss-Jordan Method�Example

CISE301_Topic3

66

67 of 67

Gauss-Jordan Method�Example

CISE301_Topic3

67