sábado, 26 de mayo de 2012

Método de Cramer



La regla de Cramer es un teorema en álgebra lineal, que da la solución de un sistema lineal de ecuaciones en
 términos de determinantes. Recibe este nombre en honor a Gabriel Cramer (1704 - 1752), quien publicó la regla
en su Introduction à l'analyse des lignes courbes algébriques de 1750, aunque Colin Maclaurin también publicó el
método en su Treatise of Geometry de 1748 (y probablemente sabía del método desde 1729).1
La regla de Cramer es de importancia teórica porque da una expresión explícita para la solución del sistema.
 Sin embargo, para sistemas de ecuaciones lineales de más de tres ecuaciones su aplicación para la resolución
del mismo resulta excesivamente costosa: computacionalmente, es ineficiente para grandes matrices y por ello
no es usado en aplicaciones prácticas que pueden implicar muchas ecuaciones. Sin embargo, como no es
necesario pivotar matrices, es más eficiente que la eliminación gaussiana para matrices pequeñas, particularmente cuando son usadas operaciones SIMD.
Si \mathbf{Ax} = \mathbf{b} es un sistema de ecuaciones. \mathbf{A} es la matriz de coeficientes del sistema,
 \mathbf{x} = (x_1,\dots,x_n) es el vector columna de las incógnitas y \mathbf{b} es el vector columna de los términos
 independientes. Entonces la solución al sistema se presenta así:

   x_j =
   \cfrac {
      \det(\mathbf{A}_j)
   }{
      \det(\mathbf{A})
   }
donde \mathbf{A}_j es la matriz resultante de reemplazar la j-ésima columna de \mathbf{A} por el vector columna \mathbf{b}.
Hágase notar que para que el sistema sea compatible determinado, el determinante de la matriz \mathbf{A} ha de ser
no nulo.

Sistema de 2 ecuaciones con 2 incógnitas

Para la resolución de un sistema de dos ecuaciones con dos incógnitas, de la forma. Dado el sistema de
ecuaciones:

   \begin{cases} 
      a{\color{blue}x} + b{\color{blue}y} = {\color{red}e}\\ 
      c{\color{blue}x} + d{\color{blue}y} = {\color{red}f}
   \end{cases}
Lo representamos en forma de matrices:

   \begin{bmatrix}
       a & b \\
       c & d 
   \end{bmatrix}
   \begin{bmatrix}
      {\color{blue}x} \\
      {\color{blue}y}
   \end{bmatrix}=
   \begin{bmatrix}
      {\color{red}e}  \\
      {\color{red}f}
   \end{bmatrix}
Entonces, x e y pueden ser encontradas con la regla de Cramer, con una división de determinantes, de la
siguiente manera:

   x =
   \frac {
      \begin{vmatrix}
         \color{red}{e} & b \\
         \color{red}{f} & d
      \end{vmatrix}
   }{
      \begin{vmatrix}
         a & b \\
         c & d
      \end{vmatrix}
   } = 
   \frac{
      {\color{red} e } d - b {\color{red} f }
   }{
      ad - bc
   }; \quad
   y =
   \frac {
      \begin{vmatrix}
         a & \color{red}{e} \\
         c & \color{red}{f}
      \end{vmatrix}
   }{
      \begin{vmatrix}
         a & b \\
         c & d
      \end{vmatrix}
   } = 
   \frac{
      a{\color{red} f } - {\color{red} e } c 
   }{
      ad - bc
   }

[editar]Sistema de 3 ecuaciones con 3 incógnitas

La regla para un sistema de tres ecuaciones con tres incógnitas es similar, con una división de determinantes:

   \begin{cases} 
      a{\color{blue}x} + b{\color{blue}y} + c{\color{blue}z} = {\color{black}j}\\ 
      d{\color{blue}x} + e{\color{blue}y} + f{\color{blue}z} = {\color{black}k}\\
      g{\color{blue}x} + h{\color{blue}y} + i{\color{blue}z} = {\color{black}l}
   \end{cases}
