A 6-point subdivision scheme and its applications for the solution of 2nd order nonlinear singularly perturbed boundary value problems

1.   Introduction

The Computer Aided Geometric Design (CAGD) is an attractive field of mathematics to deal with algorithms for the construction of smooth curves and surfaces. In this field, we present mathematical formulation of shapes which are used in computer graphics, manufacturing or analysis. It has applications in different field of mathematics such as numerical geometry, numerical analysis, theory of approximation, computer graphics, and computer algebra. CAGD gains importance due to its use in different industrial areas and engineering. One of the most important area in CAGD is "subdivision schemes". The subdivision schemes are very useful for the construction of smooth curve and surface. Here we give short review on 6-point BISS. The first 6-point BISS was introduced by ^[1] in 1989. Weissman ^[2] introduced this scheme in his Master thesis in 1990. Lee et al. ^[3] also introduced this scheme in 2006. Ko et al. ^[4] and Lian ^[5] introduced schemes in 2007 and 2008 respectively. Later on, 6-point BISS was introduced by ^[6,7].

The 6-point BISS take a polygon as an input and produce the refined polygon as an output. In order to get refined polygon, 6-point BISS use six points of coarse polygon to find one point corresponding to each edge of the polygon while carry on the points of coarse polygon. The 6-point BISS schemes introduced by above authors are different due to the different coefficients used in an affine combination of six points. All the above authors, have presented the applications of 6-point BISS in curve/surface modeling. But in this paper, we present its application for the curve modeling as well as for the solution of 2nd order NSPBVP. Especially, we find the solution of the following type of 2nd order NSPBVP:

with boundary conditions

where $0 < \epsilon \leq 1$. This type of 2nd order NSPBVP arises in the different area of engineering and other sciences. Particularly, these problems arises in the field of nuclear engineering, chemical reaction theory, physics and many other fields of sciences. Since the too small coefficient of 2nd order derivative causes the derivative approaches to zero. Therefore it is difficult to handle such type of problems. In literature, subdivision based algorithms were developed only for linear ^{[8,9,10,11,12]} and nonlinear ^[13,14,15] boundary value problems. The solution of linear singularly perturbed boundary value problems was presented by ^[16]. The solution of 2nd order NSPBVP of the type presented in (1.1) by subdivision scheme based iterative algorithm is not find yet. This motivate us to introduce the algorithm for the solution of this type of problems. The distribution of the rest of the paper is as follows:

In Section 2, we present a 6-point BISS and discuss some of its properties. In Section 3, we construct BISS based iterative algorithm for the approximate solution of NSPBVP. The convergence and error estimation of the algorithm are also presented in this section. In Section 4, the solutions of some of NSPBVP are presented. The Section 5 is reserved for the conclusion.

2.   Binary subdivision scheme

If $p^{0} = \left\{p^{0}_{i}, i\in \mathbb{Z}\right\}$ is the initial sketch (i.e., polygon) of some shape then to get the refined sketch $p^{k+1} = \left\{p^{k+1}_{i}, i\in \mathbb{Z}, k > 0\right\}$, we suggest the following 6-point BISS

where $w$ is a parameter. The points $p^{k}_{i}$ are related with the diadic mesh points $t^{k}_{i} = i/2^k$.

2.1.   Continuity of the scheme

In this section, by using the techniques of Dyn ^[17], we see that the scheme produces the curvature continuous curves.

Theorem 2.1. The 6-point BISS is $C^2$-continuous for the parametric interval $0 < w < 0.042$ i.e., scheme produces the limit curve with 2-degree of smoothness.

Proof. If we arrange the points involved in odd and even rules of (2.1) as

then the sequence of coefficients of these points in odd and even rules is

This sequence can be represented in terms of the following Laurent polynomial

Or equivalently

By multiplying it with the factor $\frac{2z}{1+z}$, we get

Again multiplying it with the same factor, we get

Further multiplying, we get

Let $S_{\alpha}$, $S_{\alpha_1}$, $S_{\alpha_2}$, $S_{\alpha_3}$, be the schemes corresponding to the Laurent polynomials $\alpha(z)$, $\alpha_{1}(z)$, $\alpha_{2}(z)$, $\alpha_{3}(z)$ respectively then

This implies

Since $\left\|\left(\frac{1}{2}S_{\alpha_1}\right)\right\|_{\infty} < 1$ for $w \in (\frac{-13}{48}, \frac{3}{48})$, therefore the scheme $S_{\alpha_1}$ is contractive and the scheme $S_{\alpha}$ is $C^0$-continuous. Since

