ガウス消元——楊子曰アルゴリズム
17709 ワード
ガウス消元——楊子曰アルゴリズム
ハイパーリンク:数学の合集(これが数論ではないことを知らない)
ガウス消元、1つの事をすることができます--n元の1回の方程式のグループの黒を解いて犬に餌をやることができます:
例えば、{2 x+3 y+z=14 3 x+y+4 z=30 x+4 y+2 z=17left{begin{aligned}2 x+3 y+z=14\3 x+y+4 z=30\x+4 y+2 z=17end{aligned}right.⎩⎪⎨⎪⎧2x+3y+z=143x+y+4z=30x+4y+2z=17
多元の方程式を解くのは実はひっきりなしに元を消して元を消して元を消して、私达は2つの方法が元を消します:消元を加減してと消元を代入して、后で私达はすべて使います
まず上の方程式を拡張行列に書きます(←何なのか全然関係ないので、下を見てわかります):
[ 2 3 1 14 3 1 4 30 1 4 2 17 ]\left[\begin{array}{ccc|c} 2 & 3 & 1 &14\\3 & 1 & 4 &30\\1 & 4 & 2 &17\\\end{array}\right] ⎣⎡231314142143017⎦⎤
アルゴリズムの普遍的な適用性に注意しなければなりません.結局、私たちはコードを打つ必要があります.
もし私たちがこの行列をこのようにすることができたら(私たちはこのような行列の係数部分に名前をつけて、逆三角行列と呼ばれています)、美しくなりますか?
[ a x a y a z s 1 0 b y b z s 2 0 0 c z s 3 ] ⇒ { a x x + a y y + a z z = s 1 b y y + b z z = s 2 c z z = s 3\left[\begin{array}{ccc|c} a_x & a_y & a_z &s_1\\0 & b_y& b_z &s_2\\0 & 0 & c_z &s_3\\\end{array}\right]\Rightarrow\left\{\begin{aligned} a_xx+a_yy+a_zz=s_1\\b_yy+b_zz=s_2\\c_zz=s_3\end{aligned}\right. ⎣ax 00 ay by 0 az bz cz s 1 s 2 s 3
完璧に解け!
等式の性質に基づいて、矩形の操作を行うことができます.ゼロ以外の数で1行 を乗算その中の1行の数倍を1行の に加える交換2行の位置 どうやって逆三角行列になるか考えてみましょう
この行列を観察すると、3つの等式の中でxが1回しか現れないことがわかります.これは、方程式を1つ選んで残り、最初の行に置いて、他の方程式のxを消して(加減算元を採用しています)他の方程式のxを無視する必要があることを意味します.それは私たちが処理したからです.
この方程式を見ないと、yが1つしか残っていないことに気づきます.ああ、さっきの操作を繰り返して、yを残して、2行目に置いて、他の方程式のyを消して、再びこの方程式を気にしません.
再処理z......
ああ、私たちの考えはだんだんはっきりしてきました.今、私たちは1つの問題を考えなければなりません.すべての未知数は私たちが方程式を残すだけです(前に処理したものを無視します).では、残ったのはどれですか.理論的には、どの方程式を選ぶかはもちろん結果に影響しません.BUT、私たちはコンピュータに深刻な問題があることを知っています.カード精度と呼ばれています.精度誤差を減らすために、現在考えている未知数の中で係数の絶対値が最も大きいものを選んで精度誤差を小さくします.
注意点:ある未知数の係数がすべてゼロであれば、理解できません(コードを打つとき、絶対値が最大の数が0であるかどうかを見るだけでいいです)
上の行列を用いてこの過程を簡単にシミュレートした[2 3 1 14 3 4 30 1 4 17]left[begin{array}{ccc|c}2&3&1&14\3&1&4&4&30\1&4&2&17\end{array}right]231 3141430171行目に移動:[3 1 4 30 2 3 14 1 4 2 17]left[begin{array}{ccc|c}3&1&4&30\2&3&1&14\1&4&2&17\end{array}right]
私たちは1行目で他の行のxを消去しなければならないので,まず1行目のxの係数を1:[1 1 1 3 4 3 3 10 2 3 3 3 1 14 1 4 4 2 17]left[ begin{array}{ ccc|c}1&frac{ 1}{3}&frac{ 4}{3}&10\2&3&1&14\1&4&2&17\end{ array} right]34 34 12 101417
そしてそれぞれ他の行xの係数に乗じて一つ一つ差をつけ、xを消去する:[1 1 1 3 3 4 3 10 2−2∗1 3−2∗1 3 1−2∗1 3 1−2∗4 3 14−2∗10 1−1∗1−1∗1 4−1∗1 3 2−1∗4 3 17−1∗10]left[begin{array}{ ccc|c}1&frac{ 1}{3}&frac{ 3}&10\2−2*2*2*2*3−2*2*2*2*2*2*2*frfrac{3}{3}&0\\\\2−2*2*2*2*2*2*ac{1}{3}&1-2*frac{4}{3}&14-2*10\1-1*1&4-1*frac{1}{3}&2-1*frac{4}{3}&17-1*10\end{array}right]⎣⎢⎢⎢⎡12−2∗11−1∗1 31 3−2∗31 4−1∗31 34 1−2∗34 2−1∗34 1014−2∗1014−2∗1017−1∗10⎧1 1 3 3 4 3 10 0 7 3−5 3−6 0 11 3 3 7]left[begin{array}{ccc|c}1&frac{1}{3}&frac{4}{3}&10\0&frac{7}{3}&-frac{5}{3}&-6\0&frac{11}{3}&frac{2}{3}&7\end{array}right]最初の行にかかわらず、絶対値を最大にするには、[1 1 1 3 4 3 3 10 0 11 3 3 3 3 3 7 7 7 3−5 3−3 3−6]left[ begin{array}{ ccc|c}1&frac{ 1}{3}&frac{ 4}{3}&10\\0&frac{ 11}{3}&frac{ 3}&frac{ 3}&7\\\\\\\\\\\\\\\\\\\\\\\\\\\\{3}&-6\end{ array}rightこの式のy前の係数を1:[1 3 3 4 3 10 0 1 11 11 0 7 3−5 3−6]left[ begin{array}{ ccc|c}1&frac{ 1}{3}&frac{ 4}{3}&10\frac{ 4}{3}&10\frac{ 4}{3}&10\frac{ 4}&10\frac{ 3}&10{10{10\{10}\\0&1&frac{2}{11}&frac{21}{11}\\0&frac{7}{3}&-frac{5}{3}&-6\end{array}right]⎣gin{array}{ccc|c}1&frac{1}{3}&frac{4}{3}&10\0&1&frac{2}{11}&frac{21}{11}\\\\0&frac{ 7}{3}-frac{ 7}{3}*1&-frac{ 5}{3}-frac{ 7}{3}-frac{ 7}{11}&−6-frac{ 7}*frac{ 21}{11}\end{ array}right]⎣⎢⎢⎢912121212121137−37∗1 34 112−35−37∗112 112−37−37−37∗112 112−37−37−37−37∗112−37−37−37−37−37−37−378727112−37−37−37−37−37−37−37−37−37 121−6−37∗1121⎦⎥⎥⎥⎥⎤つまり[1 3 4 3 10 0 1 2 11 11 11 0−23 11 345 33]left[begin{array}{ ccc|c}1&frac{ 1}{3}&frac{ 4}{3}&10\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\プログラムは実行されます.残りの1行を見つけてzの係数を1:[1 1 1 3 4 3 10 0 1 2 11 11 11 0 1 5]left[begin{array}{ccc|c}1&frac{1}{3}&frac{4}{3}&10\0&1&frac{2}{11}&frac{21}{11}\0&0&1&1&5\end{array}right]に変える100 31 10 34 112 1 101121 5得られた:[1 1 1 3 3 3 10 0 0 1 0 0 0 1 5]left[ begin{array}{ ccc|c}1&frac{ 1}{3}&frac{ 4}{3}&10\0&1&0&0&0&0&1&5\end{ array} right]私たちはy=1を持っています.最後にyとzを一緒に最初の行を連れて行きました.得られた:[1 0 0 0 0 0 0 3 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 5]left[ begin{array}{ ccc|c}1&0&0&0&0&0&0&0&0&1&5\end{ array} right]...⎩⎪⎨⎪⎧x=3y=1z=5
次に,現在の未知数のうち係数の絶対値が最も大きい式をとるたびに他の式のこの未知数を消去して誤差を最小限に抑える理由を簡単に説明する.
さらに,l番目の式における未知数tの係数をp l t p_と仮定する.{lt} plt
仮に,各式における係数がそれぞれp 1 x,p 2 x,p 3 x⋯p n x p_である未知数xを解決しているとする.{1x},p_{2x},p_{3x}\cdots p_{nx}p 1 x,p 2 x,p 3 x⋯pnx(考慮された式は無視され、下付きはいくつかの式を表す)
式iを選択して残すとします
我々は上の式を利用して消元を加減した後,他の式の下xをすべて消去し,j番目の式の未知数wの係数はこのように計算した(時間をかけて,上の例と結びつけてきっと理解できる):q j w=qj w−q j x∗q i w{jw}=q_{jw}-\frac{q_{jx}}{q_{ix}}*q_{iw} qjw=qjw−qixqjx∗qiw
私たちが選んだq i x q_{ix}qixが大きいほど、q j x q i xfrac{q_{jx}{q_{ix}}qix qjxの期待は小さくなり、それを1つの単位と見なすほど、この単位は小さくなり、減らした後の誤差は小さくなる!
完璧!
OK
c++コード(洛谷P 3389):
参照先:https://pks-loving.blog.luogu.org/p3389-mu-ban-gao-si-xiao-yuan-fa『アルゴリズムコンテスト進級ガイド』李煜東著
HG機械室で
ハイパーリンク:数学の合集(これが数論ではないことを知らない)
ガウス消元、1つの事をすることができます--n元の1回の方程式のグループの黒を解いて犬に餌をやることができます:
例えば、{2 x+3 y+z=14 3 x+y+4 z=30 x+4 y+2 z=17left{begin{aligned}2 x+3 y+z=14\3 x+y+4 z=30\x+4 y+2 z=17end{aligned}right.⎩⎪⎨⎪⎧2x+3y+z=143x+y+4z=30x+4y+2z=17
多元の方程式を解くのは実はひっきりなしに元を消して元を消して元を消して、私达は2つの方法が元を消します:消元を加減してと消元を代入して、后で私达はすべて使います
まず上の方程式を拡張行列に書きます(←何なのか全然関係ないので、下を見てわかります):
[ 2 3 1 14 3 1 4 30 1 4 2 17 ]\left[\begin{array}{ccc|c} 2 & 3 & 1 &14\\3 & 1 & 4 &30\\1 & 4 & 2 &17\\\end{array}\right] ⎣⎡231314142143017⎦⎤
アルゴリズムの普遍的な適用性に注意しなければなりません.結局、私たちはコードを打つ必要があります.
もし私たちがこの行列をこのようにすることができたら(私たちはこのような行列の係数部分に名前をつけて、逆三角行列と呼ばれています)、美しくなりますか?
[ a x a y a z s 1 0 b y b z s 2 0 0 c z s 3 ] ⇒ { a x x + a y y + a z z = s 1 b y y + b z z = s 2 c z z = s 3\left[\begin{array}{ccc|c} a_x & a_y & a_z &s_1\\0 & b_y& b_z &s_2\\0 & 0 & c_z &s_3\\\end{array}\right]\Rightarrow\left\{\begin{aligned} a_xx+a_yy+a_zz=s_1\\b_yy+b_zz=s_2\\c_zz=s_3\end{aligned}\right. ⎣ax 00 ay by 0 az bz cz s 1 s 2 s 3
完璧に解け!
等式の性質に基づいて、矩形の操作を行うことができます.
この行列を観察すると、3つの等式の中でxが1回しか現れないことがわかります.これは、方程式を1つ選んで残り、最初の行に置いて、他の方程式のxを消して(加減算元を採用しています)他の方程式のxを無視する必要があることを意味します.それは私たちが処理したからです.
この方程式を見ないと、yが1つしか残っていないことに気づきます.ああ、さっきの操作を繰り返して、yを残して、2行目に置いて、他の方程式のyを消して、再びこの方程式を気にしません.
再処理z......
ああ、私たちの考えはだんだんはっきりしてきました.今、私たちは1つの問題を考えなければなりません.すべての未知数は私たちが方程式を残すだけです(前に処理したものを無視します).では、残ったのはどれですか.理論的には、どの方程式を選ぶかはもちろん結果に影響しません.BUT、私たちはコンピュータに深刻な問題があることを知っています.カード精度と呼ばれています.精度誤差を減らすために、現在考えている未知数の中で係数の絶対値が最も大きいものを選んで精度誤差を小さくします.
注意点:ある未知数の係数がすべてゼロであれば、理解できません(コードを打つとき、絶対値が最大の数が0であるかどうかを見るだけでいいです)
上の行列を用いてこの過程を簡単にシミュレートした[2 3 1 14 3 4 30 1 4 17]left[begin{array}{ccc|c}2&3&1&14\3&1&4&4&30\1&4&2&17\end{array}right]231 3141430171行目に移動:[3 1 4 30 2 3 14 1 4 2 17]left[begin{array}{ccc|c}3&1&4&30\2&3&1&14\1&4&2&17\end{array}right]
私たちは1行目で他の行のxを消去しなければならないので,まず1行目のxの係数を1:[1 1 1 3 4 3 3 10 2 3 3 3 1 14 1 4 4 2 17]left[ begin{array}{ ccc|c}1&frac{ 1}{3}&frac{ 4}{3}&10\2&3&1&14\1&4&2&17\end{ array} right]34 34 12 101417
そしてそれぞれ他の行xの係数に乗じて一つ一つ差をつけ、xを消去する:[1 1 1 3 3 4 3 10 2−2∗1 3−2∗1 3 1−2∗1 3 1−2∗4 3 14−2∗10 1−1∗1−1∗1 4−1∗1 3 2−1∗4 3 17−1∗10]left[begin{array}{ ccc|c}1&frac{ 1}{3}&frac{ 3}&10\2−2*2*2*2*3−2*2*2*2*2*2*2*frfrac{3}{3}&0\\\\2−2*2*2*2*2*2*ac{1}{3}&1-2*frac{4}{3}&14-2*10\1-1*1&4-1*frac{1}{3}&2-1*frac{4}{3}&17-1*10\end{array}right]⎣⎢⎢⎢⎡12−2∗11−1∗1 31 3−2∗31 4−1∗31 34 1−2∗34 2−1∗34 1014−2∗1014−2∗1017−1∗10⎧1 1 3 3 4 3 10 0 7 3−5 3−6 0 11 3 3 7]left[begin{array}{ccc|c}1&frac{1}{3}&frac{4}{3}&10\0&frac{7}{3}&-frac{5}{3}&-6\0&frac{11}{3}&frac{2}{3}&7\end{array}right]最初の行にかかわらず、絶対値を最大にするには、[1 1 1 3 4 3 3 10 0 11 3 3 3 3 3 7 7 7 3−5 3−3 3−6]left[ begin{array}{ ccc|c}1&frac{ 1}{3}&frac{ 4}{3}&10\\0&frac{ 11}{3}&frac{ 3}&frac{ 3}&7\\\\\\\\\\\\\\\\\\\\\\\\\\\\{3}&-6\end{ array}rightこの式のy前の係数を1:[1 3 3 4 3 10 0 1 11 11 0 7 3−5 3−6]left[ begin{array}{ ccc|c}1&frac{ 1}{3}&frac{ 4}{3}&10\frac{ 4}{3}&10\frac{ 4}{3}&10\frac{ 4}&10\frac{ 3}&10{10{10\{10}\\0&1&frac{2}{11}&frac{21}{11}\\0&frac{7}{3}&-frac{5}{3}&-6\end{array}right]⎣gin{array}{ccc|c}1&frac{1}{3}&frac{4}{3}&10\0&1&frac{2}{11}&frac{21}{11}\\\\0&frac{ 7}{3}-frac{ 7}{3}*1&-frac{ 5}{3}-frac{ 7}{3}-frac{ 7}{11}&−6-frac{ 7}*frac{ 21}{11}\end{ array}right]⎣⎢⎢⎢912121212121137−37∗1 34 112−35−37∗112 112−37−37−37∗112 112−37−37−37−37∗112−37−37−37−37−37−37−378727112−37−37−37−37−37−37−37−37−37 121−6−37∗1121⎦⎥⎥⎥⎥⎤つまり[1 3 4 3 10 0 1 2 11 11 11 0−23 11 345 33]left[begin{array}{ ccc|c}1&frac{ 1}{3}&frac{ 4}{3}&10\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\プログラムは実行されます.残りの1行を見つけてzの係数を1:[1 1 1 3 4 3 10 0 1 2 11 11 11 0 1 5]left[begin{array}{ccc|c}1&frac{1}{3}&frac{4}{3}&10\0&1&frac{2}{11}&frac{21}{11}\0&0&1&1&5\end{array}right]に変える100 31 10 34 112 1 101121 5得られた:[1 1 1 3 3 3 10 0 0 1 0 0 0 1 5]left[ begin{array}{ ccc|c}1&frac{ 1}{3}&frac{ 4}{3}&10\0&1&0&0&0&0&1&5\end{ array} right]私たちはy=1を持っています.最後にyとzを一緒に最初の行を連れて行きました.得られた:[1 0 0 0 0 0 0 3 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 5]left[ begin{array}{ ccc|c}1&0&0&0&0&0&0&0&0&1&5\end{ array} right]...⎩⎪⎨⎪⎧x=3y=1z=5
次に,現在の未知数のうち係数の絶対値が最も大きい式をとるたびに他の式のこの未知数を消去して誤差を最小限に抑える理由を簡単に説明する.
さらに,l番目の式における未知数tの係数をp l t p_と仮定する.{lt} plt
仮に,各式における係数がそれぞれp 1 x,p 2 x,p 3 x⋯p n x p_である未知数xを解決しているとする.{1x},p_{2x},p_{3x}\cdots p_{nx}p 1 x,p 2 x,p 3 x⋯pnx(考慮された式は無視され、下付きはいくつかの式を表す)
式iを選択して残すとします
我々は上の式を利用して消元を加減した後,他の式の下xをすべて消去し,j番目の式の未知数wの係数はこのように計算した(時間をかけて,上の例と結びつけてきっと理解できる):q j w=qj w−q j x∗q i w{jw}=q_{jw}-\frac{q_{jx}}{q_{ix}}*q_{iw} qjw=qjw−qixqjx∗qiw
私たちが選んだq i x q_{ix}qixが大きいほど、q j x q i xfrac{q_{jx}{q_{ix}}qix qjxの期待は小さくなり、それを1つの単位と見なすほど、この単位は小さくなり、減らした後の誤差は小さくなる!
完璧!
OK
c++コード(洛谷P 3389):
#include
",ans[i]);
}
return 0;
}
参照先:https://pks-loving.blog.luogu.org/p3389-mu-ban-gao-si-xiao-yuan-fa『アルゴリズムコンテスト進級ガイド』李煜東著
HG機械室で