<a href="https://colab.research.google.com/github/tnaka78/mit_ocw_1806_spring_2005/blob/master/lecture02.ipynb" target="_parent"></a>


```
import numpy as np
```

# Lecture 2: Elimination with Matrices
講義動画：https://www.youtube.com/watch?v=QVKj3LADCnA

## 消去法 (Elimination)

$$
\begin{align}
x+2y+z &=2 \tag{1} \\
3x+8y+z&=12 \tag{2} \\
4y+z&=2 \tag{3}
\end{align}
$$

これを$Ax=b$の形にすると、$A$は次のように表される。
$$
A = \left[
  \begin{array}{ccc}
    1 & 2 & 1 \\
    3 & 8 & 1 \\
    0 & 4 & 1 \\
  \end{array}
\right]
$$

まず$(2)-(1)\times{}3$で$A_{2,1}$を0にする。→これで1列目のピボットができる。
$$
\left[
  \begin{array}{ccc}
    \bf{1} & 2 & 1 \\
    0 & 2 & -2 \\
    0 & 4 & 1 \\
  \end{array}
\right]
$$

次に、$(3)-(2)\times{}2$で$A_{3,2}$を0にする。→これで2列目と3列目のピボットができる。→これが上三角形(upper triangle)
$$
\left[
  \begin{array}{ccc}
  \bf{1} & 2 & 1 \\
  0 & \bf{2} & -2 \\
  0 & 0 & \bf{5} \\
  \end{array}
\right] = U
$$

ピボットの位置がすでに0だったら、それより下の行と入れ替える。

上記に$b$の列を追加してみる。

$$
\left[
  \begin{array}{ccc|c}
    1 & 2 & 1 & 2 \\
    3 & 8 & 1 & 12 \\
    0 & 4 & 1 & 2 \\
  \end{array}
\right]
$$

$(2)-(1)\times{}3$
$$
\left[
  \begin{array}{ccc|c}
    1 & 2 & 1 & 2 \\
    0 & 2 & -2 & 6 \\
    0 & 4 & 1 & 2 \\
  \end{array}
\right]
$$

$(3)-(2)\times{}2$
$$
\left[
  \begin{array}{ccc|c}
  1 & 2 & 1 & 2 \\
  0 & 2 & -2 & 6 \\
  0 & 0 & 5 & -10 \\
  \end{array}
\right]
$$

これにより、次の式を得る。
$$
\begin{align}
x+2y+z &=2 \\
2y-2z&=6 \\
5z&=-10
\end{align}
$$

ここから、$z=-2, y=1, x=2$が導き出せる。

行列×列＝列

$$
\left[
  \begin{array}{ccc}
    A_{1, 1} & A_{1, 2} & A_{1, 3} \\
    A_{2, 1} & A_{2, 2} & A_{2, 3} \\
    A_{3, 1} & A_{3, 2} & A_{3, 3} \\
  \end{array}
\right] \left[
  \begin{array}{c} a \\ b \\ c \end{array}
\right] = a\left[
  \begin{array}{c} A_{1,1} \\ A_{2,1} \\ A_{3,1} \end{array}
\right]+b\left[
  \begin{array}{c} A_{1,2} \\ A_{2,2} \\ A_{3,2} \end{array}
\right]+c\left[
  \begin{array}{c} A_{1,3} \\ A_{2,3} \\ A_{3,3} \end{array}
\right]
$$

行×行列＝行

$$
 \left[
  \begin{array}{ccc}
    a & b & c
  \end{array}
\right] \left[
  \begin{array}{ccc}
    A_{1, 1} & A_{1, 2} & A_{1, 3} \\
    A_{2, 1} & A_{2, 2} & A_{2, 3} \\
    A_{3, 1} & A_{3, 2} & A_{3, 3} \\
  \end{array}
\right] = a\left[
  \begin{array}{ccc} A_{1,1} & A_{2,1} & A_{3,1} \end{array}
\right]+b\left[
  \begin{array}{ccc} A_{2,1} & A_{2,2} & A_{2,3} \end{array}
\right]+c\left[
  \begin{array}{ccc} A_{3,1} & A_{3,2} & A_{3,3} \end{array}
\right]
$$


## 行列を使った消去法

上記の最初の変形（$\left[
  \begin{array}{ccc}
    1 & 2 & 1 \\
    3 & 8 & 1 \\
    0 & 4 & 1 \\
  \end{array}
\right]$
を
$\left[
  \begin{array}{ccc}
    1 & 2 & 1 \\
    0 & 2 & -2 \\
    0 & 4 & 1 \\
  \end{array}
\right]$
に変換）を行うには、行列の左側から
$\left[
  \begin{array}{ccc}
    1 & 0 & 0 \\
    -3 & 1 & 0 \\
    0 & 0 & 1 \\
  \end{array}
\right]$
を掛ける。

