Logo Studenta

Una-introduccion-al-analisis-numerico-hans-muller

¡Este material tiene más páginas!

Vista previa del material en texto

Hans C� M�uller S�C�
Una Introducci�on
al
An�alisis Num�erico
i
Hans C� M�uller S�C�
Una Introducci�on
al
An�alisis Num�erico
Con �� �guras
ii
Hans C� M�uller Santa Cruz
Departamento de Matem�aticas
Facultad de Ciencias y Tecnolog��a
Universidad Mayor de San Sim�on
Casilla ���� Cochabamba� Bolivia
e�mail hans	mat�umss�bo
Pr�ologo
La Facultad de Ciencias y Tecnolog��a tiene 
� a�nos de vida� per��odo que
ha sido fruct��fero en el �ambito universitario� porque se han creado carreras
tecnol�ogicas� como cient��
cas� haciendo �enfasis a una investigaci�on cient��
ca
seria como un mecanismo de garantizar una excelencia acad�emica� La
Carrera de Matem�aticas� una de nuestras Carreras de reciente creaci�on� est�a
inscrita dentro este marco�
Ahora bien� la Universidad Mayor de San Sim�on consciente de esta
situaci�on� ha conseguido convenios de cooperaci�on internacional� como es
el caso del Programa MEMI� Programa de Mejoramiento de la Ense�nanza
de la Matem�atica y la Inform�atica� De los objetivos principales de este
programa es fortalecer el �area de las matem�aticas� incentivar la difusi�on de
las diferentes ramas de las matem�aticas en el medio universitario y fuera de
�este� La Universidad y sus autoridades� dentro de sus pol��ticas acad�emicas y
de investigaci�on� han tenido la visi�on de conseguir los servicios de los mejores
profesionales en esta disciplina y Hans M�uller es uno de ellos�
El autor del libro� Hans M�uller Santa Cruz� es un joven matem�atico bo�
liviano que ha regresado a su pa��s para compartir los conocimientos adquiri�
dos en en la Universidad de Ginebra� Suiza� Actualmente es el Coordinador
del Programa Magister en Matem�aticas� programa implementado de manera
conjunta entre la Universidad Mayor de San Sim�on y la Universidad Cat�olica
del Norte� Chile� Ha dictado un curso de Elementos Finitos� destinado a los
docentes en nuestra superior Casa de Estudios� en La Paz� bajo invitaci�on ha
impartido cursos tutoriales en la Academia de Ciencias en temas relaciona�
dos a las matem�aticas aplicadas� El y otros profesionales de su ar�ea� est�an
transformando la manera de hacer matem�aticas en la Facultad de Ciencias
y Tecnolog��a�
Los t�opicos tratados en este libro est�an muy relacionados con los cam�
bios estructurales que ha ocasionado la introducci�on masiva de sistemas in�
form�aticos� En efecto� la utilizaci�on m�asiva del computador ha permitido al
Hombre efectuar c�alculos que en otra �epoca hubiese sido impensable realizar�
los� En la actualidad es muy corriente simular num�ericamente experiencias�
que en laboratorio son muy complicadas� costosas o peligrosas� o simplemente
imposible de experimentarlas� Los problemas de optimizaci�on son abordables
gracias a la utilizaci�on del ordenador y no faltan situaciones en las cuales
el uso de estos dispositivos de c�alculo� no solamente son de gran ayuda�
sino indispensables� El An�alisis Num�erico es la rama de las Matem�aticas�
cuyo campo de acci�on es el estudio y an�alisis de los diferentes algoritmos
iv Pr�ologo
y m�etodos num�ericos que se utilizan para resolver los problemas mediante
computadoras� El libro �Una Intruducci�on al An�alisis Num�erico� presenta
los temas b�asicos del An�alisis Num�erico de una manera rigurosa� permitiendo
que el lector pueda adquirir los conocimientos matem�aticos necesarios para
profundizar en t�opicos m�as especializados o simplemente pueda concebir e
implementar m�etodos num�ericos de una manera correcta y �optima�
Finalmente� mi esperanza es que este libro sea el inicio de una larga
serie de otras publicaciones de alto nivel que ofrezca el autor y su unidad
acad�emica�
Cochabamba� septiembre de 
���
Ing� Alberto Rodr��guez M�endez
Rector de la Universidad Mayor de San Sim�on
Prefacio
Este libro nace ante el vacio existente de una bibliograf��a en espa�nol que
trate los temas capitales del An�alisis Num�erico� El nombre que lleva� �Una
Introducci�on al An�alisis Num�erico�� se debe esencialmente al car�acter que
deseo que tenga este libro�
El An�alisis Num�erico es una disciplina de las Matem�aticas en gran
crecimiento gracias a la utilizaci�on masiva de medios inform�aticos� D��a que
pasa es m�as corriente el tratamiento num�erico en las Ciencias� como en
la Tecnolog��a� el modelaje� la simulaci�on num�erica son moneda corriente�
Ahora bien� toda persona que pretenda tener como herramienta de tra�
bajo� los m�etodos num�ericos� debe conocer los t�opicos introductorios del
An�alisis Num�erico que son� Sistemas Lineales� Interpolaci�on� Resoluci�on de
Ecuaciones no Lineales� C�alculo de Valores Propios y Soluci�on Num�erica de
Ecuaciones Diferenciales� porque tarde o temprano se topar�a con alguno de
estos temas�
Siguiendo la l��nea trazada por este libro� �este contiene siete cap��tulos� el
primero de car�acter introductorio� donde se da los conceptos b�asicos de error
y estabilidad� seguido de un ejemplo mostrando que la aritm�etica del punto
�otante no es un impedimento para efectuar c�alculos de precisi�on arbitraria�
el segundo cap��tulo trata sobre los problemas lineales mas comunes y
los m�etodos de soluci�on de estos� el tercer cap��tulo aborda el tema de
interpolaci�on num�erica y extrapolaci�on� introduciendo el estudio de los
splines c�ubicos� el cap��tulo IV analiza los problemas no lineales y los m�etodos
mas e
cientes de resoluci�on de estos� en el cap��tulo V se estudia el problema
de valores propios y la implementaci�on de m�etodos num�ericos para el c�alculo
de valores propios� el cap��tulo sexto trata de la integraci�on num�erica y la
transformada r�apida de Fourier y 
nalmente el cap��tulo VII estudia los
problemas diferenciales y los m�etodos num�ericos de resoluci�on mas usuales
de estos problemas�
Pr�acticamente el contenido de este libro ven los estudiantes de segundo
a�no de las Carreras de M�atematicas e Inform�atica de la Universidad de
Ginebra� Suiza� Universidad en la cual he sido formado� El pre�requisito
para un buen aprovechamiento de este libro es conocer bien los principios
b�asicos del An�alisis Real y Complejo� como tambi�en tener una buena base
de Algebra Lineal� Por consiguiente� este libro est�a destinado a estudiantes
universitarios que siguen la asignatura de An�alisis Num�erico� como as�� mismo
toda persona interesada en An�alisis Num�erico que tenga los pre�requisitos
y que desea cimentar sus conocimientos en esta disciplina� Este libro puede
vi Prefacio
ser utilizado como texto base o bien como complemento bibliogr�a
co�
Debo agredecer a mis profesores de la Universidad de Ginebra� E� Hairer
y G� Wanner cuyos cursos han servido de base para la elaboraci�on de este
libro� Por otro lado� sin el apoyo en material de trabajo del Programa
MEMI� Programa de Mejoramiento de la Ense�nanza de las Matem�aticas e
Inform�atica� de la Universidad Mayor de San Sim�on este libro no habr��a
existido� As�� mismo agradezco a mi familia� mis colegas y amigos que
seguieron con inter�s la elaboraci�on de este libro�
El libro ha sido transcrito en TEX y las gr�a
cas realidas en las sub�
rutinas gr�a
cas FORTRAN que G� Wanner me las cedi�o muy gentilmente� La
transcripci�on� como la ejecuci�on de los programas en sido realizados sobre
una WorkStation HP������
Posiblemente este libro contenga muchos errores� me gustar��a que los
hagan conocer� para que en una segunda edici�on estos sean corregidos�
Octubre� 
��� Hans C� M�uller S�C�
Contenido
I� Preliminares
I�� Algoritmos � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �
Ejercicios � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �
I�� Estabilidad � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �
Ejercicios � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
�
I�� Un ejemplo� C�alculo de PI � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
�
II� Sistemas Lineales
II�� Condici�ondel Problema Lineal � � � � � � � � � � � � � � � � � � � � � � � � � � ��
Normas de Vectores y Matrices � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
La Condici�on de una Matriz � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
Ejercicios � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
II�� M�etodos Directos � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
El Algoritmo de Gauss � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
El Algoritmo de Cholesky � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
Ejercicios � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
II�� M�etodos Iterativos � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
M�etodos de Jacobi y Gauss�Seidel � � � � � � � � � � � � � � � � � � � � � � � � � ��
El Teorema de Perron�Frobenius � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
M�etodo de Sobrerelajaci�on SOR � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
Estudio de un Problema Modelo � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
Ejercicios � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
II�	 M�etodos Minimizantes � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
M�etodo del Gradiente � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
M�etodo del Gradiente Conjugado � � � � � � � � � � � � � � � � � � � � � � � � � � ��
Polinomios de Chebichef � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
M�etodo del Gradiente Conjugado Precondicionado � � � � � � � � � ��
Resultados Num�ericos � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
Ejercicios � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �
II�� M�
nimos Cuadrados � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
La descomposici�on QR � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
La Pseudo�Inversa de una Matriz � � � � � � � � � � � � � � � � � � � � � � � � � � ��
Error del M�etodo de los M��nimos Cuadrados � � � � � � � � � � � � � � � ��
Ejercicios � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
�
viii Contenido
III� Interpolaci�on
III�� Interpolaci�on de Lagrange � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
��
Bases Te�oricas � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
��
Construcci�on del Polinomio de Interpolaci�on � � � � � � � � � � � � � � 
��
El Error de Interpolaci�on � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
Polinomios de Chebichef � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
�
Estudio de los Errores de Redondeo � � � � � � � � � � � � � � � � � � � � � � 
�
Convergencia de la Interpolaci�on � � � � � � � � � � � � � � � � � � � � � � � � � 
�
Ejercicios � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
��
III�� Splines C�ubicos � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
�
Construcci�on del Spline Interpolante � � � � � � � � � � � � � � � � � � � � � � 
��
El Error de la Aproximaci�on Spline � � � � � � � � � � � � � � � � � � � � � � � 
��
Aplicaci�on de Spline � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
��
Ejercicios � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
��
III�� Extrapolaci�on � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
��
Ejercicios � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
��
IV� Ecuaciones No Lineales
IV�� Ecuaciones Polinomiales � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
��
Ecuaciones Resolubles por Radicales � � � � � � � � � � � � � � � � � � � � � � 
��
Ecuaciones No Resolubles por Radicales � � � � � � � � � � � � � � � � � � 
��
Localizaci�on de Ceros � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
��
M�etodo de Newton � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
��
Sucesiones de Sturm � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
��
Ejercicios � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
�
IV�� M�etodos Iterativos � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
��
Posici�on del Problema � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
��
M�etodo de la Falsa Posici�on � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
��
Sistema de Ecuaciones � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
��
Un M�etodo Iterativo Simple � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
��
Ejercicios � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
��
IV�� M�etodo de Newton � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
��
El Teorema de Newton�Misovski � � � � � � � � � � � � � � � � � � � � � � � � � � 
��
M�etodo de Newton Simpli
cado � � � � � � � � � � � � � � � � � � � � � � � � � � 
��
M�etodo de Newton con Relajaci�on � � � � � � � � � � � � � � � � � � � � � � � � 
��
Aproximaci�on de Broyden � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
��
Ejercicios � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 
��
IV�	 M�etodo de Gauss Newton � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���
Convergencia del M�etodo de Gauss�Newton � � � � � � � � � � � � � � � ���
Modi
caciones del M�etodo de Gauss�Newton � � � � � � � � � � � � � ���
El M�etodo de Levenber�Marquandt � � � � � � � � � � � � � � � � � � � � � � � �
�
Ejercicios � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �
Contenido ix
V� C�alculo de Valores Propios
V�� Teor�
a Cl�asica y Condici�on del Problema � � � � � � � � � � �
�
La Condici�on del Problema a Valores Propios � � � � � � � � � � � � � �
�
Ejercicios � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
V�� Determinaci�on de Valores Propios � � � � � � � � � � � � � � � � � � � ���
El M�etodo de la Potencia � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���
Formas Tridiagonales y Formas de Hessenberg � � � � � � � � � � � � ���
Teorema de Sturm y el Algoritmo de la Bisecci�on � � � � � � � � � ���
Generalizaci�on del M�etodo de la Potencia � � � � � � � � � � � � � � � � � ���
El M�etodo QR � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���
Ejercicios � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
VI� Integraci�on Num�erica
VI�� Bases Te�oricas � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���
F�ormulas de Cuadratura � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���
El Orden de una F�ormula de Cuadratura � � � � � � � � � � � � � � � � � ���
Estimaci�on del Error � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���
Ejercicios � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���
VI�� Cuadraturas de Orden Elevado � � � � � � � � � � � � � � � � � � � � � � ���
Polinomios Ortogonales � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���
Los Polinomios de Legendre � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���
Las F�ormulas de Cuadratura de Gauss � � � � � � � � � � � � � � � � � � � ���
Ejercicios� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���
VI�� Implementaci�on Num�erica � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���
Tratamiento de Singularidades � � � � � � � � � � � � � � � � � � � � � � � � � � � ���
Ejercicios � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���
VI�	 Transformaci�on de Fourier � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���
Estudio del Error � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���
Interpolaci�on Trigonom�etrica � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���
Transformaci�on R�apida de Fourier FFT � � � � � � � � � � � � � � � � � � ���
Aplicaciones de FFT � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���
Ejercicios � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���
VII� Ecuaciones Diferenciales
VII�� Generalidades � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���
Teoremas de Existencia y Unicidad � � � � � � � � � � � � � � � � � � � � � � � ���
Problemas con Valores en la Frontera � � � � � � � � � � � � � � � � � � � � � ���
Diferenciabilidad respecto a los Valores Iniciales � � � � � � � � � � ���
Simple Shooting � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���
Shooting M�ultiple � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���
Ejercicios � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �
x Contenido
VII�� M�etodo de Euler � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �
�
Efectos de los Errores de Redondeo � � � � � � � � � � � � � � � � � � � � � � � �
�
Estabilidad del M�etodo de Euler � � � � � � � � � � � � � � � � � � � � � � � � � �
�
M�etodo de Euler Imp��cito � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
Ejercicios � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���
VII�� M�etodos de Runge�Kutta � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���
Construcci�on de un M�etodo de Orden � � � � � � � � � � � � � � � � � � � ���
M�etodos Encajonados � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���
Soluciones Continuas � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���
Convergencia de los M�etodos de Runge�Kutta � � � � � � � � � � � � ���
Experiencias Num�ericas � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���
Ejercicios � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���
VII�� M�etodos Multipasos � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
M�etodos de Adams Expl��citos � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
M�etodos de Adams Impl��citos � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���
M�etodos Predictor�Corrector � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���
M�etodos BDF � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���
Estudio del Error Local � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���
Estabilidad � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���
Convergencia de los M�etodos Multipaso � � � � � � � � � � � � � � � � � � ���
Ejercicios � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���
Bibliograf�
a � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���
Indice de S�
mbolos � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ���
Indice Alfab�etico � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � ��
Cap��tulo I
Preliminares
Con la utilizaci�on masiva de sistemas inform�aticos en la resoluci�on de
problemas a todo nivel� el An�alisis Num�erico ha tenido un gran desarrollo en
las �ultimas d�ecadas� como una rama integrante de las Matem�aticas� En este
primer cap��tulo se expondr�a las nociones de base que sustentan el An�alisis
Num�erico� para ser utilizadas en los cap��tulos posteriores�
La primera secci�on estar�a dedicada a estudiar los algoritmos como
una composici�on de operaciones elementales� partiendo de un dispositivo
ideal de c�alculo� Se analizar�a las nociones de e
ciencia y error de un
algoritmo�
En la segunda secci�on se analizar�a el problema algor��tmico a partir
de los dispositivos materiales con que se cuenta en la actualidad� es decir
ordenadores o computadoras� En esta secci�on se estudiar�a la representaci�on
en punto �otante de un n�umero real y su redondeo en la computadora� Se
introducir�a la noci�on de precisi�on de una computadora y la relaci�on de �esta
con el concepto de estabilidad� en sus diferentes versiones� de un algoritmo�
En la tercera y �ultima secci�on de este cap��tulo� se ver�a que las li�
mitaciones impuestas por la representaci�on en punto �otante� no es una res�
tricci�on para calcular con la precisi�on que se requiera� Prueba de esto� � ser�a
calculado� como un ejemplo ilustrativo� con 
���� decimales de precisi�on�
I�� Algoritmos
En esta secci�on se supondr�a que se cuenta con un dispositivo ideal de c�alculo�
es decir una computadora de precisi�on exacta� situaci�on que no sucede en la
realidad� El cuerpo de base ser�a R� a menos que se especi
que lo contrario�
Este dispositivo est�a provisto de ciertas operaciones cuya acci�on se efectua
en un tiempo 
nito� por ejemplo es capaz de realizar las � operaciones
aritm�eticas elementales� m�as algunas como la radicaci�on� la exponenciaci�on
y las otras funciones elementales que se estudian en un curso de C�alculo I�
Por consiguiente� se tiene la primera de
nici�on�
De�nici�on I������ Una operaci�on elemental es una operaci�on matem�atica
o funci�on cuya acci�on se la efectua en un tiempo 
nito y que adem�as el
dispositivo ideal la puede realizar�
Inicialmente se supondr�a que las cuatro operaciones aritm�eticas
como� la adici�on� la multiplicaci�on� la sustracci�on y la divisi�on son posibles
en este dispositivo de c�alculo� De esta manera es posible evaluar toda
funci�on polinomial� toda funci�on racional� en una cantidad 
nita de pasos o
composici�on de operaciones elementales�
De�nici�on I������ Un algoritmo es una sucesi�on 
nita de operaciones
elementales� Si se denota por fi una operaci�on elemental� un algoritmo es la
composici�on de n operaciones elementales� es decir
f � fn � fn�� � � � � � f� � f�� �I�
�
�
Por otro lado� el dispositivo de c�alculo con el que se cuenta tiene la

