Derivación de la fórmula de cálculo para el método de iteración simple. Método de iteración simple

Por analogía con (2.1), el sistema (5.1) se puede representar de la siguiente forma equivalente:

donde g(x) es una función vectorial iterativa del argumento vectorial. Los sistemas de ecuaciones no lineales a menudo surgen directamente en la forma (5.2) (por ejemplo, en esquemas numéricos para ecuaciones diferenciales, en este caso no se requiere ningún esfuerzo adicional para transformar las ecuaciones (5.1) en el sistema (5.2); Si continuamos con la analogía con el método de iteración simple para una ecuación, entonces el proceso de iteración basado en la ecuación (5.2) se puede organizar de la siguiente manera:

• 1) algún vector inicial x ((,) e 5 o (x 0, A)(se supone que x* e 5„(x 0, A));
• 2) las aproximaciones posteriores se calculan mediante la fórmula

luego se completa el proceso de iteración y

Como antes, necesitamos descubrir bajo qué condiciones

Discutamos este tema realizando un análisis simple. Primero introducimos el error de la iésima aproximación como e(^ = x(i) - x*. Luego podemos escribir

Sustituyamos estas expresiones en (5.3) y expandamos g(x* + e (/i)) en potencias e(k> en la vecindad de x* como función del argumento vectorial (asumiendo que todas las derivadas parciales de la función g(x) son continuas). Teniendo en cuenta también que x* = g(x*), obtenemos

o en forma matricial

B = (bnm)= I (x*)1 - matriz de iteración.

Si la tasa de error ||е®|| es lo suficientemente pequeño, entonces el segundo término en el lado derecho de la expresión (5.4) puede despreciarse y luego coincide con la expresión (2.16). En consecuencia, la condición para la convergencia del proceso iterativo (5.3) cerca de la solución exacta se describe en el Teorema 3.1.

Convergencia del método de iteración simple. Condición necesaria y suficiente para la convergencia del proceso iterativo (5.3):

y una condición suficiente:

Estas condiciones tienen importancia más teórica que práctica, ya que no conocemos x'. Por analogía con (1.11), obtenemos una condición que puede resultar útil. Sea x* e 5 o (x 0, A) y la matriz jacobiana para la función g(x)

existe para todo x e S norte (x 0 , a) (tenga en cuenta que C(x*) = B). Si los elementos de la matriz C(x) satisfacen la desigualdad

para todo x e 5„(x 0, A), entonces la condición suficiente (5.5) también se cumple para cualquier norma matricial.

Ejemplo 5.1 (método de iteración simple) Considere el siguiente sistema de ecuaciones:

Una posibilidad de representar este sistema en forma equivalente (5.2) es expresar X de la primera ecuación y x2 de la segunda ecuación:

Entonces el esquema de iteración tiene la forma

La solución exacta es x* e 5„((2, 2), 1). Elijamos el vector inicial x (0) = (2,2) y ? pag = CT 5. Los resultados del cálculo se presentan en la tabla. 5.1.

Tabla 5.1

Estos resultados muestran que la convergencia es bastante lenta. Para obtener una característica cuantitativa de convergencia, realizamos un análisis simple, considerando x (1/) como una solución exacta. La matriz jacobiana C(x) para nuestra función iterativa tiene la forma

entonces la matriz B se estima aproximadamente como

Es fácil comprobar que no se cumplen ni la condición (5.5) ni la condición (5.6), pero se produce convergencia, ya que 5(B) ~ 0.8.

A menudo es posible acelerar la convergencia del método de iteración simple cambiando ligeramente el proceso de cálculo. La idea de esta modificación es muy sencilla: calcular PAG componentes del vector x(A+1) se puede utilizar no sólo (t = norte,..., norte), sino también los componentes ya calculados del siguiente vector de aproximación xk^ (/= 1,PAG - 1). Por tanto, el método de iteración simple modificado se puede representar como el siguiente esquema de iteración:

Si las aproximaciones generadas por el proceso iterativo (5.3) convergen, entonces el proceso iterativo (5.8) tiende a converger más rápido debido a un uso más completo de la información.

Ejemplo 5.2 (método de iteración simple modificado) La iteración simple modificada para el sistema (5.7) se representa como

Como antes, elegimos el vector inicial x (0) = (2, 2) y gramo r = = 10-5. Los resultados del cálculo se presentan en la tabla. 5.2.

Tabla 5.2

I El gran cambio en el orden de los cálculos llevó a reducir a la mitad el número de iteraciones y, por tanto, a la mitad el número de operaciones.

Reemplacemos la ecuación original por una equivalente y construyamos iteraciones de acuerdo con la regla . Por tanto, el método de iteración simple es un proceso iterativo de un solo paso. Para iniciar este proceso es necesario conocer la aproximación inicial. Averigüemos las condiciones para la convergencia del método y la elección de la aproximación inicial.

Boleto#29

método Seidel

El método de Seidel (a veces llamado método de Gauss-Seidel) es una modificación del método de iteración simple, que consiste en que al calcular la siguiente aproximación x (k+1) (ver fórmulas (1.13), (1.14)) su Los componentes ya obtenidos x 1 ( k+1) , ...,xi - 1 (k+1) se utilizan inmediatamente para calcular x i (k+1).

En notación de coordenadas, el método de Seidel tiene la forma:

X 1 (k+1) = c 11 x 1 (k) + c 12 x 2 (k) + ... + c 1n-1 x n-1 (k) + c 1n x n (k) + d 1
x 2 (k+1) = c 21 x 1 (k+1) + c 22 x 2 (k) + ... + c 2n-1 x n-1 (k) + c 2n x n (k) + d 2
...
x n (k+1) = c n1 x 1 (k+1) + c n2 x 2 (k+1) + ... + c nn-1 x n-1 (k+1) + c nn x n (k ) + dn
donde x (0) es una aproximación inicial a la solución.

Por lo tanto, el i-ésimo componente de la (k+1)-ésima aproximación se calcula mediante la fórmula

La condición para el final del proceso iterativo de Seidel cuando se logra la precisión ε en forma simplificada tiene la forma:

|| x (k+1) - x (k) || ≤ ε.

Boleto#30

método de pase

Para resolver sistemas A x = b con una matriz tridiagonal se utiliza con mayor frecuencia el método de barrido, que es una adaptación del método de Gauss para este caso.

Escribamos el sistema de ecuaciones.

re 1 x 1 + mi 1 x 2 = segundo 1
c 2 x 1 + re 2 x 2 + mi 2 x 3 = segundo 2
c 3 x 2 + re 3 x 3 + mi 3 x 4 = segundo 3
... ... ...
c n-1 x n-2 + d n-1 x n-1 + e n-1 x n = b n-1
c norte x n-1 + re norte x n = segundo norte

en forma matricial: A x = b donde

A =

Anotemos las fórmulas del método de barrido en el orden de su aplicación.

1. Trazo directo del método de barrido (cálculo de cantidades auxiliares):

2. Invertir el método de barrido (encontrar una solución):

Boleto#31

Método de iteración simple

La esencia del método de iteración simple es pasar de la ecuación

f(x)= 0 (*)

a la ecuación equivalente

X=φ(x). (**)

Esta transición se puede lograr de diferentes maneras, dependiendo del tipo. f(x). Por ejemplo, puedes poner

φ(x) = X+novio(x),(***)

Dónde b= constante, mientras que las raíces de la ecuación original no cambiarán.

Si se conoce la aproximación inicial a la raíz x0, entonces la nueva aproximación

x1=φx(0),

aquellos. esquema general del proceso iterativo:

xk+1=φ(xk).(****)

El criterio más sencillo para finalizar el proceso.

|x k +1 -x k |<ε.

Criterio de convergencia método de iteración simple:

si cerca de la raíz | φ/(x)| < 1, то итерации сходятся. Если указанное условие справедливо для любого X, entonces las iteraciones convergen para cualquier aproximación inicial.

Exploremos la elección de la constante. b desde el punto de vista de garantizar la máxima velocidad de convergencia. De acuerdo con el criterio de convergencia, la velocidad de convergencia más alta se proporciona cuando |φ/(x)| = 0. Al mismo tiempo, con base en (***), b = –1/f / (x), y la fórmula de iteración (****) entra en x i =x i-1 -f(x i-1)/f/ (x i-1).- aquellos. en la fórmula del método de Newton. Por tanto, el método de Newton es un caso especial del método de iteración simple, que proporciona la mayor velocidad de convergencia de todas las opciones posibles para elegir una función. φ(x).

Boleto#32

El método de Newton

La idea principal del método es la siguiente: se especifica una aproximación inicial cerca de la raíz hipotética, después de lo cual se construye una tangente a la función en estudio en el punto de aproximación, para lo cual se encuentra la intersección con el eje de abscisas. Este punto se toma como la siguiente aproximación. Y así sucesivamente hasta conseguir la precisión requerida.

Sea una función de valor real definida en un intervalo y diferenciable en él. Entonces la fórmula para el cálculo de aproximación iterativa se puede derivar de la siguiente manera:

donde α es el ángulo de inclinación de la tangente en el punto.

Por lo tanto, la expresión requerida para tiene la forma:

Boleto#33

Método de la proporción áurea
El método de la proporción áurea le permite eliminar intervalos calculando solo un valor de función en cada iteración. Como resultado de los dos valores considerados de la función, se determina el intervalo que debe utilizarse en el futuro. Este intervalo contendrá uno de los puntos anteriores y el siguiente punto colocado simétricamente a él. El punto divide el intervalo en dos partes de modo que la relación entre el todo y la parte mayor sea igual a la relación entre la parte mayor y la menor, es decir, igual a la llamada “proporción áurea”.

Dividir el intervalo en partes desiguales le permite encontrar un método aún más eficaz. Calculemos la función en los extremos del segmento [ a,b] y pon a=X 1 , b=X 2. Calculemos también la función en dos puntos interiores. X 3 , X 4 . Comparemos los cuatro valores de la función y elijamos el más pequeño entre ellos. Dejemos, por ejemplo, que el más pequeño resulte ser F(x3). Evidentemente, el mínimo debe estar en uno de los segmentos adyacentes al mismo. Por lo tanto el segmento [ X 4 ,b] se puede descartar y abandonar el segmento.

Se ha dado el primer paso. En el segmento, nuevamente debe seleccionar dos puntos internos, calcular los valores de la función en ellos y en los extremos y continuar con el siguiente paso. Pero en el paso anterior de cálculos ya encontramos la función en los extremos del nuevo segmento y en uno de sus puntos internos. X 4 . Por tanto, basta con seleccionar un punto más dentro x5 determine el valor de la función en él y haga las comparaciones necesarias. Esto cuadriplica la cantidad de cálculo requerido por paso del proceso. ¿Cuál es la mejor manera de colocar puntos? Cada vez, el segmento restante se divide en tres partes y luego se descarta uno de los segmentos exteriores.
Denotaremos el intervalo de incertidumbre inicial por D.

Dado que en el caso general cualquiera de los segmentos puede descartarse X1, X3 o X 4, X 2 luego seleccione los puntos X3 Y x4 de modo que las longitudes de estos segmentos sean las mismas:

x 3 -x 1 =x 4 -x 2.

Después de descartar, obtenemos un nuevo intervalo de incertidumbre de longitud. D'.
Denotemos la relación D/D' letra φ:

es decir, establezcamos dónde está el siguiente intervalo de incertidumbre. Pero

igual en longitud al segmento descartado en la etapa anterior, es decir

Por lo tanto obtenemos:

.
Esto lleva a la ecuación o, equivalentemente
.

La raíz positiva de esta ecuación da

.

Boleto#34

interpolación de funciones, es decir Usando una función dada, construyendo otra función (generalmente más simple) cuyos valores coinciden con los valores de la función dada en un cierto número de puntos. Además, la interpolación tiene importancia tanto práctica como teórica.

Solución numérica de ecuaciones. y sus sistemas consiste en la determinación aproximada de las raíces de una ecuación o sistema de ecuaciones y se utiliza en los casos en que el método de solución exacto es desconocido o requiere mucha mano de obra.

Formulación del problema[ | ]

Consideremos métodos para resolver numéricamente ecuaciones y sistemas de ecuaciones:

( f 1 (x 1 , x 2 , … , x n) = 0 … f n (x 1 , x 2 , … , x n) = 0 (\displaystyle \left\((\begin(array)(lcr)f_(1 )(x_(1),x_(2),\ldots ,x_(n))&=&0\\\ldots &&\\f_(n)(x_(1),x_(2),\ldots ,x_( n))&=&0\end(array))\right.)

Métodos numéricos para resolver ecuaciones.[ | ]

Vamos a mostrar cómo se puede resolver el sistema de ecuaciones original sin recurrir a métodos de optimización. Si nuestro sistema es un SLAE es recomendable recurrir a métodos como el método Gaussiano o el método de Richardson. Sin embargo, seguiremos partiendo del supuesto de que desconocemos la forma de la función y utilizaremos uno de los métodos iterativos de solución numérica. Entre la gran variedad de ellos, elegiremos uno de los más famosos: el método de Newton. Este método, a su vez, se basa en el principio del mapeo compresivo. Por tanto, en primer lugar se esbozará la esencia de este último.

mapeo compresivo[ | ]

Definamos la terminología:

Se dice que la función realiza mapeo compresivo en si

Entonces el siguiente teorema principal es válido:

Del último punto del teorema se deduce que la tasa de convergencia de cualquier método basado en mapeos de contracción es nada menos que lineal.

Expliquemos el significado del parámetro. α (\displaystyle \alpha ) para el caso de una variable. Según el teorema de Lagrange tenemos: