首页 > 其他分享 >线性代数 A 的 LU 分解

线性代数 A 的 LU 分解

时间:2024-02-19 11:15:07浏览次数:31  
标签:begin end 转置 矩阵 times LU bmatrix 线性代数 分解

我们本章的目的是对 \(A=LU\) 进行分析,我们以这种思路来看待高斯消元。

好现在还是从简单的开始。

首先,讲一下上一章中没讲完的内容——乘积的逆。

假设 \(A\) 和 \(B\) 均是可逆矩阵,即有:

\[A·A^{-1} = I = A^{-1}·A \]

那 \(AB\) 的逆是什么?使用单独的逆相乘吗?是的。

用矩阵 \(A\) 的逆和 \(B\) 的逆相乘,什么顺序?反顺序相乘。因此有:

\[(AB)(B^{-1}A^{-1})=I \]

所以 \(A^{-1}B^{-1}\) 就是我们所求的东西。这里可以把括号抹去,想怎么乘就怎么乘,因为括号可以移动,矩阵有乘法结合律

首先应该把什么乘起来?\(B\) 乘以 \(B\) 的逆,乘积为单位矩阵;\(A\) 乘以 \(A\) 的逆得到单位矩阵。

关于为什么逆矩阵顺序要反过来,就相当于原来你先脱鞋子在脱袜子,他的逆动作就该是先穿鞋子,再穿袜子,而不是先穿鞋子再穿袜子(bushi。

回到刚才的例子,还要放到另一侧来检验:

\[B^{-1}A^{-1}AB=I \]

由于下一章可能会涉及到转置,这里就做一个铺垫。

如果转置某可逆方阵,那么其转置的逆是什么?

首先,\(A\) 矩阵可逆:

\[AA^{-1}=I \]

两侧同时转置,则就要涉及到矩阵转置了。转置单位矩阵会得到什么?还是单位矩阵对吧,不管怎么转置行和列,因为单位矩阵是对称的所以不会有变化。如果我对左边的乘积进行转置,这还是得改变两者的顺序。分别转置两个矩阵,然后以相反顺序相反顺序相乘。

注:矩阵 \(A\) 的转置记作 \(A^T\)

\[(A^{-1})^TA^T = I \]

这个公式的推导可以说是一目了然,它也足以告诉我们答案了,什么是矩阵 \(A\) 的转置的逆?就是\((A^{-1})^T\) 。

然后我们惊奇的发现:

\[(A^{-1})^T = (A^T)^{-1} \]

也就是说,转置和逆这两种运算,对于单个矩阵而言,顺序可以颠倒。好,这些就是我们将要用到的基础公式。

接下来,我们回到我们的主题 \(A\) 的 \(LU\) 分解。

我假设有一个矩阵 \(A\) 它是一个具有一切美好性质的矩阵。考虑 \(2 \times 2\) 的情况。

\[A=\begin{bmatrix} 2&1\\ 8&7 \end{bmatrix} \]

所以 \(E_{2,1}\) 是多少?

很显然,

\[U = \begin{bmatrix} 2&1\\0&3 \end{bmatrix}\,\,\,\,\, E_{2,1} = \begin{bmatrix} 1&0\\-4&1 \end{bmatrix} \]

有:

\[\quad \quad E_{2,1}·A = U \\ \begin{bmatrix} 1&0\\-4&1 \end{bmatrix} \begin{bmatrix} 2&1\\ 8&7 \end{bmatrix}=\begin{bmatrix} 2&1\\0&3 \end{bmatrix} \]

我们开始计算:

\[\begin{equation} A = LU\\ \begin{bmatrix} 2&1\\ 8&7 \end{bmatrix}= L \begin{bmatrix} 2&1\\ 0&3 \end{bmatrix} \end{equation} \]

所以,这里的 \(L\) 是什么,它和 \(E_{2,1}\) 有什么关系?是逆。因为如果两边同时乘以 \(E_{2,1}\) 的逆 \(\dots\)

\[\begin{aligned} E_{2,1}·A·(E_{2,1})^{-1}&=U·(E_{2,1})^{-1}\\ I·A&=U·(E_{2,1})^{-1}\\ A&=U·(E_{2,1})^{-1}\\ \therefore L&=(E_{2,1})^{-1}\\ \because (E_{2,1})^{-1}&=\begin{bmatrix} 1&0\\ 4&1 \end{bmatrix}\\ \therefore L&=\begin{bmatrix} 1&0\\ 4&1 \end{bmatrix} \end{aligned} \]

好,这是 \(2 \times 2\) 的情况。那么,\(L\) 代表什么?为什么用字母 \(L\) ?

\(U\) 代表上三角矩阵(\(Upper\)),\(L\) 表示下三角矩阵(\(Lower\))。

可以看到,他的对角线上都是 \(1\) 因为对角线上都是主元,有时我们会把主元单独列出来:

\[\begin{aligned} A&=LDU\\ \begin{bmatrix} 2&1\\ 8&7 \end{bmatrix}&= \begin{bmatrix} 1&0\\ 4&1 \end{bmatrix} \begin{bmatrix} 2&0\\ 0&3 \end{bmatrix} \begin{bmatrix} 1&\frac{1}{2}\\ 0&1 \end{bmatrix} \end{aligned} \]

\(D\) 表示对角矩阵 (\(Diagonal\))

下面不能只停留在 \(2 \times 2\) 了,这里的例子非常简单。

接下来考虑 \(3 \times 3\) 的情况:

\[\begin{aligned} E_{3,2}E_{3,1}E_{2,1}A&=U \,\,\,\,\,(No\,\,Row\,\,Exchanges)\\ A&={E_{2,1}}^{-1}{E_{3,1}}^{-1}{E_{3,2}}^{-1}U\\ &=LU \end{aligned} \]

我们假设一下:

\[E_{3,2}=\begin{bmatrix} 1&0&0\\ 0&1&0\\ 0&-5&1\\ \end{bmatrix} \quad E_{2,1}=\begin{bmatrix} 1&0&0\\ -2&1&0\\ 0&0&1\\ \end{bmatrix} \]

有:

\[\begin{bmatrix} 1&0&0\\ 0&1&0\\ 0&-5&1\\ \end{bmatrix} \begin{bmatrix} 1&0&0\\ -2&1&0\\ 0&0&1\\ \end{bmatrix}= \begin{bmatrix} 1&0&0\\ -2&1&0\\ 10&-5&1\\ \end{bmatrix}=E \longleftrightarrow EA=U \]

下面我要反顺序计算它的逆:

\[\begin{bmatrix} 1&0&0\\ 2&1&0\\ 0&0&1\\ \end{bmatrix} \begin{bmatrix} 1&0&0\\ 0&1&0\\ 0&5&1\\ \end{bmatrix}= \begin{bmatrix} 1&0&0\\ 2&1&0\\ 0&5&1\\ \end{bmatrix}=L \longleftrightarrow A=LU \]

对于 \(A=LU\) 如果不存在行交换,消元乘数可以直接写入 \(L\) 中。

我们考虑一个问题,**一个 \(n \times n\) 的矩阵 \(A\) ,需要多少次操作? **

令 \(n=100\) 假设矩阵中没有 \(0\) 。

第一步,

经过一步操作,剩下的就是 \(99 \times 99\) 的方阵了,因为主元已近在 \((1,1)\) 的位置,第一行已经固定,第一列同样的已经固定,剩下的也就是 \(99 \times 99\) 的方阵了。

那么,最终需要多少步?注意我们算的是时间复杂度(粗略理解就行,可能叫时间复杂度有点不太严谨),不是消元的次数。

所以,

\[Cost\,\,of\,\,A=n^2+(n-1)^2+(n-2)^2+\dots+1^2\approx\frac{1}{3}n^3\\ Cost\,\,of\,\,B=n^2 \]

下面讲讲置换(\(Permutations\)),考虑 \(3 \times 3\) 的情况。

有矩阵 \(\begin{bmatrix} 1&0&0\\ 0&1&0\\ 0&0&1 \end{bmatrix}\) ,通过一次置换可以得到: \(\begin{bmatrix} 0&1&0\\ 1&0&0\\ 0&0&1 \end{bmatrix}\) 、 \(\begin{bmatrix} 0&0&1\\ 0&1&0\\ 1&0&0 \end{bmatrix}\) 、

\(\begin{bmatrix} 1&0&0\\ 0&0&1\\ 0&1&0 \end{bmatrix}\) 、 \(\begin{bmatrix} 0&1&0\\ 0&0&1\\ 1&0&0 \end{bmatrix}\) 、 \(\begin{bmatrix} 0&0&1\\ 1&0&0\\ 0&1&0 \end{bmatrix}\) 。

仔细观察会发现这个矩阵群很有意思,将它们两两相乘,得到的矩阵仍然在这六个矩阵之中。

置换矩阵有一个很奇妙的性质:

\[P^{-1}=p^T \]

它的逆等于其转置。我最后再讲一点,考虑 \(4 \times 4\) 的情况,有多少种转置矩阵?显然是 \(24\) 种。

本章到此结束。

预告:下一章的内容是转置和置换

标签:begin,end,转置,矩阵,times,LU,bmatrix,线性代数,分解
From: https://www.cnblogs.com/SCAtlas-lxy23/p/18019105

相关文章

  • 在k8S中,Fluentd的工作原理是什么?
    在Kubernetes(k8s)中,Fluentd作为日志收集器和转发器,其工作原理主要包括以下几个关键步骤:数据收集:Fluentd在Kubernetes集群中通常以DaemonSet形式部署,确保每个Node节点上都有一个Fluentd实例运行。Fluentd使用输入插件(InputPlugins)从各个容器的日志源获取数据......
  • OpenResty 介绍与实战讲解(nginx&lua)
    目录一、概述二、OpenResty安装三、OpenResty的工作原理四、OpenResty核心模块1)ngx_lua模块2)ngx_stream_lua模块3)ngx_http_lua_module模块4)ngx_http_headers_more模块5)ngx_http_echo模块6)ngx_http_lua_upstream模块7)ngx_http_redis模块8)ngx_http_proxy_connect_module......
  • flutter开发Future与Stream的理解和区别
    flutter开发Future与Stream的理解和区别Future特点Future是表示一个异步操作的单个结果,只返回一次结果。通常用于处理一次性的异步操作。Future通过then()和catchError()方法来处理异步操作的结果和异常。Future使用await关键字来等待异步操作完成。FutureBuilder:通过监听......
  • Splunk ES 接入 log 的方式
    SplunkES接入log的方式主要有两种:使用SplunkUniversalForwarder(UF)UF是一个轻量级的代理,可以安装在各种操作系统和设备上。它可以收集各种类型的日志文件,并将它们发送到SplunkES进行索引和分析。使用HTTPEventCollector(HEC)HEC是一个RESTfulAPI,可以......
  • luogu2119题解
    本题考察对于枚举的方式对程序的性能的提升。有一个小的优化,\(n\)的范围比\(m\)的范围小,由于我们不关心顺序,我们既可以在值域上枚举也可以在物品上枚举,这里为了优化在值域上枚举更好。最简单的枚举是直接枚举\(a,b,c,d\)或是枚举其中三个数枚举另一个,时间复杂度为\(O(n^4)......
  • FluentFTP实战:轻松操控FTP文件,创造高效传输体验
     概述:通过FluentFTP库,轻松在.NET中实现FTP功能。支持判断、创建、删除文件夹,判断文件是否存在,实现上传、下载和删除文件。简便而强大的FTP操作,提升文件传输效率。在.NET中,使用FluentFTP库可以方便地实现FTP的相关功能。以下是判断文件夹是否存在、文件夹的创建和删除、判断文......
  • https://www.luogu.com.cn/problem/P8762
    引言题目链接:https://www.luogu.com.cn/problem/P8762思路首先可以发现到第i个数列末尾时,其前面总共有\(i*(i+1)/2\)个数所以可以用二分判断l和r处于第n1和n2个数列中,则前面完整的序列个数即为n1-1和n2-1。假设完整的序列为n个,则这n个序列的和为n......
  • 2.17 闲话 & solution『登陆宇宙/带着你所幻想的所有/灵魂加速失控 』
    拜谢了,您别Fake了,您当年自愿退出国集我是极力反对的,我知道您从小学一年级开始打NOI并且直接获得了金牌分数线上的好成绩,肆意AK了好几年NOI,直到近年才意识到自己太过强大只好肆意控分,NOIP2023的题目您当时拿到的一瞬间用\(\frac{2}{3}s\)就全部想到了正解,并在\(\frac{3}{2}......
  • Spring Boot + MyBatis-Plus 实现 MySQL 主从复制动态数据源切换
    MySQL主从复制是一种常见的数据库架构,它可以提高数据库的性能和可用性。动态数据源切换则可以根据业务需求,在不同场景下使用不同的数据源,比如在读多写少的场景下,可以通过切换到从库来分担主库的压力。在本文中,我们将介绍如何在SpringBoot中实现MySQL动态数据源切换,使用My......
  • 第二十三天:MYSQL集群Cluster
    一、MySQL主从复制 1、主从复制架构和原理读写分离复制:每个节点都有相同的数据集,向外扩展,基于二进制日志的单向复制2、复制架构(1)一主一从复制架构 (2)一主多从复制架构3、主从复制原理  主从复制相关线程主节点:dumpThread:为每个Slave的I/OThread启动一个dump线......