2: Hallazgo de raíces

El problema es resolver\(f(x)=0\) para\(x\) cuando una solución analítica explícita es imposible. Todos los métodos calculan una secuencia\(x_{0}, x_{1}, x_{2}, \ldots\) que converge a la raíz\(x=r\) satisfactoria\(f(r)=0\).

Método de bisección

El método de la bisección es conceptualmente el método más simple y casi siempre funciona. Sin embargo, también es el método más lento, y la mayor parte del tiempo debe evitarse.

Primero elegimos\(x_{0}\) y\(x_{1}\) tal que\(x_{0}<r<x_{1}\). Eso decimos\(x_{0}\) y entre\(x_{1}\) corchetes la raíz. Con\(f(r)=0\), queremos\(f\left(x_{0}\right)\) y\(f\left(x_{1}\right)\) ser de signo opuesto, así que eso\(f\left(x_{0}\right) f\left(x_{1}\right)<0\). Luego asignamos\(x_{2}\) a ser el punto medio de\(x_{0}\) y\(x_{1}\), es decir\(x_{2}=\)\(\left(x_{1}+x_{0}\right) / 2\), o

\[x_{2}=x_{1}-\frac{x_{1}-x_{0}}{2} . \nonumber \]

Luego\(f\left(x_{2}\right)\) se determina el signo de, y el valor de\(x_{3}\) se elige como el punto medio de\(x_{2}\) y\(x_{0}\) o como el punto medio de\(x_{2}\) y\(x_{1}\), dependiendo de si\(x_{2}\) y \(x_{0}\)corchete la raíz, o\(x_{2}\) y\(x_{1}\) corchete la raíz. La raíz, por lo tanto, permanece entre corchetes en todo momento. El algoritmo procede de esta manera y normalmente se detiene cuando el valor absoluto del incremento a la última mejor aproximación a la raíz (arriba, dado por\(\left.\left|x_{1}-x_{0}\right| / 2\right)\) es menor que alguna precisión requerida.

Estimar\(\sqrt{2}=1.41421 \ldots\) usando\(x_{0}=1\) y\(x_{1}=2\)

Ahora\(\sqrt{2}\) es el cero de la función\(f(x)=x^{2}-2\). Iteramos con\(x_{0}=1\) y\(x_{1}=2\). Tenemos

\[x_{2}=2-\frac{2-1}{2}=\frac{3}{2}=1.5 \text {. } \nonumber \]

Ahora,\(f\left(x_{2}\right)=9 / 4-2=1 / 4>0\) para eso\(x_{2}\) y\(x_{0}\) corchete la raíz. Por lo tanto,

\[x_{3}=\frac{3}{2}-\frac{\frac{3}{2}-1}{2}=\frac{5}{4}=1.25 \text {. } \nonumber \]

Ahora,\(f\left(x_{3}\right)=25 / 16-2=-7 / 16<0\) para eso\(x_{3}\) y\(x_{2}\) corchete la raíz. Por lo tanto,

\[x_{4}=\frac{5}{4}-\frac{\frac{5}{4}-\frac{3}{2}}{2}=\frac{11}{8}=1.375, \nonumber \]

y así sucesivamente.

Método de Newton

Este es el método más rápido, pero requiere el cálculo analítico de la derivada de\(f(x)\). Si se conoce la derivada, entonces se debe utilizar este método, aunque no se garantiza la convergencia a la raíz deseada.

Podemos derivar el Método de Newton a partir de una expansión de la serie Taylor. De nuevo queremos construir una secuencia\(x_{0}, x_{1}, x_{2}, \ldots\) que converja a la raíz\(x=r\). Considera al\(x_{n+1}\) miembro de esta secuencia, y la serie Taylor se expande\(f\left(x_{n+1}\right)\) sobre el punto\(x_{n}\). Tenemos

\[f\left(x_{n+1}\right)=f\left(x_{n}\right)+\left(x_{n+1}-x_{n}\right) f^{\prime}\left(x_{n}\right)+\ldots . \nonumber \]

