Best Least Square Solution of Boundary Value Problems Associated with a System of First Order Matrix DifferentialEquation
The best least square solution of the boundary value problem is constructed via modified QR algorithm and also RQ algorithm. As a result of this work one has a choice of effective methods for finding solutions to two point boundary value problems in the non invertible case. Further these results are...
Saved in:
| Date: | 2015 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2015
|
| Series: | Электронное моделирование |
| Subjects: | |
| Online Access: | http://dspace.nbuv.gov.ua/handle/123456789/101099 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Best Least Square Solution of Boundary Value Problems Associated with a System of First Order Matrix DifferentialEquation / N. Swapna, S. Udaya Kumar, K.N. Murty // Электронное моделирование. — 2015 — Т. 37, № 2. — С. 3-16. — Бібліогр.: 4 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-101099 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1010992016-06-01T03:02:05Z Best Least Square Solution of Boundary Value Problems Associated with a System of First Order Matrix DifferentialEquation Swapna, N. Udaya Kumar, S. Murty, K.N. Математическое моделирование и вычислительные методы The best least square solution of the boundary value problem is constructed via modified QR algorithm and also RQ algorithm. As a result of this work one has a choice of effective methods for finding solutions to two point boundary value problems in the non invertible case. Further these results are exemplified with suitable examples to highlight the modified QR and RQ algorithms. Получено решение краевой задачи методом наименьших квадратов с помощью модифицированных QR и RQ алгоритмов. Предложен способ выбора эффективных методов решения двухточечных краевых задач в случае необратимости. Приведены примеры применения модифицированных QR и RQ алгоритмов. 2015 Article Best Least Square Solution of Boundary Value Problems Associated with a System of First Order Matrix DifferentialEquation / N. Swapna, S. Udaya Kumar, K.N. Murty // Электронное моделирование. — 2015 — Т. 37, № 2. — С. 3-16. — Бібліогр.: 4 назв. — рос. 0204-3572 http://dspace.nbuv.gov.ua/handle/123456789/101099 ru Электронное моделирование Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Математическое моделирование и вычислительные методы Математическое моделирование и вычислительные методы |
| spellingShingle |
Математическое моделирование и вычислительные методы Математическое моделирование и вычислительные методы Swapna, N. Udaya Kumar, S. Murty, K.N. Best Least Square Solution of Boundary Value Problems Associated with a System of First Order Matrix DifferentialEquation Электронное моделирование |
| description |
The best least square solution of the boundary value problem is constructed via modified QR algorithm and also RQ algorithm. As a result of this work one has a choice of effective methods for finding solutions to two point boundary value problems in the non invertible case. Further these results are exemplified with suitable examples to highlight the modified QR and RQ algorithms. |
| format |
Article |
| author |
Swapna, N. Udaya Kumar, S. Murty, K.N. |
| author_facet |
Swapna, N. Udaya Kumar, S. Murty, K.N. |
| author_sort |
Swapna, N. |
| title |
Best Least Square Solution of Boundary Value Problems Associated with a System of First Order Matrix DifferentialEquation |
| title_short |
Best Least Square Solution of Boundary Value Problems Associated with a System of First Order Matrix DifferentialEquation |
| title_full |
Best Least Square Solution of Boundary Value Problems Associated with a System of First Order Matrix DifferentialEquation |
| title_fullStr |
Best Least Square Solution of Boundary Value Problems Associated with a System of First Order Matrix DifferentialEquation |
| title_full_unstemmed |
Best Least Square Solution of Boundary Value Problems Associated with a System of First Order Matrix DifferentialEquation |
| title_sort |
best least square solution of boundary value problems associated with a system of first order matrix differentialequation |
| publisher |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| publishDate |
2015 |
| topic_facet |
Математическое моделирование и вычислительные методы |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/101099 |
| citation_txt |
Best Least Square Solution of Boundary Value Problems Associated with a System of First Order Matrix DifferentialEquation / N. Swapna, S. Udaya Kumar, K.N. Murty // Электронное моделирование. — 2015 — Т. 37, № 2. — С. 3-16. — Бібліогр.: 4 назв. — рос. |
| series |
Электронное моделирование |
| work_keys_str_mv |
AT swapnan bestleastsquaresolutionofboundaryvalueproblemsassociatedwithasystemoffirstordermatrixdifferentialequation AT udayakumars bestleastsquaresolutionofboundaryvalueproblemsassociatedwithasystemoffirstordermatrixdifferentialequation AT murtykn bestleastsquaresolutionofboundaryvalueproblemsassociatedwithasystemoffirstordermatrixdifferentialequation |
| first_indexed |
2025-07-07T10:25:43Z |
| last_indexed |
2025-07-07T10:25:43Z |
| _version_ |
1836983458375663616 |
| fulltext |
N. Swapna, S. Udaya Kumar
Dept of Computer Science and Engineering
K.N. Murty
Dept of Mathematics Geethanjali College
of Engineering and Technology,
(Hyderabad (A.P.) India, å-mail: nkanuri@hotmail.com)
Best Least Square Solution of Boundary
Value Problems Associated with a System
of First Order Matrix Differential Equation
The best least square solution of the boundary value problem is constructed via modified QR al-
gorithm and also RQ algorithm. As a result of this work one has a choice of effective methods for
finding solutions to two point boundary value problems in the non invertible case. Further these
results are exemplified with suitable examples to highlight the modified QR and RQ algorithms.
Ïîëó÷åíî ðåøåíèå êðàåâîé çàäà÷è ìåòîäîì íàèìåíüøèõ êâàäðàòîâ ñ ïîìîùüþ ìîäèôè-
öèðîâàííûõ QR è RQ àëãîðèòìîâ. Ïðåäëîæåí ñïîñîá âûáîðà ýôôåêòèâíûõ ìåòîäîâ ðåøå-
íèÿ äâóõòî÷å÷íûõ êðàåâûõ çàäà÷ â ñëó÷àå íåîáðàòèìîñòè. Ïðèâåäåíû ïðèìåðû ïðè-
ìåíåíèÿ ìîäèôèöèðîâàííûõ QR è RQ àëãîðèòìîâ.
K e y w o r d s: boundary value problems, least square solution, QR and RQ algorithms, overde-
termined systems, underdetermined systems.
Introduction. In this paper we shall be concerned with the boundary value prob-
lem (BVP) associated with first order matrix differential equation of the form
� � �y A t y f t( ) ( ), a t b� � , My a Ny b g( ) ( )� � , (1)
where A is an (n � n) matrix whose components are continuous functions on
a t b� � , f is an (n � 1) vector and is continuous. M and N are constant matrixes
of order (m � n) (m > n). Usually one assumes that general differential equations
can be written as a first order system � �y f t y( , ), a t b� � , where f is continuous
on [a, b] � R and y is a column matrix with components ( , , ..., )y y yn
T
1 2 . The
interval ends a and b are finite or infinite constants. For linear problems, the or-
dinary differential equation takes the form
� � �y A t y f t( ) ( ). (2)
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 2 3
�����������
���
��
��
�����
�������
���
��������
��
� N. Swapna, S. Udaya Kumar , K.N. Murty, 2015
The linear homogeneous system associated with (2) is
� �y A t y( ) . (3)
If Y is a fundamental matrix of the homogeneous system (3), then any solution of
(3) is of the form y t Y t C( ) ( )� where C is a constant (n�1) vector. If y is any so-
lution of (2) and y is a particular solution of (2), then ( )y y� � is a solution (3).
Thus [1] y y Y t C� � ( ) or y t y t Y t C( ) ( ) ( )� � . A particular solution y t( )of (2)
is given by
y t Y t Y s f s ds
a
t
( ) ( ) ( ) ( )�
�1 .
Thus
Y t Y t C Y t Y s f s ds
a
t
( ) ( ) ( ) ( ) ( )� �
�1 . (4)
Substituting the general form of y (t) in the boundary condition matrix in
(1), we get
[ ( ) ( )] ( ) ( ) ( )MY a NY b C NY b Y s f s ds g
a
b
� � �
�1 .
If we denote the characteristic matrix D by D MY a NY b� �( ) ( ), then
DC NY b Y s f s ds g
a
b
� � �
�( ) ( ) ( )1 .
If D is non-singular, then C can be determined uniquely, and in this case
C D NY b Y s f s ds D g
a
b
� � �� � �
1 1 1( ) ( ) ( ) .
Substituting the general form of C in (4), we get
y t Y t D NY b Y s f s ds Y t Y s f s
a
b
a
t
( ) ( ) ( ) ( ) ( ) ( ) ( ) (� � �� � �
1 1 1 ) ds D g� ��1
� �
�
a
b
G t s f s ds D g( , ) ( ) 1 ,
where G is the Green’s function for the homogeneous BVP and is given by
G t s
Y t D MY a Y s a t s b
Y t D MY a Y
( , )
( ) ( ) ( ),
( ) ( ) (
�
� � �
�
� �
� �
1 1
1 1 s a s t b), � � �
�
�
�
�
.
N. Swapna, S. Udaya Kumar, K.N. Murty
4 ISSN 0204–3572. Electronic Modeling. 2015. V. 37. ¹ 2
If D is an (m n� ) matrix and rank (D) = r < m, then the system
DC = b, (5)
where
b NY b Y s f s ds g t
a
b
� � �
�( ) ( ) ( ) ( )1
possesses a solution only in the least square sense.
Least Square Solution of Over Determine Systems. If D is an (m n� ) ma-
trix with rank (D) = r < m, then the system of equations (5) is called an overdeter-
mined system. We now attempt to solve the system by the method of least
squares i.e., determine C to minimize || ||DC b z� . If rank of D is n (i.e., columns
of D are L I.), then D DC D bT T� . Note that D DT is positive definite matrix and
C D D D bT T� �( ) 1 .
However, the algorithm resulting from forming and solving (5) is not as nu-
merically stable as the alternating way of using QU decomposition [2, 3]. If r < n,
then D DT is singular and (5) cannot be solved directly. In this case, the solution
is not unique. A solution of (5) in this case is given by C D b� � , where D � is the
psuedo inverse of D. The unique distinction of the above equation is that C is the
unique solution of (5) in the least square sense.
Example 1. Consider the linear system of equations:
x x x1 2 3 10� � � . ,
x x x1 2 305 025 05� � �. . . ,
x x x1 2 300 00 00� � �. . . ,
x x x1 2 305 025 05� � �. . . ,
x x x1 2 3 20� � � . .
The above system of equations can be put in the form
1 10 10
1 05 025
1 00 00
1 05 025
1 10 10
�
�
�
�
�
�
�
�
�
�
�
�
�
. .
. .
. .
. .
. .
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
x
x
x
1
2
3
10
05
00
05
20
.
.
.
.
.
�
�
�
,
DC = b, (6)
Since D is 5�3 matrix of rank 3 .We multiply the equation (6) by DT and get
DTDC = DTb and hence C = (DTD)–1DTb, and C is unique. In general, if the mat-
Best Least Square Solution of Boundary Value Problems Associated with a System
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 2 5
rix D is rectangular (or singular), then the equation (6) can have either an infinite
number of solutions or no solution. If D is singular and R (D) and N (D) represent
the range and null space of D, respectively, then (6) will have solutions if
b R D� ( ). In this case, if C is any n vector in N (D) and C 0 is any solution of (6),
then the vector C C� 0 will also be a solution. If b R D� ( ), then the system (6)
will not have a solution.
Further, if D is an (m n� ) matrix, then for a given D C m n� � and b ˆ Cm, the
linear system (6) is consistent if and only if b R D� ( ). Otherwise the residual
vector
r = b – DC (7)
is non-zero for all C � Cn, and it may be desired to find an appropriate solution of
(6), by which we mean a vector C, making the residual vector in (7) very close to
zero in some sense. The following theorem shows that || ||DC b� is minimized by
choosing C = D+ b , where D+ is such that
D+DD+ = D+, (8)
DD+D = D, (9)
(DD+)* = DD+, (10)
(D+ D)* = D+D (11)
such a D+ is unique. If D+ satisfies conditions (9) and (10), then D+ need not
be unique.
Theorem 1. Let D C m n� � and b C m� . Then || ||DC b� is the smallest when
C D b� � where D+ satisfies (9) and (10). Conversely, if D+ has property that for
all b, || ||DC b� is the smallest when C D b� � , then D+ satisfies (9) and (10).
P r o o f. If PR D( ) is the projection matrix on R (D), then write DC b� �
� � � �( ) ( )( ) ( )DC P b P b bR D R D . Then
|| || || || || ||( ) ( )DC b DC P b P b bR D R D� � � � �2 2 2 . (12)
Since ( ) ( )( )DC P b R DR D� � and � � �( ) ( ),( )I P b R DR D it follows that (12) as-
sumes minimum value if, and only if
DC = PR(D)b, (13)
which certainly holds, if C = DT b for any D+ satisfying (9) and (10). Hence
DD+ = PR(D). Conversely, if D+ is such that for all b, || ||DC b� is the smallest when
C = D+ b, then by (13), we have DD b P b bR D
� � �( ) , and hence DD PR D
� � ( ) .
Thus, D � satisfies (9) and (10). Suppose D � satisfies (8) and (11), then we have the
following theorem.
N. Swapna, S. Udaya Kumar, K.N. Murty
6 ISSN 0204–3572. Electronic Modeling. 2015. V. 37. ¹ 2
Theorem 2. Let D C m n� � and b C m� . If DC = b has a solution for C, the
unique solution for which || ||C is the smallest is given byC D b� � , where D � sat-
isfies conditions (8) and (11). Conversely, if D C n m� �� , C n m� is such that,
whenever DC = b has solution C = D+b is the solution of minimum norm, then
D+ satisfies (8) and (11).
P r o o f. The proof is similar to the proof of the Theorem 1.
Theorem 3. Let D C m n� � and b C m� . If DC = b has a solution for C, then
the unique solution of DC = b is C = D+b, where D+ satisfies (8)-(11).
Lemma. Let D C m n� � . Then D is one�one mapping of R (D*) onto R (D).
Corollary. Let D C m n� � , b � R (D) . Then there is a unique minimum norm
solution of
DC = b, (14)
which lies in R (D*).
P r o o f. By lemma, the equation (14) has a unique solution Co in R (D*).
Now the general solution is given by C = C0 + C1 for someC N D1 � ( ). Clearly,
|| || || || || ||C C y0
2
0
2� � , proving that || || || ||C C2
0
2� and equality holds, only if
C C� 0.
Non-invertible BVP occur in a natural way in the study of bifurcation, in
singular perturbation theory, and in nonlinear eigenvalue problems. A similar
situation arises in some identification problems, which often leads to undeter-
mined two-point BVP. In such situations one normally seeks solutions which
satisfy the boundary conditions exactly and solve the differential equation in
some least square sense.
Definition 1. For a given f C a bn� [ , ], the set of all least square solutions of
(1) is defined as
S x D L Lx f
Inf
y D L
Ly ff � � � �
�
�
�
�
�
�
( ) || ||
( )
|| || ,
where D (L) is the domain of the operator L and is given by D L BC a bn( ) [ , ]� � ,
BC a bn� [ , ] is the subspace of �C a bn [ , ] satisfies the boundary conditions in (1).
Definition 2. The best least square solution (1) is denoted by y+ and is defined to
be an element of Sf of minimum norm (if such exists) i.e., || || min || ||y x
x S f
�
�
� .
We now present an algorithm for computing the minimal norm least square so-
lution of the general system of equations Ax = b, where A is an (m n� ) matrix and x is
column matrix with components ( , , ..., )x x xn
T
1 2 and b b b bn
T� ( , , ..., )1 2 .
Q-R Decomposition. In this section we first present QR algorithm and then
present our main result on modified QR algorithm, when the matrix A is of rank
Best Least Square Solution of Boundary Value Problems Associated with a System
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 2 7
p = min(m, n). The algorithm presented here depends upon the rank factorization
of the form AP = QR , where P is an (n m� ) permutation matrix such that the first
p columns of AP are linearly independent. Q is an (m n� ) matrix with ortho-
normal columns (QTQ = I ) and R is an upper trapezoidal matrix of rank p. We
shall denote lm A Ax R x Rm n( ) { | }� � � the column space of A and Ker A( ) �
� � �{ | }x R Axn 0 . We first present QR-algorithm.
Theorem 4. Let A be an (m n� ) matrix with rank n m n( )� then there exists a
unique (m n� ) orthogonal matrix Q Q QT( )� In and a unique (n n� ) upper trian-
gular matrix R with positive diagonal elements (rii > 0) such that A = QR.
P r o o f. It may be noted that the theorem is a restatement of the Gram-
Schmidt orthogonalization process. If we apply Gram-Schmidt to the columns
of A a a an� [ , ,..., ]1 2 from left to right, we get a sequence of orthonormal vectors
q1 through qn spanning the same space and these orthogonal vectors are the co-
lumns of Q. Further, Gram-Schmidt also computes coefficient r q aii j
T
i� ex-
pressing each column ai as a linear combination of q1 through qi: ai r q
j
n
ji j�
�
�
1
.
These r ji are the just entries of R.
We shall now present the classical Gram-Schmidt and modified Gram-
Schmidt algorithms for factoring of A = QR:
For i =1 to n /* compute the ith column of Q and R*/
qi = ai
for j = 1 to i – 1 /*subtract component in qj direction from ai*/
r q a CGSji j
T
i�
r q q MGSji j
T
i�
q q r qi i ji j� �
end for
r qii i� || ||2.
If rii �0 /* ai is linearly independent of a a ai1 2 1, ,..., � ,*/
quit
end if
q
q
r
i
i
ii
�
end for.
We further need the following results for construction of the least square al-
gorithm and the best least square algorithm.
Result 1. Let A be given (m n� ) matrix of rank p. Then there exists a
factorization AP = QR with the following properties:
N. Swapna, S. Udaya Kumar, K.N. Murty
8 ISSN 0204–3572. Electronic Modeling. 2015. V. 37. ¹ 2
(i) p is an (n n� ) permutation matrix with first p columns of AP form a basis
for Im (A) and
(ii) Q is an (m p� ) matrix with orthogonal columns and R is a ( p n� ) up-
per-trapezoidal matrix of the form R = [R1, R2],where R1 is non-singular ( p p� )
upper triangular matrix and R2 is a ( p n p� � ) matrix [4].
Result 2. Let A be an (m n� ) matrix with rank p = min{m, n}.Write
A a a an� [ , ,..., ]1 2 , where a j ˆ R mand p be an (n n� ) permutation matrix such that
AP = QR, where Q is an (m p� ) matrix with orthonormal columns and R is an
( p n� ) upper trapezoidal of rank p. Then the first p columns of AP are linearly
independent and all the least square solutions of the system Ax = b can be ob-
tained by solving the consistent system: RPT x=Q*b. If we write R = [R1, R2], R1
is ( p p� ) upper triangular, then x P
u
v n p
p
�
�
�
�
�
�
�
� }
}
, whereV R n p� � is arbitrary and
u R a b R v� ��
1
1
2( )* are the least square solutions of Ax = b. A basic least square
solution is obtained by taking v = 0.
Let A be an (m n� ) matrix and b R m� be given. Let rank of A be
p m n� min{ , }.The following is the algorithm to compute the least square solu-
tion. We use the following notation
aij : = bij means aij becomes bij for all i = 1 to m and j = 1 to n.
A l g o r i t h m:
q aij ij:� , i �1to m; j �1to n;
rij :�0, i �1to m; j �1to n + 1;
s jj :� , j �1to n;
p n:� ;
for k �1to n;
� j ijq� | |2, | | ,qij
i
m
2
1�
� i k n� , ..., ,
compute index c, k c n� � such that � �c
j n
j�
� �
max
1
,
if �c �0 go to 20,
20 : p : k – 1 go to 30,
interchange column K of Q with column C of Q,
interchange column K of R with column C of R
interchange number �k with number �c,
interchange index sk with index C
r kkk :� �
q q rk k kk: /�
r q qkj k j� * , j k n� �1,...,
q q r qj j kj k� � , j k n� �1,...,
Best Least Square Solution of Boundary Value Problems Associated with a System
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 2 9
r q bk n i k,
*
� �
30 : for j = p + 1 to n
xj = 0;
Back solve the system of equations
r x r x rp p n11 1 1 1 1� � � �... ,
r x r x rp p n22 12 2 2 1� � � �... ,
.....................................
r x rpp p p n� �, 1
to determine x x x p1 2, ,...,
for j = n, n–1, …, 1
k s j� .
If k j� x xk j� , x x x xn� [ , ,..., ]1 2 is the least square solution of Ax = b.
A l g o r i t h m f o r M I N L S. If p = n STOP, the least square solution al-
ready found is the minimal norm least square solution of Ax = b:
else v : = n – p
bj : = xj, j = 1 to n
xj : = 0, j = p + 1 to n
for k = p + 1 to n
xk : = 1
Back solve the equation systems Rx = 0 to determine x x x p1 2, ,...,
J : = k – p
aij : = xi for i = 1 to n
xk : = 0
for i = n to 1
k : = si ,
if k i� interchange akj and aij for j = 1 to v.
Computation of Pseudoinverse. Algorithm min Ls can be used to find
pseudoinverse of an (m n� ) matrix A. Using min Ls algorithm m times, solve for
ai
� of the problem Ax = ei, where ei (1� �i m) are the standard Eucledian basis for
Rm. Then the Pseudoinverse of the matrix A denoted by A+ is given by
A a a an
� �{ , ,..., }* * *
1 2 . To illustrate the results mentioned above, we consider the
system of equations of the form � � �y A t y f( ) , satisfying
My (0) + Ny (1) = b, (15)
where
A
t
�
�
�
�
�
�
�
�
�
�
�
0 1
0 0 1
0 0 0
, f t( ) �
�
�
�
�
�
�
�
�
�
�
0
0
1
,
N. Swapna, S. Udaya Kumar, K.N. Murty
10 ISSN 0204–3572. Electronic Modeling. 2015. V. 37. ¹ 2
M �
�
�
�
�
�
�
�
�
�
�
�
�
1 2 3
1 5 6
1 8 9
1 11 12
, N �
�
�
�
�
�
�
�
�
�
�
�
�
0 0 1
1 0 0
0 1 0
0 1 1
, b t( )
.
.
.
�
�
�
�
�
�
�
�
�
�
�
�
�
7
135
195
205
.
A fundamental matrix of the homogeneous system � �y Ay is given by
Y t
t t
t( ) �
�
�
�
�
�
�
�
�
�
�
1
0 1
0 0 1
2
.
Substituting the general form of the solution y (t) = Y (t)C in the boundary
condition matrix My (0) + Ny (1) = g, we get
DC NY Y s f s ds g� � �
�( ) ( ) ( )1
0
1
1 ,
where
D �
�
�
�
�
�
�
�
�
�
�
�
�
1 2 3
1 5 6
1 8 9
1 11 12
and the right hand side is given by [6, 13, 19, 24]T = b or DC = b. Here D is a (4 � 3)
matrix of rank 2. The minimal norm least squares solution of this system as de-
termined by the algorithm MINLS is given by C T� [ . . ]1 0 5 15 with the least
square residual equal to 1.
The best least square solution y t�( ) of BVP (15) is as follows
y t y t C y t y s f s ds
t t
t t
a
t
� �� � �
� � �
� � ( ) ( ) ( ) ( ) ( )1
2 2
2
1
1
2
1
2
3
2
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�t
.
Example 2. Consider BVP � � �y Ay f . My (0) + Ny (1) = g, where
A �
�
�
�
�
�
�
�
�
�
�
�
�
0 1 0 0
0 0 1 0
0 0 0 1
0 0 0 0
, f �
�
�
!
"
#
#
#
#
0
0
0
1
, g
T
� ��
��
�
��
4
3
75
24
125
24
,
Best Least Square Solution of Boundary Value Problems Associated with a System
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 2 11
M �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
1 1 0
1
2
1 1 1 1
0 2 2
2
3
, N �
��
�
�
�
�
�
�
�
�
�
�
�
�
�
2 0
1
2
1
1 4 0
7
6
1 0
1
2
0
.
A fundamental matrix Y of � �y Ay is given by
Y t
t t t
t t
t
( ) �
�
�
�
�
�
�
�
�
�
�
�
�
1
0 0 2 3
0 0 2 6
0 0 0 6
2 2
2
, Y t
t t t
t t
t
� �
� �
�
�
�
�
�
�
�
�
�
�
�
�
1
2 2
2
1
1
2
1
6
0 1
1
2
0 0
1
2
1
2
0 0 0
1
6
( )
�
�
�
�
�
�
�
�
�
�
.
Substituting the general form solution Y (t) C in the boundary condition matrix,
we get
1 3 3 2
2 6 5
1 3 3 0
2 0
1
2
1
1 4 0
7
6
1 0
1
2
0
g C
�
�
�
�
�
�
�
�
�
�
�
� �
��
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
1 1 1 1
0 1 2 3
0 0 2 6
0 0 0 6
�
� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
0
1
2 2
2
1
1
2
1
6
0 1
1
2
0 0
1
2
1
2
0 0 0
1
6
s s s
s s
s
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� �
�
�
�
�
�
�
�
�
�
�
�
�
�
0
0
0
1
1
3
45
24
7
24
ds g
�
� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� �
�
�
�
�
�
�
�
�
�
�
�
4
3
75
24
127
24
1
5
5
.
This is an underdetermined system and hence algorithm MINLS chooses
the minimal norm solution amongst all the solutions of the problem. The
minimal norm least square solution determined by the MINLS algorithm is
C � � �[ . . . . ]0 211009174 0633027523 0 963302752 0110091743 T . Slight al-
terations of this program will handle the complex case, as the algorithm we pre-
N. Swapna, S. Udaya Kumar, K.N. Murty
12 ISSN 0204–3572. Electronic Modeling. 2015. V. 37. ¹ 2
sented is for the real data. Note that we compiled the MINLS incorporating Al-
gorithm of least squares in IBMAT.
QR Factorization via Gram-Schmidt. Ax = b, write A = QR, where Q is
unitary and R is upper triangular, Q is m m� and R is m n� (m n� ). Since m n�
the last m-n rows of R will be zero. We first start with a1. Write
a q r q a r1 1 11 1 1 11� $ � / , (16)
a q r q r q
a r q
r
2 1 12 2 22 2
2 12 1
22
� � $ �
�
, (17)
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
a q r q r q r q
a r q
r
n n n nn n
n
i
n
in
nn
2 1 1 2 2
1
0
� � � � $ � �
�
... , (18)
since the columns of aj of A are given, we need to determine the columns qj of Q
and entries rij of R such that Q is orthonormal, i.e.,
q qi j ij
* �� , (19)
and R is upper triangular and A = QR . The latter two conditions are already re-
flected in the above formulae using (16) in (19) , we get q q
a a
r
1 1
1 1
11
2
1*
*
� � so that
r a a a11 1 1 1 2� �* || || . Note that, we choose arbitrarily the positive square root so
that the factorization becomes unique.
From (18) we have q q1 2 0* � , q q2 2 1* � . Applying (17) we get
q q
q a r q q
r
1 2
1 2 12 1 1
22
0*
* *
�
�
� .
Thus
q
a q a q
r
2
2 1 2 1
22
�
�([ ] )*
(since q q1 1 1* � , r q a12 1 2� * ). Now to find r22 we normalize || ||q2 2 1� . Thus
r a q a q22 2 1 2 1 2� �|| ( ) ||* . For n = 3 we have q q1 3 0* � , q q2 3 0* � , q q3 3 1* � . The first
two of the above conditions together with (18) for n = 3 yield
q q
q a r q q r q q
r
1 3
1 3 13 1 1 23 1 2
33
0*
* * *
�
� �
� .
Best Least Square Solution of Boundary Value Problems Associated with a System
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 2 13
Since q q1 2 0* � and q q1 1 1* � , we have r q a13 1 3� * . Similarly q q2 3 0* � and (18) for
n = 3 again yields
q q
q a r q q r q q
r
2 3
2 3 13 2 1 23 2 2
33
0*
* * *
�
� �
�
so that r q a q q q q% %
&
% %
&
% %
&
%� ' ( ' � ' �23 2 3 2 1 0 2 2 1( ) ( )and . Further q q3 3
* �
� �|| ||q3 2 1, we get
q
a q a q q a q
r
3
3 1 3 1 2 3 2
33
�
� �( ) ( )* *
, r a q a q q a q33 3 1 3 1 2 3 2 2� � �|| ( ) ( ) ||* * .
In general we have the following algorithm r q aij j� 1
* (i j� ):
v a r qj j
i
j
ij i� �
�
�
�
1
1
, r vjj j� || ||2, q
v
r
j
j
jj
� .
The following is the classical Gram-Schmidt algorithm:
for j = 1 to n
v aj j� ;
for i = 1 : j – 1
r q aij j� 1
* , v v r qj j ij i� �
end
r vjj j� || ||2, q
v
r
j
j
jj
�
end.
Example 3. Consider
1 2 0
0 1 1
1 0 1
�
�
�
�
�
�
�
�
�
�
�x b. First v a1 1
1
0
1
� �
�
�
�
�
�
�
�
�
�
�
and r v11 1 2� �|| || .
This gives q
v
v
1
1
1
1
2
1
0
1
� �
�
�
�
�
�
�
�
�
�
�
|| ||
. Next,
v a q a q a r2 2 1 2 1 2 12
2
1
0
2
2
1
0
1
� � � � �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�( )*
�
�
�
�
�
�
�
�
�
�
�
�
�
�
1
1
1
.
N. Swapna, S. Udaya Kumar, K.N. Murty
14 ISSN 0204–3572. Electronic Modeling. 2015. V. 37. ¹ 2
Thus r12 2 2 2� �/ . Moreover, r v22 2 2 3� �|| || and
q
v
v
2
2
2
1
3
1
1
1
� �
�
�
�
�
�
�
�
�
�
�
�
|| ||
.
In the last iteration we have r a q a q q a q2 2 1 2 1 2 2 2� � �( ) ( )* * , where ( )*q a q r1 3 1 13�
and ([ ] )*q a q r2 3 3 23� . From this we compute r13 1 2� / and r23 0� . This gives
v3
0
1
1
1
2
1
2
1
0
1
0
1
2
1
2
1
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� �
��
�
�
�
�
�
�
�
�
�
.
Finally, r v33 3 2 6 2� �|| || / and q
v
v
3
3
3 2
1
6
1
2
1
� �
��
�
�
�
�
�
�
�
�
�
|| ||
. Thus
Q �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
1
2
1
3
1
6
0
1
3
2
6
1
2
1
3
1
6
, R �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
2 2
1
2
0 3 0
0 0
6
2
.
Generalized QR Factorization. In this section we shall be concerned with
the system of equations Ax = b, where A is an (n m� ) matrix and x is an (m�1) vec-
tor we assume that n m� . This is an underdetermined system. The QR-facto-
rization of (n m� ) matrix A can be written as A = QR, where Q is an (n n� )
orthonormal matrix and R = QTA is zero below the main diagonal and is given by
R Q A
RT� �
�
�
�
�
�
�
11
0
, where R11 is an (n n� ) upper triangular matrix. If n < m then the
QR factorization of A assumes Q A R RT � [ ]11 12 , where R11 is an (n n� ) upper tri-
angular matrix. However in many practical applications it will be more appropri-
ate to write A in the form A R Q� [ ]0 11 , which is known as RQ factorization. In
fact QR and RQ factorization are the QL and LQ factorization and are in fact or-
thogonal — lower-triangular (QL) and lower triangular — orthogonal factori-
zation (LQ). It is well known in fact that the orthogonal factors of A provide in-
Best Least Square Solution of Boundary Value Problems Associated with a System
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 2 15
formation about its column and row spaces. If rank of A is k n m� min{ , }, then
there exist orthonormal matrix Q and a permutation matrix P such that
Q AP
R RT �
�
�
�
�
�
�
11 12
0 0
,
R11 being k k� , R12 being ( )m k k� � ,
o being k n k� �( ) and o being ( ) ( )m k n k� � � ,
where R11 is a (k k� ) upper triangular matrix and R11 is non singular we present
generalized RQ factorization for the system of equations Ax = b.
Let A be an (n m� ) matrix and assume that n < m. Then there exists orthogo-
nal matrix Q (n n� ) and U (m m� ) such that QTAU = R, where R R� [ ]0 11 , o be-
ing ( )m n n� � and R11 being (n n� ) matrix, and further R11, being upper triangu-
lar, is non-singular. By QR-factorization with column pivoting of A, we have
Q AP
R RT �
�
�
�
�
�
�
11 12
0 0
,
R11 being q q� , R12 being ( )m q q� � ,
o being q n q� �( ) and o being ( ) ( )m q n q� � � ,
where q = rank (A).
Îòðèìàíî íàéêðàùèé ðîçâ’ÿçîê êðàéîâî¿ çàäà÷³ ìåòîäîì íàéìåíøèõ êâàäðàò³â çà äîïîìî-
ãîþ ìîäèô³êîâàíèõ QR òà RQ àëãîðèòì³â. Çàïðîïîíîâàíî ñïîñ³á âèáîðó åôåêòèâíîãî ìå-
òîäó ðîçâ’ÿçóâàííÿ äâîõòî÷êîâèõ êðàéîâèõ çàäà÷ ó âèïàäêó íåîáîðîòíîñò³ ìàòðèö³. Íàâå-
äåíî ïðèêëàäè çàñòîñóâàííÿ ìîäèô³êîâàíèõ QR òà RQ àëãîðèòì³â.
REFERENCES
1. Cole, R.H. (1986), Theory of Ordinary Differential Equations, Appleton-Century Grafts,
Norwalk.
2. Rice, J.R. (1966), Experiments of Gram-Schmidt orthogonalization, Math-Comp., Vol. 20,
pp. 325-328.
3. Sreedharan, V.P. (1988), A Note on modified Gram-Schmidt process, Math-Comp., Vol. 24,
pp. 277-290.
4. Sastry, B.R., Murty, K.N. and Balaram, V.V.V.S.S. (2007), General first order matrix dif-
ference system-existence and uniqueness via new lattice based cryptographic construction,
Elektronnoe modelirovanie, Vol. 29, no. 2, pp. 245-259.
Ïîñòóïèëà 20.10.14
N. Swapna, S. Udaya Kumar, K.N. Murty
16 ISSN 0204–3572. Electronic Modeling. 2015. V. 37. ¹ 2
|