Ranges for nodal voltages
1. Introduction
Concepts of interval analysis are suitable for solving some problems for linear and nonlinear analog circuits. The effects of circuit parameter uncertainties on circuit performance are always of great concern to the system designer. It is desirable to know a priori estimates of the circuit response, subject to parameter uncertainties. In the first section of this chapter a problem of calculating of the operating regions (solutions) for linear circuits with parameters done as interval numbers is considered. Such circuits are described by linear interval equations. The set of all possible operating points of the circuit may have a very complicated structure and it is usually impractical to calculate it. Applying ideas of interval analysis it is possible to calculate multidimensional rectangular region bounding the set of operating points. In the paper an algorithm of iterative evaluation of the bounds of operating regions is applied. The second section deals with the finding DC solutions of nonlinear, inertialess circuits. Using idea of a continuation method one can solve nonlinear equations describing circuit by tracing socalled solution path. A version of the predictorcorrector method for computing points of continuation path of a nonlinear equation is presented. The target of this approach is to control the corrector step in such a manner that the predictor step is sufficiently large but that the corrector step does not jump to another continuation path. Additionally interval analysis offers possibility to solve that problem by applying generalized bisection method based on some interval operator associated with nonlinear equation. In the section Krawczyk operator is used in ndimensional boxsearching of all solutions. For both sections numerical studies are reported in order to illustrate and verify presented approach.
2. Analysis of linear circuits with interval data
The changes in the performance of a linear circuit due to the variations in circuit parameters are of great practical importance in engineering analysis and design. Such perturbations of parameters may model the effects of uncertainties in manufacturing tolerances, ageing of components, environmental causes and the like. because of these uncertainties, the value of the parameters of a given linear circuit may frequently be treated as belonging to suitable intervals.
From this point of view, the aim of this paper is to consider solutions of linear circuits using paradigm of interval computations [1]. This problem is closely related to the tolerance analysis of electric and electronic circuits especially the worstcase analysis [3].
To explain problem formulation let us consider following simple example. We are interested in computation of nodal voltages in the Rladder circuit of Fig.1.
Parameters of the circuit are done as interval number, viz. E∈[5.67, 6.93], R_{1}, R_{2}, R_{4}, R_{6}∈[0.09, 0.11], R_{3}, R_{5}∈[1.8, 2.2]. Applying nodal analysis we obtain following system of equations:
It's seen that the coefficients and righthand sides of the system are not determined exactly, but are only known to lie within some real intervals.
Denote a system of linear interval equations by
The coefficients and righthand sides of the system are not determined exactly, but are only known to lie within some real intervals. Such a system of linear interval equations represents a family of ordinary linear systems which can be obtained from it by fixing coefficients and righthandside values in the prescribed intervals. Each of these systems, under the assumption that each A∈
It forms some multidimensional operating region of a circuit.
It the next points, we introduce some notations and ideas concerned with a structures of operating regions, drawbacks of some circuit descriptions, and method of rectangular (interval) evaluating of the operating regions.
As the examples, we give the calculation of variations of the frequency response and nodal voltages of the RC circuits with interval data. We also test our approach when the widths of matrix elements in Eq.(1) are large.
2.1. Notations and preliminaries
All vectors in this paper will have n components and all matrices will be of size n×n. The sets of real vectors, real matrices, interval vectors, and interval matrices are represented by the lower case, upper case, lower case bold, and upper case bold letters respectively. A real, scalar interval
For inverse stable matrix A the signature matrix Z is defined by
(notice the transposition of indices). For two n×n matrices A = (a_{ij}) and B = (b_{ij}) their componentwise product is defined as A*B=(a_{ij}b_{ij}). Further, diag A denote the diagonal vector of A, i.e. diag A = (a_{11},...,a_{nn})^{T} and
2.2. Structure of an operating region
In the first section we introduce a linear interval
A number of authors have described ways to compute an x satisfying (2). See [12] for reference. In their pioneer work Oettli and Prager [8] showed that the solution set of a linear interval equation with regular matrix A is described following
It is known [12] that S can be represented as a union of at most 2^{n} convex polyhedra. The intersection of S with each orthant of R^{n} is convex. In general, S itself is not convex.
EXAMPLE 1. To illustrate that the solution set S given by (3) is not simple, let consider a linear system with inputoutput relationship written as y(jω) = K(jω,p) x(jω).
Frequency response K(jω,p) vary with vector p of some parameters ranging in known intervals. It can be shown [9] that for a fixed frequency changes of K(jω,p) are described by the system of two interval equations
where the intervals [a,b] and [c,d] represent the ranges of values of
Because S is generally so complicated in shape, it is usually impractical to try to use it. Instead, it is common practice to seek the interval vector x containing S which has the narrowest possible interval components. We say we "solve" the problem when we find x.
2.3. Rectangular evaluation of an operating region
From the standpoint of view of interval computations the formulation of circuit equations based of mesh analysis or modal analysis are not necessarily suitable for the networks with interval parameters. They result in a system of linear interval equations whose coefficients are not independent. We have the wider range of the coefficients since the elements of meshimpedance matrix or modeadmittance matrix are given by the linear combinations of the interval parameters of resistors, capacitors, etc. Hence the width of the elements of the matrix coefficients and righthand side vector of Eq.(1) becomes resultantly larger. This makes the evaluation of interval solution worse. Secondly owing to the interval dependency the linear combination of interval numbers gives us possibility to have the meaningless combination of the parameters. In order to avoid the drawbacks mentioned above the formulation by hybrid equation is well suited for solving linear interval systems [4], [10].
The problem treated in this section is how to compute the interval hull of S, i.e. the interval vector x with components
describing the exact range of components of the solution if coefficients and righthand sides of Eq.(1) are allowed to vary in the given intervals.
Method of computing the vector
Where B=be^{T}, D=δe^{T}, e=(1,1,...,1)^{T}∈R^{n}. Z is a signature matrix of A^{1}. Recommended initial guess for the sequence (5) is
It is assumed that coefficient matrix
and
(I is the unit matrix).
Conditions (7) and (8) under which the method works are satisfied if all coefficients of A^{1} are nonzero and Δ is sufficiently small. Under this conditions the sequences
2.4. Numerical examples
EXAMPLE 2. Consider the simple RC voltage divider circuit of Fig.3, where the resistor and the capacitor values are allowed to vary from 4.4Ω to 4.6Ω and from 520 μF to 580 μF respectively.
We want to calculate amplitude variations of the frequency response due to the changes of resistance and capacitance. For a fixed frequency, amplitude of the frequency response
where
In Fig.4, we have plotted K(ω) as a function of ω. Hatched region show the result by OettliPrager condition. Outer bounds were computed with use of the sequences (5). Both results are in a fairly good agreement.
EXAMPLE 3. Consider the linear RC circuit illustrated in Fig.5 [9]. The interval parameter with the center value m and the width 2r is denoted as (m, r). The numerical data are following: Y_{k} = G_{k} + jB_{k}, G_{k}=(1, ε), B_{k}=(0.2, 0.2ε), J=10
In spite of remarks in previous section on drawbacks of nodal analysis we applied here nodal equations. It allowed us to fulfill assumptions of Rohn's algorithm although the elements of nodeadmittance matrix are dependent. In order to carry the sequences (5) working with Eq.(1) represented by real interval numbers we replaced the interval complex nodal equations
by the real interval equation
where
The results are tabulated below






