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?
The square root problem Suppose a is a positive real number and that we want to compute its square root geometrically this task is equivalent to constructing a square whose area is A. x
The square root problem Suppose A is a positive real number and that we want to compute its square root. Geometrically, this task is equivalent to constructing a square whose area is A. c c x A x x 2 1
XC 6000/Xc 60.00000000000000100.00000000000000 80.000000000000007500000000000000 77.500000000000007741935483870968 77459677419354857745965642894325 77459666924149057745966692414763 77459666924148347745966692414834 77459666924148347745966692414834 7745966692414834
xc 6000/xc ------------------------------------------- ------- ------ 60.00000000000000 100.00000000000000 80.00000000000000 75.00000000000000 77.50000000000000 77.41935483870968 77.45967741935485 77.45965642894325 77.45966692414905 77.45966692414763 77.45966692414834 77.45966692414834 77.45966692414834 77.45966692414834 77.45966692414834
To improve an approximate square root A=m米A,4 <m<1 √A=√m*2,m∈[.25,1 a good initial guess for the reduced range problem can be obtained by linear interpolation with L(m)=(1+2m)/3 L(m)-√m|≤0.05
To improve an approximate square root 1 4 1 A m*4 , m e A m *2 , m [.25,1] e a good initial guess for the reduced range problem can be obtained by linear interpolation with L(m) (1 2m)/ 3 | L(m) m | 0.05
sqrt(m) 0.8 04 0.2 0.5 15
0 0.5 1 1.5 0 0.2 0.4 0.6 0.81 1.2 m sqrt(m)
x+ C -L(m), ek=xk 2x k It can be shown that the iterates x are al ways in the interval [5, 1, and so k+1 e4≤e3≤e2≤e8≤6≤(05)6
2 2 1 2 1 c c c c x x m m x m x m x x0 L(m),ek xk m 2 1 2 1 k k k e x e It can be shown that the iterates xk are always in the interval [.5,1], and so 2 k 1 k e e 16 16 0 8 1 4 2 2 4 3 e e e e e (.05)