$$
\left[
  \begin{array}{ccc}
    1 & 0 & 0 \\
    -3 & 1 & 0 \\
    0 & 0 & 1 \\
  \end{array}
\right] \left[
  \begin{array}{ccc}
    1 & 2 & 1 \\
    3 & 8 & 1 \\
    0 & 4 & 1 \\
  \end{array}
\right] = \left[
  \begin{array}{ccc}
    1 & 2 & 1 \\
    0 & 2 & -2 \\
    0 & 4 & 1 \\
  \end{array}
\right]
$$



```
E21 = np.array([[1, 0, 0], [-3, 1, 0], [0, 0, 1]])
A = np.array([[1, 2, 1], [3, 8, 1], [0, 4, 1]])
A_ = np.dot(E21, A)
A_
```




    array([[ 1,  2,  1],
           [ 0,  2, -2],
           [ 0,  4,  1]])



さらに次の変形（$\left[
  \begin{array}{ccc}
    1 & 2 & 1 \\
    0 & 2 & -2 \\
    0 & 4 & 1 \\
  \end{array}
\right]$
を
$\left[
  \begin{array}{ccc}
    1 & 2 & 1 \\
    0 & 2 & -2 \\
    0 & 0 & 5 \\
  \end{array}
\right]$
に変換）を行うには、行列の左側から
$\left[
  \begin{array}{ccc}
    1 & 0 & 0 \\
    0 & 1 & 0 \\
    0 & -2 & 1 \\
  \end{array}
\right]$
を掛ける。

$$
\left[
  \begin{array}{ccc}
    1 & 0 & 0 \\
    0 & 1 & 0 \\
    0 & -2 & 1 \\
  \end{array}
\right] \left[
  \begin{array}{ccc}
    1 & 2 & 1 \\
    0 & 2 & -2 \\
    0 & 4 & 1 \\
  \end{array}
\right] = \left[
  \begin{array}{ccc}
    1 & 2 & 1 \\
    0 & 2 & -2 \\
    0 & 0 & 5 \\
  \end{array}
\right]
$$


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




    array([[ 1,  2,  1],
           [ 0,  2, -2],
           [ 0,  0,  5]])



まとめると、$E_{32}(E_{21}A)=(E_{32}E_{21})A=U$


```
np.dot(np.dot(E32, E21), A)
```




    array([[ 1,  2,  1],
           [ 0,  2, -2],
           [ 0,  0,  5]])



## 置換行列 (Permutation Matrix)

左から行列を掛けると行の操作になる。
$$
\left[
  \begin{array}{cc}
    0 & 1 \\
    1 & 0 \\
  \end{array}
\right] \left[
  \begin{array}{cc}
    a & b \\
    c & d \\
  \end{array}
\right] = \left[
  \begin{array}{cc}
    c & d \\
    a & b \\
  \end{array}
\right]
$$

右から行列を掛けると列の操作になる。
$$
\left[
  \begin{array}{cc}
    a & b \\
    c & d \\
  \end{array}
\right] \left[
  \begin{array}{cc}
    0 & 1 \\
    1 & 0 \\
  \end{array}
\right] = \left[
  \begin{array}{cc}
    b & a \\
    d & c \\
  \end{array}
\right]
$$

## 逆行列
行列の変形をもとに戻す(undo)行列

$E=\left[
  \begin{array}{ccc}
    1 & 0 & 0 \\
    -3 & 1 & 0 \\
    0 & 0 & 1 \\
  \end{array}
\right]$
（2行目から1行目の3倍を引く）をもとに戻す行列は
$E^{-1}=\left[
  \begin{array}{ccc}
    1 & 0 & 0 \\
    3 & 1 & 0 \\
    0 & 0 & 1 \\
  \end{array}
\right]$

行列とその逆行列を掛けると単位行列になる。
$EE^{-1}=I$


```
E = np.array([[1, 0, 0], [-3, 1, 0], [0, 0, 1]])
E_inv = np.linalg.inv(E)
np.dot(E, E_inv)
```




    array([[1., 0., 0.],
           [0., 1., 0.],
           [0., 0., 1.]])



ipynb
9c47921cd85a1d7a3a1761d4d8e3e9bdd8ae1d94
Jupyter Notebook
10006fa0052c6802dbb522b1bef0a7b9ea3cfa62
MIT
tnaka78/mit_ocw_1806_spring_2005
lecture02.ipynb
10006fa0052c6802dbb522b1bef0a7b9ea3cfa62
MIT
tnaka78/mit_ocw_1806_spring_2005
lecture02.ipynb
10006fa0052c6802dbb522b1bef0a7b9ea3cfa62
MIT
tnaka78/mit_ocw_1806_spring_2005
lecture02.ipynb