comp 391-079 Numerical Analysis

Cramer's Rule

Cramer’s Rule is cool trick used to solve a set of linear equations with the determinate.

Naïve Gaussian elimination on the other hand has a running time = (m^3)/3+O(m^2) for forward and backward substitution. The naïve method does not pivot

Naïve Gaussian elimination

Naïve Gaussian elimination running time = (m^3)/3+O(m^2) for forward and backward substitution. The naïve method does not pivot.

Problems with naïve method and the solutions:

Without pivoting there is a divide by zero when one of the coefficients is zero. Pivoting will chose a non-zero coefficient.

Round off errors are caused by rounding errors in the computer’s representation of numbers. The error is greater for bigger sets of equations as there are more row eliminations (ie mathematical operations). The solution is to use more significant figures in the number representation.

Ill-conditioned systems are singular systems, in which two equations are equal. This loss of one degree of freedom might mean there are not enough constraints to satisfy the problem. This case might also occur if two equations are very similar; for example 1.1x+2y=4 and 1x+2y=4. The rounding errors in the computer might make these conditions singular. The solution for the second case is to scale the equations. The amount of scaling depends on the application.

LU decomposition

LU decomposition is useful when many b’s have to be solved for one A, where Ax=b. LU decomposition is an alternative method to the Gaussian elimination solving the set of linear equations. Interesting enough, Gaussian row elimination is used in LU decomposition.

The way LU decomposition works:

Matrix U is in the diagonal form needed to backwards substitute and solve for X.
The intuition to this method is as follows. The matrix A is reduced to row echelon form (U). In the naïve method the d vector is also reduced, however, in LU decomposition the operations to the d vector are recorded in the L matrix; that is, the coefficients to reduce the rows are stored in L. L*d will reduce the d vector to the same vector d would be if reduced at the same time as A. Now U and d’ can solve for X by backwards substitution.
Pivoting has to be used in the cases in which an A coefficient could be zero and cause divide by zero.
When storing the non-zero components of L in the zero components of U efficiently uses implementing LU decomposition space.

LU decomposition used for matrix inverse

The matrix inverse is equivalent to solving d= {a,b,c} for Ad={1,0,0}, and d for the columns in I, where d is the columns of the inverse matrix of A. very cool, I will never do a matrix inverse another way.

Cholesky decomposition

This decomposition applies to special case matrices: symmetric matrices A=A transpose. Such matrices are found in engineering applications such as in Kirchhoff’s Voltage law. The symmetric A matrix can be decomposed into A=LL^T with the following formulas.

This method will only work when the matrix A is positive definite, that is {X}T[A]{X} >=0 for all non-zero vectors {X}.

Sensitivity of Linear Systems

The matrix condition number evaluates the accuracy of a matrix operation. It is interesting that this method can compute to the number of accurate digits in a matrix operation. I do not understand all the details.

Reducing error in Linear Algebra

The solutions to a set of linear algebraic equations can be iterated to reduce the error while solving it. Imagine that there are three unknowns. Solving the equations with the calculated solutions will give a slight deviation of the b in Ax=b. The error term can be incorporated into the equations. Another iteration should make the solved variables more accurate.