Tema 3 con ejercicios - Sistemas de ecuaciones lineales. Métodos numéricos. PDF

Preview

Summary

y - merged files: TEMA_3._MAT_II._2012-2013.pdf - PROBLEMAS_TEMA_3._MAT_II._2012-2013.pdf...

Description

TEMA 3 SISTEMAS DE ECUACIONES LINEALES. MÉTODOS NUMÉRICOS ESQUEMA: Apartado 1: Definición y conceptos básicos Apartado 2: Clasificación de sistemas lineales Apartado 3: Rouché Frobenius Apartado 4: Regla de Cramer Apartado 5: Métodos directos de resolución 

Método de Gauss



Método de Gauss con pivote parcial



Método de Gauss con pivote total

Apartado 6: Métodos iterativos clásicos 

Métodos iterativos Método de Jacobi Método de Gauss-Seidel Método de relajación



Convergencia de los métodos iterativos Normas vectoriales y matriciales Condicionamiento de un sistema de ecuaciones lineales Sucesiones de vectores y matrices Convergencia

APARTADO 1: DEFINICIÓN Y CONCEPTOS BÁSICOS Gran variedad de disciplinas como ingeniería, finanzas, física, estadística, matemática aplicada, biología, ciencias sociales….., nos plantean problemas en los que es necesario enfrentarse a la resolución de un sistema lineal de la forma,

Ax  b; A  aij   M m n 

Definición 1.1 forma:

Sea K un cuerpo, una ecuación lineal con coeficientes en K es una expresión de la

a1 x1  a2 x2 ...  an xn  b donde los términos a1 , a2 ,....an  K son los coeficientes, el término b  K se llama término independiente, y x 1 , x 2 ...x n son las incógnitas. Definición 1.2 Un conjunto de m ecuaciones con n incógnitas:

TEMA 3.SISTEMAS DE ECUACIONES LINEALES. MÉTODOS NUMÉRICOS. MAT II

1

a11 x1  a12 x2 ...  a1n xn  b1  a21 x1  a22 x2 ...  a2 n xn  b2  ...... am1 x1  am 2 x2 ...  amn xn  bm se llama sistema de m ecuaciones lineales con n incógnitas. Se dice que x  1 ,..., n  es solución del sistema si verifica todas las ecuaciones simultáneamente.

bi  0, i  1,..., m



El sistema es homogéneo si



El sistema se dice completo si bj  0, para algun j 1,..., m



Dos sistemas se dice que son sistemas equivalentes si tienen las mismas soluciones, es decir, si toda solución de un sistema también lo es del otro.

El sistema se puede escribir en forma matricial:

 a11 a12   a21 a22   a  m1 am 2 

 

La matriz A  aij  Mm n

 x1   b1      x b  2    2   x   b   n  m



se llama matriz de coeficientes o matriz del

sistema 

El vector x   x1 , x 2...xn  se conoce como vector de incógnitas.



El vector b   b1 ,..., bm  se conoce como vector de términos independientes.

APARTADO 2: CLASIFICACIÓN DE SISTEMAS LINEALES Los sistemas de ecuaciones se pueden clasificar según el número de soluciones que pueden presentar. De acuerdo con eso se pueden presentar los siguientes casos: 

Sistema incompatible si no tiene ninguna solución.



Sistema compatible si tiene alguna solución, en este caso además puede distinguirse entre: 

Sistema compatible determinado cuando tiene un número finito de soluciones.



Sistema compatible indeterminado cuando admite un conjunto infinito de soluciones.

Desde un punto de vista algebraico los sistemas compatibles determinados se caracterizan porque el determinante de la matriz es diferente de cero: Nota: Los sistemas homogéneos son siempre compatibles, pues admiten cuando menos la solución: x 1  0,..., x n  0 Esta solución se conoce como solución trivial o nula.

APARTADO 3: ROUCHÉ FROBENIUS TEMA 3.SISTEMAS DE ECUACIONES LINEALES. MÉTODOS NUMÉRICOS. MAT II

2

Sea un sistema lineal

Ax  b , de m ecuaciones y n incógnitas:

 a11 a12 a  21 a22   a  m1 am 2

 x1   b1  x  b  2 2       x   b   n  m

llamamos matriz ampliada y la denotamos por

 A b  a la matriz

 a11 a12   a 21 a 22    a m1 a m 2

b1   b2   b m 

Teorema 3.1 (de Rouché-Frobenius) El sistema lineal

Ax  b es compatible si y sólo si ran  A  rang  A b

Corolario 1. El sistema lineal

Ax  b es compatible determinado si y sólo si ran  A  rang  A b   n

(n número de incógnitas) 2. El sistema lineal

Ax  b es compatible indeterminado si y sólo si ran  A  rang  A b  n

APARTADO 4: REGLA DE CRAMER Un sistema lineal Ax  b se dice que es un sistema de Cramer si su matriz de coeficientes, A, es cuadrada y regular, esto es, si el sistema tiene tantas ecuaciones como incógnitas y su determinante es no nulo.

 a11 a12 a  21 a22    an 1 an 2

 x1   b1   x  b  2 2           xn   bn 

Regla de Cramer Si el sistema lineal

Ax  b es compatible determinado, la solución viene dada por: xj 

1 Mj A

donde M j es la matriz obtenida a partir de A al sustituir la columna j-ésima por el vector de términos independientes de b

 a11  a21 Mj     an 1

a12 a22

b1 b2

a1 j1 ... a1 n   a2 j 1 ... a2 n 

an 2

bn

anj 1

 ... ann 

Ejemplo: TEMA 3.SISTEMAS DE ECUACIONES LINEALES. MÉTODOS NUMÉRICOS. MAT II

3

x  y  z  1  x  2y  3z  2 x  z  5  1 1 1   x   1  1 2 3    2     y    1 0 1   z   5       1

1

1

1

1 2 3  2; 1 0 1

x

1

1

1 1 1

1

1

1

2 2 3  21; 1 2 3  8; 1  2 2   11 5 0 1 1 5 1 1 0 5

8 11 21 ; y  4; z  2 2 2

RESOLUCIÓN DE UN SISTEMA COMPATIBLE INDETERMINADO Sea

Ax  b un sistema lineal de m ecuaciones y n incógnitas.





Si ran  A  rang A b  n existe una submatriz cuadrada regular de A orden r menor que n (que supondremos, la formada por las r primeras filas y las r primeras columnas). En este caso el sistema es equivalente a:

a11x1  a12x 2 ...  a1r xr  b1   a1,r  1xr  1  ...  a 1n xn   a21 x1  a22 x2 ...  a2 r xr  b2   a2, r 1 xr 1  ...  a2 n xn   ...... a x a x  r1 1  r 2 2 ...  arr xr  br   ar , r 1xr 1  ...  arn xn   a11  con C   a  r1

...

a1r  

...

arr 

K

matriz regular

Observaciones: 

Para cada asignación que hagamos sobre las variables

xr 1 ,..., xn de

elementos de K, obtendremos un sistema de Cramer que se puede resolver mediante la regla de Cramer, y que proporciona una única solución para

x 1 ,..., x r 

A

xr 1 ,..., xn se les denomina usualmente parámetros del sistema de

ecuaciones. 

Dimensión del conjunto de soluciones = número de incógnitas- rang  A 

Ejemplo:

x  y  2 z  2   y  z 1 2 x  2 z  2 

1 1 2    A  0 1 1  2 0 2  

A 0

TEMA 3.SISTEMAS DE ECUACIONES LINEALES. MÉTODOS NUMÉRICOS. MAT II

4

Buscamos un menor de orden 2 no nulo

x  y  2  2z   y 1  z x

1 1  1  0 y nos quedamos con el sistema 0 1

y aplicando la regla de Cramer nos queda

2  2z 1 1  z 1 z 1

y

1 22z 1  z y si hacemos z   la solución nos queda 0 1 z

x 1  ; y 1  ; z  

APARTADO 5: MÉTODOS DIRECTOS DE RESOLUCIÓN Permiten calcular la solución exacta del sistema en un número finito de pasos (salvo errores de redondeo) El método de Cramer es poco práctico cuando el número de ecuaciones es grande, ya que da lugar a determinantes complicados de calcular. Para estos casos se utiliza el método de eliminación de Gauss. MÉTODO DE GAUSS La idea de este método es transformar el sistema de ecuaciones lineales original en un sistema de matriz triangular superior con las mismas soluciones. El método de eliminación gaussiana está basado en las siguientes operaciones elementales sobre las ecuaciones del sistema:

  0 , y la ecuación resultante



La ecuación (i) puede ser multiplicada por un valor utilizarse en lugar de la ecuación (i)



La ecuación (j) puede ser multiplicada por un valor   utilizar el resultado en lugar de las ecuaciones (i) o (j)



Las ecuaciones (i) y (j) pueden intercambiarse entre sí.

0 , sumarse a la ecuación (i), y

El elemento en el que nos basamos para reducir los elementos a cero se llama pivote. Ejemplo: Resolver el sistema

x  2 y  3z  4t  30 2 x  2 y  z  4t  19   4 x  y  2 z  t  8 8 x  2 y  2 z  t  10 Primer pivote

1  2 4  8

1 2 forma matricial:  4  8

4   x   30 2 1 4   y   19   1 2 1   z   8      2 2 1   t   10  2

3

a11  1  0

2 3 4 30   2 1 4 19  1 2 1 8   2 2 1 10 

 F1

3 4 30  1 2    F2  2 F1 0 2 7 4  41    0 7 10 17 112   F3  4 F1    F4  8 F1  0 14 26 31  230 

TEMA 3.SISTEMAS DE ECUACIONES LINEALES. MÉTODOS NUMÉRICOS. MAT II

5

Segundo pivote

3 1 2  7 0 2 0 7 10  0 14 26 Tercer pivote

1 2  0 2 0 0   0 0

a22  2  0 4 4 17 31

1 2 30   F1    41   F2  0 2  112   F3  7 F2  0 0 2   0 0  230   F  7 F 4 2 

3 7 29 2 23

4 30   4  41  3 632   3 57 

a33  29 2  0

3 4 30   7 4  41  29 63  2 3 2 23 3 57 

1 2   0 2  0 0   F 4  46 F3  0 0 29 

 F1  F2  F3

3 7 29 2 0

 4 30  4  41  3 632   51 204  29 29 

Resolvemos el sistema triangular superior

 204 29  4 t  51  29  63 63  24 29 z 3  z  3 4  2 2 29  41  21  16         41  y  2  2y 7 3 4 4 2  x  2  2  3  3  4  4  30  x  30  4  9  16  1 MÉTODO DE GAUSS. PIVOTE PARCIAL Consiste en utilizar como pivote el elemento que tenga mayor valor absoluto de la primera columna e intercambiar la fila en la que se encuentra este elemento con la primera fila. Este método se utiliza para minimizar los posibles errores de redondeo. Ejemplo:

TEMA 3.SISTEMAS DE ECUACIONES LINEALES. MÉTODOS NUMÉRICOS. MAT II

6

Comprobamos a continuación con un ejemplo como realmente los resultados obtenidos con el método de Gauss normal y con el método de Gauss con pivote parcial pueden ser significativamente diferentes debido a los errores del redondeo (mucho mayores en el método sin pivote) Consideramos el sistema de ecuaciones lineales siguiente:

0.007 x 0.033 y  2.5  1.113 x  2.5 y  1.45 Método de Gauss sin utilizar el pivote

