🔠 Linear Algebra
Linear Algebra - [ 04. Factorization into A = LU ]
date
Jun 11, 2023
slug
linear-algebra-04
author
status
Public
tags
Linear Algebra
summary
Factorization into A = LU
type
Post
thumbnail
category
🔠 Linear Algebra
updatedAt
Jul 28, 2023 07:30 AM
- "Lec 4 | MIT 18.06 선형대수학, 2005년 봄"
- 이 강의에서는 행렬의 곱의 역원에 대해 이야기합니다.
- A와 B가 역원을 가지고 있을 때, A와 B의 곱인 AB의 역원은 B의 역원과 A의 역원을 역순으로 곱한 것입니다.
- 또한, 행렬의 전치(transpose)에 대해 이야기합니다. A의 역원의 전치는 A의 전치의 역원과 같습니다.
- 이러한 기본 사실들을 사용하여 가우스 소거법을 이해하는 방법과 L, U, A 간의 관계를 설명합니다. L은 하삼각행렬(lower triangular matrix)이며, U는 상삼각행렬(upper triangular matrix)입니다.
- 행렬의 연산량에 대해 논의하고, 행렬 분해를 통해 시스템 방정식을 효율적으로 해결할 수 있는 알고리즘을 설명합니다.
What’s the inverse of a product?
If I multiply two matrices together and I know their inverses, how do I get the inverse of A times B?
What matrix do I multiply by to get the identity if I have AB?
I will be have a product of matrices and the product that we’ll meet will be these elimination matrices and the net result of today’s lecture is the big formula for elimination.
So the net result of today’s lecture is this great way to look at Gaussian elimination.
If I transpose one, what’s its inverse?
This equation tells me what I wanted to know, namely what is the inverse of this guy A transpose?
And this equation tells me that inverse of (A^T)^-1 is (A^-1)^T
Why A = LU ?
<two by two>
Well, first. So how is related to E_21? It’s the inverse.
<three by three>
L is product of inverses.
Now you can still can ask why is this guy preferring inverses?
And let me explain why is the right hand side product nicer than the left hand side product.
The order that the matrices come for L is the right order.
The 2 and 5 don’t sort of interfere to produce 10.
In the right order, the multipliers just sit in the matrix L. That’s the point.
If I want to know L, I have no work to do.
⇒ A = Lu If no row exchanges, multipliers go directly into L.
So, this is the way to look at elimination.
can we think together how expensive is elimination?
How many operations on n x n elimination A? ex) n =100
first step of elimination
second step of elimination
In first step, about 100^2 operations. (정확하게는 99 x 100. 첫 줄은 계산하지 않으니까)
In second step, about 99^2 operations. (99 x 98)
결국, n^2 + (n-1)^2 + … 2^2 + 1^2 = 1/3 n^3 (적분 개념)
Cost of b = n^2
We pay the higher price on A to get it split up into L and u to do elimination on A,
but then we can process every right hand side at low cost.
Preview next lecture
I’m ready to allow row exchanges.
permutations
P^-1 = P^T
3 x 3 = 6 P’s , 4 x 4 = 24 P’s