Numerical Methods-Lecture V-Newton's Method
Numerical Methods-LectureV-Newton’s MethodTrevor GallenFall, 20151/1
GoalsAim is to teach numerical methods, give you the tools you need towrite down, solve, and estimate models1. Interpolation2. Numerical derivatives3. Maximization/minimizationIDeterministic, stochasticIDerivative-based, derivative-freeILocal, global4. Numerical integration/quadrature5. Bellman equations2/1
MotivationIWe have some function f (x)IWant to find x such that f (x ) 0.IExamples:IEquilibrium conditions: X S (p) X D (p) 0IMaximization conditions: u 0 (c) λ 03/1
Newton’s Method: Idea1. Take a linear approximation of function, find slope andintercept2. Given equation of line, solve for zero3. Take that new point, repeat.4/1
Newton’s Method Derivation1. Take Taylor expansion: f (x) f (x0 ) 2. Set equal to zero: 0 f (x0 ) 3. Solve for x: x x0 f (x) x x x0 f (x) x x x0(x x0 )(x x0 )f (x0 ) f (x) x x x04. Call x x0 repeat.In other words, the interative procedure:xn 1 xn f (xn )f 0 (xn )5/1
Example: f (x) sin(x), x0 11. x1 sin(1) sin(1)cos(1)2. x2 0.56 sin( 0.56)cos( 0.56)3. x3 0.07 sin(0.07)cos(0.07) 1 0.84140.5403 0.56 0.56 0.07 0.0710.530.85 0.07 1e 44. And so on until xi 0.Note: I round.6/1
Do different starting places matter?Iteration0123.Trial 11-.560.07-1e-4.Trial 20.5-0.053e-5-1e-14.Trial 324.12.43.2.Trial 43.53.133.143.14.Trial 51.4-4.401.322.64.003.14.3.14.3.14.10A little, and a lot.7/1
Newton’s Method, Graphically-I8/1
Newton’s Method, Graphically-II9/1
Newton’s Method, Graphically-III10 / 1
Newton’s Method, Graphically-IV11 / 1
Newton’s Method, Graphically-V12 / 1
Newton’s Method, Graphically-VI13 / 1
Newton’s Method, Graphically-VII14 / 1
Newton’s Method, Graphically-VIII15 / 1
Newton’s Method, Graphically-IX16 / 1
Newton’s Method, Graphically, New StartingPoint17 / 1
Newton’s Method, Graphically-XI18 / 1
Newton’s Method, Graphically-XII19 / 1
Newton’s Method, Graphically-XIII20 / 1
Newton’s Method, Graphically-XIV21 / 1
Newton’s Method, Graphically-XV22 / 1
Newton’s Method, Graphically-XVI23 / 1
Newton’s Method, Graphically-XVII24 / 1
Newton’s Method, Graphically-XVIII25 / 1
Benefits, CostsINewton’s method is quite rapid (locally quadraticallyconvergent)IRequires smoothness/derivativeICan get trapped at local minimaICan be sensitive to starting points26 / 1
One dimension is easy.how about two?Before, scalar equation:f (x) 0Now: f [1] (x1 , x2 )f [2] (x1 , x2 ) 00 27 / 1
Newton’s Method: Vector of Equations f [1] (x1 , x2 )f [2] (x1 , x2 ) 00 The Jacobian (matrix of first derivatives):" [1]#[1]Df f x1 f [2] x1 f x2 f [2] x2So we can take the multivariate taylor expansion, in matrix form: " f [1] f [1] # [1] [1] xf (x1 , x2 )f (x1 , x2 )x11 x x f [2]1 f [2]2 x2x2f [2] (x1 , x2 )f [2] (x1 , x2 ) x x1228 / 1
Newton’s Method: Vector of EquationsSet it equal to zero: 00 f [1] (x1 , x2 )f [2] (x1 , x2 ) Solving for x1x2x1x2 f [1] x1 f [2] x1 f [1] x2 f [2] x2# x1x2f [1] (x1 , x2 )f [2] (x1 , x2 ) x1x2 assuming and inverse matrix: " x1x2" f [1] x1 f [2] x1 f [1] x2 f [2] x2# 1 Or, with obvious notation for the vector X , X̄ , F , and the jacobianof F , J:Xn 1 X̄n J 1 F (X̄n )29 / 1
Example-I f [1] (x1 , x2 )f [2] (x1 , x2 ) exp(x1 ) 2 exp(x2 )x1 x2 3 So we can write: J(X ) J(X ) 1exp(x1 ) 2 exp(x2 )111 exp(x1 ) 2 exp(x2 ) 1 2 exp(x2 ) 1 exp(x1 ) 30 / 1
Example-IIStart at (0, 0): x1x2x1x2 002.330.66 0.33 0.66 0.33 0.660.07 0.27 0.07 0.72 1 1 1 3 6.410 2.330.66 2.881.11 And so on until the solution, x1 1.84 and x2 1.1531 / 1
Example-II: First equation and zeros32 / 1
Example-II: Second equation and zeros33 / 1
Example-II: Both Equations and zeros34 / 1
Example-II: Both Equations and zeros(rotated)35 / 1
Equations, approximations, and zerosStart at (0,0), take tangent planes, find where planes intersectwith zero (green lines), find where lines intersect (new point). Inthis case, red and green line are same because linear expansion oflinear plane is plane.36 / 1
MinimizationConceptually, minimization is the same: just find the zeros of thederivative:f 0 (xn )xn 1 xn 00f (xn )and:Xn 1 Xn H 1 f 0 (xn )37 / 1
ExtensionsI80% of the minimization and solving methods you meet willbe derivative-based twists of Newton’s MethodIHalley’s Method, Householder Methods: Higher-orderderivativesIQuasi-Newton Methods: If you can’t take J, approximate itISecant Method: Newton’s Method with finite differencesIGauss-Newton: Minimize sum of squared functionsILecture 2 talks about alternatives38 / 1
Extensions I 80% of the minimization and solving methods you meet will be derivative-based twists of Newton's Method I Halley's Method, Householder Methods: Higher-order derivatives I Quasi-Newton Methods: If you can't take J, approximate it I Secant Method: Newton's Method with nite di erences I Gauss-Newton: Minimize sum of squared functions I Lecture 2 talks about alternatives
Introduction of Chemical Reaction Engineering Introduction about Chemical Engineering 0:31:15 0:31:09. Lecture 14 Lecture 15 Lecture 16 Lecture 17 Lecture 18 Lecture 19 Lecture 20 Lecture 21 Lecture 22 Lecture 23 Lecture 24 Lecture 25 Lecture 26 Lecture 27 Lecture 28 Lecture
Galilean Relativity Newton's profound perspective Newton's Laws of Motion 3 ways Newton's Law of Gravitation 9/8/10 2 Newton's profound perspective Newton formulated a universal theory of motion and gravity Same laws of physics operate anywhere and anytime in the Universe
6. Newton-Raphson Method In numerical analysis, Newton-Raphson (James, 2008) method also known as Newton's methods is one of the well-known approximation methods in solving non-linear equations. Newton's method is well-known for its fast converge speed; especially when the initial guess is sufficiently closed to the root.
Derivation Example Convergence Final Remarks Outline 1 Newton's Method: Derivation 2 Example using Newton's Method & Fixed-Point Iteration 3 Convergence using Newton's Method 4 Final Remarks on Practical Application Numerical Analysis (Chapter 2) Newton's Method R L Burden & J D Faires 2 / 33
Chapter 4 Newton’s Laws of Motion q4.1 Force and Interactions q4.2 Newton’s First Law q4.3 Mass and Weight q4.4 Newton’s Second Law q4.5 Newton’s Third Law q4.6 Free-Body Diagrams Isaac Newton’s work represents one of the greatest contributions to science ever made by an individual.
Discussion of Newton's Method II Newton's method solves linear system at every iteration. Can be computationally expensive, if n is large. Remedy: Apply iterative solvers, e.g. conjugate-gradients. Newton's method needs rst and second derivatives. Finite di erences are computationally expensive. Use automatic di erentiation (AD) for gradient
Lecture 1: A Beginner's Guide Lecture 2: Introduction to Programming Lecture 3: Introduction to C, structure of C programming Lecture 4: Elements of C Lecture 5: Variables, Statements, Expressions Lecture 6: Input-Output in C Lecture 7: Formatted Input-Output Lecture 8: Operators Lecture 9: Operators continued
SUBJECT: ARALING PANLIPUNAN 5 YEAR/LEVEL: GRADE 5 DATE TOPIC MINIMUM LEARNING COMPETENCIES ACTIVITY/MATERIALS KEY TERMS EVALUATION OUTPUT HUNYO 18, 2018 ARALIN 1: ANG KINALALAGYAN NG PILIPINAS SA MUNDO p. 2-3 1. Nailalarawan ang lokasyon ng Pilipinas sa mapa 1.1 Natutukoy ang kinalalagyan ng Pilipinas sa mundo gamit ang mapa batay sa “absolute location” nito (longitude at latitude) (AP5PLP .
