假设你有一个鸡、犀牛和山羊的动物园。如果有12个头,38只脚和10只角,每种动物有多少只?
x + y + z = 12
2*x + 4*y + 4*z = 38
0*x + 1*y + 2*z = 10
解决这个问题的一个方法是将每个属性的方程式转化为矩阵。
import matplotlib.pyplot as plt
import numpy as np
from mpl_toolkits.mplot3d import Axes3D
import scipy as sp
import scipy.linalg
import sympy as sy
sy.init_printing()
np.set_printoptions(precision=3)
np.set_printoptions(suppress=True)
x = np.linspace(-5, 5, 100)
y1 = -x + 14
y2 = -0.5*x + 19*0.5
fig, ax = plt.subplots(figsize = (12, 7))
ax.scatter(9, 5, s = 200, zorder=5, color = 'r', alpha = .8)
ax.plot(x, y1, lw =3, label = '$x+y=14$')
ax.plot(x, y2, lw =3, label = '$2x+4y=38$')
ax.plot([1, 1], [0, 5], ls = '--', color = 'b', alpha = .5)
ax.plot([-5, 1], [5, 5], ls = '--', color = 'b', alpha = .5)
ax.set_xlim([-5, 5])
ax.set_ylim([0, 12])
ax.legend()
s = '$(1,5)$'
ax.text(9, 5.5, s, fontsize = 20)
ax.set_title('Solution of $x+y=14$, $2x+4y=38$', size = 22)
ax.grid()
x,y交点为解(9,5)
x, y = [-1, 0, 1], [-1, 0, 1]
X, Y = np.meshgrid(x, y)
fig, ax = plt.subplots(figsize = (12, 7))
ax.scatter(X, Y, s = 200, color = 'red')
ax.axis([-2, 3.01, -2.01, 2])
ax.spines['left'].set_position('zero') # alternative position is 'center'
ax.spines['right'].set_color('none')
ax.spines['bottom'].set_position('zero')
ax.spines['top'].set_color('none')
ax.grid()
plt.show()
import numpy as np
import matplotlib as plt
import matplotlib.pyplot as plt
'''
x + y + z = 12
2*x + 4*y + 4*z = 38
0*x + 1*y + 2*z = 10
'''
x1 = np.linspace(0, 35, 20)
x2 = np.linspace(0, 20, 20)
X1, X2 = np.meshgrid(x1, x2)
fig = plt.figure(figsize = (9, 9))
ax = fig.add_subplot(111, projection = '3d')
X3 = 12 - X2 - X1
ax.plot_surface(X1, X2, X3, cmap ='winter', alpha = 1)
X3 = 19*0.5 - X2 - 0.5*X1
ax.plot_surface(X1, X2, X3, cmap ='summer', alpha = 1)
X3 = 5 - 0.5*X2
ax.plot_surface(X1, X2, X3, cmap ='spring', alpha = 1)
#numpy 求解交点
A = np.array([[1,1,1],[2,4,4],[0,1,2]])
B = np.array([12,38,10])
dot = np.linalg.solve(A,B)
x,y,z = [int(i) for i in dot]
print(x,y,z)
#ax.scatter(29, 16, 3, s = 200, color = 'black')
ax.scatter(x, 0, 0, s = 200, color = 'black')
ax.scatter(0, y, 0, s = 200, color = 'black')
ax.scatter(0, 0, z, s = 200, color = 'black')
plt.show()
推荐线性代数github代码
https://github.com/MacroAnalyst/Linear_Algebra_With_Python
以Python为特色的线性代数的讲义。这一系列的讲义将引导你了解所有最必须知道的概念,为数据科学或高级量化技能组合奠定基础。适用于统计学家/计量学家、定量分析员、数据科学家等,在Python计算和可视化的帮助下,快速复习线性代数。
推荐3blue1Brown线性代数的本质
线性代数的本质 - 01 - 向量究竟是什么?_哔哩哔哩_bilibili
https://www.bilibili.com/video/BV1Ys411k7yQ
算法优化提速篇(慎入)
商业学校的数学学生很可能熟悉老师告诫他们不要随便猜测问题的答案。但一个新的证明表明,事实上,正确的猜测有时是解决线性方程组的最好方法,这是数学中的基础计算之一。
因此,该证明建立了第一个能够超越以前对这些类型问题的解决速度的硬性限制的方法。
'滑铁卢大学的Mark Giesbrecht说:'这是计算中最基本的问题之一。'现在我们有一个证明,我们可以走得更快。'
乔治亚理工学院的Richard Peng和Santosh Vempala的新方法于7月在网上发布,并在1月的ACM-SIAM离散算法年度研讨会上进行了展示,它在会上获得了最佳论文奖。
线性系统涉及两个或多个带有变量的方程,这些变量规定了事物之间的不同关系。它们是 '线性 '的,因为唯一允许的功率正好是1,而且方程的解的图形形成平面。
一个常见的线性系统的例子--也可能是数学学生所熟悉的--涉及一个鸡和兔同在的笼子。如果你只知道有10个头和30个脚,那么有多少只鸡,有多少只兔子?正如代数学生所学,有一个固定的程序来计算它。写下两个代数方程,然后一起解决。
但线性系统的作用不仅仅是计算鸡和兔子。它们出现在许多实际环境中,在那里建造一座更坚固的桥梁或一架更隐蔽的飞机可能涉及解决有数百万个相互依赖的线性方程的系统。
更根本的是,线性系统在计算机科学的许多基本优化问题中占有重要地位,这些问题涉及在一个约束系统中为一组变量寻找最佳值。如果我们能够更快地解决线性系统,那么我们也可以更快地解决这些问题。
'文帕拉说:'线性系统是现代计算的主力军。
新的证明找到了一种更快解决一大类线性系统的方法,避开了这个过程中通常使用的主要技术之一。这种技术被称为矩阵乘法,以前对线性系统的求解速度设置了严格的速度限制。
它仍然是这项工作的特色,但却是一个补充性的角色。作者将其与一种新的方法结合起来,从本质上讲,这是一种训练有素的占卜。
'你可以猜测你的解决方案,'彭说。而且没有老师会因此对你生气。
为了感受线性系统以及你如何解决它们,请回到畜牧场,但想象它现在更像是一个动物园:鸡、单角犀牛和双角山羊。你快速数一下,确定有12个头,38只脚和10只角。你能算出每种动物有多少只吗?
要继续下去,给每种动物分配一个变量(鸡为c,犀牛为r,山羊为g),并为每种属性写一个方程式。每个变量前面的数字,或系数,反映了每种动物拥有的该属性的数量。
C + R + G = 12头
2c + 4r + 4g = 38英尺
0C + 1R + 2G = 10个角
现在你有三个方程和三个未知数。
解决这些问题的方法之一是操作一个方程,用其他两个方程定义一个变量。例如,0c + 1r + 2g = 10 变成r = 10 - 2g。
在其他两个方程中用这个值代替r,然后继续这样做,直到你只用一个变量来定义所有的变量,然后你就可以准确地解决这个问题。然后你可以重复这个过程,利用你已经解决的一个变量来解决下一个变量。
但另一种更复杂的方法是创建一个矩阵,其条目是方程的系数。这三个方程变成了这个矩阵。
接下来,我们用另一个矩阵表示鸡、犀牛和山羊的未知数量。
最后,我们用第三个矩阵表示观察到的头、脚和角的数量。
我们可以把这三个矩阵合并成一个线性系统,第一个矩阵乘以第二个矩阵的未知值等于第三个矩阵--这时我们可以用线性代数来解决第二个矩阵的问题。
无论你是操作方程还是走矩阵路线,你最终都会执行相同的计算步骤来解决问题。这个数字是系统中变量数量的立方(n3)
在这种情况下,我们有三个变量,所以需要33个,或27个计算步骤。如果我们有四个动物和四个方程,则需要43或64步来解决它们。
在过去的50年里,研究人员已经找到了更有效地执行这一程序的方法。通常有一些他们可以采用的捷径--重复使用或组合操作的方法--让他们以更少的步骤解决线性系统。
桑托什-文帕拉(Santosh Vempala)与理查德-彭(Richard Peng)一起想出了一种解决某些线性方程的新的、更快的方法,文帕拉认为这是 '现代计算的主力'。
佐治亚理工学院计算机学院提供
1969年,沃尔克-斯特林设计了一种仅用n2.81步进行矩阵乘法的算法。从那时起,数学家和计算机科学家们一直在争夺进一步降低指数的机会。
去年10月,麻省理工学院的弗吉尼亚-瓦西列夫斯卡-威廉姆斯和哈佛大学的博士后研究员乔希-阿尔曼取得了最新进展,证明有可能以n2.37286步进行矩阵乘法,比之前的最佳指数提高了0.00001。
所有这些的结果是,你想要解决的任何线性系统都可以被简化为一个关于矩阵乘法的问题,而截至目前,矩阵乘法至少在理论上可以在n2.37286步内进行。
但各种技术特征表明,应该可以比这更快地解决线性系统--可能是n2步。我们使用矩阵乘法是因为它一直是最好的可用工具,但这并不意味着没有更好的工具等待我们去发现。
'文帕拉说:'解决线性系统的这个问题没有理由依赖于矩阵乘法的改进。
猜测解决方案
为了理解这个新的和改进的工具,你需要记住另一个既定的解决线性系统的方法。这是一个直观的方法,当你第一次面对一群鸡、一群犀牛和一群山羊混在一起时,你可能会想到这个方法。猜测每个数字,把它们插入方程,看看你有多大的偏差,然后再猜。
这种 '迭代法 '是工程师和科学家经常采用的方法。它对许多实际问题都很有效,因为专家们通常不会盲目猜测,这就减少了他们在找到解决方案之前需要进行的反复猜测的次数。
'对于现实世界的科学计算问题,人类对答案应该是什么有非常好的直觉,'彭说。
迭代方法在直觉可以提供一些支持的特定情况下是有用的。当你试图解决的线性系统有大量系数为零的变量时,它们也会更普遍地发挥作用。
这个特点在畜牧场的例子中是存在的,而且很有帮助,因为在这个例子中,最容易解决的属性是角。为什么?因为鸡没有角,这就使鸡的项归零,把涉及三种动物的问题减少到真正涉及两种动物的问题。一旦你解决了角的问题,你就可以利用这些信息来快速解决脚和头的问题。
在更复杂的线性系统中,这种类型的关系,即并非所有属性都与所有变量有关,可能是普遍存在的。你可能有数以百万计的变量和数以百万计的方程,但每个方程可能只涉及整体变量的一小部分。
这些类型的线性系统被称为 '稀疏',反映了大多数变量在大多数方程中取值为零的方式。这是一种在现实世界的线性系统中经常出现的情况。在这种情况下,迭代方法可以战胜矩阵乘法。
Peng和Vempala解决线性方程的新方法包括进行随机但协调的猜测,并从那里找到解决方案。
特伦斯-拉辛威廉姆斯说:'只有当你的矩阵足够稀疏时,它才能发挥作用。
但在这项新工作之前,没有人能够证明,对于所有稀疏的线性系统,迭代方法总是比矩阵乘法快。
协调的随机性
Peng和Vempala的新技术采用了一个增强版的迭代猜测策略。他们的算法不是只做一个猜测,而是并行地做许多猜测。这种方法加快了搜索速度,就像如果你有很多人同时看,你会更快地找到森林中的宝石。
'Giesbrecht说:'平行性是奇迹发生的地方。
一次调集多个猜测似乎是显而易见的,但让这个策略发挥作用并不那么简单。新算法的有效性在很大程度上取决于如何聪明地做出初始猜测,作为迭代过程的种子,并找到巧妙的方法将平行猜测的结果结合到一个单一的最终答案。
回到农场的例子,该算法可能会做出三个初始猜测,每个猜测是一个3乘1的矩阵,指定鸡、犀牛和山羊的数量。该算法将观察每个猜测的偏差程度,然后进行更多的猜测。
再回到稗田的例子,该算法可能会进行三次初始猜测,每次猜测都是一个3乘1的矩阵,规定了鸡、犀牛和山羊的数量。该算法将观察每个猜测的偏差程度,然后进行更多的猜测,继续平行猜测线程。
该算法最终成功的一个关键是,它的三个初始猜测是随机进行的。随机性似乎不是猜测的良好基础,但作为一种通用的方法,它有其优势,特别是当你在处理巨大的问题时。也就是说,随机性可以确保你不会意外地将你的搜索偏向问题的某一部分,而可能忽略了实际解决方案所在的空间。
'我需要确保我所有的猜测都有足够的随机性,以便它们涵盖所有可能的组合,'彭说。'正是这种非常可怕的猜测方式,随着问题变得非常大,最终成为首选方法。'
Peng和Vempala的论文中大部分困难的技术工作涉及证明不同的随机猜测股也一起工作,包括任何特定的猜测事实上是问题的答案。
'有协调的随机性,'Vempala说。
这意味着随机猜测不仅说明了猜测本身的确切数值,而且还涵盖了位于它们之间的所有潜在猜测。这在精神上类似于两个人在森林中搜索时不只是搜索他们走过的地面;他们还覆盖他们之间的全部视线。
'两个[猜测]之间的任何东西也被覆盖,'文帕拉说。
这种搜索功能确保算法会在某个地方遇到解决方案。但它本身并不能确定解决方案到底是什么。要做到这一点--真正把他们的手放在解决方案上--彭和文帕拉必须证明其他东西。
该算法将其随机猜测作为一个矩阵中的条目进行跟踪。在矩阵中的条目中寻找解决方案就成了一个矩阵乘法的问题,这当然是他们要绕过的障碍。但在这里,他们又一次利用了他们用来给矩阵中的条目的随机性。
因为矩阵中的条目是随机的,而且它们之间发生协调,矩阵本身最终具有某些对称性。这些对称性促成了计算上的捷径。就像任何高度对称的物体一样,你只需要知道它的一部分是什么样子,就可以推断出整体。
因此,Peng和Vempala的算法可以在矩阵中找到解决方案,比它在一个具有相同数目的条目但没有有用的对称性的矩阵中找到解决方案要快。矩阵的对称性也带来了另一个重要的好处。它们有助于确保猜测永远不会大到从算法效率的角度看变得难以应付。
'我们不得不在做这种猜测和协调时控制一个数字显示的大小,'彭说。
Peng和Vempala证明,他们的算法可以在n2.332步内解决任何稀疏线性系统。这比矩阵乘法的最佳算法的指数(n2.37286)要高出约百分之四。
淘汰矩阵乘法不会很快对实际应用产生影响,但作为一个概念证明,这种轻微的改进是一个鸿沟。它表明有一种完全更好的方法来解决线性系统。
文帕拉说:'从哲学上讲,我们以前不知道你是否能比矩阵乘法更快,'
现在我们知道了。
联系客服