Numberical Analysis --- Interpolation & Polynomial Approximation

  If a function $y=f(x)$ is too complicated for calculation or is even unknown, one way to approximate it is to first obtain its values $y_0=f(x_0),...,x_n=f(x_n)$ at a sequence of points $x_0,...,x_n$, and then construct a relatively simple approximating function $g(x)\approx f(x)$.

  If $g(x)$ satisfies that $g(x_i)=f(x_i)$ for all $i=0,...,n$, it is called the interpolating function of $f(x)$. The most commonly used interpolating functions are algebraic polynomials.

Interpolation and the Lagrange Polynomial

  Find a polynomial of degree $n$, $P_n(x)=a_0+a_1x+...+a_nx^n$, such that $P_n(x_i)=y_i$ for all $i=0,...,n$.

   $n=1$: Given $x_0,x_1;y_0,y_1$. Find $P_1(x)=a_0+a_1x$ such that $P_1(x_0)=y_0$ and $P_1(x_1)=y_1$. $P_1(x)$ is the line function through the two given points $(x_0,y_0)$ and $(x_1,y_1)$.
$$\Rightarrow \begin{aligned} P_1(x)&=y_0+\frac{y_1-y_0}{x_1-x_0}(x-x_0)\\ &=(\frac{x-x_1}{x_0-x_1})y_0+(\frac{x-x_0}{x_1-x_0})y_1\\ &=\sum\limits_{i=0}^1L_{1,i}(x)y_i\\ \end{aligned}$$

  $n\geq 1$: Find $L_{n,i}(x)$ for $i=0,...,n$ such that $L_{n,i}(x_j)=\delta_{ij}$. Then let $P_n(x)=\sum\limits_{i=0}^nL_{n,i}(x)y_i$. Hence $P_n(x_i)=y_i$.

Each $L_{n,i}$ has $n$ roots $x_0,...,x_n$.

The $n$-th Lagrange interpolating polynomial:
$$L_{n,i}(x)=\prod\limits_{j\neq i,0\leq j\leq n}\frac{(x-x_j)}{(x_i-x_j)}\Rightarrow P_n(x)=\sum\limits_{i=0}^nL_{n,i}(x)y_i$$

Theorem: If $x_0,...,x_n$ are $n+1$ distinct numbers and $f$ is a function whose values are given at these numbers, then the $n$-th Lagrange interpolating polynomial is unique.

Proof: If not… Then there exists two polynomials $P_n(x)$ and $Q_n(x)$ both satisfying the interpolating conditions.
$$\Rightarrow D(x)=P_n(x)-Q_n(x)\text{ is a polynomial of degree }\leq n$$

Yet $D(x)$ has $n+1$ distinct roots $x_0,x_1,...,x_n$.

Note: The interpolating polynomial is NOT unique unless its degree is constrained to be no greater than $n$. A counterexample is $P(x)=L_n(x)+p(x)\prod\limits_{i=0}^n(x-x_i)$ where $p(x)$ can be a polynomial of any degree.

Analyze the Remainder

Suppose $a\leq x_0<x_1<...<x_n\leq b$ and $f\in C^{n+1}[a,b]$. Consider the truncation error $R_n(x)=f(x)-P_n(x)$

$$R_n(x)\text{ has at least }n+1\text{ roots}\Rightarrow R_n(x)=K(x)\prod\limits_{i=0}^n(x-x_i)$$

Fix any $x\neq x_i$ for all $i=0,...,n$. Define the function $g$ for $t$ in $[a,b]$ by
$$g(t)=R_n(t)-K(x)\prod\limits_{i=0}^n(t-x_i)$$
$g(x)$ has $n+2$ distinct roots $x_0,...,x_n,x\Rightarrow g^{(n+1)}(\xi_x)=0,\xi_x\in(a,b)$
$$f^{(n+1)}(\xi_x)-P_n^{(n+1)}(\xi_x)-K(x)(n+1)!=R_n^{(n+1)}(\xi_x)-K(x)(n+1)!$$
$$\Rightarrow K(x)=\frac{f^{(n+1)}(\xi_x)}{(n+1)!}\quad \Rightarrow R_n(x)=\frac{f^{(n+1)}(\xi_x)}{(n+1)!}\prod\limits_{i=0}^n(x-x_i)$$

Note:

