矩阵分块乘法的证明

2024-08-26 12:20
文章标签 矩阵 证明 乘法 分块

本文主要是介绍矩阵分块乘法的证明,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

      设A是一个m \times l的矩阵,B是一个l \times n的矩阵,

A_{m \times l} = \left( \begin{matrix} a_{11} & \cdots & a_{1l} \\ \vdots & \qquad & \vdots \\ a_{m1} & \cdots & a_{ml} \end{matrix} \right)           B_{l \times n} = \left( \begin{matrix} b_{11} & \cdots & b_{1n} \\ \vdots & \qquad & \vdots \\ b_{l1} & \cdots & b_{ln} \end{matrix} \right)

A和B的分块矩阵分别记为  A^{'}B^{'} ,

A^{'}_{s \times t} = \left( \begin{matrix} A_{11} & \cdots & A_{1t} \\ \vdots & \qquad & \vdots \\ A_{s1} & \cdots & A_{st} \end{matrix} \right)        B^{'}_{t \times r} = \left( \begin{matrix} B_{11} & \cdots & B_{1r} \\ \vdots & \qquad & \vdots \\ B_{t1} & \cdots & B_{tr} \end{matrix} \right)

证明AB = A^{'}B^{'}.

证明:设

AB = \left( \begin{matrix} e_{11} & \cdots & a_{1n} \\ \vdots & \qquad & \vdots \\ a_{m1} & \cdots & a_{mn} \end{matrix} \right)     e_{ij} = \sum_{k=1}^l a_{ik} b_{kj} 

