Math explanation

[tomer953]

Hi,

Could you please ellaborate on your algorithem?
what is the math behinds it,
for example, what is this:
ftt = [0]+[3*(h[i+1]-h[i])/(w[i+1]+w[i]) for i in range(N-1)]+[0]
this is second derivative of f(x) ? if so, why multiply by 3 ?
why A,B,C,D is computed like that?
I read a lot of articles about the different algorithems, but they all use Matrix to solve system of equations.. while you did it very simple.

It would be awesome to attach a simple "Proof" of your solution.

Great work, thank you very much, Tomer.

[barakman]

@tomer953:
Hi Tomer.
Thank you, I'm glad that you've found it useful.
Yes, ftt stands for second derivative ("f tag tag").
To be honest, I implemented this some 6 or 7 years ago, based on my Numerical Analysis class notebook which dates back to somewhere around 2001 (back in the days when notebooks were still in use).
So I'm gonna have a hard time recalling why I did things this way.
I can look it up in the top shelf of a "back-end" closet, if you really need to understand the math.
For the record, this is Cubic Spline that I've implemented here (perhaps those matrices that you've mentioned are used in some other form of Spline).
In any case, I'll have a look at the code and see if I can answer your questions about 3, A, B, C and D.
Thanks :)

[tomer953]

Much appreciated.

If it helps, this is looks like the similar algo to your code:
https://www.math.ntnu.no/emner/TMA4215/2008h/cubicsplines.pdf

It would be great to understand how you calclated the coefficients

[barakman]

@tomer953:
So I found the notebook, and even the related page in that notebook (not an easy task when you don't have the Ctrl/F option).

We start by defining a function f(x) such that f''(x0) = 0 = f''(xn).
Then, the Matrix is just a step on the way, in order to calculate f''(x) for each value of x in our n input points (except x0 and xn, for which we have already defined f''(x) = 0).

The result of that matrix is that ftt[i+1] = 6*(h[i+1]-h[i])/(2(w[i+1]+w[i])).
So that's where the multiplication by 3 comes from (6 in the numerator and 2 in the denominator).

Thanks

[tomer953]

Hi,
Ctrl-F for notebooks could be the a nice startup lol :), thank you so much.

if you can digg a little bit more, please take a look here in slides 19-20

so I assume that, if we change your code from: "w" -> "h", "h" -> "b"
this slides is what you are building,
then the "ftt" (Zi) = Ui / Vi.
__
Sidenote:
I can understand why is it correct for: [v1] * [Z1] = [U1]
so this leads to z1 = U1/V1 and this explains the "3*.." part, but can't understand why this is the case for more complex matrix like:
[ v1 h1] [ Z1 ] = [ u1 ]
[ h1 v2] [ Z2 ] [ u2 ]
since in this case we need to solve system of equations.
if its too complex, so nevermind.
__

but what I really need to understand, after we find the Z1..Zn-1 ("Ftt")
how you calculated "A,B,C" (D = Yi so its easy)
I Can guess that "A" is some manipulation to slide number 17.

Thank you so much.

[tomer953]

@barakman , hey sorry for the double comment,
but if you plan to answer, I will be appreciate if it will be in the next couple of days, since I need to explain about the alg in some school task...

🙏