Linear Equation

Linear Equation

「線性方程式」。僅由變數的加法、變數的倍率組成的方程式。

1 x + 2 y - 5 z = 5

System of Linear Equations

「線性方程組」。許多道線性方程式同時成立。

{ 1 x + 2 y - 5 z = 5
{ 2 x + 4 y + 6 z = 1
{ 3 x + 1 y + 7 z = 4

線性方程組求解,等同矩陣求解。儘管標題是Linear Equation,但是接下來要談的都是矩陣求解。

{ 1 x + 2 y - 5 z = 5        [ 1 2 -5 ] [ x ]   [ 5 ]
{ 2 x + 4 y + 6 z = 1  ===>  [ 2 4  6 ] [ y ] = [ 1 ]
{ 3 x + 1 y + 7 z = 4        [ 3 1  7 ] [ z ]   [ 4 ]
                                 A        x⃗       y⃗

另外,特殊矩陣擁有特殊演算法,稍微省時,詳情請見MATLAB的mldivide說明圖片。簡單起見,以下不介紹特殊矩陣的演算法。

Linear Equation: Gaussian Elimination

等量公理

相信大家已經學過如何解線性方程組:由上往下消除變數,變成階梯狀;由下往上解出變數,變成對角線。

由上往下消除變數的過程,就叫做「高斯消去法」。

演算法(Gaussian Elimination)

一個矩陣,化成上三角矩陣,對角線元素皆為一。

由上往下,處理每個橫條,實施三種運算:交換、倍率、相減。

如果橫條的首項係數不是零,以該橫條抵銷下方橫條,令下方橫條的首項係數化成零。如果是零,就往下找到非零橫條,先交換,再抵銷。

pivot row:首項係數不是零的橫條。
pivot:上述橫條的首項係數。
pivoting:找到pivot row,視情況進行交換。

減少誤差的方法:取絕對值最大的pivot row,抵銷其餘row。換句話說,首項係數絕對值最大的橫條,總是交換到上方,再來抵銷下方橫條。倍率小於1,相減誤差少。

矩陣邊長N×M,時間複雜度是O(N²M)。大家習慣討論方陣,N = M,時間複雜度是O(N³)。

方陣的高斯消去法,程式碼如下所示。矩陣的高斯消去法,留給大家自行練習。

解線性方程組

首先實施高斯消去法,求得上三角矩陣。

由下往上,處理每個橫條。把先前解出的變數,代入到目前橫條,解出變數。時間複雜度是O(N²)。

UVa 10109 10524 10828 ICPC 3563

LU Decomposition

http://ccjou.wordpress.com/2010/09/01/

高斯消去法可以改寫成LUP分解!時間複雜度是O(N³)。

交換橫條、抵銷橫條,可以改寫成矩陣乘法。一連串交換橫條、抵銷橫條,可以整併成三個矩陣連乘:下三角矩陣L、上三角矩陣U、列交換矩陣P。稱做「LUP分解」。

如果恰好都沒有交換橫條,則可忽略P。稱做「LU分解」。

LU分解的用途是解大量線性方程組Ax = b,A固定,b有許多組。這種情況下,LUP分解,每次求解需時O(N²);高斯消去法,每次求解需時O(N³)。

Cholesky Decomposition

對稱正定矩陣的LU分解。L與U將互相對稱。

時間複雜度仍是O(N³),但是步驟數量較少。

演算法(Gauss-Jordan Elimination)

「高斯喬登消去法」是延伸版本。對角線化成一、其餘化成零。

時間複雜度仍是O(N³)。

高斯喬登消去法也可以解線性方程組,但是步驟數量比較多。主要用途是求反矩陣。

求反矩陣

利用「高斯喬登消去法」。

求determinant

利用「高斯消去法」,對角線不化成一,保留原有數字。

上三角矩陣,對角線元素的乘積,便是determinant。

如果矩陣裡都是整數,那麼determinant也是整數。想避免浮點數誤差,可以使用輾轉相除法進行消去。時間複雜度是O(N³logC),C是絕對值最大的首項係數。

UVa 684

Linear Equation: Preconditioner

移項法則

所有等式一齊求反矩陣,繁文縟節,慢慢吞吞。

每道等式一一求反函數,化整為零,簡單明快。

演算法(Jacobi Method)

每回合依序計算x y z,一次處理一種變數。可以視作不動點遞推法的進化版本。

二維:

[ 4  3 ] [ x ] = [ 1 ]
[ 2  5 ] [ y ]   [ 2 ]

{ 4x + 3y = 1  => { x = (1 - 3y) / 4
{ 2x + 5y = 2     { y = (2 - 2x) / 5

[ x₀ ] = [ 0 ] 隨便設定一個初始值
[ y₀ ]   [ 0 ]
    
[ x₁ ] = [ (1 - 3y₀) / 4 ]
[ y₁ ]   [ (2 - 2x₀) / 5 ]
    
[ x₂ ] = [ (1 - 3y₁) / 4 ]
[ y₂ ]   [ (2 - 2x₁) / 5 ]

三維:

[ 4  3 -1 ] [ x ]   [ 1 ]
[ 2  5  1 ] [ y ] = [ 2 ]
[-2 -2  6 ] [ z ]   [ 3 ]

{  4x + 3y -  z = 1     { x = (1 - 3y +  z) / 4
{  2x + 5y +  z = 2  => { y = (2 - 2x -  z) / 5
{ -2x - 2y + 6z = 3     { z = (3 + 2x + 2y) / 6

[ x₀ ]   [ 0 ]
[ y₀ ] = [ 0 ] 隨便設定一個初始值
[ z₀ ]   [ 0 ]

[ x₁ ]   [ (1 - 3y₀ +  z₀) / 4 ]
[ y₁ ] = [ (2 - 2x₀ -  z₀) / 5 ]
[ z₁ ]   [ (3 + 2x₀ + 2y₀) / 6 ]

任意維度:

      Ax = b
(D+L+U)x = b             D是對角線、L是下三角、U是上三角
      Dx = b - (L+U)x
       x = D⁻¹ [b - (L+U)x]
x₀ = 隨便設定一個初始值
xₖ₊₁ = D⁻¹ [b - (L+U)xₖ]

時間複雜度是O(N²T),N是方陣維度,T是遞推次數。

高斯消去法直接得到正解。不動點遞推法逐步逼近正解。

判斷收斂:檢查D⁻¹(L+U)的特徵值的絕對值是否都小於1。

x = D⁻¹ [b - (L+U)x]
x = D⁻¹b - D⁻¹(L+U)x

滿足strictly diagonally dominant就保證收斂。不滿足時,可能收斂、也可能不收斂。

for each row, |Aii| > ∑ |Aij|
                     j≠i

演算法(Gauss-Seidel Method)

每回合依序計算x y z,剛出爐的數字,馬上拿來使用,加快收斂速度。

[ 4  3 -1 ] [ x ]   [ 1 ]
[ 2  5  1 ] [ y ] = [ 2 ]
[-2 -2  6 ] [ z ]   [ 3 ]

{  4x + 3y -  z = 1     { x = (1 - 3y +  z) / 4
{  2x + 5y +  z = 2  => { y = (2 - 2x -  z) / 5
{ -2x - 2y + 6z = 3     { z = (3 + 2x + 2y) / 6

[ x₀ ]   [ 0 ]
[ y₀ ] = [ 0 ] 隨便設定一個初始值
[ z₀ ] = [ 0 ]

[ x₁ ]   [ (1 - 3y₀ +  z₀) / 4 ]
[ y₁ ] = [ (2 - 2x₁ -  z₀) / 5 ]
[ z₁ ]   [ (3 + 2x₁ + 2y₁) / 6 ]
依序計算x₁、y₁、z₁,剛出爐的數字,馬上拿來使用,加快收斂速度。
xₖ₊₁ = D⁻¹ (b - Uxₖ - Lxₖ₊₁)

演算法(Successive Over Relaxation)

原數值、新數值,以固定比例混合。

[ x₁ ]   [ (1-w) ⋅ x₀ + w ⋅ (1 - 3y₀ +  z₀) / 4 ]
[ y₁ ] = [ (1-w) ⋅ y₀ + w ⋅ (2 - 2x₁ -  z₀) / 5 ]
[ z₁ ]   [ (1-w) ⋅ z₀ + w ⋅ (3 + 2x₁ + 2y₁) / 6 ]

Linear Equation: Eigendecomposition

Linear Equation與Algebra

線性方程組可以寫成矩陣乘法的形式。

{ 1 x + 2 y - 5 z = 5        [ 1 2 -5 ] [ x ]   [ 5 ]
{ 2 x + 4 y + 6 z = 1  ===>  [ 2 4  6 ] [ y ] = [ 1 ]
{ 3 x + 1 y + 7 z = 4        [ 3 1  7 ] [ z ]   [ 4 ]
                                 A        x⃗       y⃗

線性方程組得視作線性函數,解線性方程組得視作線性反函數。

                                                 -1
[ 1 2 -5 ] [ x ]   [ 5 ]        [ x ]   [ 1 2 -5 ] [ 5 ]
[ 2 4  6 ] [ y ] = [ 1 ]  ===>  [ y ] = [ 2 4  6 ] [ 1 ]
[ 3 1  7 ] [ z ]   [ 4 ]        [ z ]   [ 3 1  7 ] [ 4 ]
    A        x⃗       y⃗           x⃗         A⁻¹      y⃗

Inverse

一旦求得反矩陣,即可輕鬆解線性方程組。

solve Ax⃗ = y⃗  ===>  find A⁻¹, then x⃗ = A⁻¹y⃗

計算反矩陣,使用高斯喬登消去法,時間複雜度O(N³)。

不過與其採用高斯喬登消去法求反矩陣、再用反矩陣解線性方程組,不如直接採用高斯消去法解線性方程組。就當作是學個想法吧。

數學公式(Eigendecomposition)

求根、求不動點、求特徵點、求解是等價的,使得矩陣求解有著各式各樣的演算法。

線性函數的精髓:求得在特徵向量上的分量,分別伸縮,伸縮倍率是特徵值。線性反函數的精髓:逆向縮放,縮放倍率變成倒數。

             -1          T
A   = Q  Λ  Q   = Q  Λ  Q 

 -1       -1 -1       -1 T
A   = Q  Λ  Q   = Q  Λ  Q 

矩陣實施特徵分解,求反矩陣,再拿來解線性方程組。

以特徵值來判斷是否存在反矩陣。特徵值皆不為零,則有反矩陣。就這樣子。

不過與其採用特徵分解求反矩陣、再用反矩陣解線性方程組,不如直接採用高斯消去法解線性方程組。就當作是學個想法吧。

Linear Equation: Cramer's Rule

Linear Equation與Geometry

線性方程式得視作幾何元件:點、線、面、……。

ContourPlot3D[1 x + 2 y - 5 z == 5, {x, -5, 5}, {y, -5, 5}, {z, -5, 5}, Boxed -> False, Axes -> False, Mesh -> None]

線性方程組得視作一堆幾何元件的交集。

f := 1 x + 2 y - 5 z - 5; g := 2 x + 4 y + 6 z - 1; h := 3 x + 1 y + 7 z - 4; ContourPlot3D[{f == 0, g == 0, h == 0}, {x, -5, 5}, {y, -5, 5}, {z, -5, 5}, Boxed -> False, Axes -> False, Mesh -> None, ContourStyle -> Directive[Opacity[0.5]]]

數學公式(Cramer's Rule)

兩線交點的演算法:求得平行四邊形的面積,以面積比例求得交點位置。請見本站文件「Intersection」。

「克拉瑪公式」則是此演算法的高維度版本,形成了非常漂亮的公式解!求得超平行體的容積,以容積比例求得解。

linear equation:
  Ax⃗ = y⃗

solution:
  { x = det(Aˣ) / det(A)
  { y = det(Aʸ) / det(A)
  { z = det(Aᶻ) / det(A)

unisolvence:
   Ax⃗ = y⃗ has a unique solution   iff   det(A) ≠ 0

example:
  { 1 x + 2 y - 5 z = 5        [ 1 2 -5 ] [ x ]   [ 5 ]
  { 2 x + 4 y + 6 z = 1  ===>  [ 2 4  6 ] [ y ] = [ 1 ]
  { 3 x + 1 y + 7 z = 4        [ 3 1  7 ] [ z ]   [ 4 ]
                                   A        x⃗       y⃗
         _ y⃗                  _ y⃗                  _ y⃗
       [|5| 2 -5 ]       [ 1 |5|-5 ]       [ 1  2 |5|]
  Aˣ = [|1| 4  6 ]  Aʸ = [ 2 |1| 6 ]  Aᶻ = [ 2  4 |1|]
       [|4| 1  7 ]       [ 3 |4| 7 ]       [ 3  1 |4|]
         ‾                    ‾                    ‾

determinant是矩陣當中所有向量所構成的超平行體的容積。時間複雜度等於N+1次determinant的時間複雜度,O(N⁴)。

Determinant

determinant起初用來判定一個線性方程組是否有解、解是多少,因而稱作「決定因子」。古人沒有意識到determinant是容積。

字面意義是「決定因子」,中文教科書卻譯作「行列式」。真是異想天開的翻譯啊!

http://mathworld.wolfram.com/DeterminantExpansionbyMinors.html

行列式的計算過程是:先刪除一橫行,接著分別刪除每一直行,形成N-1個(N-1)×(N-1)子矩陣,添上正負號。原矩陣的行列式,等於這些子矩陣的行列式總和。每個子矩陣各自遞迴下去,直到N=1。1×1矩陣的行列式,等於矩陣元素。時間複雜度O(N!)。

N = 2 or 3的時候比較特別,可以直接累加所有「左上右下斜線」的乘積、累減「右上左下斜線」的乘積。中學數學課程有教。

計算行列式,也可以使用高斯消去法,時間複雜度O(N³)。

不過與其採用高斯消去法求行列式、再用行列式解線性方程組,不如直接採用高斯消去法解線性方程組。就當作是學個想法吧。

Linear Least Squares

Linear Least Squares(Linear Least Squares Equation)

唯一解是稀奇的,無解、多解是普遍的。無解、多解時,可以改為找到平方誤差最小的解。

solve Ax = b

 overdetermined system: 等式太多 -> 無解 -> 改求‖Ax - b‖²最小的解
underdetermined system: 等式太少 -> 多解 -> 改求‖x‖²最小的解

等式太多、等式太少(中學數學的講法是:變數少於等號、變數多於等號),兩種情況分別處理。嚴格來說,必須預先消去所有等價的、多餘的等式,以rank大小、矩陣邊長來區分這兩種情況。

一、等式太多因而無解:方程組每一道等式,求得等號左右兩邊的差的平方;累計所有等式,總和越小越好。

二、等式太少因而多解:解的每一項的平方,總和越小越好。

Least意指「盡量小」,Squares意指「平方和」。

平方誤差的優勢是:循規蹈矩,成為一個參考指標,誤差高低可以拿來比較,科學多了。缺陷是:計算速度慢。

平方誤差比起絕對值誤差,有三個好處:一、讓每道等式的誤差保持均勻,不會有某道等式誤差特別高。二、「一次微分等於零」容易推導數學公式。三、誤差函數是開口向上的拋物線函數,沒有鞍點,容易最佳化。

Linear Least Squares: Decomposition

三種數學公式

函式庫兜一兜,答案就出來了,大可不必深究細節。

solve overdetermined system Ax = b   minimize ‖Ax - b‖²

       T    -1  T          T       T
x = ( A  A )   A  b     ( A A x = A b )   Normal Equation

     -1 T
x = R  Q  b             ( A = Q R )       QR Decomposition

        +  T                       T
x = V  Σ  U  b          ( A = U Σ V )     Singular Value Decomposition
solve underdetermined system Ax = b   minimize ‖x‖²

     T      T -1  
x = A  ( A A )   b                        Normal Equation

         T -1              T
x = Q ( R )   b         ( A = Q R )       QR Decomposition

        +  T               T       T
x = U  Σ  V  b          ( A = U Σ V )     Singular Value Decomposition

Timus 1668

數學公式(Normal Equation)

http://people.csail.mit.edu/bkph/articles/Pseudo_Inverse.pdf

線性代數經典公式!視作最佳化問題,以微分求極值。

「一次微分等於零」的地方是極值、鞍點。因為平方誤差是開口向上的拋物面,所以「一次微分等於零」的地方必是最小值,而非最大值、鞍點。

以下只證明等式太多的情況。時間複雜度O(N³)。

solve  Ax = b
                 2
minimize ‖Ax - b‖

∂          2
―― ‖Ax - b‖ = 0                     「一次微分等於零」的地方是最小值
∂x
  ∂
[ ―― (Ax - b) ] [ 2(Ax - b) ] = 0   微分連鎖律
  ∂x
 T
A  [ 2(Ax - b) ] = 0                微分

 T       T
A A x = A b                         同除以2、展開、移項

       T    -1  T  
x = ( A  A )   A  b                 移項。注意到A的向量們必須線性獨立!

注意到最後一步,A的向量們必須線性獨立(事先清除冗餘的、無意義的變數),AᵀA才有反矩陣。

數學公式(QR Decompostion)

http://www.cs.cornell.edu/courses/cs322/2007sp/notes/qr.pdf

A = QR。將矩陣拆開成正規正交矩陣Q、零餘部分R。正規正交矩陣Q不影響最小值,最小值取決於零餘部分R。

以下只證明等式太多的情況。等式太少的情況,改為分解A的轉置矩陣Aᵀ = QR。

時間複雜度O(N³)。但是計算量比Normal Equation少。

solve  Ax = b

              2
min ‖ Ax - b ‖

       T          2
min ‖ Q (Ax - b) ‖         正規正交矩陣,變換後長度不變

       T       T   2
min ‖ Q A x - Q b ‖        展開

             T   2          T     T
min ‖ R x - Q b ‖          Q A = Q Q R = R

                 T     2
    ‖ [ R₁ x - Q₁ b ] ‖    R = [ R₁ ]  區分出零,讓R₁是方陣
min ‖ [          T  ] ‖        [ 0  ]  區分上段和下段
    ‖ [    0 - Q₂ b ] ‖ 

            T
令 R₁ x - Q₁ b = 0         此式有唯一解,可為零
               T   2
令最小值是 ‖ Q₂ b ‖ 

         T
R₁ x = Q₁ b                移項

     -1  T
x = R₁ Q₁ b                移項

數學公式(Singular Value Decompostion)

和QR分解的手法如出一轍。

以下只證明等式太多的情況。等式太少的情況,改為分解A的轉置矩陣Aᵀ = UΣVᵀ。

時間複雜度O(N³ + NK)。我不確定實務上是否比較快。

solve  Ax = b

              2
min ‖ Ax - b ‖

       T          2
min ‖ U (Ax - b) ‖       正規正交矩陣,變換後長度不變

       T       T   2
min ‖ U A x - U b ‖      展開

         T     T   2      T     T     T      T
min ‖ Σ V x - U b ‖      U A = U U Σ V  = Σ V 

      T     T
令 Σ V x - U b = 0       此式有唯一解,可為零

   T     T
Σ V x = U b              移項

        +  T
x = V  Σ  U  b           移項

Linear Least Squares: Optimization

Tikhonov Regularization

線性方程組,無解、多解時,改為最佳化問題,以得到唯一解。

                                       2
solve Ax = b   --->   minimize ‖Ax - b‖    [overdetermined system]

                                  2
solve Ax = b   --->   minimize ‖x‖         [underdetermined system]

甚至利用Regularization,追加其他最佳化目標。

                                       2
solve Ax = b   --->   minimize ‖Ax - b‖ + α f(x)   (α ≥ 0)

                                  2
solve Ax = b   --->   minimize ‖x‖ + α f(x)   (α ≥ 0)

線性方程組,有許多式子和變數。可能有其中一群變數與式子構成無解、另一群構成唯一解、剩下一群構成多解。更有甚者,切割一些群結果無解變多解、整併某些群結果多解變無解。

無法釐清是無解、多解的時候,那就兩個情況一起上吧。

                                       2        2
solve Ax = b   --->   minimize ‖Ax - b‖  + α ‖x‖    (α ≥ 0)
∂            2        2        
―― [ ‖Ax - b‖  + α ‖x‖  ] = 0    「一次微分等於零」的地方是極值、鞍點
∂x                               二次函數、恆正,必得最小值

   T         T
2 A A x - 2 A b + 2 α x = 0      展開

   T               T                             T
( A A + α I ) x = A b            移項,左式即是 A A 的對角線加上 α

左式是實數對稱正定方陣,有唯一解。時間複雜度O(N³)。

Homogeneous Linear Equation

討論特例b = 0的情況。當b = 0,則x = 0,缺乏討論意義。於是添加限制「x長度(的平方)為1」,增進討論意義。

                                   2               2
solve Ax = 0   --->   minimize ‖Ax‖  subject to ‖x‖ = 1
             2         2
minimize ‖Ax‖ - λ ( ‖x‖ - 1 )     Lagrange multiplier

∂        2         2
―― [ ‖Ax‖ - λ ( ‖x‖ - 1 ) ] = 0   「一次微分等於零」的地方是極值、鞍點
∂x                                 二次函數,必得極值

   T
2 A A x - 2 λ x = 0               展開

 T
A A x = λ x                       移項,此即特徵向量的格式

答案是AᵀA的最小的特徵值的特徵向量!又因為AᵀA是實數對稱半正定方陣,所以特徵值都是正數、零。

欲求最小的特徵值,可以採用QR Iteration或Lanczos Iteration演算法求得所有特徵值,再挑出最小的,時間複雜度O(N³ + N²K)。亦可採用Singular Value Decomposition的演算法,不必計算AᵀA,節省一點時間。

Basis Pursuit(Lasso)

改成L¹ norm,討論多解的情況。NP-hard。

solve Ax = b   --->   minimize ‖x‖₁ subject to Ax = b
                      [underdetermined system]

解法是改寫成線性規劃:

http://www4.ncsu.edu/~kksivara/masters-thesis/kristen-thesis.pdf

Basis Pursuit Denoising

無解採用L² norm、多解採用L¹ norm。走火入魔。

                                       2        2
solve Ax = b   --->   minimize ‖Ax - b‖  + α ‖x‖₁    (α ≥ 0)

Linear Inequality

System of Linear Inequalities

「線性不等式組」。許多道線性不等式同時成立。

正是計算幾何「Half-plane Intersection」推廣到高維度,所有解形成一個凸多胞形,也可能形成開放區間、退化、空集合。

目前沒有演算法。有人適度乘上負號,調整成Ax > b的格式,套用高斯消去法,但是不知道正不正確。

大家習慣採用線性規劃,將凸多胞形硬是位移至第一象限(各個變數加上一個足夠大的數值,代換成新變數),以符合線性規劃的格式。

Linear Equation: Conjugate Gradient Method(Under Construction!)

普通矩陣改成正定矩陣

     solve Ax = b       (A is invertible)
---> solve AᵀAx = Aᵀb   (AᵀA is symmetric positive definite)
---> solve A'x = b'     (unique solution)
     solve Ax = b       (overdetermined system: no solution)
---> min ‖Ax - b‖²      (least squares) (linear regression: rows of A are data)
---> solve AᵀAx = Aᵀb   (normal equation)
---> solve A'x = b'     (unique solution)

演算法(Conjugate Gradient Method)

請參考教學文《An Introduction to the Conjugate Gradient Method Without the Agonizing Pain》。以下僅歸納重點。

一、「一次函數求解」化做「二次函數求極值」。

f(x) = 1/2 xᵀAx - bᵀx + c。f′(x) = Ax - b。

xᵀAx是橢圓拋物面函數。等高線是同心橢圓。有唯一最小值。

1/2 xᵀAx - bᵀx是橢圓拋物面函數減去線性函數。等高線是一頭大一頭小的同心橢圓。有唯一最小值。

f(x)的最小值位於一次微分等於零的地方f′(x) = Ax - b = 0。

f(x)的最小值位置,就是Ax = b的解。

二、最佳化演算法。

給定現在地點x,給定現在移動方向d,請一步走到最低處xnext。推得步伐大小是-(f′(x) dot d) / (Ad dot d)。

一步走到最低處,畫成圖形就是等高線的切線。

current position is x
current direction is d
find next position xnext such that f(xnext) is minimum

{ xnext = x + d ⋅ step
{ f′(xnext) dot d = 0

f′(x + d ⋅ step)       dot d = 0
[A(x + d ⋅ step) - b]  dot d = 0
[Ax + step ⋅ Ad - b]   dot d = 0
[(Ax - b) + step ⋅ Ad] dot d = 0
[  f′(x)  + step ⋅ Ad] dot d = 0
f′(x) dot d + step ⋅ (Ad dot d) = 0
step = -(f′(x0) dot d) / (Ad dot d)   by the way f′(x) = Ax - b = r

順帶一提,分子分母再同除以d的長度平方。分子:當前梯度投影到移動方向。分母:虛擬特徵值Rayleigh Quotient。我不知道如何解釋幾何意義。

共軛梯度法(切線方向)、梯度下降法(法線方向)、座標下降法(座標軸方向)。

三、設定每一步的移動方向。

兩兩互相垂直dᵢ dot dⱼ = 0,逐漸趨近最小值,走無限步。

兩兩互相對A垂直Adᵢ dot dⱼ = 0,N步以內抵達最小值。

四、奇怪的演算法名稱。

論文作者取名gradient,然而演算法內容跟gradient無關。

論文作者將A-orthogonal改稱為conjugate。

演算法(Preconditioned Conjugate Gradient Method)

再加上Preconditioner。

Nonlinear Least Squares(Under Construction!)

三種最佳化演算法

梯度下降法:適用一次可微函數。牛頓法:適用二次可微函數。兩種混和。

演算法(Conjugate Gradient Method)

Normal Equation AᵀAx = Aᵀb,左側的AᵀA即是對稱正定矩陣。

演算法(Gauss-Newton Algorithm)

最佳化演算法Newton Method,針對平方誤差進行改良,速度更快。

演算法(Levenberg-Marquardt Algorithm)

視情況使用Conjugate Gradient Method或者Gauss-Newton Algorithm,兩害相權取其輕。