nalidad de evaluar la o las soluciones de un problema matem�atico� siempre
que sea posible hacerlo� Ahora bien� lo que cuenta en este estudio es el
resultado� de donde la�
De�nici�on I������ Un problema es darse un dato x � Rn y obtener un
resultado P�x� � R�
En consecuencia� son problemas todas las funciones cuyo dominio
es un espacio vectorial real de dimensi�on 
nita� cuya imagen est�a incluida
en la recta real� Una funci�on cuya imagen est�a incluida en un espacio de
dimensi�on m�as grande que 
� puede ser interpretada como un conjunto de
problemas� donde cada problema es la funci�on proyecci�on correspondiente�
Las ecuaciones pueden ser vistas como problemas� pero antes aclarando cual
de las soluciones se est�a tomando�
I�� Algoritmos �
Es necesario recalcar que problema y algoritmo son conceptos dife�
rentes� aunque de alguna manera ligados� Consid�erese el problema siguiente�
P�x� � anxn � an��xn�� � � � �� a�x� a�� �I�
���
P�x� puede ser obtenido de muchas maneras� en particular utilzando los �
siguientes algoritmos� El primero consiste en evaluar el polinomio �I�
��� tal
como est�a de
nido� con la convenci�on que�
x� � x�xn � x � xn��� para n � �� �I�
���
La segunda manera de evaluar el polinomio consiste en utilizar el algoritmo
de H�orner� el cual est�a dado por�
q��x� � an�
q��x� � q��x�x � an���
q��x� � q��x�x � an���
���
qn�x� � qn���x�x � a��
�I�
���
Como puede observarse ambos algoritmos eval�uan el polinomio P�x�� sin
embargo en el primero se requiere� 
 � � � � � n � 
 multiplicaciones para
