Part 1 of this two-part series presented the Newton-Raphson algorithm for solving systems of nonlinear equations. In that article I showed how to package the algorithm in CEqSystem, an object suitable for reuse. CEqSystem operates over any implementation of two interfaces, IEqEquation and IEqUnknown. An application developer encodes a system of nonlinear equations as a set of objects that implement these interfaces and attaches those objects to the solver. The solver iterates in an attempt to find a solution to the system.
This conclusion of the series presents a model of a network that uses CEqSystem. To demonstrate the solution, the included sample code solves basic electrical circuit problems. Through research, mathematics, and a little creative problem solving, a solution emerges that is capable of modeling complex systems.
The Circuit as a System of Equations
Before modeling a network, we must first understand how it works. We must understand what flows through the network, what forces compel the flow, and what forces impede the flow. These forces provide the parameters, which are known quantities, and the unknowns — the quantities for which we wish to solve. The unknowns in a basic electrical circuit are current (I), measured in amperes, and electromotive force (EMF or simply E), measured in volts. The parameter provided by a battery is output voltage (V), also measured in volts. (Voltage is the same thing as EMF, but I list it as V, to indicate that it is a parameter, not an unknown.) The parameter contributed by a resistor is resistance (R), measured in ohms.
It is important to note that EMF is a relative quantity. It represents the potential for current to flow from one point to another. It is actually meaningless to talk about EMF at a single point; unfortunately, we must use this artificial convention if we are to represent a component as a distinct entity that connects two adjacent points. (It is also a common convention employed in electrical engineering domains.) Use of this convention requires the introduction of a reference, or "ground" point to the circuit. Had this been a model based on an absolute quantity, such as pressure or temperature, the reference point would be unnecessary.
Once the unknowns and parameters have been identified, it is important to understand the relationships among these quantities. The equations are given by Kirchhoff's first law and Ohm's law. Kirchhoff's first law states that the total current flowing into a given point is equal to the total current flowing out of that point. I use sign to represent direction of current flow, so I can write Kirchhoff's first law as in Equation 1 below.
Eq. 1) 
Ohm's law states that the voltage difference, or "drop" across a resistor is equal to the product of the current flowing through the resistor and the resistor's resistance. In terms of unknowns and parameters, Ohm's law appears in Equation 2 below.
Eq. 2) 
The output voltage difference that appears across an (ideal) battery is a constant. This situation is represented by Equation 3:
Eq. 3) 
Across a wire (again, ideal), the voltage drop is zero. This is represented by Equation 4:
Eq. 4) 
Finally, to introduce an EMF reference point, the ground component specifies Equation 5:
Eq. 5) 
By plugging these equations into a typical circuit, you can see how they combine to form a solvable system. The circuit in Figure 1 combines a battery with two resistors in parallel. Although an actual circuit does not need to be grounded to function, the example includes a ground component to artificially inject a zero EMF. As I will show, this is necessary to ensure solvability.
The circuit in Figure 1 defines the system of equations shown in Figure 2. As stated in Part 1 of this series, just having a set of equations is not enough. The system must pass a few tests before the Newton-Raphson algorithm can solve it. To review: first, there should be a practical reason to expect a unique solution. Basic circuits are quite predictable, so they pass this test. Second, the equations must contain no singularities. All nine equations are linear, thus they have no singularities. Third, the number of equations must equal the number of unknowns. In other words, the total degrees of freedom, or DOF, must be zero. With nine equations and nine unknowns, this condition is also met.
This particular system is easy to solve by hand. Combining Equation 7 with Equation 5 shows that E1 = 0 and E2 = 10. Applying Equations 1 and 3 provides the result that I1 = -2/3 and I2 = -2. Continuing around the circuit, I5 = 2/3, I6 = 2, I7 = -2 2/3, I3 = 2 2/3, and I4 = 0.
Given the nature of the ground component, the fact that I4 is zero is not unexpected. However, had this component not been included (thus eliminating I4 and Equation 7), it would be impossible to find a unique solution for the system, for a couple of reasons. First, any two values for E1 and E2 would be acceptable, provided that their difference was 10 volts. Second, Equation 8 would be redundant, as the values of I1, I2, and I3 can be found without the benefit of the equation. This confirms the need, however unfortunate, of the ground component.
The Circuit as a Network
Now I will show how to model this circuit as a network of interconnected components. Components meet at vertices. The degree of a component is defined as the number of vertices to which it connects. The degree of a vertex, similarly, is defined as the number of components it connects. Because each degree of a vertex corresponds to one degree of a component, the total degree of all components is equal to the total degree of all vertices.
Some of the components used in electrical circuits are the battery, the resistor, and the wire (see Figure 3). Each has a degree of two and specifies two equations: Kirchhoff's first law (Equation 1 above) and one of the other three equations described above. Thus, each component added to the system decreases the total degrees of freedom by the degree of the component.
Each vertex is a single point in the circuit (see Figure 4). Kirchhoff's second law tells us that each vertex has a single EMF, which in this system represents one unknown. A different amount of current enters or exits via each branch of the vertex, providing an additional N unknowns, where N is the number of branches attached to the vertex. The vertex must also obey Kirchhoff's first law, so in addition to the N+1 unknowns, the vertex adds one equation to the system. The net effect of each vertex is to increase the degrees of freedom by N, the degree of the vertex.
To model the circuit in code, I define CComponent, a base class for all component types. Two derived classes, CComponentUnary and CComponentBinary, subdivide the hierarchy according to degree. Finally, a derived class for each component type inherits from one of these two subclasses.
I also define CVertex to represent a vertex. To enable a vertex to differentiate one component from another, I introduce the class CLeg. A leg connects one vertex to one component. It identifies the component to the vertex, and accesses EMF and current for the component (see Leg.h, Listing 1).
Because the current through each leg of a vertex is different, the network must somehow associate a distinct current with each one. One obvious solution is to add a member to CLeg to record this value. However, this solution has its drawbacks. Both the vertex and the component know about the leg. However, only the vertex should have direct access to the current through that leg. If the current were stored in the leg, it would be necessary to use friendship (i.e., make CVertex a friend of CLeg) to enforce this rule. Because friendship violates encapsulation, this is not an ideal solution.
Instead, I introduce the LegStruct structure to bind a CLeg pointer with a double. The vertex keeps a list of LegStructs, and searches the list when it needs access to the current for a specific leg. Only the vertex has access to the LegStruct, so it also has exclusive access to the current (see Vertex.h, Listing 2). The UML class diagram in Figure 5 documents the structure of the model.
Notice the use of diamonds on several of the relationships. This notation is usually reserved for aggregation; however, I have extended this convention to document ownership. This change is justified because aggregation is an informal kind of ownership. Every object, except the root object, has exactly one owner, that being the object responsible for its creation and destruction. Identifying ownership is important in any model, but it is crucial to understanding systems with many-to-many relationships, such as that between vertices and components. In such a system, it is often necessary to define one class as the owner for all others. In the above model, this class is CNetwork (see Network.h, Listing 3).
The ownership path not only helps with creation and deletion, but also helps dictate other responsibilities. Attaching the model to the Newton-Raphson solver, in this case, is accomplished through the AddToSystemPrimary and AddToSystemSecondary methods in CNetwork (see Figure 6). CNetwork routes these requests to its components and vertices. Each vertex, in turn, routes the requests to the objects it owns.
For the network model to integrate with the Newton-Raphson solver, it must implement the two interfaces described in Part 1. The IEqUnknown interface represents an unknown quantity in the system, while the IEqEquation interface represents a constraint, or condition, that must be met. The appropriate objects to implement IEqUnknown are CVertex for EMF, and LegStruct for current, because the values are recorded in members of these objects. These classes inherit the IEqUnknown interface and override the GetValue and SetValue methods, thus providing access to the unknowns (see Listing 2).
The appropriate objects to implement IEqEquation are the components, because each has a different set of conditions that must be met. All binary components add an equation for Kirchhoff's first law, but each different component type adds a unique equation for EMF. To implement the IEqEquation twice within the same object, I define intermediate classes (as described in Part 1). IEqEquationKirchhoff and IEqEquationEMF each inherit from IEqEquation. They implement the methods CalculateValue and DependsUpon, in each case calling a pure virtual method introduced locally.
CComponentBinary inherits from both IEqEquationKirchhoff and IEqEquationEMF, thus providing two separate implementations of IEqEquation without conflict (see Figure 7). To add these two implementations to the solver object, CComponentBinary must cast its pointer to each of the intermediate base classes (see CComponentBinary::AddToSystemPrimary in Figure 6).
To complete the model, CNetwork aggregates all vertices and components. The application (see Main.cpp, Listing 4) asks the network object to create all components and vertices on its behalf, then connects them to form a circuit. The example function Circuit1 in Listing 4 specifies the problem illustrated in Figure 1, a simple circuit with two resistors in parallel. Execute the code to confirm that it calculates the solution that appears in the text above.
Extending the Network Solver
While the first example demonstrates the solution of a network, it does not answer one of the most common questions in basic circuit design: how much resistance is needed to achieve a desired current? Also, since Ohm's law is linear when resistance is known, the first example does not show off the full power of Newton-Raphson. By observing the trace generated for the first problem, you can see that it solves in only one step. Therefore, allow me to introduce two new component classes.
To solve the more complex problem of finding resistance to achieve a specific current, we need a resistor that treats resistance as an unknown. CComponentResistorUnknown inherits from CComponentResistor with the purpose of adding an unknown to the system. Offsetting this new unknown requires the addition of another equation. CComponentWireKnown inherits from CComponentWire to add the equation that specifies current through the wire. By combining the same number of each of these with the more traditional components, an application can solve a circuit with any number of unknown resistors.
Since the problem has changed, we must again return to the mathematics to determine whether it is solvable. Assuming a fixed voltage difference across a resistor, Ohm's law implies that a plot of resistance vs. current will be a hyperbola (see Figure 8). This becomes apparent if you rearrange the equation that states Ohm's law from
to
The voltage, however, is unknown, so the quadrant of the hyperbola is undetermined. Furthermore, the way the solver is currently set up, the current starts at zero, a condition which always produces a singularity. We must therefore know at least the sign of the voltage difference, and subsequently the current, to give the solver initial conditions from which it can converge.
To find the appropriate initial conditions, observe that the magnitude of resistance does not affect the direction of current. As long as resistance is positive, which it must be, the current can flow in only one direction, which is determined by the sign of the voltage difference. Because of this, the easiest way to solve for appropriate initial conditions is to fix resistance and solve the simpler linear problem. It doesn't matter what choice is made for the initial resistance, as long as it is positive. The default choice of 1 ohm is as good as any.
The application calls AddToSystemPrimary, which defines only a linear system, and solves for initial conditions. It then calls AddToSystemSecondary and solves the complete problem. While the initial guess of zero current is unlikely to find a solution, the calculated initial guess leads to a solution in only a few iterations.
The diagram in Figure 9 illustrates the example problem solved by function Circuit2 (see Listing 4). Notice that, in this circuit, the resistance of the unknown resistor influences the direction of the current through the center. If the resistor is less than 10 ohms, the current will flow upward. If it is greater, the current will flow downward. If it is exactly 10 ohms, no current flows through the center. At first glance, this appears to be a problem. However, it is only the direction of the current through the unknown resistor that is of concern. In this case, it is clear that, no matter what its resistance, the current through the unknown resistor always flows toward the left. Therefore, even though the initial guess of 1 ohm puts the current in the wrong direction through the center, the algorithm is able to solve the problem nonetheless.
The above example problem illustrates one shortcoming of the Newton-Raphson engine presented here. Notice that as the resistance approaches infinity (essentially disconnecting the resistor) the current through the center approaches a limit (namely 5/30 amps). If you attempt to solve for a current greater than this limit, the Newton-Raphson engine will not terminate. It continues to try ever-higher values for resistance, never reaching its goal. It does not have any test for failure to converge, and therefore does not know to stop.
One such test that the reader could add is a limit on the number of iterations attempted. In the types of basic circuit problems presented here, 100 iterations might be enough. Then again, for a complex circuit, it might not. Any choice of limit would be arbitrary. A better choice might be to run the solver engine in its own thread. Continually report to the user some metric (such as norm) indicating how close it is to a solution, and give the user the opportunity to cancel the calculation. This I leave as an exercise to the reader.
Conclusion
The basic electrical circuit model presented here can be further extended to solve harmonic circuits by adding capacitors, inductors, and frequency. No change to the solution would be necessary. However, digital circuits are another matter. Diodes and transistors have a singularity where current is equal to zero, as they allow current to flow in only one direction. Because of this singularity, Newton-Raphson alone is not sufficient to solve digital circuits in all cases. It may be a part, but a full solution would require even more research and creativity. But then again, isn't that why we are programmers?
Sidebar: Optimizing the Solution
Michael L. Perry is a software developer with six years of industry experience. As the founder of Mallard Software Designs, Inc., Michael strives to make sound development practices more commonplace in the software community. For more information, please visit the Mallard web site at http:\\www.mallardsoft.com.