%15 Mar 91 \documentstyle{article} \topmargin=-.5in \textwidth 6.0in \textheight 8.5in \oddsidemargin .25in \evensidemargin .25in \begin{document} \title{\bf NUMERICAL ANALYSIS \\ MATHEMATICS OF SCIENTIFIC COMPUTING} \smallskip \author{ David Kincaid and Ward Cheney \\ \copyright 1991 Brooks/Cole Publishing Co.\\ ISBN 0--534--13014--3} \date{March 15, 1991} \maketitle \section*{Introduction} The following table lists files containing sample programs based on the pseudocode given in the textbook cited above. They are intended primarily as a learning and teaching aid for use with this book. We believe that these computer routines are coded in a clear and easy-to-understand style. We have intentionally included few comment statements so that students will read the code and study the algorithms---they can add comments as they decipher them. These programs are usable on computer systems with Fortran 77 compilers, from small personal computers to large scientific computing machines. However, they do not contain all of the ``bells-and-whistles'' of robust state-of-the-art software such as may be found in general-purpose scientific libraries. Nevertheless, they are adequate for many small nonpathological problems. \noindent \section*{Installation and Usage} On a Unix system, unpack the file kincaid-cheney.shar as follows \indent {\tt sh kincaid-cheney.shar} \noindent These programs will run as is on any computer with a standard Fortran 77 compiler. However, the statement {\tt data epsi/1.0e-6/} in some routines should be changed to the machine epsilon (single precision roundoff error) for the computer that is to be used. Compile and execute the program on file romberg.f as follows \indent {\tt f77 romberg.f} \indent {\tt a.out} \section*{Availability} For information on the availability of this software, contact either the publisher of the textbook or the authors at the following addresses. \medskip \begin{center} \begin{tabular}{lcl} Brooks/Cole Publishing Co.& &Center for Numerical Analysis\\ 511 Forest Lodge Road& &University of Texas at Austin\\ Pacific Grove, CA 93950--5098& &Austin, TX 78713--8510\\[0.1in] (408) 373--0728& &(512) 471--1242\\ fax: (408) 375--6414& &fax: (512) 471--9038 \\ &&kincaid@cs.utexas.edu \end{tabular} \end{center} \newpage \begin{center} \begin{tabular}{lrl} {\bf File Name} & {\bf Pages} & {\bf Description of Code\quad (Subprogram Names)} \\[0.1in] {\bf \tt elimit.f} & 10 & Example of a slowly converging sequence \\ {\bf \tt sqrt2.f} & 10 & Example of a rapidly converging sequence \\ {\bf \tt nest.f} & 14 & Nested multiplication \\[0.1in] {\bf \tt epsi.f} & 36 & Approximate value of machine precision \\ {\bf \tt depsi.f} & 36 & Approximate value of double precision machine precision \\ {\bf \tt ex2s22.f} & 43--44 & Loss of significance \\ {\bf \tt unstab1.f} & 49 & Example of an unstable sequence \\ {\bf \tt unstab2.f} & 50 & Example of another unstable sequence \\ {\bf \tt instab.f} & 50 & Example of numerical instability \\[0.1in] {\bf \tt ex1s31.f} & 58--59 & Bisection method to find root of $\exp(x)=\sin x$ \quad({\bf bisect}) \\ {\bf \tt ex1s32.f} & 65 & Newton's method example \\ {\bf \tt ex2s32.f} & 68 & Simple Newton's method \\ {\bf \tt ex3s32.f} & 69--70 & Implicit function example \\ {\bf \tt ex1s33.f} & 76 & Secant method example \quad ({\bf f\,}) \\ {\bf \tt ex3s34.f} & 83--84 & Contractive mapping example \\ {\bf \tt ex3s35.f} & 93 & Horner's method example \\ {\bf \tt ex6s35.f} & 94 & Newton's method on a given polynomial \quad({\bf horner}) \\ {\bf \tt ex7s35.f} & 99 & Bairstow's method example \\ {\bf \tt laguerre.f} & 102 & Laguerre's method example \\[0.1in] {\bf \tt forsub.f} & 127 & Forward substitution example \\ {\bf \tt bacsub.f} & 127 & Backward substitution example \\ {\bf \tt pforsub.f} & 128 & Forward substitution for a permuted system \\ {\bf \tt pbacsub.f} & 128 & Backward substitution for a permuted system \\ {\bf \tt genlu.f} & 130 & General LU-factorization example \\ {\bf \tt doolt.f} & 131 & Doolittle's-factorization example \\ {\bf \tt cholsky.f} & 134 & Cholesky-factorization example\\ {\bf \tt bgauss.f} & 143 & Basic Gaussian elimination \\ {\bf \tt pbgauss.f} & 145 & Basic Gaussian elimination with pivoting \\ {\bf \tt gauss.f} & 148 & Gaussian elimination with scaled row pivoting \\ {\bf \tt paxeb.f} & 150 & Solves $Lz=Pb$ and then $Ux=z$ \quad ({\bf gauss}) \\ {\bf \tt yaec.f} & 151 & Solves $U^{T}z=c$ and then $L^{T}Py=z$ \quad ({\bf gauss}) \\ {\bf \tt tri.f} & 155 & Tridiagonal system solver \quad ({\bf tri}) \\ {\bf \tt ex1s45.f} & 173 & Neumann series example \quad ({\bf setI, mult, store, add, prt}) \\ {\bf \tt ex2s45.f} & 175 & Gaussian elimination followed by iterative improvement\\ && \qquad ({\bf residual, gauss, solve}) \\ {\bf \tt ex1s46.f} & 182 & Example of Jacobi and Gauss-Seidel methods \\ {\bf \tt ex2s46.f} & 184 & Richardson method example (with scaling) \\ {\bf \tt jacobi.f} & 186 & Jacobi method example (with scaling) \\ {\bf \tt ex3s46.f} & 190 & Gauss-Seidel method (with scaling)\\ {\bf \tt ex6s46.f} & 200 & Chebyshev acceleration example \quad ({\bf extrap, cheb, vnorm}) \\ {\bf \tt steepd.f} & 207 & Steepest descent method example \quad ({\bf prod, mult}) \\ {\bf \tt cg.f} & 211 & Conjugate gradient method \quad ({\bf prod, residual, mult}) \\ {\bf \tt pcg.f} & 217 & Jacobi preconditioned conjugate gradient method\\ & & \qquad ({\bf prod, residual, mult}) \end{tabular} \end{center} \newpage \begin{center} \begin{tabular}{lrl} {\bf File Name} & {\bf Pages} & {\bf Description of Code \quad (Subprogram Names)} \quad (continued)\\[0.1in] {\bf \tt ex1s51.f} & 231 & Power method example \quad ({\bf dot, prod, store, norm, normal}) \\ {\bf \tt poweracc.f} & 231 & Power method with Aitken acceleration\\ & &\qquad ({\bf dot, prod, store, norm, normal}) \\ {\bf \tt ex2s51.f} & 233 & Inverse power method example \\ & &\qquad ({\bf gauss, dot, prod, store, norm, normal, solve)} \\ {\bf \tt ipoweracc.f} & 233 & Inverse power method with Aitken acceleration \\ & & \qquad ({\bf gauss, dot, prod, store, norm, normal, solve}) \\ {\bf \tt ex1s52.f} & 239 & Schur factorization example \quad ({\bf prtmtx, mult}) \\ {\bf \tt qrshif.f} & 248 & Modified Gram-Schmidt example \quad ({\bf prtmtx, mgs, mult}) \\ {\bf \tt ex1s53.f} & 253--255 & QR-factorization using Householder transformations \\ & &\qquad ({\bf QRfac, setoI, prtmtx, UtimesA, findV, prod,}\\ & &\qquad {\bf formU, formW, trans, mult}) \\ {\bf \tt ex2s55.f} & 272--273 & QR-factorization example \\ & &\qquad ({\bf QRfac, setoI, prtmtx, UtimesA, findV, prod, } \\ & &\qquad {\bf formU, formW, trans, mult, copy, scale}) \\ {\bf \tt ex3s55.f} & 274 & Shifted QR-factorization example \\ & &\qquad ({\bf submtx, shiftA, unshiftA, hess, QRfac, setoI, }\\ & &\qquad {\bf prtmtx, UtimesA, findU, findV, prod, formU, }\\ & &\qquad {\bf formW, Trans, mult, copy, scale}) \\[0.1in] {\bf \tt coef.f} & 280--281 & Coefficients in the Newton form of a polynomial \\ {\bf \tt fft.f} & 419 & Fast Fourier transform example \quad ({\bf f\,}) \\ {\bf \tt adapta.f} & 426--428 & Adaptive approximation example \quad ({\bf f, max}) \\[0.1in] {\bf \tt ex1s71.f} & 431--432 & Derivative approximations: forward difference formula \\ {\bf \tt ex2s71.f} & 434 & Derivative approximation: central difference \\ {\bf \tt ex5s71.f} & 437--438 & Derivative approximation: Richardson extrapolation \\ {\bf \tt ex6s71.f} & 440--441 & Richardson extrapolation \\ {\bf \tt gauss5.f} & 459 & Gaussian five-point quadrature example \\ {\bf \tt romberg.f} & 468 & Romberg extrapolation \\ {\bf \tt adapt.f} & 475 & Adaptive quadrature \\[0.1in] {\bf \tt taylor.f} & 492 & Taylor-series method \\ {\bf \tt rk4.f} & 501--502 & Runge-Kutta method \quad ({\bf f, u}) \\ {\bf \tt rkfelberg.f} & 503--505 & Runge-Kutta-Fehlberg method \quad ({\bf f\,}) \\ {\bf \tt taysys.f} & 526--527 & Taylor series for systems \\[0.1in] {\bf \tt exs91.f} & 576 & Boundary value problem (BVP): Explicit method example\\ & & \qquad ({\bf a, b, vnorm}) \\ {\bf \tt exs92.f} & 582 & BVP: Implicit method example \quad ({\bf tri, unorm}) \\ {\bf \tt exs93.f} & 589 & Finite difference method \quad ({\bf g\,}) \\ {\bf \tt ex3s96.f} & 613 & BVP: Method of characteristics \quad ({\bf f, g, df, tu}) \\ {\bf \tt mgrid1.f} & 624 & Multigrid method example \quad ({\bf vnorm}) \\ {\bf \tt exs98.f} & 625 & Damping of errors \\ {\bf \tt mgrid2.f} & 630 & Multigrid method V-cycle \quad ({\bf vnorm}) \\[0.1in] {\bf \tt code-info.tex}&&This \LaTeX\ file\\ {\bf \tt code-info.tty}&&This tty file \end{tabular} \end{center} \end{document}