How to solve Ax=b

How to solve Ax=b

Wanho Choi (wanochoi.com)

Many engineering problems result in

• A system of linear equations (n unknowns, n eqns.)

a

₁₁

x

₁

+ a

₁₂

x

₂

+!+ a

_1n

x

_n

= b

₁

a

₂₁

x

₁

+ a

₂₂

x

₂

+!+ a

_2n

x

_n

= b

₂

"

Many engineering problems result in

• A system of linear equations (n unknowns, n eqns.)

a

₁₁

a

₁₂

! a

_1n

a

₂₁

a

₂₂

! a

_2n

"

"

#

"

a

_n1

a

_n2

! a

_nn

⎡

⎣

⎢

⎢

⎢

⎢

⎢

⎤

⎦

⎥

⎥

⎥

⎥

⎥

x

₁

x

₂

"

x

_n

⎡

⎣

⎢

⎢

⎢

⎢

⎢

⎤

⎦

⎥

⎥

⎥

⎥

⎥

=

b

₁

b

₂

"

b

_n

⎡

⎣

⎢

⎢

⎢

⎢

⎢

⎤

⎦

⎥

⎥

⎥

⎥

⎥

A Linear System

• A system of linear equations (n unknowns, n eqns.)

Ax

= b

Exceptional Cases

• Singular case:

‣ Infinite amount of solutions (부정)

‣ No solutions (불능)

• _{Under-determined case: fewer eqns. than unknowns}

‣ Infinite amount of solutions (부정)

• Over-determined case: more eqns. than unknowns

‣ No solutions (불능)

