Systems of Linear Equations and Ax=b

Outline:

1) The relationship between systems of linear
equations and Linear Combinations of vectors
2) The relationship between systems of equations
and
3) Basic rules of Matrix - vector products
as linear combinations of vectors
4) : the fundamental issues
5) Solving linear systems:
Introduction to Gaussian Elimination
Systems of linear Equations

A simple example :

x - y = 1
2x + y = 5

Solution by "elimination" and "back-substitution":
The geometry of Linear Systems: the "row" picture

The geometry of Linear Systems: the "column" picture

Linear systems of equations as Linear Combinations of
vectors

x - y = 1
2x + y = 5

Is equivalent to :

Interpretation: solving linear systems is equivalent to finding linear
combination of vectors that add up to another vector

The geometry of Linear Systems: the "column" picture

3x3 problems (3 equations, 3 unknowns ):
A more compact approach:

Introducing the Matrix A

x - y = 1
2x + y = 5

2x2 problem:

3x3 problem:
Matrix-Vector Products:

the Column Picture:

Example:
Matrix-Vector Products:

the Row Picture (dot products):

Example:

Point!: Both Column and Row approaches are identical
Matrix Component Notation:

Matrices in Matlab:
Big Points:

1) is a linear combination of the columns of A
2) is a vector
3) maps to a new vector

The Forward Problem: you know A and , just find .
Easy! Just use Matrix Vector multiplication . A
solution must always exist.

The Inverse Problem: Given A and , find , such that
Much Harder! This is the problem of solving linear
systems.

Fundamental Math questions : Given square A and a vector

1) does a solution exist such that ?
2) is the solution unique ?
3) How do you find ?
The geometry of

The geometry of : Interesting complications...

General results (to be shown):

for square nxn A: has exactly one of three outcomes

1) There is a unique solution
2) There is no solution
3) There are an infinite number of solutions

Question: How can you tell and how do you find the
solution?
Gaussian Elimination:

A systematic algorithm to both diagnose and solve
linear systems

Consider our toy 2x2 problem again:
 
x - y = 1
2x + y = 5
with solution: x=2, y=1

Suppose you wanted to eliminate x instead of y in 2nd equation?

Matrix Form of equations:

Gaussian Elimination:

A systematic algorithm to transform a general matrix A
to upper Triangular form.

Upper Triangular system:

Easily solved by Back Substitution :

Gaussian Elimination:

A systematic algorithm to transform a general matrix A
to upper Triangular form.

Need to transform both A and the RHS b to maintain equality.
Useful to Consider the Augmented matrix

Idea of Elimination: Use row operations to zero out elements
below the pivot using multipliers of the pivot row
Gaussian Elimination:

A systematic algorithm to transform a general matrix A
to upper Triangular form.

Examples:

If it "works", Gaussian Elimination transforms A→U with n distinct pivots.
n Pivots implies a unique solution.
Failure of Gaussian Elimination:

Consider:
Temporary Failure of Gaussian Elimination:

Consider:

The Fix: Row exchange (permutation operation
Gaussian Elimination on a 3x3 system of equations:

Consider:

2x + y + 3z = 3
4x + 3y + 8z = 6
-2x + 3z = 1

Matrix Vector form:

Augmented Matrix form:

 
   
  Gaussian Elimination on a 3x3 system of equations:

Example 2 (row exchange):

x + 2y + 4z = 1
2x + 4y + 2z = 2
6x + 10y - z = 8

Matrix Vector form:

Augmented Matrix form:
   
Gaussian Elimination: The Overall Pattern Linear combinations in 3
Dimensions

 
Prev Next