Problem Set 3: Gaussian Elimination and A=LU

Problem Set 3: Gaussian Elimination and \(A=LU\)#

Part A: Gaussian Elimination and Row Reduction#

Problem 1#

Solve the following system using Gaussian elimination with back substitution:

\[\begin{split} \begin{cases} 2x_1 + 3x_2 - x_3 = 7 \\ x_1 - 2x_2 + 2x_3 = -1 \\ 3x_1 + x_2 + x_3 = 8 \end{cases} \end{split}\]

Problem 2#

Use Gaussian elimination to solve:

\[\begin{split} \begin{cases} x_1 + 2x_2 + x_3 = 4 \\ 2x_1 + x_2 - x_3 = 1 \\ x_1 - x_2 + 2x_3 = 3 \end{cases} \end{split}\]

Problem 3#

Solve the system by reducing the augmented matrix to row echelon form:

\[\begin{split} \left[\begin{array}{ccc|c} 1 & -1 & 2 & 5 \\ 3 & 1 & 4 & 13 \\ 2 & -1 & 3 & 8 \end{array}\right] \end{split}\]

Problem 4#

Determine if the following system has a unique solution, infinitely many solutions, or no solution:

\[\begin{split} \begin{cases} 2x_1 + 4x_2 - 2x_3 = 6 \\ x_1 + 2x_2 - x_3 = 3 \\ 3x_1 + 6x_2 - 3x_3 = 9 \end{cases} \end{split}\]

Problem 5#

Solve using Gaussian elimination (reduce to reduced row echelon form):

\[\begin{split} \begin{cases} x_1 + x_2 + x_3 = 6 \\ 2x_1 + 3x_2 + x_3 = 11 \\ x_1 + 2x_2 + 2x_3 = 9 \end{cases} \end{split}\]

Problem 6#

Find the solution to the homogeneous system:

\[\begin{split} \begin{cases} x_1 + 2x_2 - 3x_3 + x_4 = 0 \\ 2x_1 + 4x_2 - 5x_3 + 3x_4 = 0 \\ x_1 + 2x_2 - 4x_3 - x_4 = 0 \end{cases} \end{split}\]

Problem 7#

Solve the system with parameters. For what value(s) of \(k\) does the system have: a) A unique solution
b) No solution
c) Infinitely many solutions

\[\begin{split} \begin{cases} x_1 + x_2 + x_3 = 3 \\ 2x_1 + 3x_2 + x_3 = 7 \\ x_1 + 2x_2 + kx_3 = k + 1 \end{cases} \end{split}\]

Problem 8#

Use row operations to solve:

\[\begin{split} \left[\begin{array}{cccc|c} 2 & -1 & 3 & 1 & 8 \\ 1 & 2 & -1 & 2 & 3 \\ 3 & 1 & 2 & -1 & 7 \\ 1 & -1 & 4 & -2 & 5 \end{array}\right] \end{split}\]

Part B: LU Factorization#

Problem 9#

Find the LU factorization of the matrix:

\[\begin{split} A = \begin{bmatrix} 2 & 4 & -2 \\ 1 & 5 & 2 \\ 3 & -1 & 1 \end{bmatrix} \end{split}\]

Problem 10#

Decompose the following matrix into LU form:

\[\begin{split} A = \begin{bmatrix} 1 & 3 & 2 \\ 2 & 8 & 6 \\ 4 & 11 & 13 \end{bmatrix} \end{split}\]

Problem 11#

Find the LU factorization (without pivoting) of:

\[\begin{split} A = \begin{bmatrix} 3 & -3 & 6 \\ -6 & 7 & -13 \\ 3 & -4 & 10 \end{bmatrix} \end{split}\]

Problem 12#

Given the matrix below, determine if LU factorization (without pivoting) is possible. If so, find L and U:

\[\begin{split} A = \begin{bmatrix} 0 & 2 & 1 \\ 1 & 3 & 2 \\ 2 & 1 & 4 \end{bmatrix} \end{split}\]

Problem 13#

Find the LU factorization of:

\[\begin{split} A = \begin{bmatrix} 4 & 2 & 1 \\ 8 & 6 & 4 \\ 12 & 8 & 13 \end{bmatrix} \end{split}\]

Problem 14#

Use LU factorization to solve the system \(Ax = b\) where:

\[\begin{split} A = \begin{bmatrix} 2 & 1 & 0 \\ 4 & 3 & 1 \\ 6 & 6 & 4 \end{bmatrix}, \quad b = \begin{bmatrix} 3 \\ 8 \\ 16 \end{bmatrix} \end{split}\]

Steps: a) Find the LU factorization of A
b) Solve \(Ly = b\) by forward substitution
c) Solve \(Ux = y\) by back substitution

Problem 15#

Given that \(A = LU\) where:

\[\begin{split} L = \begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ -1 & 3 & 1 \end{bmatrix}, \quad U = \begin{bmatrix} 3 & 6 & -3 \\ 0 & -2 & 4 \\ 0 & 0 & 5 \end{bmatrix} \end{split}\]

Solve \(Ax = b\) for \(b = \begin{bmatrix} 9 \\ 4 \\ 15 \end{bmatrix}\)

Part C: Mixed Applications#

Problem 16#

For the matrix \(A = \begin{bmatrix} 1 & 2 & 1 \\ 3 & 8 & 7 \\ 2 & 7 & 9 \end{bmatrix}\):

a) Find the LU factorization
b) Use the factorization to solve \(Ax = b\) for \(b = \begin{bmatrix} 4 \\ 18 \\ 18 \end{bmatrix}\)
c) Verify your answer by direct substitution

Problem 17#

Consider the system:

\[\begin{split} \begin{cases} x_1 + 2x_2 + 3x_3 = 14 \\ 2x_1 + 5x_2 + 8x_3 = 36 \\ x_1 + 3x_2 + 6x_3 = 25 \end{cases} \end{split}\]

Solve this system using: a) Gaussian elimination
b) LU factorization
Compare your results.

Problem 18#

Given the coefficient matrix:

\[\begin{split} A = \begin{bmatrix} 2 & -1 & 1 \\ 4 & 1 & 2 \\ 6 & -2 & 5 \end{bmatrix} \end{split}\]

a) Perform Gaussian elimination to find the row echelon form
b) Find the LU factorization
c) Solve \(Ax = b\) for \(b = \begin{bmatrix} 2 \\ 9 \\ 10 \end{bmatrix}\) using both methods

Problem 19#

Analyze the following system for consistency:

\[\begin{split} \begin{cases} 2x_1 + 3x_2 - x_3 + 4x_4 = 7 \\ x_1 + 2x_2 + x_3 - x_4 = 3 \\ 3x_1 + 5x_2 + 2x_3 - 5x_4 = 10 \\ x_1 + x_2 - 2x_3 + 3x_4 = 1 \end{cases} \end{split}\]

If consistent, find the general solution.

Problem 20#

Challenge Problem: For the matrix:

\[\begin{split} A = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & 2 & 3 & 4 \\ 1 & 3 & 6 & 10 \\ 1 & 4 & 10 & 20 \end{bmatrix} \end{split}\]

a) Find the LU factorization
b) Use the factorization to solve \(Ax = e_2\) (where \(e_2\) is the second standard basis vector)
c) What do you notice about the structure of matrix A? (Hint: Consider the pattern in the entries)

Note: Remember to show all row operations clearly, maintain proper fraction arithmetic, and verify your final answers when possible. For LU factorizations, always check that \(LU = A\).