Linear numerical boundary-value problems

Let $p_1=2$ and $p_j=2-1\mathrm{/}{p}_{j-1}$ for $2\le j\le N$, as in [F1]. Induction gives $p_j=(j+1)\mathrm{/}j$: it holds at $j=1$, and if $p_{j-1}=j\mathrm{/}(j-1)$ then $p_j=2-(j-1)\mathrm{/}j=(j+1)\mathrm{/}j>0$. Thus every Thomas pivot is nonzero.

Define $q_j=x_j(1-x_j)\mathrm{/}2$ and $q_0=q_{N+1}=0$. Direct expansion of this quadratic gives $q_{j-1}-2q_j+q_{j+1}=-h^2$, so $A_{h}q=\mathbf{1}$. Also $0\le q_j\le 1\mathrm{/}8$, since $x(1-x)=1\mathrm{/}4-(x-1\mathrm{/}2{)}^2$ on $0\le x\le 1$.

For the equation $A_{h}w=r$, put $b_j=h^2{r}_j$ and $s_1=b_1$. The first row is $p_1{w}_1-w_2=s_1$. If elimination has produced $p_{j-1}{w}_{j-1}-w_j=s_{j-1}$, then $w_{j-1}=(s_{j-1}+w_j)\mathrm{/}{p}_{j-1}$; substituting this into $-w_{j-1}+2w_j-w_{j+1}=b_j$ gives $p_j{w}_j-w_{j+1}=b_j+s_{j-1}\mathrm{/}{p}_{j-1}=s_j$, exactly the recurrence in [F1].

Since $w_{N+1}=0$, backward substitution gives $w_N=s_N\mathrm{/}{p}_N$ and then $w_j=(s_j+w_{j+1})\mathrm{/}{p}_j$ for $j=N-1,\dots ,1$. Each pivot is positive by step 1.1, so each value is uniquely determined; substitution into the transformed rows proves it solves the original rows. Hence for every $r$ there is exactly one $w$ with $A_{h}w=r$, and $A_h^{-1}$ exists.

Suppose $r_j\ge 0$ and let $w=A_h^{-1}r$. If the finite list $w_0,\dots ,w_{N+1}$ had a negative minimum $m$ at an interior index $j$, then $w_{j-1},w_{j+1}\ge m$ and $h^2{r}_j=2m-w_{j-1}-w_{j+1}\le 0$. Since $r_j\ge 0$ and $h>0$, equality must hold, forcing both neighbors to equal $m$. Repeating this equality to the left reaches $w_0=m<0$, contradicting $w_0=0$. Thus $w_j\ge 0$ at every interior index.

Put $R=\mathrm{\parallel }r{\mathrm{\parallel }}_{\mathrm{\infty }}$. The coordinate bounds $-R\mathbf{1}\le r\le R\mathbf{1}$ and step 4.1 show that $A_h^{-1}(R\mathbf{1}-r)=Rq-A_h^{-1}r\ge 0$ and $A_h^{-1}(R\mathbf{1}+r)=Rq+A_h^{-1}r\ge 0$. Hence $-Rq\le A_h^{-1}r\le Rq$ coordinatewise.

Step 5.1 and $q_j\le 1\mathrm{/}8$ from step 1.2 give $\mathrm{\mid }(A_h^{-1}r{)}_j\mathrm{\mid }\le R\mathrm{/}8$ for every $j$, so $\mathrm{\parallel }{A}_h^{-1}r{\mathrm{\parallel }}_{\mathrm{\infty }}\le \mathrm{\parallel }r{\mathrm{\parallel }}_{\mathrm{\infty }}\mathrm{/}8$ for every mesh.