Que representadas en forma de matriz es:

   \begin{bmatrix}
      a & b & c \\
      d & e & f \\
      g & h & i
   \end{bmatrix}
   \begin{bmatrix}
      {\color{blue}x} \\
      {\color{blue}y} \\
      {\color{blue}z}
   \end{bmatrix} =
   \begin{bmatrix}
      {\color{red}j} \\
      {\color{red}k} \\
      {\color{red}l} 
   \end{bmatrix}
xyz pueden ser encontradas como sigue:

   x =
   \frac {
      \begin{vmatrix}
         {\color{red}j} & b & c \\
         {\color{red}k} & e & f \\
         {\color{red}l} & h & i
      \end{vmatrix}
   }{
      \begin{vmatrix} a & b & c \\
         d & e & f \\
         g & h & i
      \end{vmatrix}
   }; \quad
   y =
   \frac {
      \begin{vmatrix}
         a & {\color{red}j} & c \\
         d & {\color{red}k} & f \\
         g & {\color{red}l} & i
      \end{vmatrix}
   }{
      \begin{vmatrix}
         a & b & c \\
         d & e & f \\
         g & h & i
      \end{vmatrix}
   } , \quad
   z =
   \frac {
      \begin{vmatrix}
         a & b & {\color{red}j} \\
         d & e & {\color{red}k} \\
         g & h & {\color{red}l}
      \end{vmatrix}
   }{
      \begin{vmatrix}
         a & b & c \\
         d & e & f \\
         g & h & i
      \end{vmatrix}
   }

[editar]Demostración

Sean:

   \mathbf x =
   \begin{pmatrix}
      x_1 \\
      x_2 \\
      x_3
   \end{pmatrix}
   ; \quad
   \mathbf A =
   \begin{bmatrix}
      a_{1,1} & \cdots & a_{1,n} \\
      \vdots & \ddots & \vdots \\
      a_{n,1} & \cdots & a_{n,n}
   \end{bmatrix}
   ; \quad
   \mathbf b =
   \begin{pmatrix}
      b_1 \\
      b_2 \\
      b_3
   \end{pmatrix}

   \mathbf A_j =
   \left [
      \begin{array}{llllllll}
         a_{1,1}   & \cdots & a_{1,j-1}  & b_1     & a_{1,j+1}   & \cdots & a_{1,n}   \\
         a_{2,1}   & \cdots & a_{2,j-1}  & b_2     & a_{2,j+1}   & \cdots & a_{2,n}   \\
                                                                                      \\
         \vdots    &        &            & \ddots  &             &        & \vdots    \\
                                                                                      \\
         a_{n-1,1} & \cdots & a_{n-1,j-1}& b_{n-1} & a_{n-1,j+1} & \cdots & a_{n-1,n} \\
         a_{n,1}   & \cdots & a_{n,j-1}  & b_n     & a_{n,j+1}   & \cdots & a_{n,n}
      \end{array}
   \right ]
Usando las propiedades de la multiplicación de matrices:

   \mathbf A \mathbf x = \mathbf b \Leftrightarrow
   \mathbf A^{-1} \mathbf A \mathbf x = \mathbf A^{-1} \mathbf b \Leftrightarrow
   \mathbf{Ix} = \mathbf A^{-1} \mathbf b \Leftrightarrow
   \mathbf x = \mathbf A^{-1} \mathbf b
entonces:

   \mathbf x = \mathbf A^{-1} \mathbf b =
   \frac{
      (\operatorname{Adj} \mathbf A)^t
   }{
      \left|
         \mathbf A
      \right|
   } \;
   \mathbf b

   (\operatorname{Adj}\mathbf A)^t =
   \frac{\mathbf A^\prime_{pl}}{\mathbf A^\prime_{pl}} =
    \mathbf A_{lp}
