Numerical Analysis - preliminaries - Hanyang University Jong-Il Park

Numerical Analysis란? Analytic하게 풀 수 없는 문제를 해결하고자 하는 접근방법 eg. 비선형방정식… 특수함수의 값을 계산하는데 이용   eg. Taylor series를 이용한 삼각함수의 계산… 컴퓨터를 사용하여 과학적 문제의 해를 구하고자 하는 방법 eg. 전자장 해석, 모든 공학적 최적화 문제…

본 강의의 목표 및 범위 계산알고리듬 자체가 중요한 것이 아니라, 어떠한 문제가 주어졌을 때, 어떤 방법으로 해를 구할 것인가에 대한 근본적인 사고능력을 중요시 함.           본 강의의 지향하는 바 수치계산 알고리듬의 디자인  계산학의 문제 수치계산 패키지의 단순한 이용  평범한 사용자, 과학자/공학자 해당 ☞ 양자의 중간을 지향. 자신의 문제해결에 즉 자신이 작성한 프로그램에 필요한 루틴을 링크시켜 사용할 수 있도록 함. 범위: 선형방정식의 해법, 소팅, 함수의 극대화/극소화, Fourier변환, 데이터 모델링, 미분방정식, DSP 등

강의 진행 방법 알고리즘을 사용하여 실제 문제를 해결하는 연습을 반복. 프로그래밍 숙제 및 문제풀기 과제가 많음 Numerical Recipes in C의 루틴을 자유로이 사용할 수 있도록 함. (필요 루틴을 course webpage를 통해 제공 ) MATLAB, Mathematica, Maple 등의 사용법은 각자 필요할 때 학습하기 바람

교재 및 참고문헌 [1] S.C. Chapra and R.P. Canale, Numerical Methods for Engineers, 6th ed., McGraw-Hill, 2011. [2] W.Press, S.Teukolski, W.Vetterling, and B.Flannery, Numerical Recipes in C, 2nd edition, Cambridge University Press, 1992. (Free Download: http://www.nrbook.com/a/bookcpdf.html) 참고문헌 <1> 이관수, 공학도를 위한 수치해석, 원화, 1999. <2> S.C. Chapra, Applied Numerical Methods with MATLAB, 2nd ed., McGraw-Hill, 2008. <3> J.D.Faires and R.Burden, Numerical Methods, 3rd ed., Thomson, 2003.

수치해법의 필요성 1. 주어진 문제의 해를 해석적으로 구할 수 없을 때 2. 비용절약:시뮬레이션은 실험적 연구에 비해 비용과 시간을 절감 3. 상업용 프로그램을 효율적으로 사용하기 위한 기초 이론지식 4. 주어진 문제가 상업용 프로그램으로 해결하기 어려울 때 5. 상업용 프로그램이 너무 비싸서 구입이 용이하지 않을 때 6. 컴퓨터 사용법을 배우는 좋은 교육 도구 7. 고차원의 애매한 문제를 분명히 함  문제 이해를 도움 ※수치해법 의존의 폐해 일단 프로그램을 짜서, 돌리고 나서 생각하는 경향  사고력의 저하

Engineering Problem Solving

Overview of the topics(I)

Overview of the topics(II)

Overview of the topics(III) +Sorting +DSP (FFT, convolution, etc.)

컴퓨터의 수 표현 Finite number of bits for representing a number floating point representation s: sign bit M: exact positive integer mantissa(가수) B: base(보통 2 또는 16) e: exact integer exponent E: bias of the exponent(기계별 고정상수)

IEEE Binary Floating Point Arithmetic Standard 754 - 1985 Eg. Double precision real numbers (64 bits) c: 11 bit exponent( 0 ~ 211-1) f: 52 bit binary fraction 0 10000000011 1011100100010000000000000000000000000000000000000000 c f

Eg. 64 bit floating point number 0 10000000011 1011100100010000000000000000000000000000000000000000 c f

Accuracy, range… Accuracy Smallest number Largest number 27.56640625 represents the interval Smallest number Largest number Underflow: when smaller than the smallest number Generally set to 0 Overflow: when larger than the largest number Generally cause the computation to stop

Machine Accuracy Def. The smallest floating-point number which, when added to the floating-point number 1.0, produces a floating-point result different from 1.0                          (m=# of bit for mantissa) eg. typical machines with b=2 and a 32-bit word length ~ 10-8 .

Homework #1 [Due: 9/12] Programming: Obtain the machine accuracy of “float” and “double” of your computer in two ways. Method 1: Use the routine machar() in NR in C (Modification is required for “double”) Method 2: Use your own code, get_eps(), which is based on finding minimum n that satisfies 1+2-n=1

Accuracy and Precision

Roundoff error machine accuracy로 인한 오차 Chopping(버림) Symmetric rounding(반올림) 주의: roundoff error는 기계가 표현할 수 있는 가장 작은 수와 다름

Roundoff error를 최소화하는 법 십진수로 입력되는 자료를 계산기가 저장할 수 있는 만큼 유효숫자로 반올림하여 입력할 것 오버플로우나 언더플로우의 가능성을 줄이기 위해 중간 계산값이 ±1에 근접하게 할 것 확산마무리 오차의 누적을 최소화하기 위해 연산수를 최소화할 것. 예) 괄호곱셈법 유효숫자 상실을 막을 것 비슷한 숫자간의 뺄셈을 없애기 작은 수부터 연산을 시작할 것 배정밀도를 사용

유효숫자 상실 Eg. F(x)=x(sqrt(x+1)-sqrt(x)) 를 x=100에서 6s 인 컴퓨터로 계산한다. 참값 F(100)=4.98756 방법1: 직접 계산 sqrt(x+1)=10.0498, sqrt(x)=10.0000 x(sqrt(x+1)-sqrt(x))=100(10.0498-10.0000)=4.98000 Error=0.00756 방법 2: 식을 변형 F(x)= x/(sqrt(x+1)+sqrt(x)) =4.98758 Error=0.00002 유효숫자 상실 0.0498  3s

Truncation error 정확한 해와 실제 계산기를 사용하여 얻은 해와의 차이 수치계산시 근사식을 사용함으로써 발생 이를 줄이는 것이 수치해석의 목표 Round-off error는 어쩔 수 없지만 truncation error는 프로그램에 달려있음          

Taylor series

Approximation

Approximation of the 1st derivative Forward difference Backward difference Centered difference

Error의 종류 Absolute error: Et = (참값-근사값) Relative error: et =(참값-근사값)/참값 Approximate relative error : ea =(근사참값-근사값)/근사참값 Stopping condition in iterative algorithms: Terminate computation when ea < es where es is the desired relative error

Data errors data error data relative error relative error of x Ignoring higher order terms of Taylor series

Error propagation Single variable function Multivariable function

Condition number if condition number < 1  error reduction if condition number >> 1  ill-conditioned

Total error Total error = roundoff error + truncation error Trade-off Interval h

Homework #2 Read Chapter 1, Numerical Recipes in C, and summarize [Due: 9/19] Read Chapter 1, Numerical Recipes in C, and summarize how to use pointers for memory allocation how to use pointer to function Solve the problems: 3.6, 3.7, 4.2, 4.5, 4.12