CSE 245: Computer Aided Circuit
Simulation and Verification
Fall 2004, Nov
Nonlinear Equation
Outline
Nonlinear problems
Iterative Methods
Newton’s Method
Derivation of Newton
Quadratic Convergence
Examples
Convergence Testing
Multidimensonal Newton Method
Basic Algorithm
Quadratic convergence
Application to circuits
Improve Convergence
Limiting Schemes
Direction Corrupting
Non corrupting (Damped Newton)
Continuation Schemes
Source stepping
June 7, 2018 2 courtesy Alessandra Nardi UCB
Nonlinear Problems - Example
1
Vd
I1 Ir Id I d I s (e Vt
1) 0
Need to Solve
I r I d I1 0
e1
1
e1 I s (e 1) I1 0
Vt
g (e1 ) I1
R
June 7, 2018 3 courtesy Alessandra Nardi UCB
Nonlinear Equations
Given g(V)=I
It can be expressed as: f(V)=g(V)-I
Solve g(V)=I equivalent to solve
f(V)=0
Hard to find analytical solution for f(x)=0
Solve iteratively
June 7, 2018 4 courtesy Alessandra Nardi UCB
Nonlinear Equations – Iterative Methods
Start from an initial value x0
Generate a sequence of iterate xn-1,
xn, xn+1 which hopefully converges to
the solution x*
Iterates are generated according to
an iteration function F: xn+1=F(xn)
Ask
• When does it converge to correct solution ?
• What is the convergence rate ?
June 7, 2018 5 courtesy Alessandra Nardi UCB
Newton-Raphson (NR) Method
Consists of linearizing the system.
Want to solve f(x)=0 Replace f(x) with its
linearized version and solve.
df *
f ( x) f ( x ) ( x )( x x* )
*
Taylor Ser ies
dx
k 1 df k k 1 k
f ( x ) f ( x ) ( x )( x x )
k
dx
1
k 1 df k
x x ( x ) f ( x k )
k
Iteration function
dx
Note: at each step need to evaluate f and f’
June 7, 2018 6 courtesy Alessandra Nardi UCB
Newton-Raphson Method – Graphical View
June 7, 2018 7 courtesy Alessandra Nardi UCB
Newton-Raphson Method – Algorithm
Define iteration
Do k = 0 to ….
1
k 1 df k
x x ( x ) f ( x k )
k
dx
until convergence
How about convergence?
An iteration {x(k)} is said to converge with order q if
there exists a vector norm such that for each k N:
k 1 q
June 7, 2018 x xˆ 8x xˆ
k
courtesy Alessandra Nardi UCB
Newton-Raphson Method – Convergence
2
df d f
0 f ( x ) f ( x ) ( x )( x x ) 2 ( x)( x* x k ) 2
* k k * k
dx dx
some x [ x k , x* ]
Mean Value theorem
truncates Taylor series
But
df k k 1 k by Newton
0 f ( x ) ( x )( x x )
k
dx definition
June 7, 2018 9 courtesy Alessandra Nardi UCB
Newton-Raphson Method – Convergence
df k k 1 * d 2 f
Subtracting ( x )( x x ) 2 ( x)( x x )
k * 2
dx d x
2
k 1 df k 1 d f
Dividing through ( x x ) [ ( x )]
*
2
( x )( x k
x * 2
)
dx d x
df k 1 d 2 f
Let [ ( x )] 2
( x ) K k
dx d x
k 1 * 2
then x x K x x
* k k
Convergence is quadratic
June 7, 2018 10 courtesy Alessandra Nardi UCB
Newton-Raphson Method – Convergence
Local Convergence Theorem
If
df
a) bounded away from zero
dx
K is bounded
d2 f
b) bounded
dx 2
Then Newton’s method converges given a
sufficiently close initial guess (and
convergence is quadratic)
June 7, 2018 11 courtesy Alessandra Nardi UCB
Newton-Raphson Method – Convergence
Example 1
f ( x) x 2 1 0, find x ( x* 1)
df k
( x ) 2 xk
dx
k
2x (x k 1
x ) x
k
k
2
1
x
2 2
k 1
k
2x (x x ) 2x (x x ) x
* k * k k *
k 1 1
or ( x x ) k ( x k x* ) 2
*
2x Convergence is quadratic
June 7, 2018 12 courtesy Alessandra Nardi UCB
Newton-Raphson Method – Convergence
Example 2
f ( x) x 0, x 0
2 *
1
df
df k Note : not bounded
(x ) 2 x k
dx
dx away from zero
k 1
2 x ( x 0) ( x 0)
k k 2
k 1
x 0 x 0
2
1 k
for x k x* 0
1
or ( xk 1 x ) ( xk x )
* *
2
Convergence is linear
June 7, 2018 13 courtesy Alessandra Nardi UCB
Newton-Raphson Method – Convergence
Example 1,2
June 7, 2018 14 courtesy Alessandra Nardi UCB
Newton-Raphson Method – Convergence
x = Initial Guess, k 0
0
Repeat {
f x k
x
x k 1 x k f x k
k k 1
} Until ?
x k 1
x threshold ?
k
f x k 1
threshold ?
June 7, 2018 15 courtesy Alessandra Nardi UCB
Newton-Raphson Method – Convergence
Convergence Check
Need a "delta-x" check to avoid false convergence
f(x)
x k 1
x xa xr x
k k 1
k 1 k *
x x x X
f x k 1 fa
June 7, 2018 16 courtesy Alessandra Nardi UCB
Newton-Raphson Method – Convergence
Convergence Check
Also need an "f x " check to avoid false convergence
f(x)
f x k 1
fa
*
x
X
x k 1 x k
x k 1
x xa xr x
k k 1
June 7, 2018 17 courtesy Alessandra Nardi UCB
Newton-Raphson Method – Convergence
demo2
June 7, 2018 18 courtesy Alessandra Nardi UCB
Newton-Raphson Method – Convergence
Local Convergence
Convergence Depends on a Good Initial Guess
f(x)
1 1
x x
2 0 0 X
x x x
June 7, 2018 19 courtesy Alessandra Nardi UCB
Newton-Raphson Method – Convergence
Local Convergence
Convergence Depends on a Good Initial Guess
June 7, 2018 20 courtesy Alessandra Nardi UCB
Nonlinear Problems – Multidimensional Example
v1 i2 + v2b - v2 Nodal Analysis
i1 i3 At Node 1: i1 i2 0
+ + g v1 g v1 v2 0
b b
v v
1 3
At Node 2: i3 i2 0
- - g v3 g v1 v2 0
Nonlinear
Resistors Two coupled
i g v nonlinear equations
in two unknowns
June 7, 2018 21 courtesy Alessandra Nardi UCB
Outline
Nonlinear problems
Iterative Methods
Newton’s Method
Derivation of Newton
Quadratic Convergence
Examples
Convergence Testing
Multidimensonal Newton Method
Basic Algorithm
Quadratic convergence
Application to circuits
Improve Convergence
Limiting Schemes
Direction Corrupting
Non corrupting (Damped Newton)
Continuation Schemes
Source stepping
June 7, 2018 22 courtesy Alessandra Nardi UCB
Multidimensional Newton Method
Problem: Find x such that F x 0
*
*
x
* N
and F : N
N
F ( x) F ( x ) J ( x )( x x )
* * *
Taylor Ser ies
F1 ( x) F1 ( x)
x
x
1 N
J ( x) Jacobian Matrix
FN ( x) FN ( x)
x1 x N
k 1 k 1
x x J (x ) F (x )
k k
Iteration function
June 7, 2018 23 courtesy Alessandra Nardi UCB
Multidimensional Newton Method
Computational Aspects
Iteration : x k 1 x k J ( x k ) 1 F ( x k )
k 1
Do not compute J ( x ) (it is not sparse).
Instead solve : J ( x k )( x k 1 x k ) F ( x k )
Each iteration requires:
1. Evaluation of F(xk)
2. Computation of J(xk)
3. Solution of a linear system of algebraic
equations whose coefficient matrix is J(xk)
and whose RHS is -F(xk)
June 7, 2018 24 courtesy Alessandra Nardi UCB
Multidimensional Newton Method
Algorithm
x = Initial Guess, k 0
0
Repeat {
Compute F x k , J F x k
Solve J F x x x F x for x
k k 1 k k k 1
k k 1
} Until x k 1 x k ,
f x k 1 small enough
June 7, 2018 25 courtesy Alessandra Nardi UCB
Multidimensional Newton Method
Convergence
Local Convergence Theorem
If
a) J F1 x k Inverse is bounded
b) J F x J F y x y Derivative is Lipschitz Cont
Then Newton’s method converges given a
sufficiently close initial guess (and
convergence is quadratic)
June 7, 2018 26 courtesy Alessandra Nardi UCB
Application of NR to Circuit Equations
Companion Network
Applying NR to the system of equations we find
that at iteration k+1:
all the coefficients of KCL, KVL and of BCE of the
linear elements remain unchanged with respect to
iteration k
Nonlinear elements are represented by a linearization
of BCE around iteration k
This system of equations can be interpreted as the
STA of a linear circuit (companion network) whose
elements are specified by the linearized BCE.
June 7, 2018 27 courtesy Alessandra Nardi UCB
Application of NR to Circuit Equations
Companion Network
General procedure: the NR method applied
to a nonlinear circuit whose eqns are
formulated in the STA form produces at
each iteration the STA eqns of a linear
resistive circuit obtained by linearizing the
BCE of the nonlinear elements and leaving
all the other BCE unmodified
After the linear circuit is produced, there is
no need to stick to STA, but other methods
(such as MNA) may be used to assemble
the circuit eqns
June 7, 2018 28 courtesy Alessandra Nardi UCB
Application of NR to Circuit Equations
Companion Network – MNA templates
Note: G0 and Id depend on the iteration count k
G0=G0(k) and Id=Id(k)
June 7, 2018 29 courtesy Alessandra Nardi UCB
Application of NR to Circuit Equations
Companion Network – MNA templates
June 7, 2018 30 courtesy Alessandra Nardi UCB
Modeling a MOSFET (MOS Level 1, linear regime)
June 7, 2018 31 courtesy Alessandra Nardi UCB
Modeling a MOSFET (MOS Level 1, linear regime)
June 7, 2018 32 courtesy Alessandra Nardi UCB
DC Analysis Flow Diagram
For each state variable in the system
June 7, 2018 33 courtesy Alessandra Nardi UCB
Implications
Device model equations must be continuous
with continuous derivatives (not all models do
this - - be sure models are decent - beware of
user-supplied models)
Watch out for floating nodes (If a node
becomes disconnected, then J(x) is singular)
Give good initial guess for x(0)
Most model computations produce errors in
function values and derivatives. Want to have
convergence criteria || x(k+1) - x(k) || < such
that > than model errors.
June 7, 2018 34 courtesy Alessandra Nardi UCB
Outline
Nonlinear problems
Iterative Methods
Newton’s Method
Derivation of Newton
Quadratic Convergence
Examples
Convergence Testing
Multidimensonal Newton Method
Basic Algorithm
Quadratic convergence
Application to circuits
Improve Convergence
Limiting Schemes
Direction Corrupting
Non corrupting (Damped Newton)
Continuation Schemes
Source stepping
June 7, 2018 35 courtesy Alessandra Nardi UCB
Improving convergence
Improve Models (80% of problems)
Improve Algorithms (20% of
problems)
Focus on new algorithms:
Limiting Schemes
Continuations Schemes
June 7, 2018 36 courtesy Alessandra Nardi UCB
Improve Convergence
Limiting Schemes
Direction Corrupting
Non corrupting (Damped Newton)
Globally Convergent if Jacobian is
Nonsingular
Difficulty with Singular Jacobians
Continuation Schemes
Source stepping
June 7, 2018 37 courtesy Alessandra Nardi UCB
Multidimensional Newton Method
Convergence Problems – Local Minimum
Local
Minimum
f
At a local minimum, 0
x
Multidimensional Case: J F x is singular
June 7, 2018 38 courtesy Alessandra Nardi UCB
Multidimensional Newton Method
Convergence Problems – Nearly singular
f(x)
x1
X
x0
Must Somehow Limit the changes in X
June 7, 2018 39 courtesy Alessandra Nardi UCB
Multidimensional Newton Method
Convergence Problems - Overflow
f(x)
0
X
x 1
x
Must Somehow Limit the changes in X
June 7, 2018 40 courtesy Alessandra Nardi UCB
Newton Method with Limiting
Newton Algorithm for Solving F x 0
x = Initial Guess, k 0
0
Repeat {
Compute F x k , J F x k
Solve J F x x F x for x
k k 1 k k 1
x k 1 x k limited x
k 1
k k 1
} Until x k 1
, F x k 1
small enough
June 7, 2018 41 courtesy Alessandra Nardi UCB
Newton Method with Limiting
Limiting Methods
• Direction Corrupting
limited x k 1 x k 1
xik 1 if xik 1
limited x k 1
sign xik 1 otherwise
i
• NonCorrupting
limited x k 1 x k 1
x k 1
limited x k 1
min 1, k 1
x
Heuristics, No Guarantee of Global Convergence
June 7, 2018 42 courtesy Alessandra Nardi UCB
Newton Method with Limiting
Damped Newton Scheme
General Damping Scheme
Solve J F x k x k 1 F x k for x k 1
x k 1 x k k x k 1
Key Idea: Line Search
2
Pick to minimize F x x
k k k k 1
2
2 T
F x x
k k k 1
F x xk k k 1
F x k k x k 1
2
Method Performs a one-dimensional search in
Newton Direction
June 7, 2018 43 courtesy Alessandra Nardi UCB
Newton Method with Limiting
Damped Newton – Convergence Theorem
If
a) J F1 x k Inverse is bounded
b) J F x J F y x y Derivative is Lipschitz Cont
Then
There exists a set of k ' s 0,1 such that
F x k 1 F x k k x k 1 F xk with <1
Every Step reduces F-- Global Convergence!
June 7, 2018 44 courtesy Alessandra Nardi UCB
Newton Method with Limiting
Damped Newton – Nested Iteration
x = Initial Guess, k 0
0
Repeat {
Compute F x k , J F x k
Solve J x x F x for x
F
k k 1 k k 1
Find 0,1 such that F x x
k k k k 1
is minimized
x k 1 x k k x k 1
k k 1
} Until
x k 1 , F x k 1 small enough
June 7, 2018 45 courtesy Alessandra Nardi UCB
Newton Method with Limiting
Damped Newton – Singular Jacobian Problem
x2
1 0 X
x 1 xD x
Damped Newton Methods “push” iterates to local minimums
Finds the points where Jacobian is Singular
June 7, 2018 46 courtesy Alessandra Nardi UCB
Newton with Continuation schemes
Basic Concepts - General setting
Newton converges given a close initial guess
Idea: Generate a sequence of problems,
s.t. a problem is a good initial guess for the
following one
F (x) 0 Solve F x , 0 where:
a) F x 0 , 0 0 is easy to solve Starts the continuation
b) F x 1 ,1 F x Ends the continuation
c) x is sufficiently smooth Hard to insure!
June 7, 2018 47 courtesy Alessandra Nardi UCB
Newton with Continuation schemes
Basic Concepts – Template Algorithm
Solve F x 0 , 0 , x prev x 0
=0.01,
While 1 {
x0 x prev
Try to Solve F x , 0 with Newton
If Newton Converged
x prev x , , 2
Else
1
, prev
2
}
June 7, 2018 48 courtesy Alessandra Nardi UCB
Newton with Continuation schemes
Basic Concepts – Source Stepping Example
June 7, 2018 49 courtesy Alessandra Nardi UCB
Newton with Continuation schemes
Basic Concepts – Source Stepping Example
R
v
f v , idiode v v Vs 0
1
+ R
Vs -
Diode
f v, idiode v 1
Not dependent!
v v R
Source Stepping Does Not Alter Jacobian
June 7, 2018 50 courtesy Alessandra Nardi UCB
Transient Analysis Flow Diagram
Predict values of variables at tl
Replace C and L with resistive elements via integration formula
Replace nonlinear elements with G and indep. sources via NR
Assemble linear circuit equations
Solve linear circuit equations
NO
Did NR converge?
YES
Test solution accuracy
Save solution if acceptable
Select new t and compute new integration formula coeff.
NO
Done?
June 7, 2018 51 courtesy Alessandra Nardi UCB