TMV035 Analysis and Linear Algebra A, 2005

LECTURE 3.2

In this lecture we present the bisection algorithm in its general setting and use it to prove two theorems: Bolzano’s Theorem and the Intermediate Value Theorem. We then present another algorithm, the fixed point iteration, and use it to prove the Contraction Mapping Theorem.

This covers AMBS Ch 16, 18, 19. Skip on first reading: 16.2, 16.3, 18.6–7, 19.4–6, 19.10–11. Note: the figures are missing, I did not have time to do them yet.

1. The bisection algorithm

AMBS Ch 16. We have now defined the real numbers R and we have seen that Lipschitz continuous functions can be defined on R. So from now on we consider real-valued functions of a real variable, f : R → R, or f : [a, b] → R where [a, b] is an interval of real numbers.

We first consider equations of the form f(x) = 0.

Theorem. (Bolzano’s theorem) Assume that f : [a, b] → R is Lipschitz continuous and that f(a)f(b) < 0 (opposite signs). Then there is a real number x̄ ∈ [a, b] such that f(x̄) = 0. If f is strictly monotone (increasing or decreasing) then x̄ is unique (the only such number).

The proof is a constructive proof, in contrast to, for example, a proof by contradiction. This means that the proof describes how the number x̄ is constructed. It is organized in the following four steps:

(1) an algorithm which produces an approximating sequence {x_{i}};

(2) a proof that {x_{i}} is a Cauchy sequence so that we get a real number (decimal expansion)

x̄ = lim_{i→∞} x_{i}.

(3) a proof that x̄ solves the equation: {f(x_{i})} is also a Cauchy sequence and f(x̄) =

lim_{i→∞} f(x_{i}) = 0;

(4) a proof that x̄ is unique (in the case of strictly monotone function).

Remember these steps, we will use the same kind of proof many times. The first three steps give the existence of a solution. The last step gives uniqueness of the solution of the equation f(x) = 0. One important consequence of uniqueness is that all approximating sequences will converge to the same solution x̄. That is, the solution is independent of the choice of algorithm or approximating sequence (independent of the construction).

Proof. Step 1. We use the bisection algorithm with starting points a and b, see AMBS pp. 188–189. Step 2. We obtain two sequences {x_{i}}_{i=0}^{∞} and {X_{i}}_{i=0}^{∞} with

(1)  |x_{i} − X_{i}| ≤ (b − a)2^{−i},
(2)  |x_{i} − x_{j}| ≤ (b − a)2^{−i}, j > i,
(3)  |X_{i} − X_{j}| ≤ (b − a)2^{−i}, j > i.

The inequalities (2) and (3) mean that x_{i} and X_{i} are Cauchy sequences: |x_{i}−x_{j}| → 0, |X_{i}−X_{j}| → 0 as i, j → ∞, and we get decimal expansions (real numbers)

x̄ = lim_{i→∞} x_{i}, X̄ = lim_{i→∞} X_{i}.

The inequality (1) means that the decimal expansions are the same:

x̄ = lim_{i→∞} x_{i} = lim_{i→∞} X_{i} = X̄.

Step 3. The Lipschitz continuity of f gives

|f(x_{i}) − f(x_{j})| ≤ L|x_{i} − x_{j}| ≤ L(b − a)2^{−i}, j > i,

Date: September 19, 2005, Stig Larsson, Mathematical Sciences, Chalmers University of Technology.

which means that f(x_{i}) is a Cauchy sequence, |f(x_{i}) − f(x_{j})| → 0 as i, j → ∞. It gives a decimal expansion (real number) which we denote f(x̄):

f(x̄) = lim_{i→∞} f(x_{i}).

We must show that this is equal to 0. To do this we note that the distance between f(x_{i}) and 0 is less than or equal to the distance between f(x_{i}) and f(X_{i}). This is because f(x_{i}) and f(X_{i}) have opposite signs. For example, if f(x_{i}) < 0 and f(X_{i}) > 0:

|f(x_{i}) − 0| = −f(x_{i}) < −f(x_{i}) + f(X_{i}) = |f(x_{i}) − f(X_{i})|.

In any case:

|f(x_{i}) − 0| ≤ |f(x_{i}) − f(X_{i})| ≤ L|x_{i} − X_{i}| ≤ L(b − a)2^{−i} → 0,

where we also used the Lipschitz condition and (1). This means that

lim_{i→∞} f(x_{i}) = 0,

or in other words f(x̄) = 0.

