método de lu

Índice de términos.

i.i. Lower: inferior.i.ii. Upper: superior.Índice de figuras.

Figura i.i. Matriz cuadrada, es decir una matriz con el número de columnas igual al número de renglones.Figura i.ii. Las matrices [L] y [U] son resultado del proceso del método de LU.Figura i.iii. La multiplicación de las matrices [L] y [U] dan como resultado la matriz [A].Figura i.iv. Diagrama de flujo del método de LU.

Figura i.v. Diagrama de flujo del método de Cholesky.

Figura i.vi. Programa en código C, mostrando la descomposición de una matriz, utilizando el ejemplo número cinco del método de LU.

Figura i.vii. Programa en código C, mostrando la resolución de un sistema de ecuaciones, utilizando el ejemplo número cinco del método de Cholesky.

Resumen

El empleo de métodos numéricos es indispensable para encontrar la respuesta a un problema, pero no todo se basa en el tiempo, hay factores que ocasionan problemas, como lo son la interacción de ciertos materiales, fuerzas.

Objetivo general.

Introducción.

Una matriz simétrica definida positiva puede ser descompuesta como el producto de una matriz triangular inferior y la traspuesta de la matriz triangular inferior. La matriz triangular inferior es el triángulo de Cholesky de la matriz original positiva definida. El resultado de Cholesky ha sido extendido a matrices con entradas complejas. Es una manera de resolver sistemas de ecuaciones matriciales y se deriva de la factorización LU con una pequeña variación.

Cualquier matriz cuadrada A con pivotes no nulos puede ser escrita como el producto de una matriz triangular inferior L y una matriz triangular superior U; esto recibe el nombre de factorización LU. Sin embargo, si A es simétrica y definida positiva, se pueden escoger los factores tales que U es la transpuesta de L, y esto se llama la descomposición o factorización de Cholesky. Tanto la descomposición LU como la descomposición de Cholesky son usadas para resolver sistemas de ecuaciones lineales. Cuando es aplicable, la descomposición de Cholesky es dos veces más eficiente que la descomposición LU.

Marco teorico.

Método de LU y Cholesky.

Son métodos similares para encontrar respuestas a variables que sirven para describir que pasa en cierto punto o área, como una fuerza, presión o temperatura o para establecer un sistema en equilibrio.

Método de Lu.

Su nombre se deriva de las palabras inglesas “Lower" y “Upper”. Estudiando el proceso que se sigue en la descomposición LU es posible comprender el porqué de este nombre, analizando cómo una matriz original se descompone en dos matrices triangulares, una superior y otra inferior. La descomposición LU involucra solo operaciones sobre los coeficientes de la matriz [A], proporcionando un medio eficiente para calcular la matriz inversa o resolver sistemas de álgebra lineal. Primeramente se debe obtener la matriz [L] y la matriz [U]. [L] es una matriz diagonal inferior con números 1 sobre la diagonal. [U] es una matriz diagonal superior en la que sobre la diagonal no necesariamente tiene que haber números 1.El primer paso es descomponer o transformar [A] en [L] y [U], es decir obtener la matriz triangular inferior [L] y la matriz triangular superior [U].

Figura 1.1.

Pasos para encontrar la matriz triangular superior (matriz [U])

1. Hacer cero todos los valores abajo del pivote sin convertir este en 1.2. Para lograr lo anterior se requiere obtener un factor el cual es necesario

para convertir a cero los valores abajo del pivote.3. Dicho factor es igual al número que se desea convertir en cero entre el

número pivote. Este factor multiplicado por -1 se multiplica luego por el pivote y a ese resultado se le suma el valor que se encuentra en la posición a cambiar (el valor en la posición que se convertirá en cero).

Pasos para encontrar la matriz triangular inferior (matriz [L])

Para encontrar la matriz triangular inferior se busca hacer ceros los valores de arriba de cada pivote, así como también convertir en 1 cada pivote. Se utiliza el mismo concepto de “factor” explicado anteriormente y se ubican todos los “factores” debajo dela diagonal según corresponda en cada uno. Esquemáticamente se busca lo de siguiente:

Figura 1.2.

Debido a que [A] = [L] [U], al encontrar [L] y [U] a partir de [A] no se altera en nada la ecuación y se tiene lo siguiente:

Figura 1.3.

Por lo tanto, si Ax=b, entonces LUx=b, de manera que Ax=LUx=b.

Pasos para resolver un sistema de ecuaciones por el método de LU .

