给定 n 个矩阵{A1,A2,A3,…,An},其中,Ai 和 Ai+1(i=1,2,…,n−1)是可乘的。
矩阵乘法如图 4-40 所示。用加括号的方法表示矩阵连乘的次序,不同的计算次序计算量(乘 法次数)是不同的,找出一种加括号的方法,使得矩阵连乘的计算量最小。
例如: A1是 M5×10的矩阵; A2是 M10×100的矩阵; A3是 M100×2的矩阵。 那么有两种加括号的方法: (1)(A1 A2)A3; (2)A1(A2 A3)。 第 1 种加括号方法运算量:5×10×100+5×100×2=6000。 第 2 种加括号方法运算量:10×100×2+5×10×2=2100。 可以看出,不同的加括号办法,矩阵乘法的运算次数可能有巨大的差别!
矩阵连乘问题就是对于给定 n 个连乘的矩阵,找出一种加括号的方法,使得矩阵连乘的 计算量(乘法次数)小。