ROS基本命令

右键新标签页查看大图！

have to do

Command

Command	Result	中文解释	图示
roscore	Open the core of the ROS.	启动ROS Master。
sudo apt install python3-ros+	Install the ros+ command.	下载需要用到的命令，如rosservice（如果你的python版本不是python3，用python-ros+就行）

Error

Error	Whose	Solution
	roscore	gedit ~/.bashrc export ROS_MASTER_URI=http://localhost:11311 export ROS_HOSTNAME=localhost export ROS_IP=’hostname -I’ source ~/.bashrc
“正在等待缓存锁：无法获得锁……”	apt install	use ‘sudo -i’ and install with root
若之后的指令运行不了，检查是否有右侧所示包，有关ros系统的安装问题参考Ubuntu 20.04安装Ros Noetic及Ubuntu 18.04安装ROS Melodic（两版本详细填坑）	rosrun turtlesim等等	sudo apt-get install ros-noetic-rospy、sudo apt install ros-noetic-roslaunch、sudo apt install ros-noetic-rosbash、sudo apt install ros-noetic-turtlesim、sudo apt-get install ros-noetic -teleop-twist-keyboard（注意我的版本是ubuntu20.04，因此对应ros-noetic系统）

need to run

rosrun: ros-run

Command	Result	中文解释	图示
rosrun turtlesim	Show you all the turtlesim commands.	列出所有可用的turtlesim命令。
rosrun turtlesim turtlesim-node	Create and run a turtle node.	启动小海龟结点、小海龟仿真器。
rosrun turtlesim turtle_teleop_key	Create and run a control node to control turtle with keyboard.	启动小海龟控制结点。

Error

Error	Whose	Solution
	rosrun turtlesim	打完指令之后，不要回车，tab两次就能出结果。

how to know

rqt_

Command	Result	中文解释	图示
rqt_graph	Show a graph contained nodes, topics and so on.	利用基于qt的可视化工具显示系统当前的结点和话题信息。
rqt_plot	rqt_plot /turtle1/pose/x:y: A plot show just-in-time turtle1’s pose.	基于qt的用于显示某信息的坐标工具。

ros+

Command	Add	Result	图示
rosnode	list，info，ping，machine，kill，cleanup	rosnode list: Show the names of all the nodes. rosnode info ABC: Show the information of the node named ABC, such as Publications, Subscriptions, Services and some Low-level communication information.	/rosout is a default active node.
rostopic	bw，delay，echo，find，hz，info，list，pub，type	rostopic list: Show the names of all the topics. rostopic pub ABC content[tab,tab]: Publish the content of ABC. Tab twice will make the content show. rostopic hz: 用来检测消息标题的发布频率。
rosmsg	show，info，list，md5，package，packages	rosmsg show [tab,tab]: Show message description. Tab twice will make the message description show.
rosservice	list，call，args，find，info，type，uri	rosservice list: Show the names of all the services. rosservice call ABC content[tab,tab]: Open a service named ABC, whose content can be shown by tab twice.	/spwan是产卵的意思。
rosbag	record，play	rosbag record: Start recording messages. rosbag play ABC: Play the messages of the bag named ABC.

附录

　　ROS可以通过在shell环境中输入命令来进行文件系统的使用、源代码编辑、构建、调试和功能包管理等。为了正确使用ROS,除了基本的Linux命令之外,还需要熟悉ROS专用命令。为了熟练掌握ROS的各种命令,我们对每个命令的功能进行了简单的描述,并给出了例子。在介绍每条命令时,考虑到使用的频率和重要性,标了星级评分。虽然很难从一开始就很熟练地使用所有的命令,但是随着使用的次数增多,读者会发现越来越方便快捷地使用各个ROS命令。

ROS功能包命令

roscd：移动功能包

roscd [功能包名称]
这是一个移动到保存有功能包的目录的命令。该命令的基本用法是在roscd命令之后将功能包名称写入参数。在以下示例中,turtlesim功能包位于安装ROS的目录中,但是,如果将创建的功能包名称(例如,在上一章中创建的your_pkg)作为参数,则会移至您指定的功能包的目录。这是在使用基于命令行的ROS时常用的命令。

1
2
3
4

$ roscd turtlesim
/ opt / ros / kinetic / share / turtlesim
$ roscd your_pkg
~/ catkin_ws / src / your_pkg

rosls: ROS文件列表

rosls [功能包名称]
该命令查看指定的ROS功能包的文件列表。您可以使用roscd命令移动到功能包,然后使用正常的ls命令执行相同的功能,但有时需要立即查看。实际中并不经常使用。

1
2

$ rosls turtlesim
cmake images msg srv package.xml

ROS执行命令

ROS执行命令管理ROS节点的运行。最重要的是,roscore被用作节点之间的名称服务器。执行命令是rosrun和roslaunch。rosrun运行一个节点,当运行多个节点或设置各种选项时使用roslaunch。rosclean是删除节点执行时记录的日志的命令。

roscore: 运行roscore

roscore [选项]
roscore命令会运行主节点,主节点管理节点之间的消息通信中的连接信息。主节点是使用ROS时必须首先被运行的必要元素。ROS 主节点由roscore运行命令来驱动,并作为XMLRPC服务器运行。主节点接收多种信息的注册,如节点的名称、话题和服务名称、消息类型、URI地址和端口号,并在收到节点的请求时将此信息通知给其他节点。此外,会运行rosout ,这个命令用于记录ROS中使用的ROS标准输出日志,例DEBUG、INFO、WARN、
ERROR和FATAL。它还运行一个管理参数的参数服务器。当执行roscore时,将用户设置的ROS_MASTER_URI作为主URI,并且驱动主节点，用户可以在~/.bashrc文件中设置。ROS_MASTER_URI。

rosrun:运行ROS节点

rosrun [功能包名称] [节点名称]
rosrun是执行指定的功能包中的一个节点的命令。以下例子运行turtlesim功能包的turtlesim_node节点。请注意,屏幕上出现的乌龟图标是随机选择并运行的。你也可以敲击[Tab] 观察turtlesim下的其他程序功能。

1

$ rosrun turtlesim turtlesim_node