1. Obtener la matriz triangular inferior L y la matriz triangular superior U.2. Resolver Ly=b(para encontrar y).3. El resultado del paso anterior se guarda en una matriz nueva de nombre “y”.4. RealizarUx= y (para encontrar x).5. El resultado del paso anterior se almacena en una matriz nueva llamada “x”, la cual brinda los valores correspondientes a las incógnitas de la ecuación.

Método de Cholesky

Cuando se tiene una matriz a coeficientes reales, simétrica y definida positiva, entonces se dispone de una factorización de tipo LU especial, donde U = LT. El método de Cholesky es el que aprovecha la ventaja de la simetría de A para encontrar una matriz L tal que A = L LT. Esta descomposición es única.Si A = L LT, el sistema original A x = b se puede escribir como:

                                               Este método tiene un planteo recursivo, en el que se descomponen sucesivamente los menores principales de la matriz A. Se llamará A[m] a los menores principales de orden m. Se empieza por el menor principal de orden 1,

luego el de orden 2 y así sucesivamente hasta el de orden n, es decir la matriz original. La incógnita es una única matriz triangular inferior L, y su transpuesta hace de matriz triangular superior.

Suponiendo ahora descompuesto el menor de orden k, es decir A[k]= L[k] U[k], interesa estudiar cómo se descompone el siguiente menor principal A[k+1]. Así,A [k+1] = L [k+1] U [k+1]

             Donde f [k+1] = (ak+1 1, ak+1 2, ak+1 3, . . ., ak+1 k)T, y l[k+1] = (lk+1 1, lk+1 2, lk+1 3, . . ., lk+1 k)T

Tras proceder a multiplicar L [k+1] y U [k+1], se obtienen las ecuaciones necesarias para la descomposición del menor principal A [k+1]:                     L[k] l[k+1] = f[k+1]

 El algoritmo que permite obtener la matriz L, a partir de A se escribe a partir de las siguientes expresiones:

Ejemplo 1 del método de CholeskyResolver el siguiente sistema de ecuaciones lineales usando el método de Cholesky

A = [ 6 15 5515 55 22555 225 979 ]

y C= [100150100 ]

En el método de Cholesky el primer paso es encontrar la matriz L usando las fórmulas

lki=aki−∑

j=1

i−1

lij lkj

lii Y lkk=√akk−∑

j=1

k−1

lkj2

La primera ecuación se usa para elementos fuera de la diagonal y la segunda para elementos en la diagonal principal.

Entonces.

l11=√a11=√6 = 2.4495l21=

a21l11

=152 .4495 = 6.1237

l21=a31l11

=552 .4495 = 22.454 Ya sabemos que l12 = 0

l22=√a22−l212 =√55−6 .12372= 4.1833

l32=a32−l21 l31l22

=55−(6 .1237 )(22 .454 )

4 .1833 = 20.916

De igual forma l13 = l23 = 0 y

l33=√a33−( l312 + l32

2 )=√979−(22.4542+20.9162)= 6.1106

La matriz L es igual a

L=[2 .4495 0 06 .1237 4 .1833 022.454 20 .916 6 .1106 ]

En el método de Cholesky U = LT

U=[2 .4495 6 .1237 22 .4540 4 .1833 20 .9160 0 6 .1106 ]

El siguiente paso es encontrar el vector D de la misma manera que en el método de descomposición de LU

d i=ci−∑

j=1

i−1

lijd j

lii

d1=c1l11

=1002 .4495 =40.8246

d2=c2−l21d1l22

=150−(6 .1237)( 40 .8246 )

4 .1833 =-23.9045

d3=c3−( l31d1+ l32d2 )

