Solving Linear Systems: Methods, Errors & Applications

TAKEAWAYS:

• Linear systems are solved via direct methods (exact but computationally expensive) or iterative methods (approximate but efficient for large systems).
• Pivoting (partial/complete) prevents division by zero and improves numerical stability.
• Error analysis (true error, relative error) quantifies solution accuracy.
• Jacobi/Gauss-Seidel methods converge faster for diagonally dominant matrices.
• Real-world uses include loan amortization (banks), traffic flow optimization (Pathao), and portfolio risk modeling (NEPSE).

1. Introduction to Linear Systems

A linear system is a set of linear equations with the same variables. For example: $$\{\begin{array}{l}2x+3y=5\\ 4x-y=1\end{array}$$ Solutions can be:

• Unique solution (lines intersect at one point).
• No solution (parallel lines).
• Infinite solutions (same line).

Matrix Form: $A\mathbf{x}=\mathbf{b}$, where:

• $A$ = coefficient matrix,
• $\mathbf{x}$ = solution vector,
• $\mathbf{b}$ = constant vector.

2. Direct Methods: Gaussian Elimination

Goal: Convert $A\mathbf{x}=\mathbf{b}$ into upper triangular form, then back-substitute.

Steps:

1. Forward Elimination: Use row operations to create zeros below the diagonal.
2. Back Substitution: Solve for variables starting from the last row.

Example 1: Solve

$$\{\begin{array}{l}2x+2y+z=12\\ 3x+2y+2z=8\\ 5x+10y-8z=10\end{array}$$

Solution Trace:

1. Augmented Matrix:

   [2  2  1 | 12]
   [3  2  2 |  8]
   [5 10 -8 | 10]
   

2. Row Reduction:
   • $R_2\leftarrow R_2-\frac{3}{2}{R}_1$
   • $R_3\leftarrow R_3-\frac{5}{2}{R}_1$ → Upper triangular form:

   [2   2   1 | 12]
   [0  -1  0.5 | -2]
   [0   0  -12 | -10]
   

3. Back Substitution:
   • $z=\frac{10}{12}=\frac{5}{6}$
   • $y=2+0.5z=\frac{17}{12}$
   • $x=6-y-0.5z=\frac{5}{3}$

Final Answer: $x=\frac{5}{3}$, $y=\frac{17}{12}$, $z=\frac{5}{6}$.

3. Pivoting Strategies

Problem: Division by small numbers causes numerical instability (round-off errors).

Types:

1. Partial Pivoting: Swap rows to place the largest absolute value in the pivot position.
2. Complete Pivoting: Swap rows and columns for the largest absolute value.

Example 2: Partial Pivoting Solve: $$\{\begin{array}{l}0.0001x+y=1\\ x+y=2\end{array}$$ Without Pivoting: $x\approx 1$ (incorrect due to tiny pivot). With Pivoting: Swap rows → correct solution $x=1$, $y=1$.

flowchart TD
    A["Original System\n(Unstable)"] -->|"Swap Rows"| B["Stable System\nAfter Pivoting"]
    B --> C["Correct Solution\nx=1, y=1"]

4. LU Decomposition

Decompose $A=LU$, where:

• $L$ = lower triangular matrix,
• $U$ = upper triangular matrix.

Advantage: Faster for multiple right-hand sides ($\mathbf{b}$).

Example 3: LU Decomposition For $A=\left[\begin{array}{cc}2& 1\\ 4& 3\end{array}\right]$:

1. $L=\left[\begin{array}{cc}1& 0\\ 2& 1\end{array}\right]$
2. $U=\left[\begin{array}{cc}2& 1\\ 0& 1\end{array}\right]$ → Solve $L\mathbf{y}=\mathbf{b}$, then $U\mathbf{x}=\mathbf{y}$.

5. Iterative Methods: Jacobi and Gauss-Seidel

Used for large sparse systems (e.g., power grids, traffic networks).

Jacobi Method

Update all variables simultaneously: $$x_i^{(k+1)}=\frac{1}{a_{ii}}\left(b_i-\sum _{j\ne i}{a}_{ij}{x}_j^{(k)}\right)$$

Gauss-Seidel Method

Update variables sequentially (uses latest values): $$x_i^{(k+1)}=\frac{1}{a_{ii}}\left(b_i-\sum _{j<i}{a}_{ij}{x}_j^{(k+1)}-\sum _{j>i}{a}_{ij}{x}_j^{(k)}\right)$$

Example 4: Gauss-Seidel for $$\{\begin{array}{l}10x+y+z=12\\ 2x+10y+z=13\\ 2x+2y+10z=14\end{array}$$ Initial Guess: $x_0=y_0=z_0=0$ Iteration 1:

• $x_1=1.2$
• $y_1=1.08$
• $z_1=1.176$ Convergence: After 5 iterations, $x\approx 1.1$, $y\approx 1.1$, $z\approx 1.1$.

6. Error Analysis

Example 5: For $x_{\text{true}}=2$, $x_{\text{approx}}=1.9$:

• True error = $0.1$
• Relative error = $0.05$ (5%).

7. Comparison of Methods

In the Real World

1. Bank Loan Amortization (Nabil Bank, Global IME)

   • Idea Used: Solving linear systems for monthly payments.
   • How: The system $A\mathbf{x}=\mathbf{b}$ models loan principal/interest, where $A$ encodes interest rates and $\mathbf{b}$ is the total repayment. Gaussian elimination solves for monthly installments.
   • Example: A ₹500,000 loan at 8% for 10 years → 120 equations (one per month) solved iteratively.

2. Traffic Route Optimization (Pathao, Daraz Logistics)

   • Idea Used: Least-cost path via linear systems.
   • How: Traffic flow is modeled as $A\mathbf{f}=\mathbf{d}$, where $\mathbf{f}$ = flow rates, $\mathbf{d}$ = demand. Gauss-Seidel finds optimal routes dynamically.
   • Example: Pathao’s algorithm reduces Kathmandu’s Thamel traffic congestion by 15% using real-time system solves.

3. Stock Portfolio Risk (NEPSE, Kantipur Stocks)

   • Idea Used: Portfolio optimization via linear systems.
   • How: The Markowitz model solves $A\mathbf{w}=\mathbf{r}$ to minimize risk for a given return $\mathbf{r}$. LU decomposition speeds up recalculations.
   • Example: A ₹1M portfolio with 5 stocks → 5×5 system solved daily to rebalance holdings.

Exam Tip

1. For Gaussian Elimination:

   • Always show row operations explicitly.
   • Use partial pivoting unless told otherwise.
   • Check for inconsistent systems (e.g., $0=5$).

2. For Iterative Methods:

   • State the convergence criterion (e.g., $|x^{(k+1)}-x^{(k)}|<ϵ$).
   • Gauss-Seidel converges faster if the matrix is diagonally dominant ( $|a_{ii}|>{\sum }_{j\ne i}|a_{ij}|$ ).

3. Error Questions:

   • True error is absolute; relative error is normalized.
   • Example: If the true value is 100 and approximate is 99, relative error = 0.01.

4. Common Pitfalls:

   • Forgetting to swap rows in pivoting → wrong answer.
   • Misapplying back substitution → incorrect variables.
   • LU decomposition requires $A$ to be invertible (check $\det (A)\ne 0$).

Visual Summary:

mindmap
  root((Linear Systems))
    Direct Methods
      Gaussian Elimination
      LU Decomposition
    Iterative Methods
      Jacobi
      Gauss-Seidel
    Error Analysis
      True Error
      Relative Error
    Real-World
      Banks
      Traffic
      Stocks