2.007 –Design and Manufacturing I Optimization and Solution of SystemsToday’s AgendaSeedingImpoundingLinear Systems (Back Solving)Linear Systems (Solving)Linear Systems (Existence of Soln)Linear Systems (Existence of Soln)Linear Systems (Multiple Solutions)ComparisonsNewton-Raphson MethodNewton-Raphson MethodA Fundamental DifficultySecant MethodSecant MethodBisection MethodsBisection MethodsRates of ConvergenceRates of ConvergenceOptimizationExample ProblemRepresenting the GeometryDefine a Few FunctionsCompute a SolutionCompute Another SolutionRepresenting the GeometryAnimate the Leg MechanismBack-Drive the Leg with Link cdMatlab’s fsolveAdd a LinkAnimate the New MechanismTry Another Geometry3 Position SynthesisDiscussion QuestionRepresenting the Desired MotionsSynthesize the Leg MechanismAnimate the Synthesized MechanismPath GenerationDiscussion QuestionOptimizationOptimization Under ConstraintsNext StepsMIT OpenCourseWare http://ocw.mit.edu 2.007 Design and Manufacturing ISpring 2009For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.2.007 –Design and Manufacturing I Optimizationand Solution of SystemsDan Frey28 APR 2009-2 -1 0 1 2 3-4-3-2-101fghabcdce0x1x2x*xToday’s Agenda• Seeding and impounding procedures• Methods for Solving Systems– Newton-Raphson– Secant– Bisection• Examples related to mechanism designSeeding• Run on the table unopposed• Timing and set-up as in the actual contest• Three tries – best of three counts• Your “seeding card”is essential– Get your scores recorded and initialed– Don’t lose your card• “In-lab” competition– Basically a way to get round 1 partly finished– Same as next Weds but not broadcastImpounding• A way to bring the work to an end• Your machine is checked–Safety– Wiring– Rules issues• Your “seeding card” is essential– Your impound checks are recorded– Your card goes in the WOODEN BOXLinear Systems (Back Solving)A=[1 1 1;0 2 3;0 0 6];b=[3; 1; 4];x(3)=b(3)/A(3,3)x(2)=(b(2)-x(3)*A(2,3))/A(2,2)x(1)=(b(1)-x(2)*A(1,2)-x(3)*A(1,3))/A(1,1);norm(b-A*x')What will happen when I run this code?Linear Systems (Solving)A=[1 1 1;1 2 3;1 3 6];b=[3; 1; 4];x=A\bb=[5; 0; -10];x=A\bWhat will happen when I run this code?Linear Systems (Existence of Soln)A=[1 1 1;1 2 3;1 3 6;-1 -1 1];b=[3; 1; 4; 7];x=A\b;norm(b-A*x)What will happen when I run this code?Linear Systems (Existence of Soln)A=[1 1 1;1 2 3;1 3 6;-1 -1 1];b=[3; 1; 4; 6];x=A\b;norm(b-A*x)What will happen when I run this code?Linear Systems (Multiple Solutions)A=[1 1 1;1 2 3;1 3 6;-1 -1 1];b1=[3; 1; 4; 7];x1=A\b1; norm(b1-A*x1)b2=[5; 0; -10; -15];x2=A\b2; norm(b2-A*x2)What will happen when I run this code? b3=5*b1-2*b2;x3=A\b3; norm(b3-A*x3)norm(x3-(5*x1-2*x2))ComparisonsLinear Systems• Sometimes solved sequentially• # of equations = # of unknowns• # of equations > # of unknowns• When we can find two solutionsNonlinear systems•?•?•?•?Newton-Raphson Method• Make a guess at the solution• Make a linear approximation of a function by e.g., finite difference• Solve the linear system• Use that solution as a new guess• Repeat until some criterion is metInitial guess0Next estimateNewton-Raphson Method)()(1kkkkxfxfxx′+=+0x1x2x()( ))(1 kkkkFxFxxxJ−=−+If one equation in one variableSolve this system for xk+1Generalizing to systems of equations*xA Fundamental Difficultyxguess10:=xrootroot y xguess()xguess,():=50510154020020yx()yxroot()xxroot,• If there are many solutions, which solution you find will depend on the initial guessxguess3−:=xrootroot y xguess()xguess,():=50510154020020yx()yxroot()xxroot,If you seek to find a root of a function f(x), and you use the Newton-Raphson method. Choose all the numbers corresponding to outcomes that are NOT possible :1) You find the same solution no matter what initial guess you use2) You find many different solutions using many different initial guesses 3) You cannot find a solution because none exists4)You cannot find a solution even though one exists, even with many, many initial guessesSecant Method• No derivative needed!• Uses the current and the last iterate to compute the next one• Needs two starting valuesSecant Method)()()()(1111kkkkkkkxfxfxfxxfxx−−=−−−+0x1x2x3x*xBisection Methods• Given an interval in which a solution is known to lie• Look in the middle and determine which half has the root• Iterate until the remaining interval is small enoughBisection Methods0x1x2x211−++=kkkxxx0)()( if by replace0)()( if by replace1111111><−++−−++kkkkkkkkxfxfxxxfxfxxYou seek to find a root of a continuous function f(x), and you use the bisection method. Your initial guesses are such that What are the possible outcomes? Choose all the numbers that apply:1) You find a solution 2) You cannot find a solution even though one exists3)You cannot find a solution because no solution exists0)()(10<xfxfRates of Convergence• Linear convergence• Super linear convergence• Quadratic convergence*1*xxxxkk−≤−−α2*1*xxxxkk−≤−−α∞→→−≤−−−−kxxxxkkkk as 01*11*αα*0*xxxxkk−≤−αRates of Convergence• Linear convergence– Bisection (with α=1/2)• Super linear convergence– Secant method if x* is simple• Quadratic convergence– Newton-Raphson method if x* is simple*1*xxxxkk−≤−−α2*1*xxxxkk−≤−−α∞→→−≤−−−−kxxxxkkkk as 01*11*ααYou seek to find a root of a continuous function f(x), and you use the bisection method. Your initial guesses are such that You want to know that your estimated solution satisfiesAbout how many iterations (i.e. k=?)1) ~22) ~203)~2004)~10^51010=−xx5*10−<− xxkOptimization• You seek• The first order optimilalitycondition isx1x2f(x)f(x*)x*x*+εf(x*+ε)min ( ) f x∇=fT(*)x0Example Problem• Here is a leg from a simple robot• If the servo motor starts from the position shown and rotates 45 deg CCW• How far will the “foot”descend?Representing the Geometry-2 -1 0 1 2 3-4-3-2-101fghabcdcea=[0 0 0 1]';b=[1.527 0.556 0 1]';c=[2.277 -1.069 0 1]';d=[0.75 -1.625 0 1]';e=[2.277 -3.069 0 1]';f=[-1.6 -1.3 0 1]';g=[-1.4 -1.75 0 1]';h=[-1.527 -0.556 0 1]';leg=[f g h a b c d c e];names=char('f','g','h','a','b','c','d','c','e'); plot(leg(1,:),leg(2,:),'o-b')axis equalaxis([-2.5 3.5 -4.5 1.5]); for i=1:length(leg)text(leg(1,i)+0.1, leg(2,i)-0.1, names(i))endDefine a Few FunctionsR=@(theta) [cos(theta)