Fixed-point Iteration §

Intuition: a contraction mapping “shrinks” distances. If $g$ brings every point closer to $x^*$ by a factor of at least $\rho < 1$, then repeated application must converge. The rate $\rho$ determines how many iterations are needed: to reach precision $\varepsilon$, we need $t > \log(\varepsilon / \|x_0 - x^*\|) / \log \rho$.

Example: the fixed point of $g(x) = \cos(x)$ is $x^* \approx 0.739085$. Since $|g'(x^*)| = |\sin(x^*)| \approx 0.674 < 1$, convergence is linear with rate $\rho \approx 0.674$. To reach $10^{-6}$ precision from $x_0 = 1$: $t > \log(10^{-6})/\log(0.674) \approx 37$ iterations.

When the contraction fails: if $\|g'(x^*)\| \geq 1$, the iteration diverges or oscillates. One can sometimes find a different map $g_{\text{alt}}$ with the same fixed point but $\|g_{\text{alt}}'(x^*)\| < 1$ (e.g., damped iteration $g_d(x) = (1-\alpha)x + \alpha g(x)$ for $\alpha \in (0,1)$).

Example problem:

Why quadratic: the fixed-point map is $g(x) = x - f(x)/f'(x)$. At the root, $g'(x^*) = 0$ (the linear term vanishes), so the error is dominated by the quadratic term. This means the number of correct digits roughly doubles each step, making Newton’s method extremely fast once close to the solution.

Example: finding $\sqrt{2}$ (i.e., the root of $f(x) = x^2 - 2$). Starting from $x_0 = 1$:

• $x_1 = 1 - (1-2)/2 = 1.5$
• $x_2 = 1.5 - (2.25-2)/3 = 1.4167$
• $x_3 \approx 1.41421356$ (8 correct digits)

Three steps to 8 digits: the hallmark of quadratic convergence.

Connection to optimization: minimizing $f(\theta)$ is equivalent to finding the root of $\nabla f(\theta) = 0$. Newton’s method for optimization uses the Hessian: $\theta_{t+1} = \theta_t - [\nabla^2 f(\theta_t)]^{-1} \nabla f(\theta_t)$. The cost per step is $O(d^3)$ (Hessian inversion), making it impractical for high-dimensional problems. Gradient descent (see Gradient Descent) replaces the Hessian with a scalar learning rate, trading convergence speed for per-step cost.

Example problem:

The contraction condition: the Jacobian of $g$ is $g'(\theta) = I - \eta \nabla^2 f(\theta)$. For $g$ to be a contraction, we need $\|I - \eta \nabla^2 f\| < 1$, which holds when $0 < \eta < 2/L$ (where $L$ is the largest eigenvalue of the Hessian, i.e., the Lipschitz constant of the gradient).

Why the upper bound matters: if $\eta > 2/L$, the iteration overshoots the minimum and diverges. If $\eta$ is too small, convergence is slow (the contraction factor $\rho \approx 1 - \eta\mu$ is close to 1). The optimal choice $\eta = 1/L$ gives the fastest linear convergence for strongly convex problems.

Connection to the contraction framework: this is exactly the contraction mapping theorem applied to $g(\theta) = \theta - \eta \nabla f(\theta)$. The rate $\rho = 1 - \eta\mu$ (for $\mu$-strongly convex $f$) determines the number of iterations to reach precision $\varepsilon$: $t > \log(\varepsilon) / \log(\rho)$.

See Gradient Descent for the full treatment of learning rates, momentum, and stochastic variants.

Example problem:

Consider the iteration $x_{t+1} = x_t - 0.1(x_t^2 - 4)$ (Newton’s method for $\sqrt{4}$ with a damping factor). Starting from $x_0 = 1$, compute $x_1$ and $x_2$, and determine whether the iteration is converging.