Circuit Simulation and Verification: Nonlinear Equations Iterative Methods

CSE 245: Computer Aided Circuit Simulation and Verification Nonlinear Equations

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 April 4, 2025 2 courtesy Alessandra Nardi UCB

Nonlinear Equations Given system equations + Integration mechanism, we have ? ? = ? Solve ?(?) = ? equivalent to solve ? ?,? = ? ? ? = 0 Hard to find an analytical solution for ? ?,? = 0 Solve iteratively April 4, 2025 3 courtesy Alessandra Nardi UCB

Nonlinear Problems - Example 1 V d = V ( 1) 0 I I e I1 t Id Ir d s 0 Need to Solve + = 0 I I I 1 r d e 1 R 1 = + ) 1 = ( 1) t V g e I ( 0 e I e I 1 1 1 s April 4, 2025 4 courtesy Alessandra Nardi UCB

Nonlinear Equations Iterative Methods Start from an initial value ?0 Generate a sequence of iterate ?? 1,??,??+1which hopefully converges to the solution ? Iterates are generated according to an iteration function ?:??+1= ? ?? Ask When does it converge to correct solution ? What is the convergence rate ? April 4, 2025 5 courtesy Alessandra Nardi UCB

Newton-Raphson (NR) Method Consists of linearizing the system. Want to solve ? ? = 0 Approximate the function with manageable expressions (Taylor expansion). ? ? = ? ? + ? ??? ? + = 0. We replace ? with ??+1, and derive from ??: ? ??+1= ? ??+ ? ?????+1 ??= 0 Thus, we have ??+1= ?? ? ?? ??(??) and ? ?? ? At each step, we evaluate ? ?? April 4, 2025 6 courtesy Alessandra Nardi UCB

Newton-Raphson Method Graphical View April 4, 2025 7 courtesy Alessandra Nardi UCB

Newton-Raphson Method Algorithm Define iteration Do k = 0 to . 1 1 1 k k k ( dx dx dx ( ( ) ) ) df df df x x x + + + = = = 1 1 1 k k k k k k k k k ( ( ( ) ) ) x x x x x x f f f x x x until convergence How about convergence? An iteration {x(k)} is said to converge with order ? if there exists a vector norm such that for each k N: |??+1 ? | ?? ? q April 4, 2025 8 courtesy Alessandra Nardi UCB

Newton-Raphson Method Convergence A simplified case that ? ? ? ~ x 2 k ( dx ) ( ) df x d f = = + + * * * 2 k k k 0 ( ) ( ) ( ) ( ) f x f x x x x x 2 2 dx But Mean Value theorem truncates Taylor series k ( dx ) df x + = + 1 k k k 0 ( ) ( ) f x x x by definition of the Newton-Raphson method April 4, 2025 9 courtesy Alessandra Nardi UCB

Newton-Raphson Method Convergence Subtracting ~ x 2 k ( dx ) ( ) df x d f + = 1 * * 2 k k ( ) ( ) x x x x 2 2 dx Dividing through 1 ?? ?? ?? ??+1 ? =1 ?2?( ?)/??2?? ? 2 2 Thus, we have |??+1-? | ?|?? ? |2, where K 1 2[??(??)/??] 1?2?( ?)/??2 Convergence is quadratic April 4, 2025 10 courtesy Alessandra Nardi UCB

Newton-Raphson Method Convergence Local Convergence Theorem If df ) bounded aw a ay from ze ro dx bounded K is 2 d f 2 ) bounded b dx Then Newton s method converges given a sufficiently close initial guess (and convergence is quadratic) April 4, 2025 11 courtesy Alessandra Nardi UCB

