Difference between revisions of "Nonlinear equations"

From Sutherland_wiki
Jump to: navigation, search
m (→‎Closed Domain Methods === {{Stub|section}} ==== Bisection =)
Line 1: Line 1:
 
== Introduction ==
 
== Introduction ==
−
{{Stub|section}}
 
  
 +
Nonlinear equations arise ubiquitously in science and engineering applications.  There are several key distinctions between linear and nonlinear equations:
 +
; Number of roots (solutions)
 +
: For linear systems of equations there is a single unique solution for a well-posed system.
 +
: For nonlinear equaitons there may be zero to many roots
 +
 +
; Solution Approach
 +
: For linear systems, an exact solutions exist if system is well-posed
 +
: For nonlinear systems, exact solutions are occasionally possible, but not in general.  Solution methods are iterative.
  
  
Line 11: Line 18:
 
must rewrite the equation in ''residual form'':
 
must rewrite the equation in ''residual form'':
  
−
{| border="1" cellpadding="5" cellspacing="0"
+
:{| border="1" cellpadding="5" cellspacing="0"
 
|-
 
|-
 
| Original Equation || Residual Form
 
| Original Equation || Residual Form
 +
|-
 
| <math>f(x)=\alpha</math> || <math>r(x)=f(x)-\alpha</math>
 
| <math>f(x)=\alpha</math> || <math>r(x)=f(x)-\alpha</math>
 
|}
 
|}
Line 23: Line 31:
  
 
== Solving a Single Nonlinear Equation ==
 
== Solving a Single Nonlinear Equation ==
 +
 +
[[Image:nonlinear_categorization.png|right|300px]]
  
 
There are two general classes of techniques for solving nonlinear
 
There are two general classes of techniques for solving nonlinear
Line 31: Line 41:
 
