solución numérica de sistemas de ecuaciones lineales · pdf file3 ilustraciones...
TRANSCRIPT
2014
Alejandro González Vásquez
Manuela Yepes Gómez
Universidad EAFIT
Solución numérica de sistemas de ecuaciones lineales
1
MÉTODOS NUMÉRICOS PARA INGENIEROS
ALEJANDRO GONZÁLEZ VÁSQUEZ 201310040014
MANUELA YEPES GÓMEZ 201110025012
Trabajo escrito
Solución numérica de sistemas de ecuaciones lineales
Procesos numéricos ST0241
Docente: Gabriel Jaime Castaño Chica
Noviembre 3
UNIVERSIDAD EAFIT
FALCULTAD DE INGENIERÍA
MEDELLÍN
2014
2
TABLA DE CONTENIDO
1. INTRODUCCIÓN .............................................................................................. 4
2. OBJETIVOS ...................................................................................................... 5
2.1 OBJETIVO GENERAL ......................................................................................................5
2.2 OBJETIVOS ESPECÍFICOS ...........................................................................................5
3. MARCO TEÓRICO ........................................................................................... 6
3.1 SISTEMAS DE ECUACIONES LINEALES ...................................................................6
3.2 MÉTODOS DIRECTOS DE SOLUCIÓN .......................................................................7
3.2.1 Eliminación gaussiana simple .......................................................................................7
3.2.2 Eliminación gaussiana con pivoteo parcial .................................................................9
3.3.3 Factorización LU de matrices ..................................................................................... 12
3.3 MÉTODOS ITERATIVOS.............................................................................................. 14
3.3.1 Criterios de parada y medición del error................................................................... 15
3.3.2 Método de Jacobi. ........................................................................................................ 15
3.3.3 Método de Gauss Seidel ............................................................................................. 16
3.3.4 Método de S.O.R .......................................................................................................... 16
3.4 INTERPOLACIÓN POLINOMIAL ...................................................................................... 17
3.4.1 Interpolación polinomial de Newton en diferencias divididas ................................ 18
4. CUADRO COMPARATIVO ............................................................................. 20
5. CONCLUSIONES ........................................................................................... 21
6. ANEXOS ......................................................................................................... 22
ANEXO A. .................................................................................................................................... 22
ANEXO B. .................................................................................................................................... 23
ANEXO C. ................................................................................................................................... 23
ANEXO D. ................................................................................................................................... 23
7. BIBLIOGRAFÍA .............................................................................................. 24
3
ILUSTRACIONES
ILUSTRACIÓN 1. SISTEMA DE ECUACIONES LINEALES .............................................. 6
ILUSTRACIÓN 2. FORMA MATRICIAL DE UN SISTEMA DE ECUACIONES .................. 6
ILUSTRACIÓN 3. MATRIZ AUMENTADA ......................................................................... 7
ILUSTRACIÓN 4. PASO 2. OPERACIONES FILA. ELIMINACIÓN GAUSSIANA SIMPLE 8
ILUSTRACIÓN 5.PASO 3. OPERACIONES FILA. ELIMINACIÓN GAUSSIANA SIMPLE . 8
ILUSTRACIÓN 6. MATRIZ TRIANGULAR SUPERIOR. .................................................... 8
ILUSTRACIÓN 7. SELECCIÓN DEL PIVOTE. EG CON PIVOTEO PARCIAL ................ 10
ILUSTRACIÓN 8. INTERCAMBIO DE FILAS. EG CON PIVOTEO PARCIAL ................. 10
ILUSTRACIÓN 9. FACTORIZACIÓN LU DE UNA MATRIZ CUADRADA A .................... 12
ILUSTRACIÓN 10. DESCOMPOSICIÓN D-L-U DE UNA MATRIZ A .............................. 15
ILUSTRACIÓN 11. POLINOMIO INTERPOLANTE DE NEWTON ................................... 18
ILUSTRACIÓN 12. REPRESENTACIÓN GRÁFICA DE LA NATURALEZA RECURSIVA
DE LAS DIFERENCIAS DIVIDIDAS FINITAS. .......................................................... 19
TABLAS
TABLA 1. MÉTODOS DE FACTORIZACIÓN LU ............................................................ 12
TABLA 2. DIFERENCIAS DIVIDIDAS FINITAS. .............................................................. 18
TABLA 3. CUADRO COMPARATIVO ............................................................................. 20
4
1. INTRODUCCIÓN
El arte de la ingeniería consiste en la capacidad de plantear y resolver modelos
matemáticos que expliquen realidades complejas; los sistemas de ecuaciones
lineales son muy utilizados en este campo, sin embargo, cuando el ingeniero se
enfrenta a situaciones en donde muchas variables intervienen, se requiere de un
gran número de operaciones aritméticas para dar solución al sistema y por lo tanto
se deben emplear herramientas de cálculo que agilicen este proceso.
Según el autor (Zabala, 2011): La computación provee el software y el hardware
que garantizan la calidad y eficiencia de la solución, pero es el análisis numérico el
que sustenta y selecciona el método de solución adecuado. A partir del desarrollo
de algoritmos que describen métodos numéricos para resolver sistemas de
ecuaciones lineales se logra ahorrar tiempo de cómputo, posiciones de memoria y
reducción de la propagación de error. Gracias a la combinación de estos dos
elementos es que los ingenieros pueden analizar y diseñar de forma eficiente y
eficaz estructuras civiles, circuitos eléctricos, sistemas mecánicos, hidráulicos,
térmicos o asignar recursos dentro de un sistema productivo teniendo en cuenta
las restricciones del mismo, entre otras muchas aplicaciones que contribuyen al
desarrollo industrial, tecnológico y científico.
En este informe se presentarán diferentes métodos para la solución numérica de
sistemas de ecuaciones lineales y se desarrollarán los códigos de programación
con la herramienta de cómputo Octave 3.2.4. Inicialmente, se describirá el
fundamento matemático y la metodología de cada proceso; luego se realizará un
análisis comparativo de las diferentes técnicas con sus ventajas y limitaciones; y
finalmente se llegará a una serie de conclusiones y sugerencias con el propósito
de dar pautas a los ingenieros para seleccionar e implementar correctamente un
método numérico y así resolver un sistema de ecuaciones lineales.
5
2. OBJETIVOS
2.1 OBJETIVO GENERAL
Aplicar de forma asertiva las diferentes estrategias de solución de sistemas de
ecuaciones lineales, vistas en la asignatura procesos numéricos; de tal manera
que el ingeniero u otra persona de interés pueda obtener un resultado con la
calidad esperada de forma eficiente.
2.2 OBJETIVOS ESPECÍFICOS
Comprender el fundamento matemático y la metodología de los métodos
directos e iterativos de solución de sistemas de ecuaciones lineales e
identificar la estructura de los algoritmos en el lenguaje de Octave 3.2.4.
Programar en el lenguaje de Octave los códigos de programación de cada
una de las técnicas de solución de sistemas de ecuaciones lineales,
utilizando el esquema de funciones, de tal forma que se minimice el tiempo
de cómputo, las posiciones de memoria y la propagación de error.
Identificar la importancia de los métodos numéricos en la formulación y
evaluación de modelos matemáticos que involucren sistemas de
ecuaciones lineales.
Reconocer las ventajas y limitaciones de cada estrategia de solución con el
propósito de generar pautas y sugerencias para la correcta selección y
utilización de los mismos.
6
3. MARCO TEÓRICO
A continuación se presenta la fundamentación teórica de los métodos de solución
numérica de sistemas de ecuaciones lineales.
3.1 SISTEMAS DE ECUACIONES LINEALES
Un sistema de ecuaciones lineales es un conjunto de ecuaciones que deben
resolverse simultáneamente. Se asume que los elementos que componen el
sistema están definidos en los números reales y que siempre hay la misma
cantidad de ecuaciones que de incógnitas.
Ilustración 1. Sistema de ecuaciones lineales
Todo sistema de ecuaciones se puede representar en forma matricial dada por la
igualdad 𝐴𝑛𝑥𝑛𝑥 = 𝑏, donde 𝐴 es la matriz cuadrada de coeficientes, 𝑥 es el vector
de incógnitas y 𝑏 es el vector de términos independientes.
Ilustración 2. Forma matricial de un sistema de ecuaciones
El objetivo es encontrar la solución única del sistema, si existe; la cual es un
conjunto de valores para las incógnitas que satisfacen todas las ecuaciones.
7
3.2 MÉTODOS DIRECTOS DE SOLUCIÓN
A continuación se describirá la metodología de las técnicas de eliminación
gaussiana simple, eliminación gaussiana con pivoteo parcial y factorización LU de
matrices. Éstas técnicas se caracterizan por tener un número finito de operaciones
y de pasos a seguir para hallar la solución.
El fundamento matemático de la eliminación gaussiana simple y con pivoteo
parcial es el mismo y consiste en transformar el sistema de ecuaciones dado en
un sistema equivalente1 más simple de resolver, aplicando operaciones
elementales fila2. En ambos procesos la solución sería exacta si no fuese por los
errores de redondeo. (ZABALA, 2011)
3.2.1 Eliminación gaussiana simple Esta estrategia de solución consta de dos
procesos: la eliminación y el despeje. El primer paso consiste en transformar la
matriz aumentada3 (𝐴|𝑏) a una matriz triangular superior4 por medio de la
aplicación de operaciones fila; de esta manera se obtiene que el sistema [𝐴𝑥 =
𝑏] ≡ [𝑈𝑥 = 𝐵]. El segundo paso consiste en realizar una sustitución regresiva para
encontrar los valores de las incógnitas.
3.2.1.1 Metodología
Paso 1. Construir la matriz aumentada del sistema de ecuaciones lineales
Ilustración 3. Matriz aumentada
1 dos sistemas de ecuaciones son equivalentes si tienen exactamente la misma solución 2 Intercambiar filas, sumar a una fila un múltiplo de otra y multiplicar una fila por un escalar no nulo. 3 es la matriz obtenida al agregar el vector 𝑏 a la matriz 𝐴 en la posición columna n+1 4 es una matriz donde los elementos situados por debajo de la diagonal principal son ceros.
8
Paso 2. Aplicar a la matriz aumentada operaciones fila, para transformar en ceros
los elementos debajo de 𝑎11.
Ilustración 4. Paso 2. Operaciones fila. Eliminación gaussiana simple
Paso 3. Aplicar a la nueva matriz ampliada operaciones fila, para convertir en
ceros los elementos debajo de 𝑎22.
Ilustración 5.Paso 3. Operaciones fila. Eliminación gaussiana simple
Paso 𝒏 − 𝟏. Aplicar operaciones fila hasta conseguir que los elementos debajo de
la diagonal principal sean ceros.
Ilustración 6. Matriz triangular superior.
Finalmente se realiza la sustitución regresiva del sistema 𝑈𝑥 = 𝐵 para encontrar
los valores del vector 𝑥 de las incógnitas.
9
3.2.1.2 Código de la eliminación gaussiana simple
El siguiente código sólo incluye el proceso de eliminación.
function [ ret ] = elimgauss ()
%ELIMINACION GAUSSIANA SIMPLE
format long
A=matriz();
b=vectorb();
n=size(A);
mataum=[A b]
for i=1:n-1
for f=i+1:n
multiplicador=-mataum(f,i)/mataum(i,i)
for j=1:n+1
mataum(f,j)=mataum(f,j)+multiplicador*mataum(i,j);
end
end
mataum
end
endfunction
(Ver Anexos A y B)
3.2.2 Eliminación gaussiana con pivoteo parcial La metodología de este proceso
es similar a la de eliminación gaussiana simple; la diferencia radica en el pivote5,
es decir, en el denominador de la fracción que se forma en cada etapa del proceso
de eliminación. La técnica consiste en realizar intercambio de filas en cada paso,
si es necesario, para seleccionar dentro de los candidatos a pivote (los de la
columna), aquel cuyo valor absoluto sea el más grande.
La aplicación de esta técnica de pivoteo permite que la propagación de errores
disminuya al máximo, dado que los elementos de la matriz aumentada cambiarán
el mínimo de unidades posibles (Clase magistral).
5 Elemento de la diagonal por el cuál voy a dividir los elementos que se encuentran debajo de éste.
10
3.2.2.1 Metodología
Paso 1. Luego de construir la matriz aumentada del sistema de ecuaciones
lineales se selecciona el pivote.
6
Ilustración 7. Selección del pivote. EG con pivoteo parcial
Paso 2. Intercambiar las filas necesarias, en este caso 1 y 3 , para que el pivote se
encuentre en la posición deseada. Recordar que el vector 𝑏 también cambia.
Ilustración 8. Intercambio de filas. EG con pivoteo parcial
Paso 3. Aplicar la metodología de la eliminación gaussiana simple, y en cada
etapa de la eliminación aplicar la estrategia de pivoteo parcial.
3.2.2.2 Código de la eliminación gaussiana con pivoteo parcial
El siguiente código sólo incluye el proceso de eliminación.
6 En este caso se supuso que el valor de |𝑎31| es superior al de todos los elementos de la columna 1.
11
function [ ret ] = pivparcial ()
% ELIMINACIÓN GAUSSIANA CON PIVOTEO PARCIAL.
A=matriz();
b=vectorb();
n=size(b);
mataum=[A b]
for i=1:n-1
mayorpiv=abs(mataum(i,i));
filamayor=i;
for f=i+1:n
if abs(mataum(f,i))>mayorpiv
mayorpiv=abs(mataum(f,i));
filamayor=f;
end
end
mayorpiv
if filamayor~=i
temporal=mataum(filamayor,:);
mataum(filamayor,:)=mataum(i,:);
mataum(i,:)=temporal;
end
mataum
for f=i+1:n
multiplicador=-mataum(f,i)/mataum(i,i)
for j=1:n+1
mataum(f,j)=mataum(f,j)+multiplicador*mataum(i,j);
end
end
mataum
end
endfunction
(Ver Anexos A y B)
12
3.3.3 Factorización LU de matrices El fundamento matemático de esta estrategia
se basa en la propiedad que tiene toda matriz 𝐴 cuadrada de ser factorizada como
la multiplicación de dos matrices triangulares, una superior y otra inferior. De esta
manera 𝑠𝑖 𝐴𝑥 = 𝑏 𝑦 𝐴 = 𝐿𝑈 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑳𝑪 = 𝒃, 𝒅𝒐𝒏𝒅𝒆 𝑼𝒙 = 𝑪.
Ilustración 9. Factorización LU de una matriz cuadrada A
Luego de factorizar la matriz 𝐴 se debe seguir el siguiente procedimiento para
resolver el sistema:
Aplicar sustitución progresiva al sistema de ecuaciones lineales 𝐿𝐶 = 𝑏 para
encontrar los valores del vector 𝐶.
Aplicar sustitución regresiva al sistema de ecuaciones lineales 𝑈𝑥 = 𝐶 para
encontrar finalmente los valores del vector 𝑥 de incógnitas del sistema
inicial.
3.3.3.1 Métodos de factorización LU. A continuación se presentan tres métodos
para encontrar los valores 𝑙𝑖𝑗 𝑦 𝑢𝑖𝑗 de las matrices triangulares, de tal forma que el
producto de estas dos sea igual a la matriz 𝐴. La diferencia entre estos métodos
radica en los valores de partida de las diagonales principales de las matrices L y
U.
Método de Doolittle 𝑙𝑖𝑖 = 1
Método de Crout 𝑢𝑖𝑖 = 1
Método de Cholesky 𝑙𝑖𝑖 = 𝑢𝑖𝑖
Tabla 1. Métodos de factorización LU
A continuación se presentan los códigos de estos métodos (Ver Anexo A).
13
3.3.3.2 Código del método Doolittle
function [ ret ] = doolittle ()
% FACTORIZACIÓN LU DE DOOLITTLE
format long
A=matriz()
n=size(A);
L=eye(n);
for j=1:n-1
for i=j+1:n
mult=A(i,j)/A(j,j);
L(i,j)=mult;
for k=j:n
A(i,k)=A(i,k)-mult*A(j,k);
end
end
end
L
U=A
Endfunction
3.3.3.3 Código del método de Crout
function [ ret ] = crout ()
% FACTORIZACIÓN LU DE CROUT
format long
A=matriz()
n=size(A);
L=eye(n);
for j=1:n-1
for i=j+1:n
mult=A(i,j)/A(j,j);
L(i,j)=mult;
for k=j:n
A(i,k)=A(i,k)-mult*A(j,k);
end
end
end
U=A;
d=diag(diag(U));
L=L*d
U=d^-1*U
endfunction
14
3.3.3.4 Código del método de Cholesky
function [ ret ] = cholesky ()
% FACTORIZACIÓN LU CHOLESKY
format long
A=matriz()
n=size(A);
L=eye(n);
for j=1:n-1
for i=j+1:n
mult=A(i,j)/A(j,j);
L(i,j)=mult;
for k=j:n
A(i,k)=A(i,k)-mult*A(j,k);
end
end
end
U=A;
d=diag(diag(U));
L=L*d.^(1/2)
U=d.^(1/2)*d^-1*U
endfunction
3.3 MÉTODOS ITERATIVOS
A continuación se describirá la metodología de los métodos de Jacobi, Gauss
Seidel y un caso que intenta mejorar la probabilidad de convergencia de éste
último conocido por SOR. Éstas técnicas se caracterizan por generar una sucesión
de vectores que se espera converjan a la solución del sistema.
El fundamento numérico de estas estrategias de solución es el método de punto
fijo; donde a partir de un vector inicial cualquiera �̅�(0) se genera una aproximación
�̅�(1), y así sucesivamente, de la forma �̅�(𝒏) = 𝑻 �̅�(𝒏−𝟏) + 𝑪; donde 𝑇 es la matriz de
transición y 𝐶 es un vector constante. La diferencia entre métodos iterativos radica
en la forma de calcular 𝑇 𝑦 𝐶; sin embargo para ello, todos los métodos utilizan la
15
descomposición en bloques de la matriz 𝐴, de la forma 𝐴 = 𝐷7 − 𝐿8 − 𝑈9(toda
matriz A puede ser expresada como la suma de tres matrices)10
Ilustración 10. Descomposición D-L-U de una matriz A
3.3.1 Criterios de parada y medición del error. El proceso iterativo puede parar por
el cumplimiento de al menos uno de los siguientes criterios:
[𝑛𝑚𝑎𝑥]: 𝑁ú𝑚𝑒𝑟𝑜 𝑑𝑒 𝑖𝑡𝑒𝑟𝑎𝑐𝑖𝑜𝑛𝑒𝑠 𝑚á𝑥𝑖𝑚𝑎𝑠
𝐶𝑟𝑖𝑡𝑒𝑟𝑖𝑜 𝑑𝑒𝑙𝑡𝑎 [𝛿]: ‖𝑥𝑛 − 𝑥𝑛−1‖ ≤ 𝛿
𝐶𝑟𝑖𝑡𝑒𝑟𝑖𝑜 𝑡𝑜𝑙𝑒𝑟𝑎𝑛𝑐𝑖𝑎 [𝑡𝑜𝑙]: ‖𝑥𝑛 − 𝑥𝑛−1‖ ≤ 𝑡𝑜𝑙
El error del proceso iterativo se determina con la siguiente expresión:
𝑒𝑟𝑟𝑜𝑟 = ‖𝑥𝑛̅̅ ̅ − 𝑥𝑛−1̅̅ ̅̅ ̅̅ ‖
3.3.2 Método de Jacobi.
𝑇 = 𝐷−1(𝐿 + 𝑈)
𝐶 = 𝐷−1𝑏
𝑑𝑜𝑛𝑑𝑒 𝑏 𝑒𝑠 𝑒𝑙 𝑣𝑒𝑐𝑡𝑜𝑟 𝑑𝑒 𝑡é𝑟𝑚𝑖𝑛𝑜𝑠 𝑖𝑛𝑑𝑒𝑝𝑒𝑛𝑑𝑖𝑒𝑛𝑡𝑒𝑠 𝑑𝑒𝑙 𝑠𝑖𝑠𝑡𝑒𝑚𝑎 𝑑𝑒 𝑒𝑐𝑢𝑎𝑐𝑖𝑜𝑛𝑒𝑠 𝑙𝑖𝑛𝑒𝑎𝑙𝑒𝑠.
7 Matriz que contiene los elementos de la diagonal principal de A. 8 Matriz que contiene los inversos aditivos de los elementos que están debajo de la diagonal principal de A. 9 Matriz que contiene los inversos aditivos de los elementos que están encima de la diagonal principal de A. 10 No tiene nada que ver con factorización LU de matrices.
16
Código de Jacobi en Octave
function [ ret ] = jacobi (vectorini,nmax,delta,tolerancia)
format long
A=matriz();
b=vectorb();
[D,L,U]=partirmatriz();
T=D^-1*(L+U);
C=D^-1*b;
i=0;
m=delta+1;
error=tolerancia+1;
while i<nmax & m>delta & error>tolerancia
i=i+1
X=T*vectorini+C
m=norm(A*X-b)
error=norm(X-vectorini)
vectorini=X;
endwhile
endfunction
(Ver Anexos A,B y C)
3.3.3 Método de Gauss Seidel. Este método es un caso especial de S.O.R cuando
el grado de relajación 𝑤 es igual a 1.
𝑇 = (𝐷 − 𝐿)−1 𝑈
𝐶 = (𝐷 − 𝐿)−1 𝑏
3.3.4 Método de S.O.R Por sus siglas en inglés: Successive Over Relaxation
𝑇 = (𝐷 − 𝑤𝐿)−1 ((1 − 𝑤)𝐷 + 𝑤𝑢)
𝐶 = 𝑤(𝐷 − 𝑤𝐿)−1 𝑏
𝑑𝑜𝑛𝑑𝑒 𝑤 𝑒𝑠 𝑒𝑙 𝑔𝑟𝑎𝑑𝑜 𝑑𝑒 𝑟𝑒𝑙𝑎𝑗𝑎𝑐𝑖ó𝑛 (𝑐𝑜𝑛𝑡𝑟𝑎𝑐𝑐𝑖ó𝑛 𝑜 𝑒𝑠𝑡𝑖𝑟𝑎𝑚𝑖𝑒𝑛𝑡𝑜); 0 < 𝑤 < 2
17
Código de S.O.R y Gauss Seidel en Octave
function [ ret ] = sor (vectorini,nmax,delta,tolerancia,w)
format long
A=matriz();
b=vectorb();
[D,L,U]=partirmatriz();
T=(D-w*L)^-1*((1-w)*D+w*U);
C=(w*(D-w*L)^-1)*b;
%Para el programa de Gauss Seidel, el w=1.
i=0;
m=delta+1;
error=tolerancia+1;
while i<nmax & m>delta & error>tolerancia
i=i+1
X=T*vectorini+C
m=norm(A*X-b)
error=norm(X-vectorini)
vectorini=X;
endwhile
endfunction
(Ver Anexos A,B y C)
3.4 INTERPOLACIÓN POLINOMIAL
En la práctica es muy frecuente que los ingenieros obtengan por muestro o
experimentación una serie de datos {(𝑥𝑖, 𝑦𝑖), 𝑖 = 0,1,2, … , 𝑛}, sin embargo, al
querer estimar valores intermedios11entre los datos obtenidos, no se cuenta con
una expresión analítica 𝑓(𝑥) que le permita realizar dicha proyección.12
11 El punto arbitrario x que se quiere evaluar se encuentra dentro de los límites de los puntos de medición. 12 En ocasiones es conocida, pero se desea cambiar por una función más sencilla de calcular.
18
La interpolación polinomial consiste en determinar un polinomio único 𝑃(𝑥) de n-
ésimo grado que pase por los 𝑛 + 1 puntos medidos. A este polinomio se le
conoce como polinomio interpolante.
A pesar que solo existe uno y sólo un polinomio de n-ésimo grado que se ajusta a
n+1 puntos, existe una gran variedad de formas matemáticas en las cuales puede
expresarse este polinomio (CHAPRA Steven, 2007). A continuación se describirá
solo una de ellas: la forma de Newton
3.4.1 Interpolación polinomial de Newton en diferencias divididas El polinomio
interpolante de Newton está dado por la siguiente expresión (CHAPRA Steven,
2007):
𝑃𝑛(𝑥) = 𝑏0 + 𝑏1(𝑥 − 𝑥0) + 𝑏2(𝑥 − 𝑥0)(𝑥 − 𝑥1) + ⋯ + 𝑏𝑛(𝑥 − 𝑥0)(𝑥 − 𝑥1) … (𝑥 − 𝑥𝑛−1)
𝑏0 = 𝑓(𝑥0); 𝑏1 = 𝑓[𝑥1, 𝑥0]; 𝑏1 = 𝑓[𝑥2, 𝑥1, 𝑥0] ; … ; 𝑏𝑛 = 𝑓[𝑥𝑛, 𝑥𝑛−1, … , 𝑥0]
𝑑𝑜𝑛𝑑𝑒 𝑏𝑖 , 𝑖 = 0,1,2, … , 𝑛 se conocen como las 𝑑𝑖𝑓𝑒𝑟𝑒𝑛𝑐𝑖𝑎𝑠 𝑑𝑖𝑣𝑖𝑑𝑖𝑑𝑎𝑠 𝑓𝑖𝑛𝑖𝑡𝑎𝑠.
Ilustración 11. Polinomio interpolante de Newton
¿Qué es una diferencia dividida finita? R// Es una pendiente
1𝑟𝑎 DDF 𝑓(𝑥𝑖 , 𝑥𝑗) =
𝑓(𝑥𝑖) − 𝑓(𝑥𝑗)
𝑥𝑖 − 𝑥𝑗
2𝑟𝑎 DDF 𝑓(𝑥𝑖, 𝑥𝑗 , 𝑥𝑘) =
𝑓[𝑥𝑖 , 𝑥𝑗] − 𝑓[𝑥𝑗,𝑥𝑘]
𝑥𝑖 − 𝑥𝑘
La n-ésima DDF 𝑓(𝑥𝑛, 𝑥𝑛−1, … , 𝑥1, 𝑥0) =
𝑓[𝑥𝑛, 𝑥𝑛−1, … 𝑥1] − 𝑓[𝑥𝑛−1,𝑥𝑛−2, … , 𝑥0]
𝑥𝑛 − 𝑥0
Tabla 2. Diferencias divididas finitas.
19
A continuación se presenta la representación gráfica de la naturaleza de las DDF
13
Ilustración 12. Representación gráfica de la naturaleza recursiva de las diferencias divididas finitas.
Código de diferencias divididas finitas en Octave
A continuación se presenta el código en Octave para determinar los valores de las
DDF del polinomio interpolante de Newton.
function [ ret ] = difdivididas ()
A=puntos();
n=size(A);
for i=1:n-1
for j=i+1:n
A(j,i+2)=(A(j,i+1)-A(j-1,i+1))/(A(j,1)-A(j-i,1));
end
end
A
Endfunction
(Ver anexo D)
13 (CHAPRA Steven, 2007)
20
4. CUADRO COMPARATIVO
Método Ventajas Limitaciones
Eliminación Gaussiana
Simple
-Se puede estimar el número de
operaciones y por lo tanto el
tiempo estimado de cómputo.
-Presenta errores por
propagación o redondeo
- La matriz A no puede tener
un elemento cero o muy
cercano a éste en la diagonal
principal.
-El método es muy lento para
sistemas muy grades.
Eliminación Gaussiana
con pivoteo parcial
-Reducción del efecto del error de
redondeo
-La cantidad de operaciones
no se alteran, pero incrementa
el tiempo de cómputo dado
que se realizan comparaciones
e intercambios.
Factorización LU de
matrices
-Si el vector 𝑏 varía y la matriz 𝐴
permanece igual, no es necesario
volver a factorizar la matriz, es
decir, no se tiene que empezar
desde cero como en eliminación
gaussiana simple o con pivoteo
parcial.
-Existen infinitos métodos de
Factorización LU.
-Se puede estimar el número de
operaciones y por lo tanto el
tiempo estimado de cómputo.
-No todos los métodos de
factorización arrojan una
solución.
Jacobi -No importa el tamaño del sistema -No siempre el método
converge, por lo tanto es
necesario verificar su
convergencia.
-No se puede determinar la
rapidez de convergencia sin
determinar el radio espectral y
realizar una comparación.
SOR -No es un método único, el usuario
puede jugar con el valor de w.
-No importa el tamaño del sistema
Gauss Seidel No importa el tamaño del sistema
Tabla 3. Cuadro comparativo
21
5. CONCLUSIONES
Se comprendió que los métodos de solución propuestos por el análisis
numérico facilitan el trabajo al ingeniero, dado que en ocasiones para él
resolver problemas en su campo, se debe enfrentar a sistemas de
ecuaciones lineales de gran magnitud; y por lo anterior requiere tanto de
una herramienta de cómputo que garantice la eficiencia y la calidad de la
solución, como también de la selección de un método numérico adecuado
para ahorrar tiempo, posiciones de memoria y reducir la propagación de
error.
Se comprendió el fundamento, la metodología y la estructura de
programación en Octave con el esquema de funciones de los diferentes
métodos directos e iterativos de solución y por lo tanto, se está en
capacidad de resolver cualquier sistema de ecuaciones lineales sin importar
su complejidad.
Se identificaron ventajas y limitaciones de cada una de las estrategias de
solución de sistemas de ecuaciones lineales y en base a ello se llegó a las
siguientes recomendaciones:
Si el usuario desea resolver un sistema de ecuaciones lineales de
gran magnitud es recomendable utilizar un método iterativo para
reducir el tiempo de cómputo.
Al implementar un método iterativo es indispensable que el usuario
establezca correctamente el grado de calidad de los resultados
deseados.
El usuario debe tener presente que la rapidez de convergencia de un
método iterativo depende exclusivamente de la matriz de transición T
y por lo tanto no importa el vector inicial que seleccione.
22
Antes de seleccionar un método iterativo es prudente verificar su
convergencia.
Si el usuario elige un método directo de solución que involucre
eliminación es recomendable que evalúe el costo-beneficio que trae
la técnica de pivoteo, es decir, tiempo de cómputo vs reducción de
error.
Si la persona de interés desea resolver varios sistemas de
ecuaciones que tengan la misma matriz 𝐴 de coeficientes, es
recomendable utilizar el método de solución con factorización LU,
dado que al independizar el tratamiento del vector 𝑏 de la matriz 𝐴, la
factorización no varía y por lo tanto para dar solución al sistema se
debe sólo realizar una regresión progresiva y una regresiva.
A modo de recomendación adicional, es importante que el usuario
determine si la matriz 𝐴 está bien o mal condicionada, porque de lo
contrario no se puede concluir sobre la calidad de los resultados al
existir una incertidumbre acerca de la sensibilidad de la matriz a
pequeños cambios inevitables, como por ejemplo redondeos para el
almacenamiento del número en el sistema de cómputo.
6. ANEXOS
A continuación se presentan los códigos complementarios.
ANEXO A. Este código almacena la matriz cuadrada A.
function [ y ] = matriz ()
%y=[12 -3 5; 5 -13 6; -8 -1 17];
y=[3 -2 4;0.5 0 -1;-1 0.1 -1];
endfunction
23
ANEXO B. Este código almacena el vector de términos independientes 𝑏.
function [ y ] = vectorb ()
%y=[-3;8;0];
y=[71;-3.8;2.5];
endfunction
ANEXO C. Este código parte la matriz A en tres bloques D-L-U
function [ D,L,U ] = partirmatriz ()
A= matriz();
[m,n]=size(A);
for i=1:n
D(i,i)=A(i,i);
endfor
for j=1:n-1
for i=j+1:n
L(i,j)=-A(i,j);
endfor
endfor
L(n,n)=0;
for i=1:n-1
for j=i+1:n
U(i,j)=-A(i,j);
endfor
endfor
U(n,n)=0;
Endfunction
ANEXO D. Este código almacena n+1 puntos
function [ y ] = puntos ()
y=[3 2;-1 5;2 -2;4 -3;-2 3];
endfunction
24
7. BIBLIOGRAFÍA
CHAPRA Steven, CANALE Raymond P. 2007. Capítulo 18. Interpolación.
Métodos numéricos para ingenieros. 5ta Edición. s.l. : Mc Graw Hill, 2007, págs.
503-536.
KOLMAN Bernard, HILL David R. 2006. Matrices y sistemas lineales. Álgebra
Lineal. Octava edición. s.l. : Pearson Education, 2006, págs. 10-28.
MORA, Walter. 2011. Interpolación polinomial. [En línea] 16 de Agosto de 2011.
[Citado el: 28 de Octubre de 2014.] http://www.tec-
digital.itcr.ac.cr/revistamatematica/Libros/WMora_MetodosNumericos/WMora_INT
ERPOLACION.pdf.
PRIETO, Germán A. Capítulo 4. Interpolación. [En línea] [Citado el: 28 de Octubre
de 2014.]
http://wwwprof.uniandes.edu.co/~gprieto/classes/compufis/interpolacion.pdf.
VII ENCUENTRO MULTIDISCIPLINARIO DE INVESTIGACIÓN 2010. García,
Luis Lorenzo Jiménez. 2010. Solución numérica de sistemas de ecuaciones
lineales mediante MATLAB y su aplicación en Ingeniería. [En línea] 2010. [Citado
el: 26 de Octubre de 2014.]
http://www.aragon.unam.mx/investigacion/CIMA/Eventos/Memoria7/Ponencia%20
Luis%20Lorenzo.pdf.
ZABALA, Francisco José Correa. 2011. Solución numérica de ecuaciones de
una variable. Métodos Numéricos. 1 ed. Medellín : Fondo editorial Universidad
EAFIT, 2011, págs. 91-140.
ZABALA, Francisco José Correa. 2011. Solución numérica de sistemas de
ecuaciones lineales. Métodos Numéricos. 1 ed. Medellín : Fondo editorial
Universidad EAFIT, 2011, págs. 141-222.
CLASE MAGISTRAL PROCESOS NUMÉRICOS. (29 Septiembre; 1, 6, 8, 15,
22,27 Octubre, 2014: Medellín, Colombia). Notas de clase. Universidad EAFIT.