evaluar las potencias� n multiplicaciones para evaluar los t�erminos de la
forma aix
i y 
nalmente n adiciones� lo cual hace un total de
n�n� ��
�
operaciones elementales� �I�
���
El algoritmo de H�orner requiere a cada paso de una multiplicaci�on y una
adici�on lo cual es igual a
�n operaciones elementales� �I�����
Por lo tanto� puede observarse claramente que el algoritmo de H�orner es
m�as e
ciente que el primero� pues la implementaci�on de �este efectua menos
operaciones elementales�
El concepto de e
ciencia de un algoritmo est�a ligado por consi�
guiente al costo en operaciones elementales que se requiere para ejecutar
un algoritmo� Ahora bien� en la realidad una computadora requiere menos
tiempo para evaluar una adici�on que para una multiplicaci�on� Cada ope�
raci�on elemental toma cierto tiempo en efectuarse� que en general depende
de la computadora y el lenguaje en el que est�a escrito el programa� Es
� I Preliminares
por eso� que es m�as conveniente medir la e
ciencia en t�erminos de tiempo
ejecutado� en lugar del n�umero de operaciones elementales ejecutadas� Con
lo argumentado se puede formular una primera de
nici�on de e
ciencia�
De�nici�on I���	�� El costo del algoritmo fn � � � � � fn� est�a dado por
C � m� �m� � � � ��mn� �I�
���
donde mi es el tiempo de ejecuci�on de fi� Si C� y C� son los costos en tiempo
de dos algoritmos que resuelven el mismo problema� se dir�a que el primer
algoritmo es m�as e
ciente que el segundo si C� � C��
Tal como se dijo al inicio de esta secci�on� el dispositivo ideal con
el que se cuenta� puede efectuar una cantidad 
nita de operaciones elemen�
tales� Suponiendo nuevamente� que solamente se cuenta con las cuatro ope�
raciones aritm�eticas� las �unicas funciones que pueden evaluarse utilizando
un algoritmo son las funciones polinomiales y racionales� Ahora bien� existe
una cantidad ilimitada de funciones y se puede mostrar que no existe ning�un
algoritmo que sea la composici�on de adiciones� multiplicaciones� sustrac�
ciones o divisiones� que permita calcular una raiz cuadrada� evaluar funciones
trigonom�etricas� exponenciales o logar��tmicas� Sin embargo� existen proce�
dimientos matem�aticos que permiten aproximar estas funciones de manera
arbitraria� Los m�as com�unmente utilizados� son las series de Taylor� las frac�
ciones continuas y algunos m�etodos iterativos� Todos estos m�etodos est�an
sustentados en las nociones de l��mite� de continuidad� derivabilidad dados
en los cursos de C�alculo y An�alisis�
A continuaci�on se ver�a un ejemplo ilustrativo� donde se introducir�a
la noci�on del error de truncaci�on� Consid�erese la funci�on exponencial� cuyo
desarrollo en serie de Taylor est�a dada por
ex �
�X
k��
xk
k�
� �I�
���
Es evidente que ex no puede evaluarse en un n�umero 
nito de pasos� para
un x dado� sin embargo en lugar de evaluar ex� uno se puede contentar
evaluando una cantidad 
nita de t�erminos de la serie de Taylor� es decir
p�x� �
nX
k��
xk
k�
� �I�
���
para un n 
jado de antemano� La diferencia entre ex y p�x� es el error
de truncaci�on de ex respecto a p�x�� Este error de truncaci�on es del orden
O�xn��� cuando x tiende a �� El nombre de truncaci�on proviene del hecho
que para evaluar ex se ha despreciado una parte de la serie� Por consiguiente�
el error de truncaci�on puede de
nirse como�
I�� Algoritmos �
De�nici�on I������ Sean P�x�� P ��x� dos problemas� El error de truncaci�on
de P�x�� respecto de P ��x� est�a dado por
P�x��P ��x�� �I�
�
��
El nombre que tiene este error� como se dijo m�as arriba� es debido
a que la la serie de Taylor es truncada a un n�umero 
nito de t�erminos�
No obstante� existe una gran diversidad de m�etodos que aproximan a la
soluci�on del problema utilizando otro tipo de argumentos� en este caso es
m�as conveniente utilizar el nombre de error de aproximaci�on o error del
m�etodo� de todas formas es cuesti�on de gusto�
El concepto de e
ciencia ha sido de
nido para aquellos problemas
donde se puede encontrar la soluci�on mediante un algoritmo� Para aquellos
problemas� donde no es posible encontrar un algoritmo que de la soluci�on y
suponiendo que es posible aproximar la soluci�on de manera arbitraria me�
diante un m�etodo algor��tmico� la e
ciencia est�a ligada al costo en opera�
ciones� como tambi�en al error del m�etodo� En esta situaci�on la e
ciencia es
un concepto m�as subjetivo que depende de alguna manera del usuario� pues
existen problemas donde el error de aproximaci�on debe ser lo m�as peque�no
posible� y otros problemas donde la exactitud no es un requisito primordial�
Ejemplos
�� Consid�erese el problema� determinar �� Utilizando la identidad
arctan 
 �
�
�
y que la serie de Taylor en el origen est�a dada por
arctanx �
�X
k��
��
�k
�k � 
x�k��� �I�
�
�
se puede obtener un m�etodo que aproxime �� pero el problema de este
m�etodo es su convergencia demasiado lenta� es mas� para x � 
 la serie
�I�
�
� no es absolutamente convergente�
Otro m�etodo que permitir��a aproximar �� consiste en utilizar el hecho
que
arccos�
��� �
�
�
y desarrollando arccos en serie de Taylor� se obtiene un m�etodo cuya
convergencia es mucho m�as r�apida�
��� Consid�erese el problema� determinar
p
�� La primera manera de determi�
nar
p
� es tomar un intervalo cuya extremidad inferior tenga un cuadrado
inferior a � y la extremidad superior tenga un cuadrado m�as grande a ��
Se subdivide el intervalo en dos subintervalos de igual longitud� se elige
aquel cuyas extremidades al cuadrado contengan �� En la tabla siguiente
se da algunas de las iteraciones de este m�etodo�
� I Preliminares
Iteraci�on Ext� Inferior Ext� Superior
� ��� ���
� ���� ���
� ��	
� ���
	 ��	
� ���	
�
� ������� ���	
�
� ������� �����
�
�� �������
��
����� ���������

���	
�
 ���������
	��		� ���������

���	
�
 �������	�
������ ���������

���	
�� �������	�
������ ���������	����	�
�� �������	�
������ �������	��
	
���
La segunda posibilidad es utilizar la sucesi�on de
nida recursivamente
por�
a� � 
�
an�� �
�
an �
an
�
Esta sucesi�on es convergente y se deja al lector la demostraci�on para
que veri
que que el l��mite es
p
�� En la tabla siguiente se tiene los seis
primeros t�erminos de la sucesi�on� Efectuando unas cuantas iteraciones
se obtiene�
Iteraci�on an
� ���
� ���
� ���������������
	 ���������
��
���
� �������	���	
���
� �������	���	
	�
Puede observarse inmediatamente� que el segundo m�etodo para determinarp
� es m�as e
ciente que el primer algoritmo�
Ejercicios
�� Sup�ongase que� el dispositivo de c�alculo� con el que se cuenta� puede
efectuar la divisi�on con resto� es decir� para a� b enteros no negativos�
con b �� �� el dispositivo calcula p� q satisfaciendo�
a � pb� r y � � r � b�
a� Implementar un algoritmo que calcule el maximo com�un divisor de a
y b�
b� Utilizando el inciso precedente� implementar otro algoritmo que
permita calcular m�n � Z� tales que
mcd�a� b� � ma� nb�
I�� Algoritmos �
c� Estudiar la situaci�on m�as desfavorable� aqu�ella donde el costo en
operaciones es el m�as alto� Deducir una estimaci�on de la e
ciencia del
algoritmo�
��� Suponiendo que� el dispositivo de c�alculo puede efectuar la divisi�on con
resto� con la particularidad siguiente�
a � pb� r y � jbj
�
� r � jbj
�
�
a� Mostrar que el algoritmo implementado en el ejercicio 
a�� puede
implementarse para esta nueva divisi�on con resto�
b� Veri
car que� el nuevo algoritmo es m�as e
ciente que aqu�el con di�
visi�on con resto normal� Encontrar una estimaci�on de costo del algoritmo�
��� Para el polinomio p�x� � a� � a�x� � � �� anxn� el algoritmo de H�orner
�I�
��� est�a de
nido por�bn � an�
bi � ai � x�bi��� i � n� 
� � � � � 
� ��
Se plantea q�x� � b� � xb� � � � �� xn��bn�
a� Mostrar que p��x�� � q�x��� Veri
car que p�x� � b� � �x� x��q�x��
b� Generalizar el algoritmo de H�orner� de tal forma que se pueda calcular
p�x�� y p
��x�� al mismo tiempo�
��� Una regla y comp�as constituyen un dispositivo de c�alculo� Sup�ongase
que se conocen dos puntos O y P tales que OP sea de longitud 
�
a� Mostrar que� adem�as de las � operaciones aritm�eticas elementales� la
radicaci�on puede obtenerse a partir de un n�umero 
nito de manipula�
ciones de regla y comp�as�
b� Construir
p
 �
p
��
c� Intentar construir �
p
�� �Es posible�
I�� Estabilidad
En esta secci�on� a diferencia de la precedente� se analizar�a el problema de los
algoritmos y m�etodos num�ericos desde el punto de vista de un dispositivo
material real� m�as conocido como computadora� Para comenzar existen
esencialmente dos tipos de n�umeros en la aritm�etica de un ordenador� el tipo
entero cuya aritm�etica es igual a la de los num�eros enteros� con la diferencia
que el tipo entero de un ordenador es un conjunto 
nito� motivo por el cual
se tiene que tener cuidado con los over�ows en las operaciones aritm�eticas� el
segundo tipo de n�umero es el real� en sus diferentes versiones� la idea de este
tipo de n�umero es la representaci�on de un n�umero real en punto �otante� es
decir todo n�umero real no nulo x se puede escribir de manera �unica como
x � a � 
�b� donde jaj � 
� b � Z� �I���
�
a se llama mantisa y b el exponente� Los n�umeros reales solo tienen una
representaci�on parcial en el tipo real de un ordenador por limitaciones f��sicas
del dispositivo� por consiguiente un n�umero real estar�a en una clase de
equivalencia de tipo de n�umero real� Esta representaci�on de n�umero real
est�a dada por la precisi�on de la computadora�
Cuando se trabaja sobre un computador� se tiene a disposici�on
un n�umero 
nito de cifras� por ejemplo l� para la mantisa� Si a denota el
redondeado de a� se trabaja en realidad con
arr�x� � a � 
�b �I�����
en lugar de x� De esta manera� el n�umero
p
� � 
��
��
���� � � � est�a
representado por
arr�
p
�� � ��
�
��
��� � 
���
si se calcula con l � � cifras en base 
��
Como se dijo m�as arriba� el redondeo est�a determinado por la
precisi�on de la computadora� Esta precisi�on est�a dada por un n�umero dado
por la�
De�nici�on I������ Se denota por eps� el n�umero positivo m�as peque�no tal
que
arr�
 � eps� � 
� �I�����
Este n�umero eps llamado precisi�on de la computadora est�a dado por
los siguientes hechos� si los c�alculos se hacen en base 
� y con l cifras en la
I�� Estabilidad �
mantisa� se tiene
arr��� 
� � � � �� �z �
l
�� � � � � 
��� � 
�
arr��� 
� � � � �� �z �
l
�� � � � � 
��� � � 
� � � �
� �z �
l
�
�� � 
�
deduciendose� por consiguiente
eps � ��
��l� �I�����
si se realiza el mismo c�alculo en base �� como todas las computadoras lo
hacen� se obtiene
eps � ��l� �I�����
Para el FORTRAN sobre una HP������ se tiene�
REAL��� eps � ���� 	 ���� � 
��
�
REAL��� eps � ���� 	 
��� � 
���
�
REAL�
�� eps � ����		 ���� � 
��	��
Ahora bien� un n�umero real y su representaci�on en punto �otante
en una computadora est�an relacionados por el�
Teorema I������ Para x �� �� se tiene
jarr�x� � xj
jxj � eps� �I�����
Demostraci�on�� Sea x � a � 
�b y arr�x� � a � 
�b� Si se redondea a l cifras
signi
cativas se tiene
j a� aj � � � 
��l���
de donde
jarr�x� � xj
jxj �
j a� aj � 
�b
jaj � 
�b �
��
��l��
���
� � � 
��l � eps
por que jaj � 
�
�� �
La estimaci�on dada por �I����� puede ser escrita bajo la forma
arr�x� � x�
 � ��� donde j�j � eps� �I�����
Como se ver�a m�as adelante� la relaci�on �I����� es la base fundamental para
todo estudio de los errores de redondeo�
� I Preliminares
Cuando se trabaja en un computador� se tiene que ser cuidadoso en
la soluci�on de los problemas� pues ya no se resuelve con los datos exactos� si
no con los datos redondeados� Consid�erese la ecuaci�on de segundo grado
x� � �
p
�x� � � ��
cuya soluci�on x �
p
� es un cero de multiplicidad �� Resolviendo en simple
precisi�on� la computadora da un mensaje de error� debido a que
arr�
p
�� � ��
�
��
 � 
