线性代数漫谈(六):欧式空间的单位正交基

May 24, 2018 at 9:56 am

由于欧式空间的向量具有几何度量性,因此,在欧氏空间中常用有度量性质的基。 单位正交基 定义7.1 设是维欧式空间的一个子集,如果 则称为的单位正交基(或称标准正交基,orthonormal basis)。 由定义可知,所谓单位正交基就是每个基向量都是单位长,而且基向量两两正交。例如,在中,自然基关于标准内积是单位正交基。需要注意的是,在一般的欧式空间中,我们首先需要证明单位正交基存在。 定理7.1 欧式空间恒有单位正交基。 证明 设是维欧氏空间的一组基,我们采用下面的做法(施密特正交化方法,Schmidt orthogonalization, or Gram–Schmidt process),由构造出的一组单位正交基。令 由于线性无关,所以,为使正交,即 可取 按照这个步骤,如果已经求出两两正交的非零向量,再令 (记为1式) 为使与正交,即 […]

线性代数漫谈(五):向量的坐标与内积空间

May 15, 2018 at 9:20 am

在上一篇中,我们引入了线性空间基的概念,基于它,我们可以使用“坐标”来简洁、统一地表示线性空间中的向量。在此之上,我们将一个更强大的功能引入线性空间:内积运算,从而可以度量向量的长度和向量之间的夹角。 向量的坐标 在之前的讨论中,我们并没有讨论基的序的问题,仅将它看作是普通的集合,而在进行坐标的讨论的时候,通常我们需要指定这些这些元素的“序”。(这里的“序”实际上指的是序上的不同,而不是大小,这里我们不引入偏序关系来讨论它。) 定义5.1 有序基(ordered basis) 记维线性空间的所有基构成的集合为,设,我们定义从到的一个映射,使得,(其中括号表示定义1.1所定义的有序对),则对于每一个在下的象为的元素,称为线性空间对于基的一组有序基。 在不会引起歧义的情况下,我们仍将有序基记为,并简称为基。需要注意的是,虽然表示法一致,原来的基是无序的,是的一个子集,而现在它实际上是的一个子集。 定义5.2 向量的坐标(coordinate) 设是维线性空间的一组有序基,如果中元素表示为,则其系数组构成的有序对叫做在有序基下的坐标(coordinate with respect to the basis),记作 由定义可见,中元素的坐标是由所选的基决定的,同一元素在不同的基下一般有不同的坐标。坐标是的一个元素,也称为关于基的坐标向量。 由定理4.3可知,有限维线性空间中每一个元素在给定的基下的坐标是唯一确定的,因此,给定了的一个基,中元素与中的向量一一对应;而且保持元素间的线性运算关系不变,即如果 ,则有 ,记为 […]

线性代数漫谈(四):有限维线性空间的基和维数

May 13, 2018 at 2:17 pm

在上一篇中,我们引入了线性相关性的概念,并在最后给出了连结“线性相关性”和“张成子空间的向量数量”的定理4.3和定理4.5。在本篇中,我们将从这两个定理出发,引入线性空间维数和基的概念,用来衡量线性空间的“大小”。 有限维线性空间的基和维数 如果线性空间的两个子集和都能扩张成,则由以及定理4.5,即得,再由又得到,从而有,这就是说,线性空间如果能被其两个线性无关的有限子集张成,则它们所含向量个数相同。如此,我们可以给出下面的定义。 定义5.1 有限维线性空间的维数(dimension) 如果线性空间的有限子集线性无关,且,则称为的一组基(basis),并称为的维数(dimension)(或说是维线性空间),记作。 如果,且是的有限子集,则中最大的线性无关向量的个数就是能张成的最少的向量的个数,也就是的维数。 例5.1 的维数是,所以称它为3维(维)向量空间,其中的向量也称为3维(维)向量。它的基叫做自然基。 例5.2 是3维线性空间,和都是的基。是维线性空间,是它的一组基,也叫自然基。 例5.3 线性空间的零子空间的维数为零,因为其中没有线性无关的向量。 在维线性空间中,任一向量都可唯一地表示为基的线性组合。由定理4.5的等价命题可知,在维线性空间中,任何个向量都是线性相关的(因为它们都可由基线性表示)。于是由定理4.3又可知,维线性空间中的任何个线性无关的向量组成的子集都是的基(因为,是线性相关的,因此可由线性表示),故。这表明,有限维线性空间的基并不唯一,但任一组基所含的向量的个数是唯一确定的。 下面讨论的子空间的基与的基的关系。 定理5.1 如果是维线性空间的一个子空间,则的基可以扩充为的基(即的基可以添加中若干向量成为的基)。 证明 事实上定理4.4已经为我们构造了一组符合要求的基。这里我们再给出另一种证法。 设的基,如果,则就是的基。如果,则必然存在使得线性无关,否则中的所有向量均可以由线性表示,则,与假设矛盾。如果,则定理得证,如果,则继续上述步骤,必存在,使得线性无关,这就是的基。 […]

线性代数漫谈(三):线性相关性

May 11, 2018 at 12:04 am

线性空间中向量的线性相关性是向量在线性运算下的一种性质,它是阐明线性空间理论的一个重要的基本概念。(事实上,我们更加关注“线性无关”这一对立性质) 定义4.1 线性相关(linearly dependent) 设是一个线性空间,,如果存在不全为0的,使得成立,则称线性相关,否则称为线性无关(linearly independent)。 向量线性相关的等价定义是:若中有一个向量可由其它向量在域上线性表示,则称线性相关。我们把这个等价的定义做为定理来证明。 定理4.1 中的向量组线性相关的充分必要条件是中有一个向量可由其它向量在域上线性表示。 证明 首先证明必要性。根据线性相关的定义,如果线性相关,必然存在,使得,两边同加上相应的负元,得到 由于,存在乘法逆元,使得,由分配律可得右边可以表示为向量组不包含的一个线性组合,必要性得证。 再证充分性。如果存在一个向量可以被不包含的向量组除去后线性表示,则两边加上的负元,即可得,其中,而1不为0,得证。 定理4.1的等价命题 线性无关的充要条件是其中任意一个向量都不能由其余向量线性表示。 例4.1 维几何空间的基是线性无关的,其中是第个分量为1,其它分量全为0的向量。因为,由,即,必有 例4.2 线性空间中单个向量线性相关的充分必要条件是是零向量。因为时,等式成立的充分必要条件是。例4.2解释了我们采用定义4.1而不是定理4.1来定义线性相关的原因。定义4.1可以涵盖单个向量线性相关的定义,而定理4.2并不能,需要增加额外的说明,不够统一。 例4.3 […]

线性代数漫谈(二):线性空间的基本性质

May 4, 2018 at 12:13 am

随着两篇铺垫的结束,在上一篇的最后,我们引入了线性空间的定义。但是为什么要这样定义线性空间?这样的定义实际上抽象出了哪些性质?本篇将介绍线性空间的基本性质,以对线性空间有个初步的了解。 线性空间的基本性质 在讲线性空间的基本性质之前,我们首先通过一些示例,来了解它。 例1 全体空间向量和全体元实向量分别组成的集合和对向量的加法和数乘运算都构成实数域上的线性空间。实际上,线性空间可以理解为是对几何向量的一种抽象,这也是它也称为向量空间的原因。但实际上,具有线性性质的并不止几何向量一种。 例2 系数属于域的全体多项式的集合,以及次数小于额全体多项式同零多项式一起组成的集合,它们对多项式的加法和数乘多项式运算在数域上都构成线性空间。因为:它们关于两种运算封闭;它们对加法构成交换群;数乘多项式显然满足定义中的4条性质。但是,数域上的多项式集合对同样的运算不构成线性空间,因为集合对加法不封闭。 例3 定义在区间上的全体实值函数,对通常的函数加法和实数与函数的乘法,在实数域上构成一个线性空间。其零元是零函数,每个函数的逆元是。 例4 实数集在实数域上对实数的加法和实数与实数的乘法,构成实数域上的一个线性空间。但是,实数集在复数域上,对实数的加法和复数与实数的乘法不构成复数域上的线性空间,因为复数与实数的乘积一般不属于实数集,即对数乘不封闭。而复数集在实数域上和复数域上,对相应的加法和数乘运算分别构成实空间和复空间。 定义3.1 减法 在线性空间中,我们定义减法为:,其中是加法的逆元,也称为负元。 性质3.1 (1)线性空间作为交换群,它的零元是唯一的,每一个元的负元是唯一的; (2)数乘运算的分配律对元素的减法和数量的减法也都成立,即 证明: (2),两边同加上即得;另一组分配律同理可证。 性质3.2 […]

线性代数漫谈(一):一切从线性空间开始

April 27, 2018 at 7:17 am

在上一篇第零篇中,我们从集合论的一些基本概念出发,定义了运算和映射。这一篇将要把概念慢慢特化,讨论线性代数中所涉及的运算和映射。线性代数运作在线性空间之上,按照当代数学的划分,“线性空间”的概念归属于抽象代数(abstract algebra),为此,我们使用抽象代数的基础知识,群、环和域,过度到线性空间中。 群、环和域 代数结构是抽象代数的主要研究对象,群、环和域是最具代表性的几种代数结构。 定义2.1 代数结构(algebraic structures,或称代数系统,algebraic systems) 对于非空集合,如果在上面定义了一系列的运算,则称是一个代数结构,记作。[1] 定义2.2 群(group),交换群(commutative group,或称阿贝尔群,abelian group,或称加法群),半群,含幺半群 一个定义了(二元)代数运算的代数结构称为群: (1)运算满足结合律,即; (2)关于运算存在单位元(identity element),即,使得 (3)中每个元素关于都可逆,即,,使得(单位元),并称为可逆元,为的逆元(inverse element),记作 是一个群,也可以表述成关于构成群。 […]

线性代数漫谈(零):映射与运算

April 25, 2018 at 12:56 am

这个系列将会是一个纯数学的系列,不过考虑到线性代数自身概念相对抽象,会尽量多地结合实际的例子。线性代数的应用相当广泛,算是之后将要开展的系列的一个基础工具,数学是基础的基础,追本溯源,还是要先从线性代数开始讲起。 为了使线性代数的相关内容能够形成一个相对完整的体系,我们从最基础的概念讲起,逐步走入线性空间中去。在这之间,作为本系列的第零篇,我们需要首先熟悉映射和运算的概念。 映射与运算 定义1.1 有序对(或称有序二元组、序偶,ordered pair) 我们把非空集合的任一对有次序的元素叫做有序对,记为。[1] 定义1.2 笛卡尔积(Cartesian product,或称直积,direct product) 设是两个非空集合,我们把集合称为和的笛卡尔乘积(或称直积)。 定义1.3 映射(mapping, or map) 一个从集合到集合的一个映射是由一些满足的有序对(x,y)构成的集合,要求对于每一个,有且只有一个有序对(x,y)在这个集合中,记作。对于在这个集合中的有序对(x,y),称是在下的象(image),称是在下的原象(preimage),记作或者。称为的定义域(domain),并把的全体元素在下的象的集合称为的值域(range),或称为的象,记作或,即。集合到它自身的映射,有时也称为的变换(transformation)。[2] 定义1.4 代数运算(operation) 映射,其中称为定义在n个集合上,取值在上的n元代数运算,n称为代数运算的元数(arity)。特别地,如果,那么称这个n元代数运算为上的一个n元代数运算,简称为n元运算;更特别地,由于我们接下来讨论的主要是二元代数运算,对于二元代数运算,在不引起混淆的情况下,简称为代数运算。 […]

C++中的位域以及实现一个抽象位域类

March 17, 2017 at 11:52 am

