Background Information and Techniques - Computer Animation: Algorithms and Techniques - page 409

Ly ¼ b
L 11 000
L 21

2 3 2 3 2 3

y 1
y 2
y 3
y 4

b 1
b 2
b 3
b 4

4 5 4 5 ¼ 4 5

L 22 00

L 31 L 32 L 33

0

L 41 L 42 L 43 L 44

First row : L 11 y 1 ¼ b 1

y 1 ¼ b 1 =L 11

(B.12)

Second row : L 21 y 1 þ L 22 y 2 ¼ b 2

y 2 ¼ b 2 ð L 21 y 1 ð Þ Þ=L 22

: L 31 y 1 þ L 32 y 2 þ L 33 y 3 ¼ b 3

y 3 ¼ b 3 L 31 y 1 L 32 y 2

Third row

ð ð Þ Þ=L 33

Fourth row : L 41 y 1 þ L 42 y 2 þ L 43 y 3 þ L 44 y 4 ¼ b 4

y 4 ¼ b 4 L 41 y 1 ð ð Þ L 42 y 2 ð Þ L 43 y 3 ð Þ Þ=L 44

The decomposition procedure sets up equations and orders them so that each is solved simply.
Given the matrix equation for the decomposition relationship, one can construct equations on a term-
by-term basis for the A matrix. This results in N

2 equations with N 2

þ N unknowns. As there are more
unknowns than equations, N elements are set to some arbitrary value. A particularly useful set of values
is L ii ¼ 1.0. Once this is done, the simplest equations (for A 11 , A 12 , etc.) are used to establish values for

some of the L and U elements. These values are then used in the more complicated equations. In this
way the equations can be ordered so there is only one unknown in any single equation by the time it is
evaluated. Consider the case of a 4

4 matrix. Equation B.13 repeats the original matrix equation for
reference and Equation B.14 shows the resulting sequence of equations in which the underlined
variable is the only unknown.

2
4

3
5

2
4

3
5 ¼

2
4

3
5

1000
L 21 100
L 31

U 11 U 12 U 13 U 14
0 U 22 U 23 U 24
00 U 33 U 34
000 U 44

A 11 A 12 A 13 A 14

A 21 A 22 A 23 A 24

(B.13)

L 32 10 A 31 A 32 A 33 A 34

L 41 L 42 L 43 1 A 41 A 42 A 43 A 44

For the first column of A
U 11 ¼ A 11
L 21 U 11 ¼ A 21
L 31 U 11 ¼ A 31
L 41 U 11 ¼ A 41

(B.14)

For the second column of A
U 12 ¼ A 12
L 21 U 12 þ U 22 ¼ A 22
L 31 U 12 þ L 32 U 22 ¼ A 32
L 41 U 12 þ L 42 U 22 ¼ A 42