El problema de encontrar soluciones a un sistema de n ecuaciones algebraicas o trascendentales no lineales con n incógnitas de la forma

ampliamente considerado en la práctica informática. Pueden surgir sistemas de ecuaciones similares, por ejemplo, durante el modelado numérico de sistemas físicos no lineales en la etapa de búsqueda de sus estados estacionarios. En varios casos, los sistemas de la forma (6.1) se obtienen indirectamente, en el proceso de resolución de algún otro problema computacional. Por ejemplo, al intentar minimizar una función de varias variables, puedes buscar aquellos puntos en el espacio multidimensional donde el gradiente de la función es cero. En este caso, es necesario resolver el sistema de ecuaciones (6.1) con los lados izquierdos: proyecciones del gradiente sobre los ejes de coordenadas.

En notación vectorial, el sistema (6.1) se puede escribir de una forma más compacta

columna vectorial de funciones, el símbolo () T denota la operación de transponición

Encontrar soluciones a un sistema de ecuaciones no lineales es una tarea mucho más compleja que resolver una única ecuación no lineal. Sin embargo, varios métodos iterativos para resolver ecuaciones no lineales pueden extenderse a sistemas de ecuaciones no lineales.

Método de iteración simple

El método de iteración simple para sistemas de ecuaciones no lineales es esencialmente una generalización del método del mismo nombre para una ecuación. Se basa en el hecho de que el sistema de ecuaciones (6.1) se reduce a la forma

x 1= g 1(x 1, x 2, … , x n) , x 2= g 2(x 1, x 2, … , x n) ,

……………………

x norte = gramo norte (x 1, x 2,…, x norte),

y las iteraciones se llevan a cabo de acuerdo con las fórmulas

x 1 (k + 1 )= g 1 (x 1 (k ), x 2 (k ), ... , x n (k )), x 2 (k + 1 )= g 2 (x 1 (k ), x 2 (k ), … , x n (k )) ,

……………………………

x norte (k + 1)= g norte (x 1 (k), x 2 (k), ..., x norte (k)).

Aquí el superíndice indica el número de aproximación. El proceso iterativo (6.3) comienza con una aproximación inicial.

(x 1 (0) ,x 2 (0) ,… ,x n (0) ) y continuar hasta que los módulos de incremento

todos los argumentos después de una k-iteración no serán menores que el valor dado ε : x i (k + 1 ) − x i (k )< ε дляi = 1,2,… ,n .

Aunque el método de iteración simple conduce directamente a una solución y es fácil de programar, tiene dos desventajas importantes. Uno de ellos es la convergencia lenta. Otra es que si la aproximación inicial se elige lejos de la solución verdadera (X 1,X 2,…,X n), entonces la convergencia

El método no está garantizado. Está claro que el problema de elegir una aproximación inicial, que no es simple ni siquiera para una ecuación, se vuelve muy complejo para sistemas no lineales.

Resolver un sistema de ecuaciones no lineales:

No existen métodos directos para resolver sistemas no lineales de forma general. Sólo en algunos casos se puede resolver directamente el sistema (4.1). Por ejemplo, en el caso de dos ecuaciones, a veces es posible expresar una incógnita en términos de la otra y así reducir el problema a resolver una ecuación no lineal con respecto a una incógnita.

Los métodos iterativos se suelen utilizar para resolver sistemas de ecuaciones no lineales.

El método de Newton.

En el caso de una ecuación F(x) = 0, el algoritmo del método de Newton se obtuvo fácilmente escribiendo las ecuaciones tangentes a la curva y = F(x). El método de Newton para sistemas de ecuaciones se basa en el uso de la expansión de funciones F 1 (x 1 ...x n) en una serie de Taylor, y los términos que contienen

Las derivadas de segundo orden (y de orden superior) existentes se descartan. Sean los valores aproximados de las incógnitas del sistema (4.1) iguales a

