# Two Legendre-Dual-Petrov-Galerkin Algorithms for Solving the Integrated Forms of High Odd-Order Boundary Value Problems

Authors: Waleed M. Abd-Elhameed; Eid H. Doha; Mahmoud A. Bassuony
Journal: The Scientific World Journal
 (2014)

---

## Abstract

Two numerical algorithms based on dual-Petrov-Galerkin method are developed for solving the integrated forms of high odd-order boundary value problems (BVPs) governed by homogeneous and nonhomogeneous boundary conditions. Two different choices of trial functions and test functions which satisfy the underlying boundary conditions of the differential equations and the dual boundary conditions are used for this purpose. These choices lead to linear systems with specially structured matrices that can be efficiently inverted, hence greatly reducing the cost. The various matrix systems resulting from these discretizations are carefully investigated, especially their complexities and their condition numbers. Numerical results are given to illustrate the efficiency of the proposed algorithms, and some comparisons with some other methods are made.


---

## Body

## 1. Introduction

The spectral methods aim to approximate functions (solutions of differential equations) by means of truncated series of orthogonal polynomials. The main feature of spectral methods is to take various orthogonal systems of infinitely differentiable global functions as trial functions. The choice of different trial functions leads to different spectral approximations; for instance, the choice of trigonometric polynomials is suitable for periodic problems, while the choice of Chebyshev, Legendre, ultraspherical and classical Jacobi polynomials is suitable for nonperiodic problems. (see [1–7]).Because of being extremely accurate, spectral methods have been intensively studied and successfully applied to numerical simulations in many fields. They have gained new popularity in automatic computations for a wide class of physical problems in fluid and heat flow. Mainly, there are three types of spectral methods, namely, collocation, tau, and Galerkin. The choice of the type of the method depends essentially on the application. Collocation methods are appropriate for studying nonlinear problems or when the problem has complicated coefficients, while Galerkin methods have the advantage of a more convenient analysis and optimal error analysis estimates. The tau method is applicable in the case of complicated (even nonlinear) boundary conditions, where Galerkin approach would be impossible and the collocation is extremely tedious (see [2, 5, 8]).For the spectral solutions of odd-order differential equations by direct collocation methods, we obtain condition number ofO
(
N
2
k
), where N is the number of retained modes and k is the order of equation. This high condition number will lead to instabilities caused by rounding errors (see [9, 10]).High even-order boundary value problems have been investigated by a large number of authors because of both their mathematical importance and their potential for applications in hydrodynamic and hydromagnetic stability. Therefore, availability of fast and accurate algorithms to solve these equations will allow rapid solutions of many practical problems. Doha and Abd-Elhameed [11] and Doha et al. [12–14] have constructed efficient spectral-Galerkin algorithms using compact combinations of orthogonal polynomials for solving second and higher order equations.Also, the study of odd-order equations is of interest; for example, the third-order equation is of fundamental mathematical interest since it lacks symmetry. Also, it is of physical interest since it contains a type of operator which appears in many commonly occurring partial differential equations such as the Korteweg-de Vries equation. Fifth-order boundary value problems arise in the mathematical modelling of viscoelastic flows (see [15, 16]). Some studies are concerned with third- and fifth-order differential equations in finite intervals (see [17, 18]). Doha and Abd-Elhameed [19] have constructed efficient spectral-Galerkin algorithms using compact combinations of ultraspherical polynomials for solving the differentiated forms of elliptic equations of (
2
n
+
1
)th-order. Recently, Bhrawy and Alghamdi [20], Doha et al. [21–23],have analyzed some algorithms for solving numerically the third- and fifth-order differential equations.The main objective of this paper is to develop some efficient spectral algorithms based on Legendre-dual-Petrov-Galerkin method (LDPGM) for the solution of the integrated forms of high odd-order BVPs in one variable. We present two different choices of appropriate bases for the LDPGM applied to high odd-order BVPs with homogenous and nonhomogenous boundary conditions. All the matrix systems resulted from the application of LDPGM to the integrated forms of(
2
n
+
1
)th-order differential equations are band, and then they are cheaper to solve than the systems obtained from the differentiated forms (see Doha and Abd-Elhameed [19]). This motivates our interest for applying LDPGM to the integrated forms of (
2
n
+
1
)th-order differential equations.The remainder of the article is organized as follows. In Section2, some properties of Legendre polynomials and their shifted ones are given. The main results of this paper are presented in Section 3, in which two numerical algorithms for solving the integrated forms of (
2
n
+
1
)th-order elliptic linear differential equations subject to homogeneous boundary conditions using two choices of bases functions are presented and implemented. Also, the same equations but governed by nonhomogeneous boundary conditions are noted in Section 3. For the sake of demonstrating the efficiency and the applicability of our two presented algorithms and also for the sake of comparison between these two algorithms, some numerical results are presented in Section 4. Some concluding remarks are given in Section 5.


## 2. Some Properties of Legendre Polynomials

