Vandermonde矩陣及其變形矩陣的快速求逆格式

1、福建師范大學(xué)學(xué)報(bào)（自然科學(xué)版） JOURNAL OF FUJIAN TEACHERS UNIVERSITY 13 (2): 1520 （NATURAL SCIENCE） 1997 Vandermonde矩陣及其變形矩陣的快速求逆格式葉貽才(計(jì)算機(jī)科學(xué)系)摘 要 導(dǎo)出在實(shí)算中頗具實(shí)用的關(guān)于-陣及其變形矩陣的一種快速求逆格式，.算術(shù)運(yùn)算量為，,算法格式緊湊、簡便，并給出具體算例。關(guān)鍵詞 -陣，變形矩陣，逆陣，反遞推關(guān)系Vandermonde矩陣（簡稱-陣）以及它的變形矩陣是實(shí)際計(jì)算中一類結(jié)構(gòu)特殊的著名的常見矩陣，關(guān)于-陣求逆問題的探討，早為人們所關(guān)注。50年代以來，有關(guān)這方面的研究文章相繼出現(xiàn)（如

2、文13等）。某些算法，其運(yùn)算量可從降至，甚至更小。誠然，運(yùn)算量小，對于節(jié)省機(jī)時(shí)，減少舍入誤差的影響，改善算法的有效性等無疑是重要的.但是運(yùn)算量小，程序不一定相應(yīng)地化簡，而程序復(fù)雜（即使運(yùn)算量?。┑乃惴ㄔ谀承﹫龊舷率遣豢扇〉摹Ｒ虼?，從實(shí)算的角度，考慮一種運(yùn)算量盡量小，程序不復(fù)雜的手算格式有一定的意義。本文借助于V-陣與多項(xiàng)式之間的密切聯(lián)系，直觀地導(dǎo)出V-陣及其變形矩陣的一種簡易快速求逆算式。其運(yùn)算量為（這里記號2M和A分別代表一次乘（除）法和一次加（減）法），較通常求逆算法所需運(yùn)算量低了一個(gè)數(shù)量級。此外，該算法有效地使用遞推過程，無論用于人工手算(極具可操作性)或編程機(jī)算都很簡便。1 算法的構(gòu)成

3、任取一組互異實(shí)數(shù),可構(gòu)造一個(gè)實(shí)系數(shù)首1多項(xiàng)式： (1) 將視為實(shí)變量的函數(shù)，并記其偏導(dǎo)數(shù)為 ,有 (s=1,2,). (2)注意到有 (3)其中s,=1,2,.引入記號 (4)及 (4)這里 (=1,2,)是在處的導(dǎo)數(shù)?？蓪ⅲ?）式寫成 按已知算式當(dāng)()時(shí)陣皆可逆，且 (5)下面給出如何計(jì)算矩陣（它是一個(gè)轉(zhuǎn)置的Jacobi矩陣）的各元素的途徑。對任取的一組互異實(shí)數(shù)， ，再構(gòu)造一組相關(guān)多項(xiàng)式如下： (1) 當(dāng)=時(shí)即多項(xiàng)式（1），比較（1）兩邊系數(shù),可得以下遞推關(guān)系式: (=2,3,;=,-1,1). (6)注：(6)是韋達(dá)（Viete）定理的遞推形式. 引理1 (=2,3,;, -1,0)關(guān)于每

4、個(gè)(=1,2,)是對稱的(即交換任意兩個(gè)和, 值不變).證 因交換任意兩個(gè)和(),其結(jié)果只是改變(1)中右邊兩乘積因子的順序,積不變, 值也不變,得證.記為由,(,1)遞推算得的結(jié)果.于是,按引理1，遞推式(6)可改寫成為： (=2,3, ,1) (7) (,1). (7) 引理2 設(shè) (,1)為由數(shù)組, , (,1 )按遞推式(7)算得的值,則陣可以寫成: (8)證 由遞推關(guān)系(7),求關(guān)于的偏導(dǎo)數(shù),有 (,1),代入（4）的陣,立得（8）。證畢。 定理 1 對任取的一組互異實(shí)數(shù),Vandermonde矩陣的逆矩陣可以表示為的形式。即 （9）其中（=1,2,）,而（,1;,1）為先對整組,，

5、從遞推式（6），即 （=2,3,;,1）. (6)求得，即(,1).然后對數(shù)組, (,1 )從以下反遞推關(guān)系求出數(shù)據(jù)： （,1;,2）. (10)證 綜合（4）、（8）及（5）三式，就有（9）式成立。證畢。注：使用與定理1相同的條件和遞推關(guān)系，可得求算陣的變形矩陣的類似算式（略）。2 求逆算法的運(yùn)算量(略)和算例例 給定數(shù)組2,3,-5,7,-10,求由它構(gòu)成的陣的逆陣.解 形成中各對角元:算出.其中形成中各元:先按(6)算 然后按(10)式算出中各元(參見下式在陣旁標(biāo)出的箭頭、數(shù)據(jù)，它們示意按（10）逐行推算各元的順序、規(guī)則)。最后得逆陣的表示式：參考文獻(xiàn)123 Pan V.On compu

6、tations with dense structured matric4游兆永，線性代數(shù)與多項(xiàng)式的快速算法。上海：上?？萍汲霭嫔?，1980。A Scheme of the fast algorithm for Finding the Inverses of VandermondeMartices and their Deformed MarticesYe Yicai(Department of Computer Science)Abstract Introduces a scheme of the fast algorithm for finding the inverses of Vandermonde matrices and their deformed matrices.The algorithm operand required is .The scheme is quite compact and handy.Moreover,a concerete example illustrating the present algorithm procedure is gi