Por lo tanto:

   \mathbf A^{-1} \mathbf b =
   \sum_{i=1}^n
   \frac{
      \mathbf A^\prime_{ji}
   }{
      \left |
         \mathbf A
      \right |
   }
   b_{ik} =
   \frac{
      \sum_{i=1}^n \mathbf A_{ij} b_i
   }{
      \left |
         \mathbf A 
      \right |
   }
   =
   \cfrac {
      \left |
         \mathbf A_j
      \right |
   }{
      \left |
         \mathbf A
      \right |
   }
Aparte, recordando la definición de determinante, la sumatoria definida acumula la multiplicación del elemento
 adjunto o cofactor de la posición ij, con el elemento i-ésimo del vector \mathbf B (que es precisamente el elemento
 i-èsimo de la columna j, en la matriz \mathbf{A}_j).

Método de Gauss-Jordan


Otros documentos de este método en pdf:
http://www.uaem.mx/posgrado/mcruz/cursos/mn/JORDAN.pdf
http://www.slideshare.net/algebralineal/mtodos-de-resolucin-metodo-de-gauss-jordan

Método de Gauss


El método de Gauss consiste en convertir un sistema "normal" de 3 ecuaciones con 3 incógnitas en uno escalonado , en el que la 1ª ecuación tiene 3 incógnitas , la 2ª tiene 2 incógnitas y la tercera 1 incógnita . De esta forma será fácil a partir de la última ecuación y subiendo hacia arriba , calcular el valor de las 3 incógnitas .
Para transformar el sistema en uno que sea escalonado se combinarán las ecuaciones entre sí (sumándolas , restándolas , multiplicándolas por un número , etc.)
Ejemplo :
La 1ª ecuación siempre se deja igual , (procurando que esta sea la más sencilla) y a la 2ª y 3ª ecuación se debe anular el término que lleva la x .

Una vez que hemos anulado los términos en x debemos dejar fija la 1ª y 2ª ecuación y anular el término que lleva la y en la 3ª ecuación
De la última ecuación obtenemos que z = -256/-128 = 2, que sustituyendo en B’’ resulta
- y + 9·2 = 13 Þ y = 5
y a su vez sustituyendo en A’’ obtenemos que :
2x + 3·5 – 7·2 = -1 Þ x = -1
Por lo tanto la solución del sistema es (-1, 5, 2)
Clasificación de los sistemas :
Los sistemas de ecuaciones pueden ser de 3 tipos :
  1. Sistema compatible determinado (S.C.D.) : una única solución
  2. Sistema compatible indeterminado (S.C.I.) : infinitas soluciones
  3. Sistema incompatible (S.I.) : no tiene solución
En el ejemplo anterior hemos obtenido un S.C.D. pero ¿cuándo obtendremos los otros dos tipos? .
  • Cuando al realizar Gauss obtengamos 0 = K , siendo K un número distinto de 0 , tendremos un S.I. ya que obtenemos un absurdo .
Por ejemplo :

Dejamos fija la 1ª ecuación e intentamos anular la x de la 2ª y 3ª
Quitamos la y de la 3ª ecuación :
Como se observa hemos obtenido un absurdo , ya que 0 no es igual a 12 , por lo que el sistema no tiene solución .
  • Cuando al realizar Gauss obtengamos 0 = 0 , es decir se nos anule alguna ecuación , y el sistema resultante tenga más incógnitas que ecuaciones tendremos un S.C.I. en función de uno o dos parámetros (depende de las ecuaciones que se anulen) .
Por ejemplo :
Dejamos como siempre la 1ª ecuación igual e intentamos quitar la incógnita x de la 2ª y 3ª ecuación .
Si intentamos anular la y de la 3ª ecuación vemos que se nos anula la 3ª ecuación
Obtenemos por tanto un sistema con dos ecuaciones y 3 incógnitas (hay más incógnitas que ecuaciones) por lo que tendrá infinitas soluciones . Una de ellas sería por ejemplo dar a la z el valor z=0 y así obtendríamos que y = -13 , x = 19

Sistema de ecuaciones lineales


