Further Examples: LUDecomposition

This gives the LU decomposition of the matrix m2.

In[1]:=

Out[1]=

We solve the system m2.v = {5,8}.

In[2]:=

Out[2]=

This checks the result.

In[3]:=

Out[3]=

In[4]:=

Recovering the lower and upper triangular matrices from the LU decomposition

Given a matrix M, LUDecomposition determines a lower triangular matrix L with ones on the diagonal, an upper triangular matrix U, and a permutation vector P such that applying P to M rearranges its rows to give L.U. Solving the system L.U.x == b amounts to solving two triangular systems in a row, which is faster than solving the equivalent system M.x == b.

The matrices L and U are returned as a single matrix, with the ones on the main diagonal of L left out. The functions Lower and Upper recover the matrices by multiplying pairwise (not dot multiplying!) with appropriate matrices of zeros and ones.

In[5]:=

In[6]:=

Here is a x inexact matrix.

In[7]:=

This names the three components returned by LUDecomposition.

In[8]:=

Out[8]=

This is the lower triangular matrix L.

In[9]:=

Out[9]//MatrixForm=

This is the upper triangular matrix U.

In[10]:=

Out[10]//MatrixForm=

This checks the result.

In[11]:=

Out[11]//MatrixForm=

In[12]:=

How accurate is the numerical solution of a linear system of equations?

h7 is a x Hilbert matrix and v7 is a -vector.

In[13]:=

Out[13]//MatrixForm=

In[14]:=

Here is the exact solution of this linear system.

In[15]:=

Out[15]=

Here is the approximate solution of this linear system.

In[16]:=

Out[16]=

We check the accuracy of approxsol by comparing it to exactsol. For larger systems this may not be possible.

In[17]:=

Out[17]=

The relative error is the ratio of the error to the actual result. So or decimal places are correct.

In[18]:=

Out[18]=

The residual error measures by how much we fail to satisfy the equation using the approximate solution.

In[19]:=

Out[19]=

This gives the matrix condition number. One can estimate an upper bound on the error using the matrix condition number.

In[20]:=

Out[20]=

What typically matters is not the exact value of the condition number but its magnitude. The rough rule is that you may lose that many digits of precision in solving linear equations. For this example we have a condition number that has around digits. Most floating point hardware numbers have about digits of precision. Hence approxsol is guaranteed to at least digits.

In[21]:=