V_{1}  [5.7635, 6.2724]  [1.2652, 11447] 
V_{2}  [2.3055, 2.5090]  [0.5061, 0,4579] 
V_{3}  [1.1527, 1.2545]  [0.2530, 0.2289] 






V_{1}  [5.5336, 6.5529]  [1.3355, 10927] 
V_{2}  [2.2135, 2.6212]  [0.5342, 0.4371] 
V_{3}  [1.1067, 1.3106]  [0.2671, 0.2185] 
Results are essentially the same as in [10] although the widths of nodal voltages are greater. It confirms the influence of coefficient dependence on evaluation of interval solutions.
EXAMPLE 4. To test properties of presented approach let consider the active twoport shown in Fig.6.
Currentcontrolled description of the twoport is following
For numerical data
interval representation is following
If excitations are determined as U_{1} ∈ [2,3], U_{2} ∈ [0,1] the solutions set S has form shown in Fig.7.
Computing bounds on operating region for i_{1} and i_{2} with recommendation given by (6) and slightly different starting intervals following results were obtained:
It’s seen that this approach give poor results if widths of matrix coefficients are large.
3. On finding operating points of nonlinear, inertialess circuits
A continuation method is a method of dc circuit analysis that under proper conditions, is guaranteed to find a circuit’s operating point [26], [27]. It can be also used in calculating a circuit’s periodic steadystate response [24], [25]. Finding the dc operating point is essential for circuit simulation: both steadystate and transient analyses require a priori knowledge of circuit’s dc operating point. The idea behind a continuation method is to embed in the circuit’s equations
( nodal or hybrid ) an additional parameter λ such that the circuit that corresponds to λ = 0 is trivial or easy to find: the circuit that corresponds to λ = 1 is the original circuit whose solution is desired. Hence, a mapping (homotopy) H: R^{n+1} → R^{n} is constructed, where H(x, 0) = 0 gives the solution to the initial ( start ) circuit and H(x, 1) = 0 gives the solution to the circuit being simulated. To find this solution, one generate a sequence of points
Most of the methods on the following continuation paths are based on approximate step control. Approximate step control methods are successful and fast when the path is smooth and isolated, but problems arise when there are many paths near some points. In that case, algorithms based on approximate step control methods may jump from one path to another. Also, if rapid changes in curvature occur along the path, the method based on approximate step control sometimes even erroneously reverses orientation. However, appropriate use of interval analysis gives us guarantee that the predictor algorithm will not jump from one path to another, or, indeed, jump over different legs of the same path. We present an interval step control for tracing continuation paths which assures that the predictorcorrector iterations will not jump across paths, and each predictor step is as large as possible, subject to verification that the path is unique with the given interval extension.
3.1. Step size control
To trace a path from a known solution
where
Since this is only approximate, we correct the solution at the new value of
However, just the fact that (12) is satisfied does not guarantee the existence of a solution. We try to overcome this difficulty by first performing the three Newton steps and using them to compute an interval vector that is very likely to contain a solution of the correction step. We adopt here results presented in [22]. Consider Newton’s method
Let
for some fixed k and
Combining the properties of the Krawczyk operator and a corollary of the NewtonKantorovich theorem it can be shown, that for three successive iterates the following relation holds
In Fig. 8 there is a sketch of the idea of constructing the predictor  corrector step for twodimensional problems, i.e. x = (y, z).
We can compute interval (15) and using the Krawczyk operator K(x) we test whenever this interval contains a solution. It is true if the Krawczyk operator satisfy an inclusion
then x contain solution of the correction step
is satisfied [21], then the solution
This nested sequence is stopped when the width of the interval x_{m} becomes smaller than
μ > 0 and then
Step size control can be formalized in the following algorithm.
Unless otherwise indicated STEP {k+1} follows STEP {k}.  
Given: Solution 

