### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Tching Mid Sch Math MATH 3500

WMU

GPA 3.59

### View Full Document

## 43

## 0

## Popular in Course

## Popular in Mathematics (M)

This 139 page Class Notes was uploaded by Ms. Deborah Gaylord on Wednesday September 30, 2015. The Class Notes belongs to MATH 3500 at Western Michigan University taught by Staff in Fall. Since its upload, it has received 43 views. For similar materials see /class/216823/math-3500-western-michigan-university in Mathematics (M) at Western Michigan University.

## Reviews for Tching Mid Sch Math

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/30/15

MATH 350 Introduction to Computational Mathematics Chapter IV Locating Roots of Equations Greg Fasshauer Department of Applied Mathematics Illinois Institute of Technology Spring 2008 fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Outline Motivation and Applications Bisection Newton s Method Secant Method Inverse Quadratic Interpolation Root Finding in MATLAB The Function fzero Newton s Method for Systems of Nonlinear Equations Optimization fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Motivation and Applications utline 0 Motivation and Applications iseoton Newtonis Method Secant Method nverse ntetpolation Root Finding in MATIEAZ The Function fzero Newtonis Method tOi39 of Nonineatr Equatons pt hi i at o n H fasshaueriitedu MATH Chapter 4 iii Motivation and Applications We studied systems of linear equations in Chapter 2 and convinced ourselves of the importance for doing this fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Motivation and Applications We studied systems of linear equations in Chapter 2 and convinced ourselves of the importance for doing this Many reallife phenomena are more accurately described by nonlinear models Thus we often find ourselves asking fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Motivation and Applications We studied systems of linear equations in Chapter 2 and convinced ourselves of the importance for doing this Many reallife phenomena are more accurately described by nonlinear models Thus we often find ourselves asking Question For what values of X is the equation fX O satisfied J fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Motivation and Applications We studied systems of linear equations in Chapter 2 and convinced ourselves of the importance for doing this Many reallife phenomena are more accurately described by nonlinear models Thus we often find ourselves asking Question For what values of X is the equation fX O satisfied J Remark Such an X is called a root of the nonlinear equation fX O I fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Motivation and Applications We studied systems of linear equations in Chapter 2 and convinced ourselves of the importance for doing this Many reallife phenomena are more accurately described by nonlinear models Thus we often find ourselves asking Question For what values of X is the equation fX O satisfied J Remark Such an X is called a root of the nonlinear equation fX O Example Find the first positive root of the Bessel function J DO 2k 000 Z 22kk2x 39 KID fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Motivation and Applications We studied systems of linear equations in Chapter 2 and convinced ourselves of the importance for doing this Many reallife phenomena are more accurately described by nonlinear models Thus we often find ourselves asking Question For what values of X is the equation fX O satisfied J Remark Such an X is called a root of the nonlinear equation fX O Example Find the first positive root of the Bessel function 00 1 k D Vg 2k JOX k222kk2x in 1 in 2 at fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Motivation and Applications A more complicated example arises when the function f is given only indirectly as the solution of a differential equation Example Consider the skydive model of Chapter 1 We can use a numerical method to find the velocity at any time t 2 0 At what time will the skydiver hit the ground fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Motivation and Applications A more complicated example arises when the function f is given only indirectly as the solution of a differential equation Example Consider the skydive model of Chapter 1 We can use a numerical method to find the velocity at any time t 2 0 At what time will the skydiver hit the ground Solution We need to first find the position altitude from the initial position and calculated velocity essentially the solution of another differential equation Then we need to find the root of the position function a rather complex procedure fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Motivation and Applications Most of this chapter will be concerned with the solution of a single nonlinear equation However systems of nonlinear equations are also important and difficult to solve fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Motivation and Applications Most of this chapter will be concerned with the solution of a single nonlinear equation However systems of nonlinear equations are also important and difficult to solve Example Consider a missile M following the parametrized path XMU 1 yMt1 6quot and a missile interceptor lwhose launch angle or we want to determine to that it will intersect the missiles path Let the parametrized path for the interceptor be given as Xt1 tcosd yt tsina fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Motivation and Applications Most of this chapter will be concerned with the solution of a single nonlinear equation However systems of nonlinear equations are also important and difficult to solve Example Consider a missile M following the parametrized path XMU 1 yMt1 6quot and a missile interceptor lwhose launch angle or we want to determine to that it will intersect the missiles path Let the parametrized path for the interceptor be given as Xt1 tcosd yt tsina Thus we want to solve the nonlinear system t 1 l COSa fl oz t 1tC08aO or t t2 t t2 1 e tsrna gta 1 e tsrna 0 10 fasshaueriitedu MATH 350 Chapter 4 Spring 2008 utl i Motivation and Applications 9 Biasectin Newton s Method Seoant Method Inverse Quadratic Interpolation Root Finding in MATLAB The Function fzero Newton s Method for Systems of Nonlinear Equations Optimization fasshaueriituedu Theorem Intermediate Value Theorem ft is continuous on an interval a b and fa and fb are of opposite sign then f has at least one root in a b fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Theorem Intermediate Value Theorem ft is continuous on an interval a b and fa and fb are of opposite sign then f has at least one root in a b This theorem provides the basis for a foolproof but rather slow trialanderror algorithm for finding a root of f fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Theorem Intermediate Value Theorem ft is continuous on an interval a b anol fa anol fb are of opposite sign then f has at least one root in a b This theorem provides the basis for a foolproof but rather slow trialanderror algorithm for finding a root of f 0 Take the midpoint X of the interval a b o If fX O we re done 0 If not fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Theorem Intermediate Value Theorem ft is continuous on an interval a b anol fa anol fb are of opposite sign then f has at least one root in a b This theorem provides the basis for a foolproof but rather slow trialanderror algorithm for finding a root of f 0 Take the midpoint X of the interval a b o If fX O we re done 0 If not 0 Repeat entire procedure with either a b a X or a b X b making sure that fa and fb have opposite signs fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Bisection Algorithm while absb a gt epsabsb X a b2 if signfx signfb b x set ax as new ab else a x set xb as new ab end end MATH 350 Chapter 4 Spring 2008 Bisection Algorithm while absb a gt epsabsb X a b2 if signfx signfb b x set ax as new ab else a x set xb as new ab end end The termination condition while abs b a gt epsabs b ensures that the search continues until the root is found to within machine accuracy eps fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Bisection Algorithm while absb a gt epsabsb X a b2 if signfx signfb b x set ax as new ab else a x set xb as new ab end end The termination condition while abs b a gt epsabs b ensures that the search continues until the root is found to within machine accuracy eps See BisectDeme m and bisect m for an illustration fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Bisection Algorithm while absb a gt epsabsb X a b2 if signfx signfb b x set ax as new ab else a x set xb as new ab end end The termination condition while aios io a gt epsaraios io ensures that the search continues until the root is found to within machine accuracy eps See BisectDemo m and ioisect m for an illustration Remark The algorithm as coded above should always independent off converge in 52 iterations since the IEEE standard uses 52 bits for the mantissa and we compute the answer with 1 bit accuracy 2 fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method utli Motivation and Appiications Bisection e Newton s Method Seoant Method Inverse Quadratic Interpolation Root Finding in MAToAB The Function fzero Newtonss Method for Systems of Nonlinear Equations Optmizaton El MATH ra Newton s Method By Taylor s theorem assuming f exists we have X 32 2 fX fC X Cf C f fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method By Taylor s theorem assuming f exists we have X 32 2 So for values of c reasonably close to X we can approximate fX fC X Cf C f fX fC X Cf 0 fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method By Taylor s theorem assuming f exists we have X 32 2 fX fC X Cf C f So for values of c reasonably close to X we can approximate fX e fC X Cf C Since we are trying to find a root of f ie we are h0ping that fX O we have fC f C39 0fC l X CfC ltgt X os fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method By Taylor s theorem assuming f exists we have X C2 fX fc X Cf c 2 f So for values of c reasonably close to X we can approximate fX e fC X Cf C Since we are trying to find a root of f ie we are h0ping that fX O we have fC mf fl m O CX c o ltgt X 0 NC This motivates the Newton iteration formula fXn Xnl IZXn fXn 7071739quot where an initial guess X0 is required to start the iteration fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method Graphical Interpretation Consider the tangent line to the graph of f at Xni y fXn Z fXnXX Xn gt y fXn X XnfXn fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method Graphical Interpretation Consider the tangent line to the graph of f at Xni y fXn Z fXnXX Xn gt y fXn X XnfXn To see how this relates to Newton s method set y O and solve for x fXn OfXn X Xnf xn ltgt szn x fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method Graphical Interpretation Consider the tangent line to the graph of f at Xni y fXn Z fXnXX Xn gt y fXn X XnfXn To see how this relates to Newton s method set y O and solve for x fXn f Xn O fXnX Xnf xn ltgt szn first fasshaueriitedu MATH 350 Chapter 4 Spring 2008 codeforNewton sMethod Newton Iteration while absltx xprev gt epsabsX xprev x X X fXfprimex end fasshaueriitedu MATH 350 Chapter 4 Spring 2008 codeforNewton sMethod Newton Iteration while absx xprev gt epsabsX xprev x X X fXfprimex end See NewtonDemo m and newton m for an illustration The Maple file NewtonDemo mws contains an animated graphical illustration of the algorithm fasshaueriitedu MATH 350 Chapter 4 Spring 2008 codeforNewton sMethod Newton Iteration while absx xprev gt epsabsX xprev x X X fXfprimex end See NewtonDemo m and newton m for an illustration The Maple file NewtonDemo mws contains an animated graphical illustration of the algorithm Remark Convergence of Newton s method depends quite a bit on the choice of the initial guess X0 If successful the algorithm above converges very quickly to Within machine accuracy fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method Convergence of Newton s Method Problem How quickly does Newton s method converge How fast does the error decrease from one iteration to the next J fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method Convergence of Newton s Method Problem How quickly does Newton s method converge How fast does the error decrease from one iteration to the next j Solution Let s assume f x exists and f x y O for all X of interest 0 Denote root of f by X a error in iteration n by en Xn x j fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method Convergence of Newton s Method Problem How quickly does Newton s method converge How fast does the error decrease from one iteration to the next j Solution Let s assume f x exists and f x y O for all X of interest 0 Denote root of f by X a error in iteration n by en Xn x Then en l l Xn l I Xgtllt j fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method Convergence of Newton s Method Problem How quickly does Newton s method converge How fast does the error decrease from one iteration to the next j Solution Let s assume f x exists and f x y O for all X of interest a Denote root of f by X a error in iteration n by en Xn x Then en l l Xn l I Xgtllt fXn xn fXn X j fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method Convergence of Newton s Method Problem How quickly does Newton s method converge How fast does the error decrease from one iteration to the next j Solution Let s assume f x exists and f x y O for all X of interest a Denote root of f by X a error in iteration n by en Xn x Then en l l Xn l I Xgtllt fXn xn fXn X fXn en fXn j fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method Convergence of Newton s Method Problem How quickly does Newton s method converge How fast does the error decrease from one iteration to the next j Solution Let s assume f x exists and f x y O for all X of interest a Denote root of f by X a error in iteration n by en Xn x Then en l l Xn l I Xgtllt fXn xn WXn X fXn en fXn enf Xn fXn 1 f Xn j fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method Convergence of Newton s Method Solution oont On the other hand a Taylor expansion gives fX fX en a fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method Convergence of Newton s Method Solution oont On the other hand a Taylor expansion gives fX fX en h J fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method Convergence of Newton s Method Solution oont On the other hand a Taylor expansion gives 2 e f n X fXn en fXn enf Xn 2 f h J fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method Convergence of Newton s Method Solution oont On the other hand a Taylor expansion gives 0 we fang tom enf Xn 9 5 h J fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method Convergence of Newton s Method Solution cont On the other hand a Taylor expansion gives 2 e O X fXn en fXn enf Xn 2 f h Rearrange e2 enfXn fXn Ernaf 2 j fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method Convergence of Newton s Method Solution cont On the other hand a Taylor expansion gives 92 Z n o fX rx en fxn enfXn 2 f 5 h Rearrange e2 enfXn fXn Ernaf 2 2 in 1 2 f 9n1 fXn j fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method Convergence of Newton s Method Solution cont On the other hand a Taylor expansion gives 2 O fXgtIlt fXn en fXn enf Xn l 2 f h Rearrange e2 enfXn fXn Ernaf 2 2 in 1 2 f 9n1 fXn If Xn is close enough to X we have fX en1 z 2fXgtke2 gt en1 Oe2 j fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method Convergence of Newton s Method Solution cont On the other hand a Taylor expansion gives 2 O fXgtIlt fXn en fXn enf Xn l 2 f h Rearrange e2 enfXn fXn Ernaf 2 2 in 1 2 if 6n1 If Xn is close enough to X we have fX en1 z 2fXgtke2 gt en1 Oe2 This is known as quadratic convergence and implies that the number of correct digits approximately doubles in each iteration j fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Seoant Method utli Motivation and Appiications Bisection Newton s Method o Secant Method Inverse Quadratic Interpolation Root Finding in MAToAB The Function fzero Newtonss Method for Systems of Nonlinear Equations Optmizaton El MATH ra Secant Method Problem A significant drawback of Newton s method is its need for f Xn J fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Seoant Method Problem A significant drawback of Newton s method is its need for f Xn J Solution We approximate the value of the derivative f Xn by the slope sn given as I fXn fX1 Xn Xn t 5n fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Secant Method Problem i A significant drawback of Newton s method is its need for f Xn J Solution We approximate the value of the derivative f Xn by the slope sn given as I fXn fX1 Xn Xn t 5n Then we get the iteration formula f Xn1Xn 7 n12 n Since sn is the slope of the secant line from Xn1 fX1 to Xn fX this method is called the secant method fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Secant Method Problem A significant drawback of Newton s method is its need for f Xn Solution We approximate the value of the derivative f Xn by the slope sn given as I fXn fX1 Xn Xn t 5n Then we get the iteration formula f Xn1Xn 7 n12 n Since sn is the slope of the secant line from Xn1 fX1 to Xn fX this method is called the secant method Remark The secant method requires two initial guesses X0 and X1 fasshaueriitedu MATH 350 Chapter 4 Spring 2008 codefortheSecantMethod Secant Method while absb a gt epsabsb ca ab b b b Cfcfb l end fasshaueriitedu MATH 350 Chapter 4 Spring 2008 codefortheSecantMethod Secant Method while absb a gt epsabsb C a a b b b b CfCfb l end Xn Xn1 Xn Xn1 Xn Xn1fXn fXn Note that fXn11 fxn1 fXn fxn1 fxn sn fXn fXn fasshaueriitedu MATH 350 Chapter 4 Spring 2008 codefortheSecamMethod Seoant Method while absb a gt epsabsb C a a lo bb b CfCfb li end Xn Xn1 Xn Xn1 Xn Xn1fXn fXn fXn1 1 fxn1 fXn fXn1 fXn S n fXn fXn ISLE See SecantDemo m and secant m for an illustration The Maple file SecantDemo mws contains an animated graphical illustration of J the algorithm I4 fasshaueriitedu MATH 350 Chapter 4 Spring 2008 codefortheSecamMethod Secant Method while absb a gt epsabsb C a a lo bb b CfCfb 1 end Xn Xn1 Xn Xn1 Xn Xn1fXn fXn fXn1 1 fxn1 fXn fXn1 fXn S n fXn fXn See SecantDemo m and secant m for an illustration The Maple file SecantDemo mws contains an animated graphical illustration of the algorithm Remark Convergence of the secant method also depends on the choice of initial guesses If successful the algorithm converges superlinearly ie en1 0e Where o 2 5 12 the golden ratio A J fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Inverse Quadratic Interpolation Outline e Inverse Quadratic Interpolation fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Inverse Quadratic Interpolation We can interpret the seoant method as using the linear interpolant to the data Xn1 fX1 Xn fX to approximate the zero of the function f fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Inverse Quadratic Interpolation We can interpret the secant method as using the linear interpolant to the data Xn1 fX1 Xn fX to approximate the zero of the function f Question Wouldn t it be better if possible to use a quadratic interpolant to three data points to get this job done fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Inverse Quadratic Interpolation We can interpret the secant method as using the linear interpolant to the data Xn1 fX1 Xn fX to approximate the zero of the function f Question Wouldn t it be better if possible to use a quadratic interpolant to three data points to get this job done Answer In principle quotyesquot The resulting method is called inverse quadratic interpolation IQI 0 is like an immature race horse It moves very quickly when it is near the finish line but its global behavior can be erratic NCM fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Inverse Quadratic Interpolation How does inverse quadratic interpolation work Assume we have 3 data points a fa b fb c fc fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Inverse Quadratic Interpolation How does inverse quadratic interpolation work Assume we have 3 data points a fa b fb c fc Instead of interpolating the data directly with a quadratic polynomial we reverse the roles of X and y since then we can evaluate the resulting polynomial at y O and this gives an approximation to the root of f fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Inverse Quadratic Interpolation How does inverse quadratic interpolation work Assume we have 3 data points a fa b fb c fc Instead of interpolating the data directly with a quadratic polynomial we reverse the roles of X and y since then we can evaluate the resulting polynomial at y O and this gives an approximation to the root of f 2 El 2 El E 8 ID fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Inverse Quadratic Interpolation How does inverse quadratic interpolation work Assume we have 3 data points a fa b fb c fc Instead of interpolating the data directly with a quadratic polynomial we reverse the roles of X and y since then we can evaluate the resulting polynomial at y O and this gives an approximation to the root of f IEI fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Inverse Quadratic Interpolation How does inverse quadratic interpolation work Assume we have 3 data points a fa b fb c fc Instead of interpolating the data directly with a quadratic polynomial we reverse the roles of X and y since then we can evaluate the resulting polynomial at y O and this gives an approximation to the root of f i39 I 39 I I 2 El 2 El E 8 ID fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Inverse Quadratic Interpolation MATLAB code for the Inverse Quadratic Interpolation Method IQI Method while absc b gt epsabsc x polyinterpfafofc aocO b C OCTDJ end fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Inverse Quadratic Interpolation MATLAB code for the Inverse Quadratic Interpolation Method IQI Method while absc b gt epsabsc x polyinterpfafofc alocO b C OCTDJ end See the MATLAB script Iotoemo m which calls the function iqi m fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Inverse Quadratic Interpolation MATLAB code for the Inverse Quadratic Interpolation Method IQI Method while absc b gt epsabsc x polyinterpfafofc alocO b C OCTDJ end See the MATLAB script Iotoemo m which calls the function iqi m Remark One of the major challenges for the IQI method is to ensure that the function values i e fa fb and fc are distinct since we are using them as our interpolation nodes j V fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Root Finding in MATLAB The Function fzero Outline 6 Root Finding in MATLAB The Function fzero fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Root Finding in MATLAB The Function fzero The MATLAB code fzerotxm from NCM is based on a combination of three of the methods discussed above bisection secant and IQI fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Root Finding in MATLAB The Function fzero The MATLAB code fzerotxm from NCM is based on a combination of three of the methods discussed above bisection secant and IQI 0 Start with a and b so that fa and fb have opposite signs 0 Use a secant step to give 0 between a and b 0 Repeat the following steps until b a lt b or fb O 0 Arrange a b and c so that o fa and fb have opposite signs 0 fb s fal o c is the previous value of b If c a consider an IQI step If c a consider a secant step If the IQI or secant step is in the interval a b take it If the step is not in the interval use bisection fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Root Finding in MATLAB The Function fzero The MATLAB code fzerotxm from NCM is based on a combination of three of the methods discussed above bisection secant and IQI 0 Start with a and b so that fa and fb have opposite signs 0 Use a secant step to give 0 between a and b 0 Repeat the following steps until b a lt b or fb O 0 Arrange a b and c so that o fa and fb have opposite signs 0 fb s fal o c is the previous value of b o If c a consider an IQI step 0 If c a consider a secant step c If the IQI or secant step is in the interval a b take it o If the step is not in the interval use bisection The algorithm always works and combines the robustness of the bisection method and the speed of the secant and IQI methods fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Root Finding in MATLAB The Function fzero The MATLAB code fzerotxm from NCM is based on a combination of three of the methods discussed above bisection secant and IQI a Start with a and b so that fa and fb have opposite signs 0 Use a secant step to give 0 between a and b 0 Repeat the following steps until b a lt b or fb O 0 Arrange a b and c so that o fa and fb have opposite signs 0 fb s fal o c is the previous value of b o If c a consider an IQI step 0 If c a consider a secant step c If the IQI or secant step is in the interval a b take it o If the step is not in the interval use bisection The algorithm always works and combines the robustness of the bisection method and the speed of the secant and IQI methods This algorithm is also known as Brent s method fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Root Finding in MATLAB The Function fzero Root finding in MATLAB cont A stepbystep exploration of the fzero algorithm is possible with fzerogui m from NCM To find the first positive root of JO use fzeroguix besselj0x04 where x besselj O x is an anonymous function of the one variable x while the argument besselj would be a function handle for a function of two variables and therefore confuse the routine fzerogui fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method for Systems of Nonlinear Equations Outline a Newton s Method for Systems of Nonlinear Equations fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method for Systems of Nonlinear Equations Example We now want to solve a nonlinear system such as fl oz t 1l COSozO gl oz 1 e t tsina O fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method for Systems of Nonlinear Equations Example We now want to solve a nonlinear system such as fl oz t 1l COSozO t2 gtd 1 e t l Slnoz l O Earlier we derived the basic Newton method from the truncated Taylor expansion X C2 2 f fX fc X Cf c Then f fX m fo X cf o fgo X z o f fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method for Systems of Nonlinear Equations Example We now want to solve a nonlinear system such as fl oz t 1l COSozO t2 gtd 1 e t l Slnoz l O Earlier we derived the basic Newton method from the truncated Taylor expansion X 02 fx fc X cf c 2 f Then f fx z fc X cf c g x m c f Using vector notation our nonlinear system above can be written as fx 0 where x t dT and f f gT fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method for Systems of Nonlinear Equations Example We now want to solve a nonlinear system such as fl oz t 1l COSozO t2 gtd 1 e t l Slnoz l O Earlier we derived the basic Newton method from the truncated Taylor expansion X 02 fx fc X cf c 2 f Then f fx z fc X cf c g x m c f Using vector notation our nonlinear system above can be written as fx 0 where x t dT and f f gT We therefore need a multivariate version of Newton s method fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method for Systems of Nonlinear Equations For a single function f of m variables we would need the expansion for fc x cgtTvgtfcgt gm ciTvgt2flto a a a T where V 8X1 8X2 m IS the gradient operator If we have only m 2 variables Le x X1X2T this becomes 3 3 fX1X2 f01702X1 Ma X1 X2 02a X2gt 01702 1 8 a 2 X1 C1a X1 X2 02a X2 61762 or or 110102 X1 cog 0102 X2 Goa 0102 X1 X2 X1 012 32 32 X2 C22 32 X c X c f 2 6X12 1 1 2 2aX1aX2 2 3X22 1 2 fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method for Systems of Nonlinear Equations Therefore we can approximate f by 8f 8f fX1X2 01702 X1 013 X101C2 X2 C23 X201C2 or in more compact operator notation 7 00 f0 X CTVI C fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method for Systems of Nonlinear Equations Therefore we can approximate f by 8f 8f fX1X2 01702 X1 013 X101C2 X2 C23 X201C2 or in more compact operator notation 7 00 f0 X CTVI C Note that this approximation is a linearization of f and in fact denotes the tangent plane to the graph of f at the point c fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method for Systems of Nonlinear Equations More generally we have the multivariate Taylor expansion 1 00 2 x CTVquotfc Enxgt lt3 kO I Here the remainder is 1 T n1 f Enxgt n 1 ax c v o where 5 c 6x c with O lt 6 lt 1 is a point somewhere on the T line connecting c and x and V 2 3X1 8X2 m IS the gradient operator as before fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method for Systems of Nonlinear Equations More generally we have the multivariate Taylor expansion 1 00 2 x CTVquotfc End lt3 kO I Here the remainder is 1 n1 EnX X 0TVquot17 where 5 c 6x c with O lt 6 lt 1 is a point somewhere on the T line connecting c and x and V 3X1 8X2 m IS the gradient operator as before Note however that this is added as a referencereminder only and is not required for the derivation of the multivariate Newton method fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method for Systems of Nonlinear Equations Now we want to tackle the full problem ie we want to solve the following square system of nonlinear equations f1X1X2Xm O f2X17X277Xm 07 4 fmX1X2Xm O fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method for Systems of Nonlinear Equations Now we want to tackle the full problem ie we want to solve the following square system of nonlinear equations f1X1X2Xm O f2X17X277Xm 07 4 fmX1X2Xm 0 To derive Newton s method for 4 we write it in the form fxO i1m By linearizing f i 1m we have W m fc x ownc fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method for Systems of Nonlinear Equations Since fx O we get fc e X CTVfc 8f 8Xm X1 C1Cl X2 02C Xm Cm c fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method for Systems of Nonlinear Equations Since fx O we get fc e X 0TVfc 8f 8Xm X1 C1Cl X2 02C Xm Cm 0 Therefore we have a linear system for the unknown approximate root X of 4 f101cm X1 01017m70mXm Cm01wgtCmv f201cm X1 01017m70mXm Cm01wvcmv 5 fmc1cm X1 C1thnacmXmCmC1V fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method for Systems of Nonlinear Equations To simplify notation a bit we now introduce h h1 and note that 5 is a linear system for h of the form where f f1fmT and is called the Jacobian of f fasshaueriitedu MATH 350 Chapter 4 fc7 afi 3X1 3X2 8fz afz 3X1 3X2 3X1 3X2 dxm 8 f2 dxm 8 fm dxm Spring 2008 Newton s Method for Systems of Nonlinear Equations To simplify notation a bit we now introduce h h1 hmT x c and note that 5 is a linear system for h of the form fc7 where f f1fmT and 39 8quot1 39 3X1 3X2 39 39 39 aXm 5 f2 5 f2 3 12 J 3X1 3X2 aXm 3X1 3X2 39 39 39 aXm is called the Jacobian of f Since h x c or x c h we see that h is an update to the previous approximation 0 of the root x fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method for Systems of Nonlinear Equations Algorithm Newton s method for square nonlinear systems is performed by Input f J XO forn012do Solve JX h fx for h Update X07 x h end Output x 1 fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method for Systems of Nonlinear Equations Algorithm Newton s method for square nonlinear systems is performed by Input f J XO forn012do Solve JX h fx for h Update X07 x h end Output x 1 Remark If we symbolically write f instead of J then the Newton iteration becomes 1 Xn1 X02 pawn foam W matrix which looks just like the Newton iteration formula for the single equationsingle variable case fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method for Systems of Nonlinear Equations Example Solve the missile intercept problem t 1t003a O 1 e t tsina O fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method for Systems of Nonlinear Equations Example Solve the missile intercept problem t 1t003a O 2 1 e t tSn06f O 0 Here f1ta t 1t003a f 7 I706 f2t06 t et tsina and 1 oosa tsina 31 30 JU a 23 quot 3 3 t a e t sinoz t5 toosa 39 fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method for Systems of Nonlinear Equations Example Solve the missile intercept problem Here and Jl oz Q3 f1 81 81 2 a t 1 l t 1t003a O 2 et l SInoz1f O O f1l O f2l 0 H 1 COSoz t 1t003a 1 e t tsina tsina o 130 e t sina US 400304 This example is illustrated in the Matlab script Newtonvaemo m which requires newtonmv m missilefm and missilej m fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method for Systems of Nonlinear Equations Example Solve X2y2 4 Xy 17 which corresponds to finding the intersection points of a circle and a hyperbola in the plane j fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method for Systems of Nonlinear Equations Example Solve X2y2 Xy 1 which corresponds to finding the intersection points of a circle and a hyperbola in the plane Here f1X7Y X2y2 4 and 39 or or 39 2X 2 my xy y XV 8X 8y fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method for Systems of Nonlinear Equations Example Solve X2y2 4 Xy 17 which corresponds to finding the intersection points of a circle and a hyperbola in the plane Here fxy f1X Y X2 y24 f2XY XY 1 and 39 or or 39 1 2X 2 my xy y XV 8X 8y This example is also illustrated in the Matlab script Newtonvaemo m The files Circhypf m and Circhypj m are also needed fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method for Systems of Nonlinear Equations Remark 0 Newton s method requires the user to input the m x m Jacobian matrix which depends on the specific nonlinear system to be solved This is rather cumbersome fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method for Systems of Nonlinear Equations Remark 0 Newton s method requires the user to input the m x m Jacobian matrix which depends on the specific nonlinear system to be solved This is rather cumbersome 9 In each iteration an m gtlt m dense linear system has to be solved This makes Newton s method very expensive and slow fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method for Systems of Nonlinear Equations Remark 0 Newton s method requires the user to input the m x m Jacobian matrix which depends on the specific nonlinear system to be solved This is rather cumbersome 9 In each iteration an m gtlt m dense linear system has to be solved This makes Newton s method very expensive and slow 9 For good starting values Newton s method converges quadratically to simple zeros ie solutions for which J 1z exists fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method for Systems of Nonlinear Equations Remark 0 Newton s method requires the user to input the m x m Jacobian matrix which depends on the specific nonlinear system to be solved This is rather cumbersome 9 In each iteration an m gtlt m dense linear system has to be solved This makes Newton s method very expensive and slow 9 For good starting values Newton s method converges quadratically to simple zeros ie solutions for which J 1z exists 9 Also there is no builtin MATLAB code for nonlinear systems fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Newton s Method for Systems of Nonlinear Equations Remark 0 Newton s method requires the user to input the m x m Jacobian matrix which depends on the specific nonlinear system to be solved This is rather cumbersome 9 In each iteration an m gtlt m dense linear system has to be solved This makes Newton s method very expensive and slow 9 For good starting values Newton s method converges quadratically to simple zeros ie solutions for which J 1z exists 9 Also there is no builtin MATLAB code for nonlinear systems 9 More details for nonlinear systems are provided in MATH 477 andor MATH 478 fasshaueriitedu MATH 350 Chapter 4 Spring 2008 utl i iVIotivation and Appiications iseotion Newton s Method Seoant Method Inverse Quadratic Interpolation Root Finding in MATLAB The Function fzero Newton s Method for Systems of Nonlinear Equations Optimization I rn if 39 7 1 1 C i i i 7 I E 39j t 39J g quot1 fasshaueriitaedu Optimization A problem Closely related to that of root finding is the need to find a maximum or minimum of a given function f fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Optimization A problem closely related to that of root finding is the need to find a maximum or minimum of a given function f For a continuous function of one variable this means that we need to find the critical points ie the roots of the derivative of f fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Optimization A problem closely related to that of root finding is the need to find a maximum or minimum of a given function f For a continuous function of one variable this means that we need to find the critical points ie the roots of the derivative of f Since we decided earlier that Newton s method which requires knowledge of f is in many cases too complicated and costly to use we would again like to find a method which can find the minimum off or of f if we re interested in finding the maximum of f on a given interval without requiring knowledge of f fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Optimization A problem closely related to that of root finding is the need to find a maximum or minimum of a given function f For a continuous function of one variable this means that we need to find the critical points ie the roots of the derivative of f Since we decided earlier that Newton s method which requires knowledge of f is in many cases too complicated and costly to use we would again like to find a method which can find the minimum off or of f if we re interested in finding the maximum of f on a given interval without requiring knowledge of f The final MATLAB function will again be a robust hybrid method fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Problem Use the bisection strategy to compute a minimum of f fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Problem i Use the bisection strategy to compute a minimum of t J Simple bisection doesn t work 1 05 U5 39 fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Problem i Use the bisection strategy to compute a minimum of t J Simple bisection doesn t work 1 05 2bi393 b D D fa I V D5 I I I I I I U5 I I I I I I U 1 2 3 4 5 1 2 3 4 5 We need to trisect the interval fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Problem Use the bisection strategy to compute a minimum of f Simple bisection doesn t work 1 05 2bi393 b D D 3903 I V D5 I I I I I I U5 I I I I I I U 1 2 3 4 5 1 2 3 4 5 We need to trisect the interval Now since fa 2b3 lt f2a b3 we can limit our search to 23 b3 b fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Problem Use the bisection strategy to compute a minimum of t J Simple bisection doesn t work 1 05 2bi393 b D D fa I V D5 I I I I I I U5 I I I I I I U 1 2 3 4 5 1 2 3 4 5 We need to trisect the interval Now since fa 2b3 lt f2a b3 we can limit our search to This strategy would work but is inefficient since a 2b 3 can t used for the next trisection step fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Optimization Golden Section Serch Want an efficient trisection algorithm fasshaueriitedu MATH Chapter 4 Golden Section Search Golden Section Search Want an efficient trisection algorithm What to do pick the two interior trisection points so that they can be reused in the next iteration along with their associated function values which may have been costly to obtain fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Golden Section Search Golden Section Search Want an efficient trisection algorithm What to do pick the two interior trisection points so that they can be reused in the next iteration along with their associated function values which may have been costly to obtain Assume interior points are u 1 papb apb a V pa1 pb b pUD a where O lt 0 lt 1 is a ratio to be determined fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Golden Section Search Golden Section Search Want an efficient trisection algorithm What to do pick the two interior trisection points so that they can be reused in the next iteration along with their associated function values which may have been costly to obtain Assume interior points are u 1 papbapb a V pa1 pbb pb a where O lt 0 lt 1 is a ratio to be determined If for example the interval in the next iteration is u b with interior point v then we want 0 to be such that the position of v relative to u and b is the same as that of u was to a and b in the previous iteration a u v w b fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Golden Section Search Golden Section Search cont Therefore we want 19 U 19 a fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Golden Section Search Golden Section Search cont Therefore we want 19 U 19 a v u u a b apb a b a b pb a apb a 3pb a a fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Golden Section Search cont b u v u b apb a Therefore we want S b prb agtgt ltapb agt b aw p S la aw 2pgt fasshaueriitedu MATH 350 Chapter 4 b a u a b a apb a a b a MID a Spring 2008 Golden Section Search cont b u v u b apb a Therefore we want b a u a b a S b pb agtgt ltapb agt b agtlt1 p S la aw 2pgt 1 C 1 amp0 fasshaueriitedu MATH 350 Chapter 4 3pb a a b a Mb 1 0 Spring 2008 Golden Section Search cont b u v u b apb a Therefore we want S b pb agtgt ltapb agt ta aw pgt la aw 2pgt 1 p S 1 2p ltgt p1 p fasshaueriitedu MATH 350 Chapter 4 b a u a b a apb a a b a MID a 1 0 1 2p Spring 2008 Golden Section Search cont b u v u b apb a Therefore we want S b pb agtgt ltapb agt ta aw pgt la aw 2pgt 1 p S 1 2p ltgt p1 p ltgt 02 3pl1 fasshaueriitedu MATH 350 Chapter 4 b a u a b a apb a a b a MID a 1 0 1 2p O Spring 2008 Golden Section Search Golden Section Search cont Therefore we want 19 U 2 b a V U u a ltgt b apb a b a b pb aapb a 3pb a a S b a1p b a 19 3X1 2p pb 3 1 p 1 ltgt 1 20 p ltgt p1 p 1 2p ltgt 02 3p1 o The solution in O 1 is p 32 5 0381966 fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Golden Section Search Golden Section Search oont Therefore we want 19 U 2 b a v u u a ltgt b apb a b a b pb a apb a 3pb a a S b axi p b a bU2m pW a 1 p 1 i 1 aaquot p ltgt p1 p 1 2p ltgt 02 301 o The solution in O 1 is p 32 5 0381966 Since P 2 Cb Where 12 1618034 is the golden ratio th method is called the golden section searoh fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Golden Section Search Golden Section Search cont u 1pap b V p a 1pb 39L I 05 D I fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Golden Section Search Golden Section Search cont u 1pap b V p a 1pb 1 05 I l a LI II b Cquot I I I I I I I I I I I I U5 39 D 1 2 3 4 5 fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Golden Section Search Golden Section Search cont u 1pap b V p a 1pb 05 fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Golden Section Search Golden Section Search cont Ll 1pap b V p a 1pb 05 fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Optimization Minimization in MATLAB The Function fminbnd While golden section search is a foolproof algorithm that will always find the minimum of a unimodular1 continuous function provided the initial interval a b is chosen so that it contains the minimum it is very slow To reduce the interval length to machine accuracy eps 75 iterations are required 1a function is unimodular if it has a single extremum on a b fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Optimization Minimization in MATLAB The Function fminbnd While golden section search is a foolproof algorithm that will always find the minimum of a unimodular1 continuous function provided the initial interval a b is chosen so that it contains the minimum it is very slow To reduce the interval length to machine accuracy eps 75 iterations are required A faster and just as robust algorithm consists of 0 golden section search if necessary a parabolic interpolation when possible 1a function is unimodular if it has a single extremum on a b fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Optimization Minimization in MATLAB The Function fminbnd While golden section search is a foolproof algorithm that will always find the minimum of a unimodular1 continuous function provided the initial interval a b is chosen so that it contains the minimum it is very slow To reduce the interval length to machine accuracy eps 75 iterations are required A faster and just as robust algorithm consists of 0 golden section search if necessary 0 parabolic interpolation when possible This algorithm called fminionol in MATLAB is also due to Richard Brent 1a function is unimodular if it has a single extremum on a b fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Optimization Minimization in MATLAB The Function fminbnd While golden section search is a foolproof algorithm that will always find the minimum of a unimodular1 continuous function provided the initial interval a b is chosen so that it contains the minimum it is very slow To reduce the interval length to machine accuracy eps 75 iterations are required A faster and just as robust algorithm consists of 0 golden section search if necessary a parabolic interpolation when possible This algorithm called fminionol in MATLAB is also due to Richard Brent If f has several minima on a b then fminionol may not find the global minimum 1a function is unimodular if it has a single extremum on a b fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Optimization Minimization in MATLAB The Function fminbnd While golden section search is a foolproof algorithm that will always find the minimum of a unimodular1 continuous function provided the initial interval a b is chosen so that it contains the minimum it is very slow To reduce the interval length to machine accuracy eps 75 iterations are required A faster and just as robust algorithm consists of 0 golden section search if necessary a parabolic interpolation when possible This algorithm called fminionol in MATLAB is also due to Richard Brent If f has several minima on a b then fminionol may not find the global minimum For an illustration see the MATLAB script FminDemo m which calls fmintx m from NCIVI 1a function is unimodular if it has a single extremum on a b fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Minimization in MATLAB The Function fminbnd An alternative approach One could also use Newton s method to find the critical points of f However then not only f needs to be known but also f fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Minimization in MATLAB The Function fminbnd An alternative approach One could also use Newton s method to find the critical points of f However then not only f needs to be known but also f The iteration formula to find a critical point would be fXn n 12 fXn7 O7 77 7 Xn1 Xn with initial guess X0 fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Minimization in MATLAB The Function fminbnd An alternative approach One could also use Newton s method to find the critical points of f However then not only f needs to be known but also f The iteration formula to find a critical point would be fXn n 12 fXn7 O7 77 7 Xn1 Xn with initial guess X0 Minimization of functions of more than one variable can be attempted with fminsearch in basic MATLAB and with other more powerful functions provided in the optimization toolbox fasshaueriitedu MATH 350 Chapter 4 Spring 2008 Refereeeee References l C M o e r Numerical Computing with MATLAB SIAM Philadelphia 2004 Also httpwwwmathworkscommoler fasshaueriitedu MATH 350 Chapter 4 Spring 2008

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.