![普通の Gauss 消去法（LU 分解）
for i = 1, . . . , n: /* 前進消去 */
for i′ = i + 1, . . . , n:
α := A[i′ , i]/A[i, i]
b[i′ ] ← b[i′ ] ? αb[j]
for j = i, . . . , n:
A[i′ , j] ← A[i′ , j] ? αA[i, j]
for i = n, . . . , 1: /* 交代代入 */
for j = i + 1, . . . , n:
bij] ← b[j] ? A[i, j]b[j]
b[i] ← b[i]/A[i, i]
3/ 10](https://image.slidesharecdn.com/slide-130405111750-phpapp01/85/-4-320.jpg)
![ピボット選択つき Gauss 消去法（LUP 分解）
計算中に A[i, i] が小さくなって精度悪化（or ゼロ割）
? 普通は行ピボット選択で対応
※行ピボット選択つき Gauss は理論上不安定だが，
?破綻例を作るのは相当大変（良い例を作ると論文）
ここでは実装量的に Givens 消去法での対応をオススメ
- Givens 消去法 = 2 × 2 回転で掃き出す Gauss 消去法
- 計算時間：ピボット選択つき Gauss より少し遅い
- 数値安定性：非常に高（回転は誤差を拡大しない）
ピボット選択が不要なので，実装が非常にシンプルになる
（see: 次ページ）
4/ 10](https://image.slidesharecdn.com/slide-130405111750-phpapp01/85/-5-320.jpg)
![Givens 消去法（QR 分解）
for i = 1, . . . , n: /* 前進消去 */
for i′ = i + 1, . . . , n:
MAKEROT(A[i, i], A[i′ , i], c, s);
ROT(b[i], b[i′ ], c, s);
for j = i + 1, . . . , n:
ROT(A[i, j], A[i′ , j], c, s);
for i = n, . . . , 1: /* 交代代入 */
for j = i + 1, . . . , n:
b[i] ← b[i] ? A[i, j]b[j]
b[i] ← b[i]/A[i, i]
ピボット選択なしの Gauss 消去法と同じ手続き
5/ 10](https://image.slidesharecdn.com/slide-130405111750-phpapp01/85/-6-320.jpg)
![MAKEROT / ROT
#de?ne MAKEROT(x, y, c, s)
√
{ r = x2 + y 2 ; c = x/r; s = y/r; }
= 以下を満たす c, [ の計算 [ ]
s ] [ ]
c s x r
=
?s c y 0
#de?ne ROT(x, y, c, s)
{ u = cx + sy; v = ?sx + cy; x = u; y = v; }
= 以下の計算の適用 ]
[ [ ][ ]
x c s x
←
y ?s c y
6/ 10](https://image.slidesharecdn.com/slide-130405111750-phpapp01/85/-7-320.jpg)
竞技プログラミングでの线型方程式系
- 1. 行列プロが教える 竞技プログラミングでの线型方程式系 前原 貴憲 (@tmaehara)
- 2. 線型方程式系 入力：n × n 行列 A，ベクトル b 出力：以下を満たすベクトル x Ax = b 標準的な解法：ピボット選択つき Gauss 消去法（LUP 分解） 競技プログラミングでは → Givens 消去法（QR 分解）がオススメ かもしれない 1/ 10
- 3. 説明 2/ 10
- 4. 普通の Gauss 消去法（LU 分解） for i = 1, . . . , n: /* 前進消去 */ for i′ = i + 1, . . . , n: α := A[i′ , i]/A[i, i] b[i′ ] ← b[i′ ] ? αb[j] for j = i, . . . , n: A[i′ , j] ← A[i′ , j] ? αA[i, j] for i = n, . . . , 1: /* 交代代入 */ for j = i + 1, . . . , n: bij] ← b[j] ? A[i, j]b[j] b[i] ← b[i]/A[i, i] 3/ 10
- 5. ピボット選択つき Gauss 消去法（LUP 分解） 計算中に A[i, i] が小さくなって精度悪化（or ゼロ割） ? 普通は行ピボット選択で対応 ※行ピボット選択つき Gauss は理論上不安定だが， ?破綻例を作るのは相当大変（良い例を作ると論文） ここでは実装量的に Givens 消去法での対応をオススメ - Givens 消去法 = 2 × 2 回転で掃き出す Gauss 消去法 - 計算時間：ピボット選択つき Gauss より少し遅い - 数値安定性：非常に高（回転は誤差を拡大しない） ピボット選択が不要なので，実装が非常にシンプルになる （see: 次ページ） 4/ 10
- 6. Givens 消去法（QR 分解） for i = 1, . . . , n: /* 前進消去 */ for i′ = i + 1, . . . , n: MAKEROT(A[i, i], A[i′ , i], c, s); ROT(b[i], b[i′ ], c, s); for j = i + 1, . . . , n: ROT(A[i, j], A[i′ , j], c, s); for i = n, . . . , 1: /* 交代代入 */ for j = i + 1, . . . , n: b[i] ← b[i] ? A[i, j]b[j] b[i] ← b[i]/A[i, i] ピボット選択なしの Gauss 消去法と同じ手続き 5/ 10
- 7. MAKEROT / ROT #de?ne MAKEROT(x, y, c, s) √ { r = x2 + y 2 ; c = x/r; s = y/r; } = 以下を満たす c, [ の計算 [ ] s ] [ ] c s x r = ?s c y 0 #de?ne ROT(x, y, c, s) { u = cx + sy; v = ?sx + cy; x = u; y = v; } = 以下の計算の適用 ] [ [ ][ ] x c s x ← y ?s c y 6/ 10
- 8. QR 分解 補足 A = QR (Q : 直交， : 上三角) R ☆ QR 法のよくある計算方法 ? Gram-Schmidt の直交化 数値不安定なので，基本的に使ってはいけない ? Householder 変換 数値安定かつ早いので線型計算の教科書はこれを説明 ? Givens 回転（今回紹介） 数値安定だが Householder より遅いので説明されない しかし，実装が超シンプルになるので競プロ向き！ 7/ 10
- 9. 参考 8/ 10
- 10. 参考：Gauss が破綻する例（Wilkinson 行列） ? ? 1 0 0 1 ??1 1 0 1? A=? ??1 ? ?1 1 1? ?1 ?1 ?1 1 - Gauss 消去法をすると一番右の列が指数的に増加 - LU 分解の代わりに UL 分解するとうまくいく （LU?UL 両方が破綻する例の存在は open problem） - 行?列両方をピボットする Gauss は，常にうまくいく 9/ 10
- 11. 参考：なにをやってもダメな例（Hilbert 行列） ? ? 1/1 1/2 1/3 1/4 ?1/2 1/3 1/4 1/5? A=? ?1/3 ? 1/4 1/5 1/6? 1/4 1/5 1/6 1/7 - 線型方程式の条件数：cond(A) := ∥A?1 ∥∥A∥ （条件数 ? 誤差の拡大率） - 条件数が大きいと，何をやってもだいたい無理 ? 競プロでは，この手の入力は考えなくて良い 10/ 10