Step 4. Assume now that f is strictly increasing. (The case of decreasing function can be handled in a similar way.) This means that x < y implies f(x) < f(y). Assume also that we have two different solutions, i.e., x̄_{1} < x̄_{2} with f(x̄_{1}) = f(x̄_{2}) = 0. But this is a contradiction to the strict monotonicity. Therefore, there is only one solution. □

Figure 1. Non-monotone function with three roots.

Figure 2. Monotone function with unique root.

We now consider equations of the form f(x) = y.

Theorem. (The Intermediate Value Theorem) If f : [a, b] → R is Lipschitz continuous and the real number y is between f(a) and f(b), then there is a real number x̄ ∈ [a, b] such that f(x̄) = y. If f is strictly monotone, then x̄ is unique.

The theorem says that a Lipschitz continuous function takes all values between its end-point values. A discontinuous function may skip some value.

Proof. If f(a) = f(b) then y = f(a) = f(b) and we can choose x̄ = a or x̄ = b. Otherwise we apply Bolzano’s theorem to the function F (x) = f(x) − y. Clearly, F : [a, b] → R is Lipschitz with the same constant as f, and F (a)F (b) < 0 because y is between f(a) and f(b). Also, F is strictly monotone if f is strictly monotone. The conclusion now follows from Bolzano’s theorem: there is x̄ such that F (x̄) = f(x̄) − y = 0, and it is unique if f is strictly monotone. □

Figure 3. Equation f(x) = y with multiple solutions.

Figure 4. Equation f(x) = y with unique solution.

Figure 5. The discontinuous function skips the value y.

2. Inverse function

(This is not discussed in AMBS.) Assume now that the function in the Intermediate Value Theorem is strictly increasing. (Decreasing functions can be discussed in the same way.) Let us write A = f(a), B = f(b). We note the following consequences of the theorem.

The function takes all values y in the interval [A, B] and it takes no values outside [A, B]. This means that the range of the function is exactly R_{f} = [A, B].

The equation f(x) = y has a unique solution x for any y ∈ [a, b]. Since x is unique, this defines a function y ↦ x. More precisely, we can define a function

g : [A, B] → R

x = g(y), where x is the unique solution of f(x) = y.

(Remember that a function must have a unique value for each element of the domain of definition.) We then say that f is invertible (“inverterbar”) and the function g is called the the inverse of f. It is denoted g = f^{−1},

f^{−1} : [A, B] → R

x = f^{−1}(y), where x is the unique solution of f(x) = y.

Note that

D_{f^{−1}} = R_{f} = [A, B], R_{f^{−1}} = D_{f} = [a, b],
f(f^{−1}(y)) = y, y ∈ [A, B]; f^{−1}(f(x)) = x, x ∈ [a, b].

Of course, we may interchange the roles of x and y and write y = f^{−1}(x), x ∈ [A, B].

Warning: f^{−1} is pronounced “f inverse”, and it is not the same as “f to the minus one” (f)^{−1} = 1/f. It is confusing that “inverse” and “raised to −1” are written in the same way, but it is a tradition in mathematics, and we have to live with it and be careful when we use it.

We have now proved the following.

Theorem. A strictly monotone function is invertible.

Example. The function f : [−2, 2] → R, f(x) = x^{2}, is not invertible because the equation x^{2} = y has two solutions x = ±\sqrt{y}. In the next section we shall see that f becomes invertible if we restrict its domain of definition to the nonnegative numbers.

3. The function \sqrt{x}

AMBS18.1–3. We introduce the square root function and investigate its properties.

The function f : [0, b] → R, f(x) = x^{2}, is strictly increasing because 0 ≤ x < y implies x−y < 0 and x + y > 0 so that x^{2} − y^{2} = (x − y)(x + y) < 0. Hence the equation x^{2} = y has a unique solution x = \sqrt{y} for any y ∈ [0, b^{2}]. Therefore, f is invertible with f^{−1}(y) = \sqrt{y}.

This can be done for any b, the uniqueness implies that the bisection algorithm gives the same result no matter what starting points a = 0 and b > 0 we use. So the function f : R_{+} → R, f(x) = x^{2}, is invertible with inverse f^{−1} : R_{+} → R, f^{−1}(x) = \sqrt{x}. Note: D^{√} = R_{+} and R^{√} = R_{+}.

Warning: f^{−1}(x) = \sqrt{x} is not the same as (f)^{−1}(x) = (f(x))^{−2} = x^{−2} = 1/x^{2} although they are written in the same way.