responsable a 1 ,a 2 ,....,a n . La tarea es encontrar los incrementos (por

Expandamos los lados izquierdos de las ecuaciones (4.1) teniendo en cuenta el desarrollo de la serie de Taylor, limitándonos solo a los términos lineales de la relación

Sustituyendo en el sistema (4.1), obtenemos el siguiente sistema de ecuaciones algebraicas lineales para incrementos:

x 2 = un 2, …x norte = un norte.

El determinante del sistema (4.3) es el jacobiano:

… … … …

∂ F n… … ∂ F n∂ x 1 ∂ x n

x 1 = un 1,

Para que exista una solución única para el sistema, el jacobiano debe ser distinto de cero en cada iteración.

Así, el proceso iterativo de resolución de un sistema de ecuaciones por el método de Newton consiste en determinar los incrementos x 1 , x 2 , ..., x n a los valores de las incógnitas en cada iteración resolviendo el sistema de ecuaciones algebraicas lineales ( 4.3). El conteo se detiene si todos los incrementos se vuelven pequeños en valor absoluto: maxx i< ε . В ме-

En el método de Newton, una elección exitosa de la aproximación inicial también es importante para asegurar una buena convergencia. La convergencia se deteriora a medida que aumenta el número de ecuaciones en el sistema.

Como ejemplo, considere usar el método de Newton para resolver un sistema de dos ecuaciones:

∂ ∂ F 1.x

Las cantidades del lado derecho se calculan en x = a,y = b.

Por ejemplo:

Establezcamos la tarea de encontrar. válido raíces de esta ecuación.

¡Y definitivamente los hay! - de artículos sobre gráficas de funciones Y ecuaciones de matemáticas superiores sabes muy bien cual es el horario función polinómica grado impar cruza el eje al menos una vez, por lo tanto nuestra ecuación tiene al menos una raíz real. Uno. O dos. O tres.

En primer lugar, se ruega comprobar la disponibilidad. racional raíces. De acuerdo a teorema correspondiente, sólo los números 1, –1, 3, –3 pueden reclamar este “título”, y mediante sustitución directa es fácil asegurarse de que ninguno de ellos “se adapte”. Así, los valores irracionales permanecen. Se pueden encontrar las raíces irracionales de un polinomio de grado 3 exactamente (expresado a través de radicales) utilizando el llamado Fórmulas cardano Sin embargo, este método es bastante engorroso. Pero para los polinomios de quinto grado y superiores no existe ningún método analítico general y, además, en la práctica existen muchas otras ecuaciones en las que valores exactos es imposible obtener raíces reales (aunque existen).

Sin embargo, en aplicación (por ejemplo, ingeniería) problemas, es más que aceptable utilizar valores aproximados calculados con cierta precisión.

Establezcamos la precisión de nuestro ejemplo. ¿Qué significa? Esto significa que necesitamos encontrar TAL valor aproximado de la raíz (raíces) en el que nosotros tenemos la garantía de equivocarnos por no más de 0,001 (una milésima) .

Está absolutamente claro que la solución no se puede iniciar “al azar” y por lo tanto en el primer paso las raíces separado. Separar una raíz significa encontrar un segmento suficientemente pequeño (generalmente único) al que pertenece esta raíz y en el que no hay otras raíces. Lo más sencillo y accesible. método gráfico de separación de raíces. vamos a construir punto por punto gráfica de una función :

Del dibujo se deduce que la ecuación, aparentemente, tiene una única raíz real perteneciente al segmento. Al final de este intervalo la función toma valores de diferentes signos: , y del hecho continuidad de la función en el segmento Una forma elemental de aclarar la raíz es inmediatamente visible: dividimos el intervalo por la mitad y seleccionamos el segmento en cuyos extremos la función toma signos diferentes. En este caso, obviamente se trata de un segmento. Dividimos el intervalo resultante por la mitad y nuevamente seleccionamos el segmento de "signo diferente". Etcétera. Estas acciones secuenciales se denominan iteraciones. En este caso, se deben llevar a cabo hasta que la longitud del segmento sea menos del doble de la precisión del cálculo, y se debe elegir la mitad del último segmento de "signo diferente" como valor aproximado de la raíz.

El esquema considerado recibió un nombre natural: método de media división. Y la desventaja de este método es la velocidad. Despacio. Muy lento. Habrá demasiadas iteraciones antes de que alcancemos la precisión requerida. Con el desarrollo de la tecnología informática, esto, por supuesto, no es un problema, pero las matemáticas son para las matemáticas, para buscar las soluciones más racionales.

Y una de las formas más efectivas de encontrar el valor aproximado de la raíz es precisamente método tangente. La breve esencia geométrica del método es la siguiente: primero, utilizando un criterio especial (más sobre eso un poco más adelante) Se selecciona uno de los extremos del segmento. Este fin se llama inicial aproximación de la raíz, en nuestro ejemplo: . Ahora dibujamos una tangente a la gráfica de la función. en la abscisa (punto azul y tangente violeta):

Esta tangente cruzó el eje x en el punto amarillo, y observe que en el primer paso casi hemos “llegado a la raíz”. será primero enfoque de raíz. A continuación, bajamos la perpendicular amarilla a la gráfica de la función y “llegamos” al punto naranja. ¡Nuevamente dibujamos una tangente a través del punto naranja, que cruzará el eje aún más cerca de la raíz! Etcétera. No es difícil entender que usando el método tangente, nos acercamos a la meta a pasos agigantados, y para lograr la precisión se necesitarán literalmente varias iteraciones.

Dado que la tangente se define mediante derivada de la función, entonces esta lección terminó en la sección “Derivados” como una de sus aplicaciones. Y sin entrar en detalles justificación teórica del método, Consideraré el aspecto técnico del problema. En la práctica, el problema descrito anteriormente se presenta aproximadamente en la siguiente formulación:

Ejemplo 1

Usando el método gráfico, encuentre el intervalo en el que se encuentra la raíz real de la ecuación. Utilizando el método de Newton, obtenga un valor aproximado de la raíz con una precisión de 0,001

Aquí hay una “versión sencilla” de la tarea, en la que se indica inmediatamente la presencia de una única raíz válida.

Solución: en el primer paso la raíz debe separarse gráficamente. Esto se puede hacer trazando (ver ilustraciones arriba), pero este enfoque tiene una serie de desventajas. En primer lugar, no es un hecho que el gráfico sea simple. (no lo sabemos de antemano) y el software no siempre está a mano. Y en segundo lugar (corolario del 1º), con una probabilidad considerable el resultado ni siquiera será un dibujo esquemático, sino un dibujo aproximado, lo cual, por supuesto, no es bueno.

Bueno, ¿por qué necesitamos dificultades innecesarias? imaginemos ecuación en el formulario, construya gráficas CUIDADOSAMENTE y marque la raíz en el dibujo (coordenada “X” del punto de intersección de las gráficas):

Ventaja obvia este método es que las gráficas de estas funciones se construyen a mano con mucha más precisión y rapidez. Por cierto, tenga en cuenta que derecho cruzado parábola cúbica en un solo punto, lo que significa que la ecuación propuesta en realidad tiene una sola raíz real. Confía, pero verifica ;-)

Entonces, nuestro "cliente" pertenece al segmento y "a ojo" es aproximadamente igual a 0,65-0,7.

En el segundo paso necesito elegir aproximación inicial raíz Generalmente este es uno de los extremos del segmento. La aproximación inicial debe satisfacer la siguiente condición:

encontremos primero Y segundo funciones derivadas :

y verifique el extremo izquierdo del segmento:

Por tanto, el cero “no encajaba”.

Comprobando el extremo derecho del segmento:

- ¡Todo está bien! Elegimos como aproximación inicial.

En el tercer paso El camino a la raíz nos espera. Cada aproximación de raíz posterior se calcula a partir de los datos anteriores utilizando la siguiente recurrente fórmulas:

El proceso finaliza cuando se cumple la condición, donde hay una precisión de cálculo predeterminada. Como resultado, se toma la aproximación “nésima” como valor aproximado de la raíz: .

Los siguientes son los cálculos de rutina:

(El redondeo se suele realizar a 5-6 decimales)

Dado que el valor obtenido es mayor que , se procede a la 1ª aproximación de la raíz:

Calculamos:

, por lo que es necesario pasar a la segunda aproximación:

Pasemos a la siguiente ronda:

