Encontrar una buena función para la aplicación de iteración de punto fijo método de $f(x)=x^3-x^2-x-1$

Question

Pregunta:

Se nos da una función de $f(x)=x^3-x^2-x-1$ y sabemos que la única raíz de $f$ está en algún lugar cerca de a $\alpha=1.839$ . El objetivo es encontrar una aproximación de la raíz de $f$ el uso de iteración de punto fijo método tal que para cada punto inicial ($x_0$), la secuencia de $\{x_n\}$ tal que $x_{n+1} = g(x_n)$ converge al punto fijo de $g$, que es también la raíz de la $f$.

Yo:

Hemos aprendido un teorema que establece que si una función como $g$ tiene dos propiedades, a continuación, la secuencia realizada por siempre converge al punto fijo de la función, independientemente de que el punto inicial $x_0$. Las dos propiedades son:

1) $\text{Range}(g)\subseteq \text{Domain}(g) $

2) $\exists k \lt1 \quad \forall x\in \text{Domain}(g)\quad |g'(x)|<k$

Así, con este conocimiento, traté de encontrar una $g$ que mantiene estas condiciones, Pero yo no era un éxito. He intentado $g_1(x)=x^3-x^2-1$, $g_2(x)=\frac{x^2+1}{x^2-1}$ , $g_3(x)=\frac{x^3-1}{x+1}$. Pero ninguno de ellos funcionó.

Answer 1

Tenga en cuenta que para $x>0$, la ecuación es equivalente a $$x^2+x+1=x^3\Leftrightarrow x+1+\frac{1}{x}=x^2 \Leftrightarrow g(x)=x$$ donde $$g(x):=\sqrt{1+x+\frac{1}{x}}.$$ La función de $g$ es una contracción en $[1,+\infty)$ porque $g([1,+\infty))\subseteq [1,+\infty)$$x\geq 1$, $$0\leq g'(x)=\frac{1-\frac{1}{x^2}}{2\sqrt{1+x+\frac{1}{x}}}<\frac{1}{2\sqrt{3}}<0.2887.$$ Por lo tanto, para cualquier $x_0\geq 1$, la recurrencia de la secuencia de $x_{n+1} = g(x_n)$ converge al único punto fijo $\alpha$ (e $f(\alpha)=0$). En realidad también es $x_0\in(0,1)$ está bien porque $x_1=g(x_0)\geq 1$.

Por ejemplo, si $x_0=1$ $$x_1=1.73205,\; x_2=1.81917,\; x_3=1.83544,\; x_4=1.83855,\; x_5=1.83914.$$

Answer 2

En el escalar caso, el método de Newton se garantiza la convergencia a través de cualquier intervalo que contenga una raíz) donde la función es monótona creciente y cóncava (cambiar el signo de la función o el signo del argumento para los otros 3 casos, el cambio de aumento de la caída o de convexa a cóncava). Entonces, si el punto inicial es la izquierda de la raíz, que tiene un negativo de la función de valor, la raíz de la tangente siempre va a venir de nuevo se encuentran a la izquierda de la raíz de la función, dando un aumento de la secuencia de iteración puntos que eventualmente converge cuadráticamente.

Para un polinomio con exactamente un cambio de signo en la secuencia de coeficientes de esta situación puede obtenerse dividiendo con una potencia de $x$, de modo que en el resultado positivo de poderes positivos y los coeficientes de las potencias negativas negativo de los coeficientes. En el presente caso, esto para dar a la función $$h(x)=f(x)/x^3=1-x^{-1}-x^{-2}-x^{-3}$$ donde cada término es monótonamente creciente y cóncava sobre el positivo de la mitad del eje, lo que implica la misma propiedad para la plena expresión. Uno puede fácilmente confirmar que el valor de la función en $x=1$ también $x=\frac32$ es negatve, dando el intervalo de $(0,\frac32)$ para los valores iniciales.

