Introduction to scientific Computing A Matrix Vector Approach Using Matlab Written by Charles FVan Loan 陈文斌 Wbchen(@fudan.edu.cn 复旦大学
Introduction to Scientific Computing -- A Matrix Vector Approach Using Matlab Written by Charles F.Van Loan 陈 文 斌 Wbchen@fudan.edu.cn 复旦大学
Chapter 8 Nonlinear Equations and optimization Finding roots Minimizing a function of one variable Minimizing multivariate functions Solving systems of nonlinear equations
Chapter 8 Nonlinear Equations and Optimization • Finding Roots • Minimizing a function of one variable • Minimizing multivariate functions • Solving systems of nonlinear equations
We consider several types of nonlinear problems. They differ in whether or not the solution sought is a vector or a scalar and whether or not the goal is to produce a root or a minimizer of some given function. The presentation is organized around a family of orbit problems. Suppose the vector-valued functions x2(t) P()= P2(t)= y,(t) Specify the location at time t of a pair of planets that go around the sun. assume that the orbits are elliptical and that the sun is situated at(0,0) Question 1. At what times are the planets and the sun collinear? Iff (t) is the the sine of the angle between PI and P2, then this problem is equivalent to finding a zero of f(t). We focus on the bisection and Newton methods and the matlab zero-finder
We consider several types of nonlinear problems. They differ in whether or not the solution sought is a vector or a scalar and whether or not the goal is to produce a root or a minimizer of some given function. The presentation is organized around a family of “orbit” problems. Suppose the vector-valued functions ( ) ( ) ( ) ( ) ( ) ( ) 2 2 2 1 1 1 y t x t P t y t x t P t Specify the location at time t of a pair of planets that go around the Sun. Assume that the orbits are elliptical and that the sun is situated at (0,0). Question 1. At what times are the planets and the sun collinear? If f(t) is the the sine of the angle between P1 and P2 , then this problem is equivalent to finding a zero of f(t). We focus on the bisection and Newton methods, and the Matlab zero-finder: fzero
Question 2. How close do the two planets get for a period of time? If f(t) is distance from Pi to P2, then this is a single-variable minimization problem. We develop the method of golden section search and discuss the matlab minimizer fmin Question 3. How close do the two orbits get? The method of steepest descent and matlab multivariable minimizer fmins are designed to solve problems of this variety min |P(1)-P(2) Question 4. Where(if at all) do the two orbits intersect? This is an example of a multivariable root- finding problem F(t12t2)=P2(t2)-P(t1)=0 The Newton framework for systems of nonlinear equations is discussed Related topics include the use of finite differences to approximate the Jacobian and the Gauss-Newton method for the nonlinear least squares problem
Question 2. How close do the two planets get for a period of time? If f(t) is distance from P1 to P2 , then this is a single-variable minimization problem. We develop the method of golden section search and discuss the Matlab minmizer fmin. Question 3. How close do the two orbits get? The method of steepest descent and Matlab multivariable minimizer fmins are designed to solve problems of this variety. Question 4. Where (if at all) do the two orbits intersect? This is an example of a multivariable root-finding problem: The Newton framework for systems of nonlinear equations is discussed. Related topics include the use of finite differences to approximate the Jacobian and the Gauss-Newton method for the nonlinear least squares problem. F(t1 ,t2 ) P2 (t2 ) P1(t1) 0 1 1 2 2 2 min , ( ) ( ) 1 2 P t P t t t
Finding roots f(t)=10e31+2e5-6=0 quintic polynomial x 5-2x+x x+7=0 Algorithms in this area are iterative and proceed by producing a sequence of numbers that converge to a root of interest Where do we start the iteration? Does the iteration converge and how fast? How do we know when to terminate the iteration
Finding Roots ( ) 10 2 6 0 3 5 t t f t e e quintic polynomial 2 7 0 5 4 2 x x x x Algorithms in this area are iterative and proceed by producing a sequence of numbers that converge to a root of interest. Where do we start the iteration? Does the iteration converge and how fast? How do we know when to terminate the iteration?