Kapitola 3
Aproximace funkcí. Polynomiální interpolace. Splajny
Aproximace funkcí v počítači
Funkce je v počítači nutné reprezentovat diskrétně. Možností, jak to udělat, je celá řada: na gridu, v určité bázi (polynomy apod.), řetězovým zlomkem atd. Nejčastěji se používají polynomy, případně racionální funkce, neboť je lze snadno vyčíslit pomocí základních operací.
I když ovšem použijeme např. polynomy, máme stále několik možností, jak danou funkci aproximovat. Nejběžnější metody aproximace jsou následující tři.
Interpolace
Hodnoty funkce (případně její derivace) jsou zadány v bodech \(x_0, \dots, x_n\) a hledáme funkci \(\phi(x)\) z určité třídy funkcí (nejčastěji polynomů) takovou, že
\begin{equation}\label{eq:lagrange-podminka} \phi(x_i) = f(x_i), \quad \text{pro } i = 0, \dots, n, \end{equation}což je Lagrangeova interpolace, případně navíc
\begin{equation}\label{eq:hermite-podminka} \phi^{(k)}(x_i) = f^{(k)}(x_i), \quad \text{pro } i = 0, \dots, n, \end{equation}což je Hermiteova interpolace. Takto získaná funkce aproximuje původní funkci \(f(x)\) mezi body \(x_i\) (interpolace), případně i vně intervalu \(\langle x_0, x_n \rangle\) (extrapolace).
Metoda nejmenších čtverců
Opět hledáme aproximaci \(\phi(x)\) funkce \(f(x)\) zadané v bodech \(x_0, \dots, x_n\), ovšem nyní takovou, že
\begin{equation}\label{eq:mnc-diskretni} \sum_{i=0}^{n} w_i \left( f(x_i) - \phi(x_i) \right)^2 = \min_{\substack{\text{přes} \\ \forall \psi \text{ z jisté třídy funkcí}}} \sum_{i=0}^{n} w_i \left( f(x_i) - \psi(x_i) \right)^2 , \end{equation}kde \(w_i > 0\) jsou váhy jednotlivých funkčních hodnot.
Někdy lze minimalizovat i integrální výraz
\begin{equation}\label{eq:mnc-spojita} \int_a^b w(x) \left( f(x) - \phi(x) \right)^2 \mathrm{d}x = \min_{\psi} \int_a^b w(x) \left( f(x) - \phi(x) \right)^2 \mathrm{d}x , \end{equation}kde \(w(x)\) je (skoro všude) kladná na intervalu \(\langle a, b \rangle\), přičemž \(w \in L^2(\langle a, b \rangle)\).
Čebyševova aproximace
Hledáme \(\phi(x)\) takové, že
\begin{equation}\label{eq:cebysevova-aproximace} \max_{x \in \langle a,b \rangle} |\phi(x) - f(x)| \le \max_{x \in \langle a,b \rangle} |\psi(x) - f(x)| \quad \text{pro } \forall \psi \end{equation}z prostoru, ve kterém hledáme \(\phi\).
Volba normy a role polynomů
Volbou různých norem, případně seminorem, kterými poměřujeme blízkost funkcí, dostáváme různé aproximace. Nejčastěji se používá aproximace polynomy (případně funkcemi, které jsou po částech polynomy, tedy splajny) do určitého stupně \(n\).
Z analýzy znáte jednak Taylorův rozvoj, jednak platí Weierstrassova věta.
Nechť \(\langle a, b \rangle\) je konečný uzavřený interval a \(f\) je spojitá funkce na \(\langle a, b \rangle\), tj. \(f \in C(\langle a, b \rangle)\), a nechť \(\varepsilon > 0\) je libovolně malé. Pak existuje polynom \(p(x)\) takový, že
\[ |f(x) - p(x)| < \varepsilon \quad \text{pro } \forall x \in \langle a, b \rangle . \]V obou případech ovšem nic nevíme o stupni \(n\) polynomu, chceme-li aproximaci s určitou přesností. Postačuje přitom pouhá spojitost: i funkci jako \(|x|\) lze aproximovat polynomem libovolně přesně.
Budeme se zabývat především interpolací; k metodě nejmenších čtverců se vrátíme, až se budeme zabývat přeurčenými systémy lineárních rovnic.
Polynomiální interpolace
Polynomiální interpolace je nejjednodušší metodou aproximace funkce zadané v bodech \((x_i, f(x_i))\), \(i = 0, 1, \dots, n\). Jde ovšem o špatně podmíněnou úlohu a zvláště pro velká \(n\) můžeme dostat velmi „divoké“ polynomy (Rungeův jev). Využívá se také např. při odvozování vztahů pro numerickou aproximaci derivace funkce a integraci funkcí (viz později).
Máme-li \(f(x)\) zadanou v \(n+1\) bodech \((x_i, f(x_i))\), \(i = 0, \dots, n\), které jsou navzájem různé, pak existuje jediný polynom stupně \(n\)
\begin{equation}\label{eq:Ln} L_n(x) = a_0 + a_1 x + \dots + a_n x^n, \end{equation}který prochází všemi těmito body, tj. \(L_n(x_i) = f(x_i)\).
Pro koeficienty \(a_i\) lze sestavit soustavu \(n+1\) rovnic
\begin{equation}\label{eq:vandermonde} V a = \underbrace{\begin{pmatrix} 1 & x_0 & x_0^2 & \dots & x_0^n \\ 1 & x_1 & x_1^2 & \dots & x_1^n \\ \vdots & & & & \vdots \\ 1 & x_n & x_n^2 & \dots & x_n^n \end{pmatrix}}_{\text{tzv. Vandermondeova matice,}} \begin{pmatrix} a_0 \\ a_1 \\ \vdots \\ a_n \end{pmatrix} = \begin{pmatrix} f_0 \\ f_1 \\ \vdots \\ f_n \end{pmatrix} , \quad \text{kde } f_i = f(x_i), \end{equation}pro niž platí
\[ \det V = \prod_{i>j} (x_i - x_j) \neq 0 \quad \text{pro } x_i \neq x_j \text{ pro } \forall i,j , \]a tedy soustava má jediné řešení.
□Determinant \(\det V\) je totiž polynomem v \(x_i\) a má nuly tam, kde je determinant nulový, tj. právě když pro jisté \(i\) a \(j\) platí \(x_i = x_j\); takových možností je \(n(n+1)/2\).
Polynom \(L_n(x)\) se obvykle nazývá Lagrangeův interpolační polynom a obvykle se uvádí ve tvaru
\begin{equation}\label{eq:lagrange-tvar} L_n(x) = \sum_{i=0}^{n} f_i \ell_i(x) , \quad \text{kde } \ell_i(x) = \frac{\prod\limits_{j=0, j \neq i}^{n} (x - x_j)}{\prod\limits_{j=0, j \neq i}^{n} (x_i - x_j)} , \quad \text{pro něž } \ell_i(x_j) = \delta_{ij} . \end{equation}Aitkenovo–Nevillovo schéma
Chceme-li spočítat \(L_n(x)\) v jednom nebo v malém počtu bodů, není nutné počítat koeficienty \(L_n(x)\). Lze místo toho použít Aitkenovo–Nevillovo schéma, které počítá \(L_n(\tilde x)\) pro konkrétní \(\tilde x\) přímo z hodnot \(x_i\) a \(f_i\) pomocí tabulky
\[ \begin{array}{cc|cccccccc} & & & & \xrightarrow{\qquad k \qquad} & & & & \\ & \text{stupeň} & 0 & & 1 & & 2 & & 3 \\ \hline & x_0 & f_0 = P_0^{(0)} & \searrow & & & & & \\ & x_1 & f_1 = P_0^{(1)} & \substack{\to \\ \searrow} & P_1^{(01)} & \searrow & & & \\ i \downarrow & x_2 & f_2 = P_0^{(2)} & \substack{\to \\ \searrow} & P_1^{(12)} & \substack{\to \\ \searrow} & P_2^{(012)} & \searrow & \\ & x_3 & f_3 = P_0^{(3)} & \to & P_1^{(23)} & \to & P_2^{(123)} & \to & P_3^{(0123)} \\ & \vdots & \vdots & & \vdots & & \vdots & & \vdots & \ddots \end{array} \]Na \(i\)-tém řádku a v \(k\)-tém sloupci je hodnota
\begin{equation}\label{eq:neville-hodnota} P_k^{(i-k,\dots,i)} = L_k^{(i-k,\dots,i)}(\tilde x) \end{equation}Lagrangeova interpolačního polynomu v \(x = \tilde x\) \(k\)-tého stupně daného body \((x_{i-k}, f_{i-k}), \dots, (x_i, f_i)\). Přitom používáme rekurentní vztah
\begin{equation}\label{eq:neville} L_{k+1}^{(i-(k+1),\dots,i-1,i)}(x) = \frac{(x - x_i) L_k^{(i-(k+1),\dots,i-1)}(x) + (x_{i-(k+1)} - x) L_k^{(i-k,\dots,i)}(x)}{x_{i-(k+1)} - x_i} \end{equation}pro \(k = 0, 1, \dots, n\) a \(i = 0, 1, 2, \dots\), \(i \geq k\).
Jde o vážený průměr dvou sousedních polynomů, který zajišťuje, že \(L_{k+1}\) prochází body \(x_{i-(k+1)}, \dots, x_i\). Například pro \(P_3^{(0123)}\) se váhy kombinují takto:
\[ \begin{array}{ccccc} P_2^{(012)} & \searrow & \dfrac{(x - x_3)}{(x_0 - x_3)} & & \\ & & & P_3^{(0123)} & \\ P_2^{(123)} & \nearrow & \dfrac{(x_0 - x)}{(x_0 - x_3)} & & \end{array} \]Interpolační polynomy vznikající v Aitkenově–Nevillově schématu pro uzly \(x_0, x_1, x_2, x_3\) — téměř vodorovná přímka \(L_0^{(0)}\), přímky \(L_1^{(01)}\) a \(L_1^{(12)}\), čárkované paraboly \(L_2^{(012)}\) a \(L_2^{(123)}\) a tlustě vytažená kubika \(L_3^{(0123)}\). Uzly jsou tažitelné a všechny polynomy se počítají z jejich aktuálních poloh; posuvník volí bod \(\tilde x\), pro který se pod plátnem vyčísluje celá Nevillova tabulka rekurencí \eqref{eq:neville} — poslední hodnota \(P_3\) je \(L_3^{(0123)}(\tilde x)\). Vyzkoušejte, jak se schéma chová, když dva uzly přiblížíte k sobě, nebo když \(\tilde x\) vysunete mimo interval \(\langle x_0, x_3 \rangle\) (extrapolace).
Chyba polynomiální interpolace a Čebyševovy uzly
Nechť \(x_0, \dots, x_n\) jsou různé body z \(\langle a,b \rangle\) a \(f \in C^{n+1}(\langle a,b \rangle)\). Pak pro každé \(x \in \langle a,b \rangle\) existuje \(\xi \in \langle a,b \rangle\) takové, že
\begin{equation}\label{eq:chyba-interpolace} f(x) - L_n(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!}\,\omega_{n+1}(x) , \end{equation}kde \(\omega_{n+1}(x) = \prod_{j=0}^{n} (x - x_j)\).
Viz Segethová.
Využívá se Rolleova věta pro funkci \(\tilde{\varphi}(x) = f(x) - L_n(x) - \tilde{k}\,\omega_{n+1}(x)\), kde
\[ \tilde{K} = \frac{f(\tilde{x}) - L_n(\tilde{x})}{\omega_{n+1}(\tilde{x})} \quad \text{pro } \tilde{x} \neq x_i . \] □Chyba tedy prostřednictvím \(\omega_{n+1}(x)\) závisí na rozložení bodů! Pro ekvidistantní rozložení \(x_i\) může nabývat mnohem větších hodnot než pro jiná rozložení, zvláště než pro optimální rozložení
\begin{equation}\label{eq:cebysev-uzly} x_i^{\text{čeb}} = \cos \frac{\pi}{2}\,\frac{2i+1}{n+1} \qquad \text{na int. } \langle -1,1 \rangle , \end{equation}což jsou kořeny Čebyševova polynomu \(T_{n+1}\), neboli po přeškálování na interval \(\langle a,b \rangle\) pro
\begin{equation}\label{eq:cebysev-uzly-ab} x_i^{\text{opt}} = \frac{a+b}{2} + \frac{(b-a)}{2} \cos \frac{\pi\,(2i+1)}{2\,(n+1)} , \end{equation}kdy
\[ \omega_{n+1}(x) = \left(\frac{b-a}{2}\right)^{n+1} t_{n+1}\left(\left(x - \frac{a+b}{2}\right)\frac{2}{b-a}\right) , \]kde \(t_{n+1}\) je Čebyševův polynom s koeficientem \(1\) u \(x^{n+1}\), a maximum je
\begin{equation}\label{eq:omega-max} \max_{x \in \langle a,b \rangle} |\omega_{n+1}(x)| = \frac{(b-a)^{n+1}}{2^{2n+1}} . \end{equation}Proč zrovna kořeny Čebyševova polynomu?
Čebyševův polynom \(t_n(x) = \dfrac{1}{2^{n-1}} T_n(x)\) s koeficientem \(1\) u \(x^n\) má totiž tu význačnou vlastnost, že minimalizuje \(\infty\)-normu na \(\langle -1,1 \rangle\) mezi polynomy \(p_n\) stupně \(n\), které mají u \(x^n\) koeficient \(1\).
Pro každý polynom \(p_n\) stupně \(n\) s koeficientem \(1\) u \(x^n\) platí
\begin{equation}\label{eq:cebysev-minimalita} \max_{x \in \langle -1,1 \rangle} |p_n(x)| \geq \max_{x \in \langle -1,1 \rangle} |t_n(x)| = \frac{1}{2^{n-1}} . \end{equation}Z vyjádření \(t_n(x) = \dfrac{1}{2^{n-1}} \cos(n \arccos x)\) (viz poznámky o ortogonálních polynomech) plyne
\[ |t_n(x)| \leq \frac{1}{2^{n-1}} \quad \text{pro } x \in \langle -1,1 \rangle . \]Přitom body, kde platí rovnost, jsou ty, pro které bude \(n \arccos x_k = k\pi\), \(k = 0, \dots, n\), neboli
\[ x_k = \cos \frac{k\pi}{n} , \qquad \text{a tedy} \qquad t_n(x_k) = \frac{(-1)^k}{2^{n-1}} . \]Nechť nyní existuje \(q_n(x)\) mezi všemi \(p_n(x)\) takový, že
\[ \max_{x \in \langle -1,1 \rangle} |q_n(x)| < \frac{1}{2^{n-1}} . \]Pak \(r(x) = t_n(x) - q_n(x)\) má stupeň menší než \(n\) a je nenulový, neboť v bodech \(x_k\) je nenulový a navíc má v \(x_k\) stejné znaménko jako \(t_n\), a tedy by měl mít \(n\) kořenů, což je spor s předpokladem, že má stupeň \(< n\).
□Hermiteova interpolace
Kromě funkčních hodnot zadáváme i derivace do řádu \(\alpha_i - 1\) v bodě \(x_i\). Dostaneme tak polynom \(H_m(x)\) \(m\)-tého stupně, přičemž \(m = \sum\limits_{i=0}^{n} \alpha_i - 1\). Koeficienty \(H_m(x)\) by šlo opět určit řešením soustavy \(m+1\) rovnic pro \(m+1\) neznámých.
Pro \(f \in C^{m+1}(\langle a,b \rangle)\) je chyba dána vztahem
\begin{equation}\label{eq:chyba-hermite} f(x) - H_m(x) = \frac{f^{(m+1)}(\xi)}{(m+1)!} \, \omega_{m+1}(x) \quad \text{pro jisté } \xi \in \langle a,b \rangle , \end{equation}kde nyní
\[ \omega_{m+1}(x) = (x-x_0)^{\alpha_0} (x-x_1)^{\alpha_1} \dots (x-x_n)^{\alpha_n} . \]Pro \(\alpha_0 = \alpha_1 = \dots = \alpha_n = 1\) by šlo o standardní Lagrangeovu interpolaci; pro \(n = 0\) a \(\alpha_0 = m+1\) dostaneme Taylorův rozvoj v okolí \(x_0\) do řádu \(m\).
Speciálně pro \(\alpha_0 = \dots = \alpha_n = 2\), kdy zadáváme funkční hodnoty a první derivace, lze psát
\begin{equation}\label{eq:hermite-2np1} H_{2n+1}(x) = \sum_{i=0}^{n} s_i(x) f_i + \sum_{i=0}^{n} t_i(x) f_i' , \end{equation}kde
\begin{align*} s_i(x) &= \left[ 1 - 2(x-x_i) \ell_i'(x_i) \right] \ell_i^2(x) & &\Rightarrow & s_i(x_j) &= \delta_{ij}, & s_i'(x_j) &= 0, \\ t_i(x) &= (x-x_i) \ell_i^2(x) & &\Rightarrow & t_i(x_j) &= 0, & t_i'(x_j) &= \delta_{ij}. \end{align*}Interpolace pomocí splajnů
Namísto jediného interpolačního polynomu procházejícího body \((x_i, f_i)_{i=0,\dots,n}\), který může značně oscilovat (Rungeův jev), budeme hledat po částech polynomy nižších řádů na každém podintervalu \(\langle x_{i-1}, x_i \rangle\), \(i = 1, \dots, n\). Přitom budeme chtít, aby byla výsledná funkce (splajn) spojitá i s derivacemi do jistého řádu.
Název splajn pochází z anglického spline, které označuje dřevěný pás používaný k prokládání křivek mezi body při konstrukcích lodí.
Obyčejný splajn řádu \(k\) pro uzly \(x_0 < x_1 < \dots < x_n\) je funkce, která je na \(\forall \langle x_{i-1}, x_i \rangle\), \(i = 1, \dots, n\), polynomem stupně nejvýše \(k\) a která má na celém intervalu \(\langle x_0, x_n \rangle\) spojité derivace do řádu \(k-1\).
Splajny se používají nejen k interpolaci, ale také např. ke konstrukci bází s kompaktním nosičem (B-splajny) pro řešení PDR apod.
V praxi se využívají především kubické splajny pro své dobré „vyhlazovací“ vlastnosti,
\[ \int_{x_0}^{x_n} |S''(x)|^2 \mathrm{d}x \le \int_{x_0}^{x_n} |\psi''(x)|^2 \mathrm{d}x \quad \text{pro } \forall \psi \in C^{(n)}_{\langle x_0, x_n \rangle} \text{ pro něž } \underset{i=0,\dots,n}{\psi(x_i) = S(x_i)} , \]a zároveň pro relativně jednoduchou konstrukci.
Výhodou oproti Lagrangeovým interpolačním polynomům je, že pro \(f \in C^4_{\langle x_0, x_n \rangle}\) splajny stejnoměrně konvergují k interpolované funkci \(f\), pokud zmenšujeme \(\max\limits_{i=1,\dots,n} |x_{i-1} - x_i|\). Pro ekvidistantní uzly lze ukázat, že existuje konstanta \(C\) nezávislá na \(x\) taková, že
\begin{equation}\label{eq:splajn-konvergence} |f(x) - S(x)| \le C h^4 \quad \text{pro } \forall x \in \langle x_0, x_n \rangle . \end{equation}Interpolační kubický splajn
Interpolační kubický splajn je splajn 3. řádu procházející interpolovanými body \((x_i, f_i)\), \(i = 0, \dots, n\).
Interpolační kubický splajn není určen jednoznačně: máme \(4n-2\) podmínek
\begin{equation}\label{eq:podminky} \begin{aligned} S_i(x_{i-1}) &= f_{i-1} , \\ S_i(x_i) &= f_i , \\ S_i'(x_i) &= S_{i+1}'(x_i) , \\ S_i''(x_i) &= S_{i+1}''(x_i) , \end{aligned} \end{equation}přičemž poslední dvě podmínky se berou bez krajních bodů \(x_0\) a \(x_n\), ale \(4n\) neznámých koeficientů polynomů stupně 3 na každém \(\langle x_{i-1}, x_i \rangle\). Jsou tedy nutné dodatečné 2 podmínky.
Přirozený (natural) interpolační kubický splajn je dán podmínkami
\begin{equation}\label{eq:prirozeny} S''(x_0) = S''(x_n) = 0 . \end{equation}Obyčejný (clamped, upnutý, tj. na okrajích nasměrujeme) interpolační kubický splajn je dán podmínkami
\begin{equation}\label{eq:clamped} S'(x_0) = f'(x_0) , \quad S'(x_n) = f'(x_n) . \end{equation}Splajn s těmito okrajovými podmínkami přechází na koncích do rovné čáry.
Používají se i další varianty, např. periodický splajn:
\[ \begin{aligned} S'(x_0) &= S'(x_n) \\ S''(x_0) &= S''(x_n) \end{aligned} \qquad + \quad \begin{aligned} &\text{musí být} \\ &S(x_0) = S(x_n) . \end{aligned} \]Přirozený kubický splajn procházející body \((x_i, f_i)\)
Bylo by možné z podmínek \eqref{eq:podminky} sestavit \(4n\) rovnic, ovšem efektivnější je jít na to nepřímo:
- určíme druhé derivace \(z_i = S''(x_i)\) z tridiagonální soustavy lineárních rovnic;
- určíme \(S(x)\) ze známých \(x_i\), \(f_i\) a \(z_i\), \(i = 0, \dots, n\).
Rovnice pro druhé derivace \(z_i\)
Pokud by byly druhé derivace \(z_i\) známé, pak \(S_i''(x)\) je lineární funkce
\begin{equation}\label{eq:Sdruha} S_i''(x) = \frac{z_i}{h_i}(x - x_{i-1}) + \frac{z_{i-1}}{h_i}(x_i - x) , \qquad \text{kde } h_i = x_i - x_{i-1}, \quad i = 1, \dots, n . \end{equation}Dvojí integrací dostaneme (s vhodně zvolenými integračními konstantami)
\begin{equation}\label{eq:Si} S_i(x) = \frac{z_i}{6h_i}(x - x_{i-1})^3 + \frac{z_{i-1}}{6h_i}(x_i - x)^3 + C_i(x - x_{i-1}) + D_i(x_i - x) , \end{equation}kde integrační konstanty \(C_i\) a \(D_i\) se určí z podmínek \(S_i(x_{i-1}) = f_{i-1}\) a \(S_i(x_i) = f_i\), takže
\[ C_i = \frac{f_i}{h_i} - \frac{z_i h_i}{6} , \qquad D_i = \frac{f_{i-1}}{h_i} - \frac{z_{i-1} h_i}{6} . \]Známe-li tedy \(z_i\), můžeme určit \(S(x)\) z rovnice \eqref{eq:Si} pro \(x \in \langle x_{i-1}, x_i \rangle\), i když je vhodnější vyčíslit ji jako
\begin{equation}\label{eq:Si-horner} S_i(x) = a_i + b_i(x - x_{i-1}) + c_i(x - x_{i-1})^2 + d_i(x - x_{i-1})^3 , \end{equation}kde
\begin{align*} a_i &= f_{i-1} , \\ b_i &= -\frac{h_i}{3}\left(z_{i-1} + \frac{z_i}{2}\right) + \frac{f_i - f_{i-1}}{h_i} , \\ c_i &= z_{i-1}/2 , \\ d_i &= \frac{z_i - z_{i-1}}{6h_i} . \end{align*}Takto zkonstruované \(S_i(x)\) zatím splňuje \(S_i(x_{i-1}) = f_{i-1}\), \(S_i(x_i) = f_i\), \(i = 0, \dots, n\), a
\[ S_i''(x_i) = S_{i+1}''(x_i) , \qquad i = 1, \dots, n-1 . \]Nyní použijeme podmínku \(S_i'(x_i) = S_{i+1}'(x_i)\), \(i = 1, \dots, n-1\), k určení \(z_i\). Dostaneme
\[ S_i'(x) = \frac{z_i}{2h_i}(x - x_{i-1})^2 - \frac{z_{i-1}}{2h_i}(x_i - x)^2 + C_i - D_i \]a tedy
\begin{equation}\label{eq:tridiag-rovnice} z_{j-1} h_j + 2 z_j (h_i + h_{i+1}) + z_{j+1} h_{i+1} = 6(b_{i+1} - b_j) , \end{equation}kde
\begin{equation}\label{eq:bi} b_i = \frac{f_i - f_{i-1}}{h_i} \qquad \text{pro} \qquad i = 1, \dots, n-1 . \end{equation}Navíc položíme \(z_0 = 0\) a \(z_n = 0\), čímž dostaneme tridiagonální (a navíc symetrický) systém
\begin{equation}\label{eq:tridiag-system} \begin{pmatrix} U_1 & h_2 & & & & 0 \\ h_2 & U_2 & h_3 & & & \\ & h_3 & \ddots & & & \\ & & & \ddots & & \\ 0 & & & h_{n-2} & U_{n-2} & h_{n-1} \\ & & & & h-1 & U_{n-1} \end{pmatrix} \begin{pmatrix} z_1 \\ z_2 \\ \vdots \\ \vdots \\ z_{n-1} \end{pmatrix} = \begin{pmatrix} V_1 \\ V_2 \\ \vdots \\ \vdots \\ v_{n-1} \end{pmatrix} , \end{equation}kde
\begin{align*} U_i &= 2(h_i + h_{i+1}) , \\ v_i &= 6(b_{j+1} - b_i) . \end{align*}Systém lze řešit přímou Gaussovou eliminací na \(\mathcal{O}(n)\) operací: hodnotu \(U_i\) „nahradíme“ hodnotou
\begin{align*} U_i &\ \longleftarrow\ U_i - \frac{h_i^2}{U_{i-1}} , \\ V_i &\ \longleftarrow\ V_i - \frac{h_i V_{i-1}}{U_{i-1}} , \end{align*}a to pro \(i = 2, \dots, n-1\), a zpětnou substitucí dostaneme
\begin{align*} z_{n-1} &= \frac{V_{n-1}}{U_{n-1}} , \\ z_i &= \frac{V_i - h_{i+1} z_{i+1}}{U_i} , \qquad i = n-2, n-3, \dots, 1 . \end{align*}Vše je v pořádku, neboť \(U_i > h_{i+1} > 0\). Platí totiž \(U_1 > h_2 > 0\) a indukcí
\[ U_i = 2(h_{i+1} + h_i) - \frac{h_i^2}{U_{i-1}} > 2(h_{i+1} + h_i) - h_i > h_{i+1} > 0 . \]