ACM特殊利益集团在编程语言中,SIGPLAN,预计在一系列会议举行第四编程语言的历史2020年,明白了HOPL-IV。的论文初稿提交的8月,2018年。很长的时间让我有机会写一个详细的MATLAB的历史。我打算写论文部分,我会发布在这个博客是可用的。

MATLAB的第一个版本的数学基础开始卷由j·h·威尔金森和c . Reinsch编辑手册进行自动计算,卷二,线性代数著名的德国出版商出版的出版社,1971年。

内容

特征值

数学术语“特征值”是一个语言混合。在德国这个词是“特征值”。一个Web字典说,英语翻译是“内在价值”。但经过几十年使用术语“特征值”和“潜根”,数学家们放弃了试图翻译整个词和一般翻译只有第二个一半。

的特征值问题对于一个给定的矩阵一美元的任务找到标量\λ,美元可能对应的向量x美元,这样

x $ $ $ $ Ax = \λ

重要的是要区分情况一美元是对称的。后线性方程的问题,

$ $ $ $ Ax = b

特征值问题是最重要的在数值线性代数计算任务。

艺术的状态数值线性代数50年前,在1960年代,尚未提供可靠的、高效的方法求解矩阵特征值问题。软件库大杂烩的方法,其中很多是基于多项式根发现者。

吉姆·威尔金森讲述了这样一个故事:有两个这样的子程序,使用一个叫做贝尔斯托的方法和一个使用所谓的拉盖尔方法。他不能决定哪一个是最好的,所以他把它们放在一起在一个程序中,第一次尝试贝尔斯托的方法,然后打印一条消息,转而拉盖尔如果贝尔斯托失败了。经过几个月的频繁使用在国家物理实验室,他从来没有见过一个情况贝尔斯托失败了。他写了一篇论文推荐贝尔斯托的方法,很快收到读者的来信声称有一个例子,贝尔斯托无法处理。威尔金森尝试与程序的例子,他发现了一个bug。程序没有打印消息,切换到拉盖尔。

自动计算手册

1965 - 1970年期间,威尔金森和18的他的同事们发表了一系列论文Springer日报》Numerische Mathematik。提供的文件程序,编写的算法,求解线性方程的不同版本问题和特征值问题。这些都是研究论文显示结果的数值稳定性,微妙的细节实现,和,在某些情况下,新方法。

1971年,这些论文收集与修改,有时卷由威尔金森和Reinsch编辑。这本书是第一次出现是一个组织库密度算法的特征值问题,我们今天仍然使用MATLAB矩阵存储。尽可能使用正交变换的重要性被威尔金森和其他作者暴露。新发现的QR算法的有效性的j·弗朗西斯和相关LR算法的h . Rutishauser最近只有感激。

内容

阿果60程序每一章的重点。这些代码保持一个清晰的、可读的参考现代数值线性代数的重要思想。第一部分关于线性方程的体积是问题;第二部分是关于特征值问题。有40个程序在第一部分和43在第二部分。

这是第二部分的程序列表。过程名的后缀2表明它计算特征值和特征向量。“贝克”程序减少转换应用于特征向量。

许多程序处理降低形式,这是三对角对称或埃尔米特矩阵和Hessenberg(上三角+ 1副斜杆)非对称矩阵。,因为算法没有复数数据类型,复杂的数组是由成对的真正的数组。

对称矩阵

减少三对角
tred1、tred2 tred3、trbak1 trbak3	正交tridiagonalization。
乐队
bandrd	Tridiagonalization。
symray	特征向量。
bqr	一个特征值。
三对角
imtql1, imtql2	所有特征值向量,隐式QR。
tql1, tql2	所有特征值向量,明确QR。
ratqr	一些特征值,理性的QR。
平分	一些特征值,对切。
tristurm	一些特征值和向量。
一些特征值
ritzit	同时迭代。
雅可比方法
雅可比	雅可比方法。
广义的问题,Ax = \λBx
reduc1、reduc2 rebaka rebakb	对称,正定B。

非对称矩阵

减少Hessenberg
平衡,balbak	平衡(扩展)
dirhes、dirbak dirtrans	小学,innerprod积累起来的。
elmhes、elmbak elmtrans	小学。
奥尔特,ortbak ortrans	正交的。
乐队
unsray	特征向量。
Hessenberg
hqr, hqr2	所有特征值向量,隐式QR。
invit	几个特征向量,逆迭代。
范数减少
特征	特征值。

复杂的矩阵

comeig	规范减少雅可比。
comhes, combak	减少Hessenberg形式。
comlr, comlr2	复杂的LR算法。
cxinvit	逆迭代。

首选路径

的首选路径寻找一个真正的所有特征值,对称矩阵tred1紧随其后的是imtql1。首选路径寻找一个真正的所有特征值和特征向量,对称矩阵tred2紧随其后的是imtql2。

的首选路径寻找一个真正的所有特征值,非对称矩阵balanc,elmhes,最后hqr。首选路径寻找的所有特征值和特征向量的真实的,非对称矩阵balanc,elmhes,elmtrans,hqr2,最后balbak。

QR和QL

“QR”和“QL”是正确的,左撇子或向前和向后,版本的相同的算法。条款中描述的算法通常是一个矩阵分解成正交因素,Q,和一个上层或右三角因子,r .这导致QR算法。但原因与分级矩阵和终止循环1而不是n - 1手册的作者,决定使用左三角和QL算法。

历史上的注意

当文件从Numerische Mathematik收集形成了1971手册进行自动计算,卷二,线性代数,几乎所有人转载没有改变。但是,尽管它的脚注说什么,贡献II / 4,隐式QL算法,从未出现在杂志上。半页纸的论文是合并奥斯汀Dubrulle早些时候,R.S.马丁和威尔金森的贡献。Dubrulle能够减少内部循环的操作数。

贡献的作者手册列出的II / 4 a . Dubrulle R.S.马丁和J.H.威尔金森,尽管他们三人从来没有真正在一起工作。适当的信贷,但恐怕一个有趣的历史已经丢失。

Dubrulle版的隐式三对角QR算法仍然是重要的今天。在未来的文章中,我将描述如何手册导致EISPACK, LINPACK LAPACK。在LAPACKimtql1和imtql2功能结合成一个命名的子例程DSTEQR.F内循环的代码非常类似于奥斯丁的注意。

年后这贡献,奥斯汀回到研究生,是我的一个在新墨西哥大学的博士生。他的论文是关于矩阵的奇异值的分布来源于照片。

得到了MATLAB代码

发表与MATLAB®R2017a