roslaunch:运行多个ROS节点

roslaunch [功能包名称] [ launch 文件名]
roslaunch是运行指定功能包中的一个或多个节点或设置执行选项的命令。使用launch文件启动的方式对于运行多个节点非常有用,这是ROS中常用的执行方法。实例见实验六。

rosclean:检查及删除ROS日志

rosclean [选项]
该命令检查或删除ROS日志文件。在运行roscore时,对所有节点的记录都会写入日志文件,随着时间的推移,需要定期使用rosclean命令删除这些记录。以下是检查日志使用情况的示例。

1
2
3

$ rosclean check
320K ROS node logs 	
→ 意味着 ROS 日志一共占 320KB

当运行roscore时,如果显示以下警告信息,则意味着日志文件超过1GB,如果用户觉得会让系统不堪重负,请使用rosclean命令将其删除。

1

WARNING : disk usage in log directory [/ xxx /. ros / log ] is over 1GB .

以下是删除ROS日志存储库(笔者是/home/rt/.ros/log)的所有日志的示例。如果要删除它,请按y按钮将其删除。

1
2
3
4
5
6

$ rosclean purge
Purging ROS node logs .
PLEASE BE CAREFUL TO VERIFY THE COMMAND BELOW !
Okay to perform :
rm -rf /home/pyo/.ros/log
( y / n )?

ROS信息命令

ROS信息命令用于识别话题、服务、节点和参数等信息。尤其是rostopic、rosservice、
rosnode和rosparam经常被使用,并且rosbag是ROS的主要特征之一,它具有记录数据和回放功能,务必要掌握。

运行节点

我们将使用下面的命令,利用ROS提供的turtlesim来了解相关的节点、话题和服务。在使用ROS信息命令进行测试之前,需要做好以下准备工作。为确保顺利进行,关闭所有以前运行的终端。然后打开一个新的终端并运行以下命令。

1

$ roscore

为了运行turtlesim功能包中的turtlesim_node节点,打开一个新的终端并运行以下命令。这将从turtlesim功能包运行turtlesim_node。用户会在一个蓝色的屏幕上看到乌龟。

1

$ rosrun turtlesim turtlesim_node

运行turtlesim功能包中的turtle_teleop_key节点，打开一个新的终端并运行以下命令。这将在turtlesim功能包中运行turtle_teleop_key。一旦执行,可以在该终端窗口上,用键盘上的方向键控制乌龟。请自己尝试。当您按下方向键时,屏幕上的乌龟会移动,这是一个简单的仿真,但这是将驱动机器人所需的移动速度(m/s)和旋转速度(rad/s)用消息传送的。

1

$ rosrun turtlesim turtle_teleop_key

rosnode:ROS节点

rosnode list:列出正在运行中的所有节点

这是列出连接到roscore的所有节点的命令。如果已经运行了roscore和之前准备好的节点(turtlesim_node,turtle_teleop_key),则可以看到终端中列出了用于在roscore进行日志记录的rosout,以及teleop_turtle和turtlesim节点。

1
2
3
4

$ rosnode list
/rosout
/teleop_turtle
/turtlesim

rosnode info [节点名称]:检查指定节点的信息

使用rosnode info命令可以查看指定节点的信息。基本上,用户可以检查发布者、订阅者和服务等。此外,还可以检查关于节点运行URI和话题输入/输出的信息。由于会显示大量信息,因此省略了内容,所以请务必亲自运行。

1
2
3
4

$ rosnode info / turtlesim
------------------------------------------------
Node [/ turtlesim ] Publications :
* / turtle1 / color _ sensor [ turtlesim / Color ]

rosnode kill [节点名称]:终止指定节点的运行

这是一个终止正在运行的节点的命令。您可以在运行节点的终端窗口中使用[Ctrl+c]直接终止节点,但也可以指定要结束的的节点,如下所示。

1
2
3

$ rosnode kill /turtlesim
killing /turtlesim
killed

如果使用该命令终止了节点,则会在运行该节点的终端窗口上显示如下警告消息,并关闭该节点。

1
2

[ WARN ] [ 1499668430 . 215002371 ]: Shutdown request received .
[ WARN ] [ 1499668430 . 215031074 ]: Reason given for shutdown : [ user request ]

rostopic: ROS话题

在运行ROS话题示例之前,请先关闭所有节点。通过在不同的终端窗口中分别运行以下命令来运行turtlesim_node和turtle_teleop_key。

1
2
3

$ roscore
$ rosrun turtlesim turtlesim_node
$ rosrun turtlesim turtle_teleop_key

rostopic list：显示当前正在发送和接收的所有话题的列表。

1
2
3
4
5
6

$ rostopic list
/ rosout
/ rosout_agg
/ turtle1/cmd_vel
/ turtle1/color_sensor
/ turtle1/pose

rostopic echo [话题名称]:实时显示指定话题的消息内容

以下示例实时显示组成/turtle1/pose话题的x、y、theta、linear_velocity和angular_velocity的数据。

1
2
3
4
5
6

$ rostopic echo /turtle1/pose
x:5.35244464874
y:5.544444561
theta:0.0
linear_velocity:0.0
angular_velocity:0.0

rostopic info [话题名称]:显示指定话题的信息

在以下示例中,用户可以看到/turtle1/pose话题使用turtlesim/Pose消息类型,发布到/turtlesim节点,并且没有实际订阅的话题。

1
2
3
4

