Matrix Operations
Yu Jiangsheng
Institute of Computational Linguistics
Peking University
September 26, 2002
Topics
1. Matrix Multiplication
2. Solving System of Linear System
3. Inverting Matrixes
4. Symmetric Positive-definitive Matrixes and
Least-squares Approximation
5. Winograd Theorem and AHU Theorem
1
Matrix
A matrix A is, in fact, a sequence of arrays:
A =
a
11
a
12
· · · a
1n
a
21
a
22
· · · a
2n
...
a
m1
a
m2
· · · a
mn
=
a
ij
m
×n
Note
From the viewpoint of transformation,
Ax describes the rotation of x around 0 and
linear stretching.
2
Singular Matrix
linearly independent
→ row rank and column
rank
→ rank → full rank ↔ existence of in-
verse (nonsingular)
Definition 1 A
null vector
for a matrix A
m
×n
is a nonzero vector x such that Ax = 0.
Homework 1
A matrix A has full column rank
iff it has no null vector.
Homework 2
A square matrix is singular iff
it has null vector.
3
Determinant of Matrix
Definition 2 The ijth
minor
of matrix A
n
×n
is the (n
− 1) × (n − 1) matrix A
[ij]
obtained
by deleting the ith row and the jth column
of A.
Definition 3 The
determinant
of A
n
×n
is de-
fined recursively in terms of minors by
det(A) =
a
11
if n = 1
n
j=1
(
−1)
1+j
a
1j
det(A
[1j]
)
if n > 1
(1)
Property 1 A
n
×n
is singular iff det(A) = 0.
4
MatLab for Numerical Computing
• 1970s, Dr. Moler developed two FORTRAN sub-
routines, EISPACK for eigenvalue of matrix and
LINPACK for linear equations, which evolved to
MatLab (Matrix Laboratory).
• In 1983, John Little, Cleve Moler and Steve Bangert
developed MatLab in C.
• In 1984, J. Little and C. Moler founded Math-
Works Company.
• The recent version of MatLab is 6.1.
• Softwares of numerical computing:
MatLab
,
XMath
,
Gauss
,
SAS
,
S-Plus
,
Origin
, etc.
Softwares of
symbolic processing:
Mathematica
,
Maple
, etc.
5
A Demo of MatLab Program
6
Matrix Multiplication
M
ATRIX
-M
ULTIPLICATION
(A, B)
1
n
← rows[A]
2
let C be a n
× n matrix
3
for i
← 1 to n
3
do for j
← 1 to n
4
do c
ij
← 0
5
for k
← 1 to n
5
do c
ij
← c
ij
+ a
ik
· b
kj
6
return C
The time cost of
M
ATRIX
-M
ULTIPLICATION
(A, B)
is Θ(n
3
), where A, B are two n
× n matrixes.
7
Method of Block Matrixes
Let A, B be two n
× n matrixes, where n is an
exact power of 2. Then
C
=
A
B
C
11
C
12
C
21
C
22
=
A
11
A
12
A
21
A
22
B
11
B
12
B
21
B
22
(2)
where A
ij
, B
ij
, C
ij
are
n
2
×
n
2
matrixes. Thus,
the elements of C are
C
11
= A
11
B
11
+ A
12
B
21
C
12
= A
11
B
12
+ A
12
B
22
C
21
= A
21
B
11
+ A
22
B
21
C
22
= A
21
B
12
+ A
22
B
22
(3)
8
Time Complexity
Because the method of block matrixes divides
the multiplication to eight multiplications and
four additions of
n
2
×
n
2
matrixes. Therefore,
the recurrence is
T
(n) = 8
T
(n/2) + Θ(n
2
)
(4)
By Master Theorem,
T
(n) = Θ(n
3
). That is,
the method does not decrease the time cost.
Strassen turns recurrence (4) to
T
(n) = 7
T
(n/2) + Θ(n
2
)
(5)
whose solution is
T
(n) = Θ(n
log 7
) = O(n
2.81
)
.
9
Strassen’s Method
In 1969, Strassen found the seven variables:
X
1
= (A
11
+ A
22
)(B
11
+ B
22
)
X
2
= (A
21
+ A
22
)B
11
X
6
= (A
21
− A
11
)(B
11
+ B
12
)
X
3
= A
11
(B
12
− B
22
)
X
7
= (A
12
− A
22
)(B
21
+ B
22
)
X
4
= A
22
(B
21
− B
11
)
X
5
= (A
11
+ A
12
)B
22
Then, the (3) turns into:
C
11
= X
1
+ X
4
− X
5
+ X
7
C
12
= X
3
+ X
5
C
21
= X
2
+ X
4
C
22
= X
1
+ X
3
− X
2
+ X
6
(6)
10
Complexity of Multiplication
It is obvious that the best lower bound of
n
× n matrix multiplication is Ω(n
2
), because
we have to fill in n
2
elements of the prod-
uct matrix. The current best upper bound is
approximately O(n
2.376
).
We have not
known the exact
complexity of ma-
trix multiplication.
11
Why not Strassen’s Algorithm?
In practice, Strassen’s algorithm is not a good
choice. The reason is summarized as
1. The constant factor hidden in the running time
of Strassen’s algorithm is larger than that in the
naive Θ(n
3
) method.
2. When the matrixes are sparse, there are faster
methods.
3. Strassen’s algorithm is not quite as numerically
stable as the naive method.
4. The submatrixes formed at the levels of recursion
consume space.
12
Linear Equation
a
11
x
1
+
a
12
x
2
+
· · · + a
1n
x
n
=
b
1
a
21
x
1
+
a
22
x
2
+
· · · + a
2n
x
n
=
b
2
...
a
n1
x
1
+
a
n2
x
2
+
· · · + a
nn
x
n
=
b
n
(7)
a
11
a
12
· · · a
1n
a
21
a
22
· · · a
2n
...
a
n1
a
n2
· · · a
nn
x
1
x
2
...
x
n
=
b
1
b
2
...
b
n
(8)
Ax = b
(9)
x = A
−1
b suffers in practice from nu-
merical instability. A faster algorithm,
LUP decomposition, is numerically stable.
13
LUP Decomposition
The idea of
LUP decomposition
is to find
three n
× n matrixes L, U and P such that
P A = LU
(10)
where
• L is a unit lower-triangular matrix,
• U is a upper-triangular matrix, and
• P is a permutation matrix.
14
Permutation Matrix
Definition 4 A permutation matrix P = (p
ij
)
n
×n
has exactly one 1 in each row and column,
and 0’s elsewhere.
Example 1 P is a permutation matrix:
P =
0 0 1 0 0
1 0 0 0 0
0 1 0 0 0
0 0 0 0 1
0 0 0 1 0
Denote the permutation
by π. p
iπ[i]
= 1 and p
ij
=
0 for j
= π[i].
Given x = (x
1
, x
2
, x
3
, x
4
, x
5
)
T
, then the per-
mutation is P x = (x
3
, x
1
, x
2
, x
5
, x
4
)
T
.
15
Why LUP Decomposition?
Theorem 1 If A is a nonsingular n
×n matrix,
then there exits a unique LUP decomposition
of A.
P Ax = P b
⇒ LUx = P b or L(Ux) = P b. Let
y = U x, then Equation (9) turns to two steps:
1. Ly = P b for the unknown vector y by the
method of
forward substitution
, and
2. U x = y for the unknown vector x by the
method of
backward substitution
.
16
Forward Substitution
y
1
=
b
π[1]
l
21
y
1
+
y
2
=
b
π[2]
l
31
y
1
+
l
32
y
2
+
y
3
=
b
π[3]
...
l
n1
y
1
+
l
n2
y
2
+
l
n3
y
3
+
· · · + y
n
=
b
π[n]
The solution is:
y
1
= b
π[1]
y
2
= b
π[2]
− l
21
y
1
y
3
= b
π[3]
− (l
31
y
1
+ l
32
y
2
)
...
y
i
= b
π[i]
−
i
−1
j=1
l
ij
y
j
(11)
Therefore, the time cost of Forward Substi-
tution is Θ(n
2
).
17
Backward Substitution
u
11
x
1
+
u
12
x
2
+
· · ·
+
u
1,n
−1
x
n
−1
+
u
1n
x
n
=
y
1
u
22
x
2
+
· · ·
+
u
2,n
−1
x
n
−1
+
u
2n
x
n
=
y
2
..
.
u
n
−1,n−1
x
n
−1
+
u
n
−1,n
x
n
=
y
n
−1
u
n,n
x
n
=
y
n
The solution is:
x
n
=
y
n
/u
n,n
x
n
−1
=
(
y
n
−1
− u
n
−1,n
x
n
)
/u
n
−1,n−1
...
x
i
=
y
i
−
n
j=n+1
u
ij
x
j
/u
ii
(12)
Therefore, the time cost of Backward Sub-
stitution is Θ(n
2
).
18
LUP Algorithm
LUP-S
OLVE
(L, U, π, b)
1
n
← rows[L]
2
for i
← 1 to n
3
do y
i
← b
π[i]
−
i
−1
j=1
l
ij
y
j
4
for i
← n downto 1
5
do x
i
←
y
i
−
n
j=n+1
u
ij
x
j
/u
ii
6
return x
The complexity of
LUP-S
OLVE
is Θ(n
2
).
19
Example of LUP Algorithm
Example 2 Given Ax = b, where
A =
1
2
3
3
4
4
5
6
3
,
b =
3
7
8
The LUP of A is
L =
1
0
0
0.2
1
0
0.6
0.5
1
,
U =
5
6
3
0
0.8
−0.6
0
0
2.5
,
P =
0
0
1
1
0
0
0
1
0
Then by LUP algorithm, we have
1
0
0
0.2
1
0
0.6
0.5
1
y
1
y
2
y
3
=
8
3
7
⇒
y =
8
1.4
1.5
5
6
3
0
0.8
−0.6
0
0
2.5
x
1
x
2
x
3
=
8
1.4
1.5
⇒
x =
−1.4
2.2
0.6
20
LU Decomposition
Definition 5
LU decomposition
is a special
case of LUP decomposition, in which P = I
n
.
Ax=b
LUP
LU
21
Gauss — Forever Genius
1777-1855
22
Gaussian Elimination
A
=
a
11
a
12
· · ·
a
1n
a
21
a
22
· · ·
a
2n
...
a
n1
a
n2
· · ·
a
nn
=
a
11
w
T
v
A
then,
we have
A
=
1
0
v/a
11
I
n
−1
a
11
w
T
0
A
− vw
T
/a
11
=
1
0
v/a
11
I
n
−1
a
11
w
T
0
L
U
=
1
0
v/a
11
L
a
11
w
T
0
U
= LU
where A
− vw
T
/a
11
is called the
Schur com-
plement
of A with respect to a
11
.
23
SOS for a
11
= 0
LU
LUP
0
11
=
a
Note
If a
11
= 0 or the upper leftmost entry
of the Schur complement A
− vw
T
/a
11
is 0,
then the Gaussian elimination fails.
24
P Saves LU
Definition 6 The elements by which we di-
vide during LU decomposition is called
pivots
,
and they occupy the diagonal elements of U .
The reason of P added to LU decomposition
is to avoid dividing by 0.
Definition 7 Using permutation to avoid di-
vision by 0 (or small element) is called
pivot-
ing
. But,
symmetric positive-definite matrix
does not need pivoting
(we’ll prove it later).
25
LU Algorithm
LU-D
ECOMPOSITION
(A)
1
n
← rows[A]
2
for k
← 1 to n
3
do u
kk
← a
kk
//determining the pivot
4
for i
← k + 1 to n
5
do l
ik
← a
ik
/u
kk
//l
ik
holds v
i
6
u
ki
← a
ki
//u
ki
holds w
T
i
7
for i
← k + 1 to n
8
do for j
← k + 1 to n
9
do a
ij
← a
ij
− l
ik
u
kj
10
return L and U
Property 2 The complexity of LU algorithm
is Θ(n
3
), also is that of LUP decomposition.
26
Example of LU Decomposition
Example 3 The steps of LU:
2
3
1
5
6
13
5
19
2
19
10
23
4
10
11
31
⇒
2
3
1
5
3
4
2
4
1
16
9
18
2
4
9
21
⇒
2
3
1
5
3
4
2
4
1
4
1
2
2
1
7
17
⇒
2
3
1
5
3
4
2
4
1
4
1
2
2
1
7
3
2
3
1
5
6
13
5
19
2
19
10
23
4
10
11
31
=
1
0
0
0
3
1
0
0
1
4
1
0
2
1
7
1
2
3
1
5
0
4
2
4
0
0
1
2
0
0
0
3
A
=
L
U
27
How to Get P ?
Find a permutation matrix Q such that
QA =
a
k1
w
T
v
A
=
1
0
v/a
k1
I
n
−1
a
k1
w
T
0
A
− vw
T
/a
k1
(13)
where a
k1
= 0, v = (a
21
, a
31
,
· · · , a
n1
)
T
except
that a
11
replaces a
k1
, and w
T
= (a
k2
, a
k3
,
· · · , a
kn
).
The LUP decomposition of A
− vw
T
/a
k1
is
P
(A
− vw
T
/a
k1
) = L
U
(14)
The
permutation matrix
P is defined by
P =
1
0
0 P
Q
(15)
since it is a product of two permutation ma-
trixes (
homework
).
28
How to Get L and U ?
P A
=
1
0
0
P
QA
=
1
0
0
P
1
0
v/a
k1
I
n
−1
a
k1
w
T
0
A
− vw
T
/a
k1
=
1
0
P
v/a
k1
P
a
k1
w
T
0
A
− vw
T
/a
k1
=
1
0
P
v/a
k1
I
n
−1
a
k1
w
T
0
P
(A
− vw
T
/a
k1
)
=
1
0
P
v/a
k1
I
n
−1
a
k1
w
T
0
L
U
=
1
0
P
v/a
k1
L
a
k1
w
T
0
U
= LU
29
Example of LUP Decomposition
2
0
2
0.6
3
3
4
−2
5
5
4
2
−1 −2 3.4 −1
5
5
4
2
3
3
4
−2
2
0
2
0.6
−1
−2 3.4 −1
5
5
4
2
0.6
0
1.6
−3.2
0.4
−2
0.4
−0.2
−0.2
−1 4.2 −0.6
5
5
4
2
0.4
−2
0.4
−0.2
0.6
0
1.6
−3.2
−0.2 −1
4.2
−0.6
5
5
4
2
0.4
−2
0.4
−0.2
0.6
0
1.6
−3.2
−0.2 −0.5
4
−0.5
5
5
4
2
0.4
−2
0.4
−0.2
−0.2 −0.5
4
−0.5
0.6
0
1.6
−3.2
5
5
4
2
0.4
−2
0.4
−0.2
−0.2 −0.5
4
−0.5
0.6
0
0.4
−3
1
2
3
4
3
2
1
4
3
1
2
4
3
1
4
2
So, the permutation is
30
π =
1 2 3 4
3 1 4 2
π[i] = j indicates that the ith
row contains 1 at column j.
The permutation matrix is
P =
0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0
The LUP decomposition is
P A
=
L
U
=
1
0
0
0
0.4
1
0
0
−0.2 −0.5
1
0
0.6
0
0.4
1
5
5
4
2
0
−2 0.4 −0.2
0
0
4
−0.5
0
0
0
−3
LUP Decomposition Algorithm
LUP-D
ECOMPOSITION
(A)
1
n
← rows[A]
2
for i
← 1 to n
3
do π[i]
← i
4
for k
← 1 to n
5
do p
← 0
6
for i
← k to n
7
do if
|a
ik
> p
|
8
then p
← |a
ik
|
9
k
← i
10
if p = 0
11
then error “singular matrix”
12
exchange π[k]
↔ π[k
]
13
for i
← k to n
14
do exchange a
ki
↔ a
k
i
15
for i
← k + 1 to n
16
do a
ik
↔ a
ik
/a
kk
17
for j
← k + 1 to n
18
do a
ij
← a
ij
− a
ik
a
kj
31
Computing Matrix Inverse
Problem 1 The problem of computing the
inverse of A
n
×n
is to find X
n
×n
such that
AX = I
n
(16)
We will prove that
Theorem 2 Matrix multiplication and com-
puting the inverse of a matrix are equivalently
hard problem.
32
Inverse by LUP Decomposition
To solve AX = I
n
is equivalent to solve the
following sets of linear equations:
AX
1
= b
1
, AX
2
= b
2
,
· · · , AX
n
= b
n
where b
i
= (0,
· · · ,
i
−1
0 ,
i
1
,
i+1
0 ,
· · · , 0)
T
.
Algorithm: By LUP decomposition, we get
the column vectors X
1
, X
2
,
· · · , X
n
and X =
(X
1
X
2
· · · X
n
) is the inverse of A.
33
Positive-definite Matrix
Definition 8 A matrix A
n
×n
is called
positive-
definite
(PD) if x
T
Ax > 0 for all size-n vectors
x
= 0.
Example 4 The identity matrix I
n
is positive-
definite because x
T
I
n
x = x
T
x =
n
i=1
x
2
i
.
Homework 3
For any matrix A
m
×n
with full
column rank, the matrix A
T
A is positive-definite.
34
Properties
Property 3 Any positive-definite matrix is nonsigular.
Proof If not,
∃x s.t. Ax = 0, then x
T
Ax = 0 which is
a contradiction with assumption.
Property 4 If A is a symmetric positive-definite (SPD)
matrix, then every leading submatrix of A is symmetric
positive-definite.
Proof It is obvious that the leading submatrix A
k
is
symmetic.
If A
k
is not positive-definite, then there
exists x
k
such that x
T
k
A
k
x
k
≤ 0. Define x = (x
T
k
0)
T
be
a size-n vector, then
x
T
Ax
=
(x
T
k
0)
A
k
B
T
B
C
x
k
0
=
x
T
k
A
k
x
k
≤ 0
which contradicts A being positive-definite.
35
Schur Complement Lemma
Definition 9 Let A be a symmetric positive-
definite (SPD) matrix, and A
k
is the leading
sunmatrix of A. Partition A as
A =
A
k
B
T
B
C
(17)
The
Schur complement
of A with respect to
A
k
is defined by
S = C
− BA
−1
k
B
T
(18)
Lemma 1 Matrix (18) is symmetric and positive-
definite.
36
Proof of Schur’s Lemma
Because A is symmetric, so is the submatrix
C.
And BA
−1
k
B
T
is also symmetric (
home-
work
). Therefore, S is symmetric.
0 < x
T
Ax = (y
T
z
T
)
A
k
B
T
B
C
y
z
= y
T
A
k
y + y
T
B
T
z + z
T
By + z
T
Cz
= (y + A
−1
k
B
T
z)
T
A
k
(y + A
−1
k
B
T
z)+
z
T
(C
− BA
−1
k
B
T
)z
For any z, choose y =
−A
−1
k
B
T
z, then
z
T
(C
− BA
−1
k
B
T
)z = z
T
Sz > 0
37
Why Without Pivoting?
Corollary 1 LU decomposition of a symmet-
ric positive-definite matrix never causes a di-
vision by 0.
Proof If A is symmetric positive-definite, then
a
11
= e
T
1
Ae
1
> 0, where e
1
is the first unit
vector. The the Schur complement of A
1
=
(a
11
) is also symmetric positive-definite, whose
LU keeps on without pivoting.
38
LU Method without Pivoting
Because Ax = b
⇔ A
T
Ax = A
T
b and A
T
A
is symmetric positive-definite matrix, the LU
method for (A
T
A)x = A
T
b does not need piv-
oting. But, in practice,
LUP-D
ECOMPOSITION
still works better than it.
Homework 4
Find out the reason that
LUP-
D
ECOMPOSITION
still works better than LU
method without pivoting.
39
Winograd Theorem
Theorem 3 If we can invert an n
× n matrix in time
I(n) = Ω(n
2
) and I(n) satisfies the
regularity condi-
tion
∗
I(3n) = O(I(n)), then we can multiply two n
× n
matrixes in time O(I(n)).
Proof Given A
n
×n
and B
n
×n
, construct
D =
I
n
A
0
0
I
n
B
0
0
I
n
Then, the inverse of D is
D
−1
=
I
n
−A AB
0
I
n
−B
0
0
I
n
∗
I(n) satisfies regularity condition whenever I(n) =
Θ(n
c
log
d
n) for any constants c > 0, d
≥ 0.
40
Aho-Hopcroft-Ullman Theorem
Theorem 4 Suppose we can multiply two n
×
n matrixes in time M (n) = Ω(n
2
) and M (n)
satisfies the two regularity conditions:
1. M (n + k) = O(M (n)) for 0
≤ k ≤ n, and
2. M (n/2)
≤ cM(n) for some constant c < 1/2.
Then, we can compute the inverse of any real
nonsingular n
× n matrix in time O(M(n)).
Note
For convenience, Aho-Hopcroft-Ullman
is abbreviated by AHU.
41
Proof of AHU Theorem
Step 1: Let A
n
×n
be a symmetric positive-definite ma-
trix, where n is an exact power of 2. We partition A
into four
n
2
×
n
2
matrixes just like (17). Then
A
−1
=
B
−1
+
B
−1
C
T
S
−1
CB
−1
−
B
−1
C
T
S
−1
−
S
−1
CB
−1
S
−1
(19)
We just need four multiplications of
n
2
×
n
2
matrixes:
(1) K = CB
−1
, (2) CB
−1
C
T
= KC
T
, (3)
L
= S
−1
CB
−1
=
S
−1
K, (4) (CB
−1
)
T
(S
−1
CB
−1
) =
KL
Thus, we have the recursion:
I(n)
≤ 2I(n/2) + 4M(n/2) + O(n
2
)
=
2I(n/2) + Θ(M (n))
//because M (n) = Ω(n
2
)
=
O(M (n))
//Master Theorem (3)
Step 2: For any given invertible A, A
−1
= (A
T
A)
−1
A
T
.
42
Application of SPD Matrix
One important application of SPD matrix is
the method of
least-squares approximation
.
Problem 2 Given a sample
{(x
1
, y
1
), (x
2
, y
2
),
· · · , (x
m
, y
m
)
}, to estimate the c
i
’s in F (x) =
n
i=1
c
i
f
i
(x) such that
m
i=1
(F (x
i
)
− y
i
)
2
=
m
i=1
η
2
i
(20)
reaches the least, where η
i
is called the
ap-
proximation error
.
43
Regression Analysis
44
Representation in Matrix
Definition 10 Define m
× n matrix A, define
two size-n vectors c and η:
A =
f
1
(x
1
)
f
2
(x
1
)
· · ·
f
n
(x
1
)
f
1
(x
2
)
f
2
(x
2
)
· · ·
f
n
(x
2
)
..
.
f
1
(x
m
)
f
2
(x
m
)
· · ·
f
n
(x
m
)
, c =
c
1
c
2
..
.
c
n
, η =
η
1
η
2
..
.
η
n
then η = Ac
− y.
The problem of (20) is just to minimize
η
2
=
Ac − y
2
=
m
i=1
n
j=1
a
ij
c
j
− y
i
2
(21)
45
Pseudoinverse
Definition 11 For any matrix A
m
×n
, A
+
=
(A
T
A)
−1
A
T
is called the
pseudoinverse
of A.
Property 5 If A is an m
× n matrix, then its
pseudoinverse is an n
× m matrix.
Note
Pseudoinverse is a generalization of in-
verse when A is not square.
Why do we need pseudoinverse?
46
Least-squares Approximation
Because
∂
η
2
∂c
k
=
m
i=1
2
n
j=1
a
ij
c
j
− y
i
a
ik
= 0
thus c is the solution of
(Ac
− y)
T
A = 0
or
A
T
(Ac
− y) = 0
Therefore, c = ((A
T
A)
−1
A
T
)y = A
+
y.
Theorem 5 The solution of least-squares ap-
proximation is c = A
+
y.
Note
In practice, Firstly A
T
y, then finding
an LU decomposition of A
T
A.
47
Example of Least Square
Example 5 Let (x
1
, y
1
) = (
−1, 2), (x
2
, y
2
) = (1, 1), (x
3
, y
3
) =
(2, 1), (x
4
, y
4
) = (3, 0), (x
5
, y
5
) = (5, 3), and the ap-
proximation function is F (x) = c
1
+ c
2
x + c
3
x
2
. Then
A =
1
x
1
x
2
1
1
x
2
x
2
2
1
x
3
x
2
3
1
x
4
x
2
4
1
x
5
x
2
5
=
1
−1
1
1
1
1
1
2
4
1
3
9
1
5
25
The pseudoinverse of A is:
A
+
=
0.500
0.300
0.200
0.100
−0.100
−0.388
0.093
0.190
0.193
−0.088
0.060
−0.036 −0.048 −0.036
0.060
Multiply y by A
+
, we get c =
1.200
−0.757
0.214
, then the
approximation function is 1.200
− 0.757x + 0.214x
2
.
48
Homework
Homework 5
Find the function of the form
F (x) = c
1
+ c
2
xlogx + c
3
e
x
that is the best least-squares fit to the data
points: (1, 2), (2, 1), (3, 3), (4, 8).
Homework 6
Solve the following equation by
LUP decomposition:
1 5 4
2 0 3
5 8 2
x
1
x
2
x
3
=
12
9
5
49
Conclusion
1. The properties of symmetric positive-definite
matrix are quite interesting.
2. We have not known the exact complex-
ity of matrix multiplication and comput-
ing the inverse of matrix.
3. Singular Value Decomposition (SVD) method
is also important in Matrix Computation.
50
References
1. T. H. Cormen, C. E. Leiserson, R. L.
Rivest and C. Stein (2001),
Introduction
to Algorithms
(the second edition). The
MIT Press
2. G. H. Golub and C. F. von Loan (1996),
Matrix Computation
. The Johns Hopkins
University Press.
3. H. S. Wilf (1994),
Algorithm and Com-
plexity
.
Draft of the Internet edition at
http://www.cis.upenn.edu/wilf
51
Thank you
for your attention!
Wyszukiwarka
Podobne podstrony:
The uA741 Operational Amplifier[1]
operatory i funkcje matematyczne
operator maszyn lesnych 833[02] o1 03 n
mechanik operator pojazdow i maszyn rolniczych 723[03] z2 04 n
Kierowca operator wózków jezdniowych 833401
mechanik operator pojazdow i maszyn rolniczych 723[03] o1 05 u
OPERAT STABLE VERSION ugoda id Nieznany
operator urzadzen przemyslu szklarskiego 813[02] z2 07 n
4 Steyr Operation and Maintenance Manual 8th edition Feb 08
operator urzadzen przemyslu spozywczego 827[01] z2 02 u
mechanik operator pojazdow i maszyn rolniczych 723[03] z3 02 n
więcej podobnych podstron