El método de Newton para $h$ da la iteración de punto fijo \begin{align} x_+=g(x)&=x-\frac{h(x)}{h'(x)}\\[.5em] &=x-\frac{1-x^{-1}-x^{-2}-x^{-3}}{x^{-2}+2x^{-3}+3x^{-4}}\\[.5em] &=x-x\frac{x^3-x^{2}-x-1}{x^{2}+2x+3}\\[.5em] &=x\cdot\frac{-x^3+2x^2+3x+4}{x^2+2x+3}\\[.5em] \end{align}

La iteración a partir de $x_0=1.2345$ arbitrarios como valor inicial da

x[ 0]= 1.234500000000000, f(x[ 0])=-1.877124286375000
x[ 1]= 1.565876113606041, f(x[ 1])=-1.178365989290387
x[ 2]= 1.780838286905480, f(x[ 2])=-0.304499453179715
x[ 3]= 1.836551926465144, f(x[ 3])=-0.014926710896395
x[ 4]= 1.839280734591210, f(x[ 4])=-0.000032934773838
x[ 5]= 1.839286755184975, f(x[ 5])=-0.000000000159659
x[ 6]= 1.839286755214161, f(x[ 6])= 0.000000000000000

Answer 3

Sabiendo que la raíz está cerca de a $2$, la división con resto da $$f(x)=(x-2)(x^2+x+1)+1$$ que conduce a la iteración $$ x_{n+1}=g(x_n)=2-\frac1{1+x_n+x_n^2} $$ que converge para $x_0\ge1$.

---

Uno consigue la contracción en $[1,\infty)$ $$ |g(y)-g(x)|=\frac{|1+x+y|}{(1+x+x^2)(1+y+y^2)}\,|y-x|\le\frac1{(x+\frac1{1+x})(y+\frac1{1+y})}\,|y-x|\le\frac49\,|y-x|. $$ También se $g([1,∞))=[\frac53,2)\subset[1,∞)$.

---

Un ejemplo de iteración es

x[ 0]= 1.234500000000000, f(x[ 0])=-1.877124286375000
x[ 1]= 1.733935720599515, f(x[ 1])=-0.527333695696158
x[ 2]= 1.825798199731845, f(x[ 2])=-0.072967640174318
x[ 3]= 1.837644870408343, f(x[ 3])=-0.008969516018651
x[ 4]= 1.839088171630494, f(x[ 4])=-0.001086144304223
x[ 5]= 1.839262755473114, f(x[ 5])=-0.000131284472260
x[ 6]= 1.839283855007393, f(x[ 6])=-0.000015865119096
x[ 7]= 1.839286404747722, f(x[ 7])=-0.000001917174861
x[ 8]= 1.839286712863196, f(x[ 8])=-0.000000231674756
x[ 9]= 1.839286750096399, f(x[ 9])=-0.000000027995971
x[10]= 1.839286754595722, f(x[10])=-0.000000003383080
x[11]= 1.839286755139428, f(x[11])=-0.000000000408817
x[12]= 1.839286755205130, f(x[12])=-0.000000000049402
x[13]= 1.839286755213070, f(x[13])=-0.000000000005970
x[14]= 1.839286755214029, f(x[14])=-0.000000000000721
x[15]= 1.839286755214145, f(x[15])=-0.000000000000087
x[16]= 1.839286755214159, f(x[16])=-0.000000000000011
x[17]= 1.839286755214161, f(x[17])=-0.000000000000001

---

El uso de Aitken del delta del cuadrado de las velocidades de iteración de este nuevo convergencia cuadrática utilizando $$x_{n+1}=x_n-\frac{(g(x_n))-x_n)^2}{g(g(x_n)-2g(x_n)+x_n}$$ shortening the example iteration to

x[ 0]= 1.234500000000000, f(x[ 0])=-1.877124286375000
x[ 1]= 1.846502981630578, f(x[ 1])= 0.039710950038240
x[ 2]= 1.839287216927013, f(x[ 2])= 0.000002525733614
x[ 3]= 1.839286755214163, f(x[ 3])= 0.000000000000010
x[ 4]= 1.839286755214161, f(x[ 4])= 0.000000000000000

Note that here the third step using 9 evaluations of $g$ es tan bueno como el 16 de paso de la iteración original.