Solution of Non-Linear Equations

The problem is to find the real zeros of a nonlinear function f, that is, values of x for which f(x)=0. Typically f could be sin, cos, log, exp or combinations of these. One of the difficulties is that we may not know in advance that solutions exist or whether there is a unique solution. For example, e^x-x=0 has no solution, e^x-x-1=0 has a repeated root and $\sin x-\frac{1}{x}=0$ has an infinite number of solutions.

The methods we shall consider are all iterative and are included in the general formulation

$$x_{n+1}=g(x_n),\quad n=0,1,\ldots ,$$

where x=g(x) is some rearrangement of f(x)=0. This problem was analysed using infinite Taylor expansions in m242; we now examine it more rigorously with the help of Taylor's Theorem.

The problems we want to answer are:

• Does the problem have a solution?
• Is the solution unique?
• Is the iteration well-defined? For example $x_{n+1}=\frac{x_n}{x_n-1}$ is not defined if x_n=1.
• Does the iteration converge to a limit $\alpha$, say?
• Is $\alpha$ the required answer?
• How quickly does the method converge?

In our earlier study of the convergence of x_n+1=g(x_n) we discovered that the criterion for convergence to $\alpha$, where $\alpha =g(\alpha )$ was that |g'(x)|<1 for values of x near to $\alpha$. We shall replace this derivative condition by a slightly less restrictive one, which does not require g to be differentiable. We can see how it arises however by replacing the derivative $\frac{dg}{dx}$ by the finite difference ratio $\frac{g(x_1)-g(x_2)}{x_1-x_2}$, so that $\vert g'(x)\vert\leq L$ is replaced by $\left\vert \frac{g(x_1)-g(x_2)}{x_1-x_2}\right\vert \leq L$, or $\vert g(x_1)-g(x_2)\vert\leq L\vert x_1-x_2\vert$. This condition simply says that the slope of the chord joining (x₁,g(x₁)) and (x₂,g(x₂)) is less than L in modulus. If g is differentiable, the derivative condition is recovered by taking the limit as $x_2\to x_1$.

Definition 3451

g is Lipschitz with constant L on the interval [a,b] if there exists L>0 such that

$$\vert g(x_1)-g(x_2)\vert\leq L\vert x_1-x_2\vert$$

for all $x_1,x_2\in [a,b]$.

What are the implications of this condition? Is a continuous function necessarily Lipschitz? No, because the function g given by $g(x)=\sqrt{1-x},~x\in [0,1]$ is continuous, but no single value can be found for L for a Lipschitz condition to hold.

Conversely, if g is Lipschitz on [a,b] then it is continuous on [a,b], since for any point $x\in [a,b]$

$$\left\vert \kern.05em g(x+h)-g(x) \kern.05em \right\vert\leq L\left\vert \kern.05em x+h-x \kern.05em \right\vert=Lh,$$

which tends to zero as $h\to 0$, hence establishing continuity.

That a function which is Lipschitz is not necessarily differentiable is demonstrated by the counter example