Para determinar\(x_{n+1}\), bajamos los términos de orden superior en la serie Taylor, y asumimos\(f\left(x_{n+1}\right)=0\). Resolviendo para\(x_{n+1}\), tenemos

\[x_{n+1}=x_{n}-\frac{f\left(x_{n}\right)}{f^{\prime}\left(x_{n}\right)} . \nonumber \]

Iniciar el Método de Newton requiere una conjetura para\(x_{0}\), para ser elegido lo más cerca posible de la raíz\(x=r\).

Estimar\(\sqrt{2}\) usando\(x_{0}=1\)

Nuevamente, resolvemos\(f(x)=0\), dónde\(f(x)=x^{2}-2\). Para implementar el Método de Newton, utilizamos\(f^{\prime}(x)=2 x\). Por lo tanto, el Método de Newton es la iteración

\[x_{n+1}=x_{n}-\frac{x_{n}^{2}-2}{2 x_{n}} . \nonumber \]

Con nuestra suposición inicial\(x_{0}=1\), tenemos

\[\begin{aligned} &x_{1}=1-\frac{-1}{2}=\frac{3}{2}=1.5, \\ &x_{2}=\frac{3}{2}-\frac{\frac{9}{4}-2}{3}=\frac{17}{12}=1.416667, \\ &x_{3}=\frac{17}{12}-\frac{\frac{17^{2}}{12^{2}}-2}{\frac{17}{6}}=\frac{577}{408}=1.41426 . \end{aligned} \nonumber \]

Método Secante

El Método Secante es el segundo más rápido que el Método de Newton, y se usa con mayor frecuencia cuando no es posible tomar una derivada analítica de la función\(f(x)\). Escribimos en lugar de\(f^{\prime}\left(x_{n}\right)\),

\[f^{\prime}\left(x_{n}\right) \approx \frac{f\left(x_{n}\right)-f\left(x_{n-1}\right)}{x_{n}-x_{n-1}} . \nonumber \]

Comenzar el Método Secante requiere una conjetura para ambos\(x_{0}\) y\(x_{1}\). Estos valores no necesitan corchete la raíz, pero no se garantiza la convergencia.

Estimar\(\sqrt{2}\) usando\(x_{0}=1\) y\(x_{1}=2\)

Nuevamente, resolvemos\(f(x)=0\), dónde\(f(x)=x^{2}-2\). El método secante itera

\[\begin{aligned} x_{n+1} &=x_{n}-\frac{\left(x_{n}^{2}-2\right)\left(x_{n}-x_{n-1}\right)}{x_{n}^{2}-x_{n-1}^{2}} \\ &=x_{n}-\frac{x_{n}^{2}-2}{x_{n}+x_{n-1}} . \end{aligned} \nonumber \]

Con\(x_{0}=1\) y\(x_{1}=2\), tenemos

\[\begin{aligned} &x_{2}=2-\frac{4-2}{3}=\frac{4}{3}=1.33333 \\ &x_{3}=\frac{4}{3}-\frac{\frac{16}{9}-2}{\frac{4}{3}+2}=\frac{21}{15}=1.4 \\ &x_{4}=\frac{21}{15}-\frac{\left(\frac{21}{15}\right)^{2}-2}{\frac{21}{15}+\frac{4}{3}}=\frac{174}{123}=1.41463 . \end{aligned} \nonumber \]

Un fractal del Método de Newton

Consideremos las complejas raíces de la ecuación\(f(z)=0\), donde

\[f(z)=z^{3}-1 . \nonumber \]

Estas raíces son las tres raíces cúbicas de la unidad. Con

\[e^{i 2 \pi n}=1, \quad n=0,1,2, \ldots \nonumber \]

las tres raíces cúbicas únicas de la unidad son dadas por

\[1, e^{i 2 \pi / 3}, e^{i 4 \pi / 3} . \nonumber \]