therefore $\left\|\left(\frac{1}{2}S_{\alpha_2}\right)\right\|_{\infty} < 1$ for $w \in (\frac{-1}{16}, \frac{3}{16}), (\frac{-3}{32}, \frac{1}{32})$. Hence the scheme $S_{\alpha_2}$ is contractive and the scheme $S_{\alpha}$ is $C^1$-continuous. Again

so $\left\|\left(\frac{1}{2}S_{\alpha_3}\right)\right\|_{\infty} < 1$ for $w \in (0, \frac{1}{16})$. Thus the scheme $S_{\alpha_3}$ is contractive and the scheme $S_{\alpha}$ is $C^2$-continuous for the parametric interval $0 < w < 0.042$.

2.2.   Approximation order of the scheme

Here we compute the approximation order of the scheme. If $\alpha^{(1)}(z)$ denotes first derivative of $\alpha(z)$, $\tau = \frac{\alpha^{(1)}(1)}{2} = 0$ and $t^{k}_i = -\tau+\frac{i+\tau}{2^k} = \frac{i+0}{2^k} = \frac{i}{2^k}$ then by Conti and Hormann ^[18], the scheme (2.1) has primal parametrization. The scheme generates polynomial of degree 3 because

where

Lemma 1. The $6$-point BISS reproduces up to 3rd degree polynomials w.r.t. the primal parameterizations (i.e., for $\tau = 0$).

Proof. If $\alpha^{(i)}(z)$, $i = 0, 1, 2, 3$ denote the derivative of $\alpha(z)$ then following can be verified:

but

and

This implies that

Thus

This completes the proof.

Since by Lemma 1, scheme produces polynomial of degree 3 therefore by Dyn ^[17] it has approximation order 4.

2.3.   Eigenvalues and normalized eigenvectors

Here first we find the subdivision matrix then we compute its eigenvalues and left & right normalized eigenvectors corresponding to these eigenvalues. If we take

then by taking $i = -2, -1, 0$ and $1$ in even and odd rules and $i = 2$ in just even rule of (2.1), we get a system of equations.

where

$p^{j+1} = \left (p^{j+1}_{-4}, p^{j+1}_{-3}, p^{j+1}_{-2}, p^{j+1}_{-1}, p^{j+1}_{0}, p^{j+1}_{1}, p^{j+1}_{2}, p^{j+1}_{3}, p^{j+1}_{4} \right)^T$, and $p^{j} = \left (p^{j}_{-4}, p^{j}_{-3}, p^{j}_{-2}, \right.$ $\left. p^{j}_{-1}, p^{j}_{0}, p^{j}_{1}, p^{j}_{2}, p^{j}_{3}, p^{j}_{4} \right)^T$. Here $S$ is called the subdivision matrix of the scheme. Its eigenvalues are: $\lambda = 1, \frac{1}{2}, \frac{1}{4}, \beta_{3}, \beta_{4}, \beta_{5}, \beta_{6}, \beta_{7}, \beta_{8},$ where $\beta_{0} = 1, \beta_{1} = \frac{1}{2}, \beta_{2} = \frac{1}{4}$, while the other eigenvalues $\beta_{3}...\beta_{8}$ and their corresponding eigenvectors are not needed in rest of the paper, so we do not write their values. It has been noticed that the some of eigenvalues and eigenvectors of the subdivision matrix are complex. The right normalized eigenvectors $\xi_{\beta_{i}}$ and left normalized eigenvectors $\eta_{\beta_{i}}$, for $i = 1, 2$ corresponding to the eigenvalues $\beta_{1}$ and $\beta_{2}$ are

where

2.4.   Applications of the scheme for curve modeling

Here, we show the applications of the 6-point BISS by presenting different shapes. We also show that how the parameter controls the shape of limiting curves. Red sketches are the initial structures made by 2D data points while other sketches are produced by the scheme at different values of parameter. Here we use $w = 0.01, 0.02, 0.03$ and $0.04$.

3.   Applications of the scheme for approximate solutions of NSPBVP

Here we gather some necessary stuff to establish a subdivision based iterative algorithm to find the approximate solution of NSPBVP.

Lemma 2. ^[10,14] The fundamental solution define as

is twice continuously differentiable and cardinally supported on $\Delta = (-5, 5)$ and zero outside the $\Delta$.