Figure 6. The function y = \sqrt{x}.

Since x^{2} = a and y^{2} = b implies (xy)^{2} = ab and (x/y)^{2} = a/b, we conclude

\sqrt{ab} = \sqrt{a}\sqrt{b}, \sqrt{\frac{a}{b}} = \begin{matrix}√ & \overline{a} \\ √ & \overline{b} \end{matrix}.

We now investigate the Lipschitz continuity of \sqrt{x}:

|\sqrt{x} − \sqrt{y}| = \{multiply by the “conjugate expression” \sqrt{x} + \sqrt{y}\}

= |\frac{(\sqrt{x} − \sqrt{y})(\sqrt{x} + \sqrt{y})}{\sqrt{x} + \sqrt{y}}| = |\frac{x − y}{\sqrt{x} + \sqrt{y}} | \{by the conjugate rule\}

= \frac{1}{\sqrt{x} + \sqrt{y}} |x − y| ≤ \frac{1}{\sqrt{δ} + \sqrt{δ}} |x − y| = \frac{1}{2\sqrt{δ}} |x − y| for x, y ≥ δ.

We conclude that the square root function is Lipschitz continuous with constant L = 1/(2\sqrt{δ}) on any interval of the form [δ, ∞) with δ > 0. That is, on any interval that stays way from 0. But it is not Lipschitz on its whole domain of definition R_{+} = [0, ∞). This is clear from the previous calculation, but is also seen in the graph where the slope is infinite at 0.

4. The power function x^{r} for r ∈ Q

In AMBS 18.4–5 the power function (“potensfunktionen”) x^{r} with rational exponent r = p/q is defined by uniquely solving the equation y^{q} = x^{p} for x ≥ 0. This is possible because the function f : R_{+} → R, f(x) = x^{p}, is strictly increasing. Can you prove this? Hint:

x^{p} − y^{p} = (x − y)(x^{p−1} + x^{p−2}y + ⋯ + xy^{p−2} + y^{p−1}).

The unique solution is denoted y = x^{p/q} = x^{r}. It satisfies

x^{r}x^{s} = x^{r+s}, \frac{x^{r}}{x^{s}} = x^{r−s}, r, s ∈ Q.

We shall define x^{r} with real exponent r ∈ R later in ALA-b.

5. The fixed point iteration

AMBS 19.1–3.

An algebraic equation can be written in two equivalent ways (meaning that they have the same solutions).

1. f(x) = 0. A solution x̄ is called a root of f or a zero of f (“nollställe till f”).

Example. The function f(x) = x^{2} − 2 has two roots x̄_{1} = \sqrt{2}, x̄_{2} = −\sqrt{2}.

Algorithm: For equations of this form we have the bisection algorithm.

2. x = g(x). A solution x̄ is called a fixed point (“fixpunkt”) of g. The equation is called a fixed point equation.

Example. The function g(x) = 2/x has two fixed points, x̄_{1} = \sqrt{2}, x̄_{2} = −\sqrt{2}, because ±\sqrt{2} =

±\begin{matrix}\sqrt{2} & \sqrt{2} \\ √ & \overline{2} \end{matrix} = \frac{1}{±\sqrt{2}}.

Algorithm: a natural algorithm for a fixed point equation is to to choose a starting point x_{0} and then compute x_{i} according to x_{i} = g(x_{i−1}). This is called the fixed point iteration. We hope that the sequence x_{i} converges to a fixed point. This works sometimes and sometimes not.

Example. With g(x) = x/2 + 1/x and x_{0} = 1 we get x_{1} = g(x_{0}) = 3/2, x_{2} = 15/12 and so on. This is easy to try in Matlab:

>> format long
>> x=1
>> x=x/2+1/x
>> x=x/2+1/x
>> x=x/2+1/x
>> x=x/2+1/x

Do this now!! Does it converge? Do you recognize a decimal expansion?

Example. With g(x) = 2/x and x_{0} = 1 we get x_{1} = g(x_{0}) = 2, x_{2} = 1, x_{3} = 2, i.e., we get the sequence {1, 2, 1, 2, … } which is divergent.

Figure 7. The functions y = g(x) and y = x.

