Descarga la aplicación para disfrutar aún más
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
Compartir