l33=100−((22 .454 )(40 .8246)+(20.916 )(−23 .9045 )

6 .1106 =-51.826

Finalmente se calcula el vector de incógnitas comenzando por la última x.

x i=d i− ∑

j=i+1

n

uij x j

uii

x3=d3u33 =-8.481

x2=d2−u23 x3u22 =

[−23.9045−(20.916)(−8.481)]4.1833 = 36.69897

x1=d1−(u12 x2+u13 x3 )

u11 = [40.8246 – ((6.1237)(36.69)+(22.454 )(−8.481))]

2.4495 = 2.685

Ejemplo 2 del método de Cholesky

(4 1 21 2 02 0 5)(

x1x2x3

)=(124)l11=2 l21=0.5 l31=1 l22=1.3229 l32=−0.3779 l33=1.9639

( 2 0 00.5 1.3229 01 −0.3779 1.6939)(

y1y2y3

)=(124)y1=0.5

y2=2−(0.5)(0.5)1.3229

=1.3228

y3=4−0.5+(0.3779)(1.3228)

1.6939=2.3613

(2 0.5 10 1.3229 −0.37790 0 1.6939 )(x1x2x3)=( 0.5

1.32282.3616)

x3=2.36161.6939

=1.3941

x2=1.3228+(0.3779)(1.3941)

1.3229=1.3981

x1=0.5−(0.5 ) (1.3981 )−1.3941

2=−0.7965

Ejemplo 3 del método de Cholesky

(4 1 0 2

−1 4 −1 002

−10

4 11 3

)(x1x2x3x4

)=(631612

)[ L ]=(

2 0 0 0−0.5 1.9365 0 001

−0.51640.2582

1.9322 00.5866 1.2607

)(y1y2y3y4

)=(631612

)y1=3

y2=2.3238y3=8.9018y4=2.5213

[LT ]=(2 −0.5 0 10 1.9365 −0.5164 0.258200

00

1.9322 0.58660 1.2607

)(x1x2x3x4

)=(3

2.32388.901862.5213

)x4=2x3=4x2=22 x1=1

Ejemplo 4 del método de Cholesky

(1 2 32 8 43 4 11)(

x1x2x3

)=(010)[ L ]=(1 0 0

2 2 03 −1 1)

[LT ]=(1 2 30 2 −10 0 1 )

(1 0 02 2 03 −1 1)(

y1y2y3

)=(010)y1=0y2=0.5y3=0.5

(1 2 30 2 −10 0 1 )(x1x2x3)=( 00.50.5)

x1=−2.5x2=0.5x3=0.5

Ejemplo 5 del método de Cholesky

( 3 −1 −1−1 2 01 0 1 )(x1x2x3)=(510)

[ L ]=( 1.7320 0 0−0.5773 1.2909 0−0.5773 0.2581 0.7745)

[LT ]=(1.7320 −0.5773 −0.57730 1.2909 0.25810 0 0.7745 )

( 1.7320 0 0−0.5773 1.2909 0−0.5773 0.2581 0.7745)(

y1y2y3

)=(510)y1=2.8867y2=−1.8073y3=−0.3442

(1.7320 −0.5773 −0.57730 1.2909 0.25810 0 0.7745 )(x1x2x3)=(− 2.8867

1.8073−0.3442)

x1=1.3777x2=−1.3111x3=−0.4444

Ejemplo 1 del método de LU

Problema: Encontrar los valores de x1 , x2 , x3 para el siguiente sistema de ecuaciones:

4 x1−2x2−x3=95x1+x2−x3=7x1+2 x2−x3=12

Solucion

[A ]=(4 −2 −15 1 −11 2 −4 ) [B ]=( 9712)

Iteracion 1.Se escuentra el valor de [U ].

(4 −2 −15 1 −11 2 −4)R2=R2−1.25R1R3=R3−0.25R1

(4 −2 −10 3.5 0.250 2.5 −0.75)R3=R3−2.53.7 R2

[U ]=(4 −2 −10 3.5 0.250 0 −0.9285) [ L ]=( 1 0 0

1.25 1 00.25 0.7142 1)

Despejamos a yde Ly=b

( 1 0 01.25 1 00.25 0.7142 1)(

Y 1Y 2Y 3

)=( 9712)Y 1=9

1.25Y 1+Y 2=7→Y 2=7−1.25Y 1=−4.250.25Y 1+0.7142Y 2+Y 3=12→Y 3=12−0.25Y 1−0.7142Y 2=12.7857

El paso siguiente es econtrar a x1 , x2 , x3.

RealizamosUx= y.

(4 −2 −10 3.5 0.250 0 −0.9285)(

X1X2X3

)=( 9−4.2512.7857)

X3=13.7702X 2=−2.1978X1=4.5936

Ejemplo 2 del método de LU

Problema: Encontrar los valores de x1 , x2 , x3 para el siguiente sistema de ecuaciones:

x1 +x2 +x3=112 x1 −1x2 + x3=53 x1 2x2 + x3=29

[A ]=(1 1 12 −1 13 2 1) [B ]=(11529)

(1 1 12 −1 13 2 1)R2=R2−2 R1R3 ¿R3−3 R1 (

1 1 10 −3 −10 −1 −2)R3 ¿ R3+1R1

[U ]=(1 1 10 −3 −10 0 −1) [L ]=(1 0 0

2 1 03 −1 1)

(1 0 02 1 03 −1 1)(

Y 1Y 2Y 3

)=(11529)Y 1=11

Y 2=5−2Y 1=−6

Y 3=24−3Y 1+Y 2=−15

(1 1 10 −3 −10 0 −1)(

x1x2x3

)=( 11−6−15)

x3=15x2=90x1=−94

Ejemplo 3 del método de LU

Problema: Encontrar los valores de x1 , x2 , x3 y x4 para el siguiente sistema de ecuaciones:

2 X1−3 X 2+X3+X4=03 X1+X 2−5 X3+3 X4=−166 X1+2 X 2+X3+X4=−3X1+5 X2+4 X3−3 X 4=−6

[A ]=(2361

−3125

1−514

431

−3) [B ]=(

0−16−3−6

)

(2361

−3125

1−514

431

−3)R2=R2−1.5R1R3=R3−3R1R4=R4−0.5 R1

(2000

−35.5117.5

1−6.5−23.5

4−3−11−5

) R3=R3−2R2R4=R4−1.18 R2

(2000

−35.500

1−6.51111.18

4−3−19

−1.45)R4=R4−1.01 R3 (

2000

−35.500

1−6.5110

4−3−1917.85

)

[U ]=(2000

−35.500

1−6.5110

4−3−1917.85

) [ L ]=(11.530.5

0121.18

0011.01

0001)

(11.530.5

0121.09

0011.01

0001)(Y 1Y 2Y 3Y 4

)=(0

−16−3−6

)Y 1=0

Y 2=−16

Y 3=−3−2Y 2=29

Y 4=−6−1.18Y 2−1.01Y 3=−16.57

(2000

−35.500

1−6.5110

4−3−1917.85

)(X 1X 2X3X4

)=(0

−1629

−16.57)

X 4=0.9278

X3=−0.5371

X2=−12.5821

X1=−14.5358

Ejemplo 4 del método de LU

Problema: Encontrar los valores de x1 , x2 , x3 para el siguiente sistema de ecuaciones:

3 x1 +2 x2 + x3=011 x1 +7 x2 +5x3=019 x1 +17 x2 +13 x3=1

[A ]=( 3 2 111 7 519 17 13) [B ]=(001)

( 3 2 111 7 519 17 13)R2=R2−3.6 R1R3¿ R3−6.3R1 (

3 2 10 −0.3 −1.30 4.3 6.6 )R3 ¿R3+2.16 R1

[U ]=(3 2 10 −0.3 −1.30 0 4.5 ) [ L ]=( 1 0 0

3.6 1 06.3 2.16 1)

( 1 0 03.6 1 06.3 2.16 1)(

Y 1Y 2Y 3

)=(001)Y 1=0

Y 2=0

Y 3=1

(3 2 10 −0.3 −1.30 0 4.5 )(x1x2x3)=(001)

x3=4.5x2=0.8888x1=−0.6666

Ejemplo 5 del método de LU

Problema: Encontrar los valores de x1 , x2 , x3 para el siguiente sistema de ecuaciones:

1 x1 +2x2 +5x3=46 x1 +6x2 +5 x3=−88 x1 −4 x2 +0.1 x3=0.5

[A ]=(1 2 56 6 58 −4 0.1) [B ]=( 4−80.5)

(1 2 56 6 58 −4 0.1)R2=R2−6 R1R3¿R3−8R1 (

1 2 50 −6 −30 −20 −39.9)R3 ¿ R3−3.3333 R1

[U ]=(1 2 50 6 −30 0 −90.1) [ L ]=(1 0 0

6 1 08 3.3333 1)

(1 0 06 1 08 3.3333 1)(

Y 1Y 2Y 3

)=( 4−80.5)Y 1=4

Y 2=−32

Y 3=75.1666

(1 2 50 6 −30 0 −90.1)(

x1x2x3

)=( 4−3247.1666)

x3=0.8934x2=1.8734x1=−1.0858

Algoritmo de programa.

Método de Lu. Inicio.

Ingresar el número de ecuaciones n, las

constantes de la matriz A igualadas a b. A,n,b.

Figura 1.4.

K=1, n-1

K=1, n-1

Factor=AiK / AKK

AKK=Factor

J=k+1, n

Aij=A ij−factor∗Akj

AKK=Factor

i=2, n

Sum=bi

j=1, i-1

Sum=Sum-Aij*bi

bi=sum

X n=bn /Ann

I= 1, n J=i+1, n

I=n-1, 1, -1

X i=¿

Sum=0

Sum=Sum+Aij∗X jX i Fin.

J = 1

1-j

qk

2jkjjjj gSg

I = J+1

J = J+1

INICIO

Ingresa:MAT [S]nxn

MUD

J<=MUD+1 ?

N S

Q = J-MUD Q = 1

I = I+1

J >MUD+1 ?

No

Si

R = J-MUDR = 1

jj

1-j

1k

2jkjj

jj g

gS

g

I >N ?

J>N ?

FINN

N

SS

Figura 1.5.

Prueba de escritorio.

Figura 1.6.

Figura 1.7.

Programa del método.

//Método de LU.

#include<stdlib.h>#include<math.h>#include<string.h>#include <iostream>#include <conio.h>using namespace std;

int main(){int n,m,i,j,k; float a[35][36],b[35][36],apoyo; do {system("cls"); cout<<"\nMETODO DE LU"<<endl; cout<<"\nIngrese el numero de Ecuaciones = "; cin>>n; cout<<"\nIngrese coeficientes\n"; /* Datos para iniciar método */for(i=1;i<=n;i++) {cout<<"\nFila"<<i<<endl; for(j=1;j<=n+1;j++) { cout<<"Ingrese a("<<i<<","<<j<<") = "; cin>>a[i][j]; }}/* Fin Del Ciclo De Solicitud De Datos *//* Proceso Principal */ m=n+1; do {if(a[1][1]==0) {k=m-1; for(i=2;i<=k;i++) {if(a[i][1]!=0) { for(j=1;j<=m;j++){ apoyo=a[i][j];

a[i][j]=a[1][j];a[1][j]=apoyo;}}}}else {for(j=2;j<=m;j++){for(i=2;i<=n;i++) {b[i-1][j-1]=a[i][j]-a[1][j]*a[i][1]/a[1][1]; }}for(j=2;j<=m;j++) {b[n][j-1]=a[1][j]/a[1][1]; }m=m-1;for(j=1;j<=m;j++){for(i=1;i<=n;i++){a[i][j]=b[i][j];}}}}while(m>1); cout<<"\n\nSOLUCION DEL SISTEMA"<<endl; for(i=1;i<=n;i++) {cout<<"\nX("<<i<<") = "<<a[i][1];} getch();}while(1);}

//Método de Cholesky#include <time.h>#include <stdio.h>#include <stdlib.h>#include <cmath>#include <math.h>#include <iostream>#include <fstream>

#include <string.h> #include <conio.h> #include <string>#include <utility>#include <iomanip> #include <windows.h>#include <windows.h>#include<stdlib.h>//#include<iostream.h>#include<math.h>//#include<iomanip.h>#include<string.h>using namespace std;double *cholesky(double *A, int n) { double *L = (double*)calloc(n * n, sizeof(double)); if (L == NULL) exit(EXIT_FAILURE); for (int i = 0; i < n; i++) for (int j = 0; j < (i+1); j++) { double s = 0; for (int k = 0; k < j; k++) s += L[i * n + k] * L[j * n + k]; L[i * n + j] = (i == j) ? sqrt(A[i * n + i] - s) : (1.0 / L[j * n + j] * (A[i * n + j] - s)); } return L;} void show_matrix(double *A, int n) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) printf("%2.5f ", A[i * n + j]); printf("\n"); }} int main() { int n; cout<<"Numero de incosnitas"<<endl; cin>>n; double m1[n*n]; for(int i=0;i<n*n;i++) { cin>>m1[i];

} system("cls"); cout<<"La matriz es:"<<endl<<endl; for(int i=0,c=0;i<n*n;i++) { cout<<m1[i]<<" "; c++; if(c==3) {cout<<endl; c=0;} } cout<<"[L]="<<endl; double *c1 = cholesky(m1, n); show_matrix(c1, n); printf("\n"); free(c1);system("pause"); return 0;}

ConclusionesJuan Pablo López FrancoNo solo se usa un método para resolver todos los problemas o conflictos de una sola área o todas, existen ciertos métodos para cada una, pero un método no podrá resolver todos los problemas de cierta área, así que se tendrán dos o más métodos los cuales parecerán semejantes.Bibliografía

Chapra, Stven; Canale, Raymond. Métodos numéricos para ingenieros. 3ra Edición. McGraw Hill.