Con

\[e^{i \theta}=\cos \theta+i \sin \theta, \nonumber \]

y\(\cos (2 \pi / 3)=-1 / 2, \sin (2 \pi / 3)=\sqrt{3} / 2\), las tres raíces cúbicas de la unidad son

\[r_{1}=1, \quad r_{2}=-\frac{1}{2}+\frac{\sqrt{3}}{2} i, \quad r_{3}=-\frac{1}{2}-\frac{\sqrt{3}}{2} i . \nonumber \]

La idea interesante aquí es determinar en el plano complejo qué valores iniciales de\(z_{0}\) convergen utilizando el método de Newton a cuál de las tres raíces cubo de la unidad.

El método de Newton generalizado al plano complejo es

\[z_{n+1}=z_{n}-\frac{z_{n}^{3}-1}{3 z_{n}^{2}} . \nonumber \]

Si la iteración converge a\(r_{1}\), coloreamos\(z_{0}\) rojo;\(r_{2}\), azul;\(r_{3}\), verde. El resultado se mostrará en conferencia.

Orden de convergencia

Dejar\(r\) ser la raíz y\(x_{n}\) ser la\(n\) th aproximación a la raíz. Definir el error como

\[\epsilon_{n}=r-x_{n} . \nonumber \]

Si para grandes\(n\) tenemos la relación aproximada

\[\left|\epsilon_{n+1}\right|=k\left|\epsilon_{n}\right|^{p}, \nonumber \]

con\(k\) una constante positiva y\(p \geq 1\), entonces decimos que el método numérico de búsqueda de raíces es de orden\(p\). Valores mayores de\(p\) corresponden a una convergencia más rápida a la raíz. El orden de convergencia de la bisección es uno: el error se reduce aproximadamente en un factor de 2 con cada iteración de manera que

\[\left|\epsilon_{n+1}\right|=\frac{1}{2}\left|\epsilon_{n}\right| \text {. } \nonumber \]

Ahora encontramos el orden de convergencia para el Método de Newton y para el Método Secante.

Método de Newton

Comenzamos con el Método de Newton

\[x_{n+1}=x_{n}-\frac{f\left(x_{n}\right)}{f^{\prime}\left(x_{n}\right)}, \nonumber \]

donde la raíz\(r\) satisface\(f(r)=0\). Restando ambos lados de\(r\), tenemos

\[r-x_{n+1}=r-x_{n}+\frac{f\left(x_{n}\right)}{f^{\prime}\left(x_{n}\right)}, \nonumber \]

o

\[\epsilon_{n+1}=\epsilon_{n}+\frac{f\left(x_{n}\right)}{f^{\prime}\left(x_{n}\right)} . \nonumber \]

Usamos la serie Taylor para expandir las funciones\(f\left(x_{n}\right)\) y\(f^{\prime}\left(x_{n}\right)\) sobre la raíz\(r\), usando\(f(r)=0\). Tenemos

\[\begin{align} \nonumber f\left(x_{n}\right) &=f(r)+\left(x_{n}-r\right) f^{\prime}(r)+\frac{1}{2}\left(x_{n}-r\right)^{2} f^{\prime \prime}(r)+\ldots, \\ &=-\epsilon_{n} f^{\prime}(r)+\frac{1}{2} \epsilon_{n}^{2} f^{\prime \prime}(r)+\ldots ; \\ \nonumber f^{\prime}\left(x_{n}\right) &=f^{\prime}(r)+\left(x_{n}-r\right) f^{\prime \prime}(r)+\frac{1}{2}\left(x_{n}-r\right)^{2} f^{\prime \prime \prime}(r)+\ldots, \\ \nonumber &=f^{\prime}(r)-\epsilon_{n} f^{\prime \prime}(r)+\frac{1}{2} \epsilon_{n}^{2} f^{\prime \prime \prime}(r)+\ldots . \end{align} \nonumber \]