STEP {1} Assume 0 < Δλ < 1;  
STEP {2} Compute prediction step Δx according to (11);  
STEP {3} Compute using Newton method (13) three successive iterates;  
STEP {4} Verify the inequality (16) for some eps "/> 0;  
STEP {5} Check the relation (17). If (17) is not satisfied take Δλ = Δλ/2 and go to {2};  
STEP {6} Compute interval 

STEP {7} Check the condition (18);  
STEP {8} Generate a sequence (19) according to  
until 

where 

STEP {9} Compute  
STEP {10} Assign 

and go to {1} ( new prediction ); 
3.2. Box — Bisection searching
Introducing some interval operator ( e.g. Krawczyk operator, HansenSengupta operator or some of their modifications [20]) for system of nonlinear equations we can formulate generalized bisection algorithm applicable to find solutions of equation (9).
Let denote Krawczyk operator associated with Eq. (9) as
Here
and I is identity matrix.
Let T denotes the list of subregions yet to be tested. P is the list of subregions of B which may contain a solution to (9) but which are too small for further analysis, i.e. w(
Unless otherwise indicated STEP {k+1} follows STEP {k}.
Given: ndimensionsl box (interval vector) B ⊆ D ⊆ R^{n}.
STEP {1} Assign 
STEP {2} Compute F( 
STEP {3} If 0 ∉ F( 
STEP {4} Compute Y, if Y is singular go to STEP {9}; 
STEP {5} Assuming y = m( 
STEP {6} If K( 
STEP {7} If K( 
STEP {8} R( 
STEP {9} If w( 
STEP {10} Assign 
STEP {11} If list T is empty go to STEP {12}, otherwise take an interval vector 
STEP {12} If list P is empty, terminate search with no solution in B, otherwise print list P and terminate search. 
One can simply check that in the STEPS {5}, {7}, {8} for Algorithm with step size control and in the STEPS {2}, {4},{5} for box – bisection searching one needs to evaluate the ranges of nonlinear functions over some interval
3.3. Numerical examples
As an illustration of the implementation of the approach outlined above, consider the following two examples.
EXAMPLE 5. Our first example concerns a simple circuit of Fig. 9 which consists of two tunnel diodes and two constant current sources and a linear resistor. The tunnel diode characteristics are defined following
The network equations are obtained from the hybrid analysis as
We introduce homotopy of the form
where λ ∈ [0,1] and γ is a random complex number, different from zero.
Start equations are following
It’s seen that the solutions of equation
are distributed on unit circles and they form nine starting points (x^{0}, 0). For solving so prepared homotopy equations we splited them into real and imaginary parts.
Presented approach leads to the five real solutions
Because above equation is equivalent polynomial of 9^{th} degree there are also four complex solutions:
EXAMPLE 6. Let consider circuit hybrid equation [17].
Nonlinear functions ( characteristics of nonlinear elements ) are following
For solving this polynomial system we have applied the same homotopy as in Example 5.
Using concept of mhomogenity [18],[19] we can introduce solutions that corresponds to λ=0 and the start system H(x, 0) = Q(x) = 0 look like this
The start system respects the mhomogeneous structure [18] of the hybrid equation we want to solve and has eight start solutions. Namely
We applied the step size control previously described with tolerance eps = 0.01. We needed to trace only eight solution paths. Two pairs of them reached the same solutions, and so we obtained following six solutions of the hybrid equations:
For circuit analysis only real solutions x_{A} and x_{B} are of interest.
EXAMPLE 7. In the last example an electric circuit depicted in Fig. 10 assembling some linear resistors, diodes and operational amplifier is considered (cf. [29]).
The voltage induced in the operational amplifier is modeled by:
the current through the diodes satisfies:
resistances in ohms are following: R_{1} = 51, R_{2} = 39, R_{3} = 10, R_{4} = 10^{4}, R_{5} = 0.201, R_{6} = 25.5, R_{7} = 0.62, R_{8} = 1, R_{9} = 13. Applying Kirchhoff’s laws to the circuit leads to the system of nonlinear equations:
Functions describing nonlinearities of diodes and operational amplifier are smooth functions so we have needed their expansion to compute range values. We have assumed Taylor expansion with degree = 4 and for Bernstein coefficients degree = 10 [34]. Applying box–bisection algorithm we have obtained solutions for two different ranges of the input voltage E. Results are tabulated as
E  [ 0.320, 0.322 ]  [ 0.599, 0.601 ] 
v_{1}  [ 0.2325, 0.2354 ]  [ 0.0439, 0.0493 ] 
v_{2}  [ 0.6578, 0.6629 ]  [ 0.5423, 0.5471 ] 
v_{3}  [ 0.2303, 0.2375 ]  [ 0.0464, 0.0492 ] 
v_{4}  [ 0.2299, 0.2375 ]  [ 0.0446, 0.0496 ] 
v_{5}  [ 0.6155, 0.6208 ]  [ 0.1232, 0.1293 ] 
v_{6}  [ 9.5941, 9.6088 ]  [ 1.1597, 1.1662 ] 
4. Concluding remarks
In first section, we applied an algorithm for bounding the solution set of a system of linear interval equation which works when the interval elements of
Second sections presents an approach to compute approximations to the solution path of a systems of nonlinear equations. The suggested method is based on predictorcorrector principle. We have combined common NewtonRaphson correction step with the properties of the interval Krawczyk operator. An interval step control for tracing continuation path assures that the predictorcorrector iterations were not jumping across paths. A robust and efficient path tracker was obtained by halving the homotopy parameter step whenever uniqueness of correction solution is not assured within a given tolerance of the continuation path and doubling it when the prediction step has been sufficiently accurate several consecutive times. Presented here path tracker was more effective than the tracing homotopy path via integration socalled basic differential equations [23]. Krawczyk operator was also useful in generalized boxbisection for searching all solutions of the circuit equations.
References
 1.
Methods and Applications of Interval Analysis, SIAM Studies 2. Philadelphia: SIAM;Moore R. E 1979  2.
Introduction to Interval Computations. New York: Academic Press;Alefeld G Herzberger J 1983  3.
Tolerance Design of Electronic Circuits. London: AddisonWesley;Spence R Soin R. S 1988  4.
Interval Methods for Circuit Analysis. Singapore: World Scientific;Kolev L. V 1993  5.
Systems of linear interval equations. Linear Algebra Appl.Rohn J 1989 126 39  6.
A twosequence method for linear interval equations. ComputingRohn J 1989  7.
Bounding the solution of interval linear equations. SIAM J. Numer Anal.Hansen E. R 1992 29 5 1493 1503  8.
Compatibility of approximate solution of linear equations with given error bounds for coefficients and righthand sides. Numer. Math.Oettli W Prager W 1964 6 1 405 409  9.
Computing componentwise bounds on operating regions of linear circuits with interval data. In Proceedings of the 13^{th} European Conference on Circuit Theory and design, ECCTD’97, 30 August 3 SeptemberGarczarczyk Z 1997 Budapest.  10.
A method for solving complex linear equation of AC network by interval computation. In Proceedings of the 1994 International Symposium on Circuits and Systems, ISCAS’94, 30 May 2 JuneOkumura K Higashino S 1994 London.  11.
Matrix Iterative Analysis, Englewood Cliffs,NJ: PrenticeHall,Varga R. S 1962  12.
Interval Methods for Systems of Equations. Cambridge: Cambridge University Press,Neumaier A 1990  13.
PASCALXSC. Berlin: Springer Verlag,Klatte R et al 1992  14.
Computing exact componentwise bounds on solution of linear systems with interval data is NPhard. SIAM J. Matrix Anal. Appl.Rohn J Kreinovich V 1992 16 2 415 420  15.
If input intervals are small then interval computations are almost always easy. Reliable Computing 1995, SupplementLakeyev A. V Kreinovich V 1995 134 139  16.
Computers and Intractability: A Guide to the Theory of NPCompleteness. San Francisco: Freeman,Garey M. E Johnson D. S 1979  17.
ComputerAided Analysis of Electronic Circuits. Englewood Cliffs, NJ: PrenticeHall, Inc.,Chua L. O Lin P. M 1975  18.
A homotopy for solving general polynomial systems that respects mhomogeneous structures. Appl.Math.Comput.Morgan A Sommese A 1987 24 2 101 113  19.
Circuit design problems via polynomial equations solving, In Proceedigs of the 12^{th} European Conference on Circuit Theory and Design, ECCTD’Garczarczyk Z 95 27 31 August1995 Istanbul, Turkey.  20.
Introduction to Interval Analysis. Philadelphia: SIAM,Moore R. E Kearfott R. B Cloud M. J 2009  21.
A test for existence of solutions to nonlinear systems. SIAM J. Numer. Anal.Moore R. E 1977 14 4 611 615  22.
Alefeld G, Gienger A, & Potra F. Efficient numerical validation of solutions of nonlinear systems. SIAM J. Numer. Anal.1994  23.
Pathways to Solutions, Fixed Points and Equilibria. Englewood Clifs NJ: PrenticeHall, Inc.,Garcia C. B Zangwill W. I 1981  24.
Finding periodic solutions of ordinary differential equations via homotopy method. Appl. Math. Comput.Lu X Li Y Su Y 1996 78 1 1 17  25.
HomSPICE: simulator with homotopy algorithms for finding dc and steadystate solutions of nonlinear circuits. In Proceedings of the 1998 International Symposium on Circuits and Systems, ISCAS’98, 31 May 3 JuneTrajkovic L Fung E Sanders S 1998 Monterey, CA.  26.
Theory of dc operating points of transistor networks, Intern. J. Electronics and Comm.Trajkovic L Willson A. N 1992 46 4 228 240  27.
Parameter embedding methods for finding dc operating points of transistor circuits. In Proceedings of the International Specialist Workshop on Nonlinear Dynamics of Electronics Systems, NDES’95, JulyMathis W et al 1995 Dublin, Ireland.  28.
Numerical Continuation Methods: An Introduction. New York: Springer Verlag;Allgower E. L Georg K 1990  29.
Role of continuation in engineering analysis. Chemical Engineering ScienceSeydel R Hlavacek V 1987 42 6 1281 1295  30.
Some computational methods for systems of nonlinear equations and systems of polynomial equations. J. Global OptimizationForster W 1992 2 4 317 356  31.
Variable order AdamsBashforth predictors with an errorstepsize control for continuation methods. SIAM J. Sci. Stat. Comput.Lundberg B. N Poore A. B 1991 12 3 695 723  32.
On step size control for tracing continuation paths. In Schwarz W. (ed.) Proceedings of the 7^{th} International Specialist Workshop on Nonlinear Dynamics of Electronics Systems, NDES’Garczarczyk Z 99 15 17 July, Ronne, Island of Bornholm, Denmark. Dresden: Technical University Dresden;1999  33.
A method for evaluation the range values of a bivariate function. In Proceedings 1998 International Symposium on Nonlinear Theory and its Applications, NOLTA’Garczarczyk Z 98 14 17 September1998 CransMontana, Switzerland.  34.
Linear Analog Circuits Problems by Means of Interval Analysis Techniques. In TleloCuautle E. (ed.) Advances in Analog Circuits. Rijeka: InTech;Garczarczyk Z 2011 2011 147 164