Eigenvalue Problems & Special Topics: Methods, Applications & Boundary Value Problems

TAKEAWAYS:

• Eigenvalues/vectors are computed via power method (iterative) or Jacobi method (rotation-based), with convergence guarantees for dominant eigenvalues.
• Boundary value problems (BVPs) use the shooting method (ODE solver + boundary correction) or finite differences (discretization of derivatives).
• Partial differential equations (PDEs) model real-world phenomena (heat flow, wave propagation) via finite difference/element methods.
• Special topics like linear interpolation and matrix decomposition (LU, QR) bridge numerical methods to machine learning (e.g., PCA).
• Exam focus: Algorithmic steps (pseudocode), error analysis, and linking methods to applications (e.g., Google’s PageRank uses power iteration).

1. Eigenvalue Problems: Definitions and Methods

Eigenvalues ($\lambda$) and eigenvectors ($v$) satisfy $Av=\lambda v$. Critical for stability analysis, vibrations, and Google’s PageRank.

Key Methods

A. Power Method (for Dominant Eigenvalue)

How it works:

1. Start with a guess vector $v_0$.
2. Iterate: $v_{k+1}=\frac{A{v}_k}{\Vert A{v}_k\Vert }$.
3. Converges to eigenvector of the dominant eigenvalue (largest magnitude).

Example: Find the dominant eigenvalue of $A=\left[\begin{array}{cc}2& 3\\ 5& 4\end{array}\right]$. Steps:

1. Choose $v_0=\left[\begin{array}{c}1\\ 1\end{array}\right]$.
2. Iterate:
   • $v_1=A{v}_0=\left[\begin{array}{c}5\\ 9\end{array}\right]$
   • $v_2=A{v}_1=\left[\begin{array}{c}31\\ 59\end{array}\right]$
   • Normalize: $v_2\approx \left[\begin{array}{c}0.45\\ 0.89\end{array}\right]$.
3. Compute $\lambda \approx \frac{v_2^{T}A{v}_2}{v_2^T{v}_2}=8.9$ (true $\lambda \approx 8.94$).

Real-world tie: Google’s PageRank uses the power method to rank web pages. The matrix $A$ represents link transitions, and the dominant eigenvector gives page importance.

B. Jacobi Method (Rotation-Based)

How it works:

1. Diagonalize $A$ via rotations to eliminate off-diagonal elements.
2. Converges to a diagonal matrix where eigenvalues are the diagonal entries.

Comparison Table:

2. Boundary Value Problems (BVPs)

BVPs specify conditions at both ends of the domain (e.g., $y(a)=\alpha$, $y(b)=\beta$).

A. Shooting Method

How it works:

1. Convert BVP to an initial value problem (IVP) by guessing $y^{\prime }(a)$.
2. Solve IVP numerically (e.g., Heun’s method).
3. Adjust $y^{\prime }(a)$ until boundary condition $y(b)=\beta$ is met.

Example: Solve $y^{\prime \prime }+y=0$ with $y(0)=0$, $y(\pi /2)=1$.

flowchart TD
    A["Guess y'(0) = c"] --> B["Solve IVP: y'' = -y"]
    B --> C["Check y(π/2) ≈ 1?"]
    C -->|"No"| D["Adjust c"]
    C -->|"Yes"| E["Solution found"]

Steps:

1. Guess $y^{\prime }(0)=1$.
2. Use Heun’s method to solve $y^{\prime \prime }=-y$:
   • At $x=\pi /4$, $y\approx 0.707$, $y^{\prime }\approx 0$. . At $x=\pi /2$, $y\approx 0.92$ (not 1).
3. Adjust $c$ iteratively until $y(\pi /2)=1$ (true $c\approx 1.000$).

Real-world tie: NEPSE stock price modeling: BVPs model price trends with boundary conditions (e.g., initial and future price caps). The shooting method predicts equilibrium prices.

B. Finite Difference Method

How it works:

1. Discretize the domain into grid points.
2. Approximate derivatives (e.g., $y^{\prime \prime }\approx \frac{y_{i+1}-2y_i+y_{i-1}}{h^2}$).
3. Solve the resulting linear system (e.g., via Gauss-Seidel).

Example: Solve $y^{\prime \prime }=-y$ with $y(0)=0$, $y(1)=0$ (discretize $h=0.2$). Steps:

1. Finite difference equations: $$\frac{y_{i+1}-2y_i+y_{i-1}}{0.04}=-y_i⟹y_{i+1}-(2+0.04)y_i+y_{i-1}=0.$$
2. Solve the tridiagonal system (Gauss-Seidel):
   • Iterate until convergence (e.g., $y_1\approx 0.1987$).

Real-world tie: NTC’s power grid stability: PDEs model voltage distribution across grids. Finite differences simulate real-time adjustments to prevent blackouts.

