Chapter 10. 數值分析III─求解方程組(2)

 

 

 

疊代法(Iteration method)

  1.Jacobi method

例:

                     (1)

將式(1)之各方程式依序以為未知數,移項成

   

                     (2)

   

 

(2)中,每個方程式之右邊若為已知,則可求出新的如此疊代步驟稱之為(Jacobi method)

<Jacobi.F90>

Jacobi方法需要起始值(initial gauss)

 

令此例initial gauss

疊代次數

1

2

3

28

32

0

3.75

-1.333

2.001

2.000

0

-8

-1.917

-1.996

-2.000

0

4.3333

0.417

3.002

3.000

 

 

 

理論推導

*            

    

        

  

 

疊代方式

上式代表疊代之新值全部用前一次所有變數知已知值來計算

 

 

 

2.Gauss-Seidel method

Jacobi method 疊代之新值,全部用前一疊代之舊值,Gauss-Seidel method ,則將以依序求得之新值再帶入計算式中

 

例如前例為

 

<Gauss-Seidel.F90>

 

X

1

2

3

4

5

.

0

3.75

-5.042

-0.339

6.305

.

0

-19.25

-6.205

8.799

2.601

.

0

-3.333

3.946

7.379

3.099

.

 

.

51

52

53

54

55

56

.

2

2

2

2

2

2

.

-1.999

-1.999

-2

-2

-1.999

-2

.

3

3

3

3

3

3

 

收斂在56次疊代方收斂

 

 

Remark

(1)            Jacobi & Gauss-Seidel method選擇係數較大的項當作待求之值,收斂較快,Ex.

大,則變動小

(2)            Gauss-seidel method一般較Jacobi收斂快,但不完全是必然的

 

例:將上例方程式稍作對調

 

   (0,0,0)為起始值

   Jacobi方法發散

   Gauss-Seidel method方法9次疊代收斂

 

 

 

鬆弛法(Relaxation method)

1.Southwells relaxation method:先修正誤差較大之方程式之參數

例:

   

   

如果為正確值,則方程式之左邊值等於右邊值

如果不為正確值,則方程式之左邊值不等於右邊值

所以將此差值令成殘差(Residual)R

 

 

 

2.鬆弛法之步驟

Eq

1

-1

-0.125

0.125

2

0.143

-1

0.286

3

-0.222

-0.111

-1

 

     

 

 

0

 

0

 

0

 

 

1000

 

571

1333

1333

 

 

167

 

381

 

-1333

 

1167

1167

 

952

 

0

 

 

-1167

 

167

 

-259

 

 

0

1119

1119

 

-259

 

 

-140

 

-1119

 

-124

 

 

-140

 

0

-383

-383

 

 

-48

 

-109

 

383

 

-189

-189

 

-109

 

0

 

 

+189

 

-27

 

42

 

 

0

-136

-136

 

42

 

 

17

 

136

 

15

 

 

17

 

0

57

57

 

 

7

 

16

 

-57

 

24

24

 

16

 

0

 

 

-24

 

3

 

-5

 

 

0

19

19

 

-5

 

 

-2

 

-19

 

-2

 

 

-2

 

0

-7

-7

 

 

-1

 

-2

 

7

 

-3

-3

 

-2

 

0

 

 

3

 

0

 

1

 

 

0

-2

-2

1

1

 

 

1000

 

1001

 

 

 

 

 

 

 

 

 

 

(1)        上方成組織正確解,但近似解之誤差至小數點第三位,此因為捨去誤差(round-off)所造成

(2)        利用鬆弛法之疊代過程次數亦多,故改變鬆弛比值如上例,鬆弛0.9倍,鬆弛0.75

Eq

1

-1

-0.125

0.125

2

0.143

-1

0.286

3

-0.222

-0.111

-1

 

 

 

 

 

 

0

 

0

 

0

 

 

 

1000

 

571

1000

1333

 

 

125

 

286

 

-1000

1013

1125

 

857

 

333

 

 

-1013

 

144

 

-225

 

 

112

1001

1001

 

108

 

 

-125

 

-1001

 

-111

 

-12

 

 

 

-1

 

 

-13

12

-1

0

-1

1

 

 

-2

 

 

 

 

 

0

-2

-2

2

0

0

 

 

 

 

 

 

 

 

-3

3

0

0

0

0

 

 

 

1000

 

 

999

 

 

1000

 

     

 

如果鬆弛大小超過1稱為overrelaxing

如果鬆弛大小小於1稱為underrelaxing

3.  (1)一般而言,overrelaxing較佳於underrelaxing(但不是絕對)

(2)Southwell方法不適用於程式設計,故可把鬆弛法之概念加上

Gauss-Seidel 之數值方法,加速收斂效果

Gauss-Seidel法對方程式之疊代標準式()

 

                  (1)

 

  (1)前之已經重新疊代過,故其值為已知,但後的

  尚未重新疊代,故未知,代前一疊代之舊值

  將式(1)加入之舊值

 

               (2)

 

  (2)Gauss-Seidel之公式,式(2)右邊第一項為第n次疊代

  之值,而第二項為第n次及n+1次疊代值之殘差(residual)如果

  此殘差加入鬆弛概念來加速其收斂,此鬆弛因子稱為

  overrelaxation factor值介於1.0~2.0之間

 

             (3)

   2.10節為例

 

收斂疊代次數

1.0

9

1.02

9

1.04

9

1.06

8  optimum

1.08

8  optimum

1.1

10

1.12

11

 

 

非線性方程組(Systems of nonlinear equations)

例:

             (1)

            (2)

(1)代表半徑為2之圓

(2)代表指數曲線exponential function

 

(1)Fixed-Point iteration

  

  

solution

 

<NFixed.F90>

  

(若取負號)

(若取正號)

X

y

x

y

0

0

0

0

-2

0

2

0

-2

0.865

2

-6.389

-1.803

0.865

-6.061

-

-1.803

0.865

 

 

 

 

 

(2) Newton method

將式(1)及式(2)之正確解為

若以泰勒級數展開

         (3)

若取至一階微分項

  

                    (4)

  

 

<NNewton.F90>

 

           

 

 

1

2

3

4

5

6

7

8

9

x

1

2.5

1.7794

1.2368

.0398

1.0078

1.0043

1.0043

1.0042

1.0042

y

0

-4.507

-2.1134

-1.3643

-1.5487

-1.6868

-1.7211

-1.7281

-1.7294

-1.7296

x

-1

-2.5

-1.904

-1.8247

-1.8225

-1.8221

-1.8200

-1.8191

-1.8184

-1.8163

y

0

0.7098

0.6736

0.6817

0.7008

0.7178

0.7128

0.7461

0.7578

0.0872

 

Newton

(1)            演算前之微分工作

(2)            矩陣元素共個,函數n個共需計算個值

(3)            收斂速度快

Summary總結

l    線性

n    矩陣:

Gauss 消去法

Gauss-Jordan

n    疊代:

Jacobi method

Gauss seidel method

n    鬆弛法:

Overrelaxition method

Underrelaxation method

 

l    非線性:

疊代法 iteration method            

牛頓法 Newton method

 

l    norm

 

l    ill-condition

 

l    Conditionnumber

CNill-condition

 


 

 

        下一章節        回章節目錄        回到課程介紹首頁        回OCENGLAB首頁