RAICES DE ECUACIONES Y SISTEMA DE ECUACIONES Justo Rojas T. Laboratorio de Simulación Computacional de Materiales Facultad de Ciencias Físicas Universidad Nacional Mayor de San Marcos

Abril 24, 2012

Curso de Análisis Numérico, Semestre 2012-I

Justo Rojas T. (LSCM)

AN2012-P5

Abril 24, 2012

1 / 33

Contenido

1

Raices de ecuaciones Ecuaciones lineales y no lineales Raices de ecuaciones no lineales

Método de bisección Método de Newton

2

Raices de Sistema de ecuaciones lineales Métodos de Gauss Factorizaci'on LU

Justo Rojas T. (LSCM)

AN2012-P5

Abril 24, 2012

2 / 33

Introducción El objeto de cálculo de la raiz de una ecuación consiste en hallar los valores de x para los cuales se cumple

f (x ) = 0

(1)

La determinación de las raices de una ecuación es uno de los problemas mas antiguos de la matemética. Su importancia consiste en que una vez hallada la raiz tambien es posible hallar máximos y mínimos, resolver sistema de ecuaciones lineales, valores propios de matrices, etc La solución de la ecuación 1 pude ser muy difícil dependiendo de la naturaleza de f(x). Si f(x) es un polinomio de grado mayor que 4 o bien no es polinómica, no hay ninguna fórmula conocida de solución.

Justo Rojas T. (LSCM)

AN2012-P5

Abril 24, 2012

3 / 33

Ecuaciones lineales y no lineales Linealidad En física y matemática un sistema o ecuación es propiedades de aditividad:

lineal si satisface a las

f (x + y ) = f (x ) + f (y ) y homogeneidad f (ax ) = af (x )

En caso contrario el sistema es no lineal Dicha de otra forma, ecuación lineal es aquella que tiene la forma de un polinomio de primer grado, es decir las incógnitas no estan elevadas a potencias ni multiplicadas entre sí. Ejemplo: 2x + 3y = 4 , 3x − 5y + 2z = 1 Ejemplo de sistema no lineales: x 2 + x − 1 = 0; x − sinx = 0 Justo Rojas T. (LSCM)

AN2012-P5

Abril 24, 2012

4 / 33

Contenido

1

Raices de ecuaciones Ecuaciones lineales y no lineales Raices de ecuaciones no lineales

Método de bisección Método de Newton

2

Raices de Sistema de ecuaciones lineales Métodos de Gauss Factorizaci'on LU

Justo Rojas T. (LSCM)

AN2012-P5

Abril 24, 2012

5 / 33

Método de bisección

Es el método más elemental y antiguo para determinar las raíces de una ecuación. Se basa en el teorema de Bolzano (si una función continua, f(x), toma en los extremos del intervalo [a,b] valores de signo opuesto, entonces la función admite, al menos, una raíz en dicho intervalo.). Consiste en partir de un intervalo [x0,x1]tal que f(x0)f(x1) < 0, por lo que sabemos que existe, al menos, una raíz real. Luego se va reduciendo el intervalo sucesivamente hasta hacerlo tan pequeño como exija la precisión que hayamos decidido emplear.

Justo Rojas T. (LSCM)

AN2012-P5

Abril 24, 2012

6 / 33

Método de Newton Método de recursión efectivo y simple de implementar. Partiendo de un valor tentativo de la raiz, se va mejorando recursivamente aproximando el siguiente valor de la raiz como la intersección con el eje de x la linea tangente en el punto anterior de x. Consiste en elegir adecuadamente un valor de prueba x0 de tal manera que f (x0 ) sea no muy grande. La tangente en el punto x = x0 es f 0(x0), y de la ecuación de la linea tangente que pasa por los puntos (x0 , f (x0 )) y (x1 , f (x1 ) = 0) se obtiene la siguiente aproximación

x

1

=

x

0

+

