Last modified: April 06, 2021

This article is written in: 🇺🇸

Relaxation Method

The relaxation method, commonly referred to as the fixed-point iteration method, is an iterative approach used to find solutions (roots) to nonlinear equations of the form $f\left(x\right)=0$. Instead of directly solving for the root, the method involves rewriting the original equation in the form:

$$x=g\left(x\right),$$

where $g\left(x\right)$ is a suitable function defined such that a fixed point of $g\left(x\right)$ corresponds to a root of $f\left(x\right)$. That is, if $\alpha$ is a root of $f\left(x\right)$, then $g\left(\alpha \right)=\alpha$.

This approach transforms a root-finding problem into a fixed-point problem. If the iteration defined by:

$$x_{n+1}=g\left(x_n\right)$$

converges, it will do so to the fixed point $\alpha$, which is also the root of the original equation. Relaxation methods can sometimes converge faster than bracket-based methods (like bisection), but they do not come with guaranteed convergence from any starting point. Convergence depends on the properties of the chosen $g\left(x\right)$ and the initial guess $x_0$.

Conceptual Illustration:

Imagine the line $y=x$ and the curve $y=g\left(x\right)$. A fixed point $\alpha$ is a point where the two curves intersect:

The iteration takes a guess $x_n$, and then maps it to $x_{n+1}=g\left(x_n\right)$. If these iterations hone in on the intersection, the sequence converges to the root $\alpha$.

Mathematical Formulation

Starting Point:

Given a nonlinear equation:

$$f\left(x\right)=0$$ we want to find $\alpha$ such that $f\left(\alpha \right)=0$.

Rewriting the Equation:

We rearrange the equation into a fixed-point form:

$$x=g\left(x\right)$$

There can be infinitely many ways to rewrite $f\left(x\right)=0$ as $x=g\left(x\right)$. A suitable $g\left(x\right)$ must be chosen to ensure convergence.

Once we have:

$$x_{n+1}=g\left(x_n\right)$$

if the iteration converges, it must converge to $\alpha$ satisfying $\alpha =g\left(\alpha \right)$.

Convergence Conditions:

A key sufficient condition for convergence is that:

$$|g^{\prime }\left(x\right)|<1\text{in the neighborhood of}\alpha .$$

If the derivative of $g\left(x\right)$ in the region around the fixed point is less than 1 in absolute value, the iteration will typically converge.

Derivation

I. From Root to Fixed Point Problem:

Suppose we have $f\left(x\right)=0$. We isolate $x$ on one side:

$$x=g\left(x\right)$$

If $\alpha$ solves $f\left(\alpha \right)=0$, then $g\left(\alpha \right)=\alpha$.

II. Fixed-Point Iteration:

Define a sequence $x_n$ by choosing an initial guess $x_0$ and applying:

$$x_{n+1}=g\left(x_n\right).$$

III. Convergence Insight:

Consider a point $\alpha$ such that $g\left(\alpha \right)=\alpha$. If we expand $g$ near $\alpha$:

$$g(\alpha +h)\approx g\left(\alpha \right)+g^{\prime }\left(\alpha \right)h=\alpha +g^{\prime }\left(\alpha \right)h$$

If $|g^{\prime }\left(\alpha \right)|<1$, then iterating this process will reduce the error $|h|$ at each step, leading to convergence of $x_n$ to $\alpha$.

In essence, the choice of $g\left(x\right)$ greatly influences the convergence behavior. A poorly chosen $g\left(x\right)$ may lead to divergence or very slow convergence.

Algorithm Steps

Input:

• A function $f\left(x\right)$ and a corresponding $g\left(x\right)$ such that $f\left(x\right)=0$ is equivalent to $x=g\left(x\right)$.
• An initial guess $x_0$.
• A tolerance $ϵ>0$ or a maximum number of iterations $n_{max}$.

Initialization:

Set iteration counter $n=0$.

Iteration:

I. Compute the next approximation:

$$x_{n+1}=g\left(x_n\right)$$

II. Check convergence:

• If $|x_{n+1}-x_n|<ϵ$ or $|f\left(x_{n+1}\right)|<ϵ$, stop.
• If $n>n_{max}$, stop.

III. Otherwise, set $n=n+1$ and repeat from step I.

Output:

• Approximate root: $x_{n+1}$.
• Number of iterations performed.

Example

Given Equation:

$$x^2-3x+2=0$$

This equation factors as $(x-1)(x-2)=0$, so the roots are $x=1$ and $x=2$.

Choose a Fixed-Point Form:

We can rearrange the equation to:

$$x=\frac{x^2+2}{3}$$

Thus:

$$g\left(x\right)=\frac{x^2+2}{3}$$

Initial Guess:

Let $x_0=0$.

Iteration 1:

$$x_1=g\left(x_0\right)=g\left(0\right)=\frac{0^2+2}{3}=\frac{2}{3}\approx 0.6667$$

Iteration 2:

$$x_2=g\left(x_1\right)=g\left(0.6667\right)=\frac{(0.6667{)}^2+2}{3}=\frac{0.4444+2}{3}\approx \frac{2.4444}{3}=0.8148$$

Iteration 3:

$$x_3=g\left(x_2\right)=g\left(0.8148\right)=\frac{(0.8148{)}^2+2}{3}=\frac{0.6639+2}{3}\approx \frac{2.6639}{3}=0.8880$$

Repeating this process, we observe $x_n$ approaching one of the roots (in this case, it will move closer to $x=1$, depending on the behavior of $g\left(x\right)$ near that root).

Advantages

1. Flexible formulation allows the relaxation method to work by simply rewriting the equation in fixed-point form $x=g\left(x\right)$ and iterating, making it conceptually straightforward.
2. Potentially faster than bisection, the method can converge more quickly when $g\left(x\right)$ is well-chosen, particularly if $|g^{\prime }\left(x\right)|<1$ near the root.
3. Broad applicability makes the method suitable for nonlinear equations that do not require derivatives, although convergence often depends on the properties of $g\left(x\right)$.
4. Straightforward implementation is achieved by directly iterating $x_{n+1}=g\left(x_n\right)$, provided an appropriate $g\left(x\right)$ is identified.

Limitations

1. No guaranteed convergence means the method may fail if $|g^{\prime }\left(x\right)|\ge 1$ in the vicinity of the root, unlike bracketing methods that ensure convergence under certain conditions.
2. Sensitive to the choice of $g\left(x\right)$, as some transformations of $f\left(x\right)=0$ into $x=g\left(x\right)$ promote convergence while others lead to divergence.
3. Initial guess importance highlights that a poor starting point can result in divergence or very slow convergence, making the method less robust in such cases.
4. Dependent on continuity and differentiability, with standard convergence theory requiring $g\left(x\right)$ to be continuous and differentiable, limiting its applicability for problems that do not meet these conditions.