Problem 23 - Differential Equations and Linear Algebra

Question

Use the LU factorization of \(A\) to solve the system \(A \mathbf{x}=\mathbf{b}\). $$A=\left[\begin{array}{rrr}1 & -3 & 5 \\\3 & 2 & 2 \\\2 & 5 & 2\end{array}\right], \mathbf{b}=\left[\begin{array}{r}1 \\\5 \\\\-1\end{array}\right]$$

Step-by-Step Solution

Answer

We first compute the LU factorization of matrix A using Doolittle's algorithm, resulting in $$ L=\left[\begin{array}{ccc} 1 & 0 & 0 \\ 3 & 1 & 0 \\ 2 & 4 & 1 \end{array}\right], \quad U=\left[\begin{array}{rrr} 1 & -3 & 5 \\ 0 & 11 & -13 \\ 0 & 0 & -21 \end{array}\right] $$ Next, we perform forward substitution to find the intermediate vector \(\mathbf{y}\): $$\mathbf{y}=\begin{bmatrix} 1 \\ -2\\ 9\end{bmatrix}$$ Finally, we perform backward substitution to find the solution \(\mathbf{x}\): $$\mathbf{x} = \begin{bmatrix} \frac{22}{7} \\ \frac{1}{7}\\ -\frac{3}{7}\end{bmatrix}$$

Step 1: Compute the LU factorization of matrix A

To compute the LU factorization, let's write matrix A as the product of a lower triangular matrix L and an upper triangular matrix U: $$A = LU$$ We will use the Doolittle algorithm, which is based on Gaussian elimination, to compute the LU factorization of A. For the given matrix A: $$ A=\left[\begin{array}{rrr} 1 & -3 & 5 \\ 3 & 2 & 2 \\ 2 & 5 & 2 \end{array}\right] $$ Applying Doolittle's algorithm, we get the LU factorization to be: $$ L=\left[\begin{array}{ccc} 1 & 0 & 0 \\ 3 & 1 & 0 \\ 2 & 4 & 1 \end{array}\right], \quad U=\left[\begin{array}{rrr} 1 & -3 & 5 \\ 0 & 11 & -13 \\ 0 & 0 & -21 \end{array}\right] $$ Now that we have the LU factorization of A, we can use it to solve the linear system.

Step 2: Solve L\(\mathbf{y}\) = \(\mathbf{b}\) for \(\mathbf{y}\)

Since we have A = LU, the given linear system can be written as: $$LU\mathbf{x} = \mathbf{b}$$ We first solve the system \(L\mathbf{y} = \mathbf{b}\) for \(\mathbf{y}\) using forward substitution: $$ \begin{bmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ 2 & 4 & 1 \end{bmatrix} \begin{bmatrix} y_{1}\\ y_{2}\\ y_{3} \end{bmatrix} = \left[ \begin{array}{r} 1 \\ 5 \\ -1 \end{array} \right] $$ Solving the linear system, we get: $$y_{1} = 1$$ $$y_{2} = -5 + 1 \cdot 3 = -2$$ $$y_{3} = 1 - 2 \cdot 2 - 4 \cdot -2 = 9$$ So, \(\mathbf{y}=\begin{bmatrix} 1 \\ -2\\ 9\end{bmatrix}\).

Step 3: Solve U\(\mathbf{x}\) = \(\mathbf{y}\) for \(\mathbf{x}\)

Now, we will solve the system \(U\mathbf{x} = \mathbf{y}\) for \(\mathbf{x}\) using backward substitution: $$ \begin{bmatrix} 1 & -3 & 5 \\ 0 & 11 & -13 \\ 0 & 0 & -21 \end{bmatrix} \begin{bmatrix} x_{1}\\ x_{2}\\ x_{3} \end{bmatrix} = \left[ \begin{array}{r} 1 \\ -2\\ 9 \end{array} \right] $$ Solving the linear system, we get: $$x_{3} = -\frac{9}{21} = -\frac{3}{7}$$ $$x_{2} = \frac{-2 + 13 \cdot (-\frac{3}{7})}{11} = \frac{1}{7}$$ $$x_{1} = 1 + 3\cdot\frac{1}{7} - 5 \cdot(-\frac{3}{7}) = \frac{22}{7}$$ So, the solution \(\mathbf{x} = \begin{bmatrix} \frac{22}{7} \\ \frac{1}{7}\\ -\frac{3}{7}\end{bmatrix}\).

Key Concepts

Linear Algebra

Linear algebra is a vital branch of mathematics focused on the study of vectors, vector spaces, linear transformations, and systems of linear equations. It's instrumental in various scientific fields, including engineering, physics, computer science, and economics. Linear algebra provides a framework for solving equations that describe lines, planes, and higher-dimensional figures, which makes it fundamental in understanding and interpreting data, patterns, and structural relationships.

When we talk about systems of linear equations, we are referring to collections of two or more equations with the same set of unknowns. Solving these systems is akin to finding the intersection point of lines, planes, or hyperplanes. Linear algebra offers several methods for solving these systems, and one particularly efficient way is through matrix operations, which is where LU factorization comes into play.

Systems of Linear Equations

Systems of linear equations are sets of equations where each equation is linear, meaning that the variables are raised to the power of one. The equations in a system are linked by shared variables, and the goal is to find the values of these variables that satisfy all the equations simultaneously.

Solving a system of linear equations can be done using various methods, including graphing, substitution, elimination, and matrix-based methods such as LU factorization. The chosen method typically depends on the complexity of the system and the context in which it's applied. In more complex or larger systems, matrix-based methods are often favored for their efficiency and computational power.

Doolittle Algorithm

The Doolittle algorithm is a technique within linear algebra used to decompose a matrix into two triangular matrices: a lower triangular matrix (L) and an upper triangular matrix (U). The LU decomposition is a factorization of a matrix, allowing for the efficient solution of systems of linear equations.

The Doolittle algorithm works by systematically eliminating the variables leading to a set of equations that can be easily solved by substitution. The algorithm proceeds by iteratively computing the entries of L and U. The key advantage of the Doolittle algorithm is that, once the LU factorization is determined, it can be used repeatedly to solve systems with the same coefficient matrix but different constant arrays, saving significant computation in the long run.

Forward Substitution

Forward substitution is a method used to solve a system of linear equations once it has been simplified into a lower triangular matrix through LU factorization. The process begins with the first equation, which involves only the first variable and progresses through the system, solving for one variable at a time.

This method works sequentially from the top of the matrix down, making it a ‘forward’ process. Thus, for a lower triangular matrix L and a vector \(\mathbf{b}\), we seek a solution vector \(\mathbf{y}\) such that \(L\mathbf{y} = \mathbf{b}\). The simplicity of forward substitution lies in the lower triangular structure of the matrix, which makes it straightforward to isolate and solve for each subsequent variable.

Backward Substitution

The counterpart to forward substitution is backward substitution, a technique used to solve a system that has been transformed into an upper triangular matrix. It starts with the last equation, which typically contains only the last variable, and works its way up to the first equation.

Through backward substitution, for an upper triangular matrix U and a vector \(\mathbf{y}\) obtained from forward substitution, the final solution vector \(\mathbf{x}\) is found such that \(U\mathbf{x} = \mathbf{y}\). As with forward substitution, the triangular structure of U greatly simplifies the solution process, with each step only involving back-solving a single variable before progressing to the rest of the system.