Contents

• 1  Introduction
  • 1.1  Zero of a function
  • 1.2  Zero bracketing
  • 1.3  Numerical methods to find zeros and order of convergence
  • 1.4  Bisection method
• 2  Exercise
  • 2.1  Prove that the interval $[-1,1]$ contains only one root.
  • 2.2  May the root be approximated using the bisection method starting from this interval?
  • 2.3  Approximate the root with four iterations.
  • 2.4  Give an error bound for the approximation
  • 2.5  How many iterations guarantee an error less than $10^{-6}$?

Introduction

Zero of a function

A escalar equation is an expression of the form $$f(x)=0$$ where $f:\Omega\subset\mathbb{R}\to\mathbb{R}$ is a function.

Any number $\alpha$ such that $f(\alpha)=0$ is a solution, zero or root of $f$.

For instance, $x=-1$, $x=1$ y $x=2$ are the zeros of the equation

$$x^3-2x^2-x+2=0 \qquad (f(x)=x^3-2x^2-x+2)$$

because

• $f(-1)=(-1)^3-2(-1)^2-(-1)+2=-1-2+1+2=0$
• $f(1)=(1)^3-2(1)^2-(1)+2=1-2-1+2=0$
• $f(2)=(2)^3-2(2)^2-(2)+2=8-8-2+2=0$

Graphically, the zeros are the $x$ values ​​for which the $f$ curve intersects the $OX$ axis.

A zero of $f$, $\alpha$, has multiplicity $m$ if

$$f(\alpha)=f'(\alpha)=\ldots=f^{(m-1)}(\alpha)=0,\quad \mathrm{and}\quad f^{(m)}(\alpha)\neq0,$$

If $m=1,$ we have a single zero.

For example: $$f(x)=2(x+1)^3(x-1)^2(x-0.5)=-1 + x + 4 x^2 - 2 x^3 - 5 x^4 + x^5 + 2 x^6$$

Zero bracketing

Zero bracketing consists of finding an interval $[a, b]$ that contains one and only one root of $f.$

We will take into account the Bolzano's Theorem:

Suppose that $f:[a,b]\to\mathbb{R}$ is continuous, with $f(a)f(b)\lt 0$, that is, with a different sign at the interval borders. Then there is at least one root of $f$ in $[a,b]$.

If Bolzano's theorem is fulfilled and also the function is:

• Strictly increasing in $[a,b]$, that is, $f'(x) \gt 0$ for all $x \in (a,b)$ or
• Strictly decreasing in $[a,b]$, that is, $f'(x) \lt 0$ for all $x \in (a,b).$

The function has a single zero in $[a,b]$

For example, if $f(x)=x^2-1$ we can bracket their zeros in the intervals $[-2,0]$ and $[0,2]$.

For $[-2,0]$:

• $f(-2)=3\gt0$
• $f(0)=-1\lt0$
• $f$ is decreasing because $f'(x)=2x\lt0$ and $x$ is negative if $x\in(-2,0).$

And for $[0,2]$:

• $f(0)=-1\lt0$
• $f(2)=3\gt0$
• $f$ is increasing because $f'(x)=2x\gt0$ and $x$ is positive if $x\in(0,2).$

Numerical methods to find zeros and order of convergence

Numerical methods are not only alternative methods to analytical ones. In some cases, they are the only possible ones. For example, the equation

$$\cos x = x$$

has only one solution, but there is no way to solve it analytically.

Numerical methods to find zeros of functions are iterative methods, that is, we define a sequence $$x_0,x_1,\ldots,x_k,\ldots \rightarrow \alpha$$

such that

$$\lim_{k\to\infty}f(x_k)=0.$$

The order of convergence of the method is related to the speed of convergence of the sequence with respect to $k$.

Suppose the sequence $x_k$ converges to $\alpha\in\mathbb{R}$. We say that $x_k$ converges to $\alpha$ with order $p$ if

$$\lim_{k\to\infty}\frac{e_k}{e_{k-1}^{\,p}}=\lambda\neq0$$

being $e_k=|x_k-\alpha|$ the absolute error in iteration $k.$ That is

$$e_k\approx \lambda\, e_{k-1}^{\,p}$$

In the special cases

• $p=1$, the convergence is linear.
• $p=2$, the convergence is quadratic.

A numerical method is said to be of order $p$ if it produces a sequence which converges to the solution with order $p$.

For instance, let's suppose that our method convergence order is linear with $\lambda=\dfrac{1}{2}$ and $e_k=0.1.$ We have

$$e_{k+1}\approx \frac{e_k}{2}=0.05 \quad e_{k+2}\approx \frac{e_{k+1}}{2}=0.025 \quad e_{k+3}\approx \frac{e_{k+2}}{2}=0.0125 \quad \ldots $$

That is, at each iteration, the error halves.

Let's suppose that our method convergence order is quadratic with $\lambda=1$ and $e_k=0.1$. We have

$$e_{k+1}\approx e_k^{\,2} =0.01 \quad e_{k+2}\approx e_{k+1}^{\,2} =0.0001 \quad e_{k+3}\approx e_{k+2}^{\,2}=0.00000001 \quad \ldots $$

That is, at each step, the error decreases by an order of magnitude, first to $0.01,$ then to $0.0001,$ etc. We can see that the error decreases much faster than in the linear case.

Bisection method

If we have a continuous function $f:[a,b]\to\mathbb{R}$ such that $f(a)f(b)\lt 0$. Bolzano's theorem guarantees the existence of a zero of $f$ in $(a,b)$.

Once Loop Reflect

Algorithm

• Let $a_1=a$, $b_1=b$.
• For $k=1,2,\ldots,\mathrm{MaxNumIter}$

  • Compute the midpoint $x_k=\dfrac{a_k+b_k}{2}$
  • If stopping criteria is satisfied then $x_k$ is the approximation: stop.
  • Else,

    • if $f(a_k)f(x_k)<0$ then:

      $ a_{k+1}=a_{k},$ $ b_{k+1}=x_k,$

    • if $f(x_k)f(b_k)<0$ then:

      $ a_{k+1}=x_{k},$ $ b_{k+1}=b_k.$

    • else:

      stop.

Error boundary

Suppose that the initial interval $ [a_0, b_0] $ satisfies the conditions of Bolzano's theorem and, without loss of generality, that the interval contains a single zero. Then all other intervals obtained by the bisection algorithm contain a single zero.

We will take as an approximate solution the last $x_k$ obtained, which will be the extreme of the following interval. A boundary of the error is the length of the interval: the worst case is that the zero is very close to the other end of the interval and then the error would be a little less than the length of the interval.

Thus, after iterating, the interval is $[a_1, b_1]$ and its length is half the length of $[a_0, b_0]$. That is, the error boundary when we have done an iteration is

$$ c_1 = \frac{b_0-a_0}{2} $$

If we iterate again, the length of the interval is halved and the error boundary is

$$ c_2 = \frac{1}{2}\times\frac{b_0-a_0}{2}=\frac{b_0-a_0}{2^2} $$

For iteration 3

$$ c_3 = \frac{1}{2}\times\frac{b_0-a_0}{2^2}=\frac{b_0-a_0}{2^3} $$

and for iteration $k$

$$ c_k = \frac{b_0-a_0}{2^k} $$

So given the number of iterations, we can give an error boundary. And vice versa, given a tolerance, we can give the number of iterations that guarantee an error less than the tolerance.

Advantages

• Easy to implement.
• If the initial interval satisfies Bolzano's theorem:
  • The method is convergent.
  • It is easy to estimate an absolute error boundary.
  • We can know a priori how many iterations we have to perform.

Disadvantages

• The convergence speed is slow.
• We can be close to the zero and in the next iteration move away.

In practice, the bisection method is used to initialize faster methods.

Exercise

Consider the equation

$$\frac{x}{2}e^{-\frac{x}{2}}+\frac{1}{2}=0$$

1. Prove that the interval $\left[-1,1\right]$ contains only one root.
2. May the root be approximated using the bisection method starting from this interval?
3. Approximate the root with four iterations.
4. Give an error bound for the approximation.
5. How many iterations guarantee an error less than $10^{-6}$?

Prove that the interval $[-1,1]$ contains only one root.

We define the function $f(x)=\dfrac{x}{2}e^{-\frac{x}{2}}+\dfrac{1}{2}$.

We see that the three sufficient conditions to exist a single root in the interval are met:

1. $f$ is continuous.
2. $f$ has different signs at the endpoints.
3. $f$ is strictly increasing (or decreasing) in this interval.

Let us also prove it analytically:

1. $f$ is the sum and product of continuous functions, therefore it is continuous.
2. $f(-1)=-0.3$ y $f(1)=0.8$
3. The derivative of the function $$f'(x)= \dfrac{1}{2}e^{-\frac{x}{2}}+\dfrac{x}{2}e^{-\frac{x}{2}}\dfrac{(-1)}{2}=\dfrac{2}{4}e^{-\frac{x}{2}}-\dfrac{x}{4}e^{-\frac{x}{2}}=\dfrac{1}{4}e^{-\frac{x}{2}}(2-x)=(+)(+)\gt 0$$ because as a exponential function is always positive and $(2-x)$ is positive in $(-1,1)$ it follows that $f'\gt 0$ for every value of the interval and then it is strictly increasing in the interval.

May the root be approximated using the bisection method starting from this interval?

The conditions to apply the Bisection method are Bolzano's conditions, that is, conditions 1 and 2 of the previous section.

As we demonstrated, these two conditions are met and therefore, we can apply the Bisection method.

Approximate the root with four iterations.

We iterate taking into account that given $a$ and $b$ the midpoint is