这里说的位域(bit-field)是C/C++语言中的一个概念,它用来为struct/class/union中的成员指定特定的以位为单位的尺寸。之所以要写这个,是因为今天看到了一个位域类的实现,这个类似乎能更方便的使用位域,那就看看它到底如何实现的,顺道把位域复习一遍。说实话在实际项目中没有写过位域,一方面除了C/C++语言,一般的语言都没有这个特性;另一方面,位域在一般的项目中使用较少,仅会出现在偏底层的一些代码中。似乎偶尔在面试中会有关于位域的题目,有段时间学习过一下,不过现在也基本上忘光了,博客也好久没更了,暂时就先补上这一篇。 本文主要有如下几个内容: 1. 位域的基本概念 2. 位域内存占用和pack 3. 实现一个抽象位域类 位域的基本概念 位域通常用于代替一些位操作,典型的使用场景比如占1至2个比特的标记位,如果直接使用bool来定义这个标记位,将会浪费内存空间,32个只有true/false的标记位使用位域只需要4字节,而如果全部定义为bool则需要32个字节;一个典型的方法是将这32个标记位用一个32位的整数表示,每个标记位通过对这个整数的位操作来代替,从功能上来说,位域只是对于代码编写者(阅读者)而言比位操作更加直观一点的方式,通常来讲CPU并没有对特定位进行操作的指令,所以位域操作最终仍会被编译器转化为底层的位操作指令。 如果不需要考虑到内存空间的浪费,或者已经习惯对数字的位操作,那么位域并不是必须的。 下面给出一个最简单的位域的例子(例子引用自 http://en.cppreference.com/w/cpp/language/bit_field): #include <iostream> struct S { // three-bit […]

[非技术向]LevelDb源码阅读总结

February 17, 2017 at 1:19 pm

又是一段时间没有更新博客了。这段时间主要有两件事,一件还是在过春节假期,另一件则是在抄写(真正意义上的抄写)LevelDb。抄写的过程根据git的提交记录来看从1月14日到2月16日大约一个月的时间,按照实际的提交次数来看,大约是不到两周,每天约6个小时,抄写的是LevelDb的1.7.0版本,原版本刨去测试性的代码大约1.3万左右,最后总计抄的大约1.2万,因为按照计划昨天应该要干完这件事,今天写个总结,所以稍微有些烂尾(挖坑不填的本性暴露无疑)。整体上基本保证了可运行,昨天或多或少修了重写抄过程中的的一些错误,基本的std::map型的功能可以得到保证,但是真正要拿来用是不太现实的,可能还存在很多bug,代码仅仅自己可以用了吧。本来打算在抄完之后写一点具体一点、技术性强一点的总结,最后发现,毕竟BigTable已经10多年,LevelDb也有六七年的历史了,相关的技术性文章很多,网上中文的源码解析也非常多非常全,所以最后打消了这种想法,打算写一篇对源码阅读抄写的认识、和阅读LevelDb的源码过程中的一些收获。 本文主要有以下几个小节: 1. 对LevelDb源码进行阅读的初衷 2. 源码抄写的一些感想 3. 从抄写中学到的一些东西 这里列出两篇个人觉得LevelDb源码解析的比较技术向、全面、透彻的中文文章以避免吃瓜观众不小心踩了坑不好跳出去: malolk.com/2016/10/11/leveldb-1.19源码阅读/ www.qkldx.net/topic/64/leveldb原理探究与代码分析 对LevelDb源码进行阅读的初衷 LevelDb是由Google的两位大牛Jeffrey Dean和Sanjay Ghemawat编写的开源的持久化KV存储的库(这两位也是BigTable论文的主要作者之二),在写这篇文章时(2017-2-17)已经发布1.18版本,源码现在已经托管在github上,并遵循New BSD协议。LevelDb的最初版本就考虑可移植性,所以现在应该支持大多的主流平台,具体的我就懒得查了。LevelDb自身是以库的形式提供的,而不是一个完整的数据库产品,没有服务器端、通信协议之类的约定,仅仅是做存储,所以阅读LevelDb的源码是无法看到一个完整的数据库的全貌的;LevelDb是inpired by BigTable的,简单地可以理解为BigTable的一个开源实现,它的整体设计,包括MemTable, SSTable,都和BigTable论文中描述的基本一致;我看的是相对早期的版本1.7.0,没有和现在的版本做过完整的对比,但从部分文件的对比来看没发现有什么较大变化;LevelDb 1.7.0由C++写成,有一个简单的C接口,整体大约1.8万行的代码,除去C接口、移植性相关代码、测试相关代码后大约1.3万行,属于可以全部阅读的代码量。 […]

条件变量入门

January 19, 2017 at 10:14 pm

好久没更了呃。最近终于闲下来瞎看了一些东西,但是目前能单独整理出来的并不多,关于条件变量,算是第2次接触了,但是见到的时候还是一脸蒙蔽,所以这次更详细地学了一下。本来打算再看一下用条件变量来解决生产者消费者问题,研究一下条件变量的实现细节的,但是相关内容比较多,而且条件变量目前用到的并不多,所以暂时不多做展开,就是简单入一下门好了。 本文包含一下几个小节: 1. 条件变量及其初衷 2. 条件变量的使用:以pthread库为例 3. c++11中条件变量的使用 条件变量及其初衷 条件变量(condition variable)是多线程编程同步问题中的一个典型设计,和信号量类似,是建立在底层锁结构之上的一种同步机制。通常来讲,条件变量和信号量可以用来实现相类似的功能,比如解决生产者消费者问题,某种意义上可以说,条件变量是简陋版的信号量。条件变量的设计初衷从这个名字本身就可以很明显地体现出来。在多线程环境中,我们经常会遇到这样的场景:某个线程需要等某个条件成立时才能继续进行,而这个条件的成立过程由其它线程来完成。典型的例子是父线程在创造子线程之后,希望等到“子线程运行结束”这个条件结束,再继续执行之后的代码。问题的代码描述如下: void *child(void *arg) { printf("child\n"); // XXX how to […]