关于2-范数三角不等式的证明

数值计算课上的作业,回去想了一些,偶然看到豆瓣上11年有同学也问了,看了评论有了思路,可以用柯西不等式。
sqrt((x1+y1)^2 + ...+(xn+yn)^2)
=sqrt(x1^2 +...+xn^2+y1^2+...+yn^2+2*x1*y1+...+2*xn*yn)
<=sqrt(x1^2+...+xn^2+y1^2+...+yn^2+?2*sqrt(x1^2+...+xn^2)*sqrt(y1^2+...+yn^2))
=sqrt(x1^2+...xn^2)+sqrt(y1^2+...+yn^2)
证毕
关于课上说的关于p范数一般形式还在思考,老师说可以参考泛函分析,对于非数学专业伤不起啊,不过还是去看下吧。?

时间: 04-14

关于2-范数三角不等式的证明的相关文章

关于Floyd-Warshall算法由前趋矩阵计算出的最短路径反映出了算法的执行过程特性的证明

引言:Floyd-Warshall算法作为经典的动态规划算法,能够在O(n3)复杂度之内计算出所有点对之间的最短路径,且由于其常数较小,对于中等规模数据运行效率依然可观.算法共使用n此迭代,n为顶点个数.其中第k次迭代计算出每对顶点之间所有中间结点小于等于k的最短路径长度,其中i到j的最短路径要么是经过k的一条路径,这条路径的由k所分割出的两个路径i → k.k → j是中间路径小于等于k-1的最短路径:要么是从i到j的中间路径小于等于k-1的最短路径.定义dij(k)为从i到j的最短路径长度,

什么是矩阵的范数【转载】

在介绍主题之前,先来谈一个非常重要的数学思维方法:几何方法.在大学之前,我们学习过一次函数.二次函数.三角函数.指数函数.对数函数等,方程则是求函数的零点:到了大学,我们学微积分.复变函数.实变函数.泛函等.我们一直都在学习和研究各种函数及其性质,函数是数学一条重要线索,另一条重要线索--几何,在函数的研究中发挥着不可替代的作用,几何是函数形象表达,函数是几何抽象描述,几何研究"形",函数研究"数",它们交织在一起推动数学向更深更抽象的方向发展. 函数图象联系了函数

积分判别法的副产品——跟求和有关的不等式

(图片来自 Wikipedia) 观察这张图: 第一个矩形的面积是 1, 第二个是 1/2, 第三个是 1/3, ……第 k 个是 1/k; 这 k 个矩形的面积之和,显然大于它们下面的积分 \(\int_{1}^{k+1} \frac{1}{x}\mathrm{d}x\) 如果拿掉第一个矩形,把剩下的矩形都翻到左边来,这 k - 1 个矩形的面积之和,显然小于它们上面的积分 \(\int_{1}^{k} \frac{1}{x}\mathrm{d}x\) 由此可得: \(ln(k+1) < 1+

算法导论——lec 13 贪心算法与图上算法

之前我们介绍了用动态规划的方法来解决一些最优化的问题.但对于有些最优化问题来说,用动态规划就是"高射炮打蚊子",采用一些更加简单有效的方法就可以解决.贪心算法就是其中之一.贪心算法是使所做的选择看起来是当前最佳的,期望通过所做的局部最优选择来产生一个全局最优解. 一. 活动选择问题 [问题]对几个互相竞争的活动进行调度:活动集合S = {a1, a2, ..., an},它们都要求以独占的方式使用某一公共资源(如教室),每个活动ai有一个开始时间si和结束时间fi ,且0 ≤ si &

Clustering by fast search and find of desity peaks(基于快速搜索与寻找密度峰值的聚类)

基于快速搜索与寻找密度峰值的聚类(Alex Rodriguez and Alessandro Laio) 摘要:聚类分析目的是基于元素之间的相似度对其进行分类,应用范围从天文学到生物信息学.文献计量学到模式识别.我们提出一种方法,思想基于簇中心具有比其邻居更大密度的特点以及与更大密度点之间有一个相对较大的距离(1.簇中心点有相对高的密度 2.簇中心点之间距离一般较大,即不同类别之间一般距离较远),这种思想形成了簇数目直观出现的聚类机制的基础,自动发现和排除异常点,同时在识别簇时,不用关心其形状和

UVa 515 - King (差分约束系统 + SPFA求带负权最短路)

下面是差分约束系统的详细介绍,以及解决方法~ 摘抄自 xuezhongfenfei(他好像也是转的....) 差分约束系统 X1 - X2 <= 0 X1 - X5 <= -1 X2 - X5 <= 1 X3 - X1 <= 5 X4 - X1 <= 4 X4 - X3 <= -1 X5 - X3 <= -3 X5 - X4 <= -3 不等式组(1) 全都是两个未知数的差小于等于某个常数(大于等于也可以,因为左右乘以-1就可以化成小于等于).这样的不等式组

图像检索之EMD距离(Earth Mover&#39;s Distance)

在理解EMD距离模型时,需要先对<运筹学>中运输问题,做一下了解.下面给出几个运输问题的小例子,作为补充知识: 那么,对于上述问题我们发现是一个 产量=销量=500 ,即产销平衡的问题,可以提出这样的数学模型: 假设运到物品的个数为,用代表运到单个物品的运费(在上述表格中都有),用表示产地的产量,表示销地的销量,则总运费为,使总运费最小的数学模型为: 还有令两种可能就是 产量>销量 或者 产量<销量,这里不做模型的讨论,上面三种运输问题都可以用单纯形法进行求解.因为只有当"

最短路(floyd/dijkstra/bellmanford/spaf 模板)

floyd/dijkstra/bellmanford/spaf 模板: 1. floyd(不能处理负权环,时间复杂度为O(n^3), 空间复杂度为O(n^2)) floyd算法的本质是dp,用dp[k][i][j]表示以(1....k)为中间点,i, j之间的最短距离为多少,dp[0][i][j]即为原矩阵图. dp[k][i][j]可以由dp[k-1][i][j]转移得到,即不经过 k 点i, j之间的最短距离为多少, 也可以由dp[k-1][i][k]+dp[k-1][k][j]转移得到,即

从K近邻算法、距离度量谈到KD树、SIFT+BBF算法

从K近邻算法.距离度量谈到KD树.SIFT+BBF算法 从K近邻算法.距离度量谈到KD树.SIFT+BBF算法 前言 前两日,在微博上说:“到今天为止,我至少亏欠了3篇文章待写:1.KD树:2.神经网络:3.编程艺术第28章.你看到,blog内的文章与你于别处所见的任何都不同.于是,等啊等,等一台电脑,只好等待..”.得益于田,借了我一台电脑(借他电脑的时候,我连表示感谢,他说“能找到工作全靠你的博客,这点儿小忙还说,不地道”,有的时候,稍许感受到受人信任也是一种压力,愿我不辜负大家对我的信任)