methods for solving nonlinear equations.htm

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

            effectively uses an average derivative just like the one-dimensional 
            secant method. Initially, the <I>n</I> points are constructed from 
            two starting points that are distinct in all <I>n</I> dimensions. 
            Subsequently, as steps are taken, only the <I>n</I> points with the 
            smallest merit function value are kept. It is rare, but possible 
            that steps are collinear and the secant approximation to the 
            Jacobian becomes singular. In this case, the algorithm is restarted 
            with distinct points.</P>
            <P class=Text>The method requires two starting points in each 
            dimension. In fact, if two starting points are given in each 
            dimension, the secant method is the default method except in one 
            dimension, where Brent's method may be chosen as described 
later.</P>
            <P class=MathCaption>This shows the solution of the Rosenbrock 
            problem with the secant method.</P>
            <P class=Input><FONT class=CellLabel>In[8]:=</FONT><IMG height=19 
            src="Methods for Solving Nonlinear Equations.files/1.4_io_214.gif" 
            width=505 align=absMiddle></P>
            <P class=Graphics><IMG height=288 
            src="Methods for Solving Nonlinear Equations.files/1.4_215.gif" 
            width=288 align=absMiddle></P>
            <P class=Output><FONT class=CellLabel>Out[8]=</FONT><IMG height=15 
            src="Methods for Solving Nonlinear Equations.files/1.4_io_216.gif" 
            width=404 align=absMiddle></P>
            <P class=Text>Note that, as compared to Newton's method, many more 
            residual function evaluations are required. However, the method is 
            able to follow the relatively narrow valley without directly using 
            derivative information. </P>
            <P class=MathCaption>This shows the solution of the Rosenbrock 
            problem with Newton's method using finite differences to compute the 
            Jacobian.</P>
            <P class=Input><FONT class=CellLabel>In[35]:=</FONT><IMG height=55 
            src="Methods for Solving Nonlinear Equations.files/1.4_io_217.gif" 
            width=442 align=absMiddle></P>
            <P class=Graphics><IMG height=288 
            src="Methods for Solving Nonlinear Equations.files/1.4_218.gif" 
            width=288 align=absMiddle></P>
            <P class=Output><FONT class=CellLabel>Out[35]=</FONT><IMG height=15 
            src="Methods for Solving Nonlinear Equations.files/1.4_io_219.gif" 
            width=502 align=absMiddle></P>
            <P class=Text>However, when compared to Newton's method with finite 
            differences, the number of residual function evaluations is 
            comparable. For sparse Jacobian matrices with larger problems, the 
            finite difference Newton method will usually be more efficient since 
            the secant method does not take advantage of sparsity in any 
