UNIVERSIDAD ESTATAL DE SAN PETERSBURGO

Facultad de Matemática Aplicada - Procesos de Control

A.P.IVANOV

TALLER DE MÉTODOS NUMÉRICOS

SOLUCIÓN DE SISTEMAS DE ECUACIONES ALGEBRAICAS LINEALES

Pautas

San Petersburgo

CAPÍTULO 1. INFORMACIÓN DE APOYO

EN guía metodológica se da la clasificación de los métodos para la resolución de SLAE y los algoritmos para su aplicación. Los métodos se presentan en una forma que permite su uso sin referencia a otras fuentes. Se supone que la matriz del sistema no es singular, es decir det A 6= 0.

§1. Normas de vectores y matrices

Recuérdese que un espacio lineal Ω de elementos x se llama normalizado si contiene una función k · kΩ , que está definida para todos los elementos del espacio Ω y satisface las siguientes condiciones:

1. kxk Ω ≥ 0, y kxkΩ = 0 x = 0Ω ;

2. kλxk Ω = |λ| kxkΩ;

3. kx + ykΩ ≤ kxkΩ + kykΩ .

En el futuro, estaremos de acuerdo en denotar vectores con letras latinas minúsculas, y los consideraremos vectores columna, denotaremos matrices con letras latinas mayúsculas y denotaremos cantidades escalares con letras griegas (manteniendo las designaciones para números enteros detrás de las letras i, j, k, l, m, n) .

Las normas de vectores más utilizadas incluyen las siguientes:

2. kxk2 = ux2 ; t

3. kxk∞ = maxi |xi |.

Tenga en cuenta que todas las normas en el espacio Rn son equivalentes, es decir, dos normas cualesquiera kxki y kxkj están relacionadas por:

αij kxkj ≤ kxki ≤ βij kxkj ,

k k ≤ k k ≤ ˜ k k

α˜ ij x i x j β ij x i,

además, αij , βij , α˜ij , βij no dependen de x. Además, en un espacio de dimensión finita, dos normas cualesquiera son equivalentes.

El espacio de matrices con las operaciones naturalmente introducidas de suma y multiplicación por un número forman un espacio lineal en el que la noción de norma puede introducirse de muchas maneras. Sin embargo, las llamadas normas subordinadas se consideran con mayor frecuencia, es decir. normas relacionadas con las normas de vectores por las relaciones:

Marcando las normas subordinadas de matrices con los mismos índices que las correspondientes normas de vectores, podemos establecer que

Aquí, λi (AT A) denota el valor propio de la matriz AT A, donde AT es la matriz transpuesta a A. Además de las tres propiedades principales de la norma mencionadas anteriormente, notamos dos más aquí:

kABk ≤ kAk kBk,

kAxk ≤ kAk kxk,

además, en la última desigualdad, la norma matricial está subordinada a la norma vectorial correspondiente. Convengamos en usar en lo que sigue sólo las normas de las matrices subordinadas a las normas de los vectores. Nótese que para tales normas se cumple la igualdad: si E es la matriz identidad, entonces kEk = 1, .

§2. Matrices con dominancia diagonal

Definición 2.1. Una matriz A con elementos (aij )n i,j=1 se llama matriz con dominancia diagonal (valores δ) si las desigualdades

|ai | − |aij| ≥ δ > 0, yo = 1, norte .

§3. Matrices definidas positivas

Definición 3.1. La matriz simétrica A se llamará

definida positiva si la forma cuadrática xT Ax con esta matriz toma solo valores positivos para cualquier vector x 6= 0.

El criterio para la definitud positiva de una matriz puede ser la positividad de sus autovalores o la positividad de sus principales menores.

§4. Número de condición de SLAE

A la hora de resolver cualquier problema, como es sabido, existen tres tipos de errores: error fatal, error metodológico y error de redondeo. Consideremos la influencia del error fatal de los datos iniciales en la solución de la SLAE, despreciando el error de redondeo y teniendo en cuenta la ausencia de error metodológico.

la matriz A se conoce con exactitud y el lado derecho b contiene un error insuperable δb.