f (x ) f 0 (x

(2)

0

0

Este procedimiento se repite recursivamente hasta lograr la tolerancia especicada.

xn+ = xn + ff (0(xxn ) (3) n Cuando la primera prueba x es bastante cercana al valor verdadero, los valores sucesivos xn son cada vez mas cercanos y tienden a un 1

0

Justo Rojas T. (LSCM)

AN2012-P5

Abril 24, 2012

7 / 33

Método de Newton

Justo Rojas T. (LSCM)

AN2012-P5

Abril 24, 2012

8 / 33

Método de Newton Ejemplo 5.1 Estimar las raices de la ecuación 2x 3 − 8x + 2 = 0 con tolerancia 0.0001 Las raices estan en las cercanias de -2.4, 0.4, 1.9 Estimando la segunda, tomando como prueba x0 = 0,67

x

1

= 0,67 −

−2,7584 = 0,1501, −5,3066

x −x 1

0

= 0,51981

0,80533 = 0,25257, x2 − x1 = 0,10239 −7,86467 x3 = 0,25257 − −07,01159 = 0,25410 x3 − x2 = 0,00152 ,61722 = 0,254101, x4 − x3 = 0,0000004 x4 = 0,25410 − −0,7000003 ,61259 En consecuencia la raiz es xa = 0,2541 con los 3 primeros díigitos decimales correctos. Las otras raices son xb = −2,1149, xc = 1,8608

x

2

= 0,1501 −

Justo Rojas T. (LSCM)

AN2012-P5

Abril 24, 2012

9 / 33

Sistema de ecuaciones lineales Matrices y sistema de ecuaciones Muchos problemas y fenómenos físicos se representan en forma matricial. Por ej. la relación entre las componentes de la densidad de corriente eléctrica generada en el conductor y el campo eléctrico:

ji = σi ,k Ek

(4)

donde σik son los componentes de una matriz cuadrada  σ11 σ12 σ13 σ =  σ21 σ22 σ23  σ31 σ32 σ33 

j y E son matrices unidimensionales, es decir vectores. En general el sistema de ecuaciones 4 se puede escibir en forma

Ax = b

Justo Rojas T. (LSCM)

AN2012-P5

(5) Abril 24, 2012

10 / 33

Operaciones con matrices Algunas de la principales operaciones con las matrices estan relacionados con: Inversión de la matriz, que consiste en hallar la matriz B tal que se cumpla AB = 1. Solución de un sistema de ecuaciones denida mediante la matriz A y el vector b A.x = b (6) Determinación de los valores propios λi y sus correspondientes vectores propios a de la matriz cuadrada. i

Métodos exactos de solución: Eliminación de Gauss y Gauss-Jordan,

descomposición LU, método de recursión Métodos iterativos : relajación de Jacobi, gradiente conjugado, etc. Justo Rojas T. (LSCM)

AN2012-P5

Abril 24, 2012

11 / 33

Sistema de ecuaciones

Que problemas pueden aparecer al resolver numéricamente sistemas tipo 10? Como almacenar grandes sistemas en la memoria? Las respuestas calculadas son correctas? Cual es la precisión de los resultados? El algoritmo puede ser inestable y en que casos?

Justo Rojas T. (LSCM)

AN2012-P5

Abril 24, 2012

12 / 33

Contenido

1

Raices de ecuaciones Ecuaciones lineales y no lineales Raices de ecuaciones no lineales

Método de bisección Método de Newton

2

Raices de Sistema de ecuaciones lineales Métodos de Gauss Factorizaci'on LU

Justo Rojas T. (LSCM)

AN2012-P5

Abril 24, 2012

13 / 33

Eliminación de Gauss simple

En álgebra lineal: Es un algoritmo para resolver sistema de ecuaciones lineales Encontrar el rango de una matriz Cálculo de la inversa de una matriz cuadrada invertible. Eliminación de Gauss es llamada así por el matemático y cientíco alemán Carl Friedrich Gauss. Las operaciones elementales de la se utiliza para reducir una matriz a la forma escalonada. La eliminación de Gauss-Jordan, una extensin de este algoritmo, se reduce cuanto más lejos de la matriz de forma escalonada reducida.

Justo Rojas T. (LSCM)

AN2012-P5

Abril 24, 2012

14 / 33

Eliminación de Gauss simple El método de eliminación de Gauss permite solucionar sistemas no homogéneos de tipo (6) y es uno de los métodos mas ampliamente usados. Aplicado a sistemas lineales, es decir donde las incognitas aparecen solo en primera potencia, la solución básica del método se basa en la aplicación sistemática de las siguientes operaciones fundamentales:

Operación básica sobre sistemas lineales # 1: Agregar un múltiplo de

una ecuación a otra. El resultado de tales operaciones son sistemas equivalentes y por lo tanto tienen la misma solución. Operación básica # 2: Intercambio de ecuaciones, es decir intercambio de dos las de la matriz. Esta operación surge por ejemplo para el pivoteo.

Justo Rojas T. (LSCM)

AN2012-P5

Abril 24, 2012

15 / 33

Matriz ampliada

Sea M la matriz aumentada del sistema de ecuaciones A.x = b, donde los coecientes ai ,j y bj son conocidos, 

M = (A|b) =    

Que es una matriz

Justo Rojas T. (LSCM)

a a

11 21

.. . aN 1

a a

12 22

... ...

.. . . . . aN 2 . . .

aN b aN b 1

2

.. . aNN

1



  ..  .  2

bN

N × (N + 1)

AN2012-P5

Abril 24, 2012

16 / 33

Eliminación hacia adelante

El procedimiento de eliminación hacia adelante consiste en: 1

2

3

Identicar el elemento de mayor magnitud en la primera columna y asignar i como número de la de ese elemento; intercambiar las las primera y la la i en M y b Sustraer desde la segunda la hasta la n-sima en la matriz los elementos de la primera la multiplicados por un número adecuado para hacer a todos los elementos ai 1 = 0. Repitir este procedimiento para la segunda columna y la la, etc.

De esta manera se obtiene matriz triangular, C.x = e . Los coecientes forman triangulo superior, es decir ci ,j = 0 para todo i > j

Justo Rojas T. (LSCM)

AN2012-P5

Abril 24, 2012

17 / 33

Eliminación hacia adelante

Denición 5.1

Una matriz cuadrada se llama no singular si se puede reducir a la forma triangular superior con todos los elementos diagonales diferentes que cero los pivotes- mediante las operaciones básicas mencionadas.

Denición 5.2

El sistema lineal Ax = b tiene una única solución para cada conjunto de valores de b si y solamente si la matriz de los coecientes es cuadrada y no singular.

Justo Rojas T. (LSCM)

AN2012-P5

Abril 24, 2012

18 / 33

El seudocódigo El seudo código correspondiente de eliminación directa start for j =1 to N if mj ,j = 0 stop, print la matriz no es regular else for i = j + 1 to N set li ,j = mi ,j /mj ,j add -li ,j times row j of M to row i of M next i next j end Una vez convertida la matriz en forma triangular, hallar las incógnitas se consigue mediante la sustitución inversa.

Justo Rojas T. (LSCM)

AN2012-P5

Abril 24, 2012

19 / 33

Sustitución inversa Esto procede mediante:

xN xN −

1

= =

1

aN∗ bN

(7a)

∗

1

∗ aN − ,N − (bN − − aN − ,N xN ) ∗

xi

=

1

1

aii b

∗ ∗( i −

N X

j =i +

(7b)

1

1

1

aij∗ xj )

i = N − 2, ..,1

(7c)

1

De esta manera se halla el vector

x  x  

x Justo Rojas T. (LSCM)

1



  = .   ..  2

xn

AN2012-P5

Abril 24, 2012

20 / 33

Ejemplo Se intenta resolver el siguiente sistema 3x + 2y + z = 1

5x + 3y + 4z = 2

x +y −z =1

Colocamos en forma matricial y resolvemos  .. . 1    5 3 4 ... 2    .. 1 1 −1 . 1 

3 2

. 1 1 −1 .. 1   3 2 1 ... 1  . 5 3 4 .. 2 

1

Justo Rojas T. (LSCM)

AN2012-P5

   

Abril 24, 2012

21 / 33



1

1

. −1 ..

1





 .. . −2   .. 0 −2 −9 . −3

  0 −1 

1

1

  0 −1 

4

0

0

. −1 .. 4 1

1



 .. . −2   .. . 1

De lo cual se tiene

x +y −z =1 −y + 4z = −2 z =1 Con lo que que se resuelve que x = −4, y = 6 y z = 1

Justo Rojas T. (LSCM)

AN2012-P5

Abril 24, 2012

22 / 33

Ejercicio

Se tiene el sistema de ecuaciones en forma de matriz ampliada  .. . 3    0,56 −1,56 0,32 ... 1    .. −0,24 1,24 −0,28 . 0 

−0, 04

0,04

0,12

Solución

x

Justo Rojas T. (LSCM)

7,0 =  7,0  25,0 

AN2012-P5



Abril 24, 2012

23 / 33

Contenido

1

Raices de ecuaciones Ecuaciones lineales y no lineales Raices de ecuaciones no lineales

Método de bisección Método de Newton

2

Raices de Sistema de ecuaciones lineales Métodos de Gauss Factorizaci'on LU

Justo Rojas T. (LSCM)

AN2012-P5

Abril 24, 2012

24 / 33

Concepto

En álgebra lineal, la factorización o descomposición LU (del inglés Lower-Upper) es una forma de factorización de una matriz como el producto de una matriz triangular inferior y una superior. Debido a la inestabilidad de este método, por ejemplo si un elemento de la diagonal es cero, es necesario premultiplicar la matriz por una matriz de permutación. Método llamado factorización PA = LU o LU con pivote. Esta descomposición se usa en el análisis numérico para resolver sistemas de ecuaciones (mas ecientemente) o encontrar las matrices inversas.

Justo Rojas T. (LSCM)

AN2012-P5

Abril 24, 2012

25 / 33

El sistema de ecuaciones Ax = b puede ser resuelto fácilmente si se puede transformar la matriz A como producto de 2 matrices triangulares

A = LU

(8)

donde L - es una matriz especial triangular inferior y U - matriz triangular superior, con los elemetos diagonales D (U ) = lii todos diferentes que cero, que representan los pivotes; y D (L) = uii = 1, es decir 

L=   

l

1

21

.. . lN 1

 ... 0 ... 0    .. . 0  ... ... 1

Justo Rojas T. (LSCM)

0 1 .. .



u

11

 0

U=  

AN2012-P5

.. . 0

u u

12 22

.. .

...

... ...

..

0

.

uN uN 1

2

.. . uNN

Abril 24, 2012

    

26 / 33

La ecuacin (8) se reescribe como LU .x = b ≡ L.(U .x ) = b Notando que y = U .x es un nuevo vector, el sistema en general se resuelve en dos etapas: La primera consiste en resolver el sistema triangular izquierdo

Ly = b

(9)

respecto al vector y mediante la sustitucin hacia adelante. Explícitamente como sigue

y yi

1

Justo Rojas T. (LSCM)

=

b i− X bi − lij yj ; i = 2, ...N

(10a)

1

1

=

j=

(10b)

1

AN2012-P5

Abril 24, 2012

27 / 33

Segundo, se resuelve nalmente el sistema resultante

Ux = y

Los valores del vector

xN xi

Justo Rojas T. (LSCM)

= =

x se hallan por sustitución hacia atraz mediante: 1

uNN yN 1 u (yi − ii

(11)

(12a)

N X j =i +

uij xj ); i = N − 1, . . . 1

(12b)

1

AN2012-P5

Abril 24, 2012

28 / 33

Como hallar las matrices L y U?

Primer método de factorización de una matriz cuadrada mediante la eliminación de Gauss para obtener la matriz superior U . Los elementos de L se puede determinar directamente por el múltiplo con signo negativo para hacer cero el elemento  correspondiente.  1 1 3 Ejemplo Factorizar la matriz A = 4 2 5 2 6 4

Justo Rojas T. (LSCM)

AN2012-P5

Abril 24, 2012

29 / 33

Para hacer cero los coecientes a21 , a31 es necesario multiplicar primero por -4 y luego por -2 la primera ecuación y sumar con las las 2 y 3, respectivamente . En la matriz resultante. 1 1 3  A = 0 −2 −7 0 4 −2 



anular el coeciente a32 se logra multiplicando por 2 la segunda ecuación. La matriz superior es,   1 1 3 U = 0 −2 −7  0 0 −16

Justo Rojas T. (LSCM)

AN2012-P5

Abril 24, 2012

30 / 33

Y los correspondientes coecientes de

L son

1 0 0  L = 4 1 0 2 −2 1 



Segundo caso, se obtiene teniendo en cuenta que los elementos del producto de matrices

N X k=

lik ukj = aij ; i = 1, ...N ; j = 1, ...N

1

forman N ecuaciones con N 2 + N incógnitas. Ya que el número de incógnitas es mayor, se puede eligir lii = 1(i = 1, ..N ).

Justo Rojas T. (LSCM)

AN2012-P5

Abril 24, 2012

31 / 33

Además por la estructura de las matrices U y L, el índice de sumación no toma todos los valores.

i j :

1

j X k=

lik ukj = aij

1

Procedimiento de Crout para la evaluación de los elemntos uij y lij Para j=1,2,...N calcular:

uj

=

aj

uij

=

aij −

1

1

i −1 X k=

(13a)

lik ukj ; i = 2, ...j

(13b)

1

j −1 X 1 lij = u (aij − lik ukj ); i = j + 1, ..N jj k =1

Justo Rojas T. (LSCM)

AN2012-P5

(13c)

Abril 24, 2012

32 / 33

Problemas

Descomponer la matriz A en forma de matrices

LyU

2 −1 0 A =  −1 2 −1  0 −1 2 y hallar los valores del vector x = (x1 x2 x3 )T si el vector 

Justo Rojas T. (LSCM)



AN2012-P5

b = (132)T

Abril 24, 2012

33 / 33