way.</P>
            <P class=Subsection><A name=t:13><A name=c:13>Brent's Method</P>
            <P class=Text>When searching for a real simple root of a real valued 
            function, it is possible to take advantage of the special geometry 
            of the problem, where the function crosses the axis from negative to 
            positive or vice-versa. Brent's method [<A class=Hyperlink 
            href="http://documents.wolfram.com/v5/Built-inFunctions/AdvancedDocumentation/Optimization/UnconstrainedOptimization/1.8.html#Br02">Br02</A>] 
            is effectively a safeguarded secant method that always keeps a point 
            where the function is positive and one where it is negative so that 
            the root is always bracketed. At any given step, a choice is made 
            between an interpolated (secant) step and a bisection in such a way 
            that eventual convergence is guaranteed. </P>
            <P class=Text>If <SPAN class=MR>FindRoot</SPAN> is given two real 
            starting conditions that bracket a root of a real function, then 
            Brent's method will be used. Thus, if you are working in one 
            dimension and can determine initial conditions that will bracket a 
            root, it is often a good idea to do so since Brent's method is the 
            most robust algorithm available for <SPAN 
            class=MR>FindRoot</SPAN>.</P>
            <P class=Text>Even though essentially all of the theory for solving 
            nonlinear equations and local minimization is based on smooth 
            functions, Brent's method is sufficiently robust that you can even 
            get a good estimate for a zero crossing for discontinuous 
            functions.</P>
            <P class=MathCaption>This shows the steps and function evaluations 
            used in an attempt to find the root of a discontinuous function.</P>
            <P class=Input><FONT class=CellLabel>In[10]:=</FONT><IMG height=15 
            src="Methods for Solving Nonlinear Equations.files/1.4_io_220.gif" 
            width=347 align=absMiddle></P>
            <P class=Message><IMG height=31 
            src="Methods for Solving Nonlinear Equations.files/1.4_221.gif" 
            width=403 align=absMiddle></P>
            <P class=Graphics><IMG height=178 
            src="Methods for Solving Nonlinear Equations.files/1.4_222.gif" 
            width=288 align=absMiddle></P>
            <P class=Output><FONT class=CellLabel>Out[10]=</FONT><IMG height=15 
            src="Methods for Solving Nonlinear Equations.files/1.4_io_223.gif" 
            width=379 align=absMiddle></P>
            <P class=Text>The method gives up and issues a message when the root 
            is bracketed very closely, but it is not able to find a value of the 
            function, which is zero. This robustness carries over very well to 
            continuous functions that are very steep.</P>
            <P class=MathCaption>This shows the steps and function evaluations 
            used to find the root of a function that varies rapidly near its 
            root.</P>
            <P class=Input><FONT class=CellLabel>In[11]:=</FONT><IMG height=15 
            src="Methods for Solving Nonlinear Equations.files/1.4_io_224.gif" 
            width=345 align=absMiddle></P>
            <P class=Graphics><IMG height=178 
            src="Methods for Solving Nonlinear Equations.files/1.4_225.gif" 
            width=288 align=absMiddle></P>
            <P class=Output><FONT class=CellLabel>Out[11]=</FONT><IMG height=15 
            src="Methods for Solving Nonlinear Equations.files/1.4_io_226.gif" 
            width=379 align=absMiddle></P>
            <P class=PrevNextTableBottom>
            <TABLE align=right>
              <TBODY>
              <TR>
                <TD><A class=Hyperlink 
                  href="http://documents.wolfram.com/v5/Built-inFunctions/AdvancedDocumentation/Optimization/UnconstrainedOptimization/1.3.html"><IMG 
                  src="Methods for Solving Nonlinear Equations.files/prev-sml.gif" 
                  border=0></A><IMG height=14 
                  src="Methods for Solving Nonlinear Equations.files/prevnextbar.gif" 
                  width=15 align=bottom border=0><A class=Hyperlink 
                  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><!-- end body --><!-- begin footer --><BR 
            clear=all><BR>
            <TABLE cellSpacing=0 cellPadding=0 width="100%" border=0>
              <TBODY>
              <TR>
                <TD vAlign=bottom><A 
                  href="http://documents.wolfram.com/common/cgi/feedback.cgi?askaboutpage=1;destination=7"><IMG 
                  height=27 
                  alt="Any questions about topics on this page? Click here to get an individual response." 
                  src="Methods for Solving Nonlinear Equations.files/questions3.gif" 
                  width=196 border=0></A><IMG height=1 alt="" 
                  src="C:\Documents and Settings\Administrator\&#26700;&#38754;\Methods for Solving Nonlinear Equations.files\spacer(1).gif" 
                  width=30 border=0></TD>
                <TD vAlign=bottom align=right><IMG height=19 alt="" 
                  src="Methods for Solving Nonlinear Equations.files/tab1.gif" 
                  width=11 border=0><A 
                  onmouseover="MM_swapImage('buy','','/images/buy-now-over.gif',0)" 
                  onmouseout=MM_swapImgRestore() 
                  href="http://store.wolfram.com/"><IMG id=buy title="Buy Now" 
                  height=19 alt="Buy Now" 
                  src="Methods for Solving Nonlinear Equations.files/buy-now.gif" 
                  width=68 border=0 name=buy></A><A 
                  onmouseover="MM_swapImage('info','','/images/more-info-over.gif',0)" 
                  onmouseout=MM_swapImgRestore() 
                  href="http://www.wolfram.com/products/"><IMG id=info 
                  title="More Information" height=19 alt="More Information" 
                  src="Methods for Solving Nonlinear Equations.files/more-info.gif" 
                  width=74 border=0 name=info></A><IMG height=19 alt="" 
                  src="Methods for Solving Nonlinear Equations.files/tab-end.gif" 
                  width=7 border=0></TD></TR></TBODY></TABLE></TD>
          <TD></TD></TR>
        <TR>
          <TD></TD>
          <TD></TD></TR>
        <TR>
          <TD width=620><IMG height=1 alt="" 
            src="C:\Documents and Settings\Administrator\&#26700;&#38754;\Methods for Solving Nonlinear Equations.files\spacer(1).gif" 
            width=620></TD>
          <TD></TD></TR></TBODY></TABLE></TD></TR></TBODY></TABLE><BR><BR>
<TABLE cellSpacing=0 cellPadding=0 width=660 border=0>
  <TBODY>
  <TR>
    <TD width=40 rowSpan=2><IMG height=1 alt="" 
      src="C:\Documents and Settings\Administrator\&#26700;&#38754;\Methods for Solving Nonlinear Equations.files\spacer(1).gif" 
      width=40></TD>
    <TD width=620 bgColor=#cccccc><IMG height=1 alt="" 
      src="C:\Documents and Settings\Administrator\&#26700;&#38754;\Methods for Solving Nonlinear Equations.files\spacer(1).gif" 
      width=620></TD></TR>
  <TR>
    <TD>
      <TABLE cellSpacing=0 cellPadding=0 width="100%" border=0>
        <TBODY>
        <TR>
          <TD class=nobr vAlign=top><IMG height=20 alt="" 
            src="Methods for Solving Nonlinear Equations.files/spacer.gif" 
            width=1></TD>
          <TD class=nobr>&nbsp;<A 
            href="http://www.wolfram.com/company/contact.cgi"><SPAN 
            class=copyright>