* [[#Open_Domain_Methods|Open domain methods]] - These methods look for a root near a specified initial guess, but are not constrained in the region that they search for a root.  These methods typically converge faster than [[#Closed_Domain_Methods|closed domain methods]], ''if'' the initial guess is "close enough" to the root.
 
* [[#Open_Domain_Methods|Open domain methods]] - These methods look for a root near a specified initial guess, but are not constrained in the region that they search for a root.  These methods typically converge faster than [[#Closed_Domain_Methods|closed domain methods]], ''if'' the initial guess is "close enough" to the root.
  
 +
<br style="clear:both" />
  
  
 
=== Closed Domain Methods ===
 
=== Closed Domain Methods ===
 
{{Stub|section}}
 
{{Stub|section}}
 +
 +
 
==== Bisection ====
 
==== Bisection ====
 +
 +
The bisection technique is fairly straightforward.  Given an interval <math>x=[a,b]</math> that contains the root <math>f(x)=0</math>, we proceed as follows:
 +
# Set <math>c=(a+b)/2</math>.  We now have two intervals: <math>[a,c]</math> and <math>[c,b]</math>.
 +
# calculate <math>f(c)</math>
 +
# choose the interval containing a sign change.  In other words: if <math>f(a) \cdot f(c) < 0</math> then we know a sign change occured on the interval <math>[a,c]</math> and we select that interval.  Otherwise we select the interval <math>[c,b]</math>
 +
# Return to step 1.
 +
 +
The following Matlab code implements the bisection algorithm:
 +
 +
:{| border="1" cellpadding="5"
 +
|-
 +
|<source lang="matlab">
 +
function x = bisect( fname, a, b, tol )
 +
% function x = bisect( fname, a, b, tol )
 +
%
 +
% fname - the name of the function we are solving
 +
% a    - lower bound of interval containing the root
 +
% b    - upper bound of interval containing the root
 +
% tol  - solution tolerance (absolute)
 +
 +
err = 10*tol;
 +
 +
while err>tol
 +
  fa = feval(fname,a);
 +
  c = 0.5*(a+b);
 +
  fc = feval(fname,c);
 +
  err = abs(fc);
 +
  if fc*fa<0
 +
      % f(c) is of opposite sign from f(a).
 +
      % This means that a and c now bracket
 +
      % the root. Set up for the next pass.
 +
      b = c;
 +
  else
 +
      % f(c) is of same sign as f(a).  Thus, b and
 +
      % c bracket the root. Set up for next pass.
 +
      a = c;
 +
  end
 +
end
 +
 +
% set the return value
 +
x=0.5*(a+b);
 +
</source>
 +
|}
 +
 +
;Example:
 +
: Solve <math>y=\exp(-x)\sin(5x)</math> for <math>y=0.5</math>.  Look for a root on the interval [0,1].
 +
 +
We proceed as follows:
 +
# Write the equation in residual form: <math>r(x) = 5-\exp(-x)\sin(5x)</math>
 +
# Determine the interval that we want to search for the root.
 +
 +
{|
 +
|---------------------------------+---|
 +
| [[Image:bisect_demo_iter0.png]]
 +
|                                | {|
 +
                                  ! Iteration !! a !! b !! c !! residual
 +
                                  |-
 +
                                  | 1 || 0.0 || 1.0 || 0.5 || 0.36
 +
                                  |-
 +
                                  | 2 || 0.5 || 1.0 || 0.75 || -0.27
 +
                                  |-
 +
                                  | 3 || 0.5 || 0.75 || 0.625 || 0.0089
 +
                                  |-
 +
                                  | 4 || 0.625 || 0.75 || 0.6875 || -0.15
 +
                                  |-
 +
                                  | 5 || 0.625 || 0.6875 || 0.6562 || -0.072
 +
                                  |-
 +
                                  | 6 || 0.6250 || 0.6562 || 0.6406 || -0.032
 +
                                  |-
 +
                                  | 7 || 0.6250 || 0.6406 || 0.6328 || -0.012
 +
                                  |-
 +
                                  | 8 || 0.6250 || 0.6328 || 0.6289 || -0.0016
 +
                                  |}
 +
| }
 +
 +
 
==== Regula Falsi ====
 
==== Regula Falsi ====
 +
 +
  
 
=== Open Domain Methods ===
 
=== Open Domain Methods ===

Revision as of 11:13, 5 August 2009

Introduction

Nonlinear equations arise ubiquitously in science and engineering applications. There are several key distinctions between linear and nonlinear equations:

Number of roots (solutions)
For linear systems of equations there is a single unique solution for a well-posed system.
For nonlinear equaitons there may be zero to many roots
Solution Approach
For linear systems, an exact solutions exist if system is well-posed
For nonlinear systems, exact solutions are occasionally possible, but not in general. Solution methods are iterative.


Residual Form

Typically when solving a nonlinear equation we solve for its roots - i.e. where the equation equals zero. In some cases we want to solve an equation for where f(x)=\alpha. In such a case, we must rewrite the equation in residual form:

Original Equation Residual Form
f(x)=\alpha r(x)=f(x)-\alpha

For example, if we wanted to solve y=x^2\sin(x) for the value of x where y=3, we would solve for the roots of the function r(x)=x^2\sin(x)-3.


Solving a Single Nonlinear Equation

Nonlinear categorization.png

There are two general classes of techniques for solving nonlinear equations:

  • Closed domain methods - These methods look for a root inside a specified interval by iteratively shrinking the interval containing the root. These methods are typically more robust than open domain methods, but are somewhat slower to converge, and require that you be able to bracket the root.
  • Open domain methods - These methods look for a root near a specified initial guess, but are not constrained in the region that they search for a root. These methods typically converge faster than closed domain methods, if the initial guess is "close enough" to the root.



Closed Domain Methods

Warn.jpg
This section is a stub and needs to be expanded.
If you can provide information or finish this section you're welcome to do so and then remove this message afterwards.


Bisection

The bisection technique is fairly straightforward. Given an interval x=[a,b] that contains the root f(x)=0, we proceed as follows:

  1. Set c=(a+b)/2. We now have two intervals: [a,c] and [c,b].
  2. calculate f(c)
  3. choose the interval containing a sign change. In other words: if f(a) \cdot f(c) < 0 then we know a sign change occured on the interval [a,c] and we select that interval. Otherwise we select the interval [c,b]
  4. Return to step 1.

The following Matlab code implements the bisection algorithm: 

function x = bisect( fname, a, b, tol )
% function x = bisect( fname, a, b, tol )
%
% fname - the name of the function we are solving
% a     - lower bound of interval containing the root
% b     - upper bound of interval containing the root
% tol   - solution tolerance (absolute)
 
err = 10*tol;
 
while err>tol
   fa = feval(fname,a);
   c = 0.5*(a+b);
   fc = feval(fname,c);
   err = abs(fc);
   if fc*fa<0
      % f(c) is of opposite sign from f(a).
      % This means that a and c now bracket
      % the root. Set up for the next pass.
      b = c;
   else
      % f(c) is of same sign as f(a).  Thus, b and
      % c bracket the root. Set up for next pass.
      a = c;
   end
end
 
% set the return value
x=0.5*(a+b);
Example
Solve y=\exp(-x)\sin(5x) for y=0.5. Look for a root on the interval [0,1].

We proceed as follows:

  1. Write the equation in residual form: r(x) = 5-\exp(-x)\sin(5x)
  2. Determine the interval that we want to search for the root.
Error creating thumbnail: Unable to save thumbnail to destination
 {| Iteration a b c residual
1 0.0 1.0 0.5 0.36
2 0.5 1.0 0.75 -0.27
3 0.5 0.75 0.625 0.0089
4 0.625 0.75 0.6875 -0.15
5 0.625 0.6875 0.6562 -0.072
6 0.6250 0.6562 0.6406 -0.032
7 0.6250 0.6406 0.6328 -0.012
8 0.6250 0.6328 0.6289 -0.0016

| }


Regula Falsi

Open Domain Methods

Warn.jpg
This section is a stub and needs to be expanded.
If you can provide information or finish this section you're welcome to do so and then remove this message afterwards.

Secant Method

Newton's Method

Solving a System of Nonlinear Equations

Warn.jpg
This section is a stub and needs to be expanded.
If you can provide information or finish this section you're welcome to do so and then remove this message afterwards.

Newton's Method

Solution Approaches: Single Nonlinear Equation

Excel

To solve a nonlinear equation in Excel, we have to options:

  • Goal Seek is a simple way to solve a single nonlinear equation.
  • Solver is a more powerful way to solve a nonlinear equation. It can also perform minimization, maximization, and can solve systems of nonlinear equations as well.

Goal Seek

Warn.jpg
This section is a stub and needs to be expanded.
If you can provide information or finish this section you're welcome to do so and then remove this message afterwards.

Solver

Warn.jpg
This section is a stub and needs to be expanded.
If you can provide information or finish this section you're welcome to do so and then remove this message afterwards.


Matlab

To solve a single nonlinear equation in Matlab, we use the fzero function. If, however, we are solving for the roots of a polynomial, we can use the roots function. This will solve for all of the polynomial roots (both real and imaginary).

ROOTS

The roots function can be used to obtain all of the roots (both real and imaginary) of a polynomial 

  xroots = roots( coefs );
  • coefs are the polynomial coefficients, in descending order.
  • xroots is a vector containing all of the polynomial roots.

For example, consider the quadratic equation y=3x^2-2x+1. From the quadratic formula, we can identify the roots as

x = \frac{1 \pm i\sqrt{2}}{3}

where i\equiv\sqrt{-1} is the imaginary number.

Using the roots function we have 

 x = roots( [3 -2 1] );

which gives 

 x =
  0.3333 + 0.4714i
  0.3333 - 0.4714i

This is equivalent to the answer above obtained via the quadratic formula.


FZERO

In Matlab, fzero is the most flexible way to find the roots of a nonlinear equation. Its syntax is slightly different depending on the type of function we are using:

  • For a function stored in an m-file named myFunction.m we use
x = fzero( 'myFunction', xguess );

x = fzero( fun, xguess );
  • For a built in function (like <tt>sin, exp, etc.)
x = fzero( @sin, xguess );

Note that fzero can only find real roots. Therefore, if we tried to use it on the quadratic function y=3x^2-2x+1, it would fail. To demonstrate its usage, let's solve for the roots of the function

y=3x^2-2x-1

From the quadratic formula, or by factoring this equation, we know that its roots should be x=-1/3 and x=1.

To use fzero to solve this, we could use an anonymous function: 

f = @(x)(3*x.^2-2*x-1);
x1 = fzero( f, -2 ); % start looking for the root at -2.0
x2 = fzero( f,  2 ); % start looking for the root at 2.0

This results in x1=-0.33333 and x2=1. Note that here we found the two roots by using different initial guesses. Of course it helps to know where the roots are so that you can supply decent initial guesses!

To solve this using a m-file, first create the function you will use:

myQuadratic.m 
function y = myQuadratic(x)
y = 3*x.^2 - 2*x -1

Save this in a file myQuadratic.m and then use fzero: 

x1 = fzero( 'myQuadratic', -2.0 );  % start looking for the root at -2.0
x2 = fzero( 'myQuadratic',  2.0 );  % start looking for the root at 2.0


FMINSEARCH

Occasionally we want to maximize or minimize a function. Matlab provides a tool called fminsearch to do this. It searches for the minimum of a function near a starting guess. As with fzero, you use this in different ways depending on what kind of function you are minimizing: 

 x = fminsearch( 'myFun', xo );  % when using a function in an m-file
 x = fminsearch( myFun,   xo );  % when using an anonymous function
 x = fminsearch( @myFun,  xo );  % when using a built-in function
Warn.jpg
This section is a stub and needs to be expanded.
If you can provide information or finish this section you're welcome to do so and then remove this message afterwards.



Solution Approaches: System of Nonlinear Equations

Warn.jpg
This section is a stub and needs to be expanded.
If you can provide information or finish this section you're welcome to do so and then remove this message afterwards.

Excel

Solver...

Matlab

fsolve

Retrieved from "https://sutherland.che.utah.edu/wiki/index.php?title=Nonlinear_equations&oldid=389"