Scientific computing concerns with the design and analysis of algorithms for solving mathematical problems that arise in science and engineering
Problem Solving Process
Develop a mathematical model
Discretize the model and develop algorithms to solve the equations numerically
Implement and execute the algorithms in computer software.
Interpret and validate the computed results, repeating any or all of the preceding steps, if necessary
Sources of Approximation
Before computation
Mathematical modeling : 즉 모델링 하는 과정에서 근사를 취할 수 있다.
Empirical measurements : 즉 데이터 자체 내에 에러가 존재할 수 있다.
Previous computations : 이전 결과 자체에서 근사가 있을 수 있다.
During computation
Truncation or discretization : 수학적인 근사를 하는 과정에서 발생. 즉 algorithm 자체의 error를 의미한다.
Rounding : 컴퓨팅의 한계로 발생하는 error이다.
Others
Input의 uncertainty로 인해 문제가 가속화될 수 있다. 이를 conditioning problem 이라고 부른다.
input의 perturbation으로 인해 output의 변하는 정도는 모델의 stability와 관련이 있다.
Example
Earth is modeled as a sphere, idealizing its true shape (model simplification)
Value for radius is based on empirical measurements and previous computations (errors in inputs)
Value of π requires truncating infinite process (roundoff error)
Values for input data and results of arithmetic operations are rounded by calculator or computer (roundoff error)
Truncation Error and Rounding Error
Computation error is the sum of truncation error and rounding error. In addition, one of these usually dominates.
Truncation error
Difference between the true result (for actual input) and the result produced by given algorithm using exact arithmetic
Rounding error
Difference between result produced by given algorithm using exact arithmetic and result produced by the same algorithm using limited precision arithmetic
Example
Error in finite difference approximation exhibits tradeoff between rounding error and truncation error
Truncation error bounded by Mh/2
Rounding error bounded by 2ϵ/h, where error in function values bounded by ϵ
Total error minimized when h≈2ϵ/M
→ Error increases for smaller h because of rounding error and increases for larger h because of truncation error
Absolute Error and Relative Error
Absolute error
Approximate value - true value
Relative error
It is equivalent to
Floating-Point Numbers
Floating-point number system characterized by four integers
→ 따라서 Floating-point number system은 다음과 같이 표기될 수 있다.
예를 들어 x∈R는 다음과 같이 표현된다.
where digits dk∈{0,1,…,β−1} with d0=0 (for normalization) and exponent e is an integer such that
Properties
Total number of normalized floating-point numbers is
Smallest positive normalized number
Largest floating-point number
Floating-point numbers equally spaced only between successive powers of β
Not all real numbers are exactly representable; those that are called machine numbers
Numbers in F are symmetric with respect to zero
Example
Machine Epsilon
Definition
The distance between 1 and the smallest machine number larger than 1 is called machine epsilon and is denoted with ϵM. The value of machine epsilon is
Definition
The distance between any machine number x∈F and its consecutive machine number(successor) is called unit in the last place and is denoted with ulp(x)
Hidden Bit
Today’s computers use base 2 to internally represent numbers. Therefore, the only choice of digits that remains for the leading bit d0 is d0=1. This creates an opportunity to save some memory if we avoid occupying the bit d0 with the fixed value of 1. This implicit bit whose value is always 1 for any normalized binary number is called the hidden bit.
Rounding Rules
If real number x is not exactly representable, then it is approximated by nearby floating-point number fl(x):
This process is called rounding, and error introduced is called rounding error or rondoff error
Rounding rules
Assume x=±(d0.d1⋯dp−1dp⋯)β×βe
Chopping
Truncate base-β expansion of x after (p−1)-st digit
Rounding to nearest
fl(x) is the nearest floating-point number to x, using floating-point number whose last stored digit is even in case of tie
where d~p−1 is either dp−1 or dp−1+1
Unit roundoff
Definition
The smallest number δ such that fl(1+δ)>1 is called unit roundoff and is denoted by u, that is
For either chopping or rounding to the nearest we have
which is equivalent to
where ∣δ∣≤u
Subnormal numbers
A relatively large gap between zero and xmin (underflow region)
Therefore, we define the concept of subnormal numbers as follows
Gradual underflow
Let fl(x)=±(0.0⋯0dp−k⋯dp−1)β×βL with dp−k=0 then