0.背景

搜索技術(shù)的很多方面的知識發(fā)現(xiàn)都依賴于特征值或奇異值問題，涉及到特征值計算問題。

計算特征值沒有直接的方法。

定位特征值的計算方法基于冪迭代的思想，這是求解特征值的一類迭代方法。該思想的一個復(fù)雜版本被稱為QR算法，是確定典型矩陣所有特征值的一般方法。

特征值問題若消減為求解根的問題，在稍有誤差的多項式上用根求解器求根，會帶來災(zāi)難性后果。

1.冪迭代法

冪迭代法的主要思想：占優(yōu)特征值對應(yīng)的特征向量在多次計算后會在計算過程中占優(yōu)。

主要方法：歸一化和與矩陣A相乘。

隨著迭代不斷改進(jìn)了近似的特征向量，那么如何得到特征值呢？瑞利商。

冪迭代法的局限：局限于求解絕對值最大的特征值。

冪迭代法的逆：如果冪迭代法用于矩陣的逆矩陣，可以找到最小的特征值。

現(xiàn)在我們知道了如何找出矩陣的最大或最小值，那么怎么找到其他的特征值呢？

冪迭代法這里給出了一個解決方法：

為了找出矩陣A在實數(shù)s附近的特征值，對（A-sI)^-1使用冪迭代法得到（A-sI)^-1的最大特征值b，則x=b^-1+s為矩陣A在實數(shù)s附近的特征值。

2.QR算法

QR算法是一種可以一次找出所有特征值的方法。

QR分解是把矩陣分解成一個正交矩陣與一個上三角矩陣的積。QR 分解的實際計算有很多方法，例如 Givens 旋轉(zhuǎn)、Householder 變換，以及 Gram-Schmidt 正交化等等。

設(shè)

for j=1,2,3...?

????????

end

? ? ??

上述過程可稱做歸一化同時迭代，在第j步，得到的的列是A的特征向量的近似，對角線元素是近似的特征值。

這種算法成為無移動的QR算法，但是它對于矩陣A的要求很嚴(yán)格（即A為對稱矩陣，且滿足特征值），即使A是對稱矩陣不滿足定理的條件時，也可能失敗。以及該算法難以做出修改以計算復(fù)數(shù)特征值，以及迭代速度比較慢。

因此我們需要做出一組改進(jìn)使得特征值計算更加一般化并加速收斂。

3.上海森伯格

上海森伯格的主要思想是使用上海森伯格形式的相似矩陣替換A，即在QR迭代之前應(yīng)用相似變換，在A中放置更多的0，同時保持特征值。此外，上海森伯格將消去QR迭代無法收斂到復(fù)數(shù)特征的問題。

上海森伯格矩陣形式如下圖所示：

那么怎么將矩陣A變換成上海森伯格形式呢？Householder變換。

Householder 變換

Householder 變換可以將向量的某些元素變成零，同時保持該向量的范數(shù)不變。

通過逐步在矩陣A的左側(cè)和右側(cè)乘上反射子H，從而得到一個具有相同的特征值的特征矩陣。

做3步運算的結(jié)果：

左側(cè)為我們得到的上海森伯格矩陣5x5矩陣，由于該矩陣和A相似，它與A具體相同的特征值以及特征值的重數(shù)。

一般的對于一個nxn矩陣A，需要n-2個Householder 步將A變成上海森伯格形式。

4.移動QR算法

移動QR算法則是利用冪迭代的技巧大大加速收斂速度。

為了減少計算量，一般先利用Householder矩陣將矩陣A變成擬上三角矩陣（上海森伯格形式）,然后采用雙步位移的QR方法計算的特征值。

使用雙步位移的QR方法求矩陣A全部特征值的具體算法過程如下：

5.高斯消去與LU分解

高斯消去

高斯消去是求解合適規(guī)模的線性方程的有用工具，可以有效地求解具有n個未知數(shù)的n個方程。高斯消去主要由兩個不等同的部分組成，相對計算代價龐大的消去過程，和相對計算代價小的回代過程。n個方程n個未知數(shù)的消去計算，可以在次操作后完成。

LU分解

LU分解是高斯消去的矩陣形式，它包含把系數(shù)矩陣A寫做下三角矩陣L和上三角矩陣U的乘積。其中，U矩陣是由傳統(tǒng)的高斯消去過程得到上三角矩陣，而對應(yīng)的L矩陣則是：把1放在主對角線上，然后乘子按消去時它們的特定位置放在下三角矩陣得到。

如何利用LU分解轉(zhuǎn)化回代步驟？

Ax=b ---> LUx=b --->c=Ux Lc=b?求c---> Ux=c 求x

但是，并不是所有的矩陣都可以進(jìn)行LU分解，我們需要在LU分解前做一些工作：部分主元。

部分主元

部分主元的思想是在每一步消除步驟之前，找到第一列中最大的一個元素，其對應(yīng)行和主元行進(jìn)行交換，即PA=LU。

高斯列主元法的優(yōu)勢在于它有一個選主元的過程，這樣做可以避免程序在進(jìn)行消去操作時選取的主元素為0的情況，也減小了計算的舍入誤差，從而提高了程序的普適性和結(jié)果的準(zhǔn)確性。文章來源地址http://www.zghlxwxcb.cn/news/detail-714175.html

到了這里，關(guān)于《數(shù)值分析》-3-特征值與特征矩陣的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！