連立一次方程式れんりついちじほうていしきsystem of linear equationsと掃はき出だし法ほうGaussian elimination

Systems of linear equations連立一次方程式れんりついちじほうていしき and Gaussian elimination掃はき出だし法ほう

1導入どうにゅう

この講義こうぎで中心ちゅうしんに置おく発想はっそうは、掃はき出だし法ほうGaussian eliminationは係数けいすうcoefficientをただ消去しょうきょする技巧ぎこうではなく、連立一次方程式れんりついちじほうていしきsystem of linear equationsを同値どうちequivalentな形かたちへ変換へんかんして、解かいの構造こうぞうstructureを明示めいじする方法ほうほうだということである。

連立一次方程式れんりついちじほうていしきsystem of linear equationsを解とくとき、代入法だいにゅうほうや加減法かげんほうだけに依存いぞんすると、式しきが多おおくなった段階だんかいで構造こうぞうstructureが不明瞭ふめいりょうになる。掃はき出だし法ほうGaussian eliminationは、この手順てじゅんを体系的たいけいてきに整理せいりしたものである。

1Introduction

The essential point of this lecture is that Gaussian elimination掃はき出だし法ほう is not just a trick for eliminating coefficients. It transforms a system of linear equations連立一次方程式れんりついちじほうていしき into an equivalent同値どうち form and makes the structure構造こうぞう of the solution explicit.

If one relies only on substitution or ad hoc elimination, the structure becomes unclear when there are many equations. Gaussian elimination掃はき出だし法ほう systematizes that procedure.

2用語ようごと定義ていぎ

連立一次方程式れんりついちじほうていしきSystem of linear equations とは、未知数みちすうunknownが 1 次じで現あらわれる方程式ほうていしきを複数ふくすうまとめたものである。

行基本変形ぎょうきほんへんけいElementary row operation とは、行ぎょうrowの交換こうかん、定数倍ていすうばい、ある行ぎょうrowに別べつの行ぎょうrowの定数倍ていすうばいを加くわえる操作そうさoperationである。

2Terms and definitions

A system of linear equations連立一次方程式れんりついちじほうていしき is a collection of equations in which the unknowns未知数みちすう appear linearly.

An elementary row operation行基本変形ぎょうきほんへんけい is one of the following operations on rows: swapping rows, multiplying a row by a nonzero constant, or adding a constant multiple of one row to another row.

3方針ほうしん

まず拡大係数行列かくだいけいすうぎょうれつaugmented matrixに変換へんかんする。そのあと、行基本変形ぎょうきほんへんけいelementary row operationで前まえから順番じゅんばんに主成分しゅせいぶんpivotを確保かくほし、下したや上うえの成分せいぶんcomponentを消去しょうきょする。

3Strategy

First convert the system to an augmented matrix拡大係数行列かくだいけいすうぎょうれつ. Then use elementary row operations行基本変形ぎょうきほんへんけい to secure pivots主成分しゅせいぶん from left to right and eliminate entries below or above them.

4直感的ちょっかんてきな説明せつめい

掃はき出だし法ほうGaussian eliminationは、表ひょうの中なかで「この列れつcolumnの代表だいひょうはここ」と設定せっていし、その上下じょうげを消去しょうきょする操作そうさoperationに相当そうとうする。これを左ひだりから右みぎへ順番じゅんばんに進行しんこうすると、どの変数へんすうが自由じゆうで、どの変数へんすうが決定けっていされるかを確認かくにんできる。

4Intuitive explanation

Gaussian elimination掃はき出だし法ほう amounts to choosing a representative entry for a column in a table and clearing entries above or below it. Moving from left to right reveals which variables are determined and which variables remain free.

5厳密げんみつな説明せつめい

5.11. 拡大係数行列かくだいけいすうぎょうれつaugmented matrix

たとえば

は

と表示ひょうじできる。

5.22. 行基本変形ぎょうきほんへんけいelementary row operation