0.007 0.033 2.5  0.007 0.033 2.5  F1  F1      1.113 7.747 396.05  1.113 2.5 1.45  F2  F2  0.007 F1  0 y

396  51.123; 7.747

x  10.558

Método de Gauss con pivote parcial

0.007 0.033 2.5  F1 1.113 2.5 1.45      1.113 2.5 1.45  0.007 0.033 2.5  2.5 1.45  1.113 F1 F1   0.007   2 F2  F2  F 4.8723 10 2.4909  1.113 1  0 y

2.4909  51.124; x  116.14  4.8723 10 2

Como podemos ver hay una diferencia entre los dos resultados que en el caso de la es realmente muy grande. En el caso de

x la diferencia en % es

x

116.14  10.558  90.909% 116.14

TEMA 3.SISTEMAS DE ECUACIONES LINEALES. MÉTODOS NUMÉRICOS. MAT II

7

En el caso de la

y la diferencia en % es

51.124  51.123  0.001956% 51.124

MÉTODO DE GAUSS. PIVOTE TOTAL Consiste en utilizar como pivote el elemento de mayor valor absoluto de toda la matriz. En este caso no solo hay que intercambiar la fila en la que se encuentra el pivote con la primera, sino que también hay que intercambiar la columna. No mejora significativamente respecto del pivote parcial

APARTADO 6: MÉTODOS ITERATIVOS CLÁSICOS Los métodos iterativos son, en general, más eficientes que los métodos directos para resolver sistemas de ecuaciones lineales grandes y de matriz que tenga un gran número de ceros (hueca), ya que: 

Se basan en la operación “multiplicación matriz por vector”



Son menos sensibles a errores de redondeo



Son muy eficientes a la hora de resolver sistemas grandes en los que la matriz de coeficientes es hueca.



En los métodos directos se produce el llenado de la matriz cosa que no ocurre en estos.

Los métodos iterativos tienen el inconveniente de que, en general, no es posible predecir el número de operaciones que se requieren para obtener una aproximación a la solución con cierta precisión.

Ax  b los métodos iterativos lo que hacen es k  x 0 , x 1 , x 2 ,..., x k ,.. , a partir de generar una sucesión de aproximaciones x Dado un sistema de ecuaciones

una aproximación inicial

 

k 0,1





x  0 , que converja a la solución del sistema dado.

Para generar esta sucesión, se repite el mismo esquema de operaciones hasta que, o bien se obtiene una aproximación con una precisión especificada de antemano, o bien se rebasa un número máximo de iteraciones. Los métodos iterativos clásicos siguen el siguiente esquema;

 x  0 dado   k 1 k  Bx  c  x donde

B  M n es la matriz del método y c  K n es el vector del método.

Los métodos de descomposición que vamos a estudiar a continuación son métodos iterativos lineales. Se obtienen al descomponer la matriz A en la forma: matriz invertible. Entonces:

A  M  N donde M es una

Ax  b  Mx  Nx  b  x  M 1 Nx  M 1b

La matriz del método es

B  M 1N

El método iterativo asociado consiste en:

x 0  dado  k 1 k   Bx  c x

donde

B  M 1N

y

c  M 1b

TEMA 3.SISTEMAS DE ECUACIONES LINEALES. MÉTODOS NUMÉRICOS. MAT II

8

En la práctica, no se calcula

M 1 , sino que se resuelve, Mx     Nx    b k 1

Consideremos la descomposición de la matriz:

k

A  D  E  F , con aij  0 , donde:

D es una matriz diagonal de componentes

d ii  aii  0

E es una matriz triangular estrictamente inferior, de componentes eij  aij ,  i  j  F es una matriz triangular estrictamente superior, de componentes fij  aij ,  i  j 

 a11 0  0 a22  D    0  0

 0 a12  0 0  F    0 0

0  0  a 0 E   21    a n1 a n2

    