Lemma 3. ^[9] The Cardinal basis $\theta(t)$ is twice continuously differentiable on $(-5, 5)$ and its first and second derivatives are obtained by using the left eigenvectors of (2.3) corresponding to the eigenvalues $\beta_{1} = \frac{1}{2}$ and $\beta_{2} = \frac{1}{4}$ respectively. The derivatives values are

where

and

Hence, the first and second derivatives of (3.1) are

To construct the iterative algorithm, we only need the right and left normalized eigenvectors corresponding to the eigenvalues $\beta_1$ and $\beta_2$. Since the parameter $w$ is involved in these eigenvectors. Therefore, for simplicity, we take the randem value of $w = \frac{1}{25}$ from the $C^2$- continuity of the parametric interval of the scheme. So the left and right normalized eigenvectors corresponding to the eigenvalues $\beta_1$ and $\beta_2$ are:

Similarly, from (3.2), we get

In coming section, we introduce 6-point BISS based iterative algorithm for the solution of 2nd order NSPBVP.

3.1.   Algorithm for the approximate solution of 2nd order NSPBVP

Let $N\geq4$, $h = \frac{1}{N}$, $\epsilon < h$ and $t_{i} = ih, i = 0, 1, 2, \cdots, N$. Let

with the property $G(t_i) = g_i$ be an approximate solution of (1.1). The unknowns ${\{g_i\}}$ will be determined. From (1.1) and (3.4), we get

where

The following $N+1$ system of equations can by obtained by substituting (3.4) and (3.6) in (3.5).

Theorem 3.1. The system of equations (3.7) reduces to

where $j = 0, 1, 2, \cdots, N$ and $\theta_{j}^{''} = \theta^{''}(j)$.

Proof. Let $j = 0$ then by (3.7)

For $t_{j} = j h, \qquad j = 0, 1, 2, \cdots, N,$ this implies

Since the support of $\theta(t)$ is $(-5, 5)$ therefore $\theta^{''}(t) = 0$ beyond the interval $(-5, 5)$, so by (3.1) and (3.2), we get

If $\theta^{''}(j) = \theta^{''}_{j}$, then

The expansion of (3.7) gives

For $t_{j} = j h, j = 1, 2, \cdots, N,$ we get

If $\theta^{''}(j) = \theta^{''}_{j}$, for $j = 1, 2, \cdots, N$, then

Hence combining equations (3.9) and (3.10), we get (3.8).

The system of $N+1$ equations (3.8) with $N+9$ unknowns $g_{i}$ can be written as:

where the $(N+1)\times(N+9)$ ordered matrix

the $(N+9)\times 1$ ordered matrix

and the $(N+1)\times 1$ ordered matrix

3.2.   Boundary conditions

Since the number of equations (i.e., $N+1$) are less than the number of unknowns (i.e., $N+9$) in the system (3.11). So there are 8 degree of freedoms to get unique solution. Two degree of freedoms are given in (1.2), i.e.

Since 6-point BISS reproduces 3rd degree polynomial with 4th order of approximation so we suggest the boundary conditions of order four for solution. The values of the left end points $g_{-3}, g_{-2}, g_{-1}$ and right end points $g_{N+1}, g_{N+2}, g_{N+3}$ can be computed by using the polynomial $A(t)$ of degree three by interpolating it at $(t_i, g_i)$, $0\leq i\leq3$. Let

where

Since $G(t_i) = g_i$ then by replacing $t_i = -t_i$ for $i = 1, 2, 3$, we have

We suggest the following boundary conditions to find the values of the left end points

Similarly for the right end points, we may define $g_i = A(t_i)$, $i = N+1, N+2, N+3$ where

Similarly, we suggest the following conditions to find the values of the right end points

So we get 6 degree of freedoms from (3.16) and (3.17). Finally, we get the system of $(N+9)\times (N+9)$ nonlinear equations:

where the coefficient matrix $J = (J_{0}^{T}, W^{T}, J_{1}^{T})^T$, $W$ is defined in (3.12). To obtain matrix $J_{0}$, first three rows of $J_{0}$ comes from equation (3.16) and $4th$ row of $J_{0}$ comes from (3.15) at $g_{0} = \beta,$

Similarly for $J_{1}$, first row of $J_{1}$ comes from (3.15) at $g_{N} = \gamma$ and remaining rows come from (3.17),

And $G$ and $R(g)$ are defined as

