Solving Linear Systems: Methods, Errors & Real-World Apps

Core Concepts & Methods

1. Linear Systems: Definitions & Errors

A system of linear equations is written as $A\mathbf{x}=\mathbf{b}$, where:

• $A$ is an $n\times n$ coefficient matrix,
• $\mathbf{x}$ is the unknown vector,
• $\mathbf{b}$ is the right-hand side vector.

Types of Errors

• Round-off error: Due to finite precision in floating-point arithmetic (e.g., $0.1+0.2\ne 0.3$ in binary).
• Truncation error: Approximation errors from iterative methods (e.g., stopping Gauss-Seidel after 10 iterations).
• Condition number ($\kappa (A)$): Measures sensitivity to input errors. A high $\kappa (A)$ (e.g., $\kappa (A)>10^5$) means small changes in $\mathbf{b}$ can drastically alter $\mathbf{x}$.

Worked Example 1: Condition Number Calculation For $A=\left[\begin{array}{cc}1& 1\\ 1& 1.0001\end{array}\right]$, compute $\kappa (A)$. Solution:

1. Eigenvalues: ${\lambda }_1=2.0001$, ${\lambda }_2=0.0001$.
2. $\kappa (A)=\frac{{\lambda }_{\text{max}}}{{\lambda }_{\text{min}}}=\frac{2.0001}{0.0001}=20001$. Interpretation: A 1% error in $\mathbf{b}$ could cause a 200-fold error in $\mathbf{x}$.

2. Direct Methods

A. Gaussian Elimination

• Process: Transform $A$ into upper triangular form via row operations, then back-substitute.
• Pivoting: Partial (swap rows) or complete (swap rows/columns) to avoid division by near-zero.
• Time Complexity: $O(n^3)$.

flowchart TD
    A["Original Matrix A"] --> B["Forward Elimination\n(Create zeros below diagonal)"]
    B --> C["Back Substitution\n(Solve Ux = y)"]

Worked Example 2: Gaussian Elimination Solve: $$\{\begin{array}{l}2x+y+z=8\\ 4x-y+2z=10\\ x+2y-z=1\end{array}$$ Solution:

1. Forward Elimination:
   • $R_2\leftarrow R_2-2R_1$
   • $R_3\leftarrow R_3-\frac{1}{2}{R}_1$ Result: $$\left[\begin{array}{ccc}2& 1& 1\\ 0& -3& 0\\ 0& 1.5& -0.5\end{array}\right]\left[\begin{array}{c}x\\ y\\ z\end{array}\right]=\left[\begin{array}{c}8\\ -6\\ -3\end{array}\right]$$
2. Back Substitution:
   • $z=6$, $y=2$, $x=2$.

B. LU Decomposition

• Factorize $A=LU$, where:
  • $L$: Lower triangular with 1s on diagonal.
  • $U$: Upper triangular.
• Advantage: Reuse $L$ and $U$ for multiple $\mathbf{b}$ vectors (e.g., in optimization).

Worked Example 3: LU Decomposition Factorize: $$A=\left[\begin{array}{ccc}2& 1& 1\\ 4& -1& 2\\ 1& 2& -1\end{array}\right]$$ Solution:

1. Doolittle’s Algorithm:
   • $l_{21}=4/2=2$, $l_{31}=1/2=0.5$.
   • $u_{22}=-1-(1)(2)=-3$, $u_{32}=2-(1)(2)=0$.
   • Final: $$L=\left[\begin{array}{ccc}1& 0& 0\\ 2& 1& 0\\ 0.5& 0& 1\end{array}\right],U=\left[\begin{array}{ccc}2& 1& 1\\ 0& -3& 0\\ 0& 0& -1.5\end{array}\right]$$

C. Cholesky Decomposition

• For symmetric positive-definite matrices ($A=A^T$, all eigenvalues > 0).
• Factorize $A=L{L}^T$, where $L$ is lower triangular.
• Efficiency: Fewer operations than LU ($\frac{2}{3}{n}^3$ vs. $\frac{4}{3}{n}^3$).

Worked Example 4: Cholesky Factorization Factorize: $$A=\left[\begin{array}{ccc}4& 2& 2\\ 2& 2& 1\\ 2& 1& 2\end{array}\right]$$ Solution:

1. Compute $l_{11}=\sqrt{4}=2$.
2. $l_{21}=2/2=1$, $l_{31}=2/2=1$.
3. $l_{22}=\sqrt{2-1^2}=1$, $l_{32}=(1-1)/1=0$.
4. $l_{33}=\sqrt{2-0}=\sqrt{2}$.
5. Final $L$: $$L=\left[\begin{array}{ccc}2& 0& 0\\ 1& 1& 0\\ 1& 0& \sqrt{2}\end{array}\right]$$

3. Iterative Methods

Used for large sparse systems (e.g., finite element analysis in civil engineering).

A. Jacobi Method

• Formula: $$x_i^{(k+1)}=\frac{1}{a_{ii}}\left(b_i-\sum _{j\ne i}{a}_{ij}{x}_j^{(k)}\right)$$
• Convergence: Requires $\rho (D^{-1}(L+U))<1$ (diagonally dominant or symmetric positive-definite).

B. Gauss-Seidel Method

• Improvement: Uses updated $x_i^{(k+1)}$ immediately in the same iteration.
• Formula: $$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)$$
• Convergence: Faster than Jacobi for many problems.

