VECTORS

1

MATRICES

2

MATRICES

3

Determinant of a MATRICES

CISE301_Topic3

4

Adding and Multiplying Matrices

CISE301_Topic3

5

Systems of Linear Equations

CISE301_Topic3

6

Solutions of Linear Equations

CISE301_Topic3

7

Solutions of Linear Equations

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

CISE301_Topic3

8

Solutions of Linear Equations

• Some systems of equations may have infinite number of solutions

CISE301_Topic3

9

Graphical Solution of Systems of�Linear Equations

CISE301_Topic3

10

Solution

x₁=1, x₂=2

Cramer’s Rule is Not Practical

CISE301_Topic3

11

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

12

Elementary Row Operations

​

• Adding a multiple of one row to another

​

• Multiply any row by a non-zero constant

CISE301_Topic3

13

Example�Forward Elimination

CISE301_Topic3

14

Example�Forward Elimination

CISE301_Topic3

15

Example�Forward Elimination

CISE301_Topic3

16

Example�Backward Substitution

CISE301_Topic3

17

Forward Elimination

CISE301_Topic3

18

Forward Elimination

CISE301_Topic3

19

Backward Substitution

CISE301_Topic3

20

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 x_n ,x_n-1,…x_1.

CISE301_Topic3

21

Example 1

CISE301_Topic3

22

Example 1

CISE301_Topic3

23

Example 1�Backward Substitution

CISE301_Topic3

24

Determinant

CISE301_Topic3

25

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

CISE301_Topic3

26

Examples

CISE301_Topic3

27

Pseudo-Code: Forward Elimination

Do k = 1 to n-1

Do i = k+1 to n

factor = a_i,k / a_k,k

Do j = k+1 to n

a_i,j = a_i,j – factor * a_k,j

End Do

b_i = b_i – factor * b_k

End Do

End Do

CISE301_Topic3

28

Pseudo-Code: Back Substitution

x_n = b_n / a_n,n

Do i = n-1 downto 1

sum = b_i

Do j = i+1 to n

sum = sum – a_i,j * x_j

End Do

x_i = sum / a_i,i

End Do

CISE301_Topic3

29

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

30

Example 2

CISE301_Topic3

31

Example 2�Initialization step

CISE301_Topic3

32

Scale vector:

disregard sign

find largest in magnitude in each row

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

33

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

CISE301_Topic3

34

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

CISE301_Topic3

35

First pivot equation

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

CISE301_Topic3

36

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

CISE301_Topic3

37

Third pivot equation

Example 2�Backward Substitution

CISE301_Topic3

38

Example 3

CISE301_Topic3

39

Example 3�Initialization step

CISE301_Topic3

40

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

CISE301_Topic3

41

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

CISE301_Topic3

42

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

CISE301_Topic3

43

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

CISE301_Topic3

44

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

CISE301_Topic3

45

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

CISE301_Topic3

46

Example 3�Backward Substitution

CISE301_Topic3

47

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

48

How Good is the Solution?

CISE301_Topic3

49

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

50

Tridiagonal Systems

Tridiagonal Systems:

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

​

CISE301_Topic3

51

Tridiagonal Systems

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

​

CISE301_Topic3

52

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

53

Tridiagonal System

CISE301_Topic3

54

Diagonal Dominance

CISE301_Topic3

55

Diagonal Dominance

CISE301_Topic3

56

Diagonally Dominant Tridiagonal System

• A tridiagonal system is diagonally dominant if

​

​

​

​

• Forward Elimination preserves diagonal dominance

CISE301_Topic3

57

Solving Tridiagonal System

CISE301_Topic3

58

Example

CISE301_Topic3

59

Example

CISE301_Topic3

60

Example�Backward Substitution

• After the Forward Elimination:

​

• Backward Substitution:

CISE301_Topic3

61

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

62

Gauss-Jordan Method�Example

CISE301_Topic3

63

Gauss-Jordan Method�Example

CISE301_Topic3

64

Gauss-Jordan Method�Example

CISE301_Topic3

65

Gauss-Jordan Method�Example

CISE301_Topic3

66