1. Fundamentals of Computing
- -
What is scientific computing?
![](https://blog.kakaocdn.net/dn/3LlEz/btssTe4PJcD/4XXRB51DIVk1eI1C1OBbNK/img.png)
Scientific computing concerns with the design and analysis of algorithms for solving mathematical problems that arise in science and engineering
Problem Solving Process
![](https://blog.kakaocdn.net/dn/t5pDI/btssUKPsELs/RnV0gMkubwRr2ZBuKYmqJK/img.png)
- Develop a mathematical model
- Discretize the model and develop algorithms to solve the equations numerically💡만약 우리가 특정 함수를 taylor 근사를 통해서 접근한다고 했을 때, 특정한 항까지만 고려한 경우 discretize했다고 볼 수 있다. 그래야 컴퓨터를 통해서 계산할 수 있기 때문이다.
- 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
)
![](https://blog.kakaocdn.net/dn/cU00Y2/btssPvzhwIK/3tmcNU5lc4dLApRzVgOen1/img.png)
- Value for radius is based on empirical measurements and previous computations (
errors in inputs
)r≈6371km
- Value of π requires truncating infinite process (
roundoff error
)
![](https://blog.kakaocdn.net/dn/psns6/btssUMGtM8A/dOo5czvSLYaKYAPGXxY2r0/img.png)
- Values for input data and results of arithmetic operations are rounded by calculator or computer (
roundoff error
)A≈4×3.14159×(6371)2≈5.10064×108km2
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
finite
oneRounding error
Difference between result produced by given algorithm using exact arithmetic and result produced by the same algorithm using limited precision arithmetic
chopped
) to a certain number of digitsExample
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
![](https://blog.kakaocdn.net/dn/bgoyfm/btssPvF1VLq/3DwGpkAOgcpXoME1P7FlDK/img.png)
Absolute Error and Relative Error
Absolute error
Approximate value - true value
Relative error
It is equivalent to
estimate error
를 구하거나 bound error
를 구한다.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 is2(β−1)βp−1(U−L+1)+1
- Smallest positive normalized numberxmin=βL
- Largest floating-point numberxmax=βU+1(1−β−p)💡제일 작은 숫자 단위가 β−(p−1)이다. 1은 βU에 붙었다고 생각해주면 된다. 해당 숫자를 더해주게 되면 βU+1이 되면서 자릿수가 증가하기 때문에, 저 숫자가 최대라고 할 수 있다.
- Floating-point numbers equally spaced only between successive powers of β💡당연히 단위는 βe만큼 동간격으로 떨어지게 된다.
- Not all real numbers are exactly representable; those that are called
machine numbers
💡앞에서 설명한 것처럼 컴퓨터는 bit의 한계 때문에 round-off를 반드시 수행해야 한다. 이 과정을 통해 나타낼 수 있는 숫자들을machine number
라고 하는 것이다.
- Numbers in F are
symmetric
with respect to zero💡Computer Architecture에서 배운 것처럼 sign-bit를 차용하기 때문이라고 이해하면 될 듯 싶다.
Example
![](https://blog.kakaocdn.net/dn/C7gIY/btssVOc1fZB/kTkoc3lnjWa9ukk1Sh4uZk/img.png)
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
![](https://blog.kakaocdn.net/dn/vZaQM/btssTsoeS5k/T43SkGV3L8sD1tWLz9qFLk/img.png)
Gradual underflow
Let fl(x)=±(0.0⋯0dp−k⋯dp−1)β×βL with dp−k=0 then
소중한 공감 감사합니다