連立線形方程式

(1)

数値計算

大阪大学基礎工学部永原正章

年月日限

(2)

連立線形方程式

変数連立線形方程式

11 1

+

12 2

+ · · · +

₁

=

1 21 1

+

₂₂ ₂

+ · · · +

₂

=

₂

1 1

+

₂ ₂

+ · · · + =

表現

= , ∈ R

^×

, ∈ R , ∈ R .

(3)

連立線形方程式

=

行列正則仮定

厳密解 ∗

=

⁻¹

直接解法消去法厳密解計算量大

近似解法法法近似解計算量小

(4)

線形方程式最小化問題

線形方程式

=

行列正則

> 0

正定値次等価

∗ 方程式

=

解

∗ 次関数最小化

( ) = 1 2

⊤

−

^⊤

.

(5)

証明

→

( ) R

上微分可能

( )

最小化

∗ 次式満

∇ (

^∗

) = 0.

∇ ( )

関数

( )

勾配

∇ ( ) =

[ ∂ ( )

∂

₁

. . . ∂ ( )

∂ ]

_⊤

定義具体的

∇ ( )

計算

∇ ( ) = −

得 ^∗

=

線形方程式解

(6)

証明

→

∗ ∗

=

満任意

∈ R

対

( ) = (

^∗

+ −

^∗

) = (

^∗

) + 1

2 ( −

^∗

)

^⊤

( −

^∗

)

成立

> 0

上式

̸ =

^∗

( ) > (

^∗

)

^∗

( )

最小化

(7)

次形式勾配

∇ ( 1

2

⊤

−

^⊤

)

= − .

(8)

線形方程式最小化問題

方程式

=

解

⇔

関数

( )

最小化

初期

[0]

決

[1] ( [1]) < ( [0])

決

最急傾斜方向最急降下方向向更新

(9)

線形方程式最小化問題

∈ R ( )

最急降下方向負勾配

−∇ ( ) = −

次反復法 ^∗ 近似解得

[ + 1] = [ ] + α[ ] [ ], = 0, 1, 2, . . .

α[ ] ∈ R

未定

[ ] = − [ ]

残差

(10)

最適

反復法

[ + 1] = [ ] + α[ ] [ ], = 0, 1, 2, . . . ( + α )

最小化

α ∈ R

求

( + α ) = 1

2 ( + α )

^⊤

( + α ) − ( + α )

^⊤

= 1 2

⊤

−

^⊤

− α

^⊤

( − ) + 1 2 α

² ^⊤

= ( ) − α

^⊤

+ 1 2 α

² ^⊤

= ( 1

2

⊤

)

α

²

− (

^⊤

)α + ( )

(11)

最適

( + α ) = ( 1

2

⊤

)

α

²

− (

^⊤

)α + ( )

最小化

α ∈ R

α

^∗

=

⊤

> 0

任意

̸ = 0

対 ^⊤

> 0

第目

α[ ] = [ ]

^⊤

[ ]

^⊤

[ ]

(12)

最急降下法

方程式

=

近似解求反復法

[ ]= − [ ],

α[ ]= [ ]

^⊤

[ ] [ ]

^⊤

[ ] ,

[ + 1] = [ ] + α[ ] [ ], = 0, 1, 2, . . .

方法最急降下法呼

(13)

最急降下法

残差

[ + 1] = − [ + 1]

= − [ ] − α[ ] [ ]

= [ ] − α[ ] [ ] [ + 1] [ ]

内積計算

[ ]

^⊤

[ + 1] = [ ]

^⊤

( [ ] − α[ ] [ ])

= [ ]

^⊤

[ ] − α[ ] [ ]

^⊤

[ ]

= [ ]

^⊤

[ ] − [ ]

^⊤

[ ]

^⊤

[ ] · [ ]

^⊤

[ ]

= [ ]

^⊤

[ ] − [ ]

^⊤

[ ]

= 0

残差

[ + 1] [ ]

直交

(14)

最急降下法

[0]

最急降下方向進

方向最小以上方向進

値大止位置

[1]

下向方向度回転方向最急降下方向以下同様

(15)

最急降下法収束性

> 0

最急降下法任意初期対唯一厳密解収束

(16)

証明

行列固有値

λ

₁

≥ λ

₂

≥ · · · ≥ λ > 0

任意

∈ R ̸ = 0

対

0 <

^⊤

≤ λ

₁ ^⊤

, ∴ 1

⊤

≥ 1

λ

1 ⊤

> 0

対 ⁻¹ 固有値

0 < 1/λ

1

≤ 1/λ

2

≤ · · · ≤ 1/λ

⊤ −1

≤ 1 λ

⊤

, ∴

^⊤

≥ λ

^{⊤ −}¹

以上任意

∈ R ̸ = 0

対

⊤

≥ λ

^{⊤ −}¹

⊤

≥ λ

^{⊤ −}¹

λ

₁ ^⊤

(17)

証明

残差

[ ] = − [ ]

関

[ + 1] = [ ] − α[ ] [ ]

[ + 1]

^{⊤ −}¹

[ + 1]

= ( [ ] − α[ ] [ ])

^⊤ ⁻¹

( [ ] − α[ ] [ ])

= [ ]

^{⊤ −}¹

[ ] − α[ ] [ ]

^⊤

[ ]

α[ ] = [ ]

^⊤

[ ]

^⊤

[ ] ≥ λ [ ]

^{⊤ −}¹

[ ]

λ

1

[ ]

^⊤

[ ]

(18)

証明

[ + 1]

^{⊤ −}¹

[ + 1] ≤ [ ]

^{⊤ −}¹

[ ] − λ

λ

₁

[ ]

^{⊤ −}¹

[ ]

= (

1 − λ λ

1

)

[ ]

^{⊤ −}¹

[ ]

≤ (

1 − λ λ

₁

)

₂

[ − 1]

^{⊤ −}¹

[ − 1]

≤ · · ·

≤ (

1 − λ λ

1

)

+1

[0]

^{⊤ −}¹

[0]

→ 0 ( → ∞ )

(19)

証明

[ ]

^{⊤ −}¹

[ ] = ∥ [ ]∥

²−1

→ 0 → ∞

→∞

[ ] =

_→∞

( − [ ]) = 0 [ ]

方程式

=

厳密解収束

解一意性正則明

(20)

練習問題

正則行列

∈ R

^× 固有値

λ

1

, . . . , λ

逆行

列 ⁻¹ 固有値

1/λ

1

, . . . , 1/λ

示

行列固有値

λ

対応固有

= λ .

正則

λ ̸= 0

(21)

解答例

行列固有値

λ

対応固有

= λ

成立

行列正則

λ ̸ = 0

λ

⁻¹

=

⁻¹ 成立

λ

⁻¹ 逆行列 ⁻¹ 固有値固有

上議論任意固有値

λ

1

, . . . , λ

成立

−1 固有値

1/λ

₁

, . . . , 1/λ

(22)

最急降下法収束速

> 0 ∈ R

対

∥ ∥ = √

⊤

R

行列条件数

( ) = ∥

⁻¹

∥

2

∥ ∥

2

( ) = λ ( )/λ ( ) ≥ 1

∥ [ ] −

^∗

∥ ≤

( ( ) − 1 ( ) + 1

)

∥ [0] −

^∗

∥

成立

(23)

最急降下法収束速

( ) = λ ( )/λ ( ) ≥ 1

∥ [ ] −

^∗

∥ ≤

( ( ) − 1 ( ) + 1

)

∥ [0] −

^∗

∥

収束次数

1

条件数

( )

近行列最大固有値最小固有値近収束速

条件数

( )

大行列最大固有値最小固有値比大収束遅可能性

(24)

線形方程式丸誤差

方程式

=

正則

̸ = 0

行列丸誤差

→ + ∆ , → + ∆

丸方程式

( + ∆ ) = + ∆

解 ^∗

+ ∆

^∗

(25)

丸誤差影響

行列対丸誤差

∆

十分小

∥ ∆ ∥ < 1

∥

⁻¹

∥

成立次不等式成立

∥ ∆

^∗

∥

^∗

∥ ≤ ( )

1 − ( ) ∥ ∆ ∥ ∥ ∥

⁻¹

( ∥ ∆ ∥

∥ ∥ + ∥ ∆ ∥

∥ ∥ )

.

( )

行列条件数

( ) := ∥ ∥∥

⁻¹

∥

(26)

丸誤差影響

∥∆

^∗

∥

^∗

∥ ≤ ( )

1 − ( ) ∥ ∆ ∥ ∥ ∥

⁻¹

( ∥∆ ∥

∥ ∥ + ∥∆ ∥

∥ ∥ )

.

条件数

( )

小丸誤差方程式影響少逆条件数

( )

大丸誤差方程式影響

大可能性

(27)

反復法線図表現

法

[ + 1] = −

⁻¹

( + ) [ ] +

⁻¹

= [ ] −

⁻¹

( + + ) [ ] +

⁻¹

= [ ] −

⁻¹

( [ ] − )

法

[ + 1] = [ ] − ( + )

⁻¹

( [ ] − )

最急降下法

[ + 1] = [ ] − α[ ]( [ ] − )

(28)

反復法線図表現

[ + 1] = [ ] − ( [ ] − )

+

[ ] − σ −

[0]

[ ]

( [ ] − )

連立線形方程式

数値計算