(# of rows) < (# of columns)

(# of rows) > (# of columns)

det(A)

= 0

Solutions: Ax=b

• Invert A ‣ Very expensive • Direct methods ‣ Gaussian elimination ‣ LU-factorization ‣ QR-factorizaiton ‣ Cholesky-factorization ‣ etc. • Iterative methods ‣ Jacobi method ‣ Gauss-Seidel

‣ Successive Over Relaxation (SOR)

‣ Steepest descent, (preconditioned) conjugate gradient

‣ etc.

Triangular Matrix

L = a_1,1 0 ! 0 0 a_2,1 a_2,2 ! 0 0 ! ! " ! ! a_n−1,1 a_n−1,2 ! a_n−1,n−1 0 a_n,1 a_n,2 ! a_n,n−1 a_n,n ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ U = a_1,1 a_1,2 ! a_1,n−1 a_1,n 0 a_2,2 ! a_2,n−1 a_2,n ! ! " ! ! 0 0 ! a_n−1,n−1 a_n−1,n 0 0 ! 0 a_n,n ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥

lower triangular matrix upper triangular matrix

• A technique to solve Ax=b

when A=L with non-zero diagonal elements

Forward Substitution

a_1,1 0 ! 0 0 a_2,1 a_2,2 ! 0 0 ! ! " ! ! a_n−1,1 a_n−1,2 ! a_n−1,n−1 0 a_n,1 a_n,2 ! a_n,n−1 a_n,n ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ x₁ x₂ ! x_n−1 x_n ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ = b₁ b₂ ! b_n−1 b_n ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ x₁ = b₁/ a_1,1 x₂ = b( ₂− a_2,1x₁)/ a_2,2 x₃ = b( ₃− a_3,1x₁− a_3,2x₂)/ a_3,3 ! x_n = b( _n− a_n,1x₁− a_n,2x₂ −!− a_n,n−1x_n−1)/ a_n,n cost : 1+ 3+ 5 +!+ (2n −1) = n2 flops

• A technique to solve Ax=b

when A=U with non-zero diagonal elements

Backward Substitution

a_1,1 a_1,2 ! a_1,n−1 a_1,n 0 a_2,2 ! a_2,n−1 a_2,n ! ! " ! ! 0 0 ! a_n−1,n−1 a_n−1,n 0 0 ! 0 a_n,n ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ x₁ x₂ ! x_n−1 x_n ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ = b₁ b₂ ! b_n−1 b_n ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ x_n = b_n / a_n,n x_n−1 = b( _n−1− a_n−1,nx_n)/ a_n−1,n−1 x_n−2 = b( _n−2 − a_n−2,n−1x_n−1− a_n−2,nx_n)/ a_n−2,n−2 ! x₁ = b( ₁− a_1,2x₂ − a_1,3x₃−!− a_1,nx_n)/ a_1,1 cost : 1+ 3+ 5 +!+ (2n −1) = n2 flops

Gaussian Elimination

• Exists for any non-singular square matrix

2 4 −2 4 9 −3 −2 −3 7 ⎡ ⎣ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ x y z ⎡ ⎣ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ = 2 8 10 ⎡ ⎣ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ 2x + 4y − 2z = 2 4x + 9y − 3z = 8 −2x − 3y + 7z = 10 2x +4y −2z = 2 4x +9y −3z = 8 −2x −3y +7z = 10 2x +4y −2z = 2 y + z = 4 y +5z = 12 2x +4y −2z = 2 y + z = 4 +4z = 8

LU Factorization

• Exists for any non-singular square matrix

Ax

= b

LUx

= b

y

= Ux

Ly

= b

L = * 0 0 0 * * 0 0 * * * 0 * * * * ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ U = * * * * 0 * * * 0 0 * * 0 0 0 * ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ forward substitution backward substitution

QR Factorization

• Exists for any non-singular square matrix

Ax

= b

QUx

= b

y

= Ux

Qy

= b

U = * * * * 0 * * * 0 0 * * 0 0 0 * ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ backward substitution Q−1 = QT

Cholesky Factorization

• Exists for a square symmetric positive definite matrix

Ax

= b

LL

T

x

= b

y

= L

T

x

Ly

= b

L = * 0 0 0 * * 0 0 * * * 0 * * * * ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ LT = * * * * 0 * * * 0 0 * * 0 0 0 * ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ forward substitution backward substitution A = ΦΛΦT _{= ΦΛ}1/2_Λ1/2_ΦT _{= (ΦΛ}1/2_{) (ΦΛ}1/2₎T _{= LL}T

Cholesky Factorization

A

= LL

T a₁₁ A₂₁T A₂₁ A₂₂ ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ = l₁₁ 0 L₂₁ L₂₂ ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ l₁₁ 0 L₂₁ L₂₂ ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ T = l11 0 L₂₁ L₂₂ ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ l₁₁ LT₂₁ 0 LT₂₂ ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ∴ a11 A21 T A₂₁ A₂₂ ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ = l₁₁2 l₁₁LT₂₁ l₁₁L₂₁ L₂₁LT₂₁ + L₂₂LT₂₂ ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ a₁₁ = l₁₁2 A₂₁T = l₁₁LT₂₁ A₂₁ = l₁₁L₂₁ A₂₂ = L₂₁LT₂₁ + L₂₂LT₂₂ ⇔ l₁₁ = a₁₁ ⇔ − ⇔ L₂₁ = A₂₁ / l₁₁ ⇔ L₂₂LT₂₂ = A₂₂ − L₂₁LT₂₁

Jacobi Iteration

a₁₁x₁ + a₁₂x₂ +!+ a_1nx_n = b₁ a₂₁x₁ + a₂₂x₂ +!+ a_2nx_n = b₂ " a_n1x₁ + a_n2x₂ +!+ a_nnx_n = b_n x₁1 = 1 a₁₁ b1 − a12x2 0 −!− a 1nxn 0

(

)

x₂1 = 1 a₂₂ b2 − a21x1 0 −!− a 2nxn 0

(

)

! x_n1 = 1 a_nn bn − an1x1 0 −"− a n−1n−1xn−1 0

(

)

x0 = x₁0 x₂0 ! x_n0 ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ x_ik+1 = 1 a_ii bi − aijxj k j=1 i−1

∑

− a_ijxk_j j=i+1 n

∑

⎛ ⎝⎜ ⎞ ⎠⎟

Gauss-Seidel Iteration

a₁₁x₁ + a₁₂x₂ +!+ a_1nx_n = b₁ a₂₁x₁ + a₂₂x₂ +!+ a_2nx_n = b₂ " a_n1x₁ + a_n2x₂ +!+ a_nnx_n = b_n x₁1 = 1 a₁₁ b1− a12x2 0 −!− a 1nxn 0

(

)

x₂1 = 1 a₂₂ b2 − a21x1 1−!− a 2nxn 0

(

)

! x_n1 = 1 a_nn bn − an1x1 1−"− a n−1n−1xn−1 1

(

)

x0 = x₁0 x₂0 ! x_n0 ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ x_ik+1 = 1 a_ii bi − aijxj k+1 j=1 i−1

∑

− a_ijxk_j j=i+1 n

∑

⎛ ⎝⎜ ⎞ ⎠⎟

Jacobi vs Gauss-Seidel

x_ik+1 = 1 a_ii bi − aijxj k j=1 i−1

∑

− a_ijx_jk j=i+1 n

∑

⎛ ⎝⎜ ⎞ ⎠⎟ xi k+1 = 1 a_ii bi − aijxj k+1 j=1 i−1

∑

− a_ijxk_j j=i+1 n

∑

⎛ ⎝⎜ ⎞ ⎠⎟ Ax = b ⇒ L + D + U

(

)

x = b Dxk+1 = − L + U

(

)

xk + b

(

D + L

)

xk+1 = −Uxk + b Lxk Uxk Dxk+1 Dxk+1 Lxk+1 Uxk

Jacobi vs Gauss-Seidel

• Gauss-Seidel converges more rapidly than Jacobi.

• _{Simple to implement}

• _{No need for sparse data structure}

• _{Low memory consumption O(n)}

• _{Easy to parallelize}

• The convergence of the problem depends on the

diagonality of the matrix.

• Fortunately, Laplacian operator is a diagonal dominant operator.

Steepest Descent Method

• If is symmetric positive-definite,

solving is equivalent to minimizing

_Ax

= b

f (x)

=

1

2

x

T

Ax

− b

T

x

+ c

λ_i > 0 i = 1,2,!,n

(

)

⇒ xT Ax = xT

(

VΛVT

)

x = xTVΛVTx = V

( )

Tx T Λ V

( )

Tx = dTΛd > 0 AT = A ∵symmetric

(

)

⇒ ∇f (x) = 1 2 A T x + 1 2 Ax − b = Ax − b = 0 ∴concave up

A

Steepest Descent Method

• A specific example f (x) = 1 2 x T Ax − bTx + c A = 3 2 2 6 ⎡ ⎣ ⎢ ⎤ ⎦ ⎥,b = ⎡ ₋₈2 ⎣ ⎢ ⎤ ⎦ ⎥,c = 0 ⇒ x = ⎡ ₋₂2 ⎣ ⎢ ⎤ ⎦ ⎥

energy function contours

Steepest Descent Method

• Given:

• _{Where is ? LINE SEARCH ALGORITHM}

• _{Let’s go to the direction in which decreases}

most quickly! ‣ Direction: ‣ Amount:

x

k

x

k+1

f (x)

d

k

= −∇f (x

k

)

= − Ax

(

k

− b

)

= −r

k

α

k

= ?

d dα k f x k +αk rk

(

)

= 0 → ∇f xk +αk rk

(

)

T rk = 0 ∴αk = r k

( )

T rk rk

( )

T Ark residual

x

k+1

= x

k

+

α

k

d

k

Conjugate Gradient Method

• Better directions than “Steepest Descent Method”

• _{It improves “Steepest Descent” by avoiding}

repetitious steps.

• _{Only walking once in each direction}

• _{Orthogonal w.r.t the system matrix}

• _{It can reach the solution in steps.}

• Ideal directions are the eigenvectors of .

• Instead of eigenvectors, however, which are too hard

to compute, use “conjugate” or “A-orthogonal” directions.

A

x

n

Conjugate Gradient Method

Preconditioning

• To improve the condition number of a matrix

• _{: symmetric, positive-definite that approximates ,}

but easier to invert

• _{The eigenvalues of are better clustered than}

those of .

M

−1

Ax

= M

−1

b

M

A

M

−1

A

A