Newton Algorithm: Difference between revisions

From OpenSeesWiki
Jump to navigation Jump to search
No edit summary
No edit summary
Line 23: Line 23:
THEORY:
THEORY:


The Newton (also known as Newton-Raphson) method is the most widely used and robust method for slving nonlinear algrebraic equations. The Newton method used in finite element analysis is identical to that taught in basic calculus courses. The method as taught in basic calculus, is a root-finding algorithm that uses the first few terms of the Taylor series of a function f(x) in the vicinity of a suspected root to find the root. Newton's method is sometimes also known as Newton's iteration, although in this work the latter term is reserved to the application of Newton's method for computing square roots.
The Newton (also known as Newton-Raphson) method is the most widely used and robust method for solving nonlinear algebraic equations. The Newton method used in finite element analysis is identical to that taught in basic calculus courses. It is just extended for the n unknown degrees-of-freedom. The method as taught in basic calculus, is a root-finding algorithm that uses the first few terms of the Taylor series of a function f(x) in the vicinity of a suspected root <math>x_n</math> to find the root <math>x_{n+1}</math>. Newton's method is sometimes also known as Newton's iteration, although in this work the latter term is reserved to the application of Newton's method for computing square roots.


The Taylor series of <math>F(x)</math> about the point <math>x=x_0+\epsilon</math> is given by
The Taylor series of <math>r(x)\,\!</math> about the point <math>x=x_n+\Delta x\,\!</math> is given by


:<math>f(x_0+\epsilon) = f(x_0)+f^{'}(x_0)\epsilon + 1/2f^{''}(x_0) \epsilon^2+....</math>
:<math>f(x_n+\Delta x) = f(x_n)+r^{'}(x_n)\Delta x + 1/2r^{''}(x_n) \Delta x^2+....\,\!</math>


Keeping terms only to first order,
Keeping terms only to first order,


:<math>f(x_0+\epsilon) \approx f(x_0)+f^'(x_0)\epsilon </math>
:<math>f(x_n+\Delta x) \approx f(x_n)+r^'(x_n)\Delta x  = f(x_n)+ \frac{df(x_n)}{dx}\Delta x</math>  


and since at the root we wish to find <math>x_0 + \epsilon</math>, the function equates to 0, <math>f(x_0+\epsilon) = 0</math>, we can solve for an approximate <math>\epsilon</math>
and since at the root we wish to find <math>x_n + \Delta x</math>, the function equates to 0, i.e. <math>f(x_n+\Delta x) = 0</math>, we can solve for an approximate <math>\Delta x</math>


:<math> \epsilon \approx - \frac{f(x_0)}{f'(x_0)}</math>
:<math> \Delta x \approx -\frac{f(x_n)}{f^'(x_n)} = - \frac{df(x_n)}{dx}^{-1}f(x_n)</math>
 
The Newmark method is thus an iterative method in which we keep iterating until <math>\Delta x</math> is small enough.
 
:<math> \Delta x = - \frac{df(x_n)}{dx}^{-1}f(x_n)</math>
 
:<math> x_{n+1} = x_n + \Delta x\,\!</math>


The Newmark method is thus an iterative method in which we keep iterating until <math>\epsilon</math> is small enough.


The process starts with an initial guess <math>x_0</math> and providing the function is well behaved we arrive at a better approx <math>x_1</math>
The process starts with an initial guess <math>x_0</math> and providing the function is well behaved we arrive at a better approx <math>x_1</math>


:<math>x_{1} = x_0 - \frac{f(x_0)}{f'(x_0)}.\,\!</math>
:
 
The method is generalized to n unknowns by replacing the above scalar equations with matrix ones.
 
:<math>R(U_n+\Delta x) = R(U_n)+\frac{\partial R(U_n)}{\partial U} \Delta U + O(\Delta U ^2) \,\!</math>  


and so on ...
The matrix <math>\frac{\partial R(U_n)}{\partial U}\,\!</math> is called the system Jacobian matrix and will be denoted K:


:<math>x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}.\,\!</math>
<math>K = \frac{\partial R(U_n)}{\partial U}\,\!</math>




The method is generalized to n unknowns by replacing the above scalar equations with matrix ones.
resulting in our iterative procedure:
 
:<math> \Delta U = - K^{-1}R(U_n)</math>
 
:<math> U_{n+1} = U_n + \Delta U\,\!</math>
 


----
----


Code Developed by: <span style="color:blue"> fmk </span>
Code Developed by: <span style="color:blue"> fmk </span>

Revision as of 01:19, 3 March 2010



This command is used to construct a NewtonRaphson algorithm object. The command is of the follwoing form:

algorithm Newton


NOTES:


REFERENCES:

Read the page at Wikipedia

THEORY:

The Newton (also known as Newton-Raphson) method is the most widely used and robust method for solving nonlinear algebraic equations. The Newton method used in finite element analysis is identical to that taught in basic calculus courses. It is just extended for the n unknown degrees-of-freedom. The method as taught in basic calculus, is a root-finding algorithm that uses the first few terms of the Taylor series of a function f(x) in the vicinity of a suspected root <math>x_n</math> to find the root <math>x_{n+1}</math>. Newton's method is sometimes also known as Newton's iteration, although in this work the latter term is reserved to the application of Newton's method for computing square roots.

The Taylor series of <math>r(x)\,\!</math> about the point <math>x=x_n+\Delta x\,\!</math> is given by

<math>f(x_n+\Delta x) = f(x_n)+r^{'}(x_n)\Delta x + 1/2r^{}(x_n) \Delta x^2+....\,\!</math>

Keeping terms only to first order,

<math>f(x_n+\Delta x) \approx f(x_n)+r^'(x_n)\Delta x = f(x_n)+ \frac{df(x_n)}{dx}\Delta x</math>

and since at the root we wish to find <math>x_n + \Delta x</math>, the function equates to 0, i.e. <math>f(x_n+\Delta x) = 0</math>, we can solve for an approximate <math>\Delta x</math>

<math> \Delta x \approx -\frac{f(x_n)}{f^'(x_n)} = - \frac{df(x_n)}{dx}^{-1}f(x_n)</math>

The Newmark method is thus an iterative method in which we keep iterating until <math>\Delta x</math> is small enough.

<math> \Delta x = - \frac{df(x_n)}{dx}^{-1}f(x_n)</math>
<math> x_{n+1} = x_n + \Delta x\,\!</math>


The process starts with an initial guess <math>x_0</math> and providing the function is well behaved we arrive at a better approx <math>x_1</math>

The method is generalized to n unknowns by replacing the above scalar equations with matrix ones.

<math>R(U_n+\Delta x) = R(U_n)+\frac{\partial R(U_n)}{\partial U} \Delta U + O(\Delta U ^2) \,\!</math>

The matrix <math>\frac{\partial R(U_n)}{\partial U}\,\!</math> is called the system Jacobian matrix and will be denoted K:

<math>K = \frac{\partial R(U_n)}{\partial U}\,\!</math>


resulting in our iterative procedure:

<math> \Delta U = - K^{-1}R(U_n)</math>
<math> U_{n+1} = U_n + \Delta U\,\!</math>


Code Developed by: fmk

Retrieved from "https://opensees.ist.berkeley.edu/wiki/index.php?title=Newton_Algorithm&oldid=2703"