• Since in most of the case $\xi_x$ cannot be determined, we obtain the upper bound of $f^{(n+1)}$ instead. That is, estimate an $M_{n+1}$ such that $|f^{(n+1)}|\leq M_{n+1}$ for all $x\in(a,b)$ and take $\frac{M_{n+1}}{(n+1)!}\prod\limits_{i=0}^n|x-x_i|$ as the upper bound of the total error.
• The interpolating polynomial is accurate for any polynomial function $f$ with degree $\leq n$ since $f^{(n+1)}(x)\equiv 0$

Example: Suppose a table is to be prepared for the function $f(x)=e^x$ for $x\in[0,1]$. Assume that each entry of the table is accurate up to 8 decimal places and the step size is $h$. What should $h$ be for linear interpolation to given an absolute error of at most $10^{-6}$?

Solution: Suppose that $[0,1]$ is partitioned into $n$ equal-spaced subintervals $[x_0,x_1],[x_1,x_2],...,[x_{n-1},x_n]$, and $x$ is in the interval $[x_k,x_{k+1}]$. Then the error estimation gives
$$\begin{aligned} |f(x)-P_1(x)|&=\left|\frac{f^{(2)}(\xi)}{2!}(x-x_k)(x-x_{k+1})\right|\\ &=\left|\frac{e^\xi}{2}(x-kh)(x-(k+1)h)\right|\\ &\leq \frac{e}{2}\times \frac{h^2}{4}\\ \end{aligned}$$
$$\frac{eh^2}{8}\leq 10^{-6}\Rightarrow h\leq 1.72\times 10^{-3}$$

Simply take $n=1000$ and $h=0.001$.

Example: Given $\sin \frac{\pi}{6}=\frac{1}{2},\sin \frac{\pi}{4}=\frac{1}{\sqrt{2}},\sin \frac{\pi}{3}=\frac{\sqrt{3}}{2}$. Use the linear and the quadratic Lagrange polynomial of $\sin x$ to compute $\sin 50^\circ$ and then estimate the errors.

\textbf{Solution:} First use $x_0,x_1$ and $x_1,x_2$ to compute the linear interpolations.
$$\text{Use }x_0=\frac{\pi}{6},x_1=\frac{\pi}{4}\quad \Rightarrow P_1(x)=\frac{x-\pi/4}{\pi/6-\pi/4}\times \frac{1}{2}+\frac{x-\pi/6}{\pi/4-\pi/6}\times \frac{1}{\sqrt{2}}$$
$$\sin 50^\circ \approx P_1\left(\frac{5\pi}{18}\right)\approx0.77614\quad \text{Here }f(x)=\sin x,f^{(2)}(\xi_x)=-\sin \xi_x,\xi_x\in\left(\frac{\pi}{6},\frac{\pi}{3}\right)$$
$$\text{and }\frac{1}{2}<\sin \xi_x<\frac{\sqrt{3}}{2},R_1(x)=\frac{f^{(2)}(\xi_x)}{2!}(x-\frac{\pi}{6})(x-\frac{\pi}{4})$$
$$\Rightarrow -0.01319<R_1\left(\frac{5\pi}{18}\right)<-0.00762$$
$$\text{Error of extrapolation}\approx-0.01001; \text{Error of interpolation}\approx0.00596$$
$$\text{Now use }x_0,x_1 \text{ and }x_2\text{ to compute the quadratic interpolation.}$$
$$\begin{aligned} P_2(x)&=\frac{(x-\pi/4)(x-\pi/3)}{(\pi/6-\pi/4)(\pi/6-\pi/3)}\times \frac{1}{2}+\frac{(x-\pi/6)(x-\pi/3)}{(\pi/4-\pi/6)(\pi/4-\pi/3)}\times \frac{1}{\sqrt{2}}\\&+\frac{(x-\pi/6)(x-\pi/4)}{(\pi/3-\pi/6)(\pi/3-\pi/4)}\times \frac{\sqrt{3}}{2}\\ \end{aligned}$$
$$R_2(x)=\frac{-\cos \xi_x}{3!}(x-\frac{\pi}{6})(x-\frac{\pi}{4})(x-\frac{\pi}{3});\frac{1}{2}<\cos \xi_x<\frac{\sqrt{3}}{2}$$
$$\text{Error of the quadratic interpolation}\approx 0.00061$$

Definition: Let $f$ be a function defined at $x_0,x_1,...,x_n$, and suppose that $m_1,...,m_k$ are $k$ distinct integers with $0\leq m_i\leq n$ for each $i$. The Lagrange polynomial that agrees with $f(x)$ at the $k$ points $x_{m_1},...,x_{m_k}$ denotes by $P_{m_1,...,m_k}(x)$.

Theorem: Let $f$ be defined at $x_0,..,x_k$, and let $x_i$ and $x_j$ be two distinct numbers in this set. Then
$$P(x)=\frac{(x-x_j)P_{0,1,...,j-1,j+1,...,k}(x)-(x-x_i)P_{0,1,...,i-1,i+1,...,k}(x)}{(x_i-x_j)}$$
describes the $k$-th Lagrange polynomial that interpolates $f$ at the $k+1$ points $x_0,x_1,...,x_k$.

Proof: For any $0\leq r\leq k$ and $r\neq i$ and $j$, the two interpolating polynomials on the numerator are equal to $f(x_r)$ at $x_r$, so $P(x_r)=f(x_r)$. The first polynomials on the numerator equals $f(x_i)$ at $x_i$, while the second term is zero, so $P(x_i)=f(x_i)$. Similarly $P(x_j)=f(x_j)$. The $k$-th Lagrange polynomial that interpolates $f$ at the $k+1$ points $x_0,x_1,...,x_k$ is unique.

Divided Differences

The $1^{\text{st}}$ divided difference of $f$ w.r.t. $x_i$ and $x_j$:
$$f[x_i,x_j]=\frac{f(x_i)-f(x_j)}{x_i-x_j}\quad(i\neq j,x_i\neq x_j)$$

The $2^{\text{nd}}$ divided difference of $f$ w.r.t. $x_i,x_j$ and $x_k$.
$$f[x_i,x_j,x_k]=\frac{f[x_i,x_j]-f[x_j,x_k]}{x_i-x_k}\quad(i\neq k)$$

The $k+1$st divided difference of $f$ w.r.t.$x_0,...,x_{k+1}$:
$$\begin{aligned} f[x_0,...,x_{k+1}]&=\frac{f[x_0,x_1,...,x_k]-f[x_1,...,x_k,x_{k+1}]}{x_0-x_{k+1}}\\ &=\frac{f[x_0,...,x_{k-1},x_k]-f[x_0,...,x_{k-1},x_{k+1}]}{x_k-x_{k+1}}\\ \end{aligned}$$