3. Partial Differential Equations (PDEs)

PDEs describe spatial + temporal phenomena (e.g., heat equation, wave equation).

A. Finite Difference Method for PDEs

Example: Heat equation $u_t=\alpha u_{xx}$ with $u(0,t)=0$, $u(L,t)=0$.

graph TD
    A["Discretize space (x) and time (t)"] --> B["Approximate u_t and u_xx"]
    B --> C["Form system: u_{i,j+1} = r u_{i-1,j} + (1-2r) u_{i,j} + r u_{i+1,j}"]
    C --> D["Solve iteratively"]

Steps:

1. Let $r=\alpha \Delta t/(\Delta x{)}^2$.
2. For $u_{i,j+1}$, use: $$u_{i,j+1}=r{u}_{i-1,j}+(1-2r)u_{i,j}+r{u}_{i+1,j}.$$
3. Apply boundary conditions (e.g., $u_{0,j}=0$).

Real-world tie: Pathao’s dynamic pricing: PDEs model rider demand across zones. Finite differences predict surge pricing in real time.

4. Special Topics

A. Linear Interpolation

How it works: Estimate $f(x)$ between two points $(x_0,f_0)$ and $(x_1,f_1)$: $$f(x)\approx f_0+\frac{f_1-f_0}{x_1-x_0}(x-x_0).$$ Example: Estimate $f(0.3)$ for $f(0)=1$, $f(0.4)=1.3$. Solution: $$f(0.3)\approx 1+\frac{1.3-1}{0.4}\times 0.3=\mathrm{1.15.}$$

Real-world tie: eSewa’s transaction fees: Linear interpolation estimates fees between two transaction amounts (e.g., ₹100 → 2%, ₹500 → 1.5%).

B. LU and QR Decomposition

• LU: Factor $A=LU$ for solving $Ax=b$ (forward/back substitution).
• QR: Factor $A=QR$ for least-squares problems (used in machine learning).

Example: LU decomposition of $A=\left[\begin{array}{cc}2& 3\\ 5& 4\end{array}\right]$. Steps:

1. $L=\left[\begin{array}{cc}1& 0\\ 2.5& 1\end{array}\right]$, $U=\left[\begin{array}{cc}2& 3\\ 0& -3.5\end{array}\right]$.
2. Solve $LUx=b$ via substitution.

In the Real World

1. Google PageRank (Power Method):

   • What it uses: Power iteration to compute the dominant eigenvector of a link-transition matrix.
   • How: Each webpage is a node; links are matrix entries. The eigenvector ranks pages by importance.

2. NEPSE Stock Analysis (Boundary Value Problems):

   • What it uses: Shooting method to model price trends with boundary conditions (e.g., historical low/high).
   • How: Convert price BVP into an IVP, solve numerically, and adjust initial guesses to match market caps.

3. Pathao’s Surge Pricing (PDEs):

   • What it uses: Heat equation PDEs to model rider demand across geographic zones.
   • How: Finite differences simulate demand diffusion, predicting price surges in high-demand areas.

4. NTC Power Grid (Finite Differences):

   • What it uses: Finite difference discretization of Laplace’s equation for voltage distribution.
   • How: Solves $u_{xx}+u_{yy}=0$ to stabilize grid voltages in real time.

Exam Tip

1. Algorithmic Questions:

   • For the power method, show iteration steps and convergence proof (Rayleigh quotient).
   • For the shooting method, write pseudocode with boundary correction logic.

2. Theoretical Questions:

   • Define eigenvalue problems as $Av=\lambda v$ and contrast with IVPs/BVPs.
   • For PDEs, state the finite difference approximation (e.g., $u_t\approx \frac{u^{n+1}-u^n}{\Delta t}$).

3. Application Links:

   • Tie eigenvalues to Google PageRank or structural analysis.
   • Link BVPs to stock modeling or traffic flow (e.g., Kathmandu’s congestion as a BVP).

4. Common Pitfalls:

   • Power method: Forget normalization → divergence.
   • Shooting method: Poor initial guess → slow convergence.
   • PDEs: Stability condition ($r\le 0.5$) for explicit methods.

Visual Summary:

mindmap
  root((Eigenvalue Problems & Special Topics))
    Power Method
      Iterative
      Dominant Eigenvalue
      Google PageRank
    Jacobi Method
      Rotation
      All Eigenvalues
    Boundary Value Problems
      Shooting Method
        IVP + Correction
        NEPSE Stocks
      Finite Differences
        Discretization
        NTC Power Grid
    PDEs
      Heat Equation
      Finite Differences
      Pathao Pricing
    Special Topics
      Linear Interpolation
        eSewa Fees
      LU/QR Decomposition
        Solving Ax = b