, por lo tanto, se completan las iteraciones, y la 2ª aproximación debe tomarse como el valor aproximado de la raíz, que, de acuerdo con la precisión dada, debe redondearse a una milésima:

En la práctica, es conveniente ingresar los resultados de los cálculos en una tabla; para acortar un poco la entrada, una fracción a menudo se denota por:

Si es posible, es mejor realizar los cálculos usted mismo en Excel; es mucho más conveniente y rápido:

Respuesta: precisión de 0,001

Permítanme recordarles que esta frase implica el hecho de que cometimos un error en nuestra evaluación. verdadero significado raíz en no más de 0,001. Quienes tengan dudas pueden tomar una calculadora y nuevamente sustituir el valor aproximado de 0,674 en el lado izquierdo de la ecuación.

Ahora "escaneemos" la columna derecha de la tabla de arriba a abajo y observemos que los valores disminuyen constantemente en valor absoluto. Este efecto se llama convergencia un método que nos permite calcular la raíz con una precisión arbitrariamente alta. Pero la convergencia no siempre se produce: está garantizada una serie de condiciones, sobre el cual guardé silencio. En particular, el segmento en el que se aísla la raíz debe ser lo suficientemente pequeño– de lo contrario los valores cambiarán aleatoriamente y no podremos completar el algoritmo.

¿Qué hacer en tales casos? Comprobar que se cumplen las condiciones especificadas. (ver enlace arriba) y, si es necesario, reducir el segmento. Entonces, relativamente hablando, si en el ejemplo analizado el intervalo no nos convenía, entonces deberíamos considerar, por ejemplo, el segmento. En la práctica, me he encontrado con casos similares.¡Y esta técnica realmente ayuda! Se debe hacer lo mismo si ambos extremos del segmento "ancho" no cumplen la condición (es decir, ninguno de ellos es adecuado como aproximación inicial).

Pero normalmente todo funciona como un reloj, aunque no sin inconvenientes:

Ejemplo 2

Determinar gráficamente el número de raíces reales de la ecuación, separar estas raíces y, utilizando el método de Newton, encontrar valores aproximados de las raíces con precisión.

La condición del problema se ha vuelto notablemente más estricta: en primer lugar, contiene un fuerte indicio de que la ecuación no tiene una única raíz, en segundo lugar, ha aumentado el requisito de precisión y, en tercer lugar, con la gráfica de la función. mucho más difícil de afrontar.

Y por lo tanto solución Comencemos con un truco para ahorrar: imagina la ecuación en la forma y dibuja gráficas:


Del dibujo se deduce que nuestra ecuación tiene dos raíces reales:

El algoritmo, como comprenderá, debe "ponerse en marcha" dos veces. Pero esto ocurre incluso en los casos más graves; a veces es necesario examinar 3-4 raíces.

1) Utilizando criterio Averigüemos qué extremo del segmento elegir como aproximación inicial de la primera raíz. Encontrar derivadas de funciones. :

Probando el extremo izquierdo del segmento:

- ¡Subió!

Por tanto, es una aproximación inicial.

Refinaremos la raíz usando el método de Newton usando la fórmula recurrente:
- hasta la fracción módulo no será menor que la precisión requerida:

Y aquí la palabra “módulo” adquiere una importancia no ilusoria, ya que los valores son negativos:


Por la misma razón, se debe prestar especial atención al pasar a cada siguiente aproximación:

A pesar de los requisitos bastante altos de precisión, el proceso nuevamente terminó en la segunda aproximación: , por lo tanto:

Precisión de 0,0001

2) Encontremos el valor aproximado de la raíz.

Revisamos el extremo izquierdo del segmento en busca de piojos:

, por lo tanto, no es adecuado como aproximación inicial.

El método de Newton (también conocido como método tangente) es un método numérico iterativo para encontrar la raíz (cero) de una función determinada. El método fue propuesto por primera vez por el físico, matemático y astrónomo inglés Isaac Newton (1643-1727), bajo cuyo nombre se hizo famoso.

El método fue descrito por Isaac Newton en el manuscrito De analysi per aequationes numero terminorum infinitas (lat. .Acerca de análisis por ecuaciones de series infinitas), dirigida en 1669 a Barrow, y en la obra De metodis fluxionum et serierum infinitarum (latín: El método de las fluxiones y las series infinitas) o Geometria analytica ( lat.analítica geometría) en las obras completas de Newton, que fue escrita en 1671. Sin embargo, la descripción del método difería significativamente de su presentación actual: Newton aplicó su método exclusivamente a polinomios. No calculó aproximaciones sucesivas de x n, sino una secuencia de polinomios y como resultado obtuvo una solución aproximada de x.

El método fue publicado por primera vez en el tratado Álgebra de John Wallis en 1685, a petición de quien fue descrito brevemente por el propio Newton. En 1690, Joseph Raphson publicó una descripción simplificada en su obra Analysis aequationum universalis (lat. Análisis general de ecuaciones). Raphson vio el método de Newton como puramente algebraico y limitó su uso a polinomios, pero describió el método basado en aproximaciones sucesivas x n en lugar de la secuencia de polinomios más difícil de entender utilizada por Newton.

Finalmente, en 1740, Thomas Simpson describió el método de Newton como un método iterativo de primer orden para resolver ecuaciones no lineales utilizando derivadas como se describe aquí. En la misma publicación, Simpson generalizó el método al caso de un sistema de dos ecuaciones y señaló que el método de Newton también se puede aplicar para resolver problemas de optimización encontrando el cero de la derivada o gradiente.

De acuerdo con este método, la tarea de encontrar la raíz de una función se reduce a la tarea de encontrar el punto de intersección con el eje x de la tangente trazada a la gráfica de la función.

Fig.1 . Gráfico de cambio de función

Una recta tangente trazada en cualquier punto a la gráfica de una función está determinada por la derivada de esta función en el punto considerado, que a su vez está determinada por la tangente del ángulo α (). El punto de intersección de la tangente con el eje x se determina con base en la siguiente relación en un triángulo rectángulo: tangente del ánguloen un triángulo rectángulo está determinada por la relación entre el lado opuesto y el lado adyacente del triángulo. Así, en cada paso, se construye una tangente a la gráfica de la función en el punto de la siguiente aproximación. . Punto de intersección de la tangente con el eje. Buey será el siguiente punto de aproximación. De acuerdo con el método considerado, calcular el valor aproximado de la raíz eni-las iteraciones se realizan según la fórmula:

La pendiente de la línea recta se ajusta en cada paso de la mejor manera posible, sin embargo, se debe prestar atención al hecho de que el algoritmo no tiene en cuenta la curvatura del gráfico y, por lo tanto, durante el proceso de cálculo permanece desconocida. en qué dirección puede desviarse la gráfica.

La condición para el final del proceso iterativo es el cumplimiento de la siguiente condición:

Dónde ˗ error permisible en la determinación de la raíz.

El método tiene convergencia cuadrática. La tasa de convergencia cuadrática significa que el número de signos correctos en la aproximación se duplica con cada iteración.

Justificación matemática

Sea dada una función real, que es definido y continuo en el área considerada. Es necesario encontrar la raíz real de la función en cuestión.

La derivación de la ecuación se basa en el método de iteraciones simples, según el cual la ecuación se reduce a una ecuación equivalente para cualquier función. Introduzcamos el concepto de mapeo de contracción, que está definido por la relación.

Para la mejor convergencia del método, la condición debe cumplirse en el punto de la siguiente aproximación. Este requisito significa que la raíz de la función debe corresponder al extremo de la función.

Derivada del mapa de contracciónse define de la siguiente manera:

Expresemos la variable de esta expresión.sujeto a la declaración previamente aceptada de que cuando sea necesario para asegurar la condición. Como resultado, obtenemos una expresión para definir la variable:

Teniendo esto en cuenta, la función de compresión es la siguiente:

Así, el algoritmo para encontrar una solución numérica a la ecuación se reduce a un procedimiento de cálculo iterativo:

Algoritmo para encontrar la raíz de una ecuación no lineal usando el método

1. Establecer el punto inicial del valor aproximado de la raíz de la función., así como el error de cálculo (número positivo pequeño) y el paso de iteración inicial ().

2. Calcule el valor aproximado de la raíz de la función de acuerdo con la fórmula:

3. Comprobamos que el valor aproximado de la raíz tenga la precisión especificada, en el caso de:

Si la diferencia entre dos aproximaciones sucesivas es menor que la precisión especificada, entonces el proceso iterativo finaliza.

Si la diferencia entre dos aproximaciones sucesivas no alcanza la precisión requerida, entonces es necesario continuar el proceso iterativo y pasar al paso 2 del algoritmo considerado.

Ejemplo de resolución de ecuaciones.

por metodoNewton para una ecuación con una variable

Como ejemplo, considere resolver una ecuación no lineal usando el métodoNewton para una ecuación con una variable. La raíz debe encontrarse con precisión como primera aproximación..

Opción para resolver una ecuación no lineal en un paquete de softwareMatemáticasCADpresentado en la Figura 3.

Los resultados del cálculo, es decir, la dinámica de los cambios en el valor aproximado de la raíz, así como los errores de cálculo según el paso de iteración, se presentan en forma gráfica (ver Fig. 2).

Fig.2. Resultados del cálculo utilizando el método de Newton para una ecuación con una variable

Para garantizar la precisión especificada al buscar un valor aproximado de la raíz de la ecuación en el rango, es necesario realizar 4 iteraciones. En el último paso de la iteración, el valor aproximado de la raíz de la ecuación no lineal estará determinado por el valor: .

Fig.3 . Listado de programas enMatemáticasCad

Modificaciones del método de Newton para una ecuación con una variable

Existen varias modificaciones del método de Newton que tienen como objetivo simplificar el proceso computacional.

Método de Newton simplificado

De acuerdo con el método de Newton, es necesario calcular la derivada de la función f(x) en cada paso de iteración, lo que conduce a un aumento de los costes computacionales. Para reducir los costos asociados con el cálculo de la derivada en cada paso de cálculo, puede reemplazar la derivada f'(x n) en el punto x n de la fórmula con la derivada f'(x 0) en el punto x 0. De acuerdo con este método de cálculo, el valor aproximado de la raíz se determina mediante la siguiente fórmula:Método de Newton modificado

método de diferencia de newton

Como resultado, el valor aproximado de la raíz de la función f(x) estará determinado por la expresión del método de diferencias de Newton:

El método de dos pasos de Newton

De acuerdo con el método de Newton, es necesario calcular la derivada de la función f(x) en cada paso de iteración, lo que no siempre es conveniente y, a veces, prácticamente imposible. Este método le permite reemplazar la derivada de una función con una razón de diferencia (valor aproximado):

Como resultado, el valor aproximado de la raíz de la función f(x) vendrá determinado por la siguiente expresión:

Dónde

Fig.5 . El método de dos pasos de Newton

El método de la secante es un método de dos pasos, es decir, una nueva aproximacióndeterminado por las dos iteraciones anteriores Y . El método debe especificar dos aproximaciones iniciales. Y . La tasa de convergencia del método será lineal.

• Atrás
• Adelante

Para agregar su comentario al artículo, regístrese en el sitio.

Agencia Federal para la Educación

Universidad Estatal de Turismo y Negocios Resorts de Sochi

Facultad de Tecnologías de la Información y Matemáticas

Departamento de Matemáticas Generales

Trabajo de curso en la disciplina.

"Métodos numéricos"

"El método de Newton y sus modificaciones para la resolución de sistemas de ecuaciones no lineales"

Terminado:

estudiante de 3er año

grupos 06-INF

Lavrenko M.V.

Comprobado:

profesor asociado, candidato

ciencias pedagógicas

En relación con el desarrollo de nuevas tecnologías informáticas, la práctica de la ingeniería moderna se enfrenta cada vez más a problemas matemáticos cuya solución exacta es muy difícil o imposible de obtener. En estos casos se suele recurrir a uno u otro cálculo aproximado. Es por eso que los métodos aproximados y numéricos de análisis matemático se han desarrollado ampliamente en los últimos años y han adquirido una importancia excepcional.