En matemáticas y álgebra lineal, un sistema de ecuaciones lineales, también conocido como sistema lineal de ecuaciones o simplemente sistema lineal, es un conjunto de ecuaciones lineales (es decir, un sistema de ecuaciones en donde cada ecuación es de primer grado), definidas sobre un cuerpo o un anillo conmutativo. Un ejemplo de sistema lineal de ecuaciones sería el siguiente:

    \left \{
        \begin{array}{rcrcrcr}
             3 \,x_1 & + & 2\,x_2             & + &   \,x_3 & = & 1  \\
             2 \,x_1 & + & 2\,x_2             & + & 4 \,x_3 & = & -2 \\
             - \,x_1 & + & \frac{1}{2} \,x_2  & - &   \,x_3 & = & 0
        \end{array}
    \right .
El problema consiste en encontrar los valores desconocidos de las variables x1x2 y x3 que satisfacen las tres ecuaciones.
El problema de los sistemas lineales de ecuaciones es uno de los más antiguos de la matemática y tiene una infinidad de aplicaciones, como en procesamiento digital de señalesanálisis estructural, estimación, predicción y más generalmente en programación lineal así como en la aproximación de problemas no lineales de análisis numérico.
En general, un sistema con m ecuaciones lineales y n incógnitas puede ser escrito en forma normal como:

   \begin{matrix}
      a_{11}x_1 & + a_{12}x_2 & + \dots & + a_{1n}x_n & = b_1 \\
      a_{21}x_1 & + a_{22}x_2 & + \dots & + a_{2n}x_n & = b_2 \\
      \dots     & \dots       & \dots   & \dots       & \dots \\
      a_{m1}x_1 & + a_{m2}x_2 & + \dots & + a_{mn}x_n & = b_m
   \end{matrix}
Donde x_1,\dots,x_n\, son las incógnitas y los números a_{ij}\in\mathbb{K} son los coeficientes del sistema sobre el cuerpo \mathbb{K}\ [= \R, \mathbb{C}, \dots]. Es posible reescribir el sistema separando con coeficientes con notación matricial:
(1)
   \begin{bmatrix}
      a_{11} & a_{12} & \cdots & a_{1n} \\
      a_{21} & a_{22} & \cdots & a_{2n} \\
      \vdots & \vdots & \ddots & \vdots \\
      a_{m1} & a_{m2} & \cdots & a_{mn}
   \end{bmatrix} 
   \begin{bmatrix}
      x_1 \\
      x_2 \\
      \vdots \\
      x_n
   \end{bmatrix} =
   \begin{bmatrix}
      b_1 \\
      b_2 \\
      \vdots \\
      b_m
   \end{bmatrix}
Si representamos cada matriz con una única letra obtenemos:

   \mathbf{Ax} = \mathbf{b}
Donde A es una matriz m por nx es un vector columna de longitud n y b es otro vector columna de longitud m. El sistema de eliminación de Gauss-Jordan se aplica a este tipo de sistemas, sea cual sea elcuerpo del que provengan los coeficientes.

Otros enlaces de Sistemas de Ecuaciones Lineales:

Método de Newton-Raphson

En análisis numérico, el método de Newton (conocido también como el método de Newton-Raphson o el método de Newton-Fourier) es un algoritmo eficiente para encontrar aproximaciones de losceros o raíces de una función real. También puede ser usado para encontrar el máximo o mínimo de una función, encontrando los ceros de su primera derivada.

Descripción del método

La función ƒ es mostrada en azul y la línea tangente en rojo. Vemos que xn+1 es una mejor aproximación que xn para la raíz x de la función f.
El método de Newton-Raphson es un método abierto, en el sentido de que su convergencia global no está garantizada. La única manera de alcanzar la convergencia es seleccionar un valor inicial lo suficientemente cercano a la raíz buscada. Así, se ha de comenzar la iteración con un valor razonablemente cercano al cero (denominado punto de arranque o valor supuesto). La relativa cercanía del punto inicial a la raíz depende mucho de la naturaleza de la propia función; si ésta presenta múltiples puntos de inflexión o pendientes grandes en el entorno de la raíz, entonces las probabilidades de que el algoritmo diverja aumentan, lo cual exige seleccionar un valor supuesto cercano a la raíz. Una vez que se ha hecho esto, el método linealiza la función por la recta tangente en ese valor supuesto. La abscisa en el origen de dicha recta será, según el método, una mejor aproximación de la raíz que el valor anterior. Se realizarán sucesivas iteraciones hasta que el método haya convergido lo suficiente. f'(x)= 0 Sea f : [a,b-> R función derivable definida en el intervalo real [ab]. Empezamos con un valor inicial x0 y definimos para cada número natural n
x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}.
Donde f ' denota la derivada de f.
Nótese que el método descrito es de aplicación exclusiva para funciones de una sola variable con forma analítica o implícita cognoscible. Existen variantes del método aplicables a sistemas discretos que permiten estimar las raíces de la tendencia, así como algoritmos que extienden el método de Newton a sistemas multivariables, sistemas de ecuaciones, etc.

