```python
# This cell is for the Google Colaboratory
# https://stackoverflow.com/a/63519730
if 'google.colab' in str(get_ipython()):
  # https://colab.research.google.com/notebooks/io.ipynb
  import google.colab.drive as gcdrive
  # may need to visit a link for the Google Colab authorization code
  gcdrive.mount("/content/drive/")
  import sys
  sys.path.insert(0,"/content/drive/My Drive/Colab Notebooks/nmisp/60_linear_algebra_2")

```


```python
import numpy as np
import numpy.random as nr
import sympy as sy
import IPython.display as disp

sy.init_printing()


```

# 선형 연립 방정식<br>Systems of Linear Equations



미지수가 3개인 선형 연립 방정식을 생각해 보자.<br>Let's think about a system of linear equations with three unknowns.




```python
n = 3

x = np.array(sy.symbols(f'x:{n}'))
x


```

세 미지수를 모두 결정하려면, 보통 세개의 서로 선형 독립인 방정식이 필요하다.<br>To decide all three unknowns, usually we need three linearly independent equations.




```python
a = np.array(sy.symbols(
    f'a:{n}(:{n})'
)).reshape((n, n)).tolist()

b = sy.symbols(f'b:{n}')


```


```python
eqs = []
for coefs, const in zip(a, b):
    lhs = sum([aij * xj for aij, xj in zip(coefs, x)])
    eq = sy.Eq(lhs, const)
    eqs.append(eq)
    disp.display(eq)


```

행렬 형태로 정리해 보자<br>Let's rewrite in the matrix form




```python
matA = sy.Matrix(a)
vecB = sy.Matrix(b)
vecX = sy.Matrix(x)

eq_mat = sy.Eq(matA * vecX, vecB)

eq_mat


```

여기서 계수 행렬과 상수 벡터만 생각해 보자.<br>Here, let's just think about the coefficient matrix and constant vector.




```python
matAb = matA.col_insert(n, vecB)
matAb


```

## 가우스 소거법<br>Gauss Elimination



다음 비디오는 가우스 소거법을 소개한다.<br>
The following video introduces the Gauss Elimiation. (00:17 ~ 18:57)