$$m = \frac{a+b}{2}$$

and that the error boundary is given by

$$c = b-a$$

of the next iteration.

Iteration 1

The interval is $[-1,1]$ and its midpoint is

$$m = \frac{a+b}{2}=\frac{(-1)+1}{2}=0$$

As $f(-1)=-0.32$ and $f(0)=0.50$ the sign of the function is different at the next interval boundaries that is $[-1,0]$ and the error boundary is the length of this interval, 1.

Iteration 2

The interval is $[-1,0]$ and its midpoint is

$$m = \frac{a+b}{2}=\frac{(-1)+0}{2}=-0.5$$

As $f(-1)=-0.32$ and $f(-0.5)=0.18$ the sign of the function is different at the next interval boundaries that is $[-1,-0.5]$ and the error boundary is the length of this interval, 0.5.

Iteration 3

The interval is $[-1,-0.5]$ and its midpoint is

$$m = \frac{a+b}{2}=\frac{(-1)+(-0.5)}{2}=-0.75$$

As $f(-0.75)=-0.05$ and $f(-0.5)=0.18$ tienen signo distinto el siguiente intervalo es $[-0.75,-0.5]$ and the error boundary is the length of this interval, 0.25.

Iteration 4

The interval is $[-0.75,-0.5]$ and its midpoint is

$$m = \frac{a+b}{2}=\frac{(-1)+(-0.5)}{2}=-0.625$$

and the error boundary is half the length of the previous interval, that is, 0.125.

\begin{array}{|r|rrr|rrr|r|} \hline \mathrm{iteration} & a & m & b & f(a) & f(m) & f(b) & \mathrm{error}\; \mathrm{bound}\\ \hline 1 &{\color{red}{-1.000}} &{\color{blue}{0.000}} & 1.000 &{\color{red}{-0.32}} & {\color{blue}{0.50}} & 0.80 & 1.000\\ 2 &{\color{red}{-1.000}} &{\color{blue}{-0.500}} & 0.000 &{\color{red}{-0.32}} & {\color{blue}{0.18}} & 0.50 & 0.500\\ 3 &-1.000 &{\color{red}{-0.750}} &{\color{blue}{-0.500}} &-0.32 &{\color{red}{-0.05}} & {\color{blue}{0.18}} & 0.250\\ 4 &-0.750 &\mathbf{-0.625} &-0.500 &-0.05 & & 0.18 & 0.125\\ \hline \end{array}

Once Loop Reflect

Give an error bound for the approximation

We already calculated the error bound along with the iterations but, taking into account that the number of iterations is $k = 4$, we could also have used the formula

$$c_k=\frac{b_0-a_0}{2^k}=\frac{1-(-1)}{2^4}=\frac{2}{2^4}=\frac{1}{2^3}=\frac{1}{8} = 0.125$$

Let's check that the error is less than the error boundary. Since the exact solution is $\alpha= -0.703$, the absolute error is

$$e_4 = |x_4-\alpha|=|-0.625-(-0.703)|=0.078$$

which is less than the error boundary, as expected.

How many iterations guarantee an error less than $10^{-6}$?

We want that

$$ e_{a}=\left|\alpha-x_{n}\right|\lt 10^{-6}. $$

Since the error (unknown) is less than the error bound (known)

$$ e_{a}=\left|\alpha-x_n\right|\lt\dfrac{b_{0}-a_{0}}{2^n}. $$

a sufficient condition for the error to be less than $10^{-6}$ is that the error bound is less than $10^{-6}$

$$ \dfrac{b_{0}-a_{0}}{2^n}\lt 10^{-6}. $$

We will work with this inequality and apply the following properties

1. If $a\lt b$ and $c\gt 0$ $\Longrightarrow a\,c\lt b\,c$
2. If $f$ is and strictly increasing function then, if $x\lt y\Longrightarrow f(x)\lt f(y)$
3. $\log A^B = B \log A$

Taking into account property 1 and multiplying both members of the inequality first by $2^n$ and then $10^6$ we have

$$ \frac{1-(-1)}{2^{n}} \lt 10^{-6} \Longleftrightarrow 2 \lt 2^n 10^{-6} \Longleftrightarrow 2\times 10^6\lt 2^{n} $$

Since $f(x)=\log(x)$ is a strictly increasing function, applying property 2 we have

$$ \log\left(2\times 10^6\right)\lt\log\left(2^{n}\right) $$

and taking into account property 3

$$ \log\left(2\times 10^6\right)\lt n\log2. $$

As $\log2 \gt 0$, applying property 1 with $c=1/\log2$

$$ \frac{\log\left(2\times 10^6\right)}{\log2}\lt n $$

$\log$ represents here any logarithm in base greater than 1. We will use, for example, natural logarithms

$$20.9\lt n$$

And if we do $\fbox{$n=21$}$ iterations, we can guarantee that the error is less than $10^{-6}.$