Código en C

Programa escrito en C correspondiente al ejemplo f(x) = cos(x) - x3.
#include <stdio.h>
#include <math.h>
 
double FuncionIteracion(double x);
 
int main() {
   int i;
   double x, xvieja;
 
   xvieja = 0.5; // valor inicial
 
   printf("Iteracion      valor\n");
   for(i=0; i<8; i++){
      x = FuncionIteracion(xvieja);
      xvieja = x;
      printf("%5.0d  %20.12f\n", i+1, x);
   }
 
   return 0;
}
 
double FuncionIteracion(double x)
{
   double valorFuncion, funcionOriginal, funcionDerivada;
 
   funcionOriginal = cos(x) - pow(x, 3);
   funcionDerivada = -sin(x) - 3*pow(x, 2);
   valorFuncion = x - funcionOriginal / funcionDerivada;
 
   return valorFuncion;
}
Para compilar en GNU/Linux con compilador de GNU, se escribe en una terminal:
$ gcc programa.c -lm -o programa
donde la opción -lm le indica al compilador que utilice la biblioteca de matemáticas.

[editar]Codigo en Matlab

Programa escrito en Matlab para hallar las raíces usando el método de NEWTON-RAPHSON
% Al escribir la función, usar x como variable.
x0=input('Ingrese el valor inicial: ');
tol=input('Ingrese el porcentaje de error: ');
f=input('Ingrese la función: ');
i=1;
fx(i)=x0;
syms x;
f1=subs(f,x,fx(i));
z=diff(f);
d=subs(z,x,fx(i));
ea(1)=100;
while abs(ea(i))>=tol;
    fx(i+1)=fx(i)-f1/d; f1=subs(f,x,fx(i+1)); d=subs(z,x,fx(i+1));
    ea(i+1)=abs((fx(i+1)-fx(i))/fx(i+1)*100);
    i=i+1;
end
fprintf('i     fx(i)         Error aprox (i) \n');
for j=1:i;
    fprintf('%2d \t %11.7f \t %7.3f \n',j-1,fx(j),ea(j));
end
El programa siguiente hace el cálculo para una superficie.
syms x1
syms x2
syms x3
V=['sin(x1)+2^x2+log(x3)-7';'3*x1+2*x2-x3^3+1      ';'x1+x2+x3-5            '];
%se calcula el jacobiano:
DV(1,:)=[diff(V(1,:),x1), diff(V(1,:),x2),diff(V(1,:),x3)];
DV(2,:)=[diff(V(2,:),x1), diff(V(2,:),x2),diff(V(2,:),x3)];
DV(3,:)=[diff(V(3,:),x1), diff(V(3,:),x2),diff(V(3,:),x3)];
%se da el valor de partida:
x1=0;
x2=4;
x3=2;
x_1o=[x1;x2;x3];
%se calcula H en ese punto
Vo(1,:)=eval(V(1,:));
Vo(2,:)=eval(V(2,:));
Vo(3,:)=eval(V(3,:));
%Se calcula el Hessiano en ese punto
DV1=eval(DV);
%se calcula la Inversa del Hessiano en ese punto
DV_1=DV1^-1;
%se calcula el siguiente valor de iteración
x_1=[x1;x2;x3]-DV_1*Vo;
%cantidad de iteraciones maxima:
n=50; 
%se define a = n, si se cumple condicion de error antes,  cambia
a=n; 
 
