The algorithmic possibilities for piecewise linear and cubic spline approximation are explored in a different way in Van Loan Van Loan (2000). In that source, a binary search is used to find the interval for evaluating the piecewise polynomial interpolant.
Further details regarding the derivation of the cubic spline equations, with an emphasis on minimizing memory usage, may be found in a number of sources, e.g., Burden and Faires Burden & Faires (2001), Cheney and Kincaid Cheney & Kincaid (2012), and Atkinson and Han Atkinson & Han (2004). Comprehensive theoretical results can be found in de Boor de Boor (1978).
On a historical note, Carl de Boor was elected to several National Academies of Science (USA, Poland, and Germany, e.g.) and was awarded the (USA) National Medal of Science in 2003 for his work on splines. Splines continue to be important for computer-aided design and computer graphics, among other applications.
An excellent and pragmatic introduction to finite-difference methods is by Fornberg Fornberg (1998). Numerical integration is a large topic unto itself; one longer introduction to it is by Davis and Rabinowitz Davis & Rabinowitz (2014).
- Van Loan, C. F. (2000). Introduction to Scientific Computing: A Matrix-Vector Approach Using MATLAB. Prentice Hall.
- Burden, R. L., & Faires, J. D. (2001). Numerical Analysis (7th ed). Brooks/Cole.
- Cheney, E. W., & Kincaid, D. R. (2012). Numerical Mathematics and Computing. Cengage Learning.
- Atkinson, K. E., & Han, W. (2004). Elementary Numerical Analysis (3rd ed). J. Wiley & Sons.
- de Boor, C. (1978). A Practical Guide to Splines. Springer-Verlag.