A^{'}B^{'} = \left( \begin{matrix} C_{11} & \cdots & C_{1r} \\ \vdots & \qquad & \vdots \\ C_{s1} & \cdots & C_{sr} \end{matrix} \right)  C_{ij} = \sum_{k=1}^t A_{ik} B_{kj}

      要证明AB = A^{'}B^{'},可以首先证AB和A^{'}B^{'}是同型矩阵,即证明A^{'}B^{'}是一个m \times n的矩阵,接着再证AB = A^{'}B^{'},可以把AB做一个与A^{'}B^{'}同样的分块,然后证明相同位置的分块相等。关于矩阵分块,这里有几个结论,1)处于同一行的分块,它们包含的行数相同,2)处于同一列的分块它们包含的列数相同,3)两个可以相乘的分块矩阵,左边矩阵的第i列的分块包含的列数和右边矩阵的第i行的分块包含的行数相同,左边矩阵对行分块及右边矩阵对列分块没有什么限制。

       我们先定义两个函数L和H,L用于获取矩阵分块包含的列数,H用于获取矩阵分块包含的行数,令L(A_{ij}) = l_j (1\leqslant i \leqslant s) 有l_1+l_2+\cdots+l_t=l,同时令H(B_{ij}) = h_i (1 \leqslant j \leqslant r),有h_1+h_2+ \cdots + h_t = l,并且有l_i = h_i(1 \leqslant i \leqslant t),令H(A_{ij}) = h^{'}i(1 \leqslant j \leqslant t),有 h^{'}_1 + h^{'}_2 + \cdots + h^{'}_s = m,令L(B_{ij}) = l^{'}_j(1 \leqslant i \leqslant t),有l^{'}_1 + l^{'}_2 + \cdots + l^{'}_r = n。因为C_{ij} = \sum_{k=1}^t A_{ik} B_{kj},所以H(C_{ij}) = H(A_{ik}) = h^{'}_iL(C_{ij}) = L(B_{kj}) = l^{'}_j,所以C_{ij}是一个h^{'}_i \times l^{'}_j的矩阵,所有与C_{ij}在同一行的子块包含的行数都相同,所有与C_{ij}在同一列的子块包含的列数都相同,所以C_{ij}仍然是一个分块矩阵,A^{'}B^{'}包含的行数为\sum_{i=1}^sH(C_{ij}) = \sum_{i=1}^sh^{'}i = m, 包含的列数为\sum_{j=1}^rL(C_{ij}) = \sum_{j=1}^rl^{'}_j = n,所以A^{'}B^{'}是一个m \times n矩阵,即证明了A^{'}B^{'}和AB是同型矩阵。

       接下来证明AB = A^{'}B^{'}

       把AB做与A^{'}B^{'}同样的分块,记为

            AB = \left( \begin{matrix} E_{11} & \cdots & E_{1r} \\ \vdots & \qquad & \vdots \\ E_{s1} & \cdots & E_{sr} \end{matrix} \right)     只需证明E_{ij} = C_{ij}即可。                           

       要证明E_{ij} = C_{ij},只要证明它们的同位置元素相等,也就是证明(E_{ij})_{uv} = (C_{ij})_{uv},让我们来各自求这两个元素,看它们是否相等。

      先求(E_{ij})_{uv},先求(E_{ij})_{uv}的行列号,H((E_{ij})_{uv}) = H((E_{ij})_{1v}) + u - 1 = \sum_{r=1}^{i-1}H(E_{rv}) + 1 + u -1 = \sum_{r=1}^{i-1}h^{'}_r + u

 令\sum_{r=1}^{i-1}h^{'}_r为p,则H((E_{ij})_{uv}) = p + u

L((E_{ij})_{uv}) = L((E_{ij})_{u1}) + v - 1 = \sum_{c=1}^{j-1}L(E_{uc}) + 1 + v -1 = \sum_{c=1}^{j-1}l^{'}_c + v

\sum_{c=1}^{j-1}l^{'}_c为q,L((E_{ij})_{uv}) = q + v,则(E_{ij})_{uv} = e_{p+u, q+v} = \sum_{k=1}^l a_{p+u,k}b_{k,q+v}

接下来求(C_{ij})_{uv}C_{ij} = \sum_{k=1}^t A_{ik} B_{kj},所以(C_{ij})_{uv} = \sum_{k=1}^t (A_{ik} B_{kj})_{uv} = (A_{i1}B_{1j})_{uv} +(A_{i2}B_{2j})_{uv} + \cdots + (A_{it}B_{tj})_{uv}

      下面看如何计算(A_{ik} B_{kj})_{uv},根据矩阵的乘法规律,它是用A_{ik}的第u行乘以B_{kj}的第v列得到,

      H((A_{ik})_{u1}) = H((A_{ik})_{11}) + u - 1= \sum_{r=1}^{i-1}H(A_{r1}) + 1 + u - 1 = \sum_{r=1}^{i-1}h^{'}_r + u = p+u

      L((A_{ik})_{u1}) = \sum_{c=1}^{k-1}L(A_{ic}) + 1 = \sum_{c=1}^{k-1}l_c + 1

      H((B_{kj})_{1v}) = H((B_{kj})_{11}) = \sum_{r=1}^{k-1}H(B_{rj}) + 1 = \sum_{r=1}^{k-1}h_r + 1

      L((B_{kj})_{1v}) = L((B_{kj})_{11}) + v -1 = \sum_{c=1}^{j-1}L(B_{kc}) + 1 + v - 1= \sum_{c=1}^{j-1}l^{'}_c + v = q + v

      A_{ik}的第u行为:\{ a_{p+u, w}|\sum_{c=1}^{k-1}l_c + 1 \leqslant w \leqslant \sum_{c=1}^{k}l_c \}

      B_{kj}的第v列为:\{b_{w,q+v}|\sum_{r=1}^{k-1}h_r + 1 \leqslant w \leqslant \sum_{r=1}^{k}h_r \}

     别忘了有l_i = h_i(1 \leqslant i \leqslant t),于是(A_{ik} B_{kj})_{uv} = \sum_{w=h_1+h_2+\cdots+h_{k-1} + 1}^{h_1+h_2+\cdots+h_k}a_{p+u,w}b_{w,q+v},       (C_{ij})_{uv} = \sum_{k=1}^t (A_{ik} B_{kj})_{uv} = (A_{i1}B_{1j})_{uv} + (A_{i2}B_{2j})_{uv} + \cdots + (A_{it}B_{tj})_{uv} = \sum_{w=1}^{h_1}a_{p+u,w}b_{w,q+v} + \sum_{w=h_1 + 1}^{h_1+h_2}a_{p+u,w}b_{w,q+v} + \cdots + \sum_{w=h_1+h_2+\cdots+h_{t-1} + 1}^{h_1+h_2+\cdots+h_t}a_{p+u,w}b_{w,q+v} = \sum_{w=1}^{h_1+h_2+\cdots+h_t}a_{p+u,w}b_{w,q+v} = \sum_{w=1}^{l}a_{p+u,w}b_{w,q+v}

     (E_{ij})_{uv} = (C_{ij})_{uv},因此AB = A^{'}B^{'}

     证明完毕。

这篇关于矩阵分块乘法的证明的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1108548

相关文章

hdu 4565 推倒公式+矩阵快速幂

题意 求下式的值: Sn=⌈ (a+b√)n⌉%m S_n = \lceil\ (a + \sqrt{b}) ^ n \rceil\% m 其中: 0<a,m<215 0< a, m < 2^{15} 0<b,n<231 0 < b, n < 2^{31} (a−1)2<b<a2 (a-1)^2< b < a^2 解析 令: An=(a+b√)n A_n = (a +

hdu 6198 dfs枚举找规律+矩阵乘法

number number number Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Problem Description We define a sequence  F : ⋅   F0=0,F1=1 ; ⋅   Fn=Fn

线性代数|机器学习-P35距离矩阵和普鲁克问题

文章目录 1. 距离矩阵2. 正交普鲁克问题3. 实例说明 1. 距离矩阵 假设有三个点 x 1 , x 2 , x 3 x_1,x_2,x_3 x1​,x2​,x3​,三个点距离如下: ∣ ∣ x 1 − x 2 ∣ ∣ 2 = 1 , ∣ ∣ x 2 − x 3 ∣ ∣ 2 = 1 , ∣ ∣ x 1 − x 3 ∣ ∣ 2 = 6 \begin{equation} ||x

【线性代数】正定矩阵,二次型函数

本文主要介绍正定矩阵,二次型函数,及其相关的解析证明过程和各个过程的可视化几何解释(深蓝色字体)。 非常喜欢清华大学张颢老师说过的一段话:如果你不能用可视化的方式看到事情的结果,那么你就很难对这个事情有认知,认知就是直觉,解析的东西可以让你理解,但未必能让你形成直觉,因为他太反直觉了。 正定矩阵 定义 给定一个大小为 n×n 的实对称矩阵 A ,若对于任意长度为 n 的非零向量 ,有 恒成

python科学计算:NumPy 线性代数与矩阵操作

1 NumPy 中的矩阵与数组 在 NumPy 中,矩阵实际上是一种特殊的二维数组,因此几乎所有数组的操作都可以应用到矩阵上。不过,矩阵运算与一般的数组运算存在一定的区别,尤其是在点积、乘法等操作中。 1.1 创建矩阵 矩阵可以通过 NumPy 的 array() 函数创建。矩阵的形状可以通过 shape 属性来访问。 import numpy as np# 创建一个 2x3 矩阵mat

【UVA】10003-Cutting Sticks(动态规划、矩阵链乘)

一道动态规划题,不过似乎可以用回溯水过去,回溯的话效率很烂的。 13988658 10003 Cutting Sticks Accepted C++ 1.882 2014-08-04 09:26:49 AC代码: #include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include

算法练习题17——leetcode54螺旋矩阵

题目描述 给你一个 m 行 n 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。  代码 import java.util.*;class Solution {public List<Integer> spiralOrder(int[][] matrix) {// 用于存储螺旋顺序遍历的结果List<Integer> result = new ArrayList

线性代数 第六讲 特征值和特征向量_相似对角化_实对称矩阵_重点题型总结详细解析

文章目录 1.特征值和特征向量1.1 特征值和特征向量的定义1.2 特征值和特征向量的求法1.3 特征值特征向量的主要结论 2.相似2.1 相似的定义2.2 相似的性质2.3 相似的结论 3.相似对角化4.实对称矩阵4.1 实对称矩阵的基本性质4.2 施密特正交化 5.重难点题型总结5.1 判断矩阵能否相似对角化5.2 已知两个矩阵相似,求某个矩阵中的未知参数5.3 相似时,求可逆矩阵P,使

高精度加法,乘法,阶乘

#include <iostream>#include <map>#include <string>#include <algorithm>using namespace std;const int Max = 50000;string str1,str2;/***********乘法***********/void chenfa(){cin >> str1>>str2;int a

最大子矩阵和问题归纳总结

一,最大子矩阵问题: 给定一个n*n(0< n <=100)的矩阵,请找到此矩阵的一个子矩阵,并且此子矩阵的各个元素的和最大,输出这个最大的值。 Example: 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 其中左上角的子矩阵: 9 2 -4 1 -1 8 此子矩阵的值为9+2+(-4)+1+(-1)+8=15。 二,分析 子矩阵是在矩阵