Este trabajo de curso examina el famoso método de Newton y su modificación para resolver sistemas de ecuaciones no lineales. Resolver sistemas de ecuaciones no lineales es uno de los problemas difíciles de las matemáticas computacionales. La dificultad es determinar si el sistema tiene una solución y, de ser así, cuántas. Se estudia la convergencia de los métodos básico y simplificado de Newton y el método obtenido del método de Newton mediante un proceso iterativo para la inversión aproximada de matrices de Jacobi.

También describe brevemente: los métodos de posición falsa, el método de la secante, el método Steffensen, que muchas veces resulta ser la mejor opción para resolver sistemas de ecuaciones no lineales que el método de la secante o el método de posición falsa.

El famoso método de Newton es uno de los métodos más eficaces para resolver una amplia variedad de problemas no lineales. La fórmula de cálculo del método se puede obtener mediante varios enfoques. Veamos dos de ellos.

1) Método tangente.

Derivemos la fórmula de cálculo del método para resolver la ecuación no lineal.

Ecuación de una tangente trazada a la gráfica de una función.

Suponiendo en igualdad (1.1)

Expresando de ello

Debido a esta interpretación geométrica, este método a menudo se llama método tangente .

Sea necesario resolver un sistema de ecuaciones.

funciones de valor real norte variables reales

este sistema (2.1) se puede escribir mediante una ecuación

relativo a la función vectorial F argumento vectorial x. Por tanto, el problema original puede considerarse como un problema sobre los ceros del mapa no lineal.

2) Método de linealización.

INSTITUCIÓN EDUCATIVA DEL ESTADO

"La Universidad Estatal de Transnistria lleva su nombre. TG Shevchenko"

Sucursal Rybnitsa

Departamento de Física, Matemáticas e Informática

Trabajo de curso

en la disciplina: “Taller de resolución de problemas en una computadora”

"El método de Newton para resolver ecuaciones no lineales"

Terminado:

estudiante de 3er año;

grupo 330

especialidades: “Informática”

con adicional especializándose en ingles

Nistor A.G..

Comprobado:

profesor Panchenko T. A.

La introducción de las computadoras en todas las esferas de la actividad humana requiere que especialistas de diversos perfiles dominen las habilidades de uso de la tecnología informática. Cada vez es mayor el nivel de formación de los estudiantes universitarios, quienes desde el primer año se familiarizan con el uso de computadoras y los métodos numéricos más simples, sin mencionar que en la implementación de trabajos de curso y proyectos de diploma, el uso de tecnología informática se convierte en la norma. en la gran mayoría de las universidades.

La tecnología informática se utiliza ahora no sólo en cálculos de ingeniería y ciencias económicas, sino también en especialidades tradicionalmente no matemáticas como la medicina, la lingüística y la psicología. En este sentido, se puede afirmar que el uso de la informática se ha generalizado. Ha surgido una gran categoría de especialistas: usuarios de computadoras que necesitan conocimientos sobre el uso de computadoras en su industria, habilidades para trabajar con software existente, así como para crear su propio software adaptado para resolver un problema específico. Y aquí las descripciones de lenguajes de programación de alto nivel y métodos numéricos ayudan al usuario.

Los métodos numéricos los desarrollan e investigan, por regla general, matemáticos altamente cualificados. Para la mayoría de los usuarios, la tarea principal es comprender las ideas, métodos, características y aplicaciones básicos. Sin embargo, los usuarios quieren trabajar con una computadora no sólo como una calculadora altamente inteligente, sino también como un asistente en el trabajo diario, un depósito de información de acceso rápido y ordenado, así como una fuente y procesador de información gráfica. Tengo la intención de demostrar todas estas funciones de una computadora moderna en este trabajo de curso.

Metas y objetivos.

El propósito de este trabajo de curso es estudiar e implementar en un producto de software la solución de ecuaciones no lineales utilizando el método de Newton. Este trabajo consta de tres secciones, conclusión y apéndice. La primera sección es teórica y contiene información general sobre el método de Newton. La segunda es la parte práctica. Aquí describimos el método de Newton, analizado con ejemplos específicos. El tercero está dedicado a probar el programa y analizar los resultados. Finalmente se presenta una conclusión sobre el trabajo realizado.

El propósito de este trabajo de curso es la implementación de software del método de Newton para la resolución de ecuaciones no lineales.

Para hacer esto, debe completar las siguientes tareas:

1. Estudiar la literatura necesaria.

2. Revisar los métodos existentes para resolver ecuaciones no lineales.

3. Estudiar el método de Newton para resolver ecuaciones no lineales.

4. Considere la solución de ecuaciones no lineales mediante el método de Newton utilizando ejemplos específicos.

5. Desarrolle un programa para resolver ecuaciones no lineales mediante el método de Newton.

6. Analizar los resultados.

Considere el problema de encontrar las raíces de una ecuación no lineal.

Las raíces de la ecuación (1) son aquellos valores de x que al sustituirlo lo convierten en una identidad. Sólo para las ecuaciones más simples es posible encontrar una solución en forma de fórmulas, es decir forma analítica. Más a menudo es necesario resolver ecuaciones utilizando métodos aproximados, los más extendidos entre los cuales, debido a la llegada de las computadoras, son los métodos numéricos.

El algoritmo para encontrar raíces mediante métodos aproximados se puede dividir en dos etapas. En una primera etapa se estudia la ubicación de las raíces y se realiza su separación. Se encuentra la región en la que hay una raíz de la ecuación o una aproximación inicial a la raíz x 0. La forma más sencilla de resolver este problema es examinar la gráfica de la función f(x). En el caso general, para solucionarlo es necesario utilizar todos los medios del análisis matemático.

La existencia de al menos una raíz de la ecuación (1) en el segmento encontrado se desprende de la condición de Bolzano:

f(a)*f(b)<0 (2)

Esto implica que la función f(x) es continua en este intervalo. Sin embargo, esta condición no responde a la pregunta sobre el número de raíces de la ecuación en un intervalo dado. Si al requisito de continuidad de una función se le suma el requisito de su monotonicidad, y esto se deriva de la constancia de signo de la primera derivada, entonces podemos afirmar la existencia de una única raíz en un segmento dado.

Al localizar raíces, también es importante conocer las propiedades básicas de este tipo de ecuación. Por ejemplo, recordemos algunas propiedades de las ecuaciones algebraicas:

¿Dónde están los coeficientes reales?

a) Una ecuación de grado n tiene n raíces, entre las que pueden haber tanto reales como complejas. Las raíces complejas forman pares conjugados complejos y, por lo tanto, la ecuación tiene un número par de dichas raíces. Si n es impar, existe al menos una raíz real.

b) El número de raíces reales positivas es menor o igual al número de signos variables en la secuencia de coeficientes. Reemplazar x con –x en la ecuación (3) nos permite estimar el número de raíces negativas de la misma manera.

En la segunda etapa de resolución de la ecuación (1), utilizando la aproximación inicial obtenida, se construye un proceso iterativo que permite refinar el valor de la raíz con una cierta precisión predeterminada. El proceso iterativo consiste en un refinamiento secuencial de la aproximación inicial. Cada uno de estos pasos se denomina iteración. Como resultado del proceso de iteración, se encuentra una secuencia de valores aproximados de las raíces de la ecuación. Si esta secuencia se acerca al valor verdadero de la raíz x a medida que n crece, entonces el proceso iterativo converge. Se dice que un proceso iterativo converge al menos al orden m si se cumple la siguiente condición:

, (4)

donde C>0 es una constante. Si m=1, entonces hablamos de convergencia de primer orden; m=2 - aproximadamente cuadrática, m=3 - aproximadamente convergencia cúbica.

Los ciclos iterativos finalizan si, para un error permitido determinado, se cumplen los criterios de desviaciones absolutas o relativas:

o una pequeña discrepancia:

Este trabajo está dedicado al estudio de un algoritmo para la resolución de ecuaciones no lineales utilizando el método de Newton.

1.1 Revisión de métodos existentes para resolver ecuaciones no lineales.

Existen muchos métodos diferentes para resolver ecuaciones no lineales, algunos de ellos se presentan a continuación:

1)método de iteración. Al resolver una ecuación no lineal usando el método de iteración, usaremos la ecuación escrita en la forma x=f(x). Se especifican el valor inicial del argumento x 0 y la precisión ε. La primera aproximación de la solución x 1 se encuentra a partir de la expresión x 1 =f(x 0), la segunda - x 2 =f(x 1), etc. En el caso general, encontramos la aproximación i+1 usando la fórmula xi+1 =f(xi). Repetimos este procedimiento hasta |f(xi)|>ε. Condición de convergencia del método de iteración |f"(x)|<1.

2)El método de Newton.. Al resolver una ecuación no lineal mediante el método de Newton, se especifican el valor inicial del argumento x 0 y la precisión ε. Luego, en el punto (x 0, F(x 0)) trazamos una tangente a la gráfica F(x) y determinamos el punto de intersección de la tangente con el eje x 1. En el punto (x 1, F(x 1)) construimos nuevamente una tangente, encontramos la siguiente aproximación de la solución deseada x 2, etc. Repetimos este procedimiento hasta |F(xi)| > ε. Para determinar el punto de intersección (i+1) de la tangente con el eje de abscisas utilizamos la siguiente fórmula x i+1 =x i -F(x i)\ F’(x i). Condición para la convergencia del método tangente F(x 0)∙F""(x)>0, etc.

3). Método de dicotomía. La técnica de solución se reduce a dividir gradualmente el intervalo de incertidumbre inicial por la mitad según la fórmula C k = a k + b k /2.

Para seleccionar el requerido de los dos segmentos resultantes, es necesario encontrar el valor de la función en los extremos de los segmentos resultantes y considerar aquel en el que la función cambiará de signo, es decir, la condición f ( a k) * f (en k) debe cumplirse<0.

El proceso de división del segmento se lleva a cabo hasta que la longitud del intervalo de incertidumbre actual sea menor que la precisión especificada, es decir

en a - a a< E. Тогда в качестве приближенного решения уравнения будет точка, соответствующая середине интервала неопределённости.

4). Método de acordes. La idea del método es que se construya una cuerda sobre el segmento, subtendiendo los extremos del arco de la gráfica de la función y=f(x), y el punto c, la intersección de la cuerda con la x- eje, se considera un valor aproximado de la raíz

c = a - (f(a)Х (a-b)) / (f(a) - f(b)),

c = b - (f(b)Х (a-b)) / (f(a) - f(b)).

La siguiente aproximación se busca en el intervalo o dependiendo de los signos de los valores de la función en los puntos a, b, c.

x* O, si f(c)H f(a) > 0;

x* O si f(c)Х f(b)< 0 .

Si f"(x) no cambia de signo a , entonces denotando c=x 1 y considerando aob como aproximación inicial, obtenemos fórmulas iterativas del método de la cuerda con un punto fijo derecho o izquierdo.