Now, we see whether or not the system (3.18) is nonsingular. In this system the matrix $J$ is neither diagonally dominant nor symmetric. For the time being, if we ignore the first and last three rows and columns of the matrix $J$ then it is symmetric. We consider the symmetric part of it of order $(N+1)\times (N+1)$ for sufficiently large $N$.

It can be easily seen that the matrix $C$ is nonsingular for $N\leq 1000$. While the determinant of $J$ is also non zero. Its determinant increases as $N$ increases for $N\leq 1000$. This implies that $J$ is nonsingular. In other way, the eigenvalues of $J$ for $N\leq 1000$ are nonzero therefore it is also nonsingular by ^[19]. Hence the system (3.18) is nonsingular for $N\leq 1000$.

3.3.   The iterative algorithm

The iterative algorithm based on 6-point BISS can be summarized in three steps.

Step-$1$. Initial approximation:

First of all choose the initial approximation $G^{0}$ for the system of linear equations:

where

Here $F^{0}$ is the linear approximation of $R(g)$.

Step-$2$. Iterative scheme:

Follow the following iterative scheme for rest of the approximations

Step-$3$. Stoping criteria:

If $\epsilon_{tol}$ is error tolerance then repeat Step-2 until any one of the following inequality is satisfied

3.4.   Convergence of iterative algorithm

The following theorem guaranteed the convergence of iterative algorithm.

Proposition 1. If $L_{0}$ & $L_{1}$ and $h$ are Lipschitz constants and mesh size respectively then the solution at $k$th iteration $\{G^{(k)}\}$ converges linearly to the solution $G^{*}$ of the nonlinear system (3.18) with the condition that Lipschitz constants and mesh size are small enough i.e.,

Proof. For small values of $h$ and $\epsilon < h$, we have $JG^{*} = F(G^{*})$ and $JG^{(k+1)} = F(G^{(k)})$. Then the error vector $E^{(k)} = G^{(k)}-G^{*}$ satisfies the following

For $i = 1, 2, \cdots, N-1$, we get the following by Mean Value Theorem

where the difference operators $D_{1}$ and $D_{2}$ are defined below

Since $E_{i} = E_{N-i} = 0, i = 0, -1, -2, -3, -4,$ therefore

This implies

This further implies

Since

therefore

This completes the proof. In following theorem, we see that the power of approximation of iterative algorithm is at least $O(h^4)$. Its proof is similar to the proof of Proposition in ^[14].

Theorem 3.2. let $y(t)$ be the exact and $G(t)$ be the numerical solutions of the problem (2.1) then

4.   Solution of 2nd order NSPBVP

Here we present the solutions of two 2nd order NSPBVPs obtained by our iterative algorithm.

Example 4.1. Consider the 2nd order NSPBVP

with exact solution

We find the approximate solution of above problem by iterative algorithm with parameters: $\epsilon = (0.244)^{2}$, N = 10 and $tol_\epsilon = 10^{-6}$. We see that the maximum absolute error (MAE) is $2.55676\times10^{-6}$ after third iteration. The comparison between approximate and exact solutions is given in Table 1 and Figure 2.

Example 4.2. Consider the 2nd order NSPBVP

with exact solution

We find the approximate solutions of above problem by iterative algorithm with parameters: $\epsilon = (0.244)^{2}$, $(0.244)^{4} \& (0.244)^{5}$, N = 32 and $tol = 10^{-6}$ and MAE are $0.51\times10^{-2}$, $0.34\times10^{-3}$ $&$ $0.85\times10^{-4}$ obtained after third iteration respectively. The comparison between approximate and exact solutions is given in Tables 2, 3 & 4 and Figure 3. From these tables, we have observed that for very smaller value of $\epsilon$ (i.e. $\epsilon\rightarrow 0$) more accurate results can be achieved.

5.   Conclusion

In this paper, we have presented a 6-point BISS which produces a curvature continuous curve with 4th order of approximation. Firstly, we have explored its qualities for curve modeling. Secondly, we have used this scheme to develop an iterative algorithm for the solution of 2nd order NSPBVP arising from different physical phenomenon. The convergence of an iterative algorithm has also been presented. The approximate solutions of 2nd order NSPBVP obtained by our iterative algorithm has approximation order $\leq O(h^4)$.

Availability of data and material

Data sharing not applicable to this article as no datasets were generated or analysed during the current study.

Author's contributions

The authors have contributed equally to this manuscript. They read and approved the final manuscript.

Acknowledgement

We thanks the anonymous reviewers for careful reading of our manuscript and their many insightful comments and suggestions.

Conflict of interest

The authors declare that they have no competing interests