9. Solving Linear Equations
Michael Friendly and John Fox
2024-11-19
Source:vignettes/a9-linear-equations.Rmd
a9-linear-equations.Rmd
This vignette illustrates the ideas behind solving systems of linear equations of the form where
- is an matrix of coefficients for equations in unknowns
- is an vector unknowns,
- is an vector of constants, the โright-hand sidesโ of the equations
or, spelled out,
For three equations in three unknowns, the equations look like this:
A <- matrix(paste0("a_{", outer(1:3, 1:3, FUN = paste0), "}"),
nrow=3)
b <- paste0("b_", 1:3)
x <- paste0("x", 1:3)
showEqn(A, b, vars = x, latex=TRUE)
Conditions for a solution
The general conditions for solutions are:
- the equations are consistent (solutions exist) if
- the solution is unique if
- the solution is underdetermined if
- the equations are inconsistent (no solutions) if
We use c( R(A), R(cbind(A,b)) )
to show the ranks, and
all.equal( R(A), R(cbind(A,b)) )
to test for
consistency.
Equations in two unknowns
Each equation in two unknowns corresponds to a line in 2D space. The equations have a unique solution if all lines intersect in a point.
Two consistent equations
## 1*x1 - 1*x2 = 2
## 2*x1 + 2*x2 = 1
Check whether they are consistent:
## [1] 2 2
## [1] TRUE
Plot the equations:
plotEqn(A,b)
## x[1] - 1*x[2] = 2
## 2*x[1] + 2*x[2] = 1
Solve()
is a convenience function that shows the
solution in a more comprehensible form:
Solve(A, b, fractions = TRUE)
## x1 = 5/4
## x2 = -3/4
Three consistent equations
For three (or more) equations in two unknowns, , because . The equations will be consistent if . This means that whatever linear relations exist among the rows of are the same as those among the elements of .
Geometrically, this means that all three lines intersect in a point.
## 1*x1 - 1*x2 = 2
## 2*x1 + 2*x2 = 1
## 3*x1 + 1*x2 = 3
## [1] 2 2
## [1] TRUE
Solve(A, b, fractions=TRUE) # show solution
## x1 = 5/4
## x2 = -3/4
## 0 = 0
Plot the equations:
plotEqn(A,b)
## x[1] - 1*x[2] = 2
## 2*x[1] + 2*x[2] = 1
## 3*x[1] + x[2] = 3
Three inconsistent equations
Three equations in two unknowns are inconsistent when .
## 1*x1 - 1*x2 = 2
## 2*x1 + 2*x2 = 1
## 3*x1 + 1*x2 = 6
## [1] 2 3
## [1] "Mean relative difference: 0.5"
You can see this in the result of reducing to echelon form, where the last row indicates the inconsistency because it represents the equation .
echelon(A, b)
## [,1] [,2] [,3]
## [1,] 1 0 2.75
## [2,] 0 1 -2.25
## [3,] 0 0 -3.00
Solve()
shows this more explicitly, using fractions
where possible:
Solve(A, b, fractions=TRUE)
## x1 = 11/4
## x2 = -9/4
## 0 = -3
An approximate solution is sometimes available using a generalized inverse. This gives as a best close solution.
## [,1]
## [1,] 2
## [2,] -1
Plot the equations. You can see that each pair of equations has a solution, but all three do not have a common, consistent solution.
## x[1] - 1*x[2] = 2
## 2*x[1] + 2*x[2] = 1
## 3*x[1] + x[2] = 6
# add the ginv() solution
points(x[1], x[2], pch=15)
Equations in three unknowns
Each equation in three unknowns corresponds to a plane in 3D space. The equations have a unique solution if all planes intersect in a point.
Three consistent equations
An example:
A <- matrix(c(2, 1, -1,
-3, -1, 2,
-2, 1, 2), 3, 3, byrow=TRUE)
colnames(A) <- paste0('x', 1:3)
b <- c(8, -11, -3)
showEqn(A, b)
## 2*x1 + 1*x2 - 1*x3 = 8
## -3*x1 - 1*x2 + 2*x3 = -11
## -2*x1 + 1*x2 + 2*x3 = -3
Are the equations consistent?
## [1] 3 3
## [1] TRUE
Solve for .
solve(A, b)
## x1 x2 x3
## 2 3 -1
Other ways of solving:
## [,1]
## x1 2
## x2 3
## x3 -1
## [,1]
## [1,] 2
## [2,] 3
## [3,] -1
Yet another way to see the solution is to reduce to echelon form. The result of this is the matrix , with the solution in the last column.
echelon(A, b)
## x1 x2 x3
## [1,] 1 0 0 2
## [2,] 0 1 0 3
## [3,] 0 0 1 -1
`echelon() can be asked to show the steps, as the row operations necessary to reduce to the identity matrix .
echelon(A, b, verbose=TRUE, fractions=TRUE)
##
## Initial matrix:
## x1 x2 x3
## [1,] 2 1 -1 8
## [2,] -3 -1 2 -11
## [3,] -2 1 2 -3
##
## row: 1
##
## exchange rows 1 and 2
## x1 x2 x3
## [1,] -3 -1 2 -11
## [2,] 2 1 -1 8
## [3,] -2 1 2 -3
##
## multiply row 1 by -1/3
## x1 x2 x3
## [1,] 1 1/3 -2/3 11/3
## [2,] 2 1 -1 8
## [3,] -2 1 2 -3
##
## multiply row 1 by 2 and subtract from row 2
## x1 x2 x3
## [1,] 1 1/3 -2/3 11/3
## [2,] 0 1/3 1/3 2/3
## [3,] -2 1 2 -3
##
## multiply row 1 by 2 and add to row 3
## x1 x2 x3
## [1,] 1 1/3 -2/3 11/3
## [2,] 0 1/3 1/3 2/3
## [3,] 0 5/3 2/3 13/3
##
## row: 2
##
## exchange rows 2 and 3
## x1 x2 x3
## [1,] 1 1/3 -2/3 11/3
## [2,] 0 5/3 2/3 13/3
## [3,] 0 1/3 1/3 2/3
##
## multiply row 2 by 3/5
## x1 x2 x3
## [1,] 1 1/3 -2/3 11/3
## [2,] 0 1 2/5 13/5
## [3,] 0 1/3 1/3 2/3
##
## multiply row 2 by 1/3 and subtract from row 1
## x1 x2 x3
## [1,] 1 0 -4/5 14/5
## [2,] 0 1 2/5 13/5
## [3,] 0 1/3 1/3 2/3
##
## multiply row 2 by 1/3 and subtract from row 3
## x1 x2 x3
## [1,] 1 0 -4/5 14/5
## [2,] 0 1 2/5 13/5
## [3,] 0 0 1/5 -1/5
##
## row: 3
##
## multiply row 3 by 5
## x1 x2 x3
## [1,] 1 0 -4/5 14/5
## [2,] 0 1 2/5 13/5
## [3,] 0 0 1 -1
##
## multiply row 3 by 4/5 and add to row 1
## x1 x2 x3
## [1,] 1 0 0 2
## [2,] 0 1 2/5 13/5
## [3,] 0 0 1 -1
##
## multiply row 3 by 2/5 and subtract from row 2
## x1 x2 x3
## [1,] 1 0 0 2
## [2,] 0 1 0 3
## [3,] 0 0 1 -1
Now, letโs plot them.
plotEqn3d()
uses rgl
for 3D graphics. If
you rotate the figure, youโll see an orientation where all three planes
intersect at the solution point,
Three inconsistent equations
A <- matrix(c(1, 3, 1,
1, -2, -2,
2, 1, -1), 3, 3, byrow=TRUE)
colnames(A) <- paste0('x', 1:3)
b <- c(2, 3, 6)
showEqn(A, b)
## 1*x1 + 3*x2 + 1*x3 = 2
## 1*x1 - 2*x2 - 2*x3 = 3
## 2*x1 + 1*x2 - 1*x3 = 6
Are the equations consistent? No.
## [1] 2 3
## [1] "Mean relative difference: 0.5"