The endpoint values of the exact function agree with the algorithm's prescribed endpoint values, so both boundary closure residuals are $0$. Fix an interior index $j$. Applying [F2] with center $x_j$ and targets $x_j-h$ and $x_j+h$ gives $u(x_j\pm h)=u_j\pm h{u}^{\mathrm{\prime }}(x_j)+\frac{h^2}{2}{u}^{\mathrm{\prime }\mathrm{\prime }}(x_j)\pm \frac{h^3}{6}{u}^{\mathrm{\prime }\mathrm{\prime }\mathrm{\prime }}(x_j)+R_{\pm }$, with $\mathrm{\mid }{R}_{\pm }\mathrm{\mid }\le M{h}^4\mathrm{/}24$. Both closed intervals lie in $[0,1]$, including when $j=1$ or $j=N$.

Substituting these expansions into [F1] cancels the odd derivative terms and gives $(A_h{u}_{\mathrm{g}\mathrm{r}\mathrm{i}\mathrm{d}}{)}_j=-u^{\mathrm{\prime }\mathrm{\prime }}(x_j)-(R_{-}+R_{+})\mathrm{/}{h}^2$. Since $g=-u^{\mathrm{\prime }\mathrm{\prime }}$, it follows that ${\tau }_j=-(R_{-}+R_{+})\mathrm{/}{h}^2$.

By [F3] and step 1.1, $\mathrm{\mid }{\tau }_j\mathrm{\mid }\le (\mathrm{\mid }{R}_{-}\mathrm{\mid }+\mathrm{\mid }{R}_{+}\mathrm{\mid })\mathrm{/}{h}^2\le (M{h}^4\mathrm{/}24+M{h}^4\mathrm{/}24)\mathrm{/}{h}^2=M{h}^2\mathrm{/}12$. This holds for every interior index, and the endpoint residuals from step 1.1 are zero, proving both bounds.

Let ${\tau }_h=A_h{u}_{\mathrm{g}\mathrm{r}\mathrm{i}\mathrm{d}}-g_h$. By [F3], $\mathrm{\parallel }{\tau }_h{\mathrm{\parallel }}_{\mathrm{\infty }}\le M{h}^2\mathrm{/}12$ and the exact endpoint values agree with the imposed endpoint closure, so the endpoint error is zero.

For $e_h:=v_h-u_{\mathrm{g}\mathrm{r}\mathrm{i}\mathrm{d}}$, subtracting the definitions of ${\rho }_h$ and ${\tau }_h$ gives $A_h{e}_h={\rho }_h-{\tau }_h$. Since $A_h$ is invertible by [F2], $e_h=A_h^{-1}({\rho }_h-{\tau }_h)$.

By [F2], each coordinate satisfies $\mathrm{\mid }(e_h{)}_j\mathrm{\mid }\le \mathrm{\parallel }{\rho }_h-{\tau }_h{\mathrm{\parallel }}_{\mathrm{\infty }}\mathrm{/}8$. The coordinatewise triangle inequality [F4] gives $\mathrm{\parallel }{\rho }_h-{\tau }_h{\mathrm{\parallel }}_{\mathrm{\infty }}\le \mathrm{\parallel }{\rho }_h{\mathrm{\parallel }}_{\mathrm{\infty }}+\mathrm{\parallel }{\tau }_h{\mathrm{\parallel }}_{\mathrm{\infty }}$, because for each $j$, $\mathrm{\mid }{\rho }_j-{\tau }_j\mathrm{\mid }\le \mathrm{\parallel }{\rho }_h{\mathrm{\parallel }}_{\mathrm{\infty }}+\mathrm{\parallel }{\tau }_h{\mathrm{\parallel }}_{\mathrm{\infty }}$.

Substituting the residual bound from [F3] into step 3.1 yields $\mathrm{\parallel }{e}_h{\mathrm{\parallel }}_{\mathrm{\infty }}\le \mathrm{\parallel }{\rho }_h{\mathrm{\parallel }}_{\mathrm{\infty }}\mathrm{/}8+M{h}^2\mathrm{/}(8\cdot 12)=\mathrm{\parallel }{\rho }_h{\mathrm{\parallel }}_{\mathrm{\infty }}\mathrm{/}8+M{h}^2\mathrm{/}96$. For the exact algorithm output, [F2] guarantees that the recurrence returns the unique solution and the exact equation check succeeds, so ${\rho }_h=0$; exact endpoint closure was recorded in step 1.1.