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 so-called solution path. A version of the predictor-corrector 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 n-dimensional box-searching 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 worst-case analysis [3].

To explain problem formulation let us consider following simple example. We are interested in computation of nodal voltages in the R-ladder 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 right-hand 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 right-hand 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 right-hand-side values in the prescribed intervals. Each of these systems, under the assumption that each A∈** A**is nonsingular, has a unique solution, and all these solutions constitute a so-called solution set S. The solution set of Eq.(1) can be expressed as

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 ** x**is given by

**by**x

*(*m

**)**x

*(*w

**)**x

**=(**A

a

_{ij}) is an interval matrix, then m(

**) = (m(**A

a

_{ij})), see for example [2]. We say that a real vector x, is contained in an interval vector

**, and we write x∈**x

**, if**x

**, and we write A∈**A

**, if**A

**is called regular if detA ≠ 0 for each A∈**A

**. Let**A

_{ij}≥ 0). An interval matrix

**is called inverse stable if**A

**, i.e. if each inverse matrix element is nonzero [12]. Subsequently we introduce some concepts of matrix theory [11]. First, we use the (componentwise) natural partial ordering on sets of real rectors and matrices:**A

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 ** Ax**=

**with an interval matrix of coefficients**b

**= [A-Δ, A+Δ] and a right-hand side interval vector**A

**= [b-δ, b+δ] describing the linear circuit. Here A = m(**b

**), Δ = w(**A

**)/2 and b = m(**A

**), δ = w(**b

**)/2. The set S of all possible operating points (solutions of Eq.(1)) of linear circuit may have a very complicated structure. This set is not generally an interval vector.**b

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 input-output 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 _{1} + jy_{2}. In Fig.2 is presented the region of frequency response changes caused by variations of system parameters done by intervals [a,b] = [1,2] and [c,d] = [-0.5,0.5]. Coordinates of the points fixing the shape of the region are following: A(4/9, 2/9), B(4/3, 2/3), C(1, 0), D(4/3, -2/3), E(4/9, -2/9), and F(1/2, 0).

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 mesh-impedance matrix or mode-admittance 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 right-hand 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 right-hand sides of Eq.(1) are allowed to vary in the given intervals.

Method of computing the vector ** x**=

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 ** A**is regular and inverse stable. It is assured if following conditions are satisfied

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 _{1}=1,

In Fig.4, we have plotted K(ω) as a function of ω. Hatched region show the result by Oettli-Prager 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 node-admittance 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 two-port shown in Fig.6.

Current-controlled description of the two-port 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 steady-state response [24], [25]. Finding the dc operating point is essential for circuit simulation: both steady-state 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 ^{k} is on or near the path and x^{0} is a known solution of H(x,0) = 0. The path in R^{n+1} begins at λ = 0 and ends at λ = 1. An important problem in following homotopy path is a control of the step from a point x^{k} to x^{k+1}. The design philosophies of a step size control are numerous and varied. See, e.g. [28] - [31].

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 predictor-corrector 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 Newton-Kantorovich 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 two-dimensional 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 according to (14) and (15); | |

STEP {7} Check the condition (18); | |

STEP {8} Generate a sequence (19) according to | |

_{1}=K(), _{2}=K(_{1})..._{m}=K(_{m-1} | |

until (_{m}) | |

where (_{m}) | |

STEP {9} Compute | |

^{*}=(_{m}) | |

STEP {10} Assign | |

and go to {1} ( new prediction ); |

### 3.2. Box — Bisection searching

Introducing some interval operator ( e.g. Krawczyk operator, Hansen-Sengupta 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 * Y=*[

*(*m(F’

**))]**x

^{-1}

*(*F’

**)**x

**( e.g. y = m(**x

**) ),**x

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(** x**) ≤ ε (ε - accuracy of searching).

Unless otherwise indicated STEP {k+1} follows STEP {k}.

Given: n-dimensionsl box (interval vector) B ⊆ D ⊆ R^{n}.

STEP {1} Assign |

STEP {2} Compute F(); |

STEP {3} If 0 ∉ F() go to STEP {11}; |

STEP {4} Compute Y, if Y is singular go to STEP {9}; |

STEP {5} Assuming y = m() compute K(, y, Fand R(); |

STEP {6} If K(, y, F∩ = ∅ go to STEP {11}; |

STEP {7} If ||K(, )-||≤()/2||contains a solution, continue, else go to STEP {9}; |

STEP {8} ||R()<1|| If, if w() ≤ ε terminate search, go to STEP {11}; |

STEP {9} If w() ≤ ε add to the list P and go to STEP {11} else bisect on ’ and’’’ according to some rules of bisection; |

STEP {10} Assign ← ’, add ’’ to the head of the list T, go to STEP {2}; |

STEP {11} If list T is empty go to STEP {12}, otherwise take an interval vector _{p} at the head of list T, assign ← _{p}, delete this vector from list T and go to STEP {2}; |

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 ** x**. This problem can be solved by computing coefficients of Bernstein polynomials. For details see [34].

### 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 m-homogenity [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 m-homogeneous 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 ** A**and the interval components of

**are relatively narrow. In practice, however, we are often in situation like in Example 4 when the widths of these intervals are rather wide. This case creates difficulties. Presented here version of Rohn's algorithm doesn't work well. Gaussian elimination using interval arithmetic tends to give poor results. Interval Gaussian elimination can fail because of division by an interval containing zero. This can occur even when the interval coefficient matrix is regular i.e. does not contain a singular real matrix [2]. Maybe methods based on preconditioning of the linear interval equations [7] offer new possibilities. However, recently it was reported that the problem of computing the exact bounds of solution set for a system of linear interval equations is NP-hard (computationally intractable) [13]. Shortly speaking, NP-hardness of a problem P means that if we are able to solve this problem in reasonable time, then we would be able to solve all problems from a very large class of complicated problems (called class NP) in reasonable time, and this possibility is widely believed to be impossible. Reasonable time means a time that does not exceed some polynomial of the length of the input. For exact definitions see, e.g., [15]. On the other hand it was also proved [14] that if the interval components of**b

**and**A

**are „thin” enough, then there exists a polynomial-time algorithm that computes the exact bounds for S in „almost all” cases („almost all” in some reasonable sense). It means that solving linear interval equations isn’t a hopeless task.**b

Second sections presents an approach to compute approximations to the solution path of a systems of nonlinear equations. The suggested method is based on predictor-corrector principle. We have combined common Newton-Raphson correction step with the properties of the interval Krawczyk operator. An interval step control for tracing continuation path assures that the predictor-corrector 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 so-called basic differential equations [23]. Krawczyk operator was also useful in generalized box-bisection for searching all solutions of the circuit equations.