methods for solving nonlinear equations.htm

非线性方程求根的理论讲解

                  href="http://documents.wolfram.com/v5/Built-inFunctions/AdvancedDocumentation/Optimization/UnconstrainedOptimization/1.5.html"><IMG 
                  src="Methods for Solving Nonlinear Equations.files/next-sml.gif" 
                  border=0></A></TD></TR></TBODY></TABLE></P>
            <DIV class=Text>&nbsp;</DIV>
            <P class=Section><A name=t:10><A name=c:10>Methods for Solving 
            Nonlinear Equations</P>
            <P class=Text>There are some close connections between finding a 
            local minimum and solving a set of nonlinear equations. Given a set 
            of <I>n</I> equations in <I>n</I> unknowns, seeking a solution <IMG 
            height=14 
            src="Methods for Solving Nonlinear Equations.files/1.4_i_191.gif" 
            width=45 align=absMiddle> is equivalent to minimizing the sum of 
            squares <IMG height=14 
            src="Methods for Solving Nonlinear Equations.files/1.4_i_192.gif" 
            width=41 align=absMiddle> when the residual is zero at the minimum, 
            so there is a particularly close connection to the Gauss-Newton 
            methods. In fact, the Gauss-Newton step for local minimization and 
            the Newton step for nonlinear equations are exactly the same. Also, 
            for a smooth function, Newton's method for local minimization is the 
            same as Newton's method for the nonlinear equations <IMG height=14 
            src="Methods for Solving Nonlinear Equations.files/1.4_i_193.gif" 
            width=38 align=absMiddle>. Not surprisingly, then, many aspects of 
            the algorithms are similar. Nonetheless there are also important 
            differences.</P>
            <P class=Text>Another thing in common with minimization algorithms 
            is the need for some kind of step control. Typically, step control 
            is based on the same methods as minimization except that they are 
            applied to a merit function, usually the smooth 2-norm squared, <IMG 
            height=14 
            src="Methods for Solving Nonlinear Equations.files/1.4_i_194.gif" 
            width=41 align=absMiddle>.</P>
            <P class=DefinitionBox><IMG height=150 
            src="Methods for Solving Nonlinear Equations.files/1.4_195.gif" 
            width=580 align=absMiddle></P>
            <P class=Caption>Basic method choices for <SPAN 
            class=MR>FindRoot</SPAN>.</P>
            <P class=Subsection><A name=t:11><A name=c:11>Newton's Method</P>
            <P class=Text>Newton's method for nonlinear equations is based on a 
            linear approximation</P>
            <P class=DisplayMath>r(x)=Mk(p) = r(xk)+J(xk) p, p = (x - xk)</P>
            <P class=Text>so the Newton step is found simply by setting <IMG 
            height=14 
            src="Methods for Solving Nonlinear Equations.files/1.4_i_196.gif" 
            width=55 align=absMiddle>, </P>
            <P class=DisplayMath>J(xk) pk = -r(xk).</P>
            <P class=Text>Near a root of the equations, Newton's method has 
            q-quadratic convergence, similar to the Newton's method for 
            minimization. Newton's method is used as the default method for 
            <SPAN class=MR>FindRoot</SPAN>. </P>
            <P class=Text>Newton's method can be used with either <A 
            class=Hyperlink 
            href="http://documents.wolfram.com/v5/Built-inFunctions/AdvancedDocumentation/Optimization/UnconstrainedOptimization/1.5.html#LineSearch">line 
            search</A> or <A class=Hyperlink 
            href="http://documents.wolfram.com/v5/Built-inFunctions/AdvancedDocumentation/Optimization/UnconstrainedOptimization/1.5.html#TrustRegion">trust 
            region</A> step control. When it works, the line search control is 
            typically faster, but the trust region approach is usually more 
            robust.</P>
            <P class=MathCaption>Here is Rosenbrock's problem as a <SPAN 
            class=MR>FindRoot</SPAN> problem.</P>
            <P class=Input><FONT class=CellLabel>In[1]:=</FONT><IMG height=15 
            src="Methods for Solving Nonlinear Equations.files/1.4_io_197.gif" 
            width=271 align=absMiddle></P>
            <P class=Output><FONT class=CellLabel>Out[1]=</FONT><IMG height=17 
            src="Methods for Solving Nonlinear Equations.files/1.4_io_198.gif" 
            width=571 align=absMiddle></P>
            <P class=MathCaption>This finds the solution of the nonlinear system 
            using the default line search approach. (Newton's method is the 
            default method for <SPAN class=MR>FindRoot</SPAN>.)</P>
            <P class=Input><FONT class=CellLabel>In[2]:=</FONT><IMG height=15 
            src="Methods for Solving Nonlinear Equations.files/1.4_io_199.gif" 
            width=122 align=absMiddle></P>
            <P class=Graphics><IMG height=288 
            src="Methods for Solving Nonlinear Equations.files/1.4_200.gif" 
            width=288 align=absMiddle></P>
            <P class=Output><FONT class=CellLabel>Out[2]=</FONT><IMG height=15 
            src="Methods for Solving Nonlinear Equations.files/1.4_io_201.gif" 
            width=502 align=absMiddle></P>
            <P class=Text>Note that each of the line searches started along the 
            line <I>x</I> == 1. This is a particular property of the Newton step 
            for this particular problem.</P>
            <P class=MathCaption>This computes the Jacobian and the Newton step 
            symbolically for the Rosenbrock problem.</P>
            <P class=Input><FONT class=CellLabel>In[3]:=</FONT><IMG height=39 
            src="Methods for Solving Nonlinear Equations.files/1.4_io_202.gif" 
            width=343 align=absMiddle></P>
            <P class=Output><FONT class=CellLabel>Out[4]=</FONT><IMG height=17 
            src="Methods for Solving Nonlinear Equations.files/1.4_io_203.gif" 
            width=137 align=absMiddle></P>
            <P class=Text>When this step is added to the point, <IMG height=14 
            src="Methods for Solving Nonlinear Equations.files/1.4_i_204.gif" 
            width=42 align=absMiddle>, it is easy to see why the steps go to the 
            line <IMG height=14 
            src="Methods for Solving Nonlinear Equations.files/1.4_i_205.gif" 
            width=36 align=absMiddle>. This is a particular feature of this 
            problem, which is not typical for most functions. Because the trust 
            region approach does not try the Newton step unless it lies within 
            the region bound, this feature does not show up so strongly when the 
            trust region step control is used.</P>
            <P class=MathCaption>This finds the solution of the nonlinear system 
            using the trust region approach. The search is almost identical to 
            the <A class=Hyperlink 
            href="http://documents.wolfram.com/v5/Built-inFunctions/AdvancedDocumentation/Optimization/UnconstrainedOptimization/1.3.html#GNRosenbrock">search</A> 
            with the Gauss-Newton method for the Rosenbrock objective function 
            in <SPAN class=MR>FindMinimum</SPAN>.</P>
            <P class=Input><FONT class=CellLabel>In[5]:=</FONT><IMG height=15 
            src="Methods for Solving Nonlinear Equations.files/1.4_io_206.gif" 
            width=522 align=absMiddle></P>
            <P class=Graphics><IMG height=288 
            src="Methods for Solving Nonlinear Equations.files/1.4_207.gif" 
            width=288 align=absMiddle></P>
            <P class=Output><FONT class=CellLabel>Out[5]=</FONT><IMG height=15 
            src="Methods for Solving Nonlinear Equations.files/1.4_io_208.gif" 
            width=502 align=absMiddle></P>
            <P class=Text>When the structure of the Jacobian matrix is sparse, 
            <I>Mathematica</I> will use <SPAN class=MR>SparseArray</SPAN> 
            objects both to compute the Jacobian and to handle the necessary 
            numerical linear algebra. </P>
            <P class=Text>When solving nonlinear equations is used as a part of 
            a more general numerical procedure, such as solving differential 
            equations with implicit methods, often starting values are quite 
            good and complete convergence is not absolutely necessary. Often the 
            most expensive part of computing a Newton step is finding the 
            Jacobian and computing a matrix factorization. However, when close 
            enough to a root, it is possible to leave the Jacobian frozen for a 
            few steps (though this does certainly affect the convergence rate). 
            You can do this in <I>Mathematica</I> using the method option <SPAN 
            class=MR>"UpdateJacobian"</SPAN>, which gives the number of steps to 
            go before updating the Jacobian. The default is <SPAN 
            class=MR>"UpdateJacobian" -&gt; 1</SPAN> so the Jacobian is updated 
            every step.</P>
            <P class=MathCaption>This shows the number of steps, function 
            evaluations, and Jacobian evaluations, required to find a simple 
            square root when the Jacobian is only updated every three steps.</P>
            <P class=Input><FONT class=CellLabel>In[6]:=</FONT><IMG height=63 
            src="Methods for Solving Nonlinear Equations.files/1.4_io_209.gif" 
            width=580 align=absMiddle></P>
            <P class=Output><FONT class=CellLabel>Out[6]=</FONT><IMG height=15 
            src="Methods for Solving Nonlinear Equations.files/1.4_io_210.gif" 
            width=159 align=absMiddle></P>
            <P class=MathCaption>This shows the number of steps, function 
            evaluations and Jacobian evaluations required to find a simple 
            square root when the Jacobian is updated every step.</P>
            <P class=Input><FONT class=CellLabel>In[7]:=</FONT><IMG height=47 
            src="Methods for Solving Nonlinear Equations.files/1.4_io_211.gif" 
            width=556 align=absMiddle></P>
            <P class=Output><FONT class=CellLabel>Out[7]=</FONT><IMG height=15 
            src="Methods for Solving Nonlinear Equations.files/1.4_io_212.gif" 
            width=159 align=absMiddle></P>
            <P class=Text>Of course for a simple one-dimensional root, updating 
            the Jacobian is trivial in cost, so holding the update is only of 
            use here to demonstrate the idea.</P>
            <P class=DefinitionBox3Col><IMG height=132 
            src="Methods for Solving Nonlinear Equations.files/1.4_213.gif" 
            width=580 align=absMiddle></P>
            <P class=Caption>Method options for <SPAN 
            class=MR>Method-&gt;"Newton"</SPAN> in <SPAN 
            class=MR>FindRoot</SPAN>.</P>
            <P class=Subsection><A name=t:12><A name=c:12>The Secant Method</P>
            <P class=Text>When derivatives cannot be computed symbolically, 
            Newton's method will be used, but with a finite difference 
            approximation to the Jacobian. This can have cost in terms of both 
            time and reliability. Just as for minimization, an alternative is to 
            use an algorithm specifically designed to work without derivatives. 
            </P>
            <P class=Text>In one dimension, the idea of the secant method is to 
            use the slope of the line between two consecutive search points to 
            compute the step instead of the derivative at the latest point. 
            Similarly in <I>n</I>-dimensions, differences between the residuals 
            at <I>n</I> points are used to construct an approximation of sorts 
            to the Jacobian. Note that this is similar to finite differences, 
            but rather than trying to make the difference interval small in 
            order to get as good a Jacobian approximation as possible, it