Shared Flashcard Set

Details

Numerical Computation
General Error Analysis, Finite-Precision Computation, Operation Counts
16
Computer Science
Graduate
03/02/2014

Additional Computer Science Flashcards

 


 

Cards

Term
Well-Posed Problems
Definition
A solution exists, is unique, and depends continuously on the problem data
Term
Problems vs. Algorithms
Definition
In order to find an accurate solution, a problem must be well-posed and well-conditioned, and an algorithm must be stable.
Term
Data Error
Definition
The difference between exact function values due to error in input
Term
Computational Error
Definition
Difference between exact and approximate function values for the same input.  Composed of truncation and rounding error.
Term
Truncation Error
Definition
Difference between true result and that produced by a given algorithm using exact arithmetic.
Term
Rounding error
Definition
Difference between the result produced by a given algorithm using exact arithmetic and result produced by same algorithm using finite-precision.
Term
Forward Error
Definition

Discrepency between computed and true values:

 [image]

Term
Backward Error
Definition
The quantity [image] where [image]
Term
Conditioning of a problem
Definition

Effects of propagated data error on the solution of a problem

[image]

Term
Stability of an algorithm
Definition
The effects of computational error on the result computed by an algorithm
Term
Floating-point numbers
Definition
Expressed as a number of moderate size times a power of ten.  Base (usually two), Precision(53), Lower exponent (-1022) and upper exponent (1023).
Term
Rounding Rules
Definition

Round to zero (chop): fl(x) is truncated after the (p-1)st digit, where p is precision

Round to nearest: fl(x) is the nearest floating-point number to x

Term
Machine Precision
Definition

Bounds the relative error in representing any nonzero real number x within the normalized range of a floating-point system

[image]

Term
Floating-point arithmetic
Definition

Adding/Subtracting: Exponents must match, so shifted first.  Trailing digits of smaller number are lost.

Multiplication: exponents are summed and mantissas are multiplied.  Two p-digit mantissas contains up to 2p digits.

Term
Cancellation
Definition
Subtraction between two p-digit numbers having the same sign and similar magnitudes yields a result with fewer than p significant digits; exactly representable; potential serious loss of information
Term
Big O notation
Definition
Describes limiting behavior of a function when the argument tends towards a particular value or infinity.
Supporting users have an ad free experience!