簡單實用!3個德國人創造的線性迭代法,超越了一個時代_風聞
返朴-返朴官方账号-关注返朴(ID:fanpu2019),阅读更多!3小时前
今年12月26日是德國數學家高斯發明歷史上第一個線性迭代法200週年。在前不久發表的《怎樣迭代求解線性方程組?》的一文中,我們從基礎概念出發,釐清了迭代法求解線性方程組的準備知識和具體過程。這次我們將探討歷史上最有名氣、也最簡單實用的兩種一階定常迭代法:雅可比迭代法和高斯-賽德爾迭代法的基本思想和收斂性。
撰文 | 丁玖(美國南密西西比大學數學系教授)
我在前一篇《返樸》文章《怎樣迭代求解線性方程組?》中,為了能與適用於一般完備距離空間的壓縮映射定理掛上鈎,只給出了迭代法求解線性方程組的一個簡單的收斂性充分
條條大路通羅馬
好在我們還有其他的範數可用。作為通常直線段長度概念的直接推廣,n維歐幾里得空間
特徵值與譜半徑
然而,有一個收斂的充分必要條件等待着我們去挖掘,這個條件不再用到矩陣的範數,而是矩陣的譜。譜給出了矩陣不依賴於矩陣範數的一個內藴性質。方陣的譜是它所有特徵值全體組成的一個有限的複數集合。給定n階方陣M,我們稱複數λ為M的一個特徵值,如果復矩陣M - λI不是可逆的,即存在一個復的非零列向量x使得Mx = λx。這個x被稱為M對應於特徵值λ的一個特徵向量。我們曾經提到,一個矩陣是奇異的當且僅當它的行列式等於零,故λ是M的特徵值當且僅當det(M - λI) = 0,其中符號det表示行列式。如果把這個等式左邊中的λ看成是變元,根據行列式的定義,det(M - λI)的展開結果是關於λ的一個n階多項式,所以一個n階方陣M頂多有n個相異的特徵值。我們把M的所有特徵值絕對值中的最大值稱作 M的譜半徑,記為ρ(M)。
研究線性迭代的主要目的是數值求解線性方程組Ax = b,其中的係數矩陣A為非奇異的,
反過來,如果ρ(M) < 1,則存在一個足夠小的正數ε 使得ρ(M) + ε < 1。這一看似簡單的事實是實數的基本性質。另一方面,對於M的每一個特徵值λ和Rn上的任一個範數||•||,設x為λ所對應的一個特徵向量,由不等式||M|| ||x|| ≥ ||Mx|| = ||λx|| = |λ| ||x||以及x ≠ 0可知,剛剛獲得的不等式兩邊可以除以正數||x||,而得到不等式||M|| ≥ |λ|,從而可知:矩陣M的譜半徑ρ(M)是所有向量範數誘導出的矩陣範數在M的值||M||的一個下界。事實上,這個下界是對應於固定矩陣M的全部範數值||M||構成的實數集合的“下確界”,即這個集合的所有下界中的“最大下界”。“上、下確界”的概念是微積分學的最基礎、最重要的概念,真正學通了它,極限理論以及隨之而來的連續性、導數、積分、級數等等概念學起來甚至可以
雅可比迭代法和高斯-賽德爾迭代法
現在我們可以集中討論求解線性方程組Ax = b的雅可比迭代法和高斯-賽德爾迭代法了,其中A為n階可逆方陣。這兩種產自德意志的經典迭代法都是基於在矩陣分解A = N - P中對N和P的特殊選取,其迭代格式都可寫為
我們比較一下雅可比方法與高斯-賽德爾方法在迭代點分量計算過程中的顯著差別。由雅可比迭代法中n個分量的迭代公式可見,在第k - 1個迭代向量所有的分量都計算完畢後,第k個迭代向量的各個分量才一個接着一個地計算出來;換句話説,第k - 1步迭代獲得的全部分量都被用於對第k步迭代所有分量的計算。而對於高斯-賽德爾迭代法,每當需要算出第k個迭代向量的第i個分量時,不僅需要已完成計算的第k - 1個迭代向量從第i + 1到第n個分量幫忙,而且還需要正在進行中的本次迭代已得到的第k個迭代向量的第1到第i - 1個分量相助;或言之,高斯-賽德爾法比雅可比法“更急於求成”,命令當前迭代步驟中剛剛收入囊中的迭代點分量取代上一迭代步驟被“擒獲”的同下標分量,“披掛上陣”。這説明,高斯和賽德爾比雅可比更會“用兵”,不肯浪費半點士氣。
收斂條件
自然,無論是雅可比迭代法還是高斯-賽德爾迭代法,對矩陣A缺乏某些額外的假設條件,都不能保證其收斂性。那麼,當“A的對角線元素個個不能為零”這個先決條件被滿足後,什麼是保證它們收斂的充分條件呢?
這裏,保證雅可比迭代法收斂性的嚴格對角佔優的要求可以被改成不可約弱對角佔優,即上面的所有嚴格不等式換為一般不等式 “≥”,且至少有一個不等式嚴格成立,但增加了矩陣不可約的附加條件。如果一個方陣的行和列能以同樣的方式重新排列(不再排列也算“重新排列”,因為單位矩陣也是排列矩陣),結果變成一個2×2塊上三角矩陣,即矩陣的左下角有至少為1×1的0矩陣,那麼我們説這個矩陣是可約的,否則就説它是不可約的。