Past exam of the numerical solution of differential equations course of the University of Oxford / 2011 / B

For the second-order boundary value problem, introduce an unknown initial slope $s$ and solve the initial value problem $u^{\prime }=v$, $v^{\prime }=g(x,u,v)$ with $u(a)=\alpha$, $v(a)=s$. Its endpoint mismatch is $F(s)=u(b;s)-\beta$. The shooting method seeks a root $F(s)=0$; in general the dependence of the flow on $s$ is nonlinear. A sign-changing bracket for a continuous $F$ allows the bisection method, provided the intervening initial value solutions exist up to $b$.

For Newton's method, solve the parameter sensitivity equation alongside the trajectory. With $z={\partial }_{s}u$ and $w={\partial }_{s}v$,Then $F^{\prime }(s)=z(b)$ and the update is $\boxed{s_{\mathrm{new}}=s-F(s)/z(b)}$ whenever $z(b)\ne 0$.

For the third-order problem, shooting from $a$ leaves both $u^{\prime }(a)$ and $u^{\prime \prime }(a)$ unknown, requiring two shooting parameters to satisfy two right-endpoint conditions. Shooting backwards from $b$ already knows $u(b)=\beta$ and $u^{\prime }(b)=\gamma$; only $u^{\prime \prime }(b)$ is unknown, with the single residual $u(a)-\alpha$. Backward shooting reduces the nonlinear solve from two scalar unknowns to one. This parameter-count advantage does not by itself guarantee numerical stability of backward integration.

The four-point midpoint third derivative uses the four values at $x_{j-1},x_j,x_{j+1},x_{j+2}$, centred at $x_{j+1/2}$. The Taylor theorem about that midpoint givesThus, for $n\ge 2$, take the $n-1$ interior equationsImpose the two value conditions exactly, $U_0=\alpha$, $U_{n+1}=\beta$, and approximate the remaining condition with the second-order backward finite difference:This gives $n$ equations for $U_1,\dots ,U_n$. The endpoint derivative formula equals $u^{\prime }(b)-h^2{u}^{\prime \prime \prime }(b)/3+O(h^3)$, so its residual tends to zero along with those of the four-point equations. Every stencil lies within $[a,b]$; no unprescribed ghost value is introduced. The construction is therefore a consistent finite difference method for all three boundary conditions.

The five-point equations for the Poisson equation arewith prescribed boundary values. If $L_h\varphi \le 0$, an interior maximal value is at most the average of its four neighbours. Since no neighbour exceeds the maximum, equality forces all four to equal it. Repeating along adjacent nodes propagates that value to the boundary. Thus the discrete maximum principle gives $\max \varphi \le {\max }_{\partial {\Omega }_h}\varphi$, in particular the usual positive-maximum bound with zero included.

For an $O(h^2)$ error estimate assume the exact solution has bounded continuous fourth partial derivatives up to the boundary. The local truncation error $\tau =L_{h}u-f$ then satisfies $\Vert \tau {\Vert }_{\infty }\le C{h}^2$ by the Taylor theorem. Put $e=u{|}_{{\Omega }_h}-U$, so $L_{h}e=\tau$ and $e=0$ on boundary nodes. The Discrete Poisson barrier on a squaresatisfies $L_{h}B=1$ exactly, $B\ge 0$ on the grid boundary, and $B\le 1/8$. Set $\epsilon =\Vert \tau {\Vert }_{\infty }$. Then $L_h(\pm e-\epsilon B)\le 0$, with nonpositive boundary values. Applying the discrete maximum principle twice givesFor nonzero smooth Dirichlet boundary data $g$, impose $U=g$ at the boundary nodes. The error still vanishes there, so the same argument and order apply, under the same fourth-derivative regularity of the exact solution. Smooth boundary values alone do not remove every possible corner-regularity issue.

