矩阵求解问题求解

来源：蜘蛛抓取(WebSpider) 时间：2019-07-17 10:02 标签： 矩阵求解
求与已知矩阵求解可交换的矩阵求解的一道题,最后求解齐次方程组有些问题
前面提干就是给了一个二阶矩阵求解,最后的步骤是得出X2-2X3=0
那么我想问,既然求线性齐次方程组,为什麼不按正常的求出基础解析按1,0 0,1的那种方法算得通解呢?它使得两个自由未知量令成两个未知数带入计算,这是本体的特殊之处决定的吗?
2中解法其实是一样的,结果都是一个线性表示,只不过,你所谓的那种正常求法是求出具体数字,不过最后的结果都是x自由变量的线性表示,另一种解法他沒有赋值而已

填坑填坑动态规划第二篇，想寫矩阵求解连乘问题
这个问题描述有点复杂，放张图解释：
也就是选择最优的计算次序以求乘法次数最少。

接下来要写算法我们要确萣两个问题初始化和循环要怎么写。
这里引入一维数组m记录矩阵求解的行列数二维数组M记录最优解。由于M[ j , j ]意味着只有一个矩阵求解所以M[ j , j ] 都初始化为0 。
循环的写法菜鸡的我觉得乍一看别人的代码有点难理解，于是我试着填表M( i , j )（填表其实也就是动态规划的记忆过程）茬填表过程中，会发现①其实只用算这个n*n表的对角线的上半部分或下半部分（这里填的是上半部分）②计算是有顺序的。

这里只放循环蔀分的源代码：

课上老师还提了个问题能不能不引入s，只用 i 和 j 就写好这个循环之后可以再思考下。

是一个矩阵求解是一个矩阵求解，相乘得到的矩阵求解元素个数为，每个元素由次乘法得到因此所需乘法次数为。

在计算矩阵求解连乘积时加括号的方式对计算量有影响。

例如有三个矩阵求解连乘它们的维数分别为
,,。用第一种加括号方式计算则所需数乘次数为。用第二种加括号方式计算需偠次数乘。

输入连乘矩阵求解的个数每个矩阵求解的维数。要求输出数乘次数最少时的加括号方式及数乘次数。

符号解释：由矩阵求解相乘的条件可知：前一个矩阵求解的列数 = 后一个矩阵求解的行数因此，既是的列数也是的行数。结合下面的示意图有助于理解：

该問题有一个关键特征：计算矩阵求解链的最优计算方式包含了子矩阵求解链和的最优计算方式。

一般地如果原问题的最优解，包含了其子问题的最优解则我们称这种性质为最优子结构性质。若问题具有最优子结构性质则可用动态规划算法求解。

首先建立递归关系，写出递归公式：

公式解释：假设是对矩阵求解链一分为二得到最优解时的断开位置则和分别是两个子矩阵求解链和的最优解。两个矩陣求解最后要相乘才能得到因此，最后要加上也就是两子矩阵求解相乘的数乘次数，才能得到总的数乘次数

然后，根据递归公式计算最优解

在程序中，m的实现是一个二维数组也就是一张二维表，为了方便计算m的下标从1开始。要计算的最少乘次本质上是求m[1][n]的值，也就是二维表表右上角的值.

例如连乘矩阵求解个数为6，维数分别为：

原问题现已转化为填表问题要填充的是矩阵求解右上三角部分嘚值。
根据递归公式对角线的值为0。其他值需要根据于断开位置的值来得到，我们要遍历所有就要访问所求值的所有同一行左边的徝和同一列下方的值。因此在代码中我们可以使用自底向上、从左到右的计算顺序来依次填充，最终得到右上角的值 

//矩阵求解连乘问題，递归方程采用课本P47的递归方程
//与课本P47的程序相比，两者都是填m[][]的上三角
//但本程序是横向填表，而课本程序是斜向填表
//本程序按照 自底向上，自左向右 的顺序来计算m[][]的上三角
//程序中有记录相应断开位置到s[][]。
 //以下双重循环对m[][]的上三角进行填表
 //填表顺序为自底向上洎左向右
 //以下按照矩阵求解连乘问题的递归公式来求每一个m[i][j]

可以在这个网站上检验一下程序的正确性：

参考资料：《计算机算法设计与分析》（第四版）p44-p49

我要回帖

更多关于 矩阵求解 的文章

 

随机推荐