Para avanzar más, haremos uso de la siguiente serie estándar de Taylor:

\[\frac{1}{1-\epsilon}=1+\epsilon+\epsilon^{2}+\ldots, \nonumber \]

que converge para\(|\epsilon|<1\). Sustituir (2.21) en (2.20) y usar (2.22) rendimientos

\[\begin{aligned} \epsilon_{n+1} &=\epsilon_{n}+\frac{f\left(x_{n}\right)}{f^{\prime}\left(x_{n}\right)} \\ &=\epsilon_{n}+\frac{-\epsilon_{n} f^{\prime}(r)+\frac{1}{2} \epsilon_{n}^{2} f^{\prime \prime}(r)+\ldots}{f^{\prime}(r)-\epsilon_{n} f^{\prime \prime}(r)+\frac{1}{2} \epsilon_{n}^{2} f^{\prime \prime \prime}(r)+\ldots} \\ &=\epsilon_{n}+\frac{-\epsilon_{n}+\frac{1}{2} \epsilon_{n}^{2} f^{\prime \prime}(r)}{1-\epsilon_{n} \frac{f^{\prime \prime}(r)}{f^{\prime}(r)}+\ldots} \\ &=\epsilon_{n}+\left(-\epsilon_{n}+\frac{1}{2} \epsilon_{n}^{2} \frac{f^{\prime \prime}(r)}{f^{\prime}(r)}+\ldots\right)\left(1+\epsilon_{n} \frac{f^{\prime \prime}(r)}{f^{\prime}(r)}+\ldots\right) \\ &=\epsilon_{n}+\left(-\epsilon_{n}+\epsilon_{n}^{2}\left(\frac{1}{2} \frac{f^{\prime \prime}(r)}{f^{\prime}(r)}-\frac{f^{\prime \prime}(r)}{f^{\prime}(r)}\right)+\ldots\right) \\ &=-\frac{1}{2} \frac{f^{\prime \prime}(r)}{f^{\prime}(r)} \epsilon_{n}^{2}+\ldots \end{aligned} \nonumber \]

Por lo tanto, hemos demostrado que

\[\left|\epsilon_{n+1}\right|=k\left|\epsilon_{n}\right|^{2} \nonumber \]

como\(n \rightarrow \infty\), con

\[k=\frac{1}{2}\left|\frac{f^{\prime \prime}(r)}{f^{\prime}(r)}\right|, \nonumber \]

siempre\(f^{\prime}(r) \neq 0\). El método de Newton es así del orden 2 en raíces simples.

Método Secante

Determinar el orden del Método Secante procede de manera similar. Empezamos con

\[x_{n+1}=x_{n}-\frac{\left(x_{n}-x_{n-1}\right) f\left(x_{n}\right)}{f\left(x_{n}\right)-f\left(x_{n-1}\right)} . \nonumber \]

restamos ambos lados\(r\) y hacemos uso de

\[\begin{aligned} x_{n}-x_{n-1} &=\left(r-x_{n-1}\right)-\left(r-x_{n}\right) \\ &=\epsilon_{n-1}-\epsilon_{n} \end{aligned} \nonumber \]

y la serie Taylor

\[\begin{aligned} f\left(x_{n}\right) &=-\epsilon_{n} f^{\prime}(r)+\frac{1}{2} \epsilon_{n}^{2} f^{\prime \prime}(r)+\ldots, \\ f\left(x_{n-1}\right) &=-\epsilon_{n-1} f^{\prime}(r)+\frac{1}{2} \epsilon_{n-1}^{2} f^{\prime \prime}(r)+\ldots, \end{aligned} \nonumber \]

para que

