Implicit Finite Difference Method (FDM)

OK, let’s just keep going. This time: Implicit FDM.

Last time, when we approximated the Black-Scholes PDE,

this version — that was Explicit FDM.

So now, this Implicit FDM thing — how does it approximate?

Same idea, except instead of doing a backward difference in $t$, we do a forward difference. That is,

this differential equation — we approximate it

like this!!!

So why does approximating it this way make it “implicit”?!?!

We approximate it like this precisely so we can solve it implicitly — once you plug it in and tidy it all up~~~, you’ll see it really is Implicit!!!??? If that still doesn’t click, just plug it in and tidy it up!!! heh heh heh

Call me crazy, but I’m going to type the whole thing into the equation editor!!!

…Whoa. I actually typed all of that. I’m nuts…

Anyway!!!! Here’s what Implicit FDM is telling us!!!

— which I’ll restate, equivalently, as

What the equation is saying

OK so what is this equation actually saying~~~

Visually, it’s saying this. heh heh heh But here’s the thing.

The values we know — the knowns — they’re over here. And so:

In Explicit FDM, we could figure out the unknown middle part like this — whoosh whoosh whoosh whoosh whoosh. But now, in the Implicit FDM case,

— NOT!!! We don’t have to be stumped!!!

Three unknowns, three equations

Like in the figure above, write in approximation 1, approximation 2, approximation 3, and look at them.

(Note: this is assuming we’ve split $S$ into 4 equal pieces.)

Roll out equations 1, 2, 3 in one go — brrrrrrt — and you get

…this kind of shape??? You see it, right?

Once you write it out like this — 3 unknowns, 3 equations!!!

Aha~~~ the number of unknowns matches the number of equations (and these equations are independent), so we can pin down the 3 unknowns, one, two, three — snap snap snap!!! — uniquely.

Now I’ll take those 3 equations rolled out in the figure above and, below, rearrange them so that the unknowns sit on the left and the knowns on the right, and write the whole thing as a matrix.

Yo-ho~~~ okey-dokey~~~ nice~~~ So: the vector we don’t know,

just kick that left-hand matrix over to the right as an inverse,

and bam — that pins it down. heh heh

What if there are more unknowns?

Now, one thing that might have you a little suspicious!!!

You might be thinking “OK but this 3×3 matrix only shows up because of this specific tiny example, right?”

Well, here’s how to think about it.

If you’ve got 4 unknowns stacked in a column like this, then in matrix form:

it’d be a 4×4 matrix!!! 100 unknowns? Yeah, you guessed it — 100×100. lol heh heh heh

Whoa, so in the fully general case you get an $n \times n$ matrix, and to actually solve the matrix equation you need to be able to invert an $n \times n$ matrix…

This is insane… I’m going nuts…

So Implicit FDM needs inverse matrices, which means we need to actually study inverse matrices…. But if you’ve done linear algebra, you already know the move — find the adjoint, multiply by 1 over the determinant, done!!! (See The Adjoint Matrix (Linear Algebra I Studied #15).)

But now I’m sitting here wondering — how on earth do you express that whole adjoint-and-determinant business in code…. Turns out, when a computer inverts a matrix, rather than a person by hand, it can do it differently!!! lol It’s called LU decomposition!!!

If I tried to cram LU decomposition in here too, the scroll pressure would be absolutely insane, right??? So — next post.

---

Heads-up. The figures here are the original notes, slips and all. A few things to watch for:

• In the handwritten system of three equations, $a_j$ and $c_j$ trade places: from $f_{i+1,j} = a_j f_{i,j+1} + b_j f_{i,j} + c_j f_{i,j-1}$, the first row is $c_3 f_{3,2} + b_3 f_{3,3} + a_3 f_{3,4} = f_{4,3}$, and likewise for the others. Solved that way, the system gives 25.3248, 0.6927 and 0.0060, the values the VBA program prints.
• In the difference pictures, a time difference changes $i$, not $j$: the backward difference is $\frac{f_{i,j} - f_{i-1,j}}{\Delta t}$ and the forward one $\frac{f_{i+1,j} - f_{i,j}}{\Delta t}$.