Note that the equations x^{2} − 2 = 0, x = x/2 + 1/x, and x = 2/x are equivalent (multiply the last two equations by x to see this). We can rewrite equations between the two forms in many ways. For example, x = g(x) can be written as x − g(x) = 0. On the other hand, f(x) = 0 can be written x = x + αf(x) where α or α(x) is any nonzero number or function. The challenge is to find a “good” choice of α so that the fixed point iteration is convergent. Later, when we discuss Newton’s method, we shall find an optimal choice of α. In fact, x = x/2 + 1/x is obtained from x^{2} − 2 = 0 by using α(x) = −1/(2x) and we will learn why this is a good choice.

So when does the fixed point iteration work? It turns out that one important condition is that the Lipschitz constant L = L_{g} of g is strictly smaller than 1. More precisely, we shall assume that g is Lipschitz on an interval I with constant L < 1, i.e.,

|g(x) − g(y)| ≤ L|x − y| for x, y ∈ I and with L < 1.

Such a function is called a contraction mapping (or just contraction). Note that the distance between the images g(x) and g(y) is smaller than the distance between x and y.

Example. For g(x) = 2/x we have

|g(x) − g(y)| = 2|\frac{y − x}{xy}| = \frac{2}{|x| |y|} |x − y| ≤ \frac{1}{2}|x − y|, ∀x, y ≥ 2,

so that g is a contraction with L = 1/2 on I = [2, ∞). Note that we used that z = xy ∈ [4, ∞) so that \frac{2}{|x| |y|} = \frac{2}{z} ∈ [0, \frac{1}{2}].

Example. For g(x) = x/2 + 1/x we have

|g(x) − g(y)| = |\frac{x − y}{2} + \frac{y − x}{xy}| = |\frac{1}{2} − \frac{1}{xy} | |x − y|.

Now let us consider x, y ∈ [1, 2] for example. Write z = xy. Then z ∈ [1, 4] and we get \frac{1}{2} − \frac{1}{xy} = \frac{1}{2} − \frac{1}{z} ∈ [−\frac{1}{2}, \frac{1}{4}] with absolute value |\frac{1}{2} − \frac{1}{xy} | ≤ \frac{1}{2}. Therefore

|g(x) − g(y)| = |\frac{1}{2} − \frac{1}{xy} | |x − y| ≤ \frac{1}{2} |x − y|, ∀x, y ∈ [1, 2],

so that g is a contraction with L = 1/2 on I = [1, 2].

6. The contraction mapping theorem

AMBS 19.7–8

Remember that the bisection algorithm leads to Bolzano’s theorem. The fixed point iteration also leads to a theorem.

Remember that a closed interval I is an interval that contains its endpoints (if it has any). A closed interval can be of the following types:

I = [a, b] (closed and bounded interval)

I = [a, ∞), I = (−∞, b], I = (∞, ∞) = R, (closed and unbounded intervals)

Theorem. (The Contraction Mapping Theorem) Assume that I is a closed interval and that g : I → I is a contraction mapping. Then g has a unique fixed point x̄ ∈ I. The fixed point is obtained as the limit of the fixed point iteration, x_{i} = g(x_{i−1}), for any starting point x_{0} ∈ I.

It is important that the target set I is the same as the domain of definition, g : I → I; it guarantees that the sequence does not jump out of the interval I where g is a contraction. It is also important that I is closed; it guarantees that x̄ = lim x_{i} ∈ I.

Proof. The proof follows the four steps of a constructive proof that we mentioned before.

Step 1. An algorithm: we use the fixed point iteration. Take an arbitrary point x_{0} ∈ I and compute x_{i} = g(x_{i−1}).

Step 2. A proof that {x_{i}} is a Cauchy sequence. We must estimate |x_{i} − x_{j}| for j > i. Consider first the distance between two consecutive elements of the sequence:

|x_{k+1} − x_{k}| = |g(x_{k}) − g(x_{k−1})| ≤ L|x_{k} − x_{k−1}|.

Here we used the fact that the x_{k} stay in I and g is a contraction on I. Therefore

|x_{k+1} − x_{k}| ≤ L|x_{k} − x_{k−1}|.

Since L < 1 this means that x_{k+1}, x_{k} are closer to each other than x_{k}, x_{k−1}. In the same way:

|x_{k} − x_{k−1}| ≤ L|x_{k−1} − x_{k−2}|.

By repeating this we get

|x_{k+1} − x_{k}| ≤ L|x_{k} − x_{k−1}|
≤ L^{2}|x_{k−1} − x_{k−2}|
≤ L^{3}|x_{k−2} − x_{k−3}|
≤ ⋯ ≤ L^{k}|x_{1} − x_{0}|,