The Legendre polynomials{
L
n
(
x
)
,
n
=
0,1
,
2
,
…
} are a sequence of orthogonal polynomials on the interval (
-
1,1
); that is,
(1)
∫
-
1
1
L
k
(
x
)
L
j
(
x
)
d
x
=
{
0
,
k
≠
j
,
2
2
k
+
1
,
k
=
j
.
The following special values of L
k
(
x
) and D
q
L
k
(
x
)
=
(
d
q
L
k
(
x
)
/
d
x
q
) are important in our subsequent work:
(2)
L
k
(
-
x
)
=
(
-
1
)
n
L
k
(
x
)
,
L
k
(
±
1
)
=
(
±
1
)
k
,
D
q
L
k
(
±
1
)
=
1
2
(
±
1
)
k
+
q
∏
m
=
0
q
-
1
‍
(
k
-
m
)
(
k
+
m
+
1
)
(
m
+
1
)
,
q
=
1,2
,
…
.
The following two theorems and two lemmas are also needed hereafter.Theorem 1.
If theq times repeated integration of L
k
(
x
) is denoted by
(3)
I
k
(
q
)
(
x
)
=
∫
‍
∫
‍
⋯
∫
‍
︷
q
t
i
m
e
s
L
k
(
x
)
d
x
d
x
⋯
d
x
,
then I
k
(
q
)
(
x
) is given by
(4)
I
k
(
q
)
(
x
)
=
∑
j
=
0
q
‍
r
j
,
k
,
q
L
k
+
q
-
2
j
(
x
)
+
π
q
-
1
(
x
)
,
where
(5)
r
j
,
k
,
q
=
(
-
1
)
j
(
q
j
)
(
k
+
q
-
2
j
+
(
1
/
2
)
)
Γ
(
k
-
j
+
(
1
/
2
)
)
2
q
Γ
(
k
+
q
-
j
+
(
3
/
2
)
)
,
and π
q
-
1
(
x
) is a polynomial of degree at most (
q
-
1
).(For the proof of Theorem1, see Doha [3].)Theorem 2.
For allj
,
m
∈
ℤ
+, one has
(6)
x
m
L
j
(
x
)
=
∑
n
=
0
m
‍
λ
m
,
2
n
(
j
)
L
j
+
m
-
2
n
(
x
)
,
where
(7)
λ
m
,
2
n
(
j
)
=
2
j
+
m
-
2
n
+
1
j
!
m
!
(
j
+
m
-
2
n
+
(
1
/
2
)
)
(
j
+
m
-
2
n
)
!
×
∑
k
=
max
⁡
(
0
,
j
-
2
n
)
min
⁡
(
j
+
m
-
2
n
,
j
)
‍
(
(
(
j
+
m
-
2
n
k
)
(
j
+
k
)
!
)
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
×
(
2
k
(
2
n
+
k
-
j
)
!
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
×
(
3
j
+
2
m
-
4
n
-
k
+
1
)
!
2
k
)
-
1
(
(
j
+
m
-
2
n
k
)
)
)
×
∑
ℓ
=
0
j
-
k
‍
(
(
(
-
1
)
ℓ
(
2
j
+
m
-
2
n
-
k
-
ℓ
)
!
a
a
a
a
a
a
a
a
a
×
(
j
+
m
-
2
n
+
ℓ
)
!
)
a
a
a
a
a
a
×
(
ℓ
!
(
j
-
k
-
ℓ
)
!
(
j
-
ℓ
)
!
(
k
+
ℓ
)
!
)
-
1
(
(
-
1
)
ℓ
!
)
×
F
1
2
(
-
(
k
-
j
+
2
n
)
,
j
+
m
-
2
n
+
ℓ
+
1
;
ci
aa
3
j
+
2
m
-
4
n
-
k
+
2
;
2
)
.(For the proof of Theorem2, see, Doha [24].)Lemma 3.
For allk
,
m
∈
ℤ
+, one has
(8)
(
1
-
x
2
)
m
L
k
(
x
)
=
∑
s
=
0
2
m
‍
h
s
,
m
(
k
)
L
k
-
2
s
+
2
m
(
x
)
,
where
(9)
h
s
,
m
(
k
)
=
∑
i
=
0
m
‍
(
-
1
)
i
(
m
i
)
λ
2
i
,
s
+
i
-
m
(
k
)
,
and λ
m
,
s
(
k
) is defined as in relation (6).Proof.
By binomial theorem, we have(10)
(
1
-
x
2
)
m
L
k
(
x
)
=
∑
s
=
0
m
‍
(
-
1
)
s
(
m
s
)
x
2
s
L
k
(
x
)
;
then, by using relation (6), we get
(11)
(
1
-
x
2
)
m
L
k
(
x
)
=
∑
s
=
0
m
‍
∑
r
=
0
2
s
‍
(
-
1
)
s
(
m
s
)
λ
2
s
,
r
(
k
)
L
k
+
2
s
-
2
r
(
x
)
.
If we expand relation (11) and collect similar terms, then, after some rather algebraic manipulation, relation (8) is obtained. This completes the proof of Lemma 3.Lemma 4.
For allk
,
m
∈
ℤ
+, one has
(12)
(
1
-
x
2
)
m
(
1
+
x
)
L
k
(
x
)
=
∑
s
=
0
4
m
+
2
‍
w
s
,
m
(
k
)
L
k
+
2
m
-
s
+
1
(
x
)
,
(
1
-
x
2
)
m
(
1
-
x
)
L
k
(
x
)
=
∑
s
=
0
4
m
+
2
‍
w
-
s
,
m
(
k
)
L
k
+
2
m
-
s
+
1
(
x
)
,
where
(13)
w
s
,
m
(
k
)
=
{
(
k
+
2
m
+
1
)
(
2
k
+
4
m
+
1
)
h
0
,
m
(
k
)
,
s
=
0
,
(
k
-
2
m
+
1
)
(
2
k
-
4
m
+
1
)
h
2
m
,
m
(
k
)
,
s
=
4
m
+
2
,
h
(
s
-
1
)
/
2
,
m
(
k
)
,
s
o
d
d
,
(
k
+
2
m
-
s
+
3
)
(
2
k
+
4
m
-
s
+
5
)
h
(
s
-
2
)
/
2
,
m
(
k
)
+
(
k
+
2
m
-
s
+
1
)
(
2
k
+
4
m
-
s
+
1
)
h
s
/
2
,
m
(
k
)
,
s
e
v
e
n
,
w
-
s
,
m
(
k
)
=
(
-
1
)
s
+
1
w
s
,
m
(
k
) and h
s
,
m
(
k
) is defined as in Lemma 3.Proof.
This lemma can be immediately proved by multiplying both sides of relation (8) by (
1
+
x
) and (
1
-
x
), respectively, and performing some simple algebraic manipulations.


### 2.1. Shifted Legendre Polynomials

The shifted Legendre polynomials are defined on[
a
,
b
] as
(14)
L
k
*
(
x
)
=
L
k
(
2
x
-
a
-
b
b
-
a
)
.
All results of Legendre polynomials can be easily transformed to give the corresponding results for their shifted ones.The orthogonality relation ofL
k
*
(
x
) on [
a
,
b
] is given by
(15)
∫
a
b
‍
L
k
*
(
x
)
L
j
*
(
x
)
d
x
=
{
0
,
k
≠
j
,
b
-
a
2
k
+
1
,
k
=
j
.
Now, based on relation (14) and with the aid of formula (4), we have the following theorem.Theorem 5.
If theq times repeated integration of L
k
*
(
x
) is denoted by
(16)
J
k
(
q
)
(
x
)
=
∫
‍
∫
‍
⋯
∫
‍
︷
q
t
i
m
e
s
L
k
*
(
x
)
d
x
d
x
⋯
d
x
︷
q
t
i
m
e
s
,
then
(17)
J
k
(
q
)
(
x
)
=
(
b
-
a
2
)
q
∑
j
=
0
q
‍
r
j
,
k
,
q
L
k
+
q
-
2
j
*
(
x
)
+
π
-
q
-
1
(
x
)
,
where r
j
,
k
,
q is defined as in (5) and π
-
q
-
1
(
x
) is a polynomial in x of degree (
q
-
1
) at most.Remark 6.
For allx
∈
[
a
,
b
] and k
,
m
∈
ℤ
+, one has
(18)
(
x
-
a
)
m
+
1
(
b
-
x
)
m
L
k
*
(
x
)
=
(
b
-
a
2
)
2
m
+
1
∑
s
=
0
4
m
+
2
‍
w
s
,
m
(
k
)
L
k
+
2
m
-
s
+
1
*
(
x
)
,
(19)
(
x
-
a
)
m
(
b
-
x
)
m
+
1
L
k
*
(
x
)
=
(
b
-
a
2
)
2
m
+
1
∑
s
=
0
4
m
+
2
‍
w
-
s
,
m
(
k
)
L
k
+
2
m
-
s
+
1
*
(
x
)
,
where w
s
,
m
(
k
) and w
-
s
,
m
(
k
) are defined as in Lemma 4.


## 2.1. Shifted Legendre Polynomials

The shifted Legendre polynomials are defined on[
a
,
b
] as
(14)
L
k
*
(
x
)
=
L
k
(
2
x
-
a
-
b
b
-
a
)
.
All results of Legendre polynomials can be easily transformed to give the corresponding results for their shifted ones.The orthogonality relation ofL
k
*
(
x
) on [
a
,
b
] is given by
(15)
∫
a
b
‍
L
k
*
(
x
)
L
j
*
(
x
)
d
x
=
{
0
,
k
≠
j
,
b
-
a
2
k
+
1
,
k
=
j
.
Now, based on relation (14) and with the aid of formula (4), we have the following theorem.Theorem 5.
If theq times repeated integration of L
k
*
(
x
) is denoted by
(16)
J
k
(
q
)
(
x
)
=
∫
‍
∫
‍
⋯
∫
‍
︷
q
t
i
m
e
s
L
k
*
(
x
)
d
x
d
x
⋯
d
x
︷
q
t
i
m
e
s
,
then
(17)
J
k
(
q
)
(
x
)
=
(
b
-
a
2
)
q
∑
j
=
0
q
‍
r
j
,
k
,
q
L
k
+
q
-
2
j
*
(
x
)
+
π
-
q
-
1
(
x
)
,
where r
j
,
k
,
q is defined as in (5) and π
-
q
-
1
(
x
) is a polynomial in x of degree (
q
-
1
) at most.Remark 6.
For allx
∈
[
a
,
b
] and k
,
m
∈
ℤ
+, one has
(18)
(
x
-
a
)
m
+
1
(
b
-
x
)
m
L
k
*
(
x
)
=
(
b
-
a
2
)
2
m
+
1
∑
s
=
0
4
m
+
2
‍
w
s
,
m
(
k
)
L
k
+
2
m
-
s
+
1
*
(
x
)
,
(19)
(
x
-
a
)
m
(
b
-
x
)
m
+
1
L
k
*
(
x
)
=
(
b
-
a
2
)
2
m
+
1
∑
s
=
0
4
m
+
2
‍
w
-
s
,
m
(
k
)
L
k
+
2
m
-
s
+
1
*
(
x
)
,
where w
s
,
m
(
k
) and w
-
s
,
m
(
k
) are defined as in Lemma 4.


## 3. Solution of High Odd-Order BVPs

We are interested in using the LDPGM to solve the two-point high odd-order BVPs(20)
u
(
2
n
+
1
)
(
x
)
+
∑
i
=
0
2
n
‍
η
i
u
(
i
)
(
x
)
=
f
(
x
)
,
x
∈
(
a
,
b
)
,
n
≥
1
,
governed by the homogeneous boundary conditions
(21)
u
(
j
)
(
a
)
=
u
(
j
)
(
b
)
=
u
(
n
)
(
a
)
=
0
,
j
=
0,1
,
…
,
n
-
1
,
where u
(
j
)
(
x
)
=
D
j
u
(
x
) denotes the jth derivative of u
(
x
) with respect to x and {
η
i
,
i
=
0,1
,
…
,
2
n
} are known constant coefficients.In this section, we consider two kinds of bases to numerically solve (20) governed by (21) but by considering its integrated form; namely,
(22)
u
(
x
)
+
∑
i
=
0
2
n
‍
η
i
∫
(
2
n
-
i
+
1
)
u
(
x
)
(
d
x
)
(
2
n
-
i
+
1
)
=
p
(
x
)
+
∑
i
=
0
2
n
‍
b
i
L
i
*
(
x
)
,
x
∈
(
a
,
b
)
,
u
(
j
)
(
a
)
=
u
(
j
)
(
b
)
=
u
(
n
)
(
a
)
=
0
,
j
=
0,1
,
…
,
n
-
1
,
where
(23)
∫
(
q
)
u
(
x
)
(
d
x
)
q
=
∫
‍
∫
‍
⋯
∫
‍
︷
q
t
i
m
e
s
u
(
x
)
d
x
d
x
⋯
d
x
︷
q
t
i
m
e
s
,
p
(
x
)
=
∫
(
2
n
+
1
)
f
(
x
)
(
d
x
)
(
2
n
+
1
)
,
and {
b
i
,
i
=
0,1
,
…
,
2
n
} are the unknown constants of integration.We set(24)
S
N
=
span
⁡
{
L
0
*
(
x
)
,
L
1
*
(
x
)
,
…
,
L
N
*
(
x
)
}
,
Y
N
=
{
y
∈
S
N
:
y
(
j
)
(
a
)
=
y
(
j
)
(
b
)
=
y
(
n
)
(
a
)
=
0
,
j
=
0,1
,
…
,
n
-
1
y
(
j
)
}
,
Y
-
N
=
{
y
∈
S
N
:
y
(
j
)
(
a
)
=
y
(
j
)
(
b
)
=
y
(
n
)
(
b
)
=
0
,
j
=
0,1
,
…
,
n
-
1
y
(
j
)
}
,
and then the LDPGM for solving (20)-(21) or its equivalent integrated form (22) is to find u
N
n
∈
Y
N such that
(25)
(
u
N
n
(
x
)
,
y
(
x
)
)
+
∑
i
=
0
2
n
‍
η
i
(
∫
(
2
n
-
i
+
1
)
u
N
n
(
x
)
(
d
x
)
(
2
n
-
i
+
1
)
,
y
(
x
)
)
=
(
p
(
x
)
+
∑
i
=
0
2
n
‍
b
i
L
i
*
(
x
)
,
y
(
x
)
)
,
∀
y
∈
Y
-
N
,
where (
u
,
v
)
=
∫
a
b
‍
u
(
x
)
v
(
x
)
d
x is the scalar inner product in the space L
2
(
a
,
b
). Chebyshev, Legendre,In the following two subsections, we will apply the dual Petrov-Galerkin method to solve (22) based on choosing two kinds of bases functions. These two choices enable one to obtain two linear systems of specially structured matrices that can be efficiently inverted.


### 3.1. The First Choice of Basis Functions

First, we consider the case[
a
,
b
]
=
[
-
1,1
] and set
(26)
θ
k
,
n
(
x
)
=
L
k
(
x
)
+
∑
m
=
1
2
n
+
1
‍
d
m
,
k
L
k
+
m
(
x
)
,
k
=
0,1
,
2
,
…
,
N
-
2
n
-
1
,
n
≥
1
,
θ
¯
k
,
n
(
x
)
=
L
k
(
x
)
+
∑
m
=
1
2
n
+
1
‍
d
-
m
,
k
L
k
+
m
(
x
)
,
k
=
0,1
,
2
,
…
,
N
-
2
n
-
1
,
n
≥
1
.
We choose the coefficients {
d
m
,
k
} and {
d
-
m
,
k
} such that θ
k
,
n
(
x
)
∈
Y
k
+
2
n
+
1 and θ
¯
k
,
n
(
x
)
∈
Y
-
k
+
2
n
+
1, respectively. The boundary conditions θ
k
,
n
(
j
)
(
a
)
=
θ
k
,
n
(
j
)
(
b
)
=
θ
k
,
n
(
n
)
(
a
)
=
0
,
j
=
0,1
,
…
,
n
-
1 lead to the following system of equations:
(27)
∑
m
=
1
2
n
+
1
‍
(
-
1
)
m
d
m
,
k
=
-
1
,
∑
m
=
1
2
n
+
1
‍
(
-
1
)
m
[
∏
s
=
0
q
-
1
‍
(
k
+
m
-
s
)
(
k
+
m
+
s
+
1
)
]
×
d
m
,
k
=
-
∏
s
=
0
q
-
1
‍
(
k
-
s
)
(
k
+
s
+
1
)
,
q
=
1,2
,
…
,
n
,
n
≥
1
,
∑
m
=
1
2
n
+
1
‍
d
m
,
k
=
-
1
,
∑
m
=
1
2
n
+
1
‍
∏
s
=
0
q
-
1
‍
(
k
+
m
-
s
)
(
k
+
m
+
s
+
1
)
d
m
,
k
=
-
∏
s
=
0
q
-
1
‍
(
k
-
s
)
(
k
+
s
+
1
)
,
q
=
1,2
,
…
,
n
-
1
,
n
≥
1
.
The determinant of the above system of linear equations is different from zero; hence, {
d
m
,
k
} can be uniquely determined to give
(28)
d
m
,
k
=
(
-
1
)
m
{
(
(
-
1
)
m
/
2
(
n
m
2
)
(
k
+
m
+
1
2
)
×
Γ
(
k
+
m
+
1
2
)
Γ
(
k
+
n
+
3
2
)
(
n
m
2
)
)
×
(
Γ
(
k
+
3
2
)
Γ
(
k
+
n
+
m
+
3
2
)
)
-
1
,
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
f
m
even
,
(
(
-
1
)
(
m
+
1
)
/
2
(
n
m
-
1
2
)
(
k
+
m
+
1
2
)
×
Γ
(
k
+
m
2
+
1
)
Γ
(
k
+
n
+
3
2
)
(
n
m
2
)
)
×
(
Γ
(
k
+
3
2
)
Γ
(
k
+
n
+
m
2
+
2
)
)
-
1
,
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
m
odd
.
Similarly, it can be easily shown that {
d
-
m
,
k
} are given by
(29)
d
-
m
,
k
=
(
-
1
)
m
d
m
,
k
,
m
=
1,2
,
…
,
2
n
+
1
.
Second, if we replace x in (26) by (
(
2
x
-
a
-
b
)
/
(
b
-
a
)
), for a
≤
x
≤
b, and if we define
(30)
θ
k
,
n
(
2
x
-
a
-
b
b
-
a
)
=
ϕ
k
,
n
(
x
)
,
θ
-
k
,
n
(
2
x
-
a
-
b
b
-
a
)
=
ψ
k
,
n
(
x
)
,
x
∈
[
a
,
b
]
,
then it is obvious that the basis functions and their dual are given, respectively, by
(31)
ϕ
k
,
n
(
x
)
=
∑
m
=
0
2
n
+
1
‍
d
m
,
k
L
k
+
m
*
(
x
)
,
(32)
ψ
k
,
n
(
x
)
=
∑
m
=
0
2
n
+
1
‍
d
-
m
,
k
L
k
+
m
*
(
x
)
,
where d
m
,
k and d
-
m
,
k are as given in (28) and (29), respectively.Now it is clear that (25) is equivalent to
(33)
(
u
N
n
(
x
)
,
ψ
k
,
n
(
x
)
)
+
∑
i
=
0
2
n
‍
η
i
(
∫
(
2
n
-
i
+
1
)
u
N
n
(
x
)
(
d
x
)
(
2
n
-
i
+
1
)
,
ψ
k
,
n
(
x
)
)
=
(
p
(
x
)
+
∑
i
=
0
2
n
‍
b
i
L
i
*
(
x
)
,
ψ
k
,
n
(
x
)
)
.
If we take k
≥
2
n
+
1 in (33), then the constants b
i
,
0
≤
i
≤
2
n, would disappear, and then we get
(34)
(
u
N
n
(
x
)
,
ψ
k
,
n
(
x
)
)
+
∑
i
=
0
2
n
‍
η
i
(
∫
(
2
n
-
i
+
1
)
u
N
n
(
x
)
(
d
x
)
(
2
n
-
i
+
1
)
,
ψ
k
,
n
(
x
)
)
=
(
p
(
x
)
,
ψ
k
,
n
(
x
)
)
,
2
n
+
1
≤
k
≤
N
.
If we denote
(35)
p
k
n
=
(
p
(
x
)
,
ψ
k
,
n
(
x
)
)
,
p
n
=
(
p
2
n
+
1
n
,
p
2
n
+
2
n
,
…
,
p
N
n
)
T
,
u
N
n
(
x
)
=
∑
m
=
0
N
-
2
n
-
1
‍
v
m
n
ϕ
m
,
n
(
x
)
,
v
n
=
(
v
0
n
,
v
1
n
,
…
,
v
N
-
2
n
-
1
n
)
T
,
A
n
=
(
a
k
j
n
)
2
n
+
1
≤
k
,
j
≤
N
,
B
2
n
-
i
+
1
,
n
=
(
b
k
j
2
n
-
i
+
1
,
n
)
2
n
+
1
≤
k
,
j
≤
N
,
0
≤
i
≤
2
n
,
then (34) is equivalent to the following matrix system:
(36)
(
A
n
+
∑
i
=
0
2
n
‍
η
i
B
2
n
-
i
+
1
,
n
)
v
n
=
p
n
,
where the nonzero elements of the matrices A
n and B
2
n
-
i
+
1
,
n
(
0
≤
i
≤
2
n
) are given explicitly in the following theorem.Theorem 7.
If the basis functionsϕ
k
,
n
(
x
) and their dual ψ
k
,
n
(
x
) are taken as in (31) and (32), respectively, and if we denote a
k
j
n
=
(
ϕ
j
-
2
n
-
1
,
n
(
x
)
,
ψ
k
,
n
(
x
)
) and b
k
j
2
n
-
i
+
1
,
n
=
(
∫
(
2
n
-
i
+
1
)
ϕ
j
-
2
n
-
1
,
n
(
x
)
(
d
x
)
(
2
n
-
i
+
1
)
,
ψ
k
,
n
(
x
)
)
,
0
≤
i
≤
2
n, then
(37)
Y
N
+
2
n
+
1
=
s
p
a
n
{
ϕ
0
,
n
(
x
)
,
ϕ
1
,
n
(
x
)
,
…
,
ϕ
N
,
n
(
x
)
}
,
Y
-
N
+
2
n
+
1
=
s
p
a
n
{
ψ
0
,
n
(
x
)
,
ψ
1
,
n
(
x
)
,
…
,
ψ
N
,
n
(
x
)
}
,
and the nonzero elements of the matrices A
n
,
B
2
n
-
i
+
1
,
n
(
0
≤
i
≤
2
n
) are given explicitly by
(38)
a
k
k
n
=
(
-
1
)
n
+
1
(
b
-
a
)
Γ
2
(
k
-
n
+
(
1
/
2
)
)
2
Γ
(
k
+
(
3
/
2
)
)
Γ
(
k
-
2
n
+
(
1
/
2
)
)
,
(39)
a
k
j
n
=
(
-
1
)
j
-
k
-
1
(
b
-
a
)
×
∑
m
=
0
2
n
+
1
‍
(
-
1
)
m
d
m
,
j
-
2
n
-
1
d
j
-
k
+
m
-
2
n
-
1
,
k
(
2
j
+
2
m
-
4
n
-
1
)
,
aaaa
1
≤
j
-
k
≤
4
n
+
2
,
(40)
b
k
j
2
n
-
i
+
1
,
n
=
(
-
1
)
j
-
k
-
i
(
b
-
a
)
2
n
-
i
+
2
2
2
n
-
i
+
1
×
∑
m
=
0
2
n
+
1
‍
∑
ℓ
=
0
2
n
-
i
+
1
(
(
(
-
1
)
m
d
m
,
j
-
2
n
-
1
d
j
+
m
-
i
-
2
ℓ
-
k
,
k
h
h
h
h
h
h
h
h
h
h
h
h
h
h
×
r
ℓ
,
j
-
2
n
+
m
-
1
,
2
n
-
i
+
1
)
h
h
h
h
h
h
h
h
h
h
h
h
h
×
(
2
j
+
2
m
-
2
i
-
4
ℓ
+
1
)
-
1
)
,
hhhhhhhhhhhhhh
i
-
2
n
-
1
≤
j
-
k
≤
6
n
-
i
+
3
,
where r
ℓ
,
j
,
q and d
m
,
j are, respectively, defined as in (5) and (28).Proof .
We choose the basis functionsϕ
k
,
n
(
x
) and their dual ψ
k
,
n
(
x
) such that ϕ
k
,
n
(
x
)
∈
Y
N
+
2
n
+
1 and ψ
k
,
n
(
x
)
∈
Y
-
N
+
2
n
+
1 for k
=
0,1
,
…
,
N. Moreover, it is clear that {
ϕ
k
,
n
(
x
)
} and {
ψ
k
,
n
(
x
)
} are linearly independent and the dimension of each of Y
N
+
2
n
+
1 and  Y
-
N
+
2
n
+
1 is equal to (
N
+
1
). Hence,
(41)
Y
N
+
2
n
+
1
=
span
⁡
{
ϕ
0
,
n
(
x
)
,
ϕ
1
,
n
(
x
)
,
…
,
ϕ
N
,
n
(
x
)
}
,
Y
-
N
+
2
n
+
1
=
span
⁡
{
ψ
0
,
n
(
x
)
,
ψ
1
,
n
(
x
)
,
…
,
ψ
N
,
n
(
x
)
}
.
The nonzero elements (
a
k
j
n
) for 2
n
+
1
≤
k
,
j
≤
N, can be obtained by making use of formulae (31) and (32). Now, a
k
j
n is given by
(42)
a
k
j
n
=
(
∑
m
=
0
2
n
+
1
‍
d
m
,
j
-
2
n
-
1
L
j
-
2
n
+
m
-
1
*
(
x
)
,
∑
p
=
0
2
n
+
1
‍
(
-
1
)
p
d
p
,
k
L
k
+
p
*
(
x
)
)
=
∑
m
=
0
2
n
+
1
∑
p
=
0
2
n
+
1
(
-
1
)
p
d
m
,
j
-
2
n
-
1
d
p
,
k
(
L
j
-
2
n
+
m
-
1
*
(
x
)
,
L
k
+
p
*
(
x
)
)
,
which in turn, with the aid of the orthogonality relation (15), yields
(43)
a
k
j
n
=
(
-
1
)
j
-
k
-
1
(
b
-
a
)
×
∑
m
=
0
2
n
+
1
‍
(
-
1
)
m
d
m
,
j
-
2
n
-
1
d
j
-
k
+
m
-
2
n
-
1
,
k
(
2
j
+
2
m
-
4
n
-
1
)
,
which proves relation (39). From (43) and (28), it is not difficult to prove that
(44)
a
k
k
n
=
(
-
1
)
n
+
1
(
b
-
a
)
Γ
2
(
k
-
n
+
(
1
/
2
)
)
2
Γ
(
k
+
(
3
/
2
)
)
Γ
(
k
-
2
n
+
(
1
/
2
)
)
.
To prove relation (40), we have, for 0
≤
i
≤
2
n,
(45)
b
k
j
2
n
-
i
+
1
,
n
=
(
∫
(
2
n
-
i
+
1
)
ϕ
j
-
2
n
-
1
,
n
(
x
)
(
d
x
)
(
2
n
-
i
+
1
)
,
ψ
k
,
n
(
x
)
)
=
(
∑
m
=
0
2
n
+
1
d
m
,
j
-
2
n
-
1
J
j
-
2
n
+
m
-
1
(
2
n
-
i
+
1
)
(
x
)
,
c
c
i
i
∑
p
=
0
2
n
+
1
‍
(
-
1
)
p
d
p
,
k
L
k
+
p
*
(
x
)
)
.
Making use of Theorem 5 enables one to write
(46)
J
j
-
2
n
+
m
-
1
(
2
n
-
i
+
1
)
(
x
)
=
(
b
-
a
2
)
(
2
n
-
i
+
1
)
×
∑
ℓ
=
0
2
n
-
i
+
1
r
ℓ
,
j
-
2
n
+
m
-
1,2
n
-
i
+
1
×
L
j
+
m
-
i
-
2
ℓ
*
(
x
)
+
π
-
2
n
-
i
(
x
)
,
where r
j
,
k
,
q is defined as in (5) and π
-
2
n
-
i is a polynomial in x of degree (
2
n
-
i
) at most.
This, with the orthogonality relation (15), yields
(47)
b
k
j
2
n
-
i
+
1
,
n
=
(
-
1
)
j
-
k
-
i
(
b
-
a
)
2
n
-
i
+
2
2
2
n
-
i
+
1
×
∑
m
=
0
2
n
+
1
∑
ℓ
=
0
2
n
-
i
+
1
(
(
(
-
1
)
m
d
m
,
j
-
2
n
-
1
d
j
+
m
-
i
-
2
ℓ
-
k
,
k
‍
aaaaaaaaaaaaaaaa
a
a
×
r
ℓ
,
j
-
2
n
+
m
-
1,2
n
-
i
+
1
)
f
f
f
f
f
f
f
f
f
f
f
f
f
f
×
(
2
j
+
2
m
-
2
i
-
4
ℓ
+
1
)
-
1
)
,
which completes the proof of Theorem 7.


### 3.2. The Second Choice of Basis Functions

As a second choice ofϕ
k
,
n
(
x
) and ψ
k
,
n
(
x
), we write
(48)
ϕ
k
,
n
(
x
)
=
(
2
b
-
a
)
2
n
+
1
(
x
-
a
)
n
+
1
(
b
-
x
)
n
L
k
*
(
x
)
,
(49)
ψ
k
,
n
(
x
)
=
(
2
b
-
a
)
2
n
+
1
(
x
-
a
)
n
(
b
-
x
)
n
+
1
L
k
*
(
x
)
,
which automatically fulfill the boundary conditions (21) and their dual conditions, respectively.The following lemma is of fundamental importance in what follows.Lemma 8.
For arbitrary constantsv
k
n, one has
(50)
∑
k
=
0
N
-
2
n
-
1
‍
v
k
n
ϕ
k
,
n
(
x
)
=
∑
k
=
0
N
‍
e
k
L
k
*
(
x
)
,
where
(51)
e
k
=
∑
s
=
0
4
n
+
2
‍
w
s
,
n
(
k
-
2
n
+
s
-
1
)
v
k
-
2
n
+
s
-
1
n
.
Moreover,
(52)
∫
(
q
)
(
∑
k
=
0
N
-
2
n
-
1
‍
v
k
n
ϕ
k
,
n
(
x
)
)
(
d
x
)
(
q
)
=
∑
k
=
0
N
+
q
‍
t
k
,
q
L
k
*
(
x
)
+
ρ
q
-
1
(
x
)
,
1
≤
q
≤
2
n
+
1
,
where
(53)
t
k
,
q
=
(
b
-
a
2
)
q
×
∑
j
=
0
q
‍
∑
s
=
0
4
n
+
2
w
s
,
n
(
k
-
2
n
+
s
+
2
j
-
q
-
1
)
×
r
j
,
k
-
q
+
2
j
,
q
v
k
-
2
n
+
s
+
2
j
-
q
-
1
n
,
and w
s
,
n
(
k
) is defined as in (13) and ρ
q
-
1
(
x
) is a polynomial of degree (
q
-
1
) at most.Proof.
The first part of this lemma can be directly proved with the aid of Lemma4. To prove the second part, we integrate both sides of (50) q times, 1
≤
q
≤
2
n
+
1, and, after making use of formula (17), we obtain
(54)
∫
(
q
)
(
∑
k
=
0
N
-
2
n
-
1
‍
v
k
n
ϕ
k
,
n
(
x
)
)
(
d
x
)
(
q
)
=
(
b
-
a
2
)
q
∑
k
=
0
N
‍
e
k
∑
j
=
0
q
‍
r
j
,
k
,
q
L
k
+
q
-
2
j
*
(
x
)
+
ρ
q
-
1
,
which may be written in the form
(55)
∫
(
q
)
(
∑
k
=
0
N
-
2
n
-
1
‍
v
k
n
ϕ
k
,
n
(
x
)
)
(
d
x
)
(
q
)
=
∑
k
=
0
N
+
q
‍
t
k
,
q
L
k
*
(
x
)
+
ρ
q
-
1
,
where
(56)
t
k
,
q
=
(
b
-
a
2
)
q
∑
j
=
0
q
‍
e
k
-
q
+
2
j
r
j
,
k
-
q
+
2
j
,
q
.
Now, making use of relation (51) enables one to write t
k
,
q in the form
(57)
t
k
,
q
=
(
b
-
a
2
)
q
×
∑
j
=
0
q
‍
∑
s
=
0
4
n
+
2
w
s
,
n
(
k
-
2
n
+
s
+
2
j
-
q
-
1
)
×
r
j
,
k
-
q
+
2
j
,
q
v
k
-
2
n
+
s
+
2
j
-
q
-
1
n
,
and this completes the proof of Lemma 8.Theorem 9.
Ifu
N
n
(
x
)
=
∑
k
=
0
N
-
2
n
-
1
v
k
n
ϕ
k
,
n
(
x
) is the dual Petrov-Galerkin approximation to (20) and (21), then the expansion coefficients {
v
k
n
:
k
=
0,1
,
…
,
N
-
2
n
-
1
} satisfy the matrix system
(58)
(
A
-
n
+
∑
q
=
1
2
n
+
1
‍
η
2
n
-
q
+
1
B
-
q
,
n
)
v
n
=
p
*
n
,
where the nonzero elements of the matrices A
-
n and B
-
q
,
n
,
1
≤
q
≤
2
n
+
1 are given by
(59)
a
-
k
k
n
=
k
!
Γ
(
k
-
2
n
-
(
1
/
2
)
)
2
2
n
+
1
(
k
-
2
n
-
1
)
!
Γ
(
k
+
(
1
/
2
)
)
,
(60)
a
-
k
j
n
=
w
j
-
k
,
n
(
j
-
2
n
-
1
)
,
k
≤
j
≤
k
+
4
n
+
2
,
(61)
b
-
k
j
q
,
n
=
(
b
-
a
2
)
q
∑
s
=
0
q
‍
w
j
-
k
+
q
-
2
s
,
n
(
j
-
2
n
-
1
)
r
s
,
k
-
q
+
2
s
,
q
,
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
,
k
-
q
≤
j
≤
k
+
4
n
+
q
+
2
,
where r
ℓ
,
j
,
q and w
s
,
n are, respectively, defined as in (5) and (13).Proof.
If we apply the LDPGM to (20), then we have
(62)
(
u
N
n
(
x
)
+
∑
q
=
1
2
n
+
1
‍
η
2
n
+
1
-
q
∫
(
q
)
u
N
n
(
d
x
)
(
q
)
,
ψ
k
,
n
(
x
)
)
=
(
p
(
x
)
+
∑
i
=
0
2
n
‍
ξ
i
L
i
*
(
x
)
,
ψ
k
,
n
(
x
)
)
,
where u
N
n
(
x
)
=
∑
k
=
0
N
-
2
n
-
1
v
k
n
ϕ
k
,
n
(
x
),  ϕ
k
,
n
(
x
) and ψ
k
,
n
(
x
) are defined as in (48) and (49), respectively.
Substitution of formulae (19), (50), and (52) into (62) yields
(63)
(
∑
s
=
0
N
‍
e
s
L
s
*
(
x
)
+
∑
q
=
1
2
n
+
1
‍
η
2
n
-
q
+
1
∑
s
=
0
N
+
q
‍
t
s
,
q
L
s
*
(
x
)
,
∑
ℓ
=
0
4
n
+
2
‍
w
-
ℓ
,
n
(
k
)
L
k
-
ℓ
+
2
n
+
1
*
(
x
)
)
=
(
p
(
x
)
+
∑
i
=
0
2
n
‍
ξ
i
L
i
*
(
x
)
,
∑
ℓ
=
0
4
n
+
2
‍
w
-
ℓ
,
n
(
k
)
L
k
-
ℓ
+
2
n
+
1
*
(
x
)
)
.
The constants of integration ξ
i
,
0
≤
i
≤
2
n would disappear if we take k
≥
2
n
+
1, and therefore the application of the orthogonality relation (15) yields
(64)
(
b
-
a
2
k
+
1
)
(
e
k
+
∑
q
=
1
2
n
+
1
‍
η
2
n
+
1
-
q
t
k
,
q
)
=
p
k
n
,
k
=
2
n
+
1,2
n
+
2
,
…
,
N
,
which is equivalent to
(65)
e
k
+
∑
q
=
1
2
n
+
1
‍
η
2
n
+
1
-
q
t
k
,
q
=
p
k
*
n
k
=
2
n
+
1,2
n
+
2
,
…
,
N
,
(66)
p
k
*
n
=
(
2
k
+
1
)
p
k
n
(
b
-
a
)
.
The system of linear equation (65) in turn may be written in the following matrix form:
(67)
(
A
-
n
+
∑
q
=
1
2
n
+
1
‍
η
2
n
-
q
+
1
B
-
q
,
n
)
v
n
=
p
*
n
,
and this completes the proof of Theorem 9.


### 3.3. Structure and Complexities of the Two Matrix Systems (36) and (58)

The structures of the coefficient matricesA
n
,
B
2
n
-
i
+
1
,
n
(
0
≤
i
≤
2
n
)
,
A
-
n, B
-
q
,
n
(
1
≤
q
≤
2
n
) and hence the structures of the two combined matrices D
n
=
A
n
+
∑
i
=
0
2
n
‍
η
i
B
2
n
-
i
+
1
,
n and D
-
n
=
A
-
n
+
∑
q
=
1
2
n
+
1
η
2
n
-
q
+
1
B
-
q
,
n, which appear in the two linear systems (36) and (58), will be discussed in this section. Also, the influence of such structures on the efficiency of the solution of these two matrix systems will be discussed.With respect to the two matricesA
n and A
-
n, they are always nonsingular special upper band triangular of bandwidth (
4
n
+
2
), ∀
n
≥
1. Therefore, it is worth noting here that the case whichcorresponds to η
i
=
0
,
0
≤
i
≤
2
n, leads to linear systems with special nonsingular upper triangular matrices. The results for such case are summarized in the following two important corollaries.Corollary 10.
Ifη
i
=
0
,
0
≤
i
≤
2
n, then the system (36) takes the form A
n
v
n
=
p
n, where A
n is an upper triangular matrix whose solution can be obtained directly by the backward substitution
(68)
v
k
n
=
p
k
+
2
n
+
1
n
-
∑
j
=
k
+
1
k
+
4
n
+
2
a
k
+
2
n
+
1
,
j
+
2
n
+
1
n
v
j
n
a
k
+
2
n
+
1
,
k
+
2
n
+
1
n
,
k
=
0,1
,
…
,
N
-
2
n
-
1
,
where a
k
k
n and a
k
j
n are given by (38) and (39), respectively.Corollary 11.
Ifη
2
n
-
q
+
1
=
0
,
1
≤
q
≤
2
n
+
1, then the system (58) takes the form A
-
n
v
n
=
p
*
n,    where A
-
n is an upper triangular matrix whose solution can be obtained directly by the backward substitution
(69)
v
k
n
=
p
k
+
2
n
+
1
*
n
-
∑
j
=
k
+
1
k
+
4
n
+
2
a
-
k
+
2
n
+
1
,
j
+
2
n
+
1
n
v
j
n
a
-
k
+
2
n
+
1
,
k
+
2
n
+
1
n
,
k
=
0,1
,
…
,
N
-
2
n
-
1
,
where a
-
k
k
n and a
-
k
j
n are given by (59) and (60), respectively.Each of the matricesB
q
,
n and B
-
q
,
n
(
1
≤
q
≤
2
n
+
1
) is a band matrix whose total number of nonzero diagonals upper the main diagonal is 4
n
+
q
+
2, while the total number of nonzero diagonals lower the main diagonal is q. Thus, the coefficient matrices D
n
=
A
n
+
∑
q
=
1
2
n
+
1
‍
η
2
n
-
q
+
1
B
q
,
n and D
-
n
=
A
-
n
+
∑
q
=
1
2
n
+
1
η
2
n
-
q
+
1
B
-
q
,
n are band whose total number of nonzero diagonals upper the main diagonal does not exceed 6
n
+
3 and the total number of nonzero diagonals lower the main diagonal does not exceed 2
n
+
1. These special structures of D
n and D
-
n simplify greatly the solutions of the two linear systems (36) and (58). The two systems in such case can be factorized by L
U-decomposition, and the number of operations necessary to construct this factorization is of order 12
(
N
-
2
n
-
1
)
(
2
n
+
1
)
2 (see Stewart [28]).


### 3.4. Condition Number

Whenever spectral methods are used for solving the(
2
n
+
1
)th-order equations, one should be concerned with round-off errors caused by potentially large condition numbers. However, the LDPGM presented in this paper leads to systems with small condition numbers. For LDPGM, the two linear systems which resulted from the integrated form of the equation (
u
(
2
n
+
1
)
(
x
)
=
f
(
x
)
) using the two choices of basis functions are given, respectively, by A
n
v
n
=
p
n and A
-
n
v
n
=
p
*
n, where the matrices A
n and A
-
n
,
n
≥
1 are upper triangular matrices whose diagonal elements are given by (38) and (59), respectively. Thus, for all n
≥
1, we note that the condition number of the matrix A
n behaves like O
(
k
) for large values of k, while the condition number of the matrix D
n is independent of k. This means that the matrix D
n is well conditioned. Hence, the propagation of round-off errors should not be very significant.Table1 illustrates the condition numbers for the two matrices A
n and D
n
=
A
n
+
∑
q
=
1
2
n
+
1
η
2
n
-
q
+
1
B
q
,
n in (36) for some values of the parameter N and (
a
,
b
)
=
(
-
1,1
), while Table 2 illustrates the condition numbers for the two matrices A
-
n and D
-
n
=
A
-
n
+
∑
q
=
1
2
n
+
1
η
2
n
-
q
+
1
B
-
q
,
n in (58) (
1
≤
n
≤
3
) for the same values of N and in the same interval.Table 1
Condition numbers for the matricesA
n
,
D
n.
N
n
Cond (A
n)
(
Cond
(
A
n
)
)
/
N
Cond (D
n)
(
Cond
(
D
n
)
)
/
N
12
1
2.347
1.956 ·1
0
-
1
3.120
2.600 ·1
0
-
1
24
4.387
1.828 ·1
0
-
1
5.461
2.275 ·1
0
-
1
32
5.754
1.798 ·1
0
-
1
7.039
2.199 ·1
0
-
1
48
8.493
1.769 ·1
0
-
1
10.191
2.123 ·1
0
-
1
64
1.123
1.755 ·1
0
-
1
13.333
2.083 ·1
0
-
1
12
2
1.379
1.149 ·1
0
-
1
2.263
1.886 ·1
0
-
1
24
1.756
7.315 ·1
0
-
2
2.569
1.071 ·1
0
-
1
32
2.218
6.932 ·1
0
-
2
3.147
9.836 ·1
0
-
2
48
3.160
6.584 ·1
0
-
2
4.349
9.059 ·1
0
-
2
64
4.109
6.421 ·1
0
-
2
5.564
8.694 ·1
0
-
2
12
3
2.657
2.214 ·1
0
-
1
3.208
2.673 ·1
0
-
1
24
2.780
1.159 ·1
0
-
1
3.683
1.535 ·1
0
-
1
32
2.780
8.689 ·1
0
-
2
3.683
1.151 ·1
0
-
1
48
2.780
5.793 ·1
0
-
2
3.683
7.673 ·1
0
-
2
64
2.780
4.344 ·1
0
-
2
3.683
5.755 ·1
0
-
2Table 2
Condition numbers for the matricesA
-
n
,
D
-
n.
N
n
Cond (A
-
n)
Cond (D
-
n)
n
Cond (A
-
n)
Cond (D
-
n)
n
Cond (A
-
n)
Cond (D
-
n)
12
1
2.781
10.003
2
3.127
8.327
3
3.127
6.759
24
2.996
10.152
3.620
9.105
4.026
8.866
32
3.048
10.152
3.735
9.107
4.224
8.899
48
3.099
10.152
3.847
9.107
4.414
8.899
64
3.124
10.152
3.902
9.106
4.506
8.899


### 3.5. Nonhomogeneous Boundary Conditions

If we consider the differential equation(70)
u
(
2
n
+
1
)
(
x
)
+
∑
i
=
0
2
n
‍
η
i
u
(
i
)
(
x
)
=
f
(
x
)
,
x
∈
(
a
,
b
)
,
n
≥
1
,
governed by the nonhomogeneous boundary conditions
(71)
u
(
j
)
(
a
)
=
α
j
,
u
(
j
)
(
b
)
=
β
j
,
u
(
n
)
(
a
)
=
γ
,
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
j
=
0,1
,
…
,
n
-
1
,
one can easily show that the differential equation (70) with its nonhomogeneous boundary conditions (71) can be transformed—by using a suitable transformation—to a differential equation governed by homogeneous boundary conditions, but details will not be given here and the interested reader is referred to Doha and Abd-Elhameed [19].


## 3.1. The First Choice of Basis Functions

First, we consider the case[
a
,
b
]
=
[
-
1,1
] and set
(26)
θ
k
,
n
(
x
)
=
L
k
(
x
)
+
∑
m
=
1
2
n
+
1
‍
d
m
,
k
L
k
+
m
(
x
)
,
k
=
0,1
,
2
,
…
,
N
-
2
n
-
1
,
n
≥
1
,
θ
¯
k
,
n
(
x
)
=
L
k
(
x
)
+
∑
m
=
1
2
n
+
1
‍
d
-
m
,
k
L
k
+
m
(
x
)
,
k
=
0,1
,
2
,
…
,
N
-
2
n
-
1
,
n
≥
1
.
We choose the coefficients {
d
m
,
k
} and {
d
-
m
,
k
} such that θ
k
,
n
(
x
)
∈
Y
k
+
2
n
+
1 and θ
¯
k
,
n
(
x
)
∈
Y
-
k
+
2
n
+
1, respectively. The boundary conditions θ
k
,
n
(
j
)
(
a
)
=
θ
k
,
n
(
j
)
(
b
)
=
θ
k
,
n
(
n
)
(
a
)
=
0
,
j
=
0,1
,
…
,
n
-
1 lead to the following system of equations:
(27)
∑
m
=
1
2
n
+
1
‍
(
-
1
)
m
d
m
,
k
=
-
1
,
∑
m
=
1
2
n
+
1
‍
(
-
1
)
m
[
∏
s
=
0
q
-
1
‍
(
k
+
m
-
s
)
(
k
+
m
+
s
+
1
)
]
×
d
m
,
k
=
-
∏
s
=
0
q
-
1
‍
(
k
-
s
)
(
k
+
s
+
1
)
,
q
=
1,2
,
…
,
n
,
n
≥
1
,
∑
m
=
1
2
n
+
1
‍
d
m
,
k
=
-
1
,
∑
m
=
1
2
n
+
1
‍
∏
s
=
0
q
-
1
‍
(
k
+
m
-
s
)
(
k
+
m
+
s
+
1
)
d
m
,
k
=
-
∏
s
=
0
q
-
1
‍
(
k
-
s
)
(
k
+
s
+
1
)
,
q
=
1,2
,
…
,
n
-
1
,
n
≥
1
.
The determinant of the above system of linear equations is different from zero; hence, {
d
m
,
k
} can be uniquely determined to give
(28)
d
m
,
k
=
(
-
1
)
m
{
(
(
-
1
)
m
/
2
(
n
m
2
)
(
k
+
m
+
1
2
)
×
Γ
(
k
+
m
+
1
2
)
Γ
(
k
+
n
+
3
2
)
(
n
m
2
)
)
×
(
Γ
(
k
+
3
2
)
Γ
(
k
+
n
+
m
+
3
2
)
)
-
1
,
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
f
m
even
,
(
(
-
1
)
(
m
+
1
)
/
2
(
n
m
-
1
2
)
(
k
+
m
+
1
2
)
×
Γ
(
k
+
m
2
+
1
)
Γ
(
k
+
n
+
3
2
)
(
n
m
2
)
)
×
(
Γ
(
k
+
3
2
)
Γ
(
k
+
n
+
m
2
+
2
)
)
-
1
,
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
m
odd
.
Similarly, it can be easily shown that {
d
-
m
,
k
} are given by
(29)
d
-
m
,
k
=
(
-
1
)
m
d
m
,
k
,
m
=
1,2
,
…
,
2
n
+
1
.
Second, if we replace x in (26) by (
(
2
x
-
a
-
b
)
/
(
b
-
a
)
), for a
≤
x
≤
b, and if we define
(30)
θ
k
,
n
(
2
x
-
a
-
b
b
-
a
)
=
ϕ
k
,
n
(
x
)
,
θ
-
k
,
n
(
2
x
-
a
-
b
b
-
a
)
=
ψ
k
,
n
(
x
)
,
x
∈
[
a
,
b
]
,
then it is obvious that the basis functions and their dual are given, respectively, by
(31)
ϕ
k
,
n
(
x
)
=
∑
m
=
0
2
n
+
1
‍
d
m
,
k
L
k
+
m
*
(
x
)
,
(32)
ψ
k
,
n
(
x
)
=
∑
m
=
0
2
n
+
1
‍
d
-
m
,
k
L
k
+
m
*
(
x
)
,
where d
m
,
k and d
-
m
,
k are as given in (28) and (29), respectively.Now it is clear that (25) is equivalent to
(33)
(
u
N
n
(
x
)
,
ψ
k
,
n
(
x
)
)
+
∑
i
=
0
2
n
‍
η
i
(
∫
(
2
n
-
i
+
1
)
u
N
n
(
x
)
(
d
x
)
(
2
n
-
i
+
1
)
,
ψ
k
,
n
(
x
)
)
=
(
p
(
x
)
+
∑
i
=
0
2
n
‍
b
i
L
i
*
(
x
)
,
ψ
k
,
n
(
x
)
)
.
If we take k
≥
2
n
+
1 in (33), then the constants b
i
,
0
≤
i
≤
2
n, would disappear, and then we get
(34)
(
u
N
n
(
x
)
,
ψ
k
,
n
(
x
)
)
+
∑
i
=
0
2
n
‍
η
i
(
∫
(
2
n
-
i
+
1
)
u
N
n
(
x
)
(
d
x
)
(
2
n
-
i
+
1
)
,
ψ
k
,
n
(
x
)
)
=
(
p
(
x
)
,
ψ
k
,
n
(
x
)
)
,
2
n
+
1
≤
k
≤
N
.
If we denote
(35)
p
k
n
=
(
p
(
x
)
,
ψ
k
,
n
(
x
)
)
,
p
n
=
(
p
2
n
+
1
n
,
p
2
n
+
2
n
,
…
,
p
N
n
)
T
,
u
N
n
(
x
)
=
∑
m
=
0
N
-
2
n
-
1
‍
v
m
n
ϕ
m
,
n
(
x
)
,
v
n
=
(
v
0
n
,
v
1
n
,
…
,
v
N
-
2
n
-
1
n
)
T
,
A
n
=
(
a
k
j
n
)
2
n
+
1
≤
k
,
j
≤
N
,
B
2
n
-
i
+
1
,
n
=
(
b
k
j
2
n
-
i
+
1
,
n
)
2
n
+
1
≤
k
,
j
≤
N
,
0
≤
i
≤
2
n
,
then (34) is equivalent to the following matrix system:
(36)
(
A
n
+
∑
i
=
0
2
n
‍
η
i
B
2
n
-
i
+
1
,
n
)
v
n
=
p
n
,
where the nonzero elements of the matrices A
n and B
2
n
-
i
+
1
,
n
(
0
≤
i
≤
2
n
) are given explicitly in the following theorem.Theorem 7.
If the basis functionsϕ
k
,
n
(
x
) and their dual ψ
k
,
n
(
x
) are taken as in (31) and (32), respectively, and if we denote a
k
j
n
=
(
ϕ
j
-
2
n
-
1
,
n
(
x
)
,
ψ
k
,
n
(
x
)
) and b
k
j
2
n
-
i
+
1
,
n
=
(
∫
(
2
n
-
i
+
1
)
ϕ
j
-
2
n
-
1
,
n
(
x
)
(
d
x
)
(
2
n
-
i
+
1
)
,
ψ
k
,
n
(
x
)
)
,
0
≤
i
≤
2
n, then
(37)
Y
N
+
2
n
+
1
=
s
p
a
n
{
ϕ
0
,
n
(
x
)
,
ϕ
1
,
n
(
x
)
,
…
,
ϕ
N
,
n
(
x
)
}
,
Y
-
N
+
2
n
+
1
=
s
p
a
n
{
ψ
0
,
n
(
x
)
,
ψ
1
,
n
(
x
)
,
…
,
ψ
N
,
n
(
x
)
}
,
and the nonzero elements of the matrices A
n
,
B
2
n
-
i
+
1
,
n
(
0
≤
i
≤
2
n
) are given explicitly by
(38)
a
k
k
n
=
(
-
1
)
n
+
1
(
b
-
a
)
Γ
2
(
k
-
n
+
(
1
/
2
)
)
2
Γ
(
k
+
(
3
/
2
)
)
Γ
(
k
-
2
n
+
(
1
/
2
)
)
,
(39)
a
k
j
n
=
(
-
1
)
j
-
k
-
1
(
b
-
a
)
×
∑
m
=
0
2
n
+
1
‍
(
-
1
)
m
d
m
,
j
-
2
n
-
1
d
j
-
k
+
m
-
2
n
-
1
,
k
(
2
j
+
2
m
-
4
n
-
1
)
,
aaaa
1
≤
j
-
k
≤
4
n
+
2
,
(40)
b
k
j
2
n
-
i
+
1
,
n
=
(
-
1
)
j
-
k
-
i
(
b
-
a
)
2
n
-
i
+
2
2
2
n
-
i
+
1
×
∑
m
=
0
2
n
+
1
‍
∑
ℓ
=
0
2
n
-
i
+
1
(
(
(
-
1
)
m
d
m
,
j
-
2
n
-
1
d
j
+
m
-
i
-
2
ℓ
-
k
,
k
h
h
h
h
h
h
h
h
h
h
h
h
h
h
×
r
ℓ
,
j
-
2
n
+
m
-
1
,
2
n
-
i
+
1
)
h
h
h
h
h
h
h
h
h
h
h
h
h
×
(
2
j
+
2
m
-
2
i
-
4
ℓ
+
1
)
-
1
)
,
hhhhhhhhhhhhhh
i
-
2
n
-
1
≤
j
-
k
≤
6
n
-
i
+
3
,
where r
ℓ
,
j
,
q and d
m
,
j are, respectively, defined as in (5) and (28).Proof .
We choose the basis functionsϕ
k
,
n
(
x
) and their dual ψ
k
,
n
(
x
) such that ϕ
k
,
n
(
x
)
∈
Y
N
+
2
n
+
1 and ψ
k
,
n
(
x
)
∈
Y
-
N
+
2
n
+
1 for k
=
0,1
,
…
,
N. Moreover, it is clear that {
ϕ
k
,
n
(
x
)
} and {
ψ
k
,
n
(
x
)
} are linearly independent and the dimension of each of Y
N
+
2
n
+
1 and  Y
-
N
+
2
n
+
1 is equal to (
N
+
1
). Hence,
(41)
Y
N
+
2
n
+
1
=
span
⁡
{
ϕ
0
,
n
(
x
)
,
ϕ
1
,
n
(
x
)
,
…
,
ϕ
N
,
n
(
x
)
}
,
Y
-
N
+
2
n
+
1
=
span
⁡
{
ψ
0
,
n
(
x
)
,
ψ
1
,
n
(
x
)
,
…
,
ψ
N
,
n
(
x
)
}
.
The nonzero elements (
a
k
j
n
) for 2
n
+
1
≤
k
,
j
≤
N, can be obtained by making use of formulae (31) and (32). Now, a
k
j
n is given by
(42)
a
k
j
n
=
(
∑
m
=
0
2
n
+
1
‍
d
m
,
j
-
2
n
-
1
L
j
-
2
n
+
m
-
1
*
(
x
)
,
∑
p
=
0
2
n
+
1
‍
(
-
1
)
p
d
p
,
k
L
k
+
p
*
(
x
)
)
=
∑
m
=
0
2
n
+
1
∑
p
=
0
2
n
+
1
(
-
1
)
p
d
m
,
j
-
2
n
-
1
d
p
,
k
(
L
j
-
2
n
+
m
-
1
*
(
x
)
,
L
k
+
p
*
(
x
)
)
,
which in turn, with the aid of the orthogonality relation (15), yields
(43)
a
k
j
n
=
(
-
1
)
j
-
k
-
1
(
b
-
a
)
×
∑
m
=
0
2
n
+
1
‍
(
-
1
)
m
d
m
,
j
-
2
n
-
1
d
j
-
k
+
m
-
2
n
-
1
,
k
(
2
j
+
2
m
-
4
n
-
1
)
,
which proves relation (39). From (43) and (28), it is not difficult to prove that
(44)
a
k
k
n
=
(
-
1
)
n
+
1
(
b
-
a
)
Γ
2
(
k
-
n
+
(
1
/
2
)
)
2
Γ
(
k
+
(
3
/
2
)
)
Γ
(
k
-
2
n
+
(
1
/
2
)
)
.
To prove relation (40), we have, for 0
≤
i
≤
2
n,
(45)
b
k
j
2
n
-
i
+
1
,
n
=
(
∫
(
2
n
-
i
+
1
)
ϕ
j
-
2
n
-
1
,
n
(
x
)
(
d
x
)
(
2
n
-
i
+
1
)
,
ψ
k
,
n
(
x
)
)
=
(
∑
m
=
0
2
n
+
1
d
m
,
j
-
2
n
-
1
J
j
-
2
n
+
m
-
1
(
2
n
-
i
+
1
)
(
x
)
,
c
c
i
i
∑
p
=
0
2
n
+
1
‍
(
-
1
)
p
d
p
,
k
L
k
+
p
*
(
x
)
)
.
Making use of Theorem 5 enables one to write
(46)
J
j
-
2
n
+
m
-
1
(
2
n
-
i
+
1
)
(
x
)
=
(
b
-
a
2
)
(
2
n
-
i
+
1
)
×
∑
ℓ
=
0
2
n
-
i
+
1
r
ℓ
,
j
-
2
n
+
m
-
1,2
n
-
i
+
1
×
L
j
+
m
-
i
-
2
ℓ
*
(
x
)
+
π
-
2
n
-
i
(
x
)
,
where r
j
,
k
,
q is defined as in (5) and π
-
2
n
-
i is a polynomial in x of degree (
2
n
-
i
) at most.
This, with the orthogonality relation (15), yields
(47)
b
k
j
2
n
-
i
+
1
,
n
=
(
-
1
)
j
-
k
-
i
(
b
-
a
)
2
n
-
i
+
2
2
2
n
-
i
+
1
×
∑
m
=
0
2
n
+
1
∑
ℓ
=
0
2
n
-
i
+
1
(
(
(
-
1
)
m
d
m
,
j
-
2
n
-
1
d
j
+
m
-
i
-
2
ℓ
-
k
,
k
‍
aaaaaaaaaaaaaaaa
a
a
×
r
ℓ
,
j
-
2
n
+
m
-
1,2
n
-
i
+
1
)
f
f
f
f
f
f
f
f
f
f
f
f
f
f
×
(
2
j
+
2
m
-
2
i
-
4
ℓ
+
1
)
-
1
)
,
which completes the proof of Theorem 7.


## 3.2. The Second Choice of Basis Functions

As a second choice ofϕ
k
,
n
(
x
) and ψ
k
,
n
(
x
), we write
(48)
ϕ
k
,
n
(
x
)
=
(
2
b
-
a
)
2
n
+
1
(
x
-
a
)
n
+
1
(
b
-
x
)
n
L
k
*
(
x
)
,
(49)
ψ
k
,
n
(
x
)
=
(
2
b
-
a
)
2
n
+
1
(
x
-
a
)
n
(
b
-
x
)
n
+
1
L
k
*
(
x
)
,
which automatically fulfill the boundary conditions (21) and their dual conditions, respectively.The following lemma is of fundamental importance in what follows.Lemma 8.
For arbitrary constantsv
k
n, one has
(50)
∑
k
=
0
N
-
2
n
-
1
‍
v
k
n
ϕ
k
,
n
(
x
)
=
∑
k
=
0
N
‍
e
k
L
k
*
(
x
)
,
where
(51)
e
k
=
∑
s
=
0
4
n
+
2
‍
w
s
,
n
(
k
-
2
n
+
s
-
1
)
v
k
-
2
n
+
s
-
1
n
.
Moreover,
(52)
∫
(
q
)
(
∑
k
=
0
N
-
2
n
-
1
‍
v
k
n
ϕ
k
,
n
(
x
)
)
(
d
x
)
(
q
)
=
∑
k
=
0
N
+
q
‍
t
k
,
q
L
k
*
(
x
)
+
ρ
q
-
1
(
x
)
,
1
≤
q
≤
2
n
+
1
,
where
(53)
t
k
,
q
=
(
b
-
a
2
)
q
×
∑
j
=
0
q
‍
∑
s
=
0
4
n
+
2
w
s
,
n
(
k
-
2
n
+
s
+
2
j
-
q
-
1
)
×
r
j
,
k
-
q
+
2
j
,
q
v
k
-
2
n
+
s
+
2
j
-
q
-
1
n
,
and w
s
,
n
(
k
) is defined as in (13) and ρ
q
-
1
(
x
) is a polynomial of degree (
q
-
1
) at most.Proof.
The first part of this lemma can be directly proved with the aid of Lemma4. To prove the second part, we integrate both sides of (50) q times, 1
≤
q
≤
2
n
+
1, and, after making use of formula (17), we obtain
(54)
∫
(
q
)
(
∑
k
=
0
N
-
2
n
-
1
‍
v
k
n
ϕ
k
,
n
(
x
)
)
(
d
x
)
(
q
)
=
(
b
-
a
2
)
q
∑
k
=
0
N
‍
e
k
∑
j
=
0
q
‍
r
j
,
k
,
q
L
k
+
q
-
2
j
*
(
x
)
+
ρ
q
-
1
,
which may be written in the form
(55)
∫
(
q
)
(
∑
k
=
0
N
-
2
n
-
1
‍
v
k
n
ϕ
k
,
n
(
x
)
)
(
d
x
)
(
q
)
=
∑
k
=
0
N
+
q
‍
t
k
,
q
L
k
*
(
x
)
+
ρ
q
-
1
,
where
(56)
t
k
,
q
=
(
b
-
a
2
)
q
∑
j
=
0
q
‍
e
k
-
q
+
2
j
r
j
,
k
-
q
+
2
j
,
q
.
Now, making use of relation (51) enables one to write t
k
,
q in the form
(57)
t
k
,
q
=
(
b
-
a
2
)
q
×
∑
j
=
0
q
‍
∑
s
=
0
4
n
+
2
w
s
,
n
(
k
-
2
n
+
s
+
2
j
-
q
-
1
)
×
r
j
,
k
-
q
+
2
j
,
q
v
k
-
2
n
+
s
+
2
j
-
q
-
1
n
,
and this completes the proof of Lemma 8.Theorem 9.
Ifu
N
n
(
x
)
=
∑
k
=
0
N
-
2
n
-
1
v
k
n
ϕ
k
,
n
(
x
) is the dual Petrov-Galerkin approximation to (20) and (21), then the expansion coefficients {
v
k
n
:
k
=
0,1
,
…
,
N
-
2
n
-
1
} satisfy the matrix system
(58)
(
A
-
n
+
∑
q
=
1
2
n
+
1
‍
η
2
n
-
q
+
1
B
-
q
,
n
)
v
n
=
p
*
n
,
where the nonzero elements of the matrices A
-
n and B
-
q
,
n
,
1
≤
q
≤
2
n
+
1 are given by
(59)
a
-
k
k
n
=
k
!
Γ
(
k
-
2
n
-
(
1
/
2
)
)
2
2
n
+
1
(
k
-
2
n
-
1
)
!
Γ
(
k
+
(
1
/
2
)
)
,
(60)
a
-
k
j
n
=
w
j
-
k
,
n
(
j
-
2
n
-
1
)
,
k
≤
j
≤
k
+
4
n
+
2
,
(61)
b
-
k
j
q
,
n
=
(
b
-
a
2
)
q
∑
s
=
0
q
‍
w
j
-
k
+
q
-
2
s
,
n
(
j
-
2
n
-
1
)
r
s
,
k
-
q
+
2
s
,
q
,
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
,
k
-
q
≤
j
≤
k
+
4
n
+
q
+
2
,
where r
ℓ
,
j
,
q and w
s
,
n are, respectively, defined as in (5) and (13).Proof.
If we apply the LDPGM to (20), then we have
(62)
(
u
N
n
(
x
)
+
∑
q
=
1
2
n
+
1
‍
η
2
n
+
1
-
q
∫
(
q
)
u
N
n
(
d
x
)
(
q
)
,
ψ
k
,
n
(
x
)
)
=
(
p
(
x
)
+
∑
i
=
0
2
n
‍
ξ
i
L
i
*
(
x
)
,
ψ
k
,
n
(
x
)
)
,
where u
N
n
(
x
)
=
∑
k
=
0
N
-
2
n
-
1
v
k
n
ϕ
k
,
n
(
x
),  ϕ
k
,
n
(
x
) and ψ
k
,
n
(
x
) are defined as in (48) and (49), respectively.
Substitution of formulae (19), (50), and (52) into (62) yields
(63)
(
∑
s
=
0
N
‍
e
s
L
s
*
(
x
)
+
∑
q
=
1
2
n
+
1
‍
η
2
n
-
q
+
1
∑
s
=
0
N
+
q
‍
t
s
,
q
L
s
*
(
x
)
,
∑
ℓ
=
0
4
n
+
2
‍
w
-
ℓ
,
n
(
k
)
L
k
-
ℓ
+
2
n
+
1
*
(
x
)
)
=
(
p
(
x
)
+
∑
i
=
0
2
n
‍
ξ
i
L
i
*
(
x
)
,
∑
ℓ
=
0
4
n
+
2
‍
w
-
ℓ
,
n
(
k
)
L
k
-
ℓ
+
2
n
+
1
*
(
x
)
)
.
The constants of integration ξ
i
,
0
≤
i
≤
2
n would disappear if we take k
≥
2
n
+
1, and therefore the application of the orthogonality relation (15) yields
(64)
(
b
-
a
2
k
+
1
)
(
e
k
+
∑
q
=
1
2
n
+
1
‍
η
2
n
+
1
-
q
t
k
,
q
)
=
p
k
n
,
k
=
2
n
+
1,2
n
+
2
,
…
,
N
,
which is equivalent to
(65)
e
k
+
∑
q
=
1
2
n
+
1
‍
η
2
n
+
1
-
q
t
k
,
q
=
p
k
*
n
k
=
2
n
+
1,2
n
+
2
,
…
,
N
,
(66)
p
k
*
n
=
(
2
k
+
1
)
p
k
n
(
b
-
a
)
.
The system of linear equation (65) in turn may be written in the following matrix form:
(67)
(
A
-
n
+
∑
q
=
1
2
n
+
1
‍
η
2
n
-
q
+
1
B
-
q
,
n
)
v
n
=
p
*
n
,
and this completes the proof of Theorem 9.


## 3.3. Structure and Complexities of the Two Matrix Systems (36) and (58)

The structures of the coefficient matricesA
n
,
B
2
n
-
i
+
1
,
n
(
0
≤
i
≤
2
n
)
,
A
-
n, B
-
q
,
n
(
1
≤
q
≤
2
n
) and hence the structures of the two combined matrices D
n
=
A
n
+
∑
i
=
0
2
n
‍
η
i
B
2
n
-
i
+
1
,
n and D
-
n
=
A
-
n
+
∑
q
=
1
2
n
+
1
η
2
n
-
q
+
1
B
-
q
,
n, which appear in the two linear systems (36) and (58), will be discussed in this section. Also, the influence of such structures on the efficiency of the solution of these two matrix systems will be discussed.With respect to the two matricesA
n and A
-
n, they are always nonsingular special upper band triangular of bandwidth (
4
n
+
2
), ∀
n
≥
1. Therefore, it is worth noting here that the case whichcorresponds to η
i
=
0
,
0
≤
i
≤
2
n, leads to linear systems with special nonsingular upper triangular matrices. The results for such case are summarized in the following two important corollaries.Corollary 10.
Ifη
i
=
0
,
0
≤
i
≤
2
n, then the system (36) takes the form A
n
v
n
=
p
n, where A
n is an upper triangular matrix whose solution can be obtained directly by the backward substitution
(68)
v
k
n
=
p
k
+
2
n
+
1
n
-
∑
j
=
k
+
1
k
+
4
n
+
2
a
k
+
2
n
+
1
,
j
+
2
n
+
1
n
v
j
n
a
k
+
2
n
+
1
,
k
+
2
n
+
1
n
,
k
=
0,1
,
…
,
N
-
2
n
-
1
,
where a
k
k
n and a
k
j
n are given by (38) and (39), respectively.Corollary 11.
Ifη
2
n
-
q
+
1
=
0
,
1
≤
q
≤
2
n
+
1, then the system (58) takes the form A
-
n
v
n
=
p
*
n,    where A
-
n is an upper triangular matrix whose solution can be obtained directly by the backward substitution
(69)
v
k
n
=
p
k
+
2
n
+
1
*
n
-
∑
j
=
k
+
1
k
+
4
n
+
2
a
-
k
+
2
n
+
1
,
j
+
2
n
+
1
n
v
j
n
a
-
k
+
2
n
+
1
,
k
+
2
n
+
1
n
,
k
=
0,1
,
…
,
N
-
2
n
-
1
,
where a
-
k
k
n and a
-
k
j
n are given by (59) and (60), respectively.Each of the matricesB
q
,
n and B
-
q
,
n
(
1
≤
q
≤
2
n
+
1
) is a band matrix whose total number of nonzero diagonals upper the main diagonal is 4
n
+
q
+
2, while the total number of nonzero diagonals lower the main diagonal is q. Thus, the coefficient matrices D
n
=
A
n
+
∑
q
=
1
2
n
+
1
‍
η
2
n
-
q
+
1
B
q
,
n and D
-
n
=
A
-
n
+
∑
q
=
1
2
n
+
1
η
2
n
-
q
+
1
B
-
q
,
n are band whose total number of nonzero diagonals upper the main diagonal does not exceed 6
n
+
3 and the total number of nonzero diagonals lower the main diagonal does not exceed 2
n
+
1. These special structures of D
n and D
-
n simplify greatly the solutions of the two linear systems (36) and (58). The two systems in such case can be factorized by L
U-decomposition, and the number of operations necessary to construct this factorization is of order 12
(
N
-
2
n
-
1
)
(
2
n
+
1
)
2 (see Stewart [28]).


## 3.4. Condition Number

Whenever spectral methods are used for solving the(
2
n
+
1
)th-order equations, one should be concerned with round-off errors caused by potentially large condition numbers. However, the LDPGM presented in this paper leads to systems with small condition numbers. For LDPGM, the two linear systems which resulted from the integrated form of the equation (
u
(
2
n
+
1
)
(
x
)
=
f
(
x
)
) using the two choices of basis functions are given, respectively, by A
n
v
n
=
p
n and A
-
n
v
n
=
p
*
n, where the matrices A
n and A
-
n
,
n
≥
1 are upper triangular matrices whose diagonal elements are given by (38) and (59), respectively. Thus, for all n
≥
1, we note that the condition number of the matrix A
n behaves like O
(
k
) for large values of k, while the condition number of the matrix D
n is independent of k. This means that the matrix D
n is well conditioned. Hence, the propagation of round-off errors should not be very significant.Table1 illustrates the condition numbers for the two matrices A
n and D
n
=
A
n
+
∑
q
=
1
2
n
+
1
η
2
n
-
q
+
1
B
q
,
n in (36) for some values of the parameter N and (
a
,
b
)
=
(
-
1,1
), while Table 2 illustrates the condition numbers for the two matrices A
-
n and D
-
n
=
A
-
n
+
∑
q
=
1
2
n
+
1
η
2
n
-
q
+
1
B
-
q
,
n in (58) (
1
≤
n
≤
3
) for the same values of N and in the same interval.Table 1
Condition numbers for the matricesA
n
,
D
n.
N
n
Cond (A
n)
(
Cond
(
A
n
)
)
/
N
Cond (D
n)
(
Cond
(
D
n
)
)
/
N
12
1
2.347
1.956 ·1
0
-
1
3.120
2.600 ·1
0
-
1
24
4.387
1.828 ·1
0
-
1
5.461
2.275 ·1
0
-
1
32
5.754
1.798 ·1
0
-
1
7.039
2.199 ·1
0
-
1
48
8.493
1.769 ·1
0
-
1
10.191
2.123 ·1
0
-
1
64
1.123
1.755 ·1
0
-
1
13.333
2.083 ·1
0
-
1
12
2
1.379
1.149 ·1
0
-
1
2.263
1.886 ·1
0
-
1
24
1.756
7.315 ·1
0
-
2
2.569
1.071 ·1
0
-
1
32
2.218
6.932 ·1
0
-
2
3.147
9.836 ·1
0
-
2
48
3.160
6.584 ·1
0
-
2
4.349
9.059 ·1
0
-
2
64
4.109
6.421 ·1
0
-
2
5.564
8.694 ·1
0
-
2
12
3
2.657
2.214 ·1
0
-
1
3.208
2.673 ·1
0
-
1
24
2.780
1.159 ·1
0
-
1
3.683
1.535 ·1
0
-
1
32
2.780
8.689 ·1
0
-
2
3.683
1.151 ·1
0
-
1
48
2.780
5.793 ·1
0
-
2
3.683
7.673 ·1
0
-
2
64
2.780
4.344 ·1
0
-
2
3.683
5.755 ·1
0
-
2Table 2
Condition numbers for the matricesA
-
n
,
D
-
n.
N
n
Cond (A
-
n)
Cond (D
-
n)
n
Cond (A
-
n)
Cond (D
-
n)
n
Cond (A
-
n)
Cond (D
-
n)
12
1
2.781
10.003
2
3.127
8.327
3
3.127
6.759
24
2.996
10.152
3.620
9.105
4.026
8.866
32
3.048
10.152
3.735
9.107
4.224
8.899
48
3.099
10.152
3.847
9.107
4.414
8.899
64
3.124
10.152
3.902
9.106
4.506
8.899


## 3.5. Nonhomogeneous Boundary Conditions

If we consider the differential equation(70)
u
(
2
n
+
1
)
(
x
)
+
∑
i
=
0
2
n
‍
η
i
u
(
i
)
(
x
)
=
f
(
x
)
,
x
∈
(
a
,
b
)
,
n
≥
1
,
governed by the nonhomogeneous boundary conditions
(71)
u
(
j
)
(
a
)
=
α
j
,
u
(
j
)
(
b
)
=
β
j
,
u
(
n
)
(
a
)
=
γ
,
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
j
=
0,1
,
…
,
n
-
1
,
one can easily show that the differential equation (70) with its nonhomogeneous boundary conditions (71) can be transformed—by using a suitable transformation—to a differential equation governed by homogeneous boundary conditions, but details will not be given here and the interested reader is referred to Doha and Abd-Elhameed [19].


## 4. Numerical Results

In this section, we give some numerical results obtained by using the two algorithms presented in the previous sections.Example 1.
Consider the following third-order one-dimensional BVP:(72)
u
′′′
(
x
)
+
η
2
u
′′
(
x
)
+
η
1
u
′
(
x
)
+
η
0
u
(
x
)
=
f
(
x
)
,
a
a
a
a
a
a
a
a
a
a
u
(
±
1
)
=
u
′
(
-
1
)
=
0
,
where f
(
x
) is chosen such that the exact solution of (72) is u
(
x
)
=
(
1
-
x
2
)
(
1
+
x
)
e
x.Table3 lists the maximum pointwise error E given by |
u
-
u
N
| to the problem (72) of the given example using LDPGM with the two choices of basis functions for various values of N and for some values of the coefficients η
0
,
η
1, and η
2.Table 3
Maximum pointwise errorE for Example 1.
N
η
0
η
1
η
2
LDPG—1st choice
LDPG—2nd choice
18
0
0
0
2.20843
×
1
0
-
14
5.40665
×
1
0
-
15
20
3.06209
×
1
0
-
14
6.58881
×
1
0
-
15
22
7.61484
×
1
0
-
14
3.63132
×
1
0
-
15
18
1
-
1
-
1
1.14394
×
1
0
-
13
5.25079
×
1
0
-
15
20
1.00142
×
1
0
-
13
2.18044
×
1
0
-
15
22
2.17211
×
1
0
-
13
5.40459
×
1
0
-
15
18
16
-
1
6
2
-
1
6
3
1.15044
×
1
0
-
13
2.02084
×
1
0
-
15
20
1.65338
×
1
0
-
14
1.08947
×
1
0
-
14
22
5.91763
×
1
0
-
13
7.53041
×
1
0
-
14Example 2.
Consider the boundary value problem (see Lang and Xu [25] and Siddiqi and Akram [26]):
(73)
u
(
5
)
(
x
)
-
u
(
x
)
=
-
(
15
+
10
x
)
e
x
,
0
≤
x
≤
1
,
u
(
0
)
=
0
,
u
′
(
0
)
=
1
,
u
′′
(
0
)
=
0
,
u
(
1
)
=
0
,
u
′
(
1
)
=
-
e
,
with exact solution u
(
x
)
=
x
(
1
-
x
)
e
x.Table4 lists the maximum pointwise error E given by |
u
-
u
N
| using LDPGM with the two choices of basis functions and for various values of N. In Table 5, we give a comparison between the best errors obtained by our two methods (LDPGM-1st choice and LDPGM-2nd choice), quartic spline method (QSM) in [25], and sextic spline method (SSM) in [26]. This table shows that our methods are more accurate if compared with quartic spline method and sextic spline method illustrated in [25, 26], respectively.Table 4
Maximum pointwise errorE for Example 2 with N
=
14,16,18,20.
N
LDPG—1st choice
LDPG—2nd choice
14
2.66574
×
1
0
-
15
1.36447
×
1
0
-
15
16
4.18619
×
1
0
-
16
1.3787
×
1
0
-
16
18
9.4369
×
1
0
-
16
1.70355
×
1
0
-
16
20
1.28588
×
1
0
-
15
2.01205
×
1
0
-
16
24
5.1337
×
1
0
-
16
1.80926
×
1
0
-
16Table 5
Comparison between different methods for Example2.
Error
LDPG—1st choice
LDPG—2nd choice
QSM in [25]
SSM in [26]
E
4.18619
×
1
0
-
16
1.3787
×
1
0
-
16
1.2331
×
1
0
-
10
5.2812
×
1
0
-
7Example 3.
Consider the linear ninth-order BVP (see Wazwaz [27]):
(74)
u
(
9
)
(
x
)
-
u
(
x
)
=
-
9
e
x
,
0
<
x
<
1
,
u
(
j
)
(
0
)
=
(
1
-
j
)
,
0
≤
j
≤
4
,
u
(
j
)
(
1
)
=
-
j
e
,
0
≤
j
≤
3
,
with theoretical solution u
(
x
)
=
(
1
-
x
)
e
x.In Table6, we list the errors E given by |
u
-
u
N
| for Example 3 for N
=
16 using LDPGM based on the two kinds of basis functions. For the sake of comparison with the results obtained by Wazwaz in [27], the best errors obtained in [27] are listed in column 4 of Table 6. This table shows that our two algorithms are more accurate than the method presented by Wazwaz [27], for the problem considered.Table 6
ErrorE for Example 3 with N
=
16.
x
LDPG—1st choice
LDPG—2nd choice
Method in Wazwaz [27]
0.0
0.000000
0.000000
0.000000
0.1
2.22045
×
1
0
-
16
2.22045
×
1
0
-
16
2.0
×
1
0
-
10
0.2
1.11022
×
1
0
-
16
1.11022
×
1
0
-
16
2.0
×
1
0
-
10
0.3
1.11022
×
1
0
-
16
1.11022
×
1
0
-
16
2.0
×
1
0
-
10
0.4
1.11022
×
1
0
-
16
1.11022
×
1
0
-
16
2.0
×
1
0
-
10
0.5
1.11022
×
1
0
-
16
0.000000
2.0
×
1
0
-
10
0.6
1.11022
×
1
0
-
16
1.11022
×
1
0
-
16
6.0
×
1
0
-
10
0.7
1.11022
×
1
0
-
16
0.000000
1.0
×
1
0
-
9
0.8
0.000000
1.11022
×
1
0
-
16
2.0
×
1
0
-
9
0.9
0.000000
0.000000
3.4
×
1
0
-
9
0.1
2.22045
×
1
0
-
16
2.22045
×
1
0
-
16
0.000000


## 5. Concluding Remarks

We have presented two numerical spectral algorithms for the solution of high odd-order differential equations based on Legendre-dual-Petrov-Galerkin method. The two presented algorithms are very reliable and efficient. The main advantage of our algorithms is that all the resulting systems are band and this of course simplifies the numerical computational efforts required to solve them. The presented numerical results exhibit the high accuracy and efficiency of the proposed algorithms.



---

*Source: 309264-2014-01-27.xml*