Introduction我们在课堂上讨论了高斯积分和Clenshaw-Curtis积分方法。请阅读Lloyd Trefethen撰写的以下论文，‘Is Gauss Quadrature better than Clenshaw-Curtis?’, SIAM Review 50(1), 67–87, 2008。回答以下问题：（a）阅读本文的第1部分并总结（3-4行）该论文的主要贡献。（b）实现文中介绍的高斯积分和Clenshaw-Curtis积分的Octave程序（参见第2节）。 将它们命名为gauss.m和clenshaw_curtis.m。通过尝试命令gauss（@cos，1000）和clenshaw curtis（@ cos，1000）来验证它们是否正常工作。（c）第三部分提供了经验证据，证明Clenshaw-Curtis的收敛速度与高斯积分一致，使用六个函数。使用脚本conv_conv.m（参见Canvas的Octave页面）。绘制函数e^x和1/(1+16x^2 )在1-100之间的|I-In|1 介绍大多数数值分析教材都有一章节叫数值积分，其中大多数存在两个（n + 1）点正交规则族：首先基于等距点的Newton-Cotes公式，然后基于最优（从某种意义上）的点的高斯公式。一个关于任何积分公式的族的基本问题是，它是否收敛为n→∞，如果这样，速度有多快？长久以来，人们已经知道牛顿 - 科特斯公式不会为一般的被积函数而收敛。 它们只在f围绕积分区间的大区域进行分析时才会收敛，即使在没有舍入误差的情况下也是如此：问题是与Runge现象相关的O（2n）放大问题。相反，高斯积分公式对任何连续的f都收敛，并且没有舍入误差的问题。 此外，他们会出现有限n的效率为2倍的优势：而（n + 1）点Newton-Cotes公式恰好整合了n次多项式，即（n + 1）点高斯公式 积分2n + 1次多项式。高斯正交节点和权重需要一些工作来计算，但这可以通过解决三对角特征值问题在O（n2）运算中完成，如Golub和Welsch所示。然而，高斯积分不是牛顿 - 科特斯唯一的选择。 在这里，我们将它与Clenshaw-Curtis求积相比较，这是一组基于对采用快速傅立叶变换（FFT）的O（n log n）运算中可实现的积分切比雪夫点进行采样的公式。Clenshaw-Curtis公式在Johnson和Riess（1982），Ueberhuber（1997），Neumaier（2001）和Heath（2002）的数值分析教科书中被提及，并且在Gautschi（1997）和Cheney和Kincaid（1999））。它们也可以在数值积分专着中找到，包括Davis和Rabinowitz（1967,1975和1984），Brass（1977），Engels（1980），Evans（1993），Krommer和Ueberhuber（1998）以及Kythe和Sch？aferkotter（2005）。与Newton-Cotes正交相似，Clenshaw-Curtis求积积分n阶多项式。 像高斯积分一样，它对所有连续的f都收敛，并且没有舍入误差的问题。因此，从表面上看，我们似乎有一种方法与高斯一样稳健，可以在给定的n上实现，但“效率只有一半”。但这里有一个惊喜。 实际上，Clenshaw-Curtis的效率并不如高斯高一半。 事实上，对于大多数被积函数来说，这两个公式大致相同。这一观察结果于1968年由奥哈拉和史密斯[45]提出，并在随后的一两次出版物中报道，尤其是Evans [19]和Kythe和Sch？aferkotter [41]的着作。然而，它尚未广为人知，并且尚未进入数值分析教科书。 本文的目的是通过新的数值实验（第3节），新的定理（第4节和第5节，尤其是定理5.1）以及在复平面中包含有理逼近的新分析（第6节）来公布这个现象并理解它）。简而言之，我们的结论是，Clenshaw-Curtis和Gauss公式具有基本相同的精度，除非f在整合区间的相当大的邻域内解析 - 在这种情况下，两种方法收敛得如此之快以至于差别几乎不重要。 图4和5总结了这种行为的原因。我们在这篇文章中所关心的是积分公式的“纯”形式。 我们没有涉及的积分，外推，误差估计，非均匀权函数，稳定性和条件，复合公式，自适应性，端点和内部奇点，变量变化，无界域和多维等很多实际问题。（有关这些问题的信息，请参见[19]和[50]。）从通用集成软件的设计来看，我们距离这里很远！这种强调的一个原因是高斯和克伦肖 - 柯蒂斯公式非常基本，所以值得在细节上理解它们的基本性质。另一个是，即使在它们的纯粹形式中，积分公式在实践中也被用作其他数值计算的一部分。 例如，Gauss和Clenshaw-Curtis公式都用于ODE和PDE的数值解[7,55]。另一个让我参与这个主题的例子是面向对象MATLAB中的chebfun系统，它利用Clenshaw-Curtis积分的功能和速度来动态整合函数，这些函数可以由数百万 的数据点[4]。总而言之，看起来高斯和克伦肖 - 柯蒂斯公式应该被认为是同样有价值和基础的，前者在优雅中具有优势，后者更加简单。2 Gauss 和 Clenshaw–Curtis公式在这篇文章中我们关注的是所谓的插值型求积公式。给出[-1,1]上的连续函数f（移植到一般区间[a，b]是微不足道的），并寻求近似积分：对于各种n，其中节点{xk}依赖于n而不是f。 权重{wk}由属性唯一定义，其中In等于通过数据点的度数≤n多项式插值的积分。 因此，如果f是一个度数≤n的多项式，则通过构造，（2.2）得到完全正确的答案。Newton-Cotes公式通过使节点从-1到1等间隔来定义。低阶的Newton-Cotes公式作为微分方程和其他数值方法的离散化的构建块是重要的。 然而，它们的性质如n→∞是非常糟糕的，除了图1和图4中的简短再现之外，我们不会进一步讨论它们。高斯公式通过最优化地选择节点来定义，从而最大化（2.2）精确整合的多项式的阶数。 由于存在n + 1个节点，所以可达到的程度比一般情况（即2n + 1度）高n + 1个数量级也就不足为奇了。Gauss在30年代中期发现了高斯积分公式[25]，这是衡量高斯职业生涯非凡的生产力的一个指标，这个伟大的发现在他的生活的许多叙述中都不值一提。对于这些公式是真正强大的。 在计算机出现之前，它们的影响主要是理论上的，因为确定节点和权重以及在非理性论证中评估被积函数是困难的，但在计算机时代，特别是自从1969年Golub和Welsch发表论文以来 Goertzel在1954年的工作，1962年的Wilf和1968年的Gordon），它也是实用的[31]。 我们不会提供细节，只需提供以下MATLAB函数gauss.m，它几乎与[55]中的同名代码相同：例如，命令gauss（@ cos，6）产生1.68294196961579，这是完全正确的。 命令gauss（@ cos，1000）产生相同的结果，尽管我的笔记本电脑需要17秒。Clenshaw-Curtis积分的想法是使用Chebyshev点而不是最优节点。 这个主题有三个主要的变体（其他人参见[44]）：第一和第三变量分别被称为“经典”和“实际”克伦肖 - 柯蒂斯公式。 （特别是在20世纪60年代发表的一些相关论文没有提及Fej’er。）似乎最后的选择可能是最准确的[16]，并且与FFT最容易连接， 当n加倍时节点方便地重用节点的潜在优点; 它当然是在实践中主要使用的一个。 有问题的节点，我们简单地称切比雪夫点，由定义Clenshaw-Curtis积分公式是基于这些节点的公式（2.2）。 更好的名字可能是“Chebyshev”或“Fejer”，Clenshaw和Curtis称之为“切比雪夫公式” - 但是“Clenshaw-Curtis”这个词是标准的。Clenshaw和Curtis在1965年推出FFT之前于1960年发表了他们的论文。不久之后，Gentleman指出了与FFT的联系[28,29]。 我们再次不提供细节，但提供与gauss.m相同功能的MATLAB代码：为了获得余弦示例的完全准确性，我们现在需要clenshaw_curtis（@ cos，11）。 将n从11增加到103或106会得到相同的结果。 前者运行在我的笔记本电脑上不到一毫秒，而后者需要1.6秒。从精确地整合多项式的角度来看，Clenshaw-Curtis节点看起来像Newton-Cotes节点：两者仅仅在n阶精确。 然而，从图1可以清楚地看出，从字面意义上看，至少它们更接近高斯节点。当然它们具有与n→∞相同的渐近分布，密度nπ-1（1-x2）-1/2 众所周知，在[-1，1]上的多项式近似的各种意义上是最优的[55，Chap。5]0.43 实验比较图2显示了对于六个函数f（x），高斯和克莱肖 - 柯蒂斯公式的收敛性为n→∞。 （这个实验适用于[55]的输出30b和30c）。我们从单项函数f（x）= x20开始，在周期性上下文中的代数模拟将被称为带限函数。 这里的因子2在某种意义上是清晰可见的：高斯公式对于n≥10是精确的，对于n≥20是Clenshaw-Curtis公式。即使如此，很明显，对于较小的n值，高斯效率的优势（即达到一定准确度所需的n的大小）小于2的因子。第二个函数是ex，它是整数，即， 分析整个复杂平面。 在这里，高斯似乎比Clenshaw-Curtis更有效率，但不到2倍。RequirementCourse Name: ece275Author:NetID:Date:Project Name: project9Description:High-Level DescriptionIn this assignment you will calculate describe a social network of Twitter users as a graph and suggest friends to a specified user within that graph.Social Network AnalysisAs social networking is becoming more and more popular among people, there is a growing interest in the study of extracting information from these networks, the so-called social network analysis (SNA). The usage of social network analysis, however, is far beyond that of Facebook or Twitter. The principle of SNA can be applied to other things; such as, finding the source and flow of an infectious disease, and scheduling the optimal production-market distribution for a globalized company. The basic structure of SNA is a graph. To evaluate the characteristics of a graph and the nodes inside, people gradually develop a set of metrics, some of them are:Degree of CentralityIn an undirected graph, the degree centrality of a node i (denoted by CD(Java代写Clenshaw-CurtisGauss Quadrature better than Clenshaw-Ci)) is the node degree (number of edges), denoted by deg (i).CD(i) = deg (i)Centrality captures “how connected” a node is in general. In a directed graph, the degree of centrality comes in two types: the in-degree centrality and the out-degree centrality. The in-degree centrality is number of edges that end at the node (i.e., the number of edges going to the node). The out-degree centrality is the number edges starting at the node (i.e., the number of edges leaving the node).ClassesYou will be given one class to begin with. It is up to you to create other classes to represent the social network as a graph.The class provided is called SocialNetworkAnalysis and represents the entire program that you intend to run. The purpose of this class is similar to CarSimulator and Chars in previous projects except that it has only one function called Run which takes in only file paths. In this function, you need to call all of the functions you need to run the program from beginning to end. A good program design would be evident by this function calling only a few other select functions that do the bulk of the work of the program just as the endToEnd tests did in the past.The reason you are given this kind of class is mostly for the sake of grading your projects based on the end-to-end functionality. Since you are now given the freedom to write any functions or classes you choose, it is necessary for the grader to have a common function to call for all submissions in order to grade your project. So, you can think of this function, Run as your main function.Suggested ClassesUserUsers are essentially nodes/vertices in your graph. These need to be able to hold:A usernameA list of users following this user, you can decide which container to use for this.A list of users being followed, you can decide which container to use for this.RelationshipRelationship is essentially and edge. This should at least have:A copy, pointer, or reference to the “followed” UserA copy, pointer, or reference to the “following” UserSocialNetworkSocialNetwork is essentially the graph itself. This should at least have:A list of users, you can decide which container to use for this. You may want to hold users in more than one container for computational efficiency ^^. It’s best to start with one first.Important RequirementsFirst and foremost, your project will be graded only on the end-to-end functionality. Writing unit tests are optional, but testing and developing your program in smaller steps will save you, and instructors, loads of time. You have been shown examples on how to do this until now.Second, your program must finish in 5 seconds or less on the server. This has actually always been a requirement until now, but in this project, you will be handling substantially larger files at times. Therefore, having efficient algorithms actually becomes important. It is up to you to find the most computationally complex part of this assignment. My suggestion is that you make your program work first, then find the ineffeciencies later through debugging.Third, you must represent your social network as a graph structure for which a standard breadth-first or depth-first search can be used to search it.Input FileFormattingThe first line in the inputFilePath will contain the “root user” for which suggested friends will be found to follow.The inputFilePath will consist of real Twitter accounts with their friends and for each friend his/hers friends etc. By using this data build up a graph and calculate the in-degree centrality for each user. The input file will have the following format:github john_stewart github microsoft microsoft oracleEach line contains two usernames separated by three spaces. Each username is no longer than 15 characters and contain only alphanumeric characters (letters A-Z,a-z, numbers 0-9) with the exception of underscores. The two columns define the relationship between two accounts. The user in the second column is following the user in the first column. Thus, this is a directed graph. For an empty file, a file that does not have the correct format, or if the specified root user is not found in the graph, the program should create an empty output file.You can also assume that the input graph will be connected. Starting at any node, your program will be able to visit all other nodes using a breadth-first or depth-first search, or a variant thereof.ProcessingAs each line is read from the input text file, your program must keep track of users, their relationship, and their in-degree centrality. The in-degree centrality of a user is the number of users following it.Output FileThe program should create a file using the outputFilePath with an output consisting of a list of all the users within a depth of 3 of the specified root user that are not already being followed by that user. The list should be printed in descending order of in-degree of centrality. In case of ties, the users should be output alphabetically by username (case-insensitive). inDegreeofCentrality should be output using the default precision. The output file should have the following format:Looking for new accounts for rootUserName (inDegreeofCentrality) to follow userName1 (inDegreeofCentrality) userName2 (inDegreeofCentrality)& 转自：http://ass.3daixie.com/2018052610005431.html