x 0 =a, x i+1 = x i - f(x i)(b-x i) / (f(b)-f(x i), con f "(x)Х f "(x) > 0;

x 0 =b, x i+1 = x i - f(x i)(x i -a) / (f(x i)-f(a), con f "(x)Х f "(x)< 0 .

La convergencia del método de las cuerdas es lineal.

1.2 Algoritmo del método de Newton

Construyamos un algoritmo eficaz para calcular las raíces de la ecuación. Dejemos que se dé la aproximación inicial. Calculemos el valor de la función y su derivada en este punto. Veamos una ilustración gráfica del método:

.

(8)

Siguiendo este proceso obtenemos la famosa fórmula de Newton:

(9)

Aquí está la función de subrutina recursiva más simple:

función X_Newt(x,eps:real):real;

y:=x-f(x)/f1(x);

si abs(f(x)) > eps

entonces X_Newt:=X_Newt(y,eps)

El método de Newton (tangentes) se caracteriza por una tasa de convergencia cuadrática, es decir En cada iteración, el número de signos correctos se duplica. Sin embargo, este método no siempre conduce al resultado deseado. Consideremos este tema con más detalle.

Transformemos la ecuación (1) en una ecuación equivalente de la forma:

En el caso del método tangente . Si se conoce la aproximación inicial a la raíz x=x 0, entonces encontraremos la siguiente aproximación a partir de la ecuación x 1 =g(x 0), entonces x 2 =g(x 1),... Continuando con este proceso, obtenemos la fórmula recurrente del método de iteración simple

xk+1 =g(xk) (11)

El proceso iterativo continúa hasta que se cumplan las condiciones (5-7).

¿El proceso computacional descrito conduce siempre a la solución deseada? ¿En qué condiciones convergerá? Para responder a estas preguntas, volvamos a la ilustración geométrica del método.

La raíz de la ecuación está representada por el punto de intersección de las funciones y=x e y=g(x). Como se puede ver en la Fig. 3 (a), si se cumple la condición, entonces el proceso converge; de ​​lo contrario, diverge (Fig. 3 (b)).

Entonces, para que el proceso iterativo sea convergente y conduzca al resultado deseado, se debe cumplir la siguiente condición:

La transición de la ecuación f(x)=0 a la ecuación x=g(x) se puede realizar de varias maneras. En este caso, es importante que la función seleccionada g(x) satisfaga la condición (12). Por ejemplo, si la función f(x) se multiplica por una constante arbitraria q y la variable x se suma a ambos lados de la ecuación (1), entonces g(x)=q*f(x)+x. Elijamos una constante q tal que la tasa de convergencia del algoritmo sea la más alta. si 1

El método de Newton tiene una alta tasa de convergencia, pero no siempre converge. La condición de convergencia, donde g(x) = x – f(x)/f’(x), se reduce al requisito.

En cálculos prácticos, es importante elegir el valor inicial lo más cercano posible al valor deseado e instalar una "protección de bucle" en el programa.

La desventaja del método es que en cada paso es necesario calcular no solo la función, sino también su derivada. Esto no siempre es conveniente. Una de las modificaciones del método de Newton es calcular la derivada sólo en la primera iteración:

(13)

Otro método de modificación es reemplazar la derivada con una diferencia finita.

(14)

Entonces (15)

El significado geométrico de este cambio en el algoritmo de Newton es que de la tangente llegamos a la secante. El método de la secante es inferior al método de Newton en términos de velocidad de convergencia, pero no requiere el cálculo de la derivada. Tenga en cuenta que las aproximaciones iniciales en el método de la secante pueden ubicarse en diferentes lados de la raíz o en el mismo lado.

Escribamos el algoritmo del método de Newton en forma general.

1. Establezca la aproximación inicial x (0) para que se cumpla la condición.

f(x (0))*f''(x (0))>0. (16)

Establezca un pequeño número positivo ε como precisión de los cálculos. Establecer k = 0.

2. Calcule x (k+1) usando la fórmula (9):

.

3. Si | x (k+1) - x (k) |< ε, то процесс вычисления прекратить и положить х* = x (k+1) . De lo contrario, aumente k en 1 (k = k + 1) y vaya al paso 2.

Resolvamos manualmente varias ecuaciones no lineales utilizando el método de Newton y luego comparamos los resultados con los obtenidos al implementar el producto de software.

Ejemplo 1

pecado x 2 + cosx 2 - 10x. = 0.

F’(x)=2x cosx 2 - 2x senx 2 - 10.

F’’(x)=2cosx 2 - 4x 2 senx 2 - 2senx 2 - 4x 2 cosx 2 = cosx 2 (2-4x 2) - senx 2 (2+4x 2).

Ahora, basándonos en la gráfica, tomemos la primera raíz aproximada y verifiquemos la condición (16): f(x (0)) * f’’(x (0)) > 0.

Sea x (0) = 0, 565, entonces f(0, 565)*f''(0, 565) = -4. 387 * (-0,342) = 1,5 > 0,

La condición se cumple, por lo que tomamos x (0) = 0,565.

De ello se deduce que la raíz de la ecuación es x = 0,101.

Ejemplo 2

Resuelve la ecuación usando el método de Newton.

porque x – e -x2/2 + x - 1 = 0

Los cálculos deben realizarse con una precisión de ε = 0,001.

Calculemos la primera derivada de la función.

F’(x) = 1 – sen x + x*e -x2/2 .

Ahora calculemos la segunda derivada de la función.

F''(x) = e -x2/2 *(1-x 2) – cos x.

Construyamos una gráfica aproximada de esta función.

Ahora, basándonos en la gráfica, tomemos la primera raíz aproximada y verifiquemos la condición (16): f(x (0)) * f’’(x (0)) > 0.

Sea x (0) = 2, entonces f(2)*f''(2) = 0,449 * 0,010 = 0,05 > 0,

La condición se cumple, por lo que tomamos x (0) = 2.

Ahora creemos una tabla de valores para resolver esta ecuación.

De ello se deduce que la raíz de la ecuación es x = 1,089.

Ejemplo 3

Resuelve la ecuación usando el método de Newton.

Los cálculos deben realizarse con una precisión de ε = 0,001.

Calculemos la primera derivada de la función.

F’(x) = 2*x + e -x .

Ahora calculemos la segunda derivada de la función.

F''(x) = 2 - e -x .

Construyamos una gráfica aproximada de esta función.

Ahora, basándonos en la gráfica, tomemos la primera raíz aproximada y verifiquemos la condición (16): f(x (0)) * f’’(x (0)) > 0.

Sea x (0) = 1, entonces f(2)*f’’(2) = 0. 632 * 1, 632 = 1, 031 > 0,

Ahora creemos una tabla de valores para resolver esta ecuación.

De ello se deduce que la raíz de la ecuación es x = 0,703.

Resuelve la ecuación usando el método de Newton.

porque x –e -x/2 +x-1=0.

Calculemos la primera derivada de la función.

F’(x) = -sen x + e -x/2 /2+1.

Ahora calculemos la segunda derivada de la función.

F''(x) = -cos x - e -x/2/4.

Construyamos una gráfica aproximada de esta función.

Ahora, basándonos en la gráfica, tomemos la primera raíz aproximada y verifiquemos la condición (16): f(x (0)) * f’’(x (0)) > 0.

Sea x (0) = 1, entonces f(2)*f''(2) = -0. 066 * (-0,692) = 0,046 > 0,

La condición se cumple, por lo que tomamos x (0) = 1.

Ahora creemos una tabla de valores para resolver esta ecuación.

De ello se deduce que la raíz de la ecuación es x = 1,162.

Ejemplo 5

Resuelve la ecuación usando el método de Newton.

2+e x - e -x =0.

Calculemos la primera derivada de la función.

F’(x) = e x +e -x .

Ahora calculemos la segunda derivada de la función.

F''(x) = e x -e -x .

Construyamos una gráfica aproximada de esta función.

Ahora, basándonos en la gráfica, tomemos la primera raíz aproximada y verifiquemos la condición (16): f(x (0)) * f’’(x (0)) > 0.

Sea x (0) = 1, entonces f(2)*f’’(2) = 0. 350 * 2, 350 = 0. 823 > 0,

La condición se cumple, por lo que tomamos x (0) = 1.

Ahora creemos una tabla de valores para resolver esta ecuación.

De ello se deduce que la raíz de la ecuación es x = 0,881.

3.1 Descripción del programa

Este programa está diseñado para funcionar en modo texto y gráfico. Consta del módulo Graph, Crt, tres funciones y tres procedimientos.

1. El módulo Crt está diseñado para proporcionar control sobre los modos de texto de la pantalla, códigos de teclado extendidos, colores, ventanas y sonido;

2. El módulo Gráfico está diseñado para proporcionar control sobre objetos gráficos;

3. procedimiento GrafInit: inicializa el modo de gráficos;

4. función VF – calcula el valor de la función;

5. función f1 – calcula el valor de la primera derivada de la función;

6. función X_Newt: implementa un algoritmo para resolver una ecuación usando el método de Newton.

7. procedimiento FGraf – implementa la construcción de una gráfica de una función dada f(x);

Ots=35: una constante que determina el número de puntos para sangría desde los límites del monitor;

fmin, fmax – valores máximo y mínimo de la función;

SetColor(4) – procedimiento que establece el color actual de un objeto gráfico usando una paleta, en este caso es rojo;

SetBkColor(9) es un procedimiento que establece el color de fondo actual usando una paleta, en este caso un color azul claro.

8. Procedimiento MaxMinF – calculará los valores máximo y mínimo de la función f(x).

Línea – procedimiento que dibuja una línea desde un punto con coordenadas (x1, y1) hasta un punto con coordenadas (x2, y2);

MoveTo: procedimiento que mueve el puntero (CP) a un punto con coordenadas (x, y);

TextColor(5) – un procedimiento que establece el color actual de los caracteres, en este caso es rosa;

Outtexty(x, y, 'string'): un procedimiento que genera una cadena que comienza en la posición (x, y)

CloseGraph es un procedimiento que cierra el sistema de gráficos.

3.2 Probar el programa

Para probar el programa tomaremos los ejemplos que se resolvieron en la parte práctica del trabajo para poder comparar los resultados y comprobar el correcto funcionamiento del programa.

1) pecado x 2 + cosx 2 - 10x. = 0.

Introduzca un = -1

Introduce b=1

= [-1, 1]

(salida del gráfico de funciones)

Obtenemos: x=0.0000002

2) porque x – e -x2/2 + x - 1 = 0.

