6.1. Methods of Solving Systems of Linear Equations

These methods yield the solution in a finite number of steps.

Direct methods are designed to find an exact solution to systems of linear equations in a fixed number of steps. This is beneficial as it provides precise answers quickly for smaller systems.

Think of direct methods like following a recipe that outlines each step clearly. Just as you would follow the recipe to bake a cake exactly as it says, direct methods guide you step-by-step to find the solution.

Gaussian Elimination Method

Steps:

1. Convert the system into an upper triangular form (forward elimination).
2. Solve using back-substitution.

Advantages:

• Simple and systematic
• Suitable for small and medium-sized systems

Limitations:

• Computationally expensive for large systems
• Sensitive to rounding errors

The Gaussian elimination method involves two stages. First, you manipulate the equations to form an upper triangular matrix (where all entries below the main diagonal are zero). This step is known as forward elimination. Next, you solve for the variables starting from the last equation up to the first, which is called back-substitution. This method works best for smaller systems since it can become inefficient and less accurate with larger ones due to rounding errors.

Imagine organizing books on a shelf from top to bottom. You first stack books step-by-step (forward elimination) and then start reading from the bottom of the stack to find the answers (back-substitution).

Gauss-Jordan Elimination

An extended version of Gaussian Elimination where the matrix is reduced to row echelon form (diagonal matrix or identity matrix).

Steps:

1. Perform forward elimination as in Gaussian elimination.
2. Perform backward elimination to make all elements except pivots zero.
3. Read the solutions directly.

Gauss-Jordan elimination takes Gaussian elimination a step further by simplifying the matrix to the identity form, where every leading coefficient is '1', and all other entries in those columns are '0'. This allows you to directly read the solutions from the matrix, making it a more streamlined approach compared to Gaussian elimination.

Think of it like sorting receipts in a wallet. First, you align the receipts so that each denomination is in order. Then, you remove any clutter so that only the main receipts are visible, letting you see your expenses at a glance.

LU Decomposition Method

LU Decomposition expresses matrix 𝐴 as a product of two matrices: 𝐴 = 𝐿 ⋅ 𝑈 Where:

• 𝐿 is a lower triangular matrix
• 𝑈 is an upper triangular matrix Then solve:

1. 𝐿 ⋅ 𝑌 = 𝐵 using forward substitution
2. 𝑈 ⋅ 𝑋 = 𝑌 using back substitution

Useful for:

• Solving multiple systems with the same coefficient matrix but different constant vectors.

The LU decomposition method splits the coefficient matrix into two triangular matrices, L and U. By solving for Y first using the lower triangular matrix L (forward substitution), and then solving for X using the upper triangular matrix U (back substitution), this method becomes efficient for systems where the coefficient matrix remains the same across different equations. This is especially helpful when the system is large.

Consider this approach like making a smoothie with multiple ingredients. First, you blend the fruit (L), then mix in the yogurt and ice (U), creating a delicious, uniform smoothie. If you use the same method with different fruit combinations, you can still enjoy diverse flavors!

Iterative Methods

Used when direct methods are inefficient, especially for large sparse systems.

Iterative methods are processes where solutions are approximated over several iterations rather than calculated directly in one go. These methods are particularly advantageous for large systems where direct methods may take too long or require too much computational power.

Think of iterative methods like jogging to reach a destination. You start running, evaluate how far you've come, then adjust your path as needed, continually refining your approach until you reach your goal.

Gauss-Jacobi Method

Each equation is solved for a variable in terms of others, and values are updated in parallel.

Formula: 𝑛 1 (𝑘+1) (𝑘) 𝑥 = (𝑏 − ∑ 𝑎 𝑥 ) 𝑖 𝑎 𝑖 𝑖𝑗 𝑗 𝑖𝑖 𝑗=1,𝑗≠𝑖

Convergence Criteria:

• The matrix should be diagonally dominant: 𝑛 |𝑎 |> ∑ |𝑎 | 𝑖𝑖 𝑖𝑗 𝑗=1,𝑗≠𝑖

In the Gauss-Jacobi method, each variable is solved in isolation based on an earlier guess of the other variables’ values. All updated values are then recalculated concurrently. This method is effective under the condition of diagonal dominance, ensuring the matrix is stable for convergence.

Imagine a group project where each member handles a separate section. Each person updates their part of the report independently, then you compile everyone's contributions. If someone takes too long, it can slow the project's overall progress, just like a matrix that isn't diagonally dominant would.

Gauss-Seidel Method

Like Gauss-Jacobi, but updates each variable as soon as its new value is available.

Formula: 𝑖−1 1 (𝑘+1) (𝑘+1) (𝑘) 𝑥 = (𝑏 −∑𝑎 𝑥 − ∑ 𝑎 𝑥 ) 𝑖 𝑎 𝑖 𝑖𝑗 𝑗 𝑖𝑗 𝑗 𝑖𝑖 𝑗=1 𝑗=𝑖+1

Faster convergence compared to Jacobi if the system satisfies the necessary conditions.

The Gauss-Seidel method is similar to the Gauss-Jacobi method, but with a crucial difference: it updates each variable immediately after solving it, which can lead to faster convergence in many cases. This is particularly effective when the conditions for convergence are met, such as having a diagonally dominant matrix.

It's like a team making a presentation where members share their progress as they complete their part. Instead of waiting for everyone to finish before sharing, updates are shared immediately, leading to a more cohesive and faster project completion.

--