As a matter of fact, $f[x_0,...,x_k]=\sum\limits_{i=0}^k\frac{f(x_i)}{\omega_{k+1}'(x_i)}$

where $\omega_{k+1}(x)=\prod\limits_{i=0}^k(x-x_i),\omega_{k+1}'(x_i)=\prod\limits_{0\leq j\leq k,j\neq i}(x_i-x_j)$

The value of $f[x_0,...,x_k]$ is independent of the order of the numbers $x_0,...,x_k$.

   Newton’s Interpolation
$$N_n(x)=a_0+a_1(x-x_0)+a_2(x-x_0)(x-x_1)+...+a_n(x-x_0)...(x-x_{n-1})$$
$$\begin{cases} f(x)=f(x_0)+(x-x_0)f[x,x_0]\\ f[x,x_0]=f[x_0,x_1]+(x-x_1)f[x,x_0,x_1]\\ ......\\ f[x,x_0,...,x_{n-1}]=f[x_0,...,x_n]+(x-x_n)f[x,x_0,...,x_n]\\ \end{cases}$$
$$\Rightarrow \begin{aligned} f(x)&=f(x_0)+f[x_0,x_1](x-x_0)+f[x_0,x_1,x_2](x-x_0)(x-x_1)+...\\ &+f[x_0,...,x_n](x-x_0)...(x-x_{n-1})\\ &+f[x,x_0,...,x_n](x-x_0)...(x-x_{n-1})(x-x_n)\\ &=N_n(x)+R_n(x)\\ \end{aligned}$$
$$a_i=f[x_0,...,x_i]$$

Note:

• Since the $n$-th interpolating polynomial is unique, $N_n(x)=P_n(x)$.
• They must have the same truncation error. That is,
  $$f[x,x_0,...,x_n]\omega_{k+1}(x)=\frac{f^{(n+1)}(\xi_x)}{(n+1)!}\omega_{k+1}(x)$$
  $$\Rightarrow f[x_0,...,x_k]=\frac{f^{(k)}(\xi)}{k!},\xi\in(x_{\text{min}},x_{\text{max}})$$

   Formulae with Equal Spacing

If the points are equally spaced:$x_i=x_0+ih\quad(i=0,...,n)$

forward difference:
$$\Delta f_i=f_{i+1}-f_i$$
$$\Delta^kf_i=\Delta(\Delta^{k-1}f_i)=\Delta^{k-1}f_{i+1}-\Delta^{k-1}f_i$$

backward difference:
$$\nabla f_i=f_i-f_{i-1}$$
$$\nabla^kf_i=\nabla^{k-1}f_i-\nabla^{k-1}f_{i-1}$$

centered difference:
$$\delta^kf_i=\delta^{k-1}f_{i+\frac{1}{2}}-\delta^{k-1}f_{i-\frac{1}{2}}$$
$$\text{where }f_{i\pm \frac{1}{2}}=f(x_i\pm \frac{h}{2})$$

  Some important properties

1. Linearity:$\Delta(af(x)+bg(x))=a\Delta f+b\Delta g$

2. If $f(x)$ is a polynomial of degree $m$, then $\Delta^kf(x)(0\leq k\leq m)$ is a polynomial of degree $m-k$ and $\Delta^kf(x)=0\quad (k>m)$

3. The values of the differences can be obtained from the function
   $$\Delta^nf_k=\sum\limits_{j=0}^n(-1)^jC_n^jf_{n+k-j}\quad \nabla^nf_k=\sum\limits_{j=0}^n(-1)^{n-j}C_n^jf_{k+j-n}$$

4. And vice-versa $f_{n+k}=\sum\limits_{j=0}^nC_n^j\Delta^jf_k$

5. $$f[x_0,...,x_k]=\frac{\Delta^kf_0}{k!h^k},f[x_n,x_{n-1},...,x_{n-k}]=\frac{\nabla^kf_k}{k!h^k}$$
   $$\text{From }R_n\Rightarrow f^{(k)}(\xi)=\frac{\Delta^kf_0}{h^k}$$

   Newton’s Formulae
$$N_n(x)=f(x_0)+f[x_0,x_1](x-x_0)+...+f[x_0,...,x_n](x-x_0)...(x-x_{n-1})$$

   Newton’s forward-difference formula

Let $x=x_0+th$, then $N_n(x)=N_n(x_0+th)=\sum\limits_{k=0}^nC_t^k\Delta^kf(x_0)$
$$R_n(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}t(t-1)...(t-n)h^{n+1},\xi\in(x_0,x_n)$$

   Newton’s backward-difference formula

Reverse the order of the points
$$N_n(x)=f(x_n)+f[x_n,x_{n-1}](x-x_n)+...+f[x_n,...,x_0](x-x_n)...(x-x_1)$$

Let $x=x_n+th$, then $N_n(x)=N_n(x_n+th)=\sum\limits_{k=0}^n(-1)^kC_{-t}^k\nabla^kf(x_n)$

Hermite Interpolation

Find the osculating polynomial $P(x)$ such that $P(x_i)=f(x_i),P'(x_i)=f'(x_i),...,P^{(m-i)}(x_i)=f^{(m-i)}(x_i)$ for all $i=0,1,...,n$.

Note:

• Given $N$ conditions (and hence $N$ equations), a polynomial of degree $N-1$ can be determined.
• The osculating polynomial that agrees with $f$ and all its derivatives of order $\leq m_0$ at one point $x_0$ is just the Taylor polynomial
  $$P(x)=f(x_0)+f'(x_0)(x-x_0)+...+\frac{f^{(m_0)}}{m_0!}(x-x_0)^{x_0}$$
  with remainder $R_n(x)=f(x)-\varphi(x)=\frac{f^{(m_0+1)}(\xi)}{(m_0+1)!}(x-x_0)^{m_0+1}$
• The case when $m_i=1$ for each $i=0,1,...,n$ gives the Hermite polynomials.

Example: Suppose $x_0\neq x_1\neq x_2$. Given $f(x_0),f(x_1),f(x_2)$ and $f'(x_1)$, find the polynomial $P(x)$ such that $P(x_i)=f(x_i),i=0,1,2$, and $P'(x_1)=f'(x_1)$. Analyze the errors.

Solution: First of all, the degree of $P(x)$ must be 3. Similar to Lagrange polynomials, we may assume the form of Hermite polynomial as:
$$P_3(x)=\sum\limits_{i=0}^2f(x_i)h_i(x)+f'(x_1)\hat{h_1}(x)$$
where $h_i(x_j)=\delta_{ij},h_i'(x_1)=0,\hat{h_1}(x_i)=0,\hat{h_1'}(x_1)=1$

