Resolver ecuaciones como $xe^x = c$ mediante iteración funcional

Question

Ayer se me ocurrió al azar resolver $xe^x = c$ mediante iteración funcional (IF) tras manipular la ecuación de forma " $x = \cdots$ " que proporciona la tasa de convergencia "más rápida" independientemente de la estimación de partida.

Descubrí por ensayo y error guiado por la intuición que la ecuación $x = ( c x^r e^{-x} )^\frac{1}{r+1}$ donde $r = \ln(c)$ funciona excepcionalmente bien para grandes $c$ siempre que la estimación inicial sea positiva.

En cambio, la aproximación Newton-Raphson (NR) (sobre $x e^x - c = 0$ ) funciona mal si la estimación inicial está demasiado lejos. Conozco los detalles de este comportamiento (véase https://math.stackexchange.com/a/800070 ), pero no sé mucho sobre FI, así que no entiendo muy bien cómo encontrar una ecuación adecuada para garantizar una convergencia "rápida".

Después de eso, descubrí que la ecuación $x = (x+1)/(e^x/c+1)$ da una FI aún mejor, que supera tanto a mi primera FI como a la NR.

Primera pregunta es, por qué es tan buena esta IF (Kibble ya ha hecho esta parte, así que no tienes que mencionarla de nuevo si respondes a mi pregunta), y cómo encontrar una IF tan rápida de forma sistemática?

Después de eso, descubrí que NR-log (es decir, NR en $x + \ln(x) - \ln(c) = 0$ ) converge mucho más rápido que mi FI mejorado, pero sólo si la estimación inicial no es demasiado grande, de lo contrario genera una estimación siguiente negativa y se bloquea en la siguiente iteración.

Segunda pregunta es, ¿existe una técnica genérica que para cualquier ecuación en $x$ da una FI para resolver esa ecuación para positivo $x$ que converge "rápidamente" a la raíz para cualquier punto de partida positivo? Mi FI mejorada casi lo hace, pero no tengo ni idea de cómo hacerlo para otras ecuaciones en general, ni sé si existe una 'mejor' que la mía.

Aquí digo "rápido" y "mejor", pero en realidad no sé cómo especificar con precisión cuáles deben ser estas nociones, así que siéntete libre de especificar las tuyas propias siempre que tengan sentido.

Mi intuición

Al principio excluí estos porque mi pregunta ya es bastante larga, pero aquí está la intuición detrás de mis IF. Primero estaba pensando que tal vez hay un método genérico si tenemos una función estrictamente creciente $f$ tal que $f(0) < 0$ y queremos encontrar $y > 0$ tal que $f(y) = 0$ . Mi intuición era que para asegurar la convergencia cuadrática queremos encontrar una función $g$ de forma que la ecuación original sea equivalente a $x = g(x)$ y dónde:

1. $g$ está limitada en $\mathbb{R}_{\ge 0}$ .

2. $|g'| < 1$ .

3. $g'(y) = 0$ .

Mis dos IF cumplen las dos primeras condiciones, pero sólo la mejorada cumple la tercera. No sé qué criterios mejores hay.

Detalles adicionales

Sin embargo, si buscamos un algoritmo eficiente para calcular $W(c)$ en particular, a continuación, utilizando NR-log con estimación inicial $\ln(c+1)$ da una convergencia cuadrática uniforme sobre todos $c > 0$ que es increíble. En cambio, NR necesita $(ln(ln(c)))$ pasos para llegar a la convergencia cuadrática uniforme, mientras que (mi mejorado) FI tarda $(ln(c))$ pasos. Pero tanto NR como FI tienen convergencia cuadrática uniforme si en su lugar utilizamos la estimación de partida $\ln(c+1)-\ln(\ln(c+1)+1)$ así que no puedo decir cuál es mejor. (NR-log sólo tiene convergencia lineal uniforme si utilizamos esta estimación inicial debido a la pequeña $c$ .)

Answer 1

Voy a abordar aquí la cuestión "La primera pregunta es, ¿por qué este ( $g(x)$ abajo) tan bueno, y cómo encontrar una iteración funcional tan rápida de forma sistemática?".

Tomemos tus dos funciones de ejemplo:

$$f(x) \equiv (cx^re^{-x})^{\frac{1}{r+1}}$$ $$g(x) \equiv \frac{x+1}{\frac{e^x}{c}+1}$$

Expandir en una serie de Taylor sobre el punto fijo $x = W(c)$ . Entonces encontramos

$$f(x) = W(c) + A(x-W(c)) + O(x-W(c))^2$$ $$g(x) = W(c) + B(x-W(c))^2 + O(x-W(c))^3$$

donde $A,B$ son algunas constantes que dependen de $c$ (que es inferior a 1 en valor absoluto). Un ejemplo concreto $c=100$ entonces encontramos $A \approx 0.2$ y $B \approx 0.4$ . Por lo tanto, cuando estamos cerca del punto fijo la recursión $x_{n+1} = f(x_n)$ y $y_{n+1} = g(y_n)$ satisfacer

$$x_{n+1} - W(c) \simeq A(x_n-W(c)) \implies |x_{n+1}-W(c)| \propto A^n$$

$$y_{n+1} - W(c) \simeq B(y_n-W(c))^2 \implies |y_{n+1}-W(c)| \propto B^{2^n}$$

Ahora vemos por qué $g$ funciona mucho mejor, ya que $n\to\infty$ tenemos $B^{2^n}$ disminuyendo mucho más rápido que $A^n$ . En términos técnicos decimos que $f$ tiene un tasa de convergencia mientras que $g$ tiene una tasa de convergencia cuadrática.

Para obtener una buena tasa de convergencia queremos una función $h(x)$ que satisfagan $h(x) \simeq W(c) + C(x-W(c))^n$ cerca del punto fijo con $C$ y tan alto como $n$ como sea posible (además, también debería garantizar la convergencia al punto fijo incluso si empezamos lejos de él). Para obtener una convergencia mejor que la lineal necesitamos $h'(x) = 0$ en el punto fijo. Encontrar este tipo de funciones suele ser más un arte que una ciencia; usa tu intuición y algo de ensayo y error para intentar encontrarla.

Answer 2

Por supuesto, hay que echar un vistazo a los libros sobre Interation. No existe una Rekursion ideal para todos los problemas.

Pero..: Si quieres construirte una Iteración entonces piensa en puntos fijos $f(x)=x$ .

Un ejemplo para su problema:

$x e^x =c$ => $x(e^x+1)=x+c$ => $x=\frac{x+c}{e^x +1}$ => Recursión $x_{n+1}=\frac{x_n+c}{e^{x_n}+1}$ .

EDITAR: Era sólo un ejemplo - Pensé que usted sabe lo que quiero decir. Si hay para la divergencia grande de c entonces utilice el logaritmo en vez de la función exponencial.

$x e^x =c$ => $\ln x +x=\ln c$ => $x\ln x +x^2=x\ln c$ => Recursión $x_{n+1}=\frac{x_n \ln c}{x_n+\ln x_n}$ .

$x_0$ : Es importante utilizar un valor cercano a la solución.