Entonces para el error relativo de la solución kδxk/kxk

donde ν(A) = kAkkA−1k.

El número ν(A) se denomina número de condición del sistema (4.1) (o matriz A). Resulta que siempre ν(A) ≥ 1 para cualquier matriz A. Dado que el valor del número de condición depende de la elección de la norma de la matriz, al elegir una norma específica indexaremos ν(A), respectivamente: ν1 ( A), ν2 (A), o ν ∞(A).

En el caso ν(A) 1, se dice que el sistema (4.1) o la matriz A están mal condicionados. En este caso, como sigue de la estimación

(4.2), el error en la solución del sistema (4.1) puede resultar inaceptablemente grande. El concepto de aceptabilidad o inaceptabilidad de un error está determinado por la formulación del problema.

Para una matriz con dominancia diagonal, es fácil obtener una estimación superior de su número de condición. Ocurre

Teorema 4.1. Sea A una matriz con dominancia diagonal de δ > 0. Entonces es no singular y ν∞ (A) ≤ kAk∞ /δ.

§5. Un ejemplo de un sistema mal acondicionado.

Considere SLAE (4.1), en la que

Este sistema tiene una única solución x = (0, 0, . . . , 0, 1)T . Deje que el lado derecho del sistema contenga el error δb = (0, 0, . . . , 0, ε), ε > 0. Entonces

δxn = ε, δxn−1 = ε, δxn−2 = 2 ε, δxn−k = 2 k−1 ε, . . . , δx1 = 2n−2ε.

Por eso,

ν∞ (A) ≥ kδxk ∞ : kδbk ∞ = 2n−2 . kxk ∞ kbk ∞

Como kAk∞ = n, entonces kA−1 k∞ ≥ n−1 2 n−2 , aunque det(A−1 ) = (det A)−1 = 1. Sea, por ejemplo, n = 102. Entonces ν( A ) ≥ 2100 > 1030 . Además, incluso si ε = 10−15 obtenemos kδxk∞ > 1015 . y eso no es

Definición.

Llamamos a un sistema un sistema con dominancia diagonal de fila si los elementos de la matrizsatisfacer las desigualdades:

,

Las desigualdades significan que en cada fila de la matriz el elemento diagonal está resaltado: su módulo es mayor que la suma de los módulos de todos los demás elementos de la misma fila.

Teorema

Un sistema con dominancia diagonal siempre tiene solución y, además, es único.

Considere el sistema homogéneo correspondiente:

,

Supongamos que tiene una solución no trivial , Sea la componente de esta solución, que tiene el mayor módulo, corresponder al índice
, es decir.

,
,
.

vamos a escribir ª ecuación del sistema en la forma

y tomar el módulo de ambos lados de esta igualdad. Como resultado, obtenemos:

.

Reduciendo la desigualdad por un factor
, que, según, no es igual a cero, llegamos a una contradicción con la desigualdad que expresa dominancia diagonal. La contradicción resultante nos permite afirmar consistentemente tres afirmaciones:

El último de ellos significa que la demostración del teorema está completa.

1. Sistemas con matriz tridiagonal. Método de barrido.

Al resolver muchos problemas, uno tiene que lidiar con sistemas de ecuaciones lineales de la forma:

,
,

,
,

donde coeficientes
, lados derechos
conocido junto con los números Y . Las relaciones adicionales a menudo se denominan condiciones de contorno para el sistema. En muchos casos, pueden tener una apariencia más compleja. Por ejemplo:

;
,

Dónde
se dan números. Sin embargo, para no complicar la presentación, nos limitamos a la forma más simple de condiciones adicionales.

Aprovechando que los valores Y dado, reescribimos el sistema en la forma:

La matriz de este sistema tiene una estructura tridiagonal:

Esto simplifica enormemente la solución del sistema debido a un método especial llamado método de barrido.

El método se basa en la suposición de que las incógnitas deseadas Y
relacionados por la relación de recurrencia

,
.

Aquí las cantidades
,
, denominados coeficientes de barrido, se determinarán en función de las condiciones del problema, . De hecho, tal procedimiento significa reemplazar la definición directa de las incógnitas la tarea de determinar los coeficientes de barrido con el posterior cálculo de las cantidades .

Para implementar el programa descrito, expresamos usando la relación
a través de
:

y sustituir
Y , expresado a través de
, en las ecuaciones originales. Como resultado, obtenemos:

.

Las últimas relaciones ciertamente se cumplirán y, además, independientemente de la solución, si se requiere que en
igualdades se produjeron:

De aquí siguen las relaciones recursivas para los coeficientes de barrido:

,
,
.

Condición límite izquierda
y proporción
son consistentes si ponemos

.

Otros valores de los coeficientes de barrido
Y
encontramos from, with which y completamos la etapa de cálculo de los coeficientes de barrido.

.

Desde aquí puedes encontrar el resto de incógnitas
en el proceso de barrido hacia atrás utilizando una fórmula recursiva.

El número de operaciones requeridas para resolver un sistema general utilizando el método de Gauss aumenta con el aumento proporcionalmente . El método de barrido se reduce a dos ciclos: primero, los coeficientes de barrido se calculan usando las fórmulas, luego, usándolos, los componentes de la solución del sistema se encuentran usando las fórmulas recurrentes . Esto significa que a medida que aumenta el tamaño del sistema, el número de operaciones aritméticas crecerá proporcionalmente , pero no . Por lo tanto, el método de barrido dentro del alcance de su posible aplicación es significativamente más económico. A ello hay que añadir la especial sencillez de su implementación software en un ordenador.

En muchos problemas aplicados que conducen a SLAE con una matriz tridiagonal, sus coeficientes satisfacen las desigualdades:

,

que expresan la propiedad de dominancia diagonal. En particular, nos encontraremos con tales sistemas en los capítulos tercero y quinto.

Según el teorema del apartado anterior, la solución de tales sistemas siempre existe y es única. También tienen una declaración que es importante para el cálculo real de la solución usando el método de barrido.

lema

Si para un sistema con una matriz tridiagonal se cumple la condición de dominancia diagonal, entonces los coeficientes de barrido satisfacen las desigualdades:

.

Realizaremos la demostración por inducción. De acuerdo a
, yo como
la afirmación del lema es verdadera. Supongamos ahora que es cierto para y considerar
:

.

Entonces la inducción de A
justificada, que completa la demostración del lema.

Desigualdad para coeficientes de barrido hace que la carrera sea estable. De hecho, suponga que el componente de la solución como resultado del procedimiento de redondeo se calcula con algún error. Entonces al calcular el siguiente componente
según la fórmula recursiva, este error, debido a la desigualdad, no aumentará.

NO DEGENENERIDAD DE MATRICES Y PROPIEDAD DE DOMINANCIA DIAGONAL1

L. Cvetkovich, V. Kostic y L.A. galleta

Cvetkovic Liliana - Profesora, Departamento de Matemáticas e Informática, Facultad de Ciencias, Universidad de Novi Sad, Serbia, Obradovica 4, Novi Sad, Serbia, 21000, correo electrónico: [correo electrónico protegido]

Kostic Vladimir - Profesor Asistente, Doctor, Departamento de Matemáticas e Informática, Facultad de Ciencias, Universidad de Novi Sad, Serbia, Obradovica 4, 21000, Novi Sad, Serbia, correo electrónico: [correo electrónico protegido]

Krukier Lev Abramovich - Doctor en Ciencias Físicas y Matemáticas, Profesor, Jefe del Departamento de Computación de Alto Rendimiento y Tecnologías de la Información y la Comunicación, Director del Centro Regional de Informatización del Sur de Rusia del Sur universidad federal, Stachki Ave. 200/1, edificio. 2, Rostov del Don, 344090, correo electrónico: [correo electrónico protegido] Ru.

Cvetkovic Ljiljana - Profesor, Departamento de Matemáticas e Informática, Facultad de Ciencias, Universidad de Novi Sad, Serbia, D. Obradovica 4, Novi Sad, Serbia, 21000, correo electrónico: [correo electrónico protegido]

Kostic Vladimir - Profesor Asistente, Departamento de Matemáticas e Informática, Facultad de Ciencias, Universidad de Novi Sad, Serbia, D. Obradovica 4, Novi Sad, Serbia, 21000, correo electrónico: [correo electrónico protegido]

Krukier Lev Abramovich - Doctor en Ciencias Físicas y Matemáticas, Profesor, Jefe del Departamento de Computación de Alto Rendimiento y Tecnologías de la Información y la Comunicación, Director del Centro de Computación de la Universidad Federal del Sur, Stachki Ave, 200/1, bild. 2, Rostov del Don, Rusia, 344090, correo electrónico: [correo electrónico protegido] Ru.

La dominancia diagonal en la matriz es condición sencilla, asegurando su no degeneración. Las propiedades de matriz que generalizan la noción de dominancia diagonal siempre tienen una gran demanda. Se consideran condiciones del tipo de dominancia diagonal y ayudan a definir subclases de matrices (como matrices H) que permanecen no degeneradas bajo estas condiciones. En este artículo, construimos nuevas clases de matrices no singulares que retienen las ventajas de la dominancia diagonal pero permanecen fuera de la clase de matrices H. Estas propiedades son especialmente convenientes porque muchas aplicaciones conducen a matrices de esta clase, y ahora se puede extender la teoría de la no degeneración de matrices que no son matrices H.

Palabras clave: dominancia diagonal, no degeneración, escalado.

Si bien las condiciones simples que aseguran la no singularidad de las matrices siempre son muy bien recibidas, muchas de las cuales pueden considerarse como un tipo de dominancia diagonal tienden a producir subclases de matrices H bien conocidas. En este artículo construimos una nueva clase de matrices no singulares que mantienen la utilidad de la dominancia diagonal, pero mantienen una relación general con la clase de matrices H. Esta propiedad es especialmente favorable, ya que ahora se pueden ampliar muchas aplicaciones que surgen de la teoría de la matriz H.

Palabras clave: dominancia diagonal, no singularidad, técnica de escalado.

La solución numérica de los problemas de valores en la frontera de la física matemática generalmente reduce el problema original a la solución de un sistema de ecuaciones algebraicas lineales. Al elegir un algoritmo de solución, necesitamos saber si la matriz original es no singular. Además, la cuestión de la no degeneración de una matriz es relevante, por ejemplo, en la teoría de la convergencia de métodos iterativos, localización de valores propios, en la estimación de determinantes, raíces delantal, radio espectral, valores singulares de un matriz, etc

Tenga en cuenta que una de las condiciones más simples pero extremadamente útiles que aseguran la no degeneración de una matriz es la conocida propiedad de dominancia diagonal estricta (y las referencias a ellas).

Teorema 1. Sea dada una matriz A = e Cnxn tal que

s > r (a):= S k l, (1)

para todo i e N:= (1,2,...n).

Entonces la matriz A es no degenerada.

Las matrices con propiedad (1) se denominan matrices con dominancia diagonal estricta

(matrices 8BB). Su generalización natural es la clase de matrices con dominancia diagonal generalizada (GBD), definida de la siguiente manera:

Definición 1. Una matriz A = [a^] e Cxn se llama matriz sBB si existe una matriz diagonal no singular W tal que AW es una matriz 8BB.

Introducimos varias definiciones para la matriz

A \u003d [ay] e Spxp.

Definición 2

(A) = e Cn

se llama la matriz de comparación de la matriz A.

Definición 3. Matriz A = e C

\üj > 0, i = j

es una matriz M si

aj< 0, i * j,

tapete inverso -

matriz A">0, es decir, todos sus elementos son positivos.

Obviamente, las matrices de la clase wBB también son matrices no singulares y pueden ser

1Este trabajo fue apoyado parcialmente por el Ministerio de Educación y Ciencia de Serbia, subvención 174019, y el Ministerio de Ciencia y Desarrollo Tecnológico de Vojvodina, subvenciones 2675 y 01850.

encontrado en la literatura bajo el nombre de matrices H no degeneradas. Se pueden definir utilizando la siguiente condición necesaria y suficiente:

Teorema 2. La matriz A \u003d [ay ]e xi

matriz si y solo si su matriz de comparación es una matriz M no degenerada.

Por ahora, ya se han estudiado muchas subclases de matrices H no degeneradas, pero todas ellas se consideran desde el punto de vista de las generalizaciones de la propiedad de dominancia estrictamente diagonal (ver también las referencias allí).

En este artículo, consideramos la posibilidad de ir más allá de la clase de matrices H generalizando la clase SBB de una manera diferente. La idea principal es continuar usando el enfoque de escalado, pero con matrices que no son diagonales.

Considere la matriz A \u003d [ay] e spxn y el índice

Introducimos la matriz

r (A):= £ a R (A):= £

ßk (A) := £ y yk (A) := aü - ^

Es fácil comprobar que los elementos de la matriz bk Abk tienen la siguiente forma:

ßk (A), Yk (A), akj,

i=j=k, i=j*k,

yo = k, j * k, yo * k, j = k,

Un inöaeüiüö neo^äyö.

Si aplicamos el Teorema 1 a la matriz bk Abk1 descrita anteriormente y su transpuesta, entonces obtenemos dos teoremas principales.

Teorema 3. Sea cualquier matriz dada

A \u003d [ay] e spxn con elementos diagonales distintos de cero. Si existe k e N tal que > Rk (A), y para cada i e N \ (k),

entonces la matriz A es no degenerada.

Teorema 4. Sea cualquier matriz dada

A \u003d [ay] e spxn con elementos diagonales distintos de cero. Si existe k e N tal que > Jk (A), y para cada i e N \ (k),

Entonces la matriz A es no degenerada. Surge una pregunta natural en cuanto a la relación entre

matrices de los dos teoremas anteriores: L^ - BOO -matrices ( definido por la fórmula(5)) y

bk - Matrices BOO (definidas por la fórmula (6)) y la clase de matrices H. El siguiente ejemplo sencillo lo aclara.

Ejemplo. Considere las siguientes 4 matrices:

y consideremos una matriz bk Abk, k e N, similar a la A original. Busquemos las condiciones en las que esta matriz tendrá la propiedad de una matriz SDD (por filas o por columnas).

A lo largo del artículo, para r,k eN:= (1,2,.../?) usaremos la notación:

2 2 1 1 3 -1 1 1 1

" 2 11 -1 2 1 1 2 3

2 1 1 1 2 -1 1 1 5

Teoremas sobre la no degeneración

Todos ellos son no degenerados:

A1 es b - BOO, a pesar de que no es bk - BOO para cualquier k = (1,2,3). Tampoco es una matriz H, ya que (A^1 no es no negativo;

A2, por simetría, es simultáneamente LH - BOO y L<2 - БОО, так же как ЬЯ - БОО и

b<3 - БОО, но не является Н-матрицей, так как (А2) вырожденная;

A3 es b9 - BOO, pero tampoco es

Lr es un SDD (para k = (1,2,3)), ni una matriz H ya que (A3 ^ también es degenerado;

A4 es una matriz H ya que (A^ no es singular y ^A4) 1 > 0, aunque no es ni LR - SDD ni Lk - SDD para cualquier k = (1,2,3).

La figura muestra la relación general entre

Lr - SDD , Lk - SDD y H-matrices junto con las matrices del ejemplo anterior.

Comunicación entre lR - SDD, lC - SDD y

infierno min(|au - r (A)|) "

Empezando por la desigualdad

y aplicando este resultado a la matriz bk ab ^, obtenemos

Teorema 5. Sea dada una matriz arbitraria A = [a--] e Cxn con elementos diagonales distintos de cero.

policías Si A pertenece a la clase - BOO, entonces

1 + máx^ i*k \acc\

Matrices H

Es interesante notar que aunque tenemos

la clase de LC BOO-matrices al aplicar el Teorema 1 a la matriz obtenida al transponer la matriz LC AL^1, esta clase no coincide con la clase obtenida al aplicar el Teorema 2 a la matriz Am.

Introducimos definiciones.

Definición 4. La matriz A se llama ( bk -boo por filas) si AT ( bk -boo ).

Definición 5. La matriz A se llama ( bsk -boo por filas) si AT ( bsk -boo ).

Los ejemplos muestran que las clases W - BOO,

bc-boo, (bk-boo por fila) y (b^-boo por fila) están relacionados entre sí. Por lo tanto, hemos ampliado la clase de matrices H de cuatro maneras diferentes.

Aplicación de nuevos teoremas

Ilustremos la utilidad de los nuevos resultados para estimar la norma C de una matriz inversa.

Para una matriz A arbitraria con dominancia diagonal estricta, el conocido teorema de Varah (Varah) da la estimación

min[|pf(A)| - mk (A), min(|yk (A)| - qk(A) - |af (A)|)]" i i (Фf ​​​​ii ii

De igual manera, obtenemos el siguiente resultado para las matrices Lk - SDD por columnas.

Teorema 6. Sea dada una matriz arbitraria A = e xi con elementos diagonales distintos de cero. Si A pertenece a la clase bk -SDD por columnas, entonces

Ik-lll<_ie#|akk|_

" "mln[|pf(A)| - Rf (AT), mln(|уk (A)|- qk (AT)- |a popa |)]"

La importancia de este resultado radica en que para muchas subclases de matrices H no singulares existen restricciones de este tipo, pero para aquellas matrices no singulares que no son matrices H, este es un problema no trivial. Por lo tanto, restricciones de este tipo, como en el teorema anterior, tienen una gran demanda.

Literatura

Levy L. Sur le possibilité du l "equlibre electrique C. R. Acad. Paris, 1881. Vol. 93. P. 706-708.

Horn RA, Johnson CR análisis matricial. Cambridge, 1994. Varga R.S. Gersgorin y sus círculos // Serie Springer en matemáticas computacionales. 2004 vol. 36.226 pág. Berman A., Plemons R.J. Matrices no negativas en las ciencias matemáticas. Serie SIAM Clásicos en Matemática Aplicada. 1994 vol. 9. 340 rublos

Cvetkovic Lj. Teoría de la matriz H vs. localización de valores propios // Numer. Algor. 2006 vol. 42. Pág. 229-245. Cvetkovic Lj., Kostic V., Kovacevic M., Szulc T. Resultados adicionales sobre matrices H y sus complementos de Schur // Appl. Matemáticas. computar 1982. Pág. 506-510.

Varah J. M. Un límite inferior para el valor más pequeño de una matriz // Aplicación de álgebra lineal. 1975 vol. 11. pág. 3-5.

Recibido por el editor

Definición.

Llamamos a un sistema un sistema con dominancia diagonal de fila si los elementos de la matrizsatisfacer las desigualdades:

,

Las desigualdades significan que en cada fila de la matriz el elemento diagonal está resaltado: su módulo es mayor que la suma de los módulos de todos los demás elementos de la misma fila.

Teorema

Un sistema con dominancia diagonal siempre tiene solución y, además, es único.

Considere el sistema homogéneo correspondiente:

,

Supongamos que tiene una solución no trivial , Sea la componente de esta solución, que tiene el mayor módulo, corresponder al índice
, es decir.

,
,
.

vamos a escribir ª ecuación del sistema en la forma

y tomar el módulo de ambos lados de esta igualdad. Como resultado, obtenemos:

.

Reduciendo la desigualdad por un factor
, que, según, no es igual a cero, llegamos a una contradicción con la desigualdad que expresa dominancia diagonal. La contradicción resultante nos permite afirmar consistentemente tres afirmaciones:

El último de ellos significa que la demostración del teorema está completa.

1. Sistemas con matriz tridiagonal. Método de barrido.

Al resolver muchos problemas, uno tiene que lidiar con sistemas de ecuaciones lineales de la forma:

,
,

,
,

donde coeficientes
, lados derechos
conocido junto con los números Y . Las relaciones adicionales a menudo se denominan condiciones de contorno para el sistema. En muchos casos, pueden tener una apariencia más compleja. Por ejemplo:

;
,

Dónde
se dan números. Sin embargo, para no complicar la presentación, nos limitamos a la forma más simple de condiciones adicionales.

Aprovechando que los valores Y dado, reescribimos el sistema en la forma:

La matriz de este sistema tiene una estructura tridiagonal:

Esto simplifica enormemente la solución del sistema debido a un método especial llamado método de barrido.

El método se basa en la suposición de que las incógnitas deseadas Y
relacionados por la relación de recurrencia

,
.

Aquí las cantidades
,
, denominados coeficientes de barrido, se determinarán en función de las condiciones del problema, . De hecho, tal procedimiento significa reemplazar la definición directa de las incógnitas la tarea de determinar los coeficientes de barrido con el posterior cálculo de las cantidades .

Para implementar el programa descrito, expresamos usando la relación
a través de
:

y sustituir
Y , expresado a través de
, en las ecuaciones originales. Como resultado, obtenemos:

.

Las últimas relaciones ciertamente se cumplirán y, además, independientemente de la solución, si se requiere que en
igualdades se produjeron:

De aquí siguen las relaciones recursivas para los coeficientes de barrido:

,
,
.

Condición límite izquierda
y proporción
son consistentes si ponemos

.

Otros valores de los coeficientes de barrido
Y
encontramos from, with which y completamos la etapa de cálculo de los coeficientes de barrido.

.

Desde aquí puedes encontrar el resto de incógnitas
en el proceso de barrido hacia atrás utilizando una fórmula recursiva.

El número de operaciones requeridas para resolver un sistema general utilizando el método de Gauss aumenta con el aumento proporcionalmente . El método de barrido se reduce a dos ciclos: primero, los coeficientes de barrido se calculan usando las fórmulas, luego, usándolos, los componentes de la solución del sistema se encuentran usando las fórmulas recurrentes . Esto significa que a medida que aumenta el tamaño del sistema, el número de operaciones aritméticas crecerá proporcionalmente , pero no . Por lo tanto, el método de barrido dentro del alcance de su posible aplicación es significativamente más económico. A ello hay que añadir la especial sencillez de su implementación software en un ordenador.

En muchos problemas aplicados que conducen a SLAE con una matriz tridiagonal, sus coeficientes satisfacen las desigualdades:

,

que expresan la propiedad de dominancia diagonal. En particular, nos encontraremos con tales sistemas en los capítulos tercero y quinto.

Según el teorema del apartado anterior, la solución de tales sistemas siempre existe y es única. También tienen una declaración que es importante para el cálculo real de la solución usando el método de barrido.

lema

Si para un sistema con una matriz tridiagonal se cumple la condición de dominancia diagonal, entonces los coeficientes de barrido satisfacen las desigualdades:

.

Realizaremos la demostración por inducción. De acuerdo a
, yo como
la afirmación del lema es verdadera. Supongamos ahora que es cierto para y considerar
:

.

Entonces la inducción de A
justificada, que completa la demostración del lema.

Desigualdad para coeficientes de barrido hace que la carrera sea estable. De hecho, suponga que el componente de la solución como resultado del procedimiento de redondeo se calcula con algún error. Entonces al calcular el siguiente componente
según la fórmula recursiva, este error, debido a la desigualdad, no aumentará.

$|a\_(ii)|\; \backslash geqslant\; \backslash sum\_(j\; \backslash neq\; i)\; |a\_(ij)|,\backslash qquad\; i\; =\; 1,\; \backslash dots,\; n,$

y al menos una desigualdad es estricta. Si todas las desigualdades son estrictas, se dice que la matriz es $Ana)$ tiene estricto predominio diagonal.

Las matrices con dominancia diagonal aparecen con bastante frecuencia en las aplicaciones. Su principal ventaja es que los métodos iterativos para resolver SLAE con una matriz de este tipo (el método de iteración simple, el método de Seidel) convergen en una solución exacta que existe y es única para cualquier lado derecho.

Propiedades

• Una matriz con dominancia diagonal estricta no es degenerada.

ver también

Escriba una reseña sobre el artículo "Dominancia diagonal"

Un extracto que caracteriza el predominio diagonal