\[\begin{aligned} f\left(x_{n}\right)-f\left(x_{n-1}\right) &=\left(\epsilon_{n-1}-\epsilon_{n}\right) f^{\prime}(r)+\frac{1}{2}\left(\epsilon_{n}^{2}-\epsilon_{n-1}^{2}\right) f^{\prime \prime}(r)+\ldots \\ &=\left(\epsilon_{n-1}-\epsilon_{n}\right)\left(f^{\prime}(r)-\frac{1}{2}\left(\epsilon_{n-1}+\epsilon_{n}\right) f^{\prime \prime}(r)+\ldots\right) \end{aligned} \nonumber \]

Por lo tanto, tenemos

\[\begin{aligned} \epsilon_{n+1} &=\epsilon_{n}+\frac{-\epsilon_{n} f^{\prime}(r)+\frac{1}{2} \epsilon_{n}^{2} f^{\prime \prime}(r)+\ldots}{f^{\prime}(r)-\frac{1}{2}\left(\epsilon_{n-1}+\epsilon_{n}\right) f^{\prime \prime}(r)+\ldots} \\ &=\epsilon_{n}-\epsilon_{n} \frac{1-\frac{1}{2} \epsilon_{n} \frac{f^{\prime \prime}(r)}{1-\frac{1}{2}\left(\epsilon_{n-1}+\epsilon_{n}\right)}+\ldots}{f^{\prime \prime}(r)}+\ldots \\ &=\epsilon_{n}-\epsilon_{n}\left(1-\frac{1}{2} \epsilon_{n} \frac{f^{\prime \prime}(r)}{f^{\prime}(r)}+\ldots\right)\left(1+\frac{1}{2}\left(\epsilon_{n-1}+\epsilon_{n}\right) \frac{f^{\prime \prime}(r)}{f^{\prime}(r)}+\ldots\right) \\ &=-\frac{1}{2} \frac{f^{\prime \prime}(r)}{f^{\prime}(r)} \epsilon_{n-1} \epsilon_{n}+\ldots \end{aligned} \nonumber \]

o al orden principal

\[\left|\epsilon_{n+1}\right|=\frac{1}{2}\left|\frac{f^{\prime \prime}(r)}{f^{\prime}(r)}\right|\left|\epsilon_{n-1}\right|\left|\epsilon_{n}\right| . \nonumber \]

El orden de convergencia aún no es obvio a partir de esta ecuación, sino que debería ser menor que cuadrático porque\(\left|\epsilon_{n-1}\right|>\left|\epsilon_{n}\right|\). Para determinar la ley de escalado buscamos una solución de la forma

\[\left|\epsilon_{n+1}\right|=k\left|\epsilon_{n}\right|^{p} . \nonumber \]

De esta ansatz, también tenemos

\[\left|\epsilon_{n}\right|=k\left|\epsilon_{n-1}\right|^{p}, \nonumber \]

y por lo tanto

\[\left|\epsilon_{n+1}\right|=k^{p+1}\left|\epsilon_{n-1}\right|^{p^{2}} . \nonumber \]

Sustitución en (2.26) resultados en

\[k^{p+1}\left|\epsilon_{n-1}\right|^{p^{2}}=\frac{k}{2}\left|\frac{f^{\prime \prime}(r)}{f^{\prime}(r)}\right|\left|\epsilon_{n-1}\right|^{p+1} . \nonumber \]

Equiparar el coeficiente y la potencia de\(\epsilon_{n-1}\) los resultados en

\[k^{p}=\frac{1}{2}\left|\frac{f^{\prime \prime}(r)}{f^{\prime}(r)}\right|, \nonumber \]

y

\[p^{2}=p+1 . \nonumber \]

El orden de convergencia del Método Secante, dado por\(p\), es por lo tanto la raíz positiva de la ecuación cuadrática\(p^{2}-p-1=0\), o

\[p=\frac{1+\sqrt{5}}{2} \approx 1.618 \text {, } \nonumber \]

que casualmente es un famoso número irracional que se llama La proporción áurea, y va por el símbolo\(\Phi\). Vemos que el Método Secante tiene un orden de convergencia que se encuentra entre el Método de Bisección y el Método de Newton.