MÉTODO DE JACOBI Con la notación anterior, Ax   D  E  F  x  b  Dx   E  F  x  b lo que nos lleva a plantear el algoritmo:

 x  0 dado   k1  k  Jx  D 1b  x donde la matriz del método es: J  D y en términos de componentes:

x i k

1

1

E  F 



i 1 n 1 k  k   bi  a ijx j   a ijx j  aii  j 1 j11 

que es la llamada matriz de Jacobi

i  1,...,n 

MÉTODO DE GAUSS-SEIDEL En este caso hacemos, Ax   D  E  F  x  b   D  E x  Fx  b lo que nos lleva a plantear el algoritmo:  0  dado x   k 1 1  Gx  k    D  E  b  x

donde la matriz del método es: G   D  E  y en términos de componentes:

x i k

1



1 aii

1

F que es la llamada matriz de Gauss-Seidel

i 1 n   k1 k  bi  a ijx j   a ijx j  j 1 j 11  

 i  1,...,n 

MÉTODO DE RELAJACIÓN lenta.

La convergencia de los métodos de Jacobi y Gauss-Seidel es en general bastante

Los métodos de relajación pueden mejorar sustancialmente la convergencia del método de Gauss-Seidel. Los métodos de relajación presentan el inconveniente de que la convergencia depende de la elección adecuada de un parámetro.

TEMA 3.SISTEMAS DE ECUACIONES LINEALES. MÉTODOS NUMÉRICOS. MAT II

9

CONVERGENCIA DE LOS MÉTODOS ITERATIVOS Se dice que un método iterativo es convergente si la sucesión generada por el método converge a la solución para cualquier aproximación inicial

x

 0

.

Vamos a estudiar unos cuantos conceptos previos antes de dar los resultados sobre la convergencia de los métodos de Jacobi y Gauss-Seidel. NORMAS VECTORIALES Y MATRICIALES Llamamos norma sobre

:V 

V a toda aplicación

1. v  0, v V ,

verificando:

v 0v0

v   v ,   K , v V

2.

3. u  v  u  v ,

u , v V

(desigualdad triangular)

Un espacio vectorial dotado de una norma se denomina espacio vectorial normado y se denota:

V , 

Ejemplos: Sea v   v1 ,..., vn   Norma infinito:

v



 max v i i1,..., n

n

v 1   vi

Norma uno:

i 1

n

v

v2

Norma dos:

2 i

i 1

1

Norma p:

v

p

 n p p    vi   i 1 

Definición Se dice que dos normas constantes



,



de

son equivalentes si existen

c1 , c2  0 tales que, c1 v   v   c2 v  , v 

En particular se verifica que:

v 2 v 1 n v

v v





 v

2

 n v

 v 1 n v

2





Definición 6.1

TEMA 3.SISTEMAS DE ECUACIONES LINEALES. MÉTODOS NUMÉRICOS. MAT II

10

Sea ahora M n  K  el conjunto de las matrices cuadradas sobre un cuerpo K,

:Mn 

llamamos norma matricial a toda aplicación 1.

A  0, A  Mn,

2.

 A   A ,   K, A  Mn

3.

AB  A  B ,

4.

AB  A B ,

verificando:

A 0  A 0

A, B  Mn A, B  Mn

(propiedad submultiplicativa)

Definición 6.2 Dado que en

K n podemos definir una norma vectorial y que Ax  K n , x  K n

podemos construir la norma

A  sup x 0

Ax x

 sup Ax x 1

llamada norma matricial subordinada a la norma vectorial definida en

Kn

Una norma matricial es compatible con una norma vectorial sobre

K n si

Av  A v , v  Kn Algunas normas matriciales subordinadas como la norma uno y la norma infinito pueden calcularse en función de los coeficientes de la matriz: Norma uno:

A 1  sup x 0

Ax 1 x1

 n   max   aij  j 1,... n  i 1 

Máximo de la suma de lo...