Brownian Bridge™

1. For a symmetric positive definite (SPD) $n \times n$ matrix $A$ with condition number $\kappa = \lambda_\text{max}/\lambda_\text{min}$ , the conjugate gradient (CG) method satisfies $\|e_k\|_A \leq 2\left(\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}\right)^k \|e_0\|_A$ , while steepest descent satisfies $\|e_{k+1}\|_A \leq \left(\frac{\kappa-1}{\kappa+1}\right)^2 \|e_k\|_A$ . For $\kappa = 400$ , approximately how many iterations does each method require to reduce the A-norm error by a factor of $10^4$ ?

CG: ~44 iterations; steepest descent: ~4600 iterationsCG: ~400 iterations; steepest descent: ~4600 iterationsCG: ~44 iterations; steepest descent: ~44 iterationsCG: ~20 iterations; steepest descent: ~200 iterations

2. In the CG algorithm, the search direction update is $p_{k+1} = r_{k+1} + \beta_k p_k$ with $\beta_k = r_{k+1}^\top r_{k+1} / r_k^\top r_k$ . Which property does this update enforce, and why is it essential?

A-conjugacy: pₖ₊₁ᵀApⱼ = 0 for all j < k+1; ensures CG spans a new subspace dimension at each step without revisiting directionsEuclidean orthogonality: pₖ₊₁ᵀpⱼ = 0 for all j < k+1; prevents the search from doubling backMinimum-residual property: ‖rₖ₊₁‖ is minimised over all possible βSymmetry: pₖ₊₁ is always parallel to rₖ₊₁ regardless of prior history

3. A Crank-Nicolson pricer for a 1D Black-Scholes PDE has $N = 1000$ spatial nodes and runs for $M = 252$ time steps. Each time step requires solving $Ax = b$ where $A$ is tridiagonal. Comparing the Thomas algorithm vs LU factorisation for each solve, and assuming the LU factorisation is recomputed at every step, what are the approximate total flop counts?

Thomas total: 8 × 10³ × 252 ≈ 2×10⁶; LU total: (10³)³/3 × 252 ≈ 8×10¹⁰Thomas total: 10³ × 252 ≈ 2.5×10⁵; LU total: 10³ × 252 ≈ 2.5×10⁵Thomas total: 8 × 252 ≈ 2×10³; LU total: (10³)² × 252 ≈ 2.5×10⁸Thomas total: 8 × 10³ × 252 ≈ 2×10⁶; LU total: 10³ × 252 ≈ 2.5×10⁵

4. The preconditioned CG (PCG) method for $Ax = b$ applies a preconditioner $M \approx A$ . Which statement correctly describes the trade-off in choosing $M$ ?

M should be close to A (so κ(M⁻¹A) ≈ 1) but cheap to apply (M⁻¹r fast to compute); the ideal M = A gives convergence in one step but is as expensive as the original solveM must equal diag(A) to guarantee convergence; any other preconditioner may cause PCG to divergeM should be chosen so that κ(M⁻¹A) = κ(A)/n, reducing the condition number by the matrix sizeThe preconditioner has no effect on the convergence rate, only on numerical stability

5. An analyst applies CG to solve $Ax = b$ where $A$ is a $500 \times 500$ SPD matrix with eigenvalues: 100 copies of $\lambda = 1$ , 100 copies of $\lambda = 2$ , 100 copies of $\lambda = 3$ , 100 copies of $\lambda = 4$ , 100 copies of $\lambda = 100$ . The condition number is $\kappa_2 = 100$ . How many CG iterations are needed to reach machine precision?

Exactly 5 iterations — CG converges in at most as many steps as there are distinct eigenvaluesAbout √100 = 10 iterations — CG convergence depends on √κAbout 100 iterations — CG convergence matches the condition numberAbout 500 iterations — CG always requires n iterations for an n×n system

6. LSQR solves $\min \|Ax - b\|_2$ iteratively without forming $A^\top A$ . Compared to solving the normal equations $A^\top A x = A^\top b$ directly via Cholesky, what is the key numerical advantage of LSQR?

LSQR works with κ₂(A), while Cholesky on the normal equations works with κ₂(A)² = κ₂(AᵀA)LSQR always converges in fewer iterations than the Cholesky solve requiresLSQR requires O(n²) memory while Cholesky on AᵀA requires O(n³)LSQR avoids computing Aᵀ, which is not available in many calibration problems

7. A quant calibrates a 3-factor short-rate model to 50 swap rates using Levenberg-Marquardt. After 20 LM iterations, the residual is $10^{-5}$ and barely decreasing. The stopping tolerance was set to $10^{-12}$ . What is the most likely cause and the correct remediation?

The residual floor is set by market quote noise (~10⁻⁵ bid-ask); tighten the tolerance to match data precision, not machine precisionThe LM algorithm has diverged; restart from a different initial guessThe Jacobian is rank-deficient; add more swap tenors to the calibration set20 iterations is not enough for LM; let it run to 10,000 iterations

8. The Thomas algorithm solves a tridiagonal system $a_i x_{i-1} + b_i x_{i+1} + c_i x_{i+1} = d_i$ in two passes. Under what condition is it numerically stable without pivoting?

When |bᵢ| > |aᵢ| + |cᵢ| for all i (strict diagonal dominance)When the matrix is symmetric positive definiteWhen all off-diagonal entries have the same signWhen the matrix has condition number κ₂ < 100

Quiz: Iterative Solvers for Calibration Problems

Quick Quiz