Newton-Raphson Method Convergence Example 1 = = = 2 * ( ) f x 1 0, ( 1 ) x fin d x x df dx = k k ( ) 2 x x ) ( ( ) x 2 + = 1 k k k k 2 ( ) 1 x x x ) ( ( ) x ( ) x 2 2 + + = 1 * * * k k k k k 2 ( ) 2 ( ) x x x x x x 1 x + = 1 * * 2 k k ( ) ( ) or x x x x k 2 Convergence is quadratic April 4, 2025 12 courtesy Alessandra Nardi UCB

Newton-Raphson Method Convergence Example 2 = = = 2 * ( ) f x 0, 0 x x 1 df df dx Note : not bounded dx = k k ( ) 2 x x away from zero + = 1 2 k k k 2 ( 0) ( 0) x x x 1 2 ( ) + = = 1 * k k k 0 0 for 0 x x x x 1 2 = * * ( ) ( ) or x x x x + 1 k k Convergence is linear April 4, 2025 13 courtesy Alessandra Nardi UCB

Newton-Raphson Method Convergence Example 1,2 April 4, 2025 14 courtesy Alessandra Nardi UCB

Newton-Raphson Method Convergence k = 0 = Initial Guess, 0 x Repeat { ( )( x k = k f x ) ( ) f x + = 1 k k k x x + 1 k } Until ? ( ) + + 1 1 k k k ? ? x x threshold f x threshold April 4, 2025 15 courtesy Alessandra Nardi UCB

Newton-Raphson Method Convergence Convergence Check Need a "delta-x" check to avoid false convergence f(x) + + + 1 1 k k k x x x x x a r + 1 kx kx *x X ( ) + 1 k f x f a April 4, 2025 16 courtesy Alessandra Nardi UCB

Newton-Raphson Method Convergence Convergence Check ( ) f x Also need an " " check to avoid false convergence f(x) ( ) + 1 k f x f a *x X + 1 kx kx + + + 1 1 k k k x x x x x a r April 4, 2025 17 courtesy Alessandra Nardi UCB

Newton-Raphson Method Convergence demo2 demo2 April 4, 2025 18 courtesy Alessandra Nardi UCB

Newton-Raphson Method Convergence Local Convergence Convergence Depends on a Good Initial Guess f(x) 1x 1x X 2x 0x 0x April 4, 2025 19 courtesy Alessandra Nardi UCB

Newton-Raphson Method Convergence Local Convergence Convergence Depends on a Good Initial Guess April 4, 2025 20 courtesy Alessandra Nardi UCB

Nonlinear Problems Multidimensional Example 1v 2v Nodal Analysis 2i bv + - 2 3i 1i + = g v At Node 1: 0 ( i i + 1 2 + + ( ) g v ) = 0 v 1 1 2 bv bv 3 1 - = At Node 2: 0 i i 3 2 - ( ) g v ( ) = 0 g v v 3 1 2 Nonlinear Resistors i g v = Two coupled nonlinear equations in two unknowns ( ) April 4, 2025 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 April 4, 2025 22 courtesy Alessandra Nardi UCB

Multidimensional Newton Method Problem: Find ? such that ? ? = 0, where ? ?? and ?:?? ?? = + * * * ( ) ( ) ( )( ) Taylor Ser F x F x J x x x ies ( ) ( ) F x F x 1 1 x x 1 N = ( ) J x Jacobian M atrix ( ) ( ) F x F x N N x x 1 N + = 1 1 k k k k ( ) ( ) x x J x F x Iteration function April 4, 2025 23 courtesy Alessandra Nardi UCB

Multidimensional Newton Method Computational Aspects + = 1 1 k k k k : ( ) ( ) Iteration x x J x F x 1 k Do not compute ( ) (it is not sparse). = J x + 1 k k k k Instead 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) solve : ( ( ) ) ( ) J x x x F x April 4, 2025 24 courtesy Alessandra Nardi UCB

Multidimensional Newton Method Algorithm k = 0 = Initial Guess, 0 x Repeat { ( ) F x ( ) x k k Compute , J F ( )( x ) ( ) F x + + = 1 1 k k k k k Solve for J x x x F = + 1 k k ( ) + + } Until 1 1 k k k , small en ug o h x x f x April 4, 2025 25 courtesy Alessandra Nardi UCB

Multidimensional Newton Method Convergence Local Convergence Theorem If ( ) x ( ) x ( ) 1 k ) Inverse is bounded a J F ( ) y ( ) ) Derivative is Lipschitz Cont b J J x y F F Then Newton s method converges given a sufficiently close initial guess (and convergence is quadratic) April 4, 2025 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. April 4, 2025 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 April 4, 2025 28 courtesy Alessandra Nardi UCB

Application of NR to Circuit Equations Companion Network MNA templates Note: G0and Iddepend on the iteration count k G0=G0(k) and Id=Id(k) April 4, 2025 29 courtesy Alessandra Nardi UCB

Application of NR to Circuit Equations Companion Network MNA templates April 4, 2025 30 courtesy Alessandra Nardi UCB

Application of NR to Circuit Equations Trapezoidal Integration (assuming u=0) x(t+h)=x(t)+h/2(f(t+h)+f(t)) x(t+h) =x(t)-h/2(C(t+h)-1G(t+h)x(t+h)+C(t)-1G(t)x(t)) Thus, we have (2 (2 For each capacitor, c, the equivalent circuit has current source ieq= 2 in parallel with conductance geq= 2 C(t+h)+G(t+h))x(t+h)= C(t+h)-C(t+h)C(t)-1G(t))x(t) c(t+h)vc(t) +c(t+h)/c(t) ic(t) c(t+h) April 4, 2025 31 courtesy Alessandra Nardi UCB

Modeling a MOSFET (MOS Level 1, linear regime) d April 4, 2025 32 courtesy Alessandra Nardi UCB

