Conte, de Boor - Elementary Numerical Analysis. An Algorithmic Approach (523140), страница 72
Текст из файла (страница 72)
163program, 164Backward error analysis, 9 - 11, 19, 160,179 - 181Base of a number system, l - 4Basis for n-vectors, 140, 141, 196Bessel interpolation, 288Bessel’s function, zeros of, 124 - 125, 127Binary search, 87Binary system, l - 3Binomial coefficient, 57Binomial function, 57, 373Binomial theorem, 58Bisection method, 74 - 75, 8 1 - 84algorithm, 75program, 8 1 - 84Boundary value problems, 406 - 419collocation method for, 416 - 419finite difference methods for,406 - 412second-order equation, 407ff.shooting methods for, 412-416Breakpoints of a piecewise-polynomial function,284, 319Broken-line interpolation, 284 - 285Broyden’s method, 222Central-difference formula, 298, 407Chain rule, 28Characteristic equation:of a difference equation, 350, 391of a differential equation, 348, 392, 394of a matrix, 201Characteristic polynomial of a matrix, 202Chebyshev approximation (see Approximation,uniform)Chebyshev points, 54, 242-244, 3 18Chebyshev polynomials, 32, 239 - 241,255-256, 293, 317, 354nested multiplication for, 258,427428INDEXCholeski’s method, 160, 169Chopping, 8Compact schemes, 160, 169Composite rules for numerical integration,319ff.Condition, 14 - 15Condition number, 175, 177Continuation method, 2 18Convergence:geometric, 22linear, 95order of, 102quadratic, 100ff.of a sequence, 19ff.of a vector sequence, 191, 223Convergence acceleration, 95ff.(See also Extrapolation to the limit)Conversion:binary to decimal, 2, 6, 113decimal to binary, 3, 6Corrected trapezoid rule, 309, 310, 321, 323program, 324Corrector formulas, 379 - 388Adams-Moulton, 382 - 384Milne’s, 385Cramer’s rule, 144, 187Critical point, 209Cubic spline, 289, 302interpolation, 289-293Damped Newton’s method, 219 - 220Damping for convergence encouragement,219Data fitting, 245ff.Decimal system, 1Deflation, 117 - 119, 124, 203for power method, 207Degree of polynomial, 29, 32Descartes’ rule of sign, 110 - 111, 119Descent direction, 213Determinants, 144, 185ff., 201ff.Diagonally dominant (see Matrix)Difference equations, 349ff., 360, 361, 390,391, 392initial value, 351linear, 349Difference operators, 6 1Differential equations, 346ff.basic notions, 346 - 348boundary value problems, 406 - 419Euler’s method, 356ff.initial value problems, 347, 354Differential equations:linear, with constant coefficients, 347 - 349multistep methods, 373ff.Runge-Kutta methods, 362ff.stiff, 401ff.systems of, 398 - 401Taylor’s algorithm, 354 - 359Differential remainder for Taylor’s formula,28Differentiation:numerical, 290, 295 - 303symbolic, 356Direct methods for solving linear systems,147 - 185, 209Discrete Fourier transform, 278Discretization error, 300, 359, 361, 389dist, 236Divided difference, 40, 41ff., 62ff., 79, 236table, 41ff.Double precision, 7, 11, 18accumulation, 396partial, 3%of scalar products, 183DVERK subroutine for differential equations,370 - 372, 400 - 401Eigenvalues, 189ff.program for, 194Eigenvectors, 189, 191, 194complete set of, 1%EISPACK, 422Equivalence of linear systems, 149Error, 12ff.Euler’s formula, 30, 269Euler’s method, 356, 359-362, 373, 379,395Exactness of a rule, 3 11Exponent of a floating-point number, 7Exponential growth, 390, 391Extrapolation, 54Extrapolation to the limit, 333ff..
366, 410algorithm, 338 - 339( See also Aitken’s D2 -process)Factorization of a matrix, 160 - 166, 169, 187,229False position method (see Regula falsi)Fast Fourier transform, 277 - 284program, 281 - 282Finite-difference methods, 406 - 411Fixed point, 88INDEXFixed-point iteration, 79, 88 - 99, 108, 223ff.,381algorithm, 89for linear systems, 224-232algorithm, 227for systems, 223 - 234Floating-point arithmetic, 7ff.Forward difference:formula, 297operator D, 56ff., 373table, 58 - 61Forward-shift operator, 57Fourier coefficients, 269Fourier series, 269ff.Fourier transform:discrete, 278fast, 277-284Fraction:binary, 5decimal, 4Fractional part of a number, 4Fundamental theorem of algebra, 29, 202Gauss elimination, 145, 149ff.algorithm, 152 - 153program, 164 - 166for tridiagonal systems, 153 - 156program, 155Gauss-Seidel iteration, 230 - 232, 234, 412algorithm, 230Gaussian rules for numerical integration,311-319, 325-327Geometric series, 22Gershgorin‘s disks, 200Gradient, 209Gram-Schmidt algorithm, 250Hermite interpolation, 286Hermite polynomials, 256, 318Hessenberg matrix, 197Homogeneous difference equation, 350 - 352Homogeneous differential equation,347 - 348Homogeneous linear system, 135 - 140Homer’s method (see Nested multiplication)Householder reflections, 197Ill-conditioned, 181, 249IMSL (International Mathematical andStatistical Library), 370, 421429Initial-value problem, 347numerical solution of, 354 - 405Inner product (see Scalar product)Instability, 15-17, 117, 376, 385, 389-394,402Integral part of a number, 4Integral remainder for Taylor’s formula,27Integration, 303 - 345composite rules, 309, 319ff.corrected trapezoid rule, 309, 321Gaussian rules, 311 - 3 18program for weights and nodes, 316midpoint rule, 305, 32 1rectangle rule, 305, 320Romberg rule, 340 - 345Simpson’s rule, 307, 321, 385trapezoid rule, 305, 321Intermediate-value theorem for continuousfunctions, 25, 74, 89Interpolating polynomial, 38-71, 295difference formula, 55 - 62error, 51ff.Lagrange formula, 38, 39 - 41Newton formula, 40, 41uniqueness of, 38Interpolation:broken-line, 284 - 285in a function table, 46-50, 55-61global, 293iterated linear, 50by polynomials, 31ff.by trigonometric polynomials,275-276linear, 39local, 293optimal, 276osculatory, 63, 67, 68, 286quadratic, 120, 202, 213-214, 416Interval arithmetic, 18Inverse of a matrix, 133, 166approximate, 225calculation of, 166 - 168program, 167Inverse interpolation, 51Inverse iteration, 193 - 195Iterated linear interpolation, 50Iteration function for fixed-point iteration, 88,223Iteration methods for solving linear systems,144, 209, 223ff.Iterative improvement, 183 - 184, 229algorithm, 183430INDEXJacobi iteration, 226, 229, 234Jacobi polynomials, 3 17Jacobian (matrix), 214, 216, 404Kronecker symbol δij 201Lagrange form, 38Lagrange formula for interpolating polynomial,39, 295, 312Lagrange polynomials, 38, 147, 259, 275, 295Laguerre polynomials, 256, 318Least-squares approximation, 166, 215,247 - 251, 259-267by polynomials, 259ff., 302program, 263 - 264by trigonometric polynomials, 275Lebesque function, 243, 244Legendre polynomials, 255, 259, 260, 315Leibniz formula for divided difference of aproduct, 71Level line, 212Linear combination, 134, 347Linear convergence, 95, 98Linear independence, 140, 347, 417Linear operation, 294Linear system, 128, 136, 144numerical solution of, 147ff.Line search, 213 - 214.
215LINPACK, 422Local discretization error, 355, 359Loss of significance, 12 - 14, 32, 116, 121, 265,300Lower bound for dist236-237, 245Lower-triangular, 13 1Maehly’s method, 119Mantissa of a floating-point number, 7Matrix, 129ff.addition, 133approximate inverse, 225bandtype of banded, 350conjugate transposed, 142dense, 145diagonal, 131diagonally dominant, 184, 201, 217, 225,230, 231.
234, 250, 289equality, 129general properties, 128 - 144Hermitian, 142, 206Hessenberg , 197Householder reflection, 197Matrix:identity, 132inverse, 133, 166 - 168invertible, 132, 152, 168, 178, 185, 188,229multiplication, 130norm, 172null, 134permutation, 143, 186positive definite, 159, 169, 231similar, 196sparse, 145, 231square, 129, 135symmetric, 141, 198, 206trace.
146transpose, 141triangular, 131. 147, 168, 178, 186, 234triangular factorization, 160 - 166tridiagonal. 153 - 156, 168, 188, 198,204 - 206. 217, 230unitary, 197Matrix-updating methods for solving systems ofequations, 22 I- 222Mean-value theorem:for derivatives, 26, 52, 79, 92, 96, 102, 298,360for integrals, 26. 304, 314, 320Midpoint rule, 305composite, 321, 341Milne’s method, 378, 385, 389Minimax approximation (see Approximation,uniform)Minor of a matrix, 188Modified regula falsi, 77, 78, 84-86, 205algorithm, 77program, 84 - 86Müller’s method, 120ff., 202 - 204Multiplicity of a zero, 36Multistep methods, 373ff.Murnaghan-Wrench algorithm, 241Nested form of a polynomial, 33Nested multiplication, 112for Chebyshev polynomials, 258in fast Fourier transform, 279for Newton form, 33, 112for orthogonal polynomials, 257for series, 37Neville’s algorithm, 50Newton backward-difference formula, 62, 373,382Newton form of a polynomial, 32ff.Newton formula for the interpolatingpolynomial, 40 - 41INDEXNewton formula for the interpolatingpolynomial:algorithm for calculation of coefficients, 44program, 45, 68-69Newton forward-difference formula, 57Newton’s method, 79, 100 - 102, 104 - 106,108, 113ff., 241, 244, 404algorithm, 79for finding real zeros of polynomials, 113program, 115for systems, 216-222, 223, 224algorithm, 217damped, 218 - 220modified, 221quasi-, 223Node of a rule, 295Noise, 295Norm, 170ff.Euclidean, 171function, 235matrix, 172max, 171vector, 171Normal equations for least-squares problem,215, 248 - 251, 260Normalized floating-point number, 7Numerical differentiation, 290, 295 - 303Numerical instability (see Instability)Numerical integration (see Integration)Numerical quadrature (see Integration)Octal system, 3One-step methods, 355Optimization, 209ff.Optimum step size:in differentiation, 301in solving differential equations, 366-372,385, 396Order:of convergence, 20 - 24, 102of a root, 36, 109, 110symbol20 - 24, 163, 192, 202, 221,337ff., 353ff., 361, 363 - 365, 367, 390,393symbol o( ), 20 - 24, 98, 334ff.of a trigonometric polynomial, 268Orthogonal functions, 250, 252, 270, 418Orthogonal polynomials, 25lff., 313generation of, 261 - 265Orthogonal projection, 248Osculatory interpolation, 62ff., 308program, 68 - 69Overflow, 8431Parseval‘s relation, 270Partial double precision accumulation, 3%Partial pivoting, 159Permutation, 143Piecewise-cubic interpolation, 285ff.programs, 285, 287, 290Piecewise-parabolic, 293Piecewise-polynomial functions, 284ff., 3 19,418Piecewise-polynomial interpolation, 284ff.Pivotal equation in elimination, 151Pivoting strategy in elimination, 157, 180Polar form of a complex number, 270,277,351Polynomial equations, 110ff.complex roots, 120ff.real roots, 110ff.Polynomial forms:Lagrange, 38nested, 33Newton, 32ff.power, 32shifted power, 32Polynomial interpolation (see Interpolatingpolynomial)Polynomials:algebraic, 31ff.trigonometric, 268ff.PORT, 421Power form of a polynomial, 32Power method, 192 - 196Power spectrum, 271Predictor-corrector methods, 379ff.Propagation of errors, 14, 395Quadratic convergence, 100ff.Quadratic formula, 13 - 14Quotient polynomial, 35QR method, 199-200Rayleigh quotient, 201Real numbers, 24Rectangle rule, 305composite, 320Reduced or deflated polynomial, 117Regula falsi, 76modified (see Modified regula falsi)Relative error, 12Relaxation, 232-233Remez algorithm, 241Residual, 169Rolle’s theorem, 26, 52, 74432INDEXRomberg integration, 340 - 345program, 343 - 344Round-off error, 8in differentiation, 300 - 302in integration, 322propagation of, 9ff., 12ff., 395ff.in solving differential equations, 395 - 398in solving equations, 83, 87, 116 - 117in solving linear systems, 157, 178 - 185Rounding, 8Rule, 295Runge-Kutta methods, 362ff.Fehlberg , 369 - 370order 2, 363-364order 4, 364Verner, 370Sampling frequency, 272Scalar (or inner) product, 142, 143of functions, 251, 270, 273Schur’s theorem, 197, 234Secant method, 78 - 79, 102 - 104, 106 - 109,412algorithm, 78Self-starting, 365, 376Sequence, 20Series summation, 37Shooting methods, 412ff.Significant-digit arithmetic, 18Significant digits, 12Similarity transformation, 196ff.into upper Hessenberg form, 197 - 199algorithm, 199Simpson’s rule, 307, 317, 318, 329-332, 385composite, 320program, 325Simultaneous displacement (see Jacobi iteration)Single precision, 7Smoothing, 271SOR, 231Spectral radius, 228Spectrum:of a matrix (see Eigenvalues)of a periodic function, 271Spline, 289-293Stability (see Instability)Stable:absolutely, 394relatively, 394strongly, 391, 392weakly, 393Steepest descent, 2 1 Off.algorithm, 211Steffensen iteration, 98, 108algorithm, 98Step-size control, 366, 384, 394Sturm sequence, 205Successive displacement (see Gauss-Seideliteration)Successive overrelaxation (SOR), 231Synthetic division by a linear polynomial, 35Tabulated function, 55Taylor polynomial, 37, 63, 64Taylor series, truncated, 27, 32, 100, 336, 353,354, 357, 359, 390for functions of several variables, 29, 216.363, 414Taylor’s algorithm, 354ff., 362, 366Taylor’s formula with (integral) remainder, 27( See also Taylor series, truncated)Termination criterion, 81, 85, 122, 194, 227Three-term recurrence relation, 254Total pivoting, 159Trace of a matrix, 146Trapezoid rule, 272, 305, 317, 340composite, 32 1corrected (see Corrected trapezoid rule)program, 323Triangle inequality, 171, 176Triangular factorization, 160ff.program, 165 - 166Tridiagonal matrix (see Matrix, tridiagonal)Trigonometric polynomial, 268ff.Truncation error (see Discretization error)Two-point boundary value problems, 406ff.Underflow, 8Unit roundoff, 9Unit vector, 135Unstable (see Instability)Upper-triangular, 131, 147 - 149Vandermonde matrix, 147Vector, 129Wagon wheels, 274Waltz, 106Wavelength, 27 1Wronskian, 347Zeitgeist, 432.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
