為甚麼要控制中間元素?
在開始解三角方程組之前,高斯(Gauss)消去法先改變矩陣。即使原矩陣的每個元素都不大,中間元素仍可能變得大得多。這種元素增長在浮點誤差分析中很重要,因為中間運算會發生捨入。它不同於條件數:後者衡量數學問題本身對擾動的敏感程度。
先研究精確算術。設 非奇異。若有並列,可按任何指明的規則選取,下面的定義對每種規則都適用。
定義 2.2.1
(部分主元選取與增長因子)
在每一列,部分主元選取把當前行與剩餘行中該列元素絕對值最大的行交換。令 ,並令 表示第 階段換行之前尚未消去的活動矩陣。定義
其中最大值遍歷所有階段的活動元素,包括最後的 階段。 稱為這次消元的增長因子。
選出的主元非零:否則第 列的第 行均為零,前 列將屬於前 個座標向量的生成空間,從而線性相關。這與基本行運算保持的非奇異性矛盾。換行不改變元素絕對值的最大值。由於 非奇異, 且 。
一般上界
定理 2.2.2
(部分主元選取的增長界)
對每個非奇異的 和每種並列規則,在精確算術下做部分主元選取,都有
證明
(每個階段至多使最大元素加倍)
在第 階段,記選中的主元為 ,其列下方某個元素為 。部分主元選取保證 。剩餘子矩陣的每個元素滿足
其中 是消元之前活動元素絕對值的最大值。因此 。對 個消元階段歸納,得到 ,所以每個階段的每個活動元素的絕對值至多為 。
證明透視
因子二從何而來
非奇異性只用來保證每個階段的主元非零,使商 有意義且 。選主元規則恰好用了一次,即給出 。關鍵一步是三角不等式,而不是抵消論證:新元素是 減去 的一個絕對值至多為一的倍數,兩項的絕對值各自至多為 ,其差可以達到 。證明得以收尾,是因為不論並列規則如何,每個階段都有 ,所以 個階段給出 ;它並沒有說明哪些階段真的加倍。沒有選主元規則,這類結論便不再成立:對 ,不選主元時乘數為 ,新元素為 ,當 時無界。
這個界是最壞情況的結論:並不是說所有矩陣每一步都會翻倍,也不是說最終答案的相對誤差等於 倍機器精度。
達到上界的矩陣族
對於 ,定義 :對角線和最後一列填 ,前 列中嚴格位於對角線下方的元素填 ,前 列中對角線上方填 。例如,
命題 2.2.3
(增長達到最大的矩陣族)
對 做部分主元選取,並列規則為:當前行的主元絕對值若並列最大,就保留當前行。則不發生換行, 非奇異,並且 。
證明
(在保留當前行規則下消去 )
初始元素絕對值均不超過一。前 列的每一步中,主元為 、下方元素均為 ,所以乘數為 ,而該規則不換行。具體不變量是:第 階段的活動矩陣等於把 的最後一列乘以 所得矩陣(約定 )。 時成立。主元行在主元與最後元素之間全為零,所以加到每個下方行時只改變最後一列:下方各行的最後元素 變為 ,這正是第 階段的不變量。因此並列規則在每一步都適用。最後主元為 ,所以 非奇異;這個元素再配合增長界,便得 。
例題 2.2.4
(不換行地消去 )
第 1 階段主元為 ,把第 1 行加到每個下方行,得到下方各行 、、。活動的 塊為 ,即最後一列加倍的 。第 2 階段把主元行加到下方兩行,得到塊 ;第 3 階段再加一次,得到 。所得上三角矩陣為
由於 而最大的活動元素為 ,所以 。
例題 2.2.5
(對 採用另一種並列規則)
並列時選最下方的行。 的第 1 列所有元素絕對值都是一,所以第 1、3 行交換,得到 。乘數為 和 ,相應相減後得到 和 ,活動塊為 。第 2 列的主元為 、乘數為 ,最後主元為 。最大的活動元素絕對值為 ,故這一規則給出 ,而不是 。因此這個矩陣族說明某個允許規則達到最壞情況,而不是每個並列規則都產生相同增長。
反例模式
乘數有界並不保證與維數無關的增長界
在指定的並列規則下, 的乘數全部為 ,其增長因子卻為 。因此,控制每個乘數是有用的,但不會得到與維數無關的增長界。
不換行時的小主元
例題 2.2.6
(很小的首個元素)
對於 ,令
若不選主元,第一步乘數為 ,第二個主元為 ;當 時其絕對值無限增大。部分主元選取先交換兩行,乘數變為 ,第二個主元變為 。此時所有活動元素的絕對值至多為一,所以 。這個例子說明選主元如何避免巨大的中間元素,但並不能證明選主元總能防止增長。
增長、條件性與計算
增長因子依賴消元路徑和選主元規則;條件數依賴原矩陣及所選範數。任意一個數都不能單獨決定前向誤差。浮點後向誤差界涉及捨入、維數、分解因子和中間數值的大小;前向誤差還取決於問題的條件性。上面的精確算術計算只分離出其中一種機制,並不為特定實現聲稱通用的誤差證書。
常見錯誤
(把增長因子當成計算解的誤差)
界 比較的是精確消元中中間元素與原元素的大小。它並不表示計算出的解的相對誤差是機器精度的 倍;捨入和原問題的條件性另有影響。
常見錯誤
(把增長因子當成只由矩陣決定的量)
同一個矩陣在不同的允許並列規則下可以有不同增長: 保留當前行時 ,並列時選最下方的行則 。說出 的數值時必須指明選主元規則。
練習與解答
練習 2.2.7
(對 按保留當前行的並列規則消元,求增長因子。)
基礎
解答(3)
- 1
消去第 1 列
把第 1 行加到 的第 2、3 行,得到下方各行 和 。
依據: 主元為 ,兩個下方元素均為 ,所以乘數為 ,不換行。
- 2
消去第 2 列
活動塊為 ,主元為 ;把第 1 行加到第 2 行,最後位置得到 。
- 3
讀出增長因子
而 ,所以 。
快速檢查
(為甚麼部分主元選取保證乘數的絕對值至多為一?)
把每個下方元素與主元比較。
解答 · 答案
主元在活動列中的絕對值最大,因此每個下方元素都滿足 ,而乘數為 。
快速檢查
(在二維例子中取 ,比較換行和不換行時的第二個主元。)
計算 和 。
解答 · 答案
不換行時主元為 ;換行後為 。
快速檢查
( 是否聲稱計算出的解具有相應的相對前向誤差?)
回想 比較的是甚麼。
解答 · 答案
不。這個界控制精確消元中的中間大小相對於原元素的比例;捨入和原問題的條件性還需要另行分析。