Numerical Methods (Algebra)

⚡ Key Takeaways

Numerical Methods (Algebra) are systematic algorithms for finding approximate solutions to algebraic equations — single nonlinear equations $f(x)=0$ , and systems of linear equations $A\mathbf{x}=\mathbf{b}$ — when exact closed-form solutions are unavailable or impractical. Key result: iterative schemes (bisection, Newton, Gauss–Seidel) converge to solutions at quantifiable rates governed by derivatives, spectral radii, and condition numbers. Used everywhere computers solve equations: engineering, physics, finance, machine learning. Foundations laid by Newton, Raphson, Gauss, and Jacobi (17th–19th c.), formalized with the rise of digital computing (1940s–present).

💡 The Core Insight

Almost every numerical algebra method replaces a hard problem with a sequence of easy problems whose limit is the answer. We trade exactness for an iteration $x_{n+1} = g(x_n)$ that we can actually compute, then ask two questions: (1) Does it converge? (governed by contraction / spectral radius), and (2) How fast? (linear, quadratic, superlinear). Every error bound ultimately compares the produced approximation against the true solution through a derivative, a Lipschitz constant, or a condition number.

DefinitionRoot-Finding Problem

Given a continuous function $f:\mathbb{R}\to\mathbb{R}$ (or $f:\mathbb{R}^n\to\mathbb{R}^n$ ), find $x^*$ such that

1

\quad f(x^*)=0.

Derivation hint: This is the definitional statement; $x^*$ is called a root or zero of $f$ . A point $x^*$ is a simple root if $f(x^*)=0$ and $f'(x^*)\neq 0$ ; it is a root of multiplicity $m$ if $f(x^*)=f'(x^*)=\cdots=f^{(m-1)}(x^*)=0$ but $f^{(m)}(x^*)\neq 0$ .

DefinitionLinear System Problem

Given $A\in\mathbb{R}^{n\times n}$ nonsingular and $\mathbf{b}\in\mathbb{R}^n$ , find $\mathbf{x}\in\mathbb{R}^n$ such that

2

\quad A\mathbf{x}=\mathbf{b},\qquad \mathbf{x}=A^{-1}\mathbf{b}.

Derivation hint: Nonsingularity ( $\det A\neq 0$ ) guarantees a unique solution; in practice we never compute $A^{-1}$ explicitly — it is slower and less accurate than factorization.

DefinitionOrder of Convergence

A sequence $x_n\to x^*$ converges with order $p\ge 1$ and asymptotic constant $C>0$ if

3

\quad \lim_{n\to\infty}\frac{|x_{n+1}-x^*|}{|x_n-x^*|^p}=C.

Derivation hint: $p=1$ (with $C<1$ ) is linear, $p=2$ is quadratic (error roughly squares each step), $1<p<2$ is superlinear.

DefinitionCondition Number of a Matrix

For an induced norm $\|\cdot\|$ , the condition number of nonsingular $A$ is

4

\quad \kappa(A)=\|A\|\,\|A^{-1}\|\ \ge 1.

Derivation hint: Perturb $A\mathbf{x}=\mathbf{b}$ to $A(\mathbf{x}+\delta\mathbf{x})=\mathbf{b}+\delta\mathbf{b}$ ; subtracting gives $\delta\mathbf{x}=A^{-1}\delta\mathbf{b}$ , and bounding norms yields the relative error amplification $\tfrac{\|\delta\mathbf{x}\|}{\|\mathbf{x}\|}\le\kappa(A)\tfrac{\|\delta\mathbf{b}\|}{\|\mathbf{b}\|}$ .

TheoremNewton's Method — Quadratic Convergence

Let $f\in C^2$ near a simple root $x^*$ . The iteration

5

\quad x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}

Derivation hint: Linearize $f$ about $x_n$ via Taylor: $f(x)\approx f(x_n)+f'(x_n)(x-x_n)$ ; set the linear model to zero and solve for $x$ . converges quadratically for $x_0$ sufficiently close to $x^*$ , with the error obeying

6