��
arr�arr�
p
��� � �� � ���
���� � 
����
Como puede observarse� la manipulaci�on de ciertos problemas utilizando la
aritm�etica del punto �otante puede ocasionar grandes di
cultades� como en
el ejemplo anterior� Es por eso necesario introducir el concepto de condici�on
de un problema� el cual est�a dado en la�
De�nici�on I������ Sea P�x� un problema dado por P � Rn 
 R� La
condici�on � del problema P es el n�umero mas peque�no positivo �� tal que
j xi � xij
jxij � eps �
jP� x��P�x�j
jP�x�j � � eps� �I�����
Se dice que el problema P es bien condicionado si � no es demasiado grande�
sino el problema es mal condicionado�
En la de
nici�on� eps representa un n�umero peque�no� Si eps es la
precisi�on de la computadora entonces xi puede ser interpretado como el
redondeo de xi� Por otro lado� es necesario resaltar que � depende solamente
del problema� de x y no as�� del algoritmo con el que se calcula P�x�� Para
comprender m�as sobre la condici�on de un problema se analizar�a los siguientes
dos ejemplos�
Ejemplos
�� Multiplicaci�on de dos n�umeros reales� Sean x� y x� reales� consid�erese el
problema calcular P�x�� x�� � x� � x�� Para los dos valores perturbados
 x� � x��
 � ���� x� � x��
 � ���� j�ij � eps� �I�����
se obtiene
 x� � x� � x� � x�
x� � x� � �
 � ����
 � ���� 
 � �� � �� � �� � ���
Puesto que eps es un n�umero peque�no� el producto ��� ��� es despreciable
respecto a j��j� j��j� de donde���� x� � x� � x� � x�x� � x�
���� � � � eps� �I���
��
I�� Estabilidad 
Por consiguiente� � � �� El problema es bien condicionado�
��� Adici�on de numeros reales� Para el problema P�x�� x�� � x� � x�� por
analog��a al ejemplo precedente� se obtiene���� � x� � x��� �x� � x��x� � x�
���� � ����x��� � x���x� � x�
���� � jx�j� jx�jjx� � x�j eps� �I���
�
Si x� y x� son de signos iguales� se tiene � � 
� de donde el problema es
bien condicionado�
Pero� si x� 	 �x�� la condici�on � � jx�j� jx�jjx� � x�j se convierte en
una cantidad muy grande� Motivo por el cual el problema est�a mal
condicionado� Para mejor ilustrar el efecto de condici�on muy grande�
consid�erese el siguiente ejemplo num�erico�
x� �
�
� x� � � 
��
� para el cual � 	 ����
�
�����
� 
���
Realizando el c�alculo con � cifras signi
cativas en base 
�� se obtiene
 x� � �
�� � 
���� x� � ��
�� � 
��� y x� � x� � ���� � 
���� Como las
dos primeras cifras son las mismas para x� y x�� la adici�on las ha hecho
desaparecer y no hay m�as que una cifra que es signi
cativa� El resultado
exacto es 
���
 � ��� � ����� � 
��	�
Respecto a la de
nici�on de condici�on� se debe observar dos situa�
ciones� La primera� si uno de los xi � �� entonces se tiene xi � �� la segunda
sucede cuando P�x� � �� la condici�on se la calcula pasando al l��mite�
Una vez de
nida la condici�on de un problema� el siguiente paso es
ver la incidencia que tienen los errores de redondeo en la implementaci�on de
un algoritmo para resolver un problema dado� Tal como se dijo en la secci�on
precedente� un algoritmo es una sucesi�on 
nita de operaciones elementales�
es decir
P�x� � fn�fn���� � � f��f��x�� � � ���� �I���
��
La ampli
caci�on del error� efectuando la operaci�on fi� est�a dada por la
condici�on ��fi�� Por consiguiente�
Proposici�on I���	�� El algoritmo que resuelve el problema dado por
�I������� tiene la estimaci�on siguiente
��P� � ��f�� � ��f�� � � ���fn�� �I���
��
Demostraci�on�� Por inducci�on sobre n� Para n � 
� el resultado es trivial�
Sup�ongase� que es cierto para n� por lo tanto� si el problema es de la forma
P�x� � fn���fn�fn���� � � f��f��x�� � � �����
� I Preliminares
puede escribirse como
P�x� � fn���P ��x���
utilizando la de
nici�on de condici�on se tiene
jP ��x��P �� x�j
jP ��x�j � ��P
��eps
� jfn���P
��x�� � fn���P �� x��j
jfn���P ��x��j � ��fn�����P
��eps�
Finalmente utilizando lahip�otesis de inducci�on� se tiene �I���
��� �
De�nici�on I������ Un algoritmo es num�ericamente estable� en el sentido de
forward analysis� si
��f�� � ��f�� � � ���fn� � Const � ��P� �I���
��
donde Const no es demasiado grande�
La f�ormula �I���
�� expresa el hecho de que la in�uencia de los
errores de redondeo durante el c�alculo de P�x� no es mucho m�as grande
que la in�uencia de los errores en los datos� lo que en realidad es inevitable�
Ejemplo
Sea x � 
�� y consid�erese el problema de calcular 
��x�
 � x��� Se
examinar�a los dos algoritmos siguientes� El primero de
nido por
x� 
x x�x� 
� �
 
x�x � 
�
�

 �
x� 
Las operaciones efectuadas son muy bien condicionadas� por consiguien�
te� este algoritmo es num�ericamente estable�
El segundo algoritmo de
nido por
�x
� 
x
x
� 
x� 
�
x�x � 
�
�

 �
x� 
 �
 
��x� 
�
En este algoritmo� solamente las tres primeras operaciones son bien
condicionadas� Sin embargo la �ultima operaci�on� la sustracci�on� es muy
I�� Estabilidad 
�
mal condicionada� porque 
�x 	 
��x � 
�� Entonces� este algoritmo es
num�ericamente inestable�
La veri
caci�on� si un algoritmo es estable en el sentido de forward
analysis� sobre todo si el n�umero de operaciones es elevado� es a menudo
muy compleja y di
cil� Por esta razon� Wilkinson introduj�o otra de
nici�on
de la estabilidad de un algoritmo�
De�nici�on I������ Un algoritmo para resolver el problema P�x� es num�eri�
camente estable en el sentido de backward analysis si el resultado num�erico y
puede ser interpretado como un resultado exacto para los datos perturbados
 x� es decir y � P� x�� y si
j xi � xij
jxij � Const � eps� �I���
��
donde Const no es demasiado grande y eps es la precisi�on de la computadora�
De la de
nici�on I���� y �I���
�� se deduce que� en el estudio de este tipo
de estabilidad no se requiere conocer de antemano la condici�on del problema�
Ejemplo
Consid�erese el problema de calcular el producto escalar x� � x� � x	 � x��
Para calcular �este� se utiliza el algoritmo
x� � x�� 
�x�� x�� x	� x�� x� � x� � x	 � x��
 �
x� � x�
�I���
��
El resultado num�erico bajo la in�uencia de los errores de redondeo es�
x��
 � ��� � x��
 � ����
 � 	�� � x	�
 � �	� � x��
 � ����
 � 	��
�
�
 � 		��
donde j�ij � j	j j � eps� Este resultado es igual a x� � x� � x	 � x�� si se
plantea
 x� � x��
 � ����
 � 	���
 x� � x��
 � ����
 � 		��
 x	 � x	�
 � �	��
 � 	���
 x� � x��
 � ����
 � 		��
Despreciando los productos de la forma 	i � �j � la relaci�on �I���
�� es
satisfecha con Const � �� Por lo tanto� el algoritmo �I���
�� siempre es
num�ericamente estable en el sentido de backward analysis�
El ejemplo precedente muestra que un algoritmo puede ser estable�
incluso si el problema est�a mal condicionado� En consecuencia� es necesario
bien distinguir las nociones de estabilidad y condici�on�
� I Preliminares
Ejercicios
�� �Cual es la condici�on de la sustracci�on de dos n�umeros�
��� Determinar la condici�on del problema P�x�� x�� � x��x� con x� �� ��
��� Hallar la condici�on del c�alculo del producto escalar
hx� yi �
nX
i��
xiyi�
��� Mostrar que el sistema lineal�
ax� by � 
cx� dy � �
� con ad �� bc
es num�ericamente estable en el sentido de backward analysis�
��� Las raices del polinomio x� � �px� q � � son�
� � p�
p
p� � q� 
� � p�
p
p� � q�
Mostrar que para p � �� grande� y q � �� muy peque�no� este algoritmo
es num�ericamente inestable� Utilizando la relaci�on 
�
� � q� encontrar
un algoritmo que es num�ericamente estable en el sentido de backward
analysis�
I�� Un ejemplo� C�alculo de Pi
En las secci�on precedente se ha visto que el dispositivo material que efectua
los c�alculos num�ericos tiene en general dos tipos de n�umeros� los enteros
que se asemejan mucho a los enteros matem�aticos y el tipo real que es
una representaci�on del n�umero real� Tal como se mostr�o� ambos tipos de
n�umero presentan ciertas particularidades� por ejemplo son en cantidad

nita� para el tipo real existe el redondeo de los n�umeros� Por consiguiente
si se utiliza el tipo real para determinar �� se tendr�a una precisi�on de
� decimales� para doble precisi�on se obtendra 
� decimales de precisi�on�
para cuadruple precisi�on� que algunos lenguajes de programaci�on cuentan�
se obtendr�a �� decimales de precisi�on� Por lo tanto� la precisi�on para obtener
� est�a determinada por el lenguaje de programaci�on y en algunos casos por
el tipo de computadora con que se cuenta�
En esta secci�on se pretende mostrar que estas limitaciones no constituyen
necesariamente un impedimento para determinar un n�umero� en particular
�� con la precisi�on que se desee�
Una de las maneras m�as usuales de determinar � es utilizar el desarrollo
en serie de Taylor en el origen de arctanx� el cual est�a dado por
arctanx �
�X
k��
��
�k
�k � 
x�k��� �
���
�
De �I���
� se deduce� para x � 
� que
� � �
�X
k��
��
�k
�k � 
� �I�����
Como se recalc�o en la secci�on I��� utilizar la serie �I����� no es conveniente�
por que la convergencia de esta serie es muy lenta� Utilizando la relaci�on
tan�� � �� �
tan�� tan�
� tan� tan� �
una veri
caci�on inmediata conduce a
�
�
� 
� arctan
�
� � arctan
��
� � arctan 
���
� �I�����
Remplazando �I���
� en �I������ da como resultado
� I Preliminares
� � ��
�X
k��
��
�k
�k � 
�
�
��k��� �z �
A
���
�X
k��
��
�k
�k � 
�
��
��k��� �z �
B
� ��
�X
k��
��
�k
�k � 
�
���
��k��� �z �
C
� �I�����
Ahora bien� se desea obtener una representaci�on de � en notaci�on decimal
con N decimales de precisi�on� Si cada serie del lado derecho de �I����� es
calculada con una precisi�on de 
���N��� se tiene largamente la precisi�on
deseada� Denotando por !A� el valor calculado de A� !B� el valor calculado de
B y !C � el valor calculado de C� se tiene�
!A � ��
MAX
k��
��
�k
�k � 
�
�
��k���
!B � ��
MBX
k��
��
�k
�k � 
�
��
��k���
!C � ��
MCX
k��
��
�k
�k � 
�
���
��k���
De donde�
��� !A�A��� � �� �����
�X
k�MA��
��
�k
�k � 
�
�
��k��
����� � ���
�
���MA�	
� �
�
��� ���� !B �B��� � �� �����
�X
k�MB��
��
�k
�k � 
�
��
��k��
����� � ���
�����MB�	
� �
����� ���� !C � C��� � �� �����
�X
k�MC��
��
�k
�k � 
�
���
��k��
����� � ���
������MC�	
� �
������ �
Por hip�otesis� se tiene por ejemplo que
���A� !A��� � 
���N���� por lo tanto
para asegurar esta precisi�on es su
ciente que
��
�
�
���MA�	
� �
�
��� � 
�
��N����
remplazando el signo � por �� se tiene
��
�
�
���MA�	
� �
�
��� � 
�
��N���� �I�����
I�� Un ejemplo� C�alculo de Pi 
�
obteniendo de esta manera
log������� ��MA � �� log���
��� log���
� �
�
���� � ��N � 
��
Despejando MA� se obtiene
MA �
N � 
 � log������� � log���
�� � �
�
���
� log���
��
� �I�����
Del mismo modo se llega a�
MB �
N � 
 � log������� � log������ � �
�����
� log������
� �I�����
MC �
N � 
 � log������� � log������� � �
������
� log�������
� �I�����
Una vez determinada la cantidad de t�erminos en cada serie para calcular
!A� !B y !C� es necesario de
nir una representaci�on de los n�umeros reales y
su respectiva aritm�etica que permita calcular !A� !B y !C con la precisi�on
requerida�
Sea b � 
� entonces todo n�umero positivo x se escribe de manera �unica
como
x �
�X
k��
ak
bk
� �I�����
donde � � ak � b para k � 
� Suponiendo que b � 
�m� para obtener una
representaci�on de x con N decimales de precisi�on� es su
ciente conocer ak
para � � k � N�m� �� Se suma � a la cota anterior por seguridad� Por lo
tanto� para todo n�umero positivo x�el redondeado !x con N cifras decimales
de precisi�on puede escribirse como
!x �
N�m��X
k��
 ak�
�
mk� �I���
��
con � � ak � 
�m para k � 
� Comparando �I����� con �I���
�� se tiene
que ak � ak para � � k � N�m � 
 y jak � akj � 
 para k � N�m � ��
deduciendose de esta manera la�
Proposici�on I������ Sea x un n�umero no negativo y x su representaci�on
dada por �I����	�� entonces
j!x� xj � 
���N��m�� �I���
�
� I Preliminares
Con los elementos presentados� se est�a en la capacidad de formularun
algoritmo que permita calcular !A� !B� y !C� por razones obvias el algoritmo
ser�a el mismo� Por consiguiente� es su
ciente dar el m�etodo que permita
calcular !A con la precisi�on requerida� De la f�ormula �I����� se puede observar
que las operaciones efectuadas son adiciones o sustracciones� divisiones por
expresiones de la forma ��k�
� y divisiones por 
� o 
��� La aritm�etica ser�a
consiguientemente de
nida en tres pasos o �etapas�
El primer paso ser�a de
nir la division por un entero p� Sea x un real
positivo� su redondeo se escribe como en �I���
��� por consiguiente x�q
redondeado se escribe
bx
q
�
N�m��X
k��
bk�
�
mk� �I���
��
donde los bk se los de
ne de manera recursiva� utilizando la divisi�on
euclidiana� as���
a� � b�q � r��
a� � r� � 
�m � b�q � r��
���
aN�m�� � rN�m�� � 
�m � bN�m�� � rN�m���
�I���
��
El segundo paso ser�a de
nir la adici�on y la sustracci�on para dos reales
positivos x y y� Si se denota los redondeados por !x y !y� sus representaciones
en punto 
jo est�an dadas por�
!x �
N�m��X
k��
ak�
�
mk� !y �
N�m��X
k��
bk�
�
mk�
La suma redondeada se escribe por lo tanto
�!x� !y �
N�m��X
k��
ck�
�
mk� �I���
��
donde los ck est�an de
nidos recursivamente� utilizando la divisi�on eu�
clidiana� por�
cN�m�� � dN�m��
�
m � aN�m�� � bN�m���
cN�m�� � dN�m��
�
m � aN�m�� � bN�m�� � dN�m���
���
c� � a� � b� � d��
�I���
��
El tercer paso ser�a de
nir la multiplicaci�on de un real positivo con un
entero q� Sea el productovskip��pt
cq!x � N�m��X
k��
bk�
�
mk� �I���
��
I�� Un ejemplo� C�alculo de Pi 
�
donde !x est�a dado por �I���
��� los coe
cientes bk est�an de
nidos recursiva�
mente� utilizando la divisi�on euclidiana� de la manera siguiente�
qaN�m�� � bN�m�� � dN�m��
�
m�
qaN�m�� � dN�m�� � bN�m�� � dN�m��
�
m�
���
b� � qa� � d��
�I���
��
Habiendo de
nido las operaciones requeridas para calcular � con la
precisi�on requerida� se puede de
nir el algoritmo que calcular�a !A� y por
consiguiente !��
Algoritmo
�� Se de
ne x �� 
�
�� a � x� k � ��
��� Hacer para k � 
 hasta k � MA�
x �� x�
���
y �� x���k � 
��
a� � a� ��
�ky�
��� a �� �� � a�
Finalmente� se debe hacer un an�alisis de la propagaci�on de errores de
redondeo� cometidos en el c�alculo de !A� para asegurar que el resultado que
de la computadora corresponde con lo esperado� Este estudio se lo efectuar�a
en tres partes� Sea !x�k�� el resultado realizado por el algoritmo al calcular
x�k�� para x � 
�
�� Utilizando la proposici�on I���
� se tiene�
!x � x� �� j�j � 
��N��m � �I���
��
deduciendose inmediatamente�
!x	 � �x� ���
�� � 	�
!x� � !x	�
�� � 
�
���
�I���
��
Utilizando desigualdades triangulares y considerando series geom�etricas� se
obtiene ��!x�k�� � x�k���� � 
� �
�
���
�
�N��m� �I������
La segunda operaci�on� que aparece en el algoritmo� es la divisi�on por los
enteros de la forma �k�
� Por el mismo procedimiento que antes� se llega a��� �x�k�����k � 
�� x�k�����k � 
���� � � � 
��N��m� �I����
�
�� I Preliminares
Por ultimo para obtener !A� se tiene una suma de MA � 
 t�erminos y un
producto por ��� En cada suma se comete un error menor a � � 
��N��m� de
donde se tiene como estimaci�on del error acumulado��� !A�A��� � 
���MA � 
�
��N��m �I������
Ahora bien� si 
���MA�
� es m�as peque�no que 
�
�m��� entonces el objetivo
es satisfecho largamente�
Como ilustraci�on de lo expuesto� se ha calculado � con 
���� decimales
de precisi�on� utilizando una HP������
� con �



 decimales
	���������	� 
�
�	�	
�� ���		
	�
� ���

���
� ��	��	
��� E������
�
���
���� ���	�

��� ���
���
�� 
��
�	�
�� 	����
��
� E������

���
�
��� 	�
�	����
 ��	
������ ���
��	�
� �	����
��
 E������
�
���
���� 
����
���	 
��������� ��������
� ���	�	
��� E������
���

���
� ����		���� �
�
���
�	 	

�

	��� �
�������� E������
����
����� 	���	�
��� ���	����
� �		�	��
�� ��������
	 E���	��
���
���� ��	���

�
 �

������� ���
������ ��
��	��	� E���	��

�����	�� ���		��	�� �

������� �	
������� ���������� E������
		��
�
�	� �
�������	 ����
���
	 
��	����
� 	�����
��
 E������
�
����	
�� ��
����
	� �

�
��
�� 
����
�	
� 
	�������� E������
�
		�
		�� ��������	� 
����	���� �	�����
	
 ���
���
�
 E������
����	
��
 ��	���
�
� ��	�
�
��	 
��
�
�
�� 
�������	� E������
�����
��
� ����	���
� 

�
�	�� 
�

����� 
	�	
�
� E������
���
������ �����	�	�� ������
�	
 ����
���
� �
���
��	� E���
��
���������� ���������� 
���	���
� ��
�	���
 �
�	����� E���
��
��
�
���	 �������
	
 ��

������ ���
	�
	�
 �����	�
�� E���
��
���������� 	����
	��� �����	�
�� 		���
��	� ����	��

� E���
��
������	�	 

	
��

� �
�		��
	 
������
�
 
�����
	�	 E������
��
��	���� �
����
	 �������
�	 

�	�	
� �	
����

 E������
�
�

��	� �
����
��� �	�����
 ���������� ��������
� E������
	
�����
�� �����
�
�	 �


���	�� �		
�
�
�� 
�	�	����� E������
�	�	��
��� �
���
	�� ������	
�� ���
��
�� 
	�
��	��� E������
��
�
�
��� ���������� ��
���		�� �
��
�

�� 

��
���
	 E������

�
���	
�� ��	�	����� ��������
 ���
��	��� �
�

����� E������

�
	����	� �	
�
����� �
���
���� ��������
� ��
�

	
�� E������
���
���	
� 
�
��
�
� ����
�	��� ���
����
� ���������� E���	��
�		�	�
�� 
�
������� 
��������� �������
�	 
�����	��� E���	��
��		
��	�� 	��
����� 
����
	��	 �������
�� ��������
� E������
�

�	��

� �	����	��
 ���������� ��
�	���	� �
��
��
�� E������
��
��
��
	 
�������

 �
�������� ����
���
� 
���	����� E������
	�����	��� 
���
���� ��	��
���� ������

�
 	�
�
�	�� E������
�	��
�
��� �����

��� ��
�
��
�
 ��
�
���
 
�
�	
��� E������

���
����� ���������� �
	��
���
 
�	������� ��
	��
��
 E������
���	����
	 ������		�
 �
��
����
 �	
��		�	� �
	����			 E���
��
���
����� 
����
�
	� ���
������ ��������
� �
�������� E���
��
��
�
�
� ���������	 ���
���

� �
�	�
��

 ��
�

�	
	 E���
��

�
��
�
�� 
��������� 	

	

�	�� ����
����� ���������� E���
��
	���
�
�� �
���
�

� ���������� �����
���� �������
�	 E������
��
���

�� ��	������� ��
��	
�	
 
�������	� �	
���
�
 E������
��
����
� 
	�����	
� �
��
	���� ���
�		��� 

��
����� E������
����
���

 ��������
	 �
	�����
� �
��
����� ����
���
 E������
��
���

�� 
�
�����
� ���������� 	�	���	
�� �	����
��	 E������
���������
 ��	������	 ����
����� �������	
� ���������� E������
�
��
�
	
 �����


�� ��
��
��� 
�	����
�	 ��
��
�	
� E������
�
�
	
�
�� �
������� 
��������� �	����	��� ��
�����
� E������

���
�
	� �����
�
�� 	
	�
	���� ���������� �
�����	

 E���	��
�	�������� �	����
��
 
�
�
���� ��	���
�� �������
�� E���	��
�����
�
�� �
�
���	�	 ����
����
 �
�

��
�� 
�����
��� E������
���
��
	�� ����
��
�
 

������	
 ���������� ��
�

�	�
 E������
���������� 	��

��	�� 
�����
�	 ���	�	���
 �
�	������ E������
���
�����
 ���������� ��������

 
�
��
�	�� �����	�
�
 E������
��
�
���� �������		� 
��
��
�
� ���
�
��� �

���	
�
 E������
����
����� �
��
����	 �����

�
� 	���

�
�� �
���
��
 E������
����

��
� 
�������
� �
����	�	 
��������� 	
���	�	�� E���
��
I�� Un ejemplo� C�alculo de Pi �
���
�
���
 �����
�

� �������	�� 
	�
	���	� �	��
����� E���
��
��	�����	� �	�������� 
��	
�
�� ����
����	 ����
��	�� E���
��
�	
����
	� ��

�	���� ��
	
��

 �
�

�
��
 		�����
�	 E���
��

�
����	� ���	���
�� 	�����
�
� ���	
����� 
��
�����
 E������

�����
�	� ���������� �	��
���� ���	
����	 
�
����
�� E������
�
	������� ����
���
� �������	�
 �
�����
�
 �����	���� E��	���
��
�����
� ���������� ��	���	

� �	������	
 ���	

���� E��	���
��	
�	
 �
	�	����
 ���
	��
� ��
������� ���������� E��	���
�	��
�	
�� 
	������� ���������� �������
�� �
��
	���
 E��	���
�������	�� 	��

���
� ��
�		�
	� ��������	� ��
����
�� E��	���
������
��� ��
����
� �	�
�
	�	
 �����
���� ���
�
���� E��	���
������
��� ��
��	��	� 
������
� �
�����		 

���	���
 E��		��
�	���
�	� 
�	�����
 	�����
��� �	���
���
 ���
����
� E��		��
	���
���
 ���
�

��� ���
�����
 ��
����
�� ���
��
��� E��	���
������
�� ������
��
 	���
��
�
 �
	���
�
 	����	�	�� E��	���
�
������
	 �
����	��
 
��������� ���
���		� �
���	���� E��	���
�
���	���� 
��
���	�
 	�����
��� ������
��
 ��	
��
��
 E��	���
	�������

 �����
�
�� �
�	
	��� �
		��	��� 
��
��
�	� E��	����	����
�� 
��	��	��	 	�
�
�
��� ����
����� 
�����
��� E��	���
����
����� �	
�
��
�� 
����	���� ��

��
�
� �
�
�����	 E��	
��
�		����
�� �
���
��		 �
	����
�	 
�	����	�� �
��	��
	� E��	
��
�
	������
 �	

	�	��	 
����	
�
� 
���	
���
 ����	�
��� E��	
��
�
��	
	�� ��	�
�
��� ��������	� ��		�	
��� 
��������� E��	
��
�����	���� ��
�����
� ��	
���
	
 ����
�
�

 	��	�����
 E��	���
��	�����
� 
�
����		� ��
�	�	��
 ������	��� 
	����

� E��	���
�
�
	�
��� ���������� 
�	���
��� ���������
 �������	�� E������
����
	���� �
�����

� 	
�	���
�� ��	���
��� ����
����� E������
�
��	���
� �
�	������ 
��
���
�� 	�����
�� 
���
����� E������
		�

��	�� ��	��
�
�
 �	�������� 
�	�����
� 
�
���� E������

��������� ������
�	� ���	���	�
 �
�
��
��� �������
�� E������
���	
� ���	����
� �
���
���� ����	��	
� �����	���
 E������
���
�����
 
��
		���� 	��
������ ����

�
�
 �
�
���
	� E���	��
�	�	�
�

 ���
	���	� 
�
�		���
 �
���
���� 
��	
���� E���	��
���������
 ���
������ ������
��� �	�����
�� ���
�����	 E������
����
����
 	
������
� ��
��	�
�� 

�������� 
��
����� E������
������
��	 ���	���
�	 ������
	�� �	
��
��
	 ������
��� E������
�	
�
�	��� 
�����

�
 ���
��	��	 ��
������� �
�
�
��� E������
��
������� ��
���	�
� �
��
��� �������
�� ���		���
� E������

�	������
 
�	
�
���	 ��		��
��
 ��
�
����	 
�
������� E������
�������
 �
	
�
��� ���������� ������
�		 ��	�	
���	 E���
��
�
������
� ���	
�	��
 	�����
��� ��
�
�	
	� 
�������
� E���
��




��

�� ���������
 �
�����	�
 ���
��
��� ���������� E���
��
��
����	
 ���		
�
�� ���������� �����	�
�� ��
����
	� E���
��
����	�
�
 �	�
������ 
	���	��
� 
	�����
�� �	
�
�	��	 E������
������
�� 
�������	� �
���
�			 ���	��

� 
��	����	� E������

�����	�� ��
	
���
 ���	���
�� 
���


�
 ��	����
�� E������
�������	�� �
���
	��� �	���
��	� ����
	�	
� ��
���
�� E������
�

�
����� �����	��
� ��
��
���
 �	
�
��
�� �����
��	� E������
��	
�����	 �����
�
�� ����	�	

� ���
���
� ���	����
� E������
���

��
	
 	
�
��	��� ��	
��
�� ����
�	�

 ����

���
 E������
��

��
	�� 		������
� �����
��	
 	�	����	�� 
����	� E������
���������
 
�	�
���		 ���������� 	��
���
�� ��
	���
	
 E���	��
	������	�� ��	�
��
�� �
��	
� 	
	�	�
 ��
������� E���	��
	���
��� ���������� ����
����� ��	����
�� 

�
���		� E������
	����	���
 ���	���
�	 	����
	��
 �	�	���
� �
�	�����
 E������
�	���
�� �
����
�� 
��
��	��� ������
�
� �����	���
 E������
������
�	� 
�	��

		� 		�����	�
 
	����
�	
 ��	
���
	� E������
	���
���� ����	
�		� �
�
���� �
�	��
		� �	�
���
 E������
���
���		
 �������
�� 
��	����� 
��
��

� 
�����
 E������
���
�
	�
 �
��
�
�� 
��	���
	� ���
��
		� ���	��	��	 E���
��

	����	��	 ��
������� �������
�
 ������	��
 ��	��
��	� E���
��
�

���	


 ��
������
 ���������
 	�	������� �	����	��� E���
��
�����
��
� ��
������� �������
�
 �		
��
��� ���
��	�
� E���
��

�
�

	��	 ��
���� 

������ 
���
�
��� �	��	��
	 E������
�
�	��
��� ���
��
�
 �����
�
�� ���	���	�� �
�������� E������
�
������
	 ��
������� ������		
� �	��	���
� ���
���� E������
������
�� 
��������	 ������
�� ���������� �	�����	
 E������
�����	
	�� �	�
����
 

��	���
 ��
�
���
� ����	�
��� E������
����
����� ��	�
���	� ��������	� 	������
�� ��
������� E������
�
�	�
 
��
���
�� ���

�	�� ���������� �����
�
	
 E������
�

�
�
�
� �
��
����	 	
������� ����	����� ���
	�		�� E������
	��	
���
� ��
�	���		 ���
����	
 ��
������� �

���
�� E���	��
���������
 ���	
���	� 	��
�����
 ������	
�� ���������� E���	��
�� I Preliminares
���
���
�� 
������	�
 �����
	��� 
��

��
� 

�
		
��� E������
��
		���
� ��
��
���	 �	���		��� 
����
�	�� 	������
�� E������

�
����	�� �	
����
� 	�
��
���� 	��	�
��
	 	�	�	
	��
 E������
���������	 
�
��	
��� ��
�		
��� 
�
���		�� �
	�
���	 E������
�
�

����� �
������� 	�����	�
� 
�
�	�
��� �
����
��� E������
��
	������ ��	���
��� 

����
	�	 
���
����
 	��
�	���� E������
	�
������	 ��	����
�� �������	�� ����	����� ��
��
���� E���
��
���
	����� ���	�		��
 ��
�	����	 �
�������� ����	�	�	� E���
��
���������
 ���	
��	
� ��	�	����� ���

	
� ��	
�����
 E���
��
�
���
�	�� 	�	��	��

 ���
�
��
� ���
������ �����		��
 E���
��


���
�
�� �	���
���� �
�
��
��� 		�	�		��� �
	������� E������
������	
�� �
���
			
 ���
������ �

�	���

 �
	
�	��
� E������
�
������ 

�����	�
 		������
 	��
������ 
�����
�
 E��
���
�����
��� ���������� 
	
������� ������	

 ��
�
	��	
 E��
���
����
����
 �������
� 
������	
� 	�

�
		�	 ����

	
	� E��
���
	�	����	
� ��
�����
� ��	
��	�
 �
�		��
	 
�����	��� E��
���
���	�
�	
� �
�
��	
� �	�������� ����		
��� �
��
	�
�� E��
���
��������
� ���
�
��	� 
����
	
� ��
������� 
�
�����

 E��
���
����	���	� 	��������� �	�	�
���� �
�������� 	�
�
��� E��
	��
�
������� ���
������ 
���	�	�	 ��	�
����	 ��	���
��	 E��
	��
	��������� 	����
���
 ����
����	 �������
�
 ����	��	�
 E��
���
��
��	���� 
�	�	�	��� ����

���
 
�
����
�	 ��
��
���� E��
���
�
���		��� ������
�
	 ���������� �	�
�

��� �	��
���
� E��
���
	
�
����� ��
������� ���	��
��	 
��
��
�	� 	���		���	 E��
���
��
�
�
��� ������	
�
 ����	����� ����
�
��
 ���	���
�� E��
���
�������	�� ���
�	��	� ���
����
	 ���	�����
 ����	

��� E��
���
			
�����
 ��	����
�� ������
��
 ���
���
�� �	��
���
� E��
��
����
	���� ���������� ��
��
�
� ���������� ����
���	� E��
��

�
������� �
�������� �������

	 
��������� 	��

����� E��

��
�������
�� 

�����

� �����
���
 
�������
� ��������
	 E��

��
�
���	��� 
����	���
 �	�
������ ���
��
� �
��
����
 E��
���
���
�
�	�� ������	�
� ��	���
�� �
��	��
�� ��������
� E��
���


���
	� ���������	 	�
�����
� ���������� 
����	���
 E��
���
�
���
��� 
��
���	�� 
���

���� 

�������� ��
���
��� E��
���
���
������ ��������
� �������	�� 	
�
�����
 �		��	�	

 E��
���
��

������ 
�
��
���� ���
	�	�	� 
��		
�

� 
��	
����
 E��
���
	�

��	�� ��
�
��� ��	�
��	�� ��������	� 	���	����� E��
���
������

�	 
�	
������ �	�
�
		�	 ��
���
��	 ���	������ E��
���
�	�
�
�
� ��	��
���� ��	
��
�� ��
�	����� ��
�	����� E��
	��
���	
�
��� ��		������ 		��
�
��� �����
	
� 	�	
��
�	� E��
	��
�	�������� �		
����
	 ��
���
��� ��������	� ����
����
 E��
���

������
�� ��			�	��� 
���	
	
�� �
����

	� �
��
	��
 E��
���
�����
�
 �

������� ���
������ �
�
	���	
 ���	�
���
 E��
���
	��
���	�� �
���
���
 	
�

	���� ���
�
�
�� ������
�
� E��
���
�
�
	�

�� 	���
��
 ���������
 ��
	���
�� 	��������� E��
���
���	��	��
 ���������� ��������
� �
���
��

 �
	
������ E��
���
�
�
���	�� 
��
��	��� 
��
�	�	�� ����
����� �
��
��� E��
��
��
��
�
� ����
���
� �����	�
�� �����			�� ��
����	�� E��
��
	������

� ���������� ���	
�
��	 ������
��
 	
�������� E��

��
�����
�
� 
��
������ ��
����			 ��	��
���� 
�
������	 E��

��
��
	�	��
� ���
������ �	�	���
�� ���
����
� �����
���
 E��
���
��
���
��� 
�
	�
	�
� 	�����
��� ���	�

��� 
��
���	�	 E��
���
�����
���� ��	�
����� ��������	� 
�
	�����	 �	
����	�� E������
��

�
���� 	��	������ 	��������� 	
��
����� �	�

����� E������
���������� ��
������� 
��
����� �
��	���
� �		
��	

� E������
�������	�	 ��������
� 	

����
�� ��
�����
� 	��������
 E������
���������� ���
����
� �����
		

 ��	������� ���	��
��
 E������
�������	�
 �

���
��� 	��
�����
 
�
��
���� �����	���� E������
��
���
��� �
	

	

� ��		���
�	 ��
��	��
� �
�����
�� E���	��
���
����
 �
�
��	
�� ���
	��	�
 	�
����


 	����	
��� E���	��
��	
�
�
	� ��������
� ��

	�
�� 
�����
��� ��	������
 E������
���	
����� 
�	������
 ����
���
� ��	�

��
 

������
� E������
�	����	�
� �
������
� 
��������� �����
���� ���

��
	� E������
�������
�� ��
�����		 ��
�	�
� 
��
�
���� ���	�
���� E������
�		��
��	� 	
		������ �

�����
� �	����	
	� ��
	�	
�	� E������
�����	�
�� 	�
������� ��

��	
�� 	��
������ �	
��
��
� E������
	������	
 	���
�	��� ��������
� �
����	��� ����
��
�
 E���
��
	�
��
���
 	��	���
�	 �����
���
 ����	��	�
 ��	�
����� E���
��
���
�

� ����
��
�	 �

�
���
� ����
����� 
	���
��
	 E���
��
���������� �
�	�
���� �
�������	 ����	����� ��������
� E���
��
�����
�	�� ��	���
��	 �	�������� �
�������� ����	
��� E������
���������� 	
��

���� ��
���
�	� ���
������ ���
�
�
 E������
��������
	 ����
����� �������� ���������� ����	
��

 E������
Cap��tulo II
Sistemas Lineales
Una gran cantidad de problemas implica la resoluci�on de sistemas lineales
de la forma
Ax � b�
donde
A �
�	 a�� � � � a�n��� ���
an� � � � ann
A � b �
�	 b����
bn
A
con coe
cientes reales o complejos� Por esta necesidad es importante la cons�
trucci�on de algoritmos que permitan su resoluci�on en un tiempo razonable y
con el menor error posible� Cada problema tiene su particularidad� motivo
por el cual no existe un m�etodo general mediante el cual se pueda resolver e
�
cazmente todos los problemas� Es verdad que existen m�etodos casi generales�
que con peque�nas modi
caciones pueden servir para encontrar la soluci�on
de un problema particular� A lo largo de este cap��tulo se expondr�an estos
m�etodos� dando criterios de estabilidad y estimaciones de error�
En la primera secci�on se tratar�a la condici�on del problema lineal� para
este efecto ser�a necesario introducir elementos de la teor��a de normas en
las matrices� para luego introducir las nociones relativas a la condici�on del
problema lineal�
En la segunda secci�on se abordar�a los m�etodos de resoluci�on como son�
el Algoritmo de Eliminaci�on de Gauss� la Descomposici�on de Cholesky y
algunas modi
caciones de estos m�etodos� En esta secci�on se estudiar�a la
implementaci�on de tales m�etodos� como tambi�en la estabilidad de estos�
La tercera secci�on tratar�a� la teor��a e implementaci�on de los m�etodos ite�
rativos lineales como� Jacobi� Gauss�Seidel y SOR� As�� mismo se analizar�an
algunos problemas tipos y se har�an comparaciones de tales metodos�
En la cuarta secci�on� se ver�a los m�etodos de tipo gradiente cuyo enfoque
es diferente a los m�etodos de las dos secciones precedentes� en efecto� son
m�etodos que encuentran la soluci�on a partir de problemas de minimizaci�on�
Se resolver�an ejemplos tipos y se comparar�a la e
ciencia de �estos con otros
m�etodos�
�� II Sistemas Lineales
La �ultima secci�on describir�a el M�etodo de los M��nimos Cuadrados� como
una generalizaci�on de lo anteriormente expuesto� introduciendo como coro�
lario la noci�on de Pseudo�Inversa� As�� mismo se analizar�a la implementaci�on
del m�etodo QR� incluyendo una estimaci�on del error de tal m�etodo�
II�� Condici�on del Problema lineal
Normas de Vectores y Matrices
La noci�on de norma y espacio normado es un instrumento matem�atico muy
util en el estudio de las magnitudes que se manipulan� como tambi�en un
instrumento en el estudio de la convergencia y los l��mites� Se empezar�a
de
niendo el concepto de norma en espacios Rn � para luego de
nir en el
�algebra de las matrices a coe
cientes reales�
De�nici�on II������ Una norma sobre Rn es una aplicaci�on
k k � Rn �
 R�
con las siguientes propiedades�
kxk � �� kxk � � �� x � ��i�
k�xk � j�j kxk � donde � � R�ii�
kx� yk �� kxk� kyk �iii�
La primera condici�on implica que una norma siempre es positiva y es
nula siempre y cuando el vector sea el vector nulo� La segunda propiedad es
la homogeneidad de la norma y la tercera condici�on es m�as conocida como
desigualdad del tri�angulo� Las normas m�as usuales en Rn son las siguientes�
kxk� �
nX
i��
jxij � norma ciudad�bloque�
kxk� �
�
nX
i��
jxij�
� �
�
� norma euclidiana�
kxkp �
�
nX
i��
jxij�
� �
p
� p � 
�
kxk� � maxi�������n jxij � norma de la convergencia uniforme�
Estas normas� que son las usualmente utilizadas� tienen algunas propiedades
en com�un� La m�as importante es que� si se aumenta en valor absoluto una
de las componentes� la norma se incrementa� Es necesario formalizar este
hecho� motivo por el cual� se tiene la�
�� II Sistemas Lineales
De�nici�on II������ Si x � �x�� � � � � xn� � Rn � se de
ne el valor absoluto de
x como jxj � �jx�j � � � � � jxnj�� Se dice que jxj � jyj� si jxij � jyij para todo
i � 
� � � � � n� Una norma k k sobre Rn se dice que es�
�a� Mon�otona� si jxj � jyj implica que kxk � kyk para todo
x� y � Rn �
�b� Absoluta� si kxk � kjxjk para todo x � Rn �
Proposici�on II������ Una norma k k sobre Rn es mon�otona� si y solamente
si es absoluta�
Demostraci�on�� Si la norma k k es mon�otona� sea x � Rn � llamenos y � jxj�
Como jxj � jyj� y jyj � jxj se tiene inmediatamente� porque la norma es
mon�otona� que kxk � kyk�
Si la normak k es absoluta� sea x � Rn � consid�erese
 x � �x�� � � � � xk��� �xk� xk��� � � � � xn�� con � � "�� 
#� Utilizando el hecho
que la norma sea absoluta� desigualdad del tri�angulo y efectuando c�alculos
algebraicos se tiene�
k xk �



��
� ���x�� � � � � xk����xk� xk��� � � � � xn� � 
��
� ��x � �x



� 
�
�
� �� k�x�� � � � � xk����xk� xk��� � � � � xn�k� 
�
�
� �� kxk� �x
�
�
�
� �� kxk� 
�
�
� �� kxk� � kxk � kxk �
Ahora bien� si x � �x�� � � � � xk � � � � � xn� y y � �x�� � � � � xk� � yk� xk��� � � � � xn��
con jykj � jxkj� utilizando la desigualdad anterior se tiene kxk � kyk� Para
demostrar que jxj � jyj implica que kxk � kyk� se repite el anterior paso n
veces� es decir una vez por cada componente� �
Una matriz de ordenm�n puede ser vista como un vector que pertenece
al espacio Rmn � de esta manera de
nir la norma de una matriz como la de
un vector� pero se perder��a as�� muchas de las propiedades que tiene una
aplicaci�on lineal� Es por eso la�
De�nici�on II���	�� Sea A una matriz de m� n� se de
ne su norma como
kAk � sup
x���
kAxk
kxk � supkxk��
kAxk � �II�
�
�
La de
nici�on de la norma de una matriz depende evidentemente de las
normas elegidas para kxk y kAxk� Sin embargo puede ser veri
cado sin
ning�un problema� que la norma de una matriz� veri
ca las condiciones de
norma de un vector� La demostraci�on es una simple veri
caci�on de estas
condiciones� utilizando la de
nici�on de supremo� Adem�as si las norma de los
espacios Rn y Rm son mon�otonas o absolutas� es facil veri
car que la norma
II�� Condici�on del Problema lineal ��
de matriz inducida por �estas� es todav��a mon�otona� es su
ciente utilizar
la de
nici�on para probar esta a
rmaci�on� Por otro lado kAk es el n�umero
positivo m�as peque�no � que satisface kAxk � � kxk� por lo tanto
kAxk � kAk kxk � �x � Rn � �II�
���
Una norma sobre el espacio de matrices veri
ca las siguientes propiedades�
dada por la�
Proposici�on II������ Cualquier norma sobre el espacio de las matrices
Mm�R� satisface las propiedades adicionales siguientes
kIk � 
� �II�
���
kABk � kAk kBk � �II�
���
Demostraci�on�� La relaci�on �II�
��� de la proposici�on es consecuencia
inmediata de la de
nici�on de la norma de una matriz�
La relaci�on �II�
��� es consecuencia de las observaciones hechas despu�es de
la de
nici�on� en efecto
kABxk � kAk kBxk � kAk kBk kxk �
kABxk
kxk � kAk kBk �
kABk � kAk kBk �
�
Se ha dado las propiedades esenciales de la norma de matrices� pero es
necesario conocer algunas de �estas por su utilizaci�on frecuente� Utilizando
la misma notaci�on que en las normas de los vectores de
nidas al inicio de
la secci�on� se puede utilizar la misma notaci�on en los ��ndices de las normas
de las matrices� con la convenci�on que las normas de los vectores tienen los
mismos ��ndices�
Teorema II������ Sea A una matriz de n�m� entonces
kAk� � maxj�������m
nX
i��
jaij j � �II�
���
kAk� �
p
valor propio m�as grande de AtA� �II�
���
kAk� � maxi�������n
mX
j��
jaij j � �II�
���
�� II Sistemas Lineales
Demostraci�on�� Se comenzar�a por kAk�� se tiene�
kAxk� �
nX
i��
������
mX
j��
aijxj
������ �
nX
i��
mX
j��
jaij j jxj j
�
mX
j��
�
nX
i��
jaij j
�
jxj j �
�
max
j�������m
nX
i��
jaij j
�
kxk� �
por lo tanto kAk� � maxj�������m
nX
i��
jaij j �
Se mostrar�a� que la igualdad se cumple� en efecto� sea jo tal que�
nX
i��
jaijo j � max
j�������m
nX
i��
jaij j � y x tal que xjo � 
� xi � � si i �� jo�
de esta manera kA xk �






�B	 a�jo���
amjo
CA






�
�
nX
i��
jaijo j k xk� �
Para la k k� se tiene�
kAxk�� � hAx�Axi � xtAtAx�
ahora bien AtA es una matriz sim�etrica de
nida positiva� de donde los
valores propios son reales no negativos� adem�as es posible formar una base de
vectorespropios ortonormales� Sea fe�� � � � � emg una base de vectores propios
ortonormales� entonces x �
mX
i��
�iei y Ax �
mX
i��
i�iei� donde los 
i � � son
los valores propios de A� Por lo tanto� se tiene
kAxk�� �
mX
i��
�i�
�
i � max
i�������m
i
mX
i��
��i � max
i�������m
i kxk� �
Para obtener la igualdad� es su
ciente tomar x � ejo � donde 
jo es el
autovalor m�as grande�
Para la k k� se tiene�
kAxk� � maxi�������n
������
mX
j��
aijxj
������ � maxi�������n
�	 mX
j��
jaij j jxj j
A
� max
i������n
�	 mX
j��
jaij j max
j�������m
jxj j
A �
�	 max
i�������n
mX
j��
jaij j
A kxk� �
as�� kAk� � maxj�������m
mX
j��
jaij j �
II�� Condici�on del Problema lineal ��
Para obtener la igualdad es su
ciente tomar x � �� donde � � �
� � � � � 
�t�
�
La Condici�on de una Matriz
La resoluci�on de un sistema lineal de ecuaciones debe hacer meditar sobre
muchos aspectos relacionados� como ser la existencia de la soluci�on� si el
problema a resolver est�a bien condicionado� conocer una estimaci�on del error
cometido en la soluci�on num�erica� etc� Se tiene inicialmente el sistema de
ecuaciones
Ax � b� donde A �Mn�R�� y b � Rn � �II�
���
el problema es encontrar x � R que sea soluci�on del sistema �II�
���� esta
situaci�on puede escribirse formalmente como
P�A� b� � x�
De esta manera la condici�on del problema est�a dada por��P�A� b��P� A� b���
jP�A� b�j � cond � eps� �II�
���
donde�
 aij � aij�
 � �ij�� j�ij j � eps� �II�
�
��
 bi � bi�
 � �i�� j�ij � eps� �II�
�
���
Si se plantea P� A� b� � x� se tiene kx� xkkxk � cond � eps� Por otro lado�
considerando que solamente normas mon�onotas son utilizadas� se tiene�




�	 a����� � � � a�n�n���� ��� ���
an��n� � � � ann�nn
A





 � eps kAk �
de esta manera

 A�A

 � eps kAk y 

 b� b

 � eps kbk � �II�
�
�
Suponiendo que la matriz sea inversible� se puede enunciar el siguiente
teorema� pero antes una de
nici�on es necesaria�
De�nici�on II������ La condici�on de una matriz A inversible se de
ne como
cond�A� � kAk 

A��

 � �II�
�
��
�� II Sistemas Lineales
Teorema II������ Sea A una matriz con detA �� �� sup�ongase que

 A�A

 � kAk �A� 

 b� b

 � kbk �b� Si �Acond�A� � 
� entonces
k x� xk
kxk �
cond�A�
� �Acond�A� ��A � �b�� �II�
�
��
Si adem�as se tiene �Acond�A� �
�
� � entonces la condici�on del problema
resolver Ax � b es � �cond�A��
Demostraci�on�� Se tiene Ax � b y A x � b� de donde�
Ax� A x � b� b y Ax�A x � Ax� A x � b� b�
A�x � x� � � A�A� x� �b� b�� x� x � A��� A�A� x �A���b� b��
introduciendo las desigualdades en las normas se obtiene�
kx� xk � 

A��



 A�A

 k xk� 

A��

 

 b� b
� 

A��

 �kAk �A �kxk� k x� xk� � kbk �b�
� 

A��

 kAk ��A �kxk� k x� xk� � kxk �b� �
de esta manera
k x� xk
kxk �
cond�A�
� �Acond�A� ��A � �b�� �
Como la condici�on del problema lineal est�a ��ntimamente ligada a la
condici�on de la matriz� es importante conocer algunas de sus propiedades�
dadas por la�
Proposici�on II������ La condici�on de una matriz satisface las siguientes
propiedades
cond�A� � 
� �II�
�
��
cond�I� � 
� �II�
�
��
cond��A� � cond�A�� � � R� �II�
�
��
Demostraci�on�� Veri
caci�on inmediata� �
Ejemplos
�� Q ortogonal� es decir QtQ � I � la condici�on respecto a la norma k k�
esta dada por
cond��Q� � 
� �II�
�
��
��� Sea la matriz A dada por
A �
h
�BBBBB	
� 
 � � � � �
 � 
 � � � �
���
� � �
� � �
���
���
��� � � � 
 � 
� � � � � � 
 �
CCCCCA �
II�� Condici�on del Problema lineal �
entonces kAk� � �h � adem�as A �
�
h
�I �N� donde
N �
�BBB	
� �� � � � � �
�
� �
�
� � � � �
���
� � �
� � � � � � ���
� � � � � �� �
CCCA � kNk� � 
� � 
�
Se deduce que
A�� �
h
�
�I �N��� �
h
�
�I �N �N� �N	 � � � ���

A��
�
� h
�
�
 � kNk� 

N�

� � � ��
� h
�
�
� kNk
�
� h
�
�
entonces cond��A� � �� por lo tanto� la matriz es bien condicionada�
��� El siguiente ejemplo muestra la existencia de una matriz mal condi�
cionada�
Sea H la matriz de n� n� llamada matriz de Hilbert� de
nida por
hij �
i� j � 
 � i� j � 
� � � � � n�
H es una matriz sim�etrica de
nida positiva� motivo por el cual la
condici�on respecto a la norma euclidiana est�a dada por
cond�H �
max
min
�
donde los 
 son valores propios de H � Se puede mostrar que
cond�H � cen� �II�
�
��
Se puede observar claramente que las matrices de Hilbert son mal
condicionadas� inclusive para n bastante peque�no�
��� Finalmente� este ejemplo muestra la existencia de otra matriz mal
condicionada� como ser las matrices de Vandermonde� Sea V la matriz
de n� n de
nida por
V �
�BB	
 
 � � � 
c� c� � � � cn
���
��� � � � ���
cn��� c
n��
� � � � cn��n
CCA �
�� II Sistemas Lineales
donde los ci son diferentes� Se puede mostrar que la cond�V � bn�
donde b � 
�
Ahora bien� la estimaci�on k�x�xkkxk � �cond�A�eps puede ser demasiada
pesimista� para ver esto� consid�erese el siguiente ejemplo��
 
� 
�
��
x
y
�
�
�
�
�
�
Si se llama A a la matriz del sistema� se tiene kAk� � 
�
 y


A��

 	 
� El
sistema con los errores de redondeo incorporados� est�a dado por��
 � �� 
 � ��
� 
�
�
 � �	�
�
�
�
 x
 y
�
� � ��
 � ��� 
 � �� � �
 y � 
�
 � ��
 � �	
� 
��
�
 � �� � �	��
de donde
jy � yj
jyj � �eps�
Calculando x� se tiene
 x �
��
 � ���� �
 � ��� y
 � ��
�
�� 
��
 � ��� � 
��
��� � �� � �	�
 � ��
�
x� ��� � 
��
��� � �� � �	�
 � ��
� x�
 � �eps��
por lo tanto�
jx� xj
jxj � �eps�
El problema es bien condicionado� aunque la matriz A tenga una gran
condici�on� Si se multiplica el sistema de ecuaciones por una matriz diagonal
D se obtiene� el nuevo problema dado por
DAx � Db�
por el teorema II�
��� se tiene
kx� xk
kxk � �cond�DA�eps� si cond�DA�eps �
�
�
En el ejemplo anterior� se plantea
D �
�
 �
� 
��
�
� as�� DA �
�
 
� 
�
�
II�� Condici�on del Problema lineal ��
obteniendo el�
Corolario II����
�� Con las misma hip�otesis del teorema II����� y adem�as
si cond�DA�eps � �� � se tiene
La condici�on del problema � � inf
D diagonal
cond�DA�� �II�
�
��
Ejercicios
�� a� Sea k k de
nida en Rn � La bola unitaria cerrada se de
ne como
 B �
�
x � Rn �� kxk � 
� �
mostrar que la bola unitaria es un conjunto convexo�
b� SeaD un conjunto convexo acotado� en cuyo interior est�a �� Si se supone
que D es equilibrado� es decir si x � D implica que �x � D� Mostrar que
se puede de
nir una norma cuya bola unitaria cerrada sea precisamente
D�
��� �Es la funci�on f�x� � jx� � x�j � jx�j una norma sobre R�� Si lo es� �es
mon�otona� Dibujar la bola unitaria�
��� Dar las condiciones para que una norma sea mon�otona� observando su
bola unitaria cerrada�
��� Para una matriz A se de
ne la norma de Frobenius como
kAkF �
vuut nX
i��
nX
j��
jaij j��
a� Mostrar que kAkF es una norma sobre Rn�n �
b� Veri
car la desigualdad
kAk� � kAkF �
p
n kAk� �
��� Veri
car la desigualdad
max
i�j
jaij j � kAk� � n�maxi�j jaij j �
��� Sea A una matriz con detA �� �� Mostrar que


A��

 � � min
kxk��
kAxk
�
�
�� II Sistemas Lineales
��� Sea R una matriz triangular inversible� Mostrar que�
jriij � kRkp � jriij�� �


R��
p
� para p � 
� ����
Deducir que
condp�R� � max
i�k
jriij
jrkk j �
��� Sea
A �
�BBBBB	
�
�
�
h�
� �
h�
�
� � � � � � � �
�
h�
�
�
�
h�
� �h�
�
�
h�
� � � �
�
� � �
� � �
� � �
���
� � � � � �
hn��
�
�
�
hn��
� �
hn��
�
CCCCCA
la matriz� que se encuentra en la interpolaci�on spline� Mostrar�
a� cond��A� puede ser arbitrariamente grande�
�Si maxhi�minhi �
���
b� Existe una matriz diagonal D tal que cond��DA� � ��
II�� M�etodos Directos
En esta secci�on se desarrollar�a los algoritmos de resoluci�on directa de
sistemas lineales m�as comunes en la actualidad� El problema a resolver es
Ax � b� �II���
�
donde A � Mn�R�� x� b � Rn � Por los resultados obtenidos en la teor��a del
Algebra Lineal� este sistema de ecuaciones lineales tiene una sola soluci�on�
si y solamente si detA �� �� Para mostrar la importancia de contar con
algoritmos cuyo costo en operaciones sea m��nimo� vale la pena dar el siguiente
ejemplo

Continuar navegando