2 行目ぎょうめから 1 行目ぎょうめの 2 倍ばいを引ひくと

である。ここから $$y=1$$y=1、さらに $$x=1$$x=1 と判定はんていできる。

5.33. 何なにを判定はんていできるか

掃はき出だした結果けっか、矛盾むじゅんする行ぎょうrowが表あらわれれば解かいなし、自由変数じゆうへんすうfree variableが残のこれば無数むすうの解かいが存在そんざいする。

最小例さいしょうれいで 3 つの場合ばあいを並ならべると、見みるべき場所ばしょが明確めいかくになる。

一意解いちいかいでは、各かく未知数みちすうunknownが pivot によって決定けっていされる。解かいなしでは、係数側けいすうがわがすべて 0 なのに右辺うへんright-hand sideだけ 0 でない行ぎょうrowが現あらわれる。無数むすうの解かいでは、自由変数じゆうへんすうfree variableを任意にんいに動うごかせるため、解集合かいしゅうごうに自由度じゆうどが残のこる。

5Precise explanation

5.11. Augmented matrix拡大係数行列かくだいけいすうぎょうれつ

For example,

is represented by

5.22. Elementary row operation行基本変形ぎょうきほんへんけい

Apply

This subtracts twice the first row from the second row and gives

From the second row, $-3y=-3$-3y=-3, so $y=1$y=1. Substituting into the first row gives $x+1=2$x+1=2, hence $x=1$x=1. Therefore the solution is $x=1,y=1$x=1,y=1.

5.33. What can be decided

After elimination, a contradictory row means there is no solution, and a remaining free variable自由変数じゆうへんすう means there are infinitely many solutions.

The three smallest cases make the checkpoints explicit.

In the unique-solution case, each unknown未知数みちすう is determined by a pivot. In the no-solution case, a row appears whose coefficient side is all zero but whose right-hand side右辺うへん is nonzero. In the infinitely-many-solutions case, a free variable自由変数じゆうへんすう can be moved arbitrarily, so the solution set retains a degree of freedom.

6判定基準はんていきじゅん

• 未知数みちすうunknownが複数ふくすうあり、式しきの数かずも多おおいなら、掃はき出だし法ほうGaussian eliminationを優先ゆうせんする。
• 解かいが一意いちいか、解かいなしなのかを判定はんていしたいときも、掃はき出だし結果けっかが有効ゆうこうである。
• 変形へんけいの途中とちゅうで同値どうちequivalentを保たもっていることを確認かくにんする。
• 解かいの型かたを判断はんだんするときは、矛盾行むじゅんぎょう、pivot の個数こすう、自由変数じゆうへんすうfree variableの有無うむを順じゅんに確認かくにんする。

6Criteria

• If there are several unknowns未知数みちすう and several equations, prefer Gaussian elimination掃はき出だし法ほう.
• The elimination result is also useful when deciding whether the solution is unique or whether no solution exists.
• At every step, check that the system is being replaced by an equivalent同値どうち system.
• To decide the solution type, check for contradictory rows, count the pivots, and then check whether free variables自由変数じゆうへんすう remain.

7最終形さいしゅうけい

7Final form

$\text{[PARSE ERROR: Undefined("Command("boxed")")]}\text{systemoflinearequations}\to \text{augmentedmatrix}\to \text{Gaussianelimination}$\boxed{\text{system of linear equations} \rightarrow \text{augmented matrix} \rightarrow \text{Gaussian elimination}}

8一言ひとことでいうと

• 掃はき出だし法ほうGaussian eliminationは、連立一次方程式れんりついちじほうていしきsystem of linear equationsを解とく手順てじゅんであると同時どうじに、解かいの構造こうぞうstructureを確認かくにんする方法ほうほうも兼かねる。

8In one sentence

• Gaussian elimination掃はき出だし法ほう is both a procedure for solving a system of linear equations連立一次方程式れんりついちじほうていしき and a method for checking the structure構造こうぞう of its solutions.

9演習えんしゅうリンク

9Exercise links