$h_0(x)$: Has roots $x_1,x_2$, and $h_0'(x_1)=0\Rightarrow x_1$ is a multiple root.
$$\begin{cases} h_0(x)=C_0(x-x_1)^2(x-x_2)\\ h_0(x_0)=1\Rightarrow C_0\\ \end{cases}\Rightarrow h_0(x)=\frac{(x-x_1)^2(x-x_2)}{(x_0-x_1)^2(x_0-x_2)}$$

$h_2(x)$: Similar to $h_0(x)$.

$h_1(x)$: Has roots $x_0,x_2\Rightarrow h_1(x)=(Ax+B)(x-x_0)(x-x_2)$. $A$ and $B$ can be solved with $h_1(x_1)=1$ and $h_1'(x_1)=0$.

$\hat{h_1}(x)$: Has roots $x_0,x_1,x_2\Rightarrow\hat{h_1}(x)=C_1(x-x_0)(x-x_1)(x-x_2)$. $\hat{h_1'}(x_1)=1\Rightarrow C_1$ can be solved.

In general, given $x_0,...,x_n;y_0,...,y_n$ and $y_0',...,y_n'$. The Hermite polynomial $H_{2n+1}(x)$ satisfies $H_{2n+1}(x_i)=y_i$ and $H_{2n+1}'(x_i)=y_i'$ for all $i$.

Solution: Let $H_{2n+1}(x)=\sum\limits_{i=0}^ny_ih_i(x)+\sum\limits_{i=0}^ny_i'\hat{h_i}(x)$ where $h_i(x_j)=\delta_{ij},h_i'(x_j)=0,\hat{h_i}(x_j)=0,\hat{h_i'}(x_j)=\delta_{ij}$.

$h_i(x)$: $x_0,...,\hat{x_i},...,x_n$ are all roots with multiplicity 2
$$\Rightarrow h_i(x)=(A_ix+B_i)L_{n,i}^2(x)$$
$A_i$ and $B_i$ can be solved by $h_i(x_j)=1$ and $h_i'(x_i)=0$
$$\Rightarrow h_i(x)=[1-2L_{n,i}'(x_i)(x-x_i)]L_{n,i}^2(x)$$

$\hat{h_i}(x)$: All the roots $x_0,...,x_n$ have multiplicity 2 except $x_i\Rightarrow$
$$\begin{cases} \hat{h_i}(x)=C_i(x-x_i)L_{n,i}^2(x)\\ \hat{h_i'}(x)=1\Rightarrow C_i=1\\ \end{cases}\Rightarrow \hat{h_i}(x)=(x-x_i)L_{n,i}^2(x)$$
If $a=x_0<x_1<...<x_n=b,f\in C^{2n}[a,b]$, then
$$R_n(x)=\frac{f^{(2n+2)}(\xi_X)}{(2n+2)!}\left[\prod\limits_{i=0}^n(x-x_i)\right]^2$$

Cubic Spline Interpolation

  Piecewise linear interpolation

Approximate $f(x)$ by linear polynomials on each subinterval $[x_i,x_{i+1}]$:
$$f(x)\approx P_1(x)=\frac{x-x_{i+1}}{x_i-x_{i+1}}y_i+\frac{x-x_i}{x_{i+1}-x_i}y_{i+1}\text{ for }x\in[x_i,x_{i+1}]$$
Let $h=\max |x_{i+1}-x_i|$. Then $P_1^h(x)\to f(x)$ as $h\to 0$.

  Hermite piecewise polynomials

Given $x_0,..,x_n;y_0,...,y_n;y_0',...,y_n'$ Construct the Hermite polynomial of degree 3 with $y$ and $y'$ on the two endpoints of $[x_i,x_{i+1}]$.

   Cubic Spline

Definition: Given a function $f$ defined on $[a,b]$ and a set of nodes $a=x_0<x_1<...<x_n=b$, a cubic spline interpolant $S$ for $f$ is a function that satisfies the following conditions:

a. $S(x)$ is a cubic polynomial, denoted $S_i(x)$, on the subinterval $[x_i,x_{i+1}]$ for each $i=0,1,...,n-1$;

b. $S(x_i)=f(x_i)$ for each $i=0,1,..,n$;

c. $S_{i+1}(x_{i+1})=S_i(x_{i+1})$ for each $i=0,1,...,n-2$;

d. $S'_{i+1}(x_{i+1})=S_i'(x_{i+1})$ for each $i=0,1,...,n-2$;

e. $S_{i+1}''(x_{i+1})=S_i''(x_{i+1})$ for each $i=0,1,...,n-2$.

   Method of Bending Moment

Let $h_j=x_j-x_{j-1}$ and $S(x)=S_j(x)$ for $x\in[x_{j-1},x_j]$. Then $S_j''(x)$ is a polynomial of degree 1, which can be determined by the values of $f$ on 2 nodes.

Assume $S_j''(x_{j-1})=M_{j-1},S_j''(x_j)=M_j$. Then for all $x\in[x_{j-1},x_j]$,
$$S_j''(x)=M_{j-1}\frac{x_j-x}{h_j}+ M_j\frac{x-x_{j-1}}{h_j}$$

Integrate $S_j''(x)$ twice, we obtain $S_j'(x)$ and $S_j(x)$:
$$S_j'(x)=-M_{j-1}\frac{(x_j-x)^2}{2h_j}+M_{j-1}\frac{(x-x_{j-1})^2}{2h_j}+A_j$$
$$S_j(x)=M_{j-1}\frac{(x_j-x)^3}{6h_j}+M_j\frac{(x-x_{j-1})^3}{6h_j}+A_jx+B_j$$
$$A_j=\frac{y_j-y_{j-1}}{h_j}-\frac{M_j-M_{j-1}}{h}h_j$$
$$A_jx+B_j=\left(y_{j-1}-\frac{M_{j-1}}{6}h_j^2\right)\frac{x_j-x}{h_j}+\left(y_j-\frac{M_j}{6}h_j^2\right)\frac{x-x_{j-1}}{h_j}$$

Now solve for $M_j$: Since $S'$ is continuous at $x_j$
$$[x_{j-1},x_j]:S_j'(x)=-M_{j-1}\frac{(x_j-x)^2}{2h_j}+M_j\frac{(x-x_{j-1})^2}{2h_j}+f[x_{j-1},x_j]-\frac{M_j-M_{j-1}}{6}h_j$$
$$[x_j,x_{j+1}]:S_{j+1}'(x)=-M_j\frac{(x_{j+1}-x)^2}{2h_{j+1}}+M_{j+1}\frac{(x-x_j)^2}{2h_{j+1}}+f[x_j,x_{j+1}]-\frac{M_{j+1}-M_j}{6}h_{j+1}$$
From $S_j'(x_j)=S_{j+1}'(x_j)$, we can combine the coefficients for $M_{j-1},M_j$, and $M_{j+1}$. Define $\lambda_j=\frac{h_{j+1}}{h_j+h_{j+1}},\mu_j=1-\lambda_j$, and $g_j=\frac{6}{h_j+h_{j+1}}(f[x_j,x_{j+1}]-f[x_{j-1},x_j])$
$$\Rightarrow \mu_jM_{j-1}+2M_j+\lambda_jM_{j+1}=g_j\quad \text{for }1\leq j\leq n-1$$
That is, we have $n+1$ unknowns but only $n-1$ equations. Extra 2 boundary conditions are needed.

$S'(a)=y_0',S'(b)=y_n'\quad \text{/*Clamped boundary*/}$

$$[a,x_1]:S_1'(x)=-M_0\frac{(x_1-x)^2}{2h_1}+M_1\frac{(x-a)^2}{2h_1}+f[x_0,x_1]-\frac{M_1-M_0}{6}h_1$$

Similar for $S_n'(x)$ on $[x_{n-1},b]$:
$$\Rightarrow \begin{cases} 2M_0+M_1=\frac{6}{h_1}(f[x_0,x_1]-y_0')=g_0\\ M_{n-1}+2M_n=\frac{6}{h_n}(y_n'-f[x_{n-1},x_n])=g_n\\ \end{cases}$$

$S''(a)=y_0''=M_0,S''(b)=y_n''=M_n$
Then $\lambda_0=0,g_0=2y_0'';\mu_n=0,g_n=2y_n''$

The case when $M_0=M_n=0$ is called a free boundary, and when that occurs, the spline is called a Natural Spline.

Periodic Boundary: If $f$ is a periodic function, that is, $y_n=y_0$ and $S'(a^+)=S'(b^-)\Rightarrow M_0=M_n$

Note:

• Cubic Spline can be uniquely determined by its boundary conditions as long as the coefficient matrix is strictly diagonally dominant.
• If $f\in C[a,b]$ and $\frac{\max h_i}{\min h_i}\leq C<\infty$. Then $S(x)\to f(x)$ as $\max h_i\to 0$. That is, the accuracy of approximation can be improved by adding more nodes without increasing the degree of the splines.