that is

|x_{k+1} − x_{k}| ≤ L^{k}|x_{1} − x_{0}|. (4)

Now consider |x_{i} − x_{j}| for j > i. We have

x_{i} − x_{j} = x_{i} − x_{i+1} + x_{i+1} − x_{i+2} + x_{i+2} − ⋯ − x_{j−2} + x_{j−2} − x_{j−1} + x_{j−1} − x_{j}

= ∑_{k=i}^{j−1}(x_{k} − x_{k+1}).

Such a sum is called a telescope sum because all terms cancel except the first and the last. Applying the triangle inequality to the sum and using (4) we have

|x_{i} − x_{j}| ≤ |x_{i} − x_{i+1}| + ⋯ + |x_{j−1} − x_{j}| = ∑_{k=i}^{j−1} |x_{k} − x_{k+1}| ≤ |x_{1} − x_{0}| ∑_{k=i}^{j−1} L^{k}.

This is a geometric sum given by the well-known formula:

∑_{k=i}^{j−1} L^{k} = L^{i}(1 + L + ⋯ + L^{j−i−1}) = L^{i} \frac{1 − L^{j−i}}{1 − L} .

Therefore

|x_{i} − x_{j}| ≤ |x_{1} − x_{0}|L^{i} \frac{1 − L^{j−i}}{1 − L} ≤ |x_{1} − x_{0}|L^{i} \frac{1}{1 − L}, (5)

because 0 ≤ 1 − L^{j−i} ≤ 1 for j > i. Since L < 1 we have L^{i} → 0 and hence |x_{i} − x_{j}| → 0 as i → ∞ with j > i. Thus x_{i} is a Cauchy sequence and we get a decimal expansion (real number)

x̄ = lim_{i→∞} x_{i},

which belongs to I because I is closed.

Step 3. Proof that x̄ is a fixed point. We have

|g(x_{i}) − g(x_{j})| ≤ L|x_{i} − x_{j}| → 0, i, j → ∞,

so that g(x_{i}) is a Cauchy sequence. We get a real number which we denote g(x̄):

g(x̄) = lim_{i→∞} g(x_{i}).

We must show that lim_{i→∞} g(x_{i}) = x̄ so that g(x̄) = x̄. But

|x̄ − g(x_{i})| = |x̄ − x_{i+1}| → 0, i → ∞.

This means that lim_{i→∞} g(x_{i}) = x̄ and hence g(x̄) = x̄.

Step 4. Uniqueness. Assume that we have two fixed points x̄_{1}, x̄_{2} ∈ I. Then

|x̄_{1} − x̄_{2}| = |g(x̄_{1}) − g(x̄_{2})| ≤ L|x̄_{1} − x̄_{2}|.

which implies

(1 − L)|x̄_{1} − x̄_{2}| ≤ 0.

But 1 − L > 0 so the only possibility is |x̄_{1} − x̄_{2}| = 0. In other words: x̄_{1} = x̄_{2}. So there is only one fixed point in I.

Note that the uniqueness of x̄ implies that we get the same limit no matter which starting point x_{0} we choose. □

Example. We have seen that g(x) = 2/x is a contraction on the closed interval I = [2, ∞). But x_{0} = 3 gives x_{1} = 2/3 ∉ I so the sequence jumps out. The sequence jumps back and forth between 3 and 2/3; it does not converge.

Example. We have seen that g(x) = x/2 + 1/x is a contraction with L = 1/2 on I = [1, 2]. We check that g : I → I. If x ∈ I = [1, 2], i.e., 1 ≤ x ≤ 2, then x/2 ≤ 1 and 1/x ≤ 1 so that x/2 + 1/x ≤ 1 + 1 = 2. Also x/2 ≥ 1/2 and 1/x ≥ 1/2 so that x/2 + 1/x ≥ 1. Therefore g(x) ∈ I = [1, 2]. The contraction mapping theorem says that g has a unique fixed point in I = [1, 2]. What is it?

7. When do we stop the iteration?

We stop the iteration when the distance between two consecutive iterates is less that a given tolerance, |x_{i} − x_{i+1}| ≤ tol. Then we expect that a certain number of decimals have been fixed in the decimal expansion x̄. For example, with |x_{i} − x_{i+1}| ≤ 10^{−N−1} we expect approximately N decimals to be fixed.

This is justified by the calculation (with j > i as usual)