for i=1:n  
%error relativo entre aproximaciones sucecivas
    er=norm(x_1-x_1o)/norm(x_1);
    if er<.0001
        a=i;
       'break;' end
 
    x1=x_1(1);
    x2=x_1(2);
    x3=x_1(3);
    x_1o=[x1;x2;x3];
    Vo(1,:)=eval(V(1,:));
    Vo(2,:)=eval(V(2,:));
    Vo(3,:)=eval(V(3,:));
    DV1=eval(DV);
    DV_1=DV1^-1;
    x_1=[x1;x2;x3]-DV_1*Vo;  
 
end
    a
    x_1

Otros documento en PDF del mismo método:
http://www.epsem.upc.edu/~fpq/ale-hp/modulos/aplicaciones/newton.pdf
http://www.mty.itesm.mx/etie/deptos/m/ma00-130/lecturas/m130-18.pdf
http://www.mty.itesm.mx/etie/deptos/m/ma00-130/lecturas/m130-18.pdf

Método de la Regla falsa o Punto fijo


El método de la regla falsa, o “falsa posición”, es otro de los muchos métodos iterativos para la resolución de problemas con ecuaciones no lineales. La peculiaridad de éste, es que combina dos métodos: el método de bisección y el de la secante (ya explicados en otros artículos).
A continuación veremos una explicación de en qué consiste, y más abajo, os pongo los pasos a desarrollar.
Se basa en trazar una recta que una los extremos de un intervalo dado, considerando que la solución está cerca de uno de éstos extremos.
Hemos agregado por tanto, esa línea recta que une el intervalo [a,b]. La idea principal es que si tomamos el punto donde la recta corta el eje x, estaremos más cerca de hallar la raíz.
Entonces, supongamos que tenemos una función f(x), que es continua en el intervalo [xa, xb], y que además f(xa) y f(ba) tienen signos opuestos (RECORDATORIO: Teorema Bolzano) por lo que se deduce que existe al menos una solución para esa ecuación.
Ahora, necesitamos saber la ecuación de la línea recta que une esos dos puntos. Para ello nos ayudamos de la ecuación punto-pendiente, por eso, hallamos la pendiente:
Ahora vamos a sustituir eso en la ecuación de la recta:
Pero recordamos que la recta en cuestión corta el eje x, así que hacemos y=0:
Simplificamos multiplicando todo por xb-xa, para quitar el denominador:
Como paso final, despejamos la incógnita x:
Vamos ahora a describir paso a paso como se desarrolla el método de la regla falsa (considerando f(x) continua):
1) Primero debemos encontrar unos valores iniciales xa y xb tales que:
2) Aproximamos a la raíz, para ello usamos:
3) Evaluamos f(xr). Se pueden dar hasta tres casos:
A)
Como f(xa) y f(xr) tienen signos opuestos, por la condición mencionada anteriormente deducimos que, la raíz se encuentra en el intervalo [xa, xr]
B)
f(xa) y f(xr) tienen el mismo signo. Así que xb y xr han de tener signos distintos, pues:
Por tanto, la raíz se encuentra en el intervalo [xr, xa].
*Pista: Como consideramos que la ecuación tiene que ser continua (si o si), al darse este caso, no cumpliría con la condición de continuidad, al menos que tomemos como referencia un tercer punto (xr) cuya imagen (f(xr)) será de signo opuesto.
C)
En este caso, como f(xr)=0 ya tenemos localizada la raíz.

Debemos repetir estos 3 pasos señalados anteriormente hasta que:
|Ea|<Eb