\quad e_{n+1}=\frac{f''(\xi_n)}{2f'(x_n)}\,e_n^2,\qquad e_n:=x_n-x^*.

Derivation hint: Taylor-expand $f(x^*)=0$ about $x_n$ to second order with remainder $\xi_n$ between $x_n$ and $x^*$ , then substitute into the iteration formula.

TheoremConvergence of Stationary Iterative Methods

For a splitting $A=M-N$ giving the iteration $M\mathbf{x}_{k+1}=N\mathbf{x}_k+\mathbf{b}$ , i.e. $\mathbf{x}_{k+1}=T\mathbf{x}_k+\mathbf{c}$ with $T=M^{-1}N$ , the iteration converges for every starting vector if and only if the spectral radius satisfies

7

\quad \rho(T)=\max_i|\lambda_i(T)|<1.

Derivation hint: The error $\mathbf{e}_k=\mathbf{x}_k-\mathbf{x}^*$ satisfies $\mathbf{e}_k=T^k\mathbf{e}_0$ ; $T^k\to 0$ iff $\rho(T)<1$ (via the Jordan form).

ProofNewton's Quadratic Convergence

Step 1. Let $x^*$ be a simple root, so $f(x^*)=0$ and $f'(x^*)\neq0$ . Define the error $e_n=x_n-x^*$ .

Step 2. Taylor-expand $f$ about $x_n$ and evaluate at $x^*$ :

8

\quad 0=f(x^*)=f(x_n)+f'(x_n)(x^*-x_n)+\tfrac12 f''(\xi_n)(x^*-x_n)^2,

Derivation hint: Lagrange remainder form, with $\xi_n$ strictly between $x_n$ and $x^*$ .

Step 3. Note $x^*-x_n=-e_n$ . Divide the whole equation by $f'(x_n)$ :

9

\quad 0=\frac{f(x_n)}{f'(x_n)}-e_n+\frac{f''(\xi_n)}{2f'(x_n)}e_n^2.

Derivation hint: Substitute $(x^*-x_n)=-e_n$ and $(x^*-x_n)^2=e_n^2$ .

Step 4. The Newton iteration gives $x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}$ , so $e_{n+1}=e_n-\frac{f(x_n)}{f'(x_n)}$ . Substituting $\frac{f(x_n)}{f'(x_n)}$ from Step 3:

10

\quad e_{n+1}=e_n-\Big(e_n-\frac{f''(\xi_n)}{2f'(x_n)}e_n^2\Big)=\frac{f''(\xi_n)}{2f'(x_n)}e_n^2.

Derivation hint: Direct algebraic cancellation of $e_n$ .

Step 5. Since $f'$ is continuous and nonzero at $x^*$ , near $x^*$ we have $\left|\frac{f''(\xi_n)}{2f'(x_n)}\right|\le M$ for some constant. Thus $|e_{n+1}|\le M|e_n|^2$ , establishing $p=2$ . If $|e_0|<1/M$ , the errors shrink to zero. $\blacksquare$

∎

ProofSpectral-Radius Convergence Criterion

Step 1. The exact solution is a fixed point: $\mathbf{x}^*=T\mathbf{x}^*+\mathbf{c}$ .

Step 2. Subtract from the iteration $\mathbf{x}_{k+1}=T\mathbf{x}_k+\mathbf{c}$ to get the error recursion $\mathbf{e}_{k+1}=T\mathbf{e}_k$ , hence $\mathbf{e}_k=T^k\mathbf{e}_0$ .

Step 3. ( $\Leftarrow$ ) If $\rho(T)<1$ , then $T^k\to 0$ (Gelfand: $\|T^k\|^{1/k}\to\rho(T)<1$ forces $\|T^k\|\to 0$ ), so $\mathbf{e}_k\to\mathbf{0}$ for any $\mathbf{e}_0$ .

Step 4. ( $\Rightarrow$ ) If $\rho(T)\ge 1$ , pick an eigenvector $\mathbf{v}$ with $|\lambda|\ge1$ and set $\mathbf{e}_0=\mathbf{v}$ ; then $\mathbf{e}_k=\lambda^k\mathbf{v}$ does not vanish. $\blacksquare$

∎

mathematician · Carl Friedrich Gauss | 1777–1855

Gauss systematized the elimination procedure now bearing his name while computing the orbit of the asteroid Ceres (1801) — a least-squares fit requiring the solution of normal equations. His private work on iterative refinement of linear systems, communicated in an 1823 letter to his student Gerling, anticipated the Gauss–Seidel method by decades. Gauss's blend of theoretical depth and relentless hand-computation epitomizes the numerical tradition: he reportedly remarked that he found the iterative method's gradual self-correction "agreeable" enough to do "even while half-asleep."

