¿Cuál es la diferencia entre Hensel la elevación y el método de Newton-Raphson método?

Question

Así, en el método de Newton-Raphson método de forma iterativa aproximar una raíz de un polinomio real, empezamos con una cruda aproximación $x_0 \in \mathbb{R}$ $f(x)=0$ donde $f(x) \in \mathbb{R}[x]$. Para la siguiente iteración $x_1$, ponemos a $x_1 = x_0 + \epsilon$, y queremos determinar $\epsilon$ para obtener una mejor aproximación. Para ello utilizamos una serie de Taylor y tomar una aproximación lineal, y equiparar $f(x_1)$ a 0 para obtener un valor de $\epsilon$. $$ f(x_1) = f(x_0 + \epsilon) = f(x_0) + \epsilon f'(x_0) + O(\epsilon^2) \approx f(x_0) + \epsilon f'(x_0)$$ $$ 0 = f(x_0) + \epsilon f'(x_0)$$ $$ \epsilon = - \frac{f(x_0)}{f'(x_0)}$$ $$ x_1 = x_0 - \frac{f(x_0)}{f'(x_0)}$$ Por supuesto, una condición necesaria aquí es que $f'(x_0) \neq 0$.

Ahora, en el caso de Hensel levantamiento de una raíz modulo $p$ $f(x) \in \mathbb{Z}[x]$ a una raíz modulo $p^2$, podemos hacer algo muy similar. Si $x_0 \in \mathbb{Z}$ es tal que $f(x_0) \equiv 0 \pmod p$$f'(x_0) \neq 0 \pmod p$,, de nuevo tomamos $x_1 = x_0 + p\epsilon$, ignorar todo pero primero los términos de orden por la que va modulo $p^2$ y encontrar$\epsilon$, equiparando $f(x_1)$ a cero. $$ f(x_1) = f(x_0 + p\epsilon) = f(x_0) + p\epsilon f'(x_0) + O(p^2\epsilon^2) $$ $$ 0 = f(x_0) + p\epsilon f'(x_0) \pmod {p^2} $$ $$ \epsilon = - \frac{f(x_0)}{pf'(x_0)}$$ $$ x_1 = x_0 - \frac{f(x_0)}{f'(x_0)}$$

Así, al igual que antes, terminamos ignorando los términos más allá del término lineal, y el $x_1$ que tenemos es casi la misma cosa, excepto que si conseguimos una fracción, pensamos de la misma (la división o a la inversa) como de funcionamiento dentro del anillo de $\mathbb{Z}/p^2\mathbb{Z}$ y se expresa como un número entero.

Así, excepto para el valor inicial (en Newton-Raphson empezamos a algunos (cualquiera) de crudo de aproximación, mientras que en Hensel elevación empezamos con una raíz modulo prime $p$), son los dos métodos esencialmente el mismo? No podemos obtener los ascensores modulo poderes superiores de $p$ simplemente por mirar la iteración en el método de Newton-Raphson método, si tan solo empezamos con una agradable candidato?

Answer 1

Hay un punto de vista muy general que relaciona el método de Newton y similares de aproximación sucesiva de planes como Hensel del lexema. Este es esencialmente el folclore, pero se ha vuelto más accesible recientemente debido a aplicaciones computacionales (por ejemplo, el polinomio factorización). Para localizar la literatura pertinente que usted puede comenzar con los trabajos revisados a continuación.

---

von zur Gathen, Joachim (3-TRNT-C) 85j:12012 12J20 65P05
Hensel y Newton métodos en la valoración de los anillos.
De matemáticas. Comp. 42 (1984), no. 166, 637--661.

Hensel del lexema es una herramienta fundamental en el estudio de ecuaciones algebraicas más $p$-ádico campos. En el folklore de la teoría de los números ha sido conocido por un largo el tiempo que Hensel y el método de Newton son formalmente el mismo (este comentario aparece en forma impresa en un artículo de D. J. Lewis publicó en un libro editado por W. J. LeVeque [Estudios en teoría de números, 25--75, ver pág. 29, Prentice-Hall, Englewood Cliffs, N. J., 1969; MR 39 #2699]).

Una versión generalizada de Hensel del lexema en la adecuada valoración de los anillos es contenido de N. Bourbaki del libro [de los Elementos de las matemáticas, de 23 años, Conmutativa álgebra (francés), véase el Capítulo III, Sección 4, Teorema 1 y el Teorema 2, Hermann, París, 1958; MR 20 #4576].

Este documento también aborda el estudio de Hensel del método en la valoración de los anillos y muestra que el método de Newton es un caso especial de Hensel. La presentación hace hincapié en la algorítmica punto de vista y es muy detallado y claro. El lineal y cuadrática de los casos de Hensel del lexema son tanto. El método de Newton se aplica a sistemas no lineales de ecuaciones diferenciales parciales. A continuación, el autor presenta un algoritmo para el cálculo de un menor distinto de cero vector en un no-Arquímedes valoración módulo. Estos resultados se aplican en los últimos la sección, que contiene un algoritmo para factorizar polinomios sobre un anillo con las valoraciones.

          Reviewed by Maurice Mignotte

---

Ribenboim, Paulo (3-QEN) 87a:12014 12J10 13A18
Formas equivalentes de Hensel del lexema.
De la exposición. De matemáticas. 3 (1985), no. 1, de 3, 24.

De la introducción: "El famoso Hensel del lema, que es el la piedra angular de la teoría de la $p$-ádico números, ha sido el objeto de extensos estudios. Sin embargo, nuestro objetivo en este trabajo no es el de describir la desarrollo de ideas y aplicaciones centradas alrededor de Hensel del lema, pero en lugar de examinar de cerca las distintas formulaciones que se encuentran en la literatura. Nosotros situarnos en el marco de la teoría de los valores de los campos y mostrar que Hensel del lexema es lógicamente equivalente a muchas proposiciones relativas a la número de extensiones de la valoración de extensiones algebraicas, o el levantamiento de de polinomios a partir de los residuos de campo, o la determinación de los ceros de una polinomio por un método que se remonta a Newton, o incluso a un geométricas formulación con relación a la mutua de la distancia entre los ceros de polinomios. Estos hechos son de una "folclórico" de la naturaleza, sin embargo, no hay evidencia completa de su equivalencia ha aparecido en cualquier papel.

"Este artículo está escrito en el nivel de investigación de los estudiantes."

          Reviewed by Antonio Jose Engler

---

Miola, A. (I-ROMA-I); Mora, T. (I-GENO) 90f:68096 68Q40 13A18 13J10 Constructivo levantamiento gradual de las estructuras: una visión unificada de Buchberger y Hensel métodos.
Aspectos computacionales de álgebra conmutativa.
J. Simbólico Comput. 6 (1988), no. 2-3, 305--322.

Un graduado de la estructura es un filtrado anillo conmutativo $A$, el cual es filtrado por un totalmente ordenado grupo y se ha graduado asociado anillo y un anillo la finalización. Los autores definen un proceso para resolver, en el anillo de finalización, un polinomio multivariante de ecuación en $A$ por aproximaciones sucesivas. Ellos discutir las condiciones en las que este proceso converge.

El interés principal de esta teoría es que Hensel de elevación, Buchberger del algoritmo para Grobner la base de los cálculos en el polinomio anillos y Hironaka del proceso de división por un estándar de base en anillos de poder formal de la serie son las instancias del proceso anterior. Por ejemplo, Hensel de elevación es un aproximados de resolución de $yz-a=0$, que necesita algunas condiciones en $a$ y en los valores iniciales de $y$ $z$ a ser convergente.

{Para toda la colección ver MR 89j:68004}.

          Reviewed by Daniel Lazard

Answer 2

Ellos son, de lejos, el mismo. La principal diferencia es que la iteración del método de Newton permanecer siempre aproximaciones, mientras que Hensel elevación es exacto en los valores que calcula. Como p-ádico de los números, la recorre de Hensel también son aproximaciones, pero su menor términos de orden se vuelve estacionario después de un número finito de iteraciones.

Así por ejemplo puede utilizar Hensel de elevación para calcular una potencia de expansión de la serie de algunos, la solución de un problema algebraico, y si este poder de la serie es en realidad una función racional, esto puede ser exactamente recuperado de la Hensel-energía producida en serie.