Replace $L_h$ by $\boxed{{\tilde{L}}_h=L_h+I}$. At a positive interior maximum $v>0$, the neighbour average is no larger than $v$, so $({\tilde{L}}_h\varphi {)}_{jk}\ge v>0$. Thus ${\tilde{L}}_h\varphi \le 0$ cannot have such an interior maximum. The positive-maximum form of the discrete maximum principle therefore remains valid:With $e=u{|}_{{\Omega }_h}-U$ the error equation is ${\tilde{L}}_{h}e=\tau$, where $\tau =O(h^2)$ under the preceding regularity assumptions. Since ${\tilde{L}}_{h}B=1+B\ge 1$ for the same Discrete Poisson barrier on a square, the comparison functions $\pm e-\Vert \tau {\Vert }_{\infty }B$ proveThere is no loss of uniqueness: apply the positive-maximum argument to both signs of a homogeneous discrete solution. The continuous weak formulation also has the coercive bilinear form ${\int }_{\Omega }(|\nabla v{|}^2+v^2)$, so the added positive reaction term strengthens its positive energy.

Let $x_{\ast }=A^{-1}b$, $e_k=x_k-x_{\ast }$ and $G=M^{-1}N$. Subtract the exact fixed-point equation to obtain $e_k=G^k{e}_0$. Hence convergence for every initial vector is equivalent to $G^k\to 0$. If this holds, it holds after complexification; applying it to a complex eigenvector gives ${\lambda }^{k}v\to 0$, so $|\lambda |<1$. Conversely, the complex Jordan normal form expresses each power as a finite sum of terms $\left(\genfrac{}{}{0ex}{}{k}{r}\right){\lambda }^{k-r}$ from its blocks. Every term tends to zero when all eigenvalues have modulus below one. ThusThe convergence criterion for a stationary iteration needs complex triangularization or Jordan normal form. The paper's assertion that every real matrix is similar to a real upper-triangular matrix is false when nonreal eigenvalues occur; complex triangularization supplies the intended argument. In the Gauss-Seidel method, with $A=D+L+U$ split into diagonal, strictly lower and strictly upper parts, $\boxed{M=D+L,N=-U}$.

For $n\ge 4$, eliminating the ghost values gives the symmetric pentadiagonal matrixAll other off-diagonal entries vanish. The first two equations areand the last two areFor $n=3$ the matrix is $\left(\begin{array}{ccc}7& -4& 1\\ -4& 6& -4\\ 1& -4& 7\end{array}\right)$, for $n=2$ it is $\left(\begin{array}{cc}7& -4\\ -4& 7\end{array}\right)$, and for $n=1$ it is $(8)$ because both ghost contributions meet the same unknown. The diagonal entries are positive in every case, so the lower triangular matrix $D+L$ is invertible and the Gauss-Seidel iteration is well defined.

An eigenvalue $\lambda$ of $G=-(D+L{)}^{-1}U$ makes $H(\lambda )=\lambda (D+L)+U$ singular. Let ${\ell }_i$ and $r_i$ be the sums of absolute lower and upper entries in row $i$. The row's diagonal-dominance margin isInterior full rows have $d_i=6$, ${\ell }_i=r_i=5$, giving margin $|\lambda |-5$. Boundary rows have larger margins; for instance the first gives $7|\lambda |-5$, and the second gives at least $2|\lambda |-5$. Therefore $|\lambda |>5$ would make $H(\lambda )$ a strictly diagonally dominant matrix, hence nonsingular, a contradiction.

At $|\lambda |=5$ it is weakly diagonally dominant with strict boundary rows. Its nonzero nearest-neighbour entries make it an irreducibly diagonally dominant matrix. The nonsingularity theorem for that class again contradicts singularity. For the small matrices above all rows are already strict at this value. HenceThere is also a stronger conclusion. For $T=\mathrm{tridiag}(-1,2,-1)$,including the $n=1$ overlap. Since $T$ is positive definite, $A$ is a symmetric positive-definite matrix. The Gauss-Seidel convergence from diagonal dominance and positive definiteness theorem consequently gives the stronger bound $\rho (G)<1$.