Worked Example 5: Gauss-Seidel for Traffic Flow Model Kathmandu’s ring road traffic as: $$\{\begin{array}{l}4x_1-x_2=1000\\ -x_1+5x_2-x_3=0\\ -x_2+4x_3=1000\end{array}$$ Solution:

1. Initial guess: ${\mathbf{x}}^{(0)}=[0,0,0{]}^T$.
2. Iteration 1:
   • $x_1^{(1)}=1000/4=250$
   • $x_2^{(1)}=(1000+250)/5=250$
   • $x_3^{(1)}=(1000+250)/4=312.5$
3. Iteration 2:
   • $x_1^{(2)}=(1000+250)/4=312.5$
   • $x_2^{(2)}=(1000+312.5)/5=262.5$
   • $x_3^{(2)}=(1000+262.5)/4=315.625$
4. Convergence: After 5 iterations, $\mathbf{x}\approx [333.33,266.67,333.33{]}^T$.

C. Successive Over-Relaxation (SOR)

• Formula: $$x_i^{(k+1)}=(1-\omega )x_i^{(k)}+\frac{\omega }{a_{ii}}\left(b_i-\sum _{j\ne i}{a}_{ij}{x}_j^{(k+1)}\right)$$ where $1<\omega <2$ (optimal $\omega$ speeds convergence).
• Use Case: When Gauss-Seidel is slow (e.g., large grids in PDEs).

Comparison Table:

In the Real World

1. eSewa (Nepal):

   • Problem: Allocating servers to handle peak transaction loads (e.g., Dashain sales).
   • Method: LU decomposition solves the load-balancing matrix $A\mathbf{x}=\mathbf{b}$, where $A$ represents server capacities and $\mathbf{b}$ is demand.
   • Why? Exact solution (LU) ensures no over/under-provisioning.

2. Daraz Order Fulfillment:

   • Problem: Routing delivery trucks to minimize fuel cost (a linear system with constraints).
   • Method: Gauss-Seidel iteratively adjusts routes until the cost function converges to the optimal path.
   • Example: For 3 warehouses and 5 delivery zones, the system solves: $$A\mathbf{x}=\mathbf{b},\text{where }{A}_{ij}=\text{distance cost from warehouse }i\text{ to zone }j.$$

3. NTC Electricity Grid:

   • Problem: Solving Kirchhoff’s laws for voltage/current in the national grid.
   • Method: Cholesky decomposition for symmetric admittance matrices (since grids are lossless and symmetric).
   • Impact: Ensures stable power distribution during peak hours (e.g., winter mornings).

Exam Tip

1. For Direct Methods:

   • Always check if the matrix is symmetric positive-definite before using Cholesky (saves time).
   • Show pivoting steps in Gaussian elimination if the matrix is ill-conditioned.
   • Common Pitfall: Forgetting to normalize rows in LU decomposition (e.g., $l_{21}=a_{21}/a_{11}$).

2. For Iterative Methods:

   • Gauss-Seidel vs. Jacobi: Gauss-Seidel is preferred unless the matrix is strictly diagonally dominant (then Jacobi may converge faster).
   • Stopping Criterion: Use $\Vert {\mathbf{x}}^{(k+1)}-{\mathbf{x}}^{(k)}\Vert <ϵ$ (e.g., $ϵ=10^{-5}$).
   • SOR Trick: If Gauss-Seidel converges slowly, try $\omega =1.25$ first.

3. Error Analysis:

   • Always compute the condition number if asked about stability.
   • For iterative methods, plot the error vs. iteration graph (examiners love this!).

4. Real-World Tie-Ins:

   • If the question mentions "optimization" or "large-scale," assume iterative methods.
   • For "exact solution" or "small systems," use LU/Cholesky.
   • Nepal Context: Relate to traffic (Gauss-Seidel), finance (LU for loan amortization), or energy grids (Cholesky).

Visual Summary:

mindmap
  root((Linear Systems))
    Direct Methods
      Gaussian Elimination
        Pivoting
        Back Substitution
      LU Decomposition
        Doolittle's Algorithm
      Cholesky
        Symmetric Positive-Definite
    Iterative Methods
      Jacobi
        Slow but Simple
      Gauss-Seidel
        Faster, Uses Updated Values
      SOR
        Optimal Relaxation (ω)
    Errors
      Round-off
      Truncation
      Condition Number
    Real-World
      eSewa (LU)
      Daraz (Gauss-Seidel)
      NTC Grid (Cholesky)