$ rostopic info /turtle1/pose
Type:turtlesim/Pose
Publishers:*/turtlesim(http://192.168.1.100:42443/)
Subscribers:None

rostopic pub [话题名称] [消息类型] [参数]:使用指定的话题名称发布消息

以下是使用/turtle1/cmd_vel话题名称发布类型为geometry_msgs/Twist的消息的示例

1
2

$ rostopic pub -1 /turtle1/cmd_vel geometry_msgs/Twist -- ‘[2.0, 0.0 ,0.0 ]’ ‘[0.0 ,0.0 ,1.8 ]’
publishing and latching message for 3 . 0 seconds

每个选项的描述如下：

ROS catkin命令

ROS的catkin命令用于使用catkin 构建系统来构建功能包。

catkin_create_pkg:自动生成功能包

catkin _ create _ pkg [功能包名称] [依赖性功能包 1 ] [依赖性功能包 2 ] …
catkin_create_pkg是创建一个包含CMakeLists.txt和package.xml文件的空功能包的命令。以下例子显示了使用catkin_create_pkg命令创建一个依赖于roscpp和std_msgs的my_package功能包。

1

$ catkin_create_pkg my_package roscpp std_msgs

catkin_make:基于catkin 构建系统的构建

catkin_make [选项]
catkin_make是构建用户创建的功能包或构建下载的功能包的命令。以下示例是构建~/catkin_ws/src目录中所有功能包的示例。

1
2

$ cd ~/catkin_ws
$ catkin_make

如果要只构建一部分功能包,而不是全部功能包,请使用“–pkg [包名]”选项来运行,如下所示:

1

$ catkin_make -- pkg my_package

第一步 下载谷歌上网助手

链接：https://pan.baidu.com/s/1-QimGqEr7fLtpfkSP35waA
提取码：b9lm
下载这个文件夹中“谷歌上网助手.zip”。
之后解压，然后点击Chrome浏览器右上角三个点->更多工具->扩展程序，点开后，打开右上角开发者模式，于是左上角出现“加载已解压的扩展程序”，选中你的解压完成的文件夹。然后就添加成功了。
右上角出现黄黄绿绿蓝蓝红红的一个圈，点击，用邮箱注册，然后就可以使用谷歌一系列的服务了。
若本来就可以使用谷歌的服务或者希望在火狐浏览器下载，请忽略这一步。

第二步 下载油猴插件

点击Chrome浏览器右上角三个点->更多工具->扩展程序，打开右上角开发者模式，然后点左上角，出现：

然后点击最下方的“打开Chrome应用商店”，搜索tampermonkey，下载第一个。右上角出现油猴插件的图标。

第三步 新建脚本

点击右上角的油猴图标，点击添加新脚本，然后清空原内容，复制粘贴网盘中的“中国大学mooc脚本.txt”内容：
链接：https://pan.baidu.com/s/1-QimGqEr7fLtpfkSP35waA
提取码：b9lm
最后保存：

第四步 使用脚本

该脚本是供mooc网页版使用的，来到mooc网页，即可使用该脚本具有的功能，如自动检索答案。

Proxy

Options

Intercept Client Requests

1. Intercept requests based on the following rules: 开启Requests过滤规则。
2. Automatically fix missing or……: 自动修复丢失或多余的新行。

Intruder

Payloads

1. 如果我有罪，请让我努力学习先进的东西改造自己，而不是拿写得稀烂的程序让我原地debug。
2. 不会吧不会吧，真有实验书的代码从头到尾都是错的还缺资源包。哦原来这实验书是让我改啊，那没事了。

数值分析

引论

基本概念

• 误差：近似值和实际值（精确值）的差别。
• 误差限：误差的限度。是误差绝对值的“上界”。
• 相对误差：误差除以实际值乘以100%。相对误差较小时，可除以近似值。
• 相对误差限：相对误差的限度。相对误差限小则近似程度好。
• 有效数字：一个数中，可供判断精度的数字。若近似值x*的绝对误差限是某一位上的半个单位，且该位直到x*的第一位非零数字一共有n位，则称它有n位有效数字，或精确到该位（比如精确到0.1，0.0001）。
• 经过四舍五入得到的近似数：有效数字可以通过四舍五入判定原则直观地数出来的数。

有效数字位数的三种判定方法

• 通过定义（绝对误差）判定：计算出近似值的绝对误差，再取一个最小的某一位上的半个单位的绝对误差限，即可得到精度。

  【例】绝对误差=0.008<0.05，说明绝对误差限可取0.05=0.5/10，精确到0.1。

• 通过四舍五入原则判定：若近似值是由精确值四舍五入得到的，可采用这种判定方法。

  【例】3.1415926，3.14由小数点后第3位四舍五入得到，则3.14精确到小数点后第二位，从这一位到前面第一个不等于0的数都是3.14的有效数字。

• 通过相对误差限判定有效数字的位数：近似值边界判定+绝对误差判定=>有效数字位数。

有效数字与相对误差限的关系

（公式是记不住的，推导=绝对误差判断方法+近似值边界判定。）

• 利用有效数字估算绝对误差限，结合$a_1$确定近似值的下界，相除，以近似值估计相对误差。

  近似值$x^{＊}=±0.a_1a_2…a_n×10^m$，其有n位有效数字，$a_1≠0$，则其相对误差限为$\frac{1}{2a_1}×10^{-n+1}$。

• 结合$a_1$确定近似值的上界，相乘，得到绝对误差限，借此判断有效数字位数。

  近似值$x^{＊}=±0.a_1a_2…a_n×10^m$，$a_1≠0$，其相对误差限为$\frac{1}{2a_1+1}×10^{-n+1}$，则其有n位有效数字。

误差限的估计公式

已知x,y的绝对或相对误差限，求f(x,y)的绝对或相对误差限。

（仅写出绝对误差限公式，相对误差的公式直接由此推导就好了，记不住的）

• 加减运算：x和y的加减结果的绝对误差限=x的误差限+y的误差限。

$$
|(x^{＊}±y^{＊})-(x±y)|≤|x^{＊}-x|+|y^{＊}-y|
$$

• ☆☆☆乘除运算：绝对误差限较小时的估计方式（为简化结果）——

$$
η(x^{＊}y^{＊})≈|x^{＊}|η(y^{＊})+|y^{＊}|η(x^{＊})
$$

$$
\eta (\frac{x^{＊}}{y^{＊}})≈\frac{|x^{＊}|η(y^{＊})+|y^{＊}|η(x^{＊})}{|y^{＊}|^2},y≠0,y^{＊}≠0
$$

近似计算中的原则

保留位数原则

加减运算：小数位

• 计算时：把近似数中小数位数较多的数四舍五入，使其比小数位数最少的数多一位。
• 计算结果：保留的小数位数与原近似数中小数位数最少者相同。

  乘除运算：有效数字

• 计算时：因子保留的位数应比有效数字位数最少者的位数多一位。
• 计算结果：有效数位数与原近似值中有效数字位数最少者至多少一位。

  乘方与开方运算：有效数字

• 计算结果：有效数字位数与原近似值的有效数字位数相同。

  对数运算：有效数字

• 计算结果：有效数字位数与其真数（被对数运算的数）的有效数字位数相同。

  中间计算过程

• 应比上述保留位数原则所提及的位数多取一位，在进行最后一次计算时这一位要舍入。

  原始数据选取

• 加减运算：小数位应比计算结果要求的多一位。
• 上述其他运算：有效数字位数应比计算结果要求的多一位。

其他原则

• 避免两个相近的数相减：有效数字损失。
• 避免除数绝对值远远小于被除数绝对值的除法：舍入误差增大。
• 要防止“大数”吃掉“小数”：数量级相差过大时小数在计算过程中被舍入（比如计算机内计算时加减法要对阶）。
• 要尽可能减少运算次数：减小累积误差。

  重点应用

  求误差限

• 已知经过四舍五入得到的近似数（或误差限），求它们的四则运算结果的误差限：利用有效数字数量可以反过来估算一个绝对误差限。再结合近似值的上下界可进一步估算相对误差限。

  算术运算

• 保留位数原则的利用。
• 利用近似原则分析运算优劣。

  仅在选择、判断常见的内容

计算方法的研究方法

• “离散化”方法：将连续变量问题转化为离散变量问题。
• “递推”方法：将复杂问题转化为简单问题的重复。
• “近似替代”方法：将不能用有限计算解决的问题转化为较简单的有限计算问题。

误差的来源（需要具备判断误差种类的能力）

• 模型误差：问题理想化。
• 观测误差：原始数据观测误差。
• ☆截断误差：计算是有限次带来的误差。
• ☆舍入误差：参与计算的数长度有限带来的误差。

  为什么要引入误差限的概念？

• 答：因为精确值一般未知，误差只能在一定范围内研究，而这个范围就叫做误差限。由于研究范围是不惟一的，误差限也具有不惟一性。

插值方法

两个插值惟一性

均可用反证法证明。

• 插值多项式的存在惟一性：n+1个数据对应的次数不高于n的代数多项式存在且惟一。
• Hermite插值多项式的惟一性：满足给定条件的Hermite插值多项式惟一。

Lagrange插值公式

• 插值基函数$l_n(x)$：次数为n的、以$x_{1} ～ x_{n}$为零点、在$x_0$处为1的函数。
• Lagrange公式：函数值乘以基函数。
• Lagrange余项：反复求导用Rolle定理得到。

$$
f(x)-p_n(x)=\frac{f^{n+1}(ξ)}{(n+1)!}\prod_{i=0}^{n}(x-x_i)
$$

Newton插值公式

• 插值基函数$\varphi_n(x)$：$(x-x_0)$到$(x-x_{n-1})$的乘积。
• Newton公式：差商乘以基函数。
• ☆Newton余项：

$$
f(x)-N_n(x)=f[x,x_0,···,x_{n}]\varphi _n(x)
$$

• k阶差商：

$$
f[x_0,x_1,···,x_k]=\frac{f[x_0,···,x_{k-1}]-f[x_1,···,x_{k}]}{x_0-x_k}
$$

• ☆k阶差商表示形式二：该表示形式承袭性弱。

  用数学归纳法可证。（证明方式由差商的定义形式可知）

$$
f[x_0,x_1,···,x_k]=\sum_{j=0}^{k}\frac{f(x_j)}{\omega ‘_k(x_j)},\omega ‘k(x_j)=\prod^k{i=0,i≠j}(x-x_i)
$$

• 表达形式二可推出：
  • 差商的对称性：差商的值与节点的排列顺序无关。
  • 数据点越多的、带x数据项的差商的x幂次反而越低。

Hermite插值

• 仅讨论一阶导数值和函数值给定的情况。

• 插值基函数$\varphi _n(x)$和$\Psi _n(x)$：与Lagrange基函数构造思路一致。

  区别：根据导数条件构造的基函数与根据函数值构造的基函数符号相异。

• Hermite公式：函数或导数值乘以基函数。

• Hermite基函数的多项式系数计算方法：

  • 按照定义构造式子，解线性方程组死算。
  • 根据承袭性。比如已知$x_0,x_2,···,x_n$对应的函数值，并知道某些点的导数值(比如知道$x_0,x_1$的)，则可以构造函数，$p_n(x)$是Lagrange或者Newton求出来的多项式，分别求解$p_n(x)$和$a_i$。

$$
H_{n+2}(x)=p_{n}(x)+(a_0x+a_1)(x-x_0)(x-x_1)···(x-x_n)
$$

• Hermite余项：在某一结点有多少项就乘以多少次方。

$$
f(x)-H_n(x)=\frac{f^{n+1}(ξ)}{(n+1)!}\prod_{i=0}^{n_1}(x-x_i)×\prod_{i=0}^{n_2}(x-x_i),n_1+n_2=n
$$

分段插值法

• 分段插值公式的单个区间的x只在区域内。因此可以计算得到误差的最大值、精度可以被划分区间长度限制、收敛性总能得到保证、修改数据点只有局部受影响。而Lagrange余项或插值公式并没有对x取值进行讨论。
• 分段线性插值：单个区间的误差<$\frac{1}{8}h_i^2$×这一段二阶导的最大值。
• ☆分段三次Hermite插值：单个区间的误差<$\frac{1}{384}h_i^4$×这一段四阶导的最大值。

重点应用

构造插值多项式求函数值

• 给数据表，计算Lagrange、Newton、Hermite插值多项式。（一般给的数据比较少），Newton插值多项式在x有规律地分布时是最好算的。
• 也可能是求x的值，把表反过来用就行。

由一个插值多项式推另一个

• 多半使用了承袭性。可以先看看之前的那个多项式是由哪些点推导而来的。如果单纯增加了导数，就Hermite插值多项式的承袭性；如果增加的是点，就用Newton差商的承袭性。后者比前者好算。

证明等式成立

• 多半用了差商的性质，结合其他的定义式。

证明一致收敛

• 把误差计算出来，如果在某条件下误差趋向0，说明一致收敛。（绝对值）

仅在选择、判断中出现的内容

Lagrange与Newton插值余项的比较

• Lagrange余项要求f(x)有(n+1)阶导，Newton余项中含有f(x)。
• Newton插值公式可改写成：

$$
N_n(x)=f(x_0)+f’(ξ_1)\varphi _1(x)+···+\frac{f^{(n)}(ξ_n)}{n!}\varphi _n(x),ξ∈[min(x_i),max(x_i)]
$$

Runge现象

• 大范围内使用高次插值，逼近效果往往并不理想。

• Runge举例：在x=±5附近，$p_{10}(x)$偏离f(x)的程度远大于$p_5(x)$。

$$
f(x)=\frac{1}{1+x^2},-5≤x≤5
$$

分段插值法的缺憾

• 即使是分段三次Hermite插值，在插值节点处插值曲线也不够光滑，而且这种需要提供的信息很多。

样条插值和曲线拟合

• 样条插值：分段三次Hermite插值改进，为解决插值结点处曲线不够光滑。
• 最小二乘法：不要求所构造的逼近函数严格地通过给定的数据点，只是在某一函数类H中，以使残差的平方和最小为标准，作近似替代。主要讨论的是多项式拟合。

数值积分

基本概念

机械求积

• 定义：取一个合适的值作为积分区间的平均高度，再乘以积分区间的宽度，得到积分区间的面积。
• 应用：Newton-Cotes公式、中矩形公式等。
• 基本构造：令$A_i$为求积系数,$x_i$为求积结点，

$$
∫^b_af(x)dx≈\sum^n_{i=0}A_if(x_i)
$$

• 求积系数$A_i$的求解方法：
  • 解线性方程组法：根据代数精度的定义，依次使f(x)=$1,x,x^2,x^3,···,x^m$，建立一系列等式，求出求积系数$A_i$。
  • 插值法：用Lagrange插值多项式近似替代被积分函数，积分得到求积系数为$A_i=∫^b_al_i(x)dx$。对于已知的插值节点和常数a,b，$∫^b_al_i(x)dx$是常数。

代数精度

• 定义：如果求积公式对于一切次数小于等于m的多项式是准确的，而对于次数为m+1的某一多项式并不准确成立，则称该求积公式具有m次代数精度。
• 证明方法：因为积分具有线性性，所以“准确成立”也具有线性性。证明m阶代数精度，只需要代入证明对$x^m$和$x^{m+1}$是否准确成立即可。即：

$$
∫^b_af(x)dx=\sum^n_{i=0}A_if(x_i),f(x)=x^k(k=0,1,···,m)
$$

• 性质：n+1个互异结点构造的求积公式的代数精度不低于n。

插值型的求积公式

• 定义：求积系数为$A_i=∫^b_al_i(x)dx$的求积公式。
• 性质：求积公式至少具有n次代数精度的充要条件是它是插值型的。

数值稳定性

• 定义：即计算结果可靠。一个算法，如果在执行它的过程中舍入误差在一定条件下能够得到控制，即舍入误差的增长不影响产生可靠结果，则称它是数值稳定的。
• 证明：计算总的舍入误差，若它是有上界的，则可称它是数值稳定的。

事后误差估计法

• 定义：直接用计算结果来估计误差的方法。

Newton-Cotes公式

• 定义：等距节点的插值型的机械求积公式。将积分区间分成(n+1)份。
• n=1,2,4的Newton-Cotes公式常用：
  • ☆梯形公式：1/2, 1/2
  • ☆Simpson公式：1/6, 4/6, 1/6
  • Cotes公式：7/90, 32/90, 12/90, 32/90, 7/90
  • ☆三阶的Cotes系数为：1/8, 3/8, 3/8, 1/8
• 性质：
  • 代数精度：因为是插值型，所以至少为n；且当n为偶数时，它的代数精度至少为n+1。由n+1阶多项式对应的余项做代换之后等于0证明。
  • 数值稳定：n=8或之后不再具有数值稳定性，因为Cotes系数出现负数。总舍入误差可以写成与Cotes系数与(b-a)相关的。
  • ☆截断误差：（由Lagrange插值多项式的余项积分得到）
    • 梯形公式：$R=-\frac{1}{12}(b-a)^3f’’(ξ),ξ∈[a,b]$；
    • Simpson公式：$R=-\frac{1}{90}(\frac{b-a}{2})^5f^{(4)}(ξ),ξ∈[a,b]$；
    • Cotes公式：$R=-\frac{8}{945}(\frac{b-a}{4})^7f^{(6)}(ξ),ξ∈[a,b]$；
  • n<8时，有如下性质：(取f(x)=1可证)

$$
\sum^n_{i=0}C_i=\sum^n_{i=0}|C_i|=1
$$

复化求积法

• 原理：把区间分成n个小区间，在每个小区间上采用次数不高的插值多项式去替代被积函数，构造出相应的求积公式，然后把它们加起来作为整个积分区间上的求积公式。步长h=$\frac{b-a}{n}$。

• 确定重复被加的求积节点应作图。（见章末附图）

• 根据余项确定步长：

  • ☆复化梯形公式：$|R_T|≤\frac{nh^3}{12}max[f’’(x)]$
  • 复化Simpson公式：$|R_S|≤\frac{nh^5}{90}max[f^{(4)}(x)]$
  • 复化Cotes公式：$|R_C|≤\frac{8nh^7}{945}max[f^{(6)}(x)]$
  • 缺陷：求导麻烦、（用导数最大值）估计较保守。

• ☆递推法（二分法）确定步长（以梯形法为例）：

  • 取n，近似计算$T_n$；
  • 用$T_{n}$近似计算$T_{2n}$，其中$x_i$是二分新增的节点；

$$
T_{2n}=\frac{1}{2}T_n+(\frac{1}{2})^n[f(x_1)+f(x_2)+···+f(x_n)]
$$

• 判断$|T_{2n}-T_n|≤ε$是否成立，如果成立则表示$T_{2n}$满足精度要求。该判断误差的方法是一种事后误差估计法。

Romberg积分法

• 用误差来修正公式，由低精度求积公式的组合得到较高精度求积公式。它算法简单，收敛速度快。误差估计与Newton-Cotes公式截断误差同。
• ☆$S_n=\frac{4}{3}T_{2n}-\frac{1}{3}T_n；C_n=\frac{16}{15}S_{2n}-\frac{1}{15}S{n}；R_n=\frac{64}{63}C_{2n}-\frac{1}{63}C_n$。

重点应用

构造求积公式（例题有，课后习题没有）

• 由代数精度构造求积公式；

  1. 设f(x)=$1,x,x^2,x^3,···,x^m$，代入求积公式构造式。
  2. 解线性方程组，得到$A_i$。

• 由插值节点构造求积公式：

  1. 列出插值基函数；

  2. 计算插值基函数在区间内的积分，得到$A_i$。

求代数精度（详情见上）

计算截断误差，通过误差判断步长等

• 利用Taylor公式求截断误差；
• 利用（复化）Newton-Cotes公式结论求截断误差。

证明是插值型的

• 非常规，证明题：
  • 确定插值结点，列出插值基函数；
  • 分别对插值积分，对比求积系数，看是否相等，若均相等则为插值型。
• 常规并均分：对比Cotes系数。

常微分方程数值解法

基本概念

• ☆初值问题：求解$y’(x)=f(x,y),y(x_0)=y_0$方程组，满足Lipschitz条件则有唯一解。

$$
Lipschitz:|f(x,y)-f(x,{ \bar y})|\leq L|y-\bar y|,L\geq 0
$$

• $y_n$：$y(x_n)$的近似值。$y(x_n)$是y(x)在$x_n$处的精确值。
• 显式递推公式等式右边没有$y_{n+1}$，隐式的有。
• 局部截断误差：
  • 定义：假定在求$y_{n+1}$的递推公式中等式右边所有的量都是精确的，在此前提下的$y(x_{n+1})-y_{n+1}$。
  • 计算方法：使用局部截断误差的定义和Taylor公式展开。
• 精度：局部截断误差为$O(h^{p+1})$，则称此方法精度为p阶。
• 收敛性：h→0(同时n→∞)时趋向于准确解$y(x_n)$。
  • 收敛性定理：假设单步法具有p阶精度，且增量函数满足Lipschitz条件，且初值是准确的，则其整体截断误差为$O(h^p)$。
• 稳定性：误差的积累得到控制。
  • 扰动：$\delta _n=\tilde y_n-y_n $。
  • 隐式尤拉法无条件稳定。
• 整体截断误差：$|y(x_{n})-y_{n}|$可由局部截断误差反复递推得到。

近似递推公式

构造方法

一阶差商法

• 尤拉法（折线法）：向前差商，显式，单步，一阶；
• 隐式尤拉法：向后差商，隐式，单步，一阶；不能直接计算：
  • 计算时化为显式；
  • 预报-校正法：尤拉预报，隐式校正。
• 二步尤拉法（中心差商法）：中间差商，显式，二步，二阶。

解定积分法

• 原理：$∫^{x_{n+1}}{x_n}y’dx=y(x{n+1})-y(x_n)=hf(x_ξ,y_ξ)$。其中解定积分参考第三章。

• 梯形公式：

  • $f(x_ξ,y_ξ)=\frac{f(x_n,y_n)+f(x_{n+1},y_{n+1})}{2}$。单步，隐式，二阶。
  • 是尤拉法和隐式尤拉法的算术平均，计算量大。

• 改进的尤拉法：用预报-校正法改进梯形公式的结果。

  • 嵌套形式：将预报值直接代入梯形公式中。

  • 平均化形式：利用了梯形公式是尤拉法和隐式尤拉法的算术平均。

    这种形式更好观察几何意义。

    $y_p=y_n+hf(x_n,y_n)=y_n+hk_1;$

    $y_c=y_n+hf(x_{n+1},y_p)=y_n+hk_2;$

    $y_{n+1}=\frac{1}{2}(y_p+y_c)$。

龙格-库塔法

• 原理：
  • 本质：构造$y(x_{n+1})=y(x_n)+hy’(ξ)$中$y’(ξ)$的近似替代。
  • 方法：构造导数近似值，利用Taylor公式分析局部截断误差，求出导数近似值对应的参数的值。
• 一阶：比如用$y’(x_n)$的近似值替代$y’(ξ)$。
• 二阶：用$x_n$、$x_{n+1}$两点上的导数近似值的平均替代$y’(ξ)$。
  • 改进的尤拉法：$\lambda =\frac 12,, p=1$；
  • 变型的尤拉法（中点方法）：$\lambda =1,, p=\frac 12$；
  • ☆构造：$\lambda p=\frac 12$。

$$
f(n)= \begin{cases} y_{n+1}=y_n+h((1-\lambda )k_1+\lambda k_2) \k_1=f(x_n,y_n) \ k_2=f(x_n+ph,y_n+phk_1) \end{cases}
$$

• 三阶：举例。

$$
f(n)= \begin{cases} y_{n+1}=y_n+\frac16(k_1+4k_2+k_3) \k_1=hf(x_n,y_n) \ k_2=hf(x_n+\frac 12h,y_n+\frac 12k_1) \k_3=hf(x_n+h,y_n-k_1+2k_2) \end{cases}
$$

• ☆四阶：

  • Gill公式。

  • 经典公式（标准4阶龙格-库塔公式）：

$$
f(n)= \begin{cases} y_{n+1}=y_n+\frac16(k_1+2k_2+2k_3+k_4) \k_1=hf(x_n,y_n) \ k_2=hf(x_n+\frac 12h,y_n+\frac 12k_1) \k_3=hf(x_n+\frac 12h,y_n+\frac 12k_2)\k_4=hf(x_n+h,y_n+k_3) \end{cases}
$$

• 性质：适用于求解范围大、精确度要求高的较光滑曲线求解。

• 变步长：

  • 计算结果的偏差$△=\frac 1{2^p-1}|y_{n+1}^{(h/2)}-y_{n+1}^{(h)}|$；
  • 在满足精度的要求下，步长尽量取大。

重点应用

解初值问题

• 不是算公式，是计算离散点的值。
• 计算时先把预报的值求出来，而不是直接把公式代入预报的公式。

求解计算公式的精度

• 主要是用泰勒公式，重点步骤(偏导和导数的关系)：

$$
f’_x(x_n,y_n)+f’_y(x_n,y_n)y’(x_n)=y’’(x_n)
$$

证明收敛性、稳定性

• 收敛性：证明满足Lipschitz条件；
• 稳定性：证明扰动可控。
  • 假设一个扰动；
  • 计算这个扰动在递推后得到的下一个扰动值；
  • 令递推之后扰动的传播系数不超过1，得到稳定性条件；

仅在选择、判断中出现的

• 数值解法：能算出精确解y(x)在一系列离散节点上的近似解的方法。
• 二步尤拉法的缺陷：①计算局部截断误差时的附加限制条件不一定成立；②h足够小时，精度越高才能保证局部截断误差越小。

方程求根

基本概念

• m重根：f(x)=$(x-x^＊)^mg(x),g(x^＊)\neq 0$。
• 隔根区间：区间内只有一个根的区间。
• 有根区间：区间内有根的区间。
• 局部收敛性：如果存在领域△:$|x-x^＊|\leq \delta$，迭代过程对于任意初值$x_0\in △$均收敛，则这种在根的邻近具有收敛性的收敛性称为局部收敛性。若$\varphi (x)$在$x=\varphi (x)$的根$x^＊$邻近有连续的一阶导数，且$|\varphi ‘(x)\leq k <1|$，k越小收敛得越快。
• 迭代速度（收敛速度）：迭代误差$\varepsilon k =x_k -x^＊ (k=0,1,···)$，对某个实数p与非零常数C，有$lim{k→∞}\frac{\varepsilon _{k+1}}{\varepsilon ^p_k}=C,C\neq 0$，则称{x$_k$}是p阶收敛的，p=1则是线性收敛，p>1是超线性收敛，p=2是平方收敛。p越大，收敛越快。

逐步搜索法

• 预定步长，按一定顺序看每一步上的导数值，直到确定根区间或遍历结束。

二分法

• 逐步搜索法的改进，只能求出一个根。二分看导数值。
• 适用于：一个边界异号的有根区间。
• ☆误差估计：$|x^＊-x_k|\leq \frac {1}{2^{k+1}}(b-a),k=1,2,···$

迭代法（逐步逼近的方法）

• 原理：将$f(x)=0$转换成$x=\varphi(x)$，如果$\varphi(x)$是收敛的，迭代结果是方程的根。

• 收敛性定理：设$\varphi (x)$在[a,b]上具有连续一阶导，且$\varphi (x)\in [a,b]$，存在正数L<1，使对任意$x\in [a,b]$，有$|\varphi ‘(x)|\leq L<1$，则唯一解，而且对任意$x_0$序列收敛。

• ☆误差估计：$|x^＊-x_k|\leq \frac {L^k}{1-L}|x_1-x_0|,k=1,2,···$。

• 收敛过程加速的原理：估计迭代结果的误差，并将误差估计加至迭代式中，则可能产生一个更好的求根迭代式。如Aitken加速，用了两次迭代改进。

• 牛顿法（又称切线法）：迭代函数根据导数变化。

  • 构造：$x=x-\frac{f(x)}{f’(x)},(f’(x)\neq 0)$.
  • 局部收敛性：若$x^＊$是方程f(x)=0的一个单根，并且f(x)在$x^＊$即附近有连续的二阶导数，则牛顿法具有局部收敛性。
  • ☆收敛速度：若二阶导$f’’(x)\neq 0$，则平方收敛；
  • 局限性：初值需要选取与根相近的。要保证$|\varepsilon _1|<|\varepsilon _0|$。

• 牛顿下山法：改进的牛顿法。

  • ☆构造：$x_{n+1}=x_n-\lambda_n\frac{f(x_n)}{f’(x_n)},0<\lambda _n <1,\lambda$是下山因子。
  • ☆下山条件：$|f(x_{k+1})|<|f(x_k)|$，令$\lambda$不断减半直到满足单调性条件。

重点应用

• 二分法求根并分析误差
• 证明迭代法的收敛性和收敛速度
• 对牛顿法进行误差分析

参考文章

• 看完这篇你还不知道这些队列，我这些图白作了
• Java中的queue和deque对比详解

  总结

• 队列遵循FIFO原则，但是不一定以FIFO的方式排序各个元素。

  非循环队列

• 数据迁移只需要在tail=MaxSize&&head!=0时进行，以节省使用代价。
  
• 判断队列满了的条件，tail = MaxSize,head = 0。
• 链式队列与顺序队列比起来不需要进行数据的迁移，实现相对简单很多，但是链式队列增加了存储成本。

  循环队列

• 对于一个存储空间为n的循环队列，只能存放n-1位数据，令tail与head重合时为队空条件，(tail+1)%MaxSize==head时为队满条件。
• 出入队列都应该取模。比如入队tail=(tail+1)%MaxSize，出队head=(head+1)%MaxSize。
• 队列长度length=(tail-head+MaxSize)%MaxSize。一般队列长度仅需要tail-head，而循环队列中，head可能会比tail大，所以需要加上MaxSize并取模。
• 由长度公式以及队满条件知，显然，循环队列队满时length为MaxSize-1。

  双端队列（Deque）

• 队头、队尾都可以进行入队、出队操作。总之它即有栈的功能，也有队列的功能。
• 在将双端队列用作队列时，将得到FIFO行为；在将双端队列用作堆栈时，将得到LIFO行为；

  优先队列（不遵循FIFO）

• 从队头出队，队尾入队。不过每次入队时，都会按照入队数据项的关键值进行排序。保证优先级最高的最先出队。
• 一般用堆实现。

参考文章

计算元素地址（i、j均开始于1）

• 主要是要分析出该元素前面有多少个(记为n)元素，分析出来了即可知道下标为n，LOC(i)=LOC(0)+size(L)*n。

• 分析过程：以行序或列序优先将矩阵中的元素依次排列。以按行序优先排列为例，假设k元素在第i行，则前面应至少有x个元素，再假设k在第j列，在当前行中前面应再有y个元素，从而得到k元素与i、j的对应关系。

  按列序存放（高下标优先）

• 对于A_m*n，有LOC(i,j)=LOC(0,0)+(j*m+i)*sizeof(L)。

• 对于A_abc，有LOC(i,j,k)=LOC(0,0)+(k*a*b+j*a+i)*sizeof(L)。

• 同理可推至n维数组。

IDA报错

• please use ida (not ida64) to decomplie the current file：说明这是32位程序，需要用到ida文件夹中的ida.exe打开，而不是ida64.exe。

IDA使用

• (linux下pip install pwntools)checksec 文件名，可检查文件类型。
• 拖入文件

快捷键

1. f5反汇编成c语言伪代码。也可View-open subviews-Generate pseudocode。

2. Alt+T搜索文本。更多搜索选项可见Search栏。

3. 查看变量地址：双击这个变量。

功能

参考文章

树

• 非线性，一对多。（定义是递归形式的）

• 根（根结点的层为1）、根的子树、结点的度（结点的子树数目）、叶子结点（也叫终端节点）、分支节点、双亲（虽然叫双亲但是parent只有一个）、树的深度（又称高度，叶子结点的层数）、兄弟、堂兄弟（同层不同双亲的结点）、祖先、子孙（所有子树的结点）、有序树（子树的顺序从左到右有限定，更换则不是同一颗树）、无序树。

• 森林：m棵互不相交的数的集合，如F={T₁,T₂,T₃}，任何一棵非空树可表示为Tree=(root,F)，F是子树森林。

  因为root根结点被拆掉了之后剩下的子树就散了互不相交可以看作森林）

二叉树

• 递归定义：根节点，左子树右子树。每个结点的孩子是不会重复的。
• 每个结点至多两个子树，是有序树。
• 叶子结点的个数n₀=度为2的结点数n₂+1。（不直观，需要记）

  总数n=n₀+n₁+n₂，孩子的个数=n-1=2n₂+n₁。

• 含有n个结点的二叉链表中，有n+1个空链域。

  利用n₀=n₂+1，空链域数=2n₀+n₁。

• 满二叉树：深度为k且有2^k-1个结点的二叉树。

  完全二叉树

• 每个结点都和同深度的满二叉树中的编号从1至n的结点一一对应。其叶结点只可能出现在层次最大或者第二大的层上。结点数2^k-1-1<n<=2^k。
• 对于完全二叉树的第i个结点，若2i>n，则该结点没有左孩子结点；若2i+1>n，则该结点没有右孩子结点。若结点有双亲结点，则双亲结点的编号必然是i/2向下取整。

  存储结构

• 采用链式存储结构比较方便。
• 三叉链表比二叉链表多一个指向双亲结点的指针。
• 静态链表也可以用来描述二叉树，此时的左孩子右孩子指针只要是孩子结点对应的标号（当然也可以是指针，但没必要）就可以了，整体看起来是一个结构数组。

二叉树遍历：

D—-访问根节点，输出根节点
L—-递归遍历左子树
R—-递归遍历右子树

1. 先序遍历DLR
2. 中序遍历LDR
3. 后序遍历LRD

github使用非常简单，和百度一样用就行，也支持下载上传，多看看就能掌握基本操作，暂时不讲，先说git。

git

1.下载

链接：https://pan.baidu.com/s/1-QimGqEr7fLtpfkSP35waA
提取码：b9lm
以上是我自己在用的Git-2.11.1-64-bit。
在官网上下载也行，但是不推荐，因为官网下的也差不多，而且官网常常难以打开难以下载，容易链接失败，点一年都不一定能生成下载链接。（个人体验）
然后按默认选项安装即可。

2.git内登录github账号

之后的不赘述，直接给链，廖雪峰大神讲得比我好。由于还在入门，我们只想简单知道git而不是立即搞事情，版本库可以先不建。后面的如何回退也可以不用看。登录成功就行。
https://www.liaoxuefeng.com/wiki/896043488029600/896067074338496

3.github上不太方便而git很方便做的某些事

1

git clone xxx

xxx是github下载按钮处的链接。
还有的方便的就是用git删文件。直接在本地库上操作，再往上push一下就好了，这种需要建库的事情请继续看廖大佬的教程。
如果看不懂的话，或者说有些基础指令有问题的话，请看下面的有关大学计算机基础的教程。

大学计算机基础

链接：https://pan.baidu.com/s/1-QimGqEr7fLtpfkSP35waA
提取码：b9lm
以上还有我们计算机基础的课件。
这个是讲cmd之类的东西的，很多东西都是依赖这些指令的，所以建议随便看看用用。
其实吧，说起来就这么几条指令必用：

1
2
3

cd ..
cd Desktop
dir

第一条，退回上一级目录；
第二条，去下一级名字叫做Desktop也就是桌面的目录；
第三条，展示当前目录下的所有文件。

为什么说这三条是必备的，而不是删除之类的呢？
第一二条让你便捷地前后跳转，而第三条让你知道你现在能去哪。

一级一级跳转有时候属实不便，所以建议再会一条指令，cd 绝对路径

绝对路径：假设你已知能去的地方是长沙，同时假设最大的描述词是地球，绝对路径就是地球的中国的湖南的长沙。如E:\资料\大物\大物实验。
相对路径：假设你在中国，你想去长沙，相对路径就是湖南的长沙。如大物\大物实验。

前后跳转以及随便翻找就是我认为的文件结构了。

小彩蛋

1. win+R -> 输入taskmgr ->方便清理后台进程，检查恶意弹窗广告，还电脑清净。
2. 在系统变量里的环境变量里添加某个文件夹，之后就可以直接用win+R并输入这个文件夹的相对路径，访问这个文件夹的内容。也就是，如果把快捷方式全部放到一个文件夹里并且为它添加环境变量，就可以用键盘呼出应用和资料，不需要鼠标点点点，也不用把快捷方式放桌面上。

暂时想到这么多，之后再补充。