|x_{i} − x_{j}| ≤ ∑_{k=i}^{j−1} |x_{k} − x_{k+1}| ≤ |x_{i} − x_{i+1}| ∑_{k=i}^{j−1} L^{k−i}

≤ \frac{1 − L^{j−i}}{1 − L} |x_{i} − x_{i+1}| ≤ \frac{1}{1 − L} |x_{i} − x_{i+1}|,

which is done in the same way as (5) but using |x_{k+1} − x_{k}| ≤ L^{k−i}|x_{i} − x_{i+1}| instead of (4). Therefore

|x_{i} − x_{j}| ≤ \frac{1}{1 − L} |x_{i} − x_{i+1}| ≤ \frac{1}{1 − L} tol, j > i.

or by letting j → ∞

|x_{i} − x̄| ≤ \frac{1}{1 − L} |x_{i} − x_{i+1}| ≤ \frac{1}{1 − L} tol.

So the number of fixed decimals after i steps is determined by \frac{1}{1−L} tol. Note that this number is bigger than tol, much bigger if L is near 1, so we get fewer decimals than tol itself indicates. The reason for this is that we are looking at the residual x_{i} − x_{i+1} = x_{i} − g(x_{i}) which measures how well x_{i} satifies the equation x − g(x) = 0. The size of the residual is then magnified by the factor \frac{1}{1−L} when we use it to estimate the error in x_{i}.

8. How fast is the convergence?

From the construction of the sequence x_{i} we have

|x_{i} − x̄| = |g(x_{i−1}) − g(x̄)| ≤ L|x_{i} − x̄|.

Therefore the error is reduced by the factor L < 1 in each step. The smaller L is, the faster the convergence. This is called linear convergence. The bisection algorithm also converges linearly: the error is reduced by a factor 1/2 in each step.

Example. For g(x) = x − x^{2}/2 + 1 on I = [1, 3/2] we have L = 1/2. This follows from

g(x) − g(y) = (1 − \frac{1}{2}(x + y))(x − y).

Here 2 ≤ x + y ≤ 3 so that −\frac{1}{2} ≤ 1 − \frac{1}{2}(x + y) ≤ 0 with absolute value |1 − \frac{1}{2}(x + y)| ≤ 1/2.

If we compute a few iterations in Matlab with x_{0} = 1 and for each iteration compute |x_{i} −\sqrt{2}| we see that that the error is reduced approximately by a factor 1/2 in each step. This is what I got. The first column is x_{i} and the second is |x_{i} − \sqrt{2}|.

1.00000000000000   0.41421356237310
1.50000000000000   0.08578643762690
1.37500000000000   0.03921356237310
1.42968750000000   0.01547393762690
1.40768432617188   0.00652923620122
1.41689674509689   0.00268318272380
1.41309855196381   0.00111501040929
1.41467479318270   0.00046123080961
1.41402240794944   0.00019115442365
1.41429272285787   0.00007916048478

Note that \sqrt{2} is computed by the Matlab function sqrt(2) which is also an approximation but with approximately 16 correct decimals. So we can use it to test the accuracy of our computation.

The convergence is sometimes much faster than this. As the example g(x) = x/2 + 1/x shows. Compute and check this!! This is what I got: again the first column is x_{i} and the second is |x_{i} − \sqrt{2}|.

1.00000000000000   0.41421356237310
1.50000000000000   0.08578643762690
1.41666666666667   0.00245310429357
1.41421568627451   0.00000212390141
1.41421356237469   0.00000000000159
1.41421356237309   0.00000000000000
1.41421356237309   0.00000000000000
1.41421356237309   0.00000000000000
1.41421356237309   0.00000000000000
1.41421356237309   0.00000000000000

In fact it is possible to show that

|x_{i} − x̄| ≤ K|x_{i} − x̄|^{2},

where K is some number. This is called quadratic convergence and means that the error is reduced by a factor which is proportional to the error itself. So the speed of converges increases as x_{i} approaches x̄. We will learn later why it is so fast. See Chapter Newton’s method.

9. Advantages and disadvantages

A disadvantage with the fixed point iteration is that it is often difficult to find a suitable interval I where the iteration converges. This is usually very easy for the bisection algorithm: just plot the function and pick two points where the function has opposite signs.

There are two advantages:

(1) the fixed point iteration can be very fast. The bisection algorithm always converges linearly but not faster than that.

(2) the fixed point iteration also works for systems of equations. This is not true for bisection. We shall return to these advantages later.

/stig