Este programa calcula las raíces de una ecuación no lineal utilizando el método de Newton con precisión de eps y dibuja una gráfica aproximada de la función en el segmento.

Introduzca a = -3

Introduce b=3

= [-3, 3]

(salida del gráfico de funciones)

La raíz de la ecuación encontrada por el método de Newton:

Comprobemos sustituyendo la respuesta resultante en la ecuación.

Obtenemos: x=-0.0000000

3) x 2 - e -x = 0.

Este programa calcula las raíces de una ecuación no lineal utilizando el método de Newton con precisión de eps y dibuja una gráfica aproximada de la función en el segmento.

Introduzca un = -1

Introduce b=1

= [-1, 1]

Introduzca la precisión del cálculo eps=0. 01

(salida del gráfico de funciones)

La raíz de la ecuación encontrada por el método de Newton:

Comprobemos sustituyendo la respuesta resultante en la ecuación.

Obtenemos: x=0.0000000

4) porque x –e -x/2 +x-1=0.

Este programa calcula las raíces de una ecuación no lineal utilizando el método de Newton con precisión de eps y dibuja una gráfica aproximada de la función en el segmento.

Introduzca a = -1,5

Introduce b=1,5

= [-1,5, 1,5 ]

Introduzca la precisión del cálculo eps=0. 001

(salida del gráfico de funciones)

La raíz de la ecuación encontrada por el método de Newton:

Comprobemos sustituyendo la respuesta resultante en la ecuación.

Obtenemos: x=0.0008180

5) -2+e x - e -x =0.

Este programa calcula las raíces de una ecuación no lineal utilizando el método de Newton con precisión de eps y dibuja una gráfica aproximada de la función en el segmento.

Introduzca a = -0,9

Introduce b=0,9

= [-0,9, 0,9]

Introduzca la precisión del cálculo eps=0. 001

(salida del gráfico de funciones)

La raíz de la ecuación encontrada por el método de Newton:

Comprobemos sustituyendo la respuesta resultante en la ecuación.

El objetivo del trabajo era crear un programa que calcule la raíz de una ecuación no lineal utilizando el método de Newton. En base a esto podemos concluir que el objetivo fue logrado, ya que para su implementación se resolvieron las siguientes tareas:

1. Se ha estudiado la literatura necesaria.

2. Se revisan los métodos existentes para resolver ecuaciones no lineales.

3. Se estudió el método de Newton para la resolución de ecuaciones no lineales.

4. Se considera mediante un ejemplo la solución de ecuaciones no lineales mediante el método de Newton.

5. El programa fue probado y depurado.

Lista de literatura usada

1. B.P. Demidovich, I.A. Fundamentos de la matemática computacional. – Moscú, ed. "Ciencia"; 1970.

2. V.M. Verzhbitsky. Métodos numéricos (álgebra lineal y ecuaciones no lineales). – Moscú, “Escuela Superior”; 2000.

3. N.S.Bakhvalov, A.V.Lapin, E.V.Chizhonkov. Métodos numéricos en problemas y ejercicios. – Moscú, “Escuela Superior”; 2000.

4. Matthews, John, G., Fink, Curtis, D. Métodos numéricos MATLAB, 3ª edición - Moscú, “Villas”; 2001.