精华内容
下载资源
问答
  • 三角不等式

    万次阅读 2016-09-28 18:41:54
    对于任何实数 a,ba,b 的所谓的著名三角不等式:|a+b|≤|a|+|b|

    1. 基本形式

    对于任何实数 a,ba,ba,b 的所谓的著名三角不等式:

    ∣a+b∣≤∣a∣+∣b∣ |a+b|\leq |a| + |b| a+ba+b

    其对应的等价形式为:

    ∣α−β∣≤∣α−γ∣+∣γ−β∣ |\alpha-\beta|\leq |\alpha-\gamma|+|\gamma-\beta| αβαγ+γβ

    简单证明,令 a=α−γ,b=γ−βa=\alpha-\gamma, b=\gamma-\betaa=αγ,b=γβ,得证。等价形式对应的实际几何意义在于,从 α\alphaαγ\gammaγ 的直达距离,小于或等于经过第三点(转折) γ\gammaγ 的两短距离之和。当然,这一不等式还可对应于这样的基本事实,在任何三角形,两边之和大于第三边。

    2. 拓展

    两数之间的关系,自然可以推广到 3 个数,乃至无限多个数之间的关系。

    ∣a1+a2+⋯+an∣≤∣a1∣+∣a2∣+⋯+∣an∣ |a_1+a_2+\cdots+a_n|\leq |a_1|+|a_2|+\cdots+|a_n| a1+a2++ana1+a2++an

    可通过数学归纳法进行证明,∣a1+a2+⋯+an−1∣≤∣a1∣+⋯+∣an−1∣|a_1+a_2+\cdots+a_{n-1}| \leq |a_1|+\cdots+|a_{n-1}|a1+a2++an1a1++an1,因此,∣as+an∣≤∣as∣+∣an∣|a_s+a_n|\leq |a_s|+|a_n|as+anas+an(令 as=a1+⋯+an−1a_s=a_1+\cdots+a_{n-1}as=a1++an1

    ∣a∣=∣(a+b)−b∣≤∣a+b∣+∣−b∣=∣a+b∣+∣b∣ |a|=|(a+b)-b|\leq |a+b|+|-b|=|a+b|+|b| a=(a+b)ba+b+b=a+b+b

    因此:

    ∣a∣−∣b∣≤∣a+b∣≤∣a∣+∣b∣ |a|-|b|\leq |a+b|\leq |a|+|b| aba+ba+b

    根据对称性,显然 a⇔ba\Leftrightarrow bab,得:

    ∣b∣−∣a∣≤∣a+b∣≤∣a∣+∣b∣ |b|-|a|\leq |a+b|\leq |a|+|b| baa+ba+b

    3.

    展开全文
  • matlab开发-带函数的三角不等式。直观探索三角形不等式
  • 完美版满足三角不等式的TSP问题的近似算法,内部含有课程设计报告和源程序,适合大学数据与算法分析课程学习。 满足三角不等式的TSP问题的近似算法: (1)描述及输入原始数据模块 (2)求解最小生成树模块 (3)构造...
  • 加入三角不等式的闭合的改进算法,石康壮,陈戟,本文介绍的是加入三角不等式的闭合的K-means改进算法,它显著提高了传统k-means算法的计算效率。改进方法主要考虑到传统的K-means重分配
  • 完美版满足三角不等式的TSP问题的近似算法,内部含有课程设计报告和源程序,适合大学数据与算法分析课程学习。 满足三角不等式的TSP问题的近似算法: (1)描述及输入原始数据模块 (2)求解最小生成树模块 (3)构造...
  • 利用Cauchy柯西不等式证明三角不等式欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定...

    利用Cauchy柯西不等式证明三角不等式


    编者注:作为一个学生,希望所有人都能够免费共享成果,一起进步,为祖国一起做贡献。
    第一次写博客,先适应一下。
    已知柯西不等式|(x,y)|<=||x||·||y||,证明三角不等式||x+y||<=||x||+||y||

    欢迎交流,邮箱279644543@qq.com或者sy950812@buaa.edu.cn

    展开全文
  • 运用三角不等式加速Kmeans聚类算法 引言:最近在刷《数据挖掘导论》,第九章, 9.5.1小节有提到,可以用三角不等式,减少不必要的距离计算,从而达到加速聚类算法的目的。这在超大数据量的情况下,尤为重要。但是书...

    运用三角不等式加速Kmeans聚类算法


    引言:最近在刷《数据挖掘导论》,第九章, 9.5.1小节有提到,可以用三角不等式,减少不必要的距离计算,从而达到加速聚类算法的目的。这在超大数据量的情况下,尤为重要。但是书中并没有给出解释和证明。本文以k-means聚类算法为代表,讲解下怎么利用三角不等式减少计算过程。


    1. 三角不等式

    任一三角形,两边之和大于第三边,两边之差小于第三边。可以从欧式距离扩展到多维欧几里得空间:设任意三个向量a,b,c。d(x,y)代表x,y在空间上的距离,则三角不等式满足:
    \[d(a,b)+d(b,c)\ge d(a,c) , d(a,b) - d(b,c) \le d(a,c)\]

    2.K-means算法

    K-mean算法

    1. 随机选择K个数据点作为初始质心
    2. repeat
    3.   计算每一个数据点计算到现有K个质心的距离,将它归属到距离最近质心的所在簇中
    4.   重新计算质心。
    5. until 所有质心不再变动

    3. 定义

    \[假设存在数据点集 X=\{x_1, x_2,..,x_n\} , 质心的集合C=\{ C_1,C_2,...,C_m\}, 对应的簇集合为S=\{ S_1,S_2,...,S_m\}。\]

    4.三角不等式推出的引理

    引理1:
    \[设 C_i ,C_j(i\neq j )\in C, x \in X。如果2 d(x,C_i) \le d(C_i,C_j) ,那么d(C_i,x) \le d(C_j,x) 。 \]

    =

    引理2:
    \[ 设C_i \in C, \exists C_j \in C,使得d(C_i,C_j) = min \ d(C_i,C)。对于数据点x \in X,若有2 d(x,C_i) \le d(C_i,C_j),\ 那么min \ d(x,C) = d(C_i,x)。(记d(x,C)是x到所有质心的距离)\]

    证明引理1:

    因为有 \[2 d(C_i,x) \le d(C_i,C_j) \ (1)\]
    且由三角不等式:\[ d(C_i,C_j) \le d(x,C_i) + d(x,C_j) \ (2)\]
    所以 \[2 d(C_i,x) \le d(x,C_i) + d(x,C_j),即d(C_i,x) \le d(C_j,x)\]

    证明引理2:

    运用反证法:
    假设 \[ \exists C_k \in C,使得d(C_k,x) < d(C_i,x), \]
    由题干有:
    \[ d(C_k,C_i) \ge d(C_i,C_j) (1) , d(x,C_i) \le d(C_i,C_j) (2)\]
    又因为 \[ d(C_k,x) +d (C_i,x) \ge d(C_k,C_i) (3)\]
    所以结合(1)(3):
    \[ d(C_k,x) +d (C_i,x) \ge d(C_i,C_j) (4)\]
    又由假设:
    \[ 2d(C_i,x) > d(C_i,C_j) (5)\]
    这与条件中\[2 d(x,C_i) \le d(C_i,C_j)\]相矛盾,所以可知假设不成立。
    \[min \ d(x,C) = d(C_i,x)\]

    5.运用引理1,引理2减少不必要的距离计算

    首先\[对于每一个C_i,用一个hash表存放与它最近的距离 d(C_i,C_j)。\]

    1.如果数据点x已经被分配:

    \[ 则x与它目前所在簇的质心的距离为d(C_i,x),与d(C_i,C_j)比较。\]
    \[如果 2 d(C_i,x) \le d(C_i,C_j),则说明不需要更换x的归属。\\(注意反之: 2 d(C_i,x) \gt d(C_i,C_j)),并不能说明x应该数据 C_j所在的簇,所以还需要继续计算x与每个质心的距离。)\]

    2.如果数据点x还未被分配

    \[ 则需要遍历计算, \forall C_i \in C, 比较 2 d(C_i ,x) \le d(C_i,C_j)是否成立,若成立,说明x应当归属 C_i ,无需再计算其他距离。\]

    6. 改进的K-means算法

    前文介绍了如何运用引理1,2 将它运用在K-means算法上,改写的k-means算法如下:

    K-mean算法

    1. 随机选择K个数据点作为初始质心
    2. repeat
    3.  计算k个质心间的距离,并且用hash表保存每个质心的到其他质心的最短距离。(用d(Ci,Cj)表示质心Ci和它最近质心是Cj的距离)。
      4.  repeat
          对于每个数据点x
          if(数据点x已分配在质心Ci所在簇)
           if 2d(Ci,x) <=d(Ci,Cj)
            x分配无需变动;
           else
            继续计算x到现有K个质心的距离,将它归属到距离最近质心的所在簇中
            end if
          else(数据点x未分配到任何簇)
           for i from 0 to K do
            if 2d(Ci,x) <=d(Ci,Cj)
             将x归属到Ci所在簇中
             退出for循环
            end if
            end for
          end if
    4.   重新计算质心。
    5. until 所有质心不再变动

    引申

    本文中只举例了使用欧几里得距离的K-means算法。其实本文中的d(x,y)不仅可以指代distance,更广义的可以指代dissimilarity。任何通过度量相异性的聚类算法都可以使用三角不等式,避免多余的计算,例如计算最近邻的DBSCAN。感兴趣的读者可以自己推导改进。

    转载于:https://www.cnblogs.com/bradleon/p/6842549.html

    展开全文
  • 从线性代数理解余弦定理,三角不等式,A-G不等式和柯西-许瓦兹不等式 向量的两种运算 scalar multiplication and addition,分别为数乘和加法。两种运算一起有个好听的名字叫linear combination,也就是线性组合。...

    从线性代数理解余弦定理,三角不等式,A-G不等式和柯西-许瓦兹不等式

    向量的两种运算

    scalar multiplication and addition,分别为数乘和加法。两种运算一起有个好听的名字叫linear combination,也就是线性组合。线性组合是线代的基石之一。比如v和w的线性组合表示为,其中a,b为常数
    av+bw\begin{aligned} a\overrightarrow v + b\overrightarrow w \end{aligned}

    向量的三种表示方法

    1. []的形式,如下面这种

      [123]\begin{aligned}\left[ \begin{array}{l} 1\\ 2\\ 3 \end{array} \right]\end{aligned}

    2. arrow from 0\begin{aligned}\overrightarrow {\rm{0}} \end{aligned}

    3. point in the vector space ,如下图:
      在这里插入图片描述

    向量的内积与向量的长度

    内积:两个向量的内积定义为:vTw{v^T}w

    v=[123]\begin{aligned} v = \left[ \begin{array}{l} 1\\ 2\\ 3 \end{array} \right] \end{aligned}w=[456]\begin{aligned}w = \left[ \begin{array}{l} 4\\ 5\\ 6 \end{array} \right]\end{aligned}vTw=1×4+2×5+3×6=32\begin{aligned}{v^{\rm{T}}}w = 1 \times 4 + 2 \times {\rm{5 + 3}} \times {\rm{6 = 32}}\end{aligned}

    向量的长度为v||v||,且有v2=vTv\begin{aligned} ||v|{|^2} = {v^T}v \end{aligned},以上面为例,v2=12+22+33=14\begin{aligned}||v|{|^2} = {1^2} + {2^2} + {3^3} = 14\end{aligned},其长度为14\begin{aligned}\sqrt {14} \end{aligned}

    单位向量:unit vector,u=vv\begin{aligned}u{\rm{ = }}\frac{v}{{||v||}}\end{aligned},与v同方向的单位向量为u=114[123]\begin{aligned}u = \frac{1}{{\sqrt {14} }}\left[ \begin{array}{l} 1\\ 2\\ 3 \end{array} \right]\end{aligned}

    向量的夹角:uTU=cosθ\begin{aligned}{u^T}U = \cos \theta \end{aligned},U也为单位向量。cosθ=vTwvw\begin{aligned}\cos \theta = \frac{{{v^{\rm{T}}}w}}{{||v||||w||}}\end{aligned}

    柯西-许瓦兹不等式

    根据向量的夹角公式,由于1cosθ1\begin{aligned} - 1 \le \cos \theta \le 1 \end{aligned},推出许瓦兹不等式如下:
    vTwv.w\begin{aligned} |{v^T}w| \le ||v||.||w||\end{aligned}
    其代数表达形式为,下面的v和w为n维向量
    (i=1nviwi)2i=1nvi2i=1nwi2\begin{aligned} {\left( {\sum\limits_{i = 1}^n {{v_i}{w_i}} } \right)^2} \le \sum\limits_{i = 1}^n {{v_i}^2} \sum\limits_{i = 1}^n {{w_i}^2} \end{aligned}

    A-G不等式(arithmetic-geometry inequality)

    二维:令v=[ab],w=[ba]\begin{aligned}v{\rm{ = }}\left[ \begin{array}{l} a\\ b \end{array} \right],w = \left[ \begin{array}{l} b\\ a \end{array} \right]\end{aligned},根据许瓦兹不等式可得
    2aba2+b2aba+b2\begin{aligned} \begin{array}{l} 2ab \le {a^2} + {b^2}\\\displaystyle \sqrt {ab} \le \frac{{a + b}}{2} \end{array}\end{aligned}
    n维的待证

    三角不等式(triangle inequality)

    a+ba+b \begin{aligned}||a + b|| \le ||a|| + ||b||\end{aligned}

    证明如下
    a+b2=a2+2aTb+b2 \begin{aligned}||a + b|{|^2} = ||a|{|^2} + 2{a^T}b + ||b|{|^2}\end{aligned}
    根据许瓦兹不等式易知a2+2aTb+b2(a+b)2\begin{aligned}||a|{|^2} + 2{a^T}b + ||b|{|^2} \le {\left( {||a|| + ||b||} \right)^2}\end{aligned},所以a+b2(a+b)2\begin{aligned}||a + b|{|^2} \le {\left( {||a|| + ||b||} \right)^2}\end{aligned},得证。如果a,b为标量同样也成立
    在这里插入图片描述

    余弦定理

    vw2=v22vTw+w2=v22v.wcosθ+w2\begin{aligned} ||v - w|{|^2} = &||v|{|^2} - 2{v^T}w + ||w|{|^2}\\\displaystyle =& ||v|{|^2} - 2||v||.||w||\cos \theta + ||w|{|^2} \end{aligned}

    平行四边形对角线与边长的关系

    从图中可以看到
    vw2+v+w2=2v2+2w2\begin{aligned} ||v - w|{|^2} + ||v + w|{|^2} = 2||v|{|^2} + 2||w|{|^2}\end{aligned}
    从向量的角度很直观地知道了平行四边形对角线与边长的关系。

    展开全文
  • Schwarz不等式 三角不等式

    千次阅读 2017-11-01 14:34:44
    3. 三角不等式 | x − z | ≤ | x − y | + | y − z | | x − z | ≤ | x − y | + | y − z | |\mathbf{x} - \mathbf{z}| \le |\mathbf{x} - \mathbf{y}| + |\mathbf{y} - \mathbf{z}| 三角不等式 ∀ x ...
  • 椭圆范数的三角不等式证明
  • 廓清认知:由于三角不等式属于超越不等式,故已经不能和解\(x^2+3x+2>0\)这样的代数不等式的解法同日而语,此时必须借助图像来解决;能借助的图像有三角函数的图像,还可以借助三角函数线来解决,以下用例题加以...
  • 本节介绍欧几里得结构的两个基本不等式 1 柯西-施瓦茨(Cauchy–Schwarz)不等式 对任意向量x,y有: 证明: 观察实变量t的函数: ...2 三角不等式 对任意向量x,y有: 该定理的证明参照上一节
  • 一个三角不等式

    2017-01-04 23:47:00
    有趣的不等式: 命题 1: 设$0<\alpha<1,x>0,y>0$,那么 $$(x+y)^{\alpha}\leq x^{\alpha}+y^{\alpha}$$ 证明:设 $$F(x)=x^{\alpha}+y^{\alpha}-(x+y)^{\alpha}$$ 那么 $$F'(x)=\alpha [x^{\alpha-1...
  • 柯西不等式是欧式几何中最基本,也是最重要的不等式。它的重要之处,不仅在于该结论本身应用之广泛;也在于它的证明思想对于其他定理的证明,有极大的借鉴意义。例如,在以后介绍的凸集的支撑超平面定理中,就会用到...
  • 根据三角形不等式,前者显然小于等于后者 所以直接从1到n就是最短路了 #include #define mp make_pair #define fir first #define se second #define ll long long #define pb push_back using namespace ...
  • 我们从这一观察出发,抽象出度量距离及度量距离空间的概念,并将函数极限,连续的概念推广 到度量空间上.  定义 设X为一非空集合,: X...(3)(三角不等式).     则称是两点x,y之间的距离,
  • 定理 对于所有x,y∈Rn,∥x+y∥≤∥x∥+∥y∥x, y \in \Bbb R^n, \|x+y\| \leq \|x\|+\|y\|x,y∈Rn,∥x+y∥≤∥x∥+∥y∥,其中对于x∈Rnx \in \Bbb R^nx∈Rn, ∥x∥2=∑i=1nxi2\|x\|_2 = \sqrt...柯西不等式: (∑k=...
  • 一键关注
  • Cauchy-Schwartz不等式推论 度量矩阵 只要告诉一组基下任意两个向量的内积,就会形成一个度量矩阵。那么随便拿一个向量,都知道它的坐标,这两个向量的内积就是右边的xTGyx^TGyxTGy。如果GGG为单位矩阵,那么<...
  • 前两天我们分别提到了在三角极限求解时的化简。槿灵兮:第一天(20,11,08):一个三角极限的处理槿灵兮:第二天(20,11,09):另一个三角极限的处理对于这两篇文章,剑君给了一个补充例题:这个我只想说:证明留作...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 802
精华内容 320
关键字:

三角不等式