🧠 Intuition

Think of root-finding as trapping or chasing a target. Bisection traps the root in a shrinking interval — slow but utterly reliable, like halving a search range; you always know the root is inside. Newton chases by sliding down the tangent line — blazingly fast (errors square!) but it can shoot off to infinity or oscillate if you start far away or hit a flat spot ( $f'\approx 0$ ). The secant method is Newton without the derivative, using a chord through two points; slightly slower (order $\approx 1.618$ , the golden ratio) but cheaper. For linear systems, direct methods (Gaussian elimination, LU) are like solving a maze with a guaranteed map: finitely many steps, exact in perfect arithmetic. Iterative methods (Jacobi, Gauss–Seidel, conjugate gradient) are like repeatedly smoothing a guess toward the answer — invaluable for huge sparse systems where storing the full factorization is impossible. The condition number $\kappa(A)$ tells you how much a tiny smudge on your data can blur the answer: $\kappa=10^6$ means you can lose 6 digits of accuracy no matter how clever your algorithm is.

Figure

Newton's method: the tangent line at

x_n

slides to the next iterate

x_{n+1}

, rapidly homing in on the root

x^*

.

ExampleNewton's Method for

\sqrt{2}

Given: Solve $f(x)=x^2-2=0$ , so $f'(x)=2x$ . Start at $x_0=1.5$ . The iteration $[5]$ becomes

11

\quad x_{n+1}=x_n-\frac{x_n^2-2}{2x_n}=\frac{1}{2}\Big(x_n+\frac{2}{x_n}\Big).

Derivation hint: Substitute $f$ and $f'$ into Newton's formula and simplify; this is the ancient "Babylonian" square-root iteration.

Steps:

$x_0=1.5$
$x_1=\tfrac12(1.5+2/1.5)=\tfrac12(1.5+1.33333)=1.416667$
$x_2=\tfrac12(1.416667+2/1.416667)=1.4142157$
$x_3=1.41421356237$

The true value is $\sqrt2=1.41421356237\ldots$ — by $x_3$ we have 11 correct digits. Note the digit count roughly doubles each step (quadratic convergence): $\approx1,\,3,\,6,\,11$ .

Answer: $\boxed{\sqrt{2}\approx 1.41421356237}$ (dimensionless).

ExampleGauss–Seidel on a

2\times2

System

Given: Solve

12

\quad \begin{cases} 4x_1 + x_2 = 5,\\ x_1 + 3x_2 = 6.\end{cases}

Derivation hint: The matrix is strictly diagonally dominant ( $|4|>|1|$ , $|3|>|1|$ ), guaranteeing Gauss–Seidel convergence. Solve each equation for its diagonal unknown and use the latest values:

13

\quad x_1^{(k+1)}=\frac{5-x_2^{(k)}}{4},\qquad x_2^{(k+1)}=\frac{6-x_1^{(k+1)}}{3}.

Derivation hint: This is the splitting $A=(D+L)-U$ with forward substitution using updated components immediately.

Steps (start $x^{(0)}=(0,0)$ ):

$x_1^{(1)}=(5-0)/4=1.2500$ , $x_2^{(1)}=(6-1.25)/3=1.5833$
$x_1^{(2)}=(5-1.5833)/4=0.8542$ , $x_2^{(2)}=(6-0.8542)/3=1.7153$
$x_1^{(3)}=(5-1.7153)/4=0.8212$ , $x_2^{(3)}=(6-0.8212)/3=1.7263$
$x_1^{(4)}=0.8184$ , $x_2^{(4)}=1.7272$

The exact solution is $x_1=9/11=0.8\overline{18}$ , $x_2=19/11=1.7\overline{27}$ .

Answer: $\boxed{x_1\approx 0.8182,\ x_2\approx 1.7273}$ (dimensionless).

⚠️ Common mistake

"Newton always converges, and faster is always better." False on both counts. Newton's quadratic convergence is only local — it requires a sufficiently good starting guess. From a poor $x_0$ , Newton can diverge, cycle, or jump to a different root. It also fails or slows dramatically when $f'(x^*)=0$ (multiple roots), degrading to linear convergence. Meanwhile bisection, though only linear, is globally convergent on any sign-changing interval. The robust practitioner brackets first (bisection) then accelerates (Newton): this hybrid is Brent's method.

⚠️ Common mistake

"A small residual means a small error." For an approximate solution $\hat{\mathbf{x}}$ of $A\mathbf{x}=\mathbf{b}$ , the residual $\mathbf{r}=\mathbf{b}-A\hat{\mathbf{x}}$ can be tiny even when the actual error $\|\hat{\mathbf{x}}-\mathbf{x}^*\|$ is enormous — precisely when $A$ is ill-conditioned. The bound is $\frac{\|\hat{\mathbf{x}}-\mathbf{x}^*\|}{\|\mathbf{x}^*\|}\le\kappa(A)\frac{\|\mathbf{r}\|}{\|\mathbf{b}\|}$ . A small residual only guarantees a small error when $\kappa(A)$ is modest.

CounterexampleNewton Diverging

Consider $f(x)=\arctan(x)$ , with unique root $x^*=0$ . Newton's iteration is $x_{n+1}=x_n-(1+x_n^2)\arctan(x_n)$ . For starting values $|x_0|>x_c\approx 1.3917$ (where the iteration map has magnitude $>1$ ), the iterates grow without bound, oscillating with ever-larger amplitude — despite $f$ being smooth, monotone, and having exactly one root. This shows local quadratic convergence gives no global guarantee.

connection

Numerical algebra sits at the crossroads of analysis and computation. Root-finding via Fixed-Point Iteration generalizes Newton and underlies the Banach Fixed-Point Theorem contraction analysis. The error formula relies on Taylor's Theorem. Linear-system theory connects to LU Decomposition, Cholesky Decomposition, and QR Decomposition, while iterative solvers lead into Krylov Subspace Methods and the celebrated Conjugate Gradient Method. Conditioning and stability draw on Matrix Norms and the Singular Value Decomposition (since $\kappa_2(A)=\sigma_{\max}/\sigma_{\min}$ ). The eigenvalue problem links to The QR Algorithm and Power Iteration. Multidimensional root-finding ( $f:\mathbb{R}^n\to\mathbb{R}^n$ ) requires the Jacobian Matrix in place of $f'$ .

🔬 Where this appears

⏳ History

- c. 1800 BCE — Babylon: Clay tablets show the iterative square-root method

x_{n+1}=\tfrac12(x_n+a/x_n)

, the special case of Newton for

f(x)=x^2-a

.

- c. 200 BCE — China: The Nine Chapters on the Mathematical Art describes fangcheng, an elimination procedure equivalent to Gaussian elimination on linear systems.

- 1669 — Isaac Newton: In De analysi, applies an iterative linearization to solve

x^3-2x-5=0

, the germ of "Newton's method," though stated only for polynomials and without explicit derivatives.

- 1690 — Joseph Raphson: Publishes a simplified, general iterative formula; the method is now jointly credited as Newton–Raphson.

- 1810 — Carl Friedrich Gauss: Refines systematic elimination for least-squares orbit determination (Ceres, 1801; method published in Theoria Motus).

- 1823 — Gauss (letter to Gerling): Describes the iterative refinement that becomes the Gauss–Seidel method.

- 1845 — Carl Gustav Jacob Jacobi: Develops the Jacobi iteration and an eigenvalue rotation method.

- 1874 — Philipp Ludwig von Seidel: Publishes the successive-displacement iterative method.

- 1947 — von Neumann & Goldstine: Found rigorous rounding-error analysis of Gaussian elimination, launching modern numerical stability theory; 1952 Hestenes & Stiefel introduce the conjugate gradient method.

open-problem

Several deep issues remain active or subtle. Multiple roots destroy quadratic convergence (Newton degrades to linear with rate $1-1/m$ ); remedies like the modified Newton step $x_{n+1}=x_n-m f/f'$ require knowing $m$ in advance. Global root-finding in many variables is genuinely hard — no algorithm reliably finds all solutions of a general nonlinear system, connecting to questions in real algebraic geometry and homotopy continuation. For linear solvers, the optimal preconditioner for a given sparse matrix is problem-dependent and the subject of ongoing research; finding preconditioners that make $\kappa$ uniformly bounded as problem size grows is open for many PDE classes. Finally, rounding-error accumulation in extremely large or extended computations, and the design of provably backward-stable algorithms for all matrix structures, remains an active frontier — as does developing numerically robust methods for the eigenvalue problem of nonsymmetric and defective matrices, where eigenvectors can be arbitrarily ill-conditioned.

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also