Modeling a MOSFET (MOS Level 1, linear regime) April 4, 2025 33 courtesy Alessandra Nardi UCB

DC Analysis Flow Diagram For each state variable in the system April 4, 2025 34 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. April 4, 2025 35 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 April 4, 2025 36 courtesy Alessandra Nardi UCB

Improving convergence Improve Models (80% of problems) Improve Algorithms (20% of problems) Focus on new algorithms: Limiting Schemes Continuations Schemes April 4, 2025 37 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 April 4, 2025 38 courtesy Alessandra Nardi UCB

Multidimensional Newton Method Convergence Problems Local Minimum Local Minimum f x = At a local minimum, 0 ( ) x Multidimensional Case: is singular J F April 4, 2025 39 courtesy Alessandra Nardi UCB

Multidimensional Newton Method Convergence Problems Nearly singular f(x) 1x X 0x Must Somehow Limit the changes in X April 4, 2025 40 courtesy Alessandra Nardi UCB

Multidimensional Newton Method Convergence Problems - Overflow f(x) X 0x 1x Must Somehow Limit the changes in X April 4, 2025 41 courtesy Alessandra Nardi UCB

Newton Method with Limiting ( ) F x = Newton Algorithm for Solving 0 k = 0 = Initial Guess, 0 x Repeat { ( ) F x ( ) x k k Compute , J F ( ) x limited + ( ) F x ) + + = 1 1 k k k k Solve for J x x F ( + + = 1 1 k k k x x x = + 1 k k ( ) + + } Until 1 1 kx k , small enough F x April 4, 2025 42 courtesy Alessandra Nardi UCB

Newton Method with Limiting Limiting Methods Direction Corrupting ( ) + 1 kx + 1 kx limited + + 1 1 k i k i if ( x x ( ) + = 1 k limited x ) i + 1 otherwise k i sign x NonCorrupting ( limited ) + + = 1 1 k k x x + 1 kx ( ) + 1 kx limited = min 1, + 1 kx Heuristics, No Guarantee of Global Convergence April 4, 2025 43 courtesy Alessandra Nardi UCB

Newton Method with Limiting Damped Newton Scheme General Damping Scheme ( ) Solve F J ( ) F x + + = 1 1 k k k k for x x x + + = + 1 1 k k k k x x x Key Idea: Line Search ( ) 2 + + ( 1 k k k k Pick to minimize ( F x F x x 2 ) ) ( ) 2 T + + + + + + 1 1 1 k k k k k k k k k x F x x F x x 2 Method Performs a one-dimensional search in Newton Direction April 4, 2025 44 courtesy Alessandra Nardi UCB

Newton Method with Limiting Damped Newton Convergence Theorem If ( ) x ( ) x ( ) ( ) y 1 k ) Inverse is bounded a J F ( ) ) Derivative is Lipschitz Cont b J J x y F F Then ) ( ks There exists a set of ( F x ' 0,1 such that ) ( ( ) F x + + = + 1 1 k k k k k with <1 F x x Every Step reduces F-- Global Convergence! April 4, 2025 45 courtesy Alessandra Nardi UCB

Newton Method with Limiting Damped Newton Nested Iteration k = 0 Initial Guess, Repeat { Compute = 0 x ( ) F x ( ) x k k , J F ( ) x ( 0,1 such that k k x + ( ) F x + + = 1 1 k k k k Solve for J x x F ( ) + x + 1 k k k k Find k x is minimi e z d F x x + + = 1 1 k = + 1 k k ( ) } Until + + 1 1 kx k , small enough F x April 4, 2025 46 courtesy Alessandra Nardi UCB

Newton Method with Limiting Damped Newton Singular Jacobian Problem 2x X 1 D 0x x 1x Damped Newton Methods push iterates to local minimums Finds the points where Jacobian is Singular April 4, 2025 47 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 Construct and solve ? ? ? ,? = 0 = 0 (x ) F ( ( ) ( ) 0 ,0 ( ) 1 ,1 Starts the continuation = a) 0 is easy to solve ( ) F x Ends the continuation F x ) = b) F x ( ) x Hard to insure! c) is sufficiently smooth April 4, 2025 48 courtesy Alessandra Nardi UCB

Newton with Continuation schemes Basic Concepts Template Algorithm ( ) ( ) ( ) 0 ,0 , = ( ) 0 = Solve =0.01, F x x x prev While x Try to Solve If Newton Converged ( prev x Else = 1 { ( ) ( ) = 0 x prev F x ( ) ( ) = , 0 with Newton ) ( ) = = + = , , 2 x 1 2 = + , prev } April 4, 2025 49 courtesy Alessandra Nardi UCB

Newton with Continuation schemes Basic Concepts Source Stepping Example April 4, 2025 50 courtesy Alessandra Nardi UCB