[](https://www.youtube.com/watch?v=QVKj3LADCnA&list=PLE7DDD91010BC51F8&index=3&start=18&end=1137&version=3)



비디오에서 제시한 연립 방정식을 생각해 보자.<br>
Let's think about the system of equations of the video.




```python
A = np.array([
    [1, 2, 1],
    [3, 8, 1],
    [0, 4, 1],
])
A


```


```python
b = np.array([
    [2, 12, 2]
]).T
b


```

행렬 A와 벡터 b를 붙인다.<br>
Let's augument matrix A and b.




```python
Ab = np.hstack((A, b))
Ab


```

우선 첫 행의 첫 열 원소에 pivot 이라는 이름을 준다.<br>First, let's designate the first element of the first row as pivot.




```python
p = 0
pivot = Ab[p, p]
pivot


```

두번째 행 첫 열 원소를 pivot 으로 나눈 비를 계산한다.<br>
Divide the element at the first column of the second row with pivot




```python
i = p + 1
multiplier = Ab[i, p] / pivot
multiplier


```

첫 행에 이 비를 곱한 후 둘째 행에서 뺀다.<br>Multiply the first row with this multiplier and subtract from the second row.




```python
Ab[i, :] = Ab[i, :] + (- multiplier) * Ab[p, :]
Ab


```

두번째 행 첫번째 열이 0이 되었음을 알 수 있다.<br>
We can see that the second row first column is now zero.



세번째 행 첫번째 열은 이미 0이다.<br>
The third row first column is already zero.



이제 p 에 1을 더하고 반복하자.<br>Now let's add 1 to `p` and repeat.




```python
p += 1
pivot = Ab[p, p]
pivot


```

`p+1` 행 `p` 열 원소를 `pivot` 으로 나눈 비를 계산한다.<br>
Divide the element at the `p`th column of the `p+1`th row with pivot




```python
i = p + 1
multiplier = Ab[i, p] / pivot
multiplier


```

`p` 행에 이 비를 곱한 후 `p+1` 행에서 뺀다.<br>
Multiply the `p`th row with this multiplier and subtract from the `p+1`th row.




```python
Ab[i, :]  = Ab[i, :] + (- multiplier) * Ab[p, :]
Ab


```

이런 식으로 왼쪽 위로부터 오른쪽 아래로의 주대각선 아래 원소를 모두 0으로 만든다.<br>This way, make all elements below main diagonal, from the left upper corner to the right lower direction, zero.



## 후진대입법<br>Backward substitution



주대각선 아래가 모두 0이라면 아래와 같이 생각해 볼 수 있다.<br>If all elements below the main diagonal are zeros, we may think as follows.




```python
alpha = np.array(sy.symbols(
    f'alpha:{n}(:{n})'
)).reshape((n, n)).tolist()

beta = sy.symbols(f'beta:{n}')


```


```python
eqs2 = []
for p in range(n):
    
    lhs_list = []
    for i in range(p, n):
        lhs_list.append(alpha[p][i]*x[i])

    eq = sy.Eq(sum(lhs_list), beta[p])
    eqs2.append(eq)

for eq in eqs2:
    disp.display(eq)


```

맨 마지막 행에서 마지막 미지수를 알 수 있다.<br>
From the last row, we can find the last unknown.




```python
sol = sy.Matrix([None] * n)


```


```python
sol_n_1 = sy.solve(eqs2[-1], x[-1])
sol[-1] = sol_n_1[0]
disp.display(sol)


```

그 하나 앞 미지수는 마지막에서 두번째 방정식에서 구할 수 있다.<br>We can find the second last unknown from the second last equation.




```python
eqs2[-2].subs(x[-1], sol[-1])


```


```python
sol_n_2 = sy.solve(eqs2[-2].subs(x[-1], sol[-1]), x[-2])
sol[-2] = sol_n_2[0]
disp.display(sol)


```

반복하면 모든 해를 구할 수 있다.<br>We can find all solutions this way.



## `numpy.linalg`



`numpy.linalg` 의 `solve()` 함수를 이용할 수도 있다.<br>We can use `solve()` of `numpy.linalg`.




```python
import numpy.linalg as nl

x_sol = nl.solve(A, b)
x_sol


```


```python
import numpy.testing as nt
nt.assert_array_almost_equal(A@x_sol, b)


```

## 소거행렬<br>Elimination matrix



위에서 소개했던 행열 연산을 행하는 행렬을 생각할 수 있다.<br>
We can think about a matrix carrying out row-column operations above. (20:41 ~ 36:26)

[](https://www.youtube.com/watch?v=QVKj3LADCnA&list=PLE7DDD91010BC51F8&index=3&start=1242&end=2186)


2행1열 소거:<br>
Eliminate row 2 column 1:




```python
E21 = np.array([
    [1, 0, 0],
    [-3, 1, 0],
    [0, 0, 1]
])


```


```python
E21 @ A


```

3행2열 소거:<br>
Eliminate row 3 column 2:




```python
E32 = np.array([
    [1, 0, 0],
    [0, 1, 0],
    [0, -2, 1]
])


```


```python
E32 @ (E21 @ A)


```

교환법칙은 성립하는가?<br>
Commutative?




```python
E21 @ E32 @ A
```

결합법칙은 성립하는가?<br>
Associative?




```python
(E32 @ E21) @ A


```

위 두 행렬의 곱:<br>
Product of the two matrices above:




```python
E = E32 @ E21


```


```python
E


```

E 행렬과 A 행렬의 곱은 상삼각 행렬이다.<br>
The product of matricies of E and A is the upper triangular matrix.




```python
E @ A


```

## 표준 기능으로 구현한 가우스 소거법<br>Gauss Elimination in Standard library



다음 셀은 가우스 소거법을 표준기능 만으로 구현한다.<br>
Following cell implements the Gauss elimination with standard library only.




```python
import typing

Scalar = typing.Union[int, float]
Row = typing.List[Scalar]
Matrix = typing.List[Row]


def gauss_elimination(Ab:Matrix) -> None:
    # pivot loop
    for p in range(0, len(Ab)-1):
        pivot = Ab[p][p]
        one_over_minus_pivot = -1.0 / pivot

        # row loop
        for i in range(p+1, len(Ab)):
            multiplier = Ab[i][p] * one_over_minus_pivot
            
            # column loop
            for j in range(p, len(Ab[p])):
                Ab[i][j] += multiplier * Ab[p][j]


```

위 행렬의 예로 확인해 보자.<br>
Let's check with the matrix above.




```python
Ab_list = [
    [1, 2, 1,  2],
    [3, 8, 1, 12],
    [0, 4, 1,  2],
]


```


```python
gauss_elimination(Ab_list)


```


```python
import pprint
pprint.pprint(Ab_list, width=40)


```

다음 셀은 후진대입법을 표준기능 만으로 구현한다.<br>
Following cell implements the back substitution with standard library only.




```python
def back_substitution(Uc:Matrix) -> Row:

    # number of unknowns
    n = len(Uc)
    result = [None] * n
    
    # last unknown
    result[n-1] = Uc[n-1][n] / Uc[n-1][n-1]

    # row loop from second last to the first unknowns
    for i in range(n-2, 0-1, -1):
        s = Uc[i][n]

        # column loop
        for j in range(i+1, n-1+1):
            s += (-1) * result[j] * Uc[i][j]
        result[i] = s / Uc[i][i]

    return result


```


```python
back_substitution(Ab_list)


```

## 연습 문제<br>Exercise



위 방법을 적용 가능한 공학 문제 사례를 설명하고 `numpy.linalg.solve()`로 해를 구해 보시오. 이렇게 구한 해가 맞는지 어떻게 확인할 수 있는가?<br>
Describe an engineering problem that we can apply the method above and find the solution using `numpy.linalg.solve()`. How can we verify if the solution is correct?



## 참고문헌<br>References



* Gilbert Strang. 18.06 Linear Algebra. Spring 2010. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu. License: Creative Commons BY-NC-SA.

## Final Bell<br>마지막 종




```python
# stackoverfow.com/a/24634221
import os
os.system("printf '\a'");


```


```python

```

0a2bd69bfb61b9542fae8fb20fab19ad2ac6f5f9
ipynb
Jupyter Notebook
60_linear_algebra_2/100_Systems_of_Linear_Equations.ipynb
kangwonlee/2109eca-nmisp-template
2e078870757fa06222df62d0ff8f4f4f288af51a
BSD-3-Clause
60_linear_algebra_2/100_Systems_of_Linear_Equations.ipynb
kangwonlee/2109eca-nmisp-template
2e078870757fa06222df62d0ff8f4f4f288af51a
BSD-3-Clause
60_linear_algebra_2/100_Systems_of_Linear_Equations.ipynb
kangwonlee/2109eca-nmisp-template
2e078870757fa06222df62d0ff8f4f4f288af51a
BSD-3-Clause
Qwen/Qwen-72B
1. YES
2. YES