NUMERICAL ANALYSIS MATHEMATICS OF SCIENTIFIC COMPUTING David Kincaid and Ward Cheney (c)1991 Brooks/Cole Publishing Co. ISBN 0-534-13014-3 March 15, 1991 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. Installation and Usage: On a Unix system, unpack the file kincaid-cheney.shar as follows sh kincaid-cheney.shar These programs will run as is on any computer with a standard Fortran 77 compiler. However, the statement 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 f77 romberg.f a.out Availability: For information on the availability of this software, contact either the publisher or the textbook or the authors at the following addresses. 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 (408) 373-0728 (512) 471-1242 fax: (408) 375-6414 fax: (512) 471-9038 kincaid@cs.utexas.edu 1 File Name Pages Description of Code (Subprogram Names) elimit.f 10 Example of a slowly converging sequence sqrt2.f 10 Example of a rapidly converging sequence nest.f 14 Nested multiplication epsi.f 36 Approximate value of machine precision depsi.f 36 Approximate value of double precision machine precision ex2s22.f 43-44 Loss of significance unstab1.f 49 Example of an unstable sequence unstab2.f 50 Example of another unstable sequence instab.f 50 Example of numerical instability ex1s31.f 58-59 Bisection method to find root of exp(x) = sinx (bisect) ex1s32.f 65 Newton's method example ex2s32.f 68 Simple Newton's method ex3s32.f 69-70 Implicit function example ex1s33.f 76 Secant method example (f ) ex3s34.f 83-84 Contractive mapping example ex3s35.f 93 Horner's method example ex6s35.f 94 Newton's method on a given polynomial (horner) ex7s35.f 99 Bairstow's method example laguerre.f 102 Laguerre's method example forsub.f 127 Forward substitution example bacsub.f 127 Backward substitution example pforsub.f 128 Forward substitution for a permuted system pbacsub.f 128 Backward substitution for a permuted system genlu.f 130 General LU-factorization example doolt.f 131 Doolittle's-factorization example cholsky.f 134 Cholesky-factorization example bgauss.f 143 Basic Gaussian elimination pbgauss.f 145 Basic Gaussian elimination with pivoting gauss.f 148 Gaussian elimination with scaled row pivoting paxeb.f 150 Solves Lz = Pb and then Ux = z (gauss) yaec.f 151 Solves UT z = c and then LTPy = z (gauss) tri.f 155 Tridiagonal system solver (tri) ex1s45.f 173 Neumann series example (setI, mult, store, add, prt) ex2s45.f 175 Gaussian elimination followed by iterative improvement (residual, gauss, solve) ex1s46.f 182 Example of Jacobi and Gauss-Seidel methods ex2s46.f 184 Richardson method example (with scaling) jacobi.f 186 Jacobi method example (with scaling) ex3s46.f 190 Gauss-Seidel method (with scaling) ex6s46.f 200 Chebyshev acceleration example (extrap, cheb, vnorm) steepd.f 207 Steepest descent method example (prod, mult) cg.f 211 Conjugate gradient method (prod, residual, mult) pcg.f 217 Jacobi preconditioned conjugate gradient method (prod, residual, mult) 2 File Name Pages Description of Code (Subprogram Names) (continued) ex1s51.f 231 Power method example (dot, prod, store, norm, normal) poweracc.f 231 Power method with Aitken acceleration (dot, prod, store, norm, normal) ex2s51.f 233 Inverse power method example (gauss, dot, prod, store, norm, normal, solve) ipoweracc.f 233 Inverse power method with Aitken acceleration (gauss, dot, prod, store, norm, normal, solve) ex1s52.f 239 Schur factorization example (prtmtx, mult) qrshif.f 248 Modified Gram-Schmidt example (prtmtx, mgs, mult) ex1s53.f 253-255 QR-factorization using Householder transformations (QRfac, setoI, prtmtx, UtimesA, findV, prod, formU, formW, trans, mult) ex2s55.f 272-273 QR-factorization example (QRfac, setoI, prtmtx, UtimesA, findV, prod, formU, formW, trans, mult, copy, scale) ex3s55.f 274 Shifted QR-factorization example (submtx, shiftA, unshiftA, hess, QRfac, setoI, prtmtx, UtimesA, findU, findV, prod, formU, formW, Trans, mult, copy, scale) coef.f 280-281 Coefficients in the Newton form of a polynomial fft.f 419 Fast Fourier transform example (f ) adapta.f 426-428 Adaptive approximation example (f, max) ex1s71.f 431-432 Derivative approximations: forward difference formula ex2s71.f 434 Derivative approximation: central difference ex5s71.f 437-438 Derivative approximation: Richardson extrapolation ex6s71.f 440-441 Richardson extrapolation gauss5.f 459 Gaussian five-point quadrature example romberg.f 468 Romberg extrapolation adapt.f 475 Adaptive quadrature taylor.f 492 Taylor-series method rk4.f 501-502 Runge-Kutta method (f, u) rkfelberg.f 503-505 Runge-Kutta-Fehlberg method (f ) taysys.f 526-527 Taylor series for systems exs91.f 576 Boundary value problem (BVP): Explicit method example (a, b, vnorm) exs92.f 582 BVP: Implicit method example (tri, unorm) exs93.f 589 Finite difference method (g ) ex3s96.f 613 BVP: Method of characteristics (f, g, df, tu) mgrid1.f 624 Multigrid method example (vnorm) exs98.f 625 Damping of errors mgrid2.f 630 Multigrid method V-cycle (vnorm) code-info.tex This LaTeX file code-info.tty This tty file 3