Contenido

1 Introducción
2 Ejercicio

Introducción¶

Raíz de una función¶

Una ecuación escalar es una expresión de la forma $$f(x)=0$$ donde $f:\Omega\subset\mathbb{R}\to\mathbb{R}$ es una función.

Cualquier número $\alpha$ tal que $f(\alpha)=0$ se dice que es una solución de o una raíz de $f$.

Por ejemplo, la ecuación

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

tiene como raíces $x=-1$, $x=1$ y $x=2$ porque

$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$

Gráficamente, las raíces son los valores de $x$ para los cuales la curva $f$ corta al eje $OX.$

Decimos que una raíz de $f$, $\alpha$, es de multiplicidad $m$ si

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

En el caso de que $m=1$ decimos que la raíz es simple.

Por ejemplo: $$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$$

Separación de raíces¶

Separar una raíz de $f$ consiste en encontrar un intervalo $[a,b]$ que contiene una y solo una raíz de $f.$

Para separar raíces tendremos en cuenta el Teorema de Bolzano:

Sea $f:[a,b]\to\mathbb{R}$ una función contínua con $f(a)f(b)\lt 0$, es decir, con signo distinto en los extremos del intervalo. Entonces existe al menos una raíz de $f$ en $[a,b]$.

Si se cumple el teorema de Bolzano y además la función es:

Estrictamente creciente en $[a,b]$, es decir, $f'(x) \gt 0$ para todo $x \in (a,b)$ o
Estrictamente decreciente en $[a,b]$, es decir, $f'(x) \lt 0$ para todo $x \in (a,b).$

La función tiene una única raíz en $[a,b]$

Por ejemplo, si $f(x)=x^2-1$ podemos separar sus raíces en los intervalos $[-2,0]$ y $[0,2]$.

En el caso de $[-2,0]$:

$f(-2)=3\gt0$
$f(0)=-1\lt0$
$f$ es decreciente porque $f'(x)=2x\lt0$ porque $x$ es negativo si $x\in(-2,0).$

Para $[0,2]$:

$f(0)=-1\lt0$
$f(2)=3\gt0$
$f$ es creciente porque $f'(x)=2x\gt0$ porque $x$ es positivo si $x\in(0,2).$

Métodos numéricos de cálculo de raíces y orden de convergencia¶

Los métodos numéricos no solo son métodos alternativos a los analíticos, sino que en algunos casos son los únicos posibles. Por ejemplo la ecuación

$$\cos x = x$$

tiene una única solución, pero no hay forma de despejar la $x$ y resolver analíticamente el sistema.

Los métodos numéricos de cálculo de raíces de una función son métodos iterativos, es decir, construímos una sucesión $$x_0,x_1,\ldots,x_k,\ldots \rightarrow \alpha$$

tal que

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

El orden de convergencia de un métodos está relacionado con la velocidad de convergencia de la sucesión con respecto a $k$.

Supongamos que la sucesión $x_k$ converge a $\alpha\in\mathbb{R}$. Decimos que $x_k$ converge a $\alpha$ con orden de convergencia $p$ si

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

siendo $e_k=|x_k-\alpha|$ el error absoluto en el paso $k.$ Es decir

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

En los casos particulares

$p=1$, decimos que la convergencia es lineal.
$p=2$, decimos que la convergencia es cuadrática.

Un método numérico se dice de orden $p$ si genera una sucesión que converge a la solución con un orden de convergencia $p$.

Así, por ejemplo, supongamos que nuestro método tiene convergencia lineal con $\lambda=\dfrac{1}{2}$ y que $e_k=0.1$. Tenemos que

$$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 $$

Es decir, a cada paso, el error disminuye a la mitad.

Supongamos ahora que nuestro método tiene convergencia cuadrática con $\lambda=1$ y que $e_k=0.1$. Tenemos que

$$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 $$

Es decir, a cada paso, el error disminuye de orden de magnitud, primero a las centésimas, luego a las diezmilésimas, etc. Como se puede apreciar el error dismimuye mucho más rapidamente que en el caso lineal.

Método de bisección¶

Sea la función continua $f:[a,b]\to\mathbb{R}$ tal que $f(a)f(b)\lt 0$. El teorema de Bolzano garantiza la existencia de una raíz de $f$ en $(a,b)$.

Algoritmo¶

Sea $a_1=a$, $b_1=b$.

Para $k=1,2,\ldots,\mathrm{MaxNumIter}$

Calcular el punto medio $x_k=\dfrac{a_k+b_k}{2}$ y evaluar $f(x_k)$.

Si $x_k$ satisface el criterio de parada, parar.

En el caso contrario,

si $f(a_k)f(x_k)<0$ entonces:
$ a_{k+1}=a_{k},$ $ b_{k+1}=x_k,$

si $f(x_k)f(b_k)<0$ entonces:
$ a_{k+1}=x_{k},$ $ b_{k+1}=b_k.$

en otro caso:
acabar.

Cota de error¶

Supongamos que el intervalo inicial $[a_0,b_0]$ cumple las condiciones del teorema de Bolzano y, sin pérdida de generalidad, que el intervalo contiene una sola raíz. Entonces todos los demás intervalos obtenidos mediante el algotimo de bisección contienen una única raíz.

Tomaremos como solución aproximada el último $x_k$ obtenido, que será extremo del siguiente intervalo. Una cota del error es la longitud del intervalo: el peor caso es que la raíz esté muy cerca del otro extremo del intervalo y entonces el error sería un poco menor que la longitud del intervalo.

Así, tras hacer una iteración, el intervalo es $[a_1,b_1]$ y su longitud es la mitad de la de $[a_0,b_0]$. Es decir, la cota de error cuando hemos hecho una iteración es

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