$$g(x)=\left\{ \begin{array} {ll}x & 0\leq x\leq 1\\ x^2 & 1<x<2\end{array} \right.$$

in which g is not differentiable at x=1.

How would we find a Lipschitz constant for this example? The full procedure would be to find an upper bound for

$$\frac{\left\vert \kern.05em g(x_1)-g(x_2) \kern.05em \right\vert}{\left\vert \kern.05em x_1-x_2 \kern.05em \right\vert}$$

for all pairs of values x₁,x₂. There are three cases:

• $x_1,x_2\in [0,1]$. Here

  $$\frac{\left\vert \kern.05em g(x_1)-g(x_2) \kern.05em \right\vert}{\left\vert \kern.05em x_1-x_2 \kern.05em \right\vert}=1.$$

• $x_1\in [0,1],~x_2\in (1,2]$. Here

  $$\frac{\left\vert \kern.05em g(x_1)-g(x_2) \kern.05em \right\... ...x_2^2}{x_1-x_2}\leq \frac{x_2^2-x_1^2}{x_2-x_1}=x_2+x_1\leq 3.$$

• $x_1,x_2 \in (1,2]$. Here

  $$\frac{\left\vert \kern.05em g(x_1)-g(x_2) \kern.05em \right\... ....05em \right\vert}=\frac{x_1^2-x_2^2}{x_1-x_2}= x_1+x_2\leq 4.$$

The value 4 turns out to be the least possible for a Lipschitz constant. Any greater value would also be a perfectly good Lipschitz constant.

If g is a differentiable function in [a,b], we can apply the Mean Value Theorem to obtain

$$\left\vert \kern.05em g(x_1)-g(x_2) \kern.05em \right\vert=\... ...\kern.05em g'(\xi ) \kern.05em \right\vert,\quad \xi \in (a,b)$$

for all $x_1,x_2\in [a,b]$, and so we can take the Lipschitz constant as

$$L=\max _{x\in [a,b]}\left\vert \kern.05em g'(x) \kern.05em \right\vert.$$

Altogether

g differentiable $\Rightarrow$ g Lipschitz $\Rightarrow$g continuous,

but not conversely.

Now we are ready to start looking at the existence and uniqueness of solutions and whether convergence to the solution is achieved. We shall assume that g is defined in an interval [a,b]. For the equation x=g(x) to have a solution in this interval, the line y=x and the curve y=g(x) must intersect. Figure shows two situations where no solution exists.

  

Figure: The Case of No Solutions

Figure shows two cases where solutions exist, but we do not try to analyse these because the iterations may escape into places where g is undefined.

  

Figure: Escaping Iterations

Figure shows a situation where a solution does exist, and where the iteration cannot escape. We suspect from this graph that continuity of g and the contraction property

$$x\in [a,b]~\Rightarrow~ g(x)\in [a,b],$$

will guarantee existence of a solution and a convergent iteration. If we write [a,b]=I, the contraction property is more concisely written as $g(I)\subseteq I$, where $g(I)=\{ g(x):x\in I\}$. We prove the result in the following lemma.

  

Figure: The Convergent Case

Lemma 3500

Let g be a continuous function on a closed interval I=[a,b] and $g(I)\subseteq I$. Then there exists $\alpha \in I$ such that $\alpha =g(\alpha )$. ($\alpha$ is called a fixed point of g.)

What about uniqueness? How can we avoid a situation such as that shown in Figure ? Clearly we need $\left\vert \kern.05em g'(x) \kern.05em \right\vert\leq 1$ if g is differentiable, but the Lipschitz condition on g provides a less restrictive way of ensuring this, as the following lemma shows.

  

Figure: Multiple Solutions

Lemma 3510

Let g be as in Lemma 1 and also satisfy the Lipschitz condition

$$\left\vert \kern.05em g(x_1)-g(x_2) \kern.05em \right\vert\leq L\left\vert \kern.05em x_1-x_2 \kern.05em \right\vert$$

for all $x_1,x_2\in I$, with L<1. Then g has a unique fixed point in I.

Corollary 3515

If g is differentiable in I the Lipschitz condition may be replaced by $\left\vert \kern.05em g'(x) \kern.05em \right\vert\leq L<1$ for all $x\in I$.

Note that this result is much easier to work with than the Lipschitz condition. In the example we looked at before, where the function was not differentiable at a single point, we can use the derivative for the interval excluding the point of nondifferentiability and check that case 1 (x₁ and x₂ in different parts of the interval) does not require a larger constant. In that example, where

$$g(x)=\left\{ \begin{array} {ll}x & 0\leq x\leq 1\\ x^2 & 1<x<2\end{array} \right.,$$

g'(x)=1 in (0,1) and g'(x)=2x in (1,2), so over the union of these two intervals we can take L=4. With $x_1\in [0,1]$ and $x_2\in (1,2]$ the greatest chord slope of 3 occurs when x₁=1 and x₂=2.

It turns out that the conditions of the lemmas are sufficient for convergence of the functional iteration, as the following theorem shows.

Theorem 3538

Let g be a function continuous on the closed finite interval I=[a,b], $g(I)\subseteq I$ and $\left\vert \kern.05em g(x_1)-g(x_2) \kern.05em \right\vert\leq L\left\vert \kern.05em x_1-x_2 \kern.05em \right\vert$ for all $x_1,x_2\in I$ with I<1. Then for any $x_0\in I$ the sequence defined by $x_{n+1}=g(x_n),~n=0,1,\ldots$ converges to the unique fixed point of g in I.

If we know that a solution exists, we can prove a simpler theorem with a more restricted form of Lipschitz condition.

Theorem 3551

If x=g(x) has a root $\alpha$ and g satisfies the condition

$$\left\vert \kern.05em g(x)-g(\alpha ) \kern.05em \right\vert\leq L\left\vert \kern.05em x-\alpha \kern.05em \right\vert$$

in the interval $I=(\alpha -\rho ,\alpha +\rho )$ and L<1, then for any $x_0\in I$

• all iterates $x_n=g(x_{n-1}),~n=1,2,\ldots$ are in I,
• the iterates converge to $\alpha$,
• $\alpha$ is unique in I.

The proof is left as an exercise. Note that a more useful way of describing the interval is $I=\{ x:\left\vert \kern.05em x-\alpha \kern.05em \right\vert<\rho \}$ which shows that it is centred on $\alpha$.

Corollary 3556

If g is differentiable, we may take $L=\max _{x\in I}\left\vert \kern.05em g'(x) \kern.05em \right\vert$.

Note that the Lipschitz condition is actually less restrictive here in the sense that g simply has to lie between the lines $y=\pm L(x-\alpha )$, so the slope of g may exceed 1 away from $\alpha$, as can be seen in Figure .

  

Figure: Lipschitz Restriction