Lecture Note 1:Introduction,calculus review and computer representation of numbers Xiaoqun Zhang Shanghai Jiao Tong University Last updated:September 17,2012
Lecture Note 1: Introduction, calculus review and computer representation of numbers Xiaoqun Zhang Shanghai Jiao Tong University Last updated: September 17, 2012
Lecture note 1 Numerical Analysis 1.1 Course descrioption What is numerical methods? Numerical methods is the study of algorithms for the problems of continuous math- ematics. 1.Topic covered in this course: Solutions of one variation nonlinear equations: Given f,find p such that f(p)=0. Computation error analysis Interpolation and curve fitting: given (xo,y0),(1,y),..,(In,yn),find a polynomial passing through these points. Numerical differentiation and integration: 张，，f)dr Solve linear equations: Solve for Ax=b with A being a large size matrix.Gaussian elimination etc. 2.Not covered in this course: Solutions of Partial/Ordinary differential equations ●Optimization ·Approximation Many more...(Eigenvalue problems,evaluation of matrix functions,etc.) Why numerical methods? Many problems have no analytical solution. Example:3x-e =0. Numerical methods can handle large scale problems. Example:System of linear equations Ax =b,where A is n x n and b,r are n x 1.Analytical solution (Cramer's rule).zi=det(Ai)/det(A).In the computation of det(A;),we need sums over all permutations of the numbers {1,2,...,n}.Operation n!.(factorial of n.)1GHz computer,n =60,we need more than60/10°/(3600*24*365)≈2.63×1064 years! However,using Gaussian elimination,O(n).Much much less than 1 seconds. The arithmetic in computer is finite-digital.Many numbers cannot be repre- sented EXACTLY in computer. Example:Arithmetic in mathematics(√②)2=2.Computer√2=l.4l4 (4-digits)and (1.414)22. 2
Lecture note 1 Numerical Analysis 1.1 Course descrioption What is numerical methods? Numerical methods is the study of algorithms for the problems of continuous mathematics. 1. Topic covered in this course: • Solutions of one variation nonlinear equations: Given f, find p such that f(p) = 0. • Computation error analysis • Interpolation and curve fitting: given (x0, y0),(x1, y1), · · · ,(xn, yn), find a polynomial passing through these points. • Numerical differentiation and integration: df dx, d 2 f dx2 , R b a f(x)dx • Solve linear equations: Solve for Ax = b with A being a large size matrix. Gaussian elimination etc. 2. Not covered in this course: • Solutions of Partial/Ordinary differential equations • Optimization • Approximation • Many more...(Eigenvalue problems, evaluation of matrix functions, etc.) Why numerical methods? • Many problems have no analytical solution. Example: 3x − e x = 0. • Numerical methods can handle large scale problems. Example: System of linear equations Ax = b, where A is n × n and b, x are n × 1. Analytical solution (Cramer’s rule). xi = det(Ai)/ det(A). In the computation of det(Ai), we need sums over all permutations of the numbers {1, 2, ..., n}. Operation > n!.(factorial of n.) 1GHz computer, n = 60, we need more than 60!/109/(3600 ∗ 24 ∗ 365) ≈ 2.63 × 1064 years! However, using Gaussian elimination, O(n 3 ). Much much less than 1 seconds. • The arithmetic in computer is finite-digital. Many numbers cannot be represented EXACTLY in computer. Example: Arithmetic in mathematics (√ 2)2 = 2. Computer √ 2 = 1.414 (4-digits) and (1.414)2 6= 2. 2
Lecture note 1 Numerical Analysis Computer cannot operate on functions directly. Example:What is the integral ofedt. 。Many more.… 1.2 Calculus Review In the following,we assume f is a function defined on a set X of real numbers. 1.2.1 Some definitions Definition 1 (Limit)f has the limit L at ro,written lim f(x)=L I-T0 if,given any real number e>0,there erists a real number o>0 such that lf(x)-L<e,whenever x∈Xand‖x-xol<6. Definition 2(Continuous)f is continuous at ro if lim f(x)=f(xo). Remarks: We say f is continuous on the set X if it is continuous at each number in X. The limit of a sequence is defined in a similar manner. f is continuous at to If {In}is any sequence in X converging to ro,then limn→of(xn)=f(xo. Definition 3(Derivative)If f is defined in an open interval containing ro.f is differentiable at ro if f'(xo）=lim f()-f(xo) x→x0工-T0 erists.The number f'(ro)is called the derivative of f at ro. Remarks: f is differentiable on X if f is differentiable at each number in X. Geometrically,the derivative of f at zo is the slope of the tangent line to the graph at f at (ro,f(ro)). If the function f is differentiable at zo,then f is continuous at xo
Lecture note 1 Numerical Analysis • Computer cannot operate on functions directly. Example: What is the integral of R x −∞ e −t 2 dt. • Many more... 1.2 Calculus Review In the following, we assume f is a function defined on a set X of real numbers. 1.2.1 Some definitions Definition 1 (Limit) f has the limit L at x0, written limx→x0 f(x) = L if, given any real number ǫ > 0, there exists a real number δ > 0 such that kf(x) − Lk < ǫ, whenever x ∈ X and kx − x0k < δ. Definition 2 (Continuous) f is continuous at x0 if limx→x0 f(x) = f(x0). Remarks: • We say f is continuous on the set X if it is continuous at each number in X. • The limit of a sequence is defined in a similar manner. • f is continuous at x0 ⇔ If {xn} is any sequence in X converging to x0, then limn→∞ f(xn) = f(x0). Definition 3 (Derivative) If f is defined in an open interval containing x0. f is differentiable at x0 if f ′ (x0) = limx→x0 f(x) − f(x0) x − x0 exists. The number f ′ (x0) is called the derivative of f at x0. Remarks: • f is differentiable on X if f is differentiable at each number in X. • Geometrically, the derivative of f at x0 is the slope of the tangent line to the graph at f at (x0, f(x0)). • If the function f is differentiable at x0, then f is continuous at x0. 3
Lecture note 1 Numerical Analysis Note:all the functions we will consider when discussing numerical methods will be assumed to be continuous since this is a minimal requirement for predictable be- havior.More sophisticated assumptions about a function generally lead to better approximation results.For example,smooth function,such as differentiable func- tions,will normally behave more predictable than on numerous jagged features. Notations: C(X)denotes the set of all functions that are continuous on X.For example C(a,b),Cla,b] Cn(X)denotes the set of all functions that have n continuous derivatives on X.For example C"(a,b),Cn[a,b].The set of functions that have derivatives of all orders on X is denoted C().Polynomial,rational,trigonometric, exponential,and logarithmic functions are in C(X). .Given a function f on X,f(X)denotes the set of all the number f(r)for xEX.For example f([a,b]). 1.2.2 Important theorems Theorem 1 (Rolle's Theorem)Suppose f Cla,b and f is differentiable on (a,b).If f(a)=f(b),then a number c in (a,b)erists with f'(c)=0. See Figure 1.1. '(c=0 v=f(r) f(a)=f(b) Figure 1.1:Rolle's Theorem Theorem 2 (Mean Value Theorem)Suppose f is differentiable on (a,B).Let a,b be two distinct points in (a,B).Then there exists a pointE(a,b),such that f')=f)-fa) b-a that is f(b)=f(a)+f'()(b-a). 4
Lecture note 1 Numerical Analysis Note: all the functions we will consider when discussing numerical methods will be assumed to be continuous since this is a minimal requirement for predictable behavior. More sophisticated assumptions about a function generally lead to better approximation results. For example, smooth function, such as differentiable functions, will normally behave more predictable than on numerous jagged features. Notations: • C(X) denotes the set of all functions that are continuous on X. For example C(a, b), C[a, b] • C n(X) denotes the set of all functions that have n continuous derivatives on X. For example C n(a, b), Cn[a, b]. The set of functions that have derivatives of all orders on X is denoted C∞(X). Polynomial, rational, trigonometric, exponential, and logarithmic functions are in C∞(X). • Given a function f on X, f(X) denotes the set of all the number f(x) for x ∈ X. For example f([a, b]). 1.2.2 Important theorems Theorem 1 (Rolle’s Theorem) Suppose f ∈ C[a, b] and f is differentiable on (a, b). If f(a) = f(b), then a number c in (a, b) exists with f ′ (c) = 0. See Figure 1.1. f ′ (c) = 0 b b f(a) = f(b) a c b y = f(x) x y Figure 1.1: Rolle’s Theorem Theorem 2 (Mean Value Theorem) Suppose f is differentiable on (α, β). Let a, b be two distinct points in (α, β). Then there exists a point ξ ∈ (a, b), such that f ′ (ξ) = f(b) − f(a) b − a that is f(b) = f(a) + f ′ (ξ)(b − a). 4
Lecture note 1 Numerical Analysis f(r) Slope) Slope Figure 1.2:Mean value Theorem Figure 1.3:Extreme value theorem See figure 1.2. Example:Let f(x)=xsin(x)-(x-2)Inx show that f'(x)=0 at least on [1,2]Since f(1)=0 and f(2)=0,thus there exists c such that f'(c)=0. Theorem 3(Extreme Value Theorem)Suppose f ECla,b],then there erists two points E,2∈[a,bl,such that f()≤f(x)≤f(ξ2)forx∈[a,.In addition, if f is differentiable on [a,b],then E,2 occur either at the endpoints of a,bl or where f'is zero. Theorem 4(Intermediate Value Theorem)Suppose f E Cla,b]and K is any number between f(a),f(b),then there exists a numbergE(a,b)for which f()=K. Example:Let f(x)=x-e-z For f(0)=-1,f(1)=1-1>0,then there exists c such that f(c)=0. Theorem 5(Taylor's theorem)Suppose fCn[a,b]that fn+1 erists on [a,b], and ro E [a,b],there erists a number E(r)between ro and r with f(r)=Pn(x)+
Lecture note 1 Numerical Analysis b b a c b y = f(x) b Slope f ′ (c) Slope f(b)−f(a) b−a x y Figure 1.2: Mean value Theorem b b a ξ2 b y = f(x) x y ξ1 Figure 1.3: Extreme value theorem See figure 1.2. Example: Let f(x) = x sin(πx) − (x − 2) ln x show that f ′ (x) = 0 at least on [1, 2] Since f(1) = 0 and f(2) = 0, thus there exists c such that f ′ (c) = 0. Theorem 3 (Extreme Value Theorem) Suppose f ∈ C[a, b], then there exists two points ξ1, ξ2 ∈ [a, b], such that f(ξ1) ≤ f(x) ≤ f(ξ2) for x ∈ [a, b]. In addition, if f is differentiable on [a, b], then ξ1, ξ2 occur either at the endpoints of [a, b] or where f ′ is zero. Theorem 4 (Intermediate Value Theorem) Suppose f ∈ C[a, b] and K is any number between f(a), f(b), then there exists a number ξ ∈ (a, b) for which f(ξ) = K. Example: Let f(x) = x − e −x For f(0) = −1, f(1) = 1 − 1 e > 0, then there exists c such that f(c) = 0. Theorem 5 (Taylor’s theorem) Suppose f ∈ C n[a, b] that f n+1 exists on [a, b], and x0 ∈ [a, b], there exists a number ξ(x) between x0 and x with f(x) = Pn(x) + 5