[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

716.0. "need help with partial difference eqn" by EAGLE1::BEST (R D Best, Systems architecture, I/O) Tue Jun 09 1987 15:06

Is anybody familiar with how to solve partial difference equations ?

The following two variable recurrence results from writing Kirchoff's
current law for the infinite resistor grid in note 703.

4*V(x,y) = V(x-1,y) + V(x+1,y) + V(x,y-1) + V(x,y+1)

V(0,0) = 1

There are also a number of boundary conditions that can be derived from
symmetry and so forth.  I'll put down the ones I could think of.

By symmetry:

V(0,1) = V(1,0) = V(0,-1) = V(-1,0)

Also, by symmetry, I suspect that you can do something analogous to
separation of variables in cont. part. diff. eqns.:

V(x,y) = Vx(x)*Vy(y)

Still more, by symmetry, I think:

Vx(u) = Vy(u)  (i.e. Vx and Vy are the same function)

Is this sufficient to get V(x,y) ?

If not, what other boundary conditions are needed ?

Additional information might also be derived from use of KVL.
T.RTitleUserPersonal
Name
DateLines
716.1ENGINE::ROTHWed Jun 10 1987 14:3423
    You need to specify the boundry conditions surrounding the grid of
    resistors to get a unique solution.  Once the boundry conditions are
    specified, (and the problem is reduced somwhat via symmetry) a simple
    relaxation method could be used to iteratively solve for the current
    distribution.  In partial differential equations, specifying the
    value of a scalar potential on the boundry is called a Dirichlet
    problem, and leads to what is called an elliptic boundry value
    problem.

    One approach to the "boundry at infinity" may be to model the current
    flow as a diffusive process which approaches some steady state that
    satisfies Kirchoffs laws.  This would allow you to approach the final
    solution in a mathematically satisfying way, as a well defined limit.

    To be more specific, consider a small capacitor to be present at
    each node of the grid and apply a step of current at the center, or
    two opposite steps of current at selected grid points.  Now you have
    a large RC network, which will approach the solution you desire in the
    steady state.  And it is far closer to actual physical reality than
    a capacitance free grid of resistors, which is never realisable in
    practice.

    - Jim
716.2re .1; what is Tellegen's theorem ?EAGLE1::BESTR D Best, Systems architecture, I/OFri Jun 12 1987 18:0452
>    You need to specify the boundry conditions surrounding the grid of
>    resistors to get a unique solution.  Once the boundry conditions are
>    specified, (and the problem is reduced somwhat via symmetry) a simple
>    relaxation method could be used to iteratively solve for the current
>    distribution.  In partial differential equations, specifying the
>    value of a scalar potential on the boundry is called a Dirichlet
>    problem, and leads to what is called an elliptic boundry value
>    problem.

What makes a sufficient set of boundary conditions ?  Since the
grid is infinite, it seems that the condition is something like
V( infinity, infinity ) = 0.  I'm not sure if this is meaningful.
The problem I see is that there are many V that should be able to
meet this criterion.  It seems to me that the boundary conditions that
will determine a unique solution will have to be finite.  That is,
it seems that the solution will become unique when given enough
( e.g. n) boundary value conditions of the form:

	V(p,q) = k(m)
	with p and q integers,
	m natural, and
	k(m) real for m between 1 and n.

>    One approach to the "boundry at infinity" may be to model the current
>    flow as a diffusive process which approaches some steady state that
>    satisfies Kirchoffs laws.  This would allow you to approach the final
>    solution in a mathematically satisfying way, as a well defined limit.

Hmm. Sounds complicated.  Maybe I should try to get the
solution for a finite grid (parametrised by something like the number
of resistors on a 'side' of the grid) and then let that number approach
infinity ?

>    To be more specific, consider a small capacitor to be present at
>    each node of the grid and apply a step of current at the center, or
>    two opposite steps of current at selected grid points.  Now you have
>    a large RC network, which will approach the solution you desire in the
>    steady state.  And it is far closer to actual physical reality than
>    a capacitance free grid of resistors, which is never realisable in
>    practice.

It seems that I should be able to get the steady state solution without
having to solve for the voltage at each node for all time.  In the steady
state, I think that the circuit reduces to just the resistors and that
the final state must depend only on the values of the resistors.

You mentioned something earlier about Tellegen's theorem.  I hadn't heard
of that before.  Could you tell what it is ?

Thanks for the help so far.

>    - Jim
716.3some computational ideasENGINE::ROTHMon Jun 15 1987 11:0974
    Actually, the idea of capacitive loading is probably unnecessarily
    complicated - it was just an attempt to make the problem more phyiscally
    meaningful...

    I forgot to mention Tellegen's theorem.  It states that in a network,
    SUM(v*i) = 0, and is actually valid for time varying and nonlinear
    networks.  It doesn't state anything fundamentally new and can be
    derived from KVL and KCL, but surprisingly wasn't stated explicitly
    until some time in the '50's, by B. Tellegen, in a Phillips Research
    Reports paper.  I can dig a copy out, I found a reprint of it once.
    (Some of those early papers, like Nyquist's paper on regeneraton are
    really worth reading.)

    A sufficient set of boundry conditions is either the value of the
    function along the boundry, or the normal of its gradient.  You must
    specify the whole boundry, either the value or gradient, or some
    mixture, to have a unique solution. Boundries at infinity must be
    handled by a limiting process using a finite boundry, though often a
    simple handwave (boundry at infinity = 0) will work.

    Here is one way of approaching the problem computationally:

    By symmetry, we can consider only one quadrant of the grid.  Define
    mesh currents in each square, numbered I[i,j], and put a current
    source of strength I at the origin.  Now we have the boundry conditions
    I[i,0] = -I[0,j] = I/2, and by further symmetry we clearly have
    I[j,i] = -I[i,j], and I[i,i] = 0.  Writing KVL around the resistors
    surrounding one mesh square gives the relation on the mesh currents
    I[i,j] = (1/4)*(I[i,j-1]+I[i+1,j]+I[i,j+1]+I[i-1,j]), and it is only
    necessary to solve this along a 45 degree wedge due to symmetry.

    Note that this relation, that each mesh current is the average of its
    neighbors, is just the discrete form of Laplace's equation, so we can
    estimate the character of the solution from normal electrostatics.
    If we perform a conformal transformation of the 45 degree wedge via
    ln(z), we find that the mesh currents along any ray are equal.  In the
    discrete case the mesh current at I[i,j] will be approximately
    I[i,j] ~= (I/2)/(PI/2)*ATN(i,j).  Near the origin, the discrete nature will
    mess this up, but far away it is a fair approximation.  This conforms to
    intuition, since these mesh currents will approach each other far from the
    origin, and sum to nearly zero along any resisitor.

    To numerically solve this problem for the finite grid you can use
    Gauss-Seidel iteration.  Fix the values of I at the sides of the wedge,
    and estimate the values along the circular border with the ATN approx
    above, and initialize the interior points via the ATN approx as well.
    Then just iteratively improve I[i,j] by settting it to the average of
    its neighbors and repeat.  This should converge to the solution because
    the matrix of equations is diagonally dominant, and I think, positive
    definite.  You can accelerate the iteration with the usual tricks like
    overrelaxation (make something like 1.5 times the change to any I
    each iteratin) and Aitken's delta-squared extrapolation.

    Now, to get an idea of the mesh currents near the origin for an infinite
    boundry you can extrapolate to it.  Assume you've calculated the
    mesh currents for a number of wedge radii (say the sequence 24, 32, 48,
    64, 96, etc) - you will find the final values near the origin to be
    converging to something.  The idea is to assume these mesh currents
    have a power series expansion in h = 1/n (n = radius of wedge), and
    by using several approximations above, eliminate the leading terms of
    the expansion and extrapolate to the limit, where n -> infinity, h -> 0.
    Naturally, you can use the previous estimates of a given grid size as
    the starting values for the next size up to save time.  This technique
    will give surprisingly rapid convergence to the limiting values.

    I don't think the mesh currents in the limiting case have any simple
    relation in the discrete case - one way is to calculate them and find
    out!  I played with the problem a bit, hoping that the mesh currents
    would fall out as something simple like Pascal's triangle, but no luck
    so far...  Perhaps the problem is related to certain problems in
    crystallography where you need to sum up multidimensional series
    over the crystal lattice.

    - Jim
716.4KIRK::KOLKERTue Jun 16 1987 12:254
    re .0 .1
    correct me if I am wrong. Isn't this a numerical solution to the
    Dirichlet Problem, about which much has been written?
    
716.5ENGINE::ROTHTue Jun 16 1987 13:0420
    Re .4 - yes, I was only pointing that out and quoting some known
    results...

    However, there is a difference, since the stated problem is not
    to find an approximation but to solve a problem on a grid.

    I tried iterating the solution for a few sizes of grid (16, 32, 64, 128)
    with a simple minded averaging of neighboring mesh currents and
    noticed that the currents near the origin converge to a limit with
    a power series expansion of the form

	x0 + x6*(1/n)^6 + x8*(1/n)^8 + ...

    That is, the accuracy seems to go up by 64 for each doubling of the
    size of the grid.  I then printed the rational approximants to the
    mesh current at [1,2], but it did not seem to be a simple rational
    number, or an obvious quadratic.  Too bad... the problem seems to have
    no neat closed form solution.

    - Jim