選主元

樸素的高斯消元用主元——當前正在處理的對角元——去除每一行。數學上任何非零主元都行，但在電腦上，微小的主元是毒藥：除以一個接近零的數會產生巨大的乘數，而那些巨大的數會把矩陣其餘部分淹沒在捨入誤差裡。選主元就是這個簡單的修正：每步消元前，交換行使主元盡可能大。

選主元的標準做法是部分選主元：在當前列中從對角元往下掃描，把絕對值最大的那一行換到頂部。這保證每個乘數的絕對值至多為 1，故單步中沒有元素會失控增長。它產生的分解是 PA = LU，其中 P 是記錄交換的置換矩陣。完全選主元還會跨列搜尋整個剩餘子矩陣中的最大元；理論上更安全，但很少值得那份額外開銷。

更深一層的要點是：選主元正是讓高斯消元值得信賴的東西。沒有它，消元在再普通不過的矩陣上也可能災難性地不穩定；有了部分選主元，它在實踐中對你遇到的幾乎所有矩陣都變得後向穩定。代價僅是行交換的記帳——與算術相比微不足道。

有一點告誡值得知道：部分選主元在實踐中穩定，但在最壞情形下並非可證明穩定。存在人為構造的矩陣，其元素增長是指數級的。它們在實際應用中幾乎從不出現，這正是部分選主元仍是通用預設、而完全選主元只留給真正多疑者的原因。