I hope I can bring these two disparate ideas together. Here goes!
I will first talk about implicit methods which are used for stiff differential equations. Here is an introduction which may help some in following my introduction. I discuss heat flow and its calculation as a motivation for these mathematical calculation techniques. The stuff immediately below, however introduces the same mathematical problem with a simpler fanciful problem.
We can give meanings to the numbers used in the heat flow scheme. Our algorithm passes over the trees first from left to right and then from right to left. During the rightward pass, we know how high a tree will be as a linear formula involving only the new height of the tree to its right. From this state of knowledge we can, with just a few arithmetic operations, proceed to the state where we know the same for the next tree. When we have done this for the next to last tree we know its new height for the new height of the last tree is given. We can now pass to the left employing the formula we left behind at each tree, computing its new hight in light of the now known hight to the tree to its right.
This reasoning amounts to thinking about the meanings of the expressions that we are taught to manipulate in the algebra class recalled above. The messages (A B L) towards the right, between neighboring trees means:
I will be this tall: A + B*(how ever tall you turn out to be.) Please reply how tall that makes you and these here (L) farther neighbors? (L is the list of trees to your right.)The returned messages mean:
Here is the list of heights, me first.Let fh and lh be the heights of the first and last trees. Let lst be a list of triples, one triple for each tree, from left to right, except for the first and last trees. For each tree the triple (x y z) means that the new height of this tree will be
The calculations for a and b come from these considerations:
We call my new unknown height “h”. We call my neighbor’s new unknown height “q”.
h = x*(A+B*h) + y + z*q
(1 – x*B)*h = x*A + y + z*q
h = (x*A + y)/(1 – x*B) + (z/(1 – x*B))*q = a + b*q
where a = (x*A + y)/(1 – x*B)
and b = z/(1 – x*B)
(define (solve lst fh lh) (cons fh (let qry ((A fh)(B 0)(L lst)) (if (null? L) (list lh) (let* ( (v (car L)) (x (car v)) (y (cadr v)) (z (caddr v)) (r (/ ( - 1 (* x B)))) (a (* (+ (* x A) y) r)) (b (* z r)) (resp (qry a b (cdr L)))) (cons (+ a (* b (car resp))) resp) ))))) ; A check: (define (evl ls ans) (if (null? ls) '() (cons (- (+ (* (car ans) (caar ls)) (cadar ls) (* (caddr ans) (caddar ls))) (cadr ans)) (evl (cdr ls)(cdr ans))))) ; A test: (define ls '((1 3 2)(2 7 3))) (solve ls 4 5) ; => (4 -17 -12 5) (evl ls (solve ls 4 5)) ; => (0 0) ; Another test (define ls '((0.03 3 0.02)(0.034 3.6 0.28)(0.022 4 0.018))) (solve ls 4 5) ; => (4 3.217693825768255 4.884691288412744 4.197463208345081 5) (evl ls (solve ls 4 5)) ; => (0.0 0.0 -8.881784197001252e-16)And a C version
Here is some code to do more general higher dimensional mesh calculations. It is more general, more complex and somewhat slower.