Si hacemos otra iteración, la longitud del intervalo se reduce a la mitad y la cota de error es

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

Para la iteración 3

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

y para la iteración $k$

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

Así que dado el número de iteraciones, podemos dar una cota del error. Y viceversa, dada una tolerancia, podemos dar el número de iteraciones que garantizan un error menor que la tolerancia.

Ventajas¶

Fácil de programar.
Si el intervalo inicial cumple el teorema de Bolzano:
- El método es convergente.
- Es fácil estimar una cota del error absoluto.
- Podemos saber a priori cuantas iteraciones tenemos que realizar.

Desventajas¶

La velocidad de convergencia es lenta.
Podemos estar cerca de la raíz y en la siguiente iteración alejarnos.

En la práctica, el método de bisección se utiliza para inicializar métodos más rápidos.

Ejercicio¶

Sea la ecuación

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

Demostrar que en $\left[-1,1\right]$ existe una única raíz.
¿Se puede calcular por el método de bisección partiendo de dicho intervalo?
Aproximar la raíz haciendo cuatro iteraciones.
Dar una cota del error cometido al calcular esta raíz.
¿Cuántas iteraciones n tendríamos que hacer para garantizar que el error es menor que $10^{-6}$?

Demostrar que en $[-1,1]$ existe una única raíz.¶

Podemos definir la función $f(x)=\dfrac{x}{2}e^{-\frac{x}{2}}+\dfrac{1}{2}$.

Vemos que se cumplen las tres condiciones suficientes para que exista una única raíz en el intervalo:

$f$ es contínua.
$f$ tiene distinto signo en los extremos.
$f$ es estrictamente creciente (o decreciente) en este intervalo.

Demostrémoslo también analíticamente:

$f$ es la suma y producto de funciones contínuas, por lo tanto es continua.
$f(-1)=-0.3$ y $f(1)=0.8$
La derivada de la función $$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$$ porque como una función exponencial es siempre positiva y $(2-x)$ es positiva en $(-1,1)$ se sigue que $f'\gt 0$ para todo valor del intervalo y entonces es estrictamente creciente en el intervalo.

¿Se puede calcular por el método de bisección partiendo de dicho intervalo?¶

Las condiciones para aplicar el método de Bisección son las condiciones de Bolzano, es decir, las condiciones 1 y 2 del apartado anterior.

Como demostramos, se cumplen estas dos condiciones y por lo tanto, podemos aplicar el método de Bisección.

Aproximar la raíz haciendo cuatro iteraciones.¶

Hacemos las iteraciones teniendo en cuenta que dados $a$ y $b$

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

y que la cota de error viene dada por

$$c = b-a$$

pero de la iteración siguiente.

Iteración 1

El intervalo es $[-1,1]$ y su punto medio es

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

Como $f(-1)=-0.32$, $f(0)=0.50$ tienen signo distinto el siguiente intervalo es $[-1,0]$ y la cota de error es la longitud de este nuevo intervalo, 1.

Iteración 2

El intervalo es $[-1,0]$ y su punto medio es

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

Como $f(-1)=-0.32$, $f(-0.5)=0.18$ tienen signo distinto el siguiente intervalo es $[-1,-0.5]$ y la cota de error es la longitud de este nuevo intervalo, 0.5.

Iteración 3

El intervalo es $[-1,-0.5]$ y su punto medio es

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

Como $f(-0.75)=-0.05$, $f(-0.5)=0.18$ tienen signo distinto el siguiente intervalo es $[-0.75,-0.5]$ y la cota de error es la longitud de este nuevo intervalo, 0.25.

Iteración 4

El intervalo es $[-0.75,-0.5]$ y su punto medio es

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

y la cota de error es la mitad de la longitud del intervalo anterior, es decir, 0.125.

\begin{array}{|r|rrr|rrr|r|} \hline \mathrm{iteración} & a & m & b & f(a) & f(m) & f(b) & \mathrm{cota}\; \mathrm{error}\\ \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}

Dar una cota del error cometido al calcular esta raíz.¶

Ya calculamos la cota de error conforme calculábamos las iteraciones, pero, teniendo en cuenta que el número de iteraciones es $k=4$, también podíamos haber usado la fórmula

$$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$$

Comprobemos que el error es menor que la cota de error. Como la solución exacta es $\alpha= -0.703$, el error absoluto es

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

que es menor que la cota de error, como era de esperar.

¿Cuántas iteraciones $n$ tendríamos que hacer para garantizar que el error es menor que $10^{-6}$?¶

Buscamos que

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

Como se verifica que el error (desconocido) es menor que la cota de error (conocida)

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

una condición suficiente para que el error sea menor que $10^{-6}$ es que la cota de error sea menor que $10^{-6}$

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

Trabajaremos con esta desigualdad y aplicaremos las siguientes propiedades

Si $a\lt b$ y $c\gt 0$ $\Longrightarrow a\,c\lt b\,c$
Si $f$ es una función estrictamente creciente se tiene que si $x\lt y\Longrightarrow f(x)\lt f(y)$
$\log A^B = B \log A$

Teniendo en cuenta la propiedad 1 y multiplicando ambos miembros de la desigualdad primero por $2^n$ y luego $10^6$ tenemos que

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

Como $f(x)=\log(x)$ es una función estrictamente creciente, aplicando la propiedad 2 se tiene que

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

y teniendo en cuenta la propiedad 3

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

Como $\log2 \gt 0$, aplicando la propiedad 1 con $c=1/\log2$

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

$\log$ representa aquí un logaritmo en cualquier base mayor que 1. Usaremos, por ejemplo, logaritmos neperianos

$$20.9\lt n$$

Y si hacemos $\fbox{$n=21$}$ iteraciones, podemos garantizar que el error es menor que $10^{-6}.$