惟愿言行合一,砥砺前行

0%

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
$$

近似计算中的原则

保留位数原则

加减运算:小数位
  • 计算时:把近似数中小数位数较多的数四舍五入,使其比小数位数最少的数多一位。
  • 计算结果:保留的小数位数与原近似数中小数位数最少者相同。
    乘除运算:有效数字
  • 计算时:因子保留的位数应比有效数字位数最少者的位数多一位。
  • 计算结果:有效数位数与原近似值中有效数字位数最少者至多少一位。
    乘方与开方运算:有效数字
  • 计算结果:有效数字位数与原近似值的有效数字位数相同。
    对数运算:有效数字
  • 计算结果:有效数字位数与其真数(被对数运算的数)的有效数字位数相同。
    中间计算过程
  • 应比上述保留位数原则所提及的位数多取一位,在进行最后一次计算时这一位要舍入。
    原始数据选取
  • 加减运算:小数位应比计算结果要求的多一位。
  • 上述其他运算:有效数字位数应比计算结果要求的多一位。

其他原则

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

    重点应用

    求误差限

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

    算术运算

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

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

计算方法的研究方法

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

误差的来源(需要具备判断误差种类的能力)

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

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

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

Summary_page_1




插值方法

两个插值惟一性

均可用反证法证明。

  • 插值多项式的存在惟一性: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中,以使残差的平方和最小为标准,作近似替代。主要讨论的是多项式拟合。

Summary_page_2




数值积分

基本概念

机械求积

  • 定义:取一个合适的值作为积分区间的平均高度,再乘以积分区间的宽度,得到积分区间的面积。
  • 应用: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系数。

Summary_page_3




常微分方程数值解法

基本概念

  • ☆初值问题:求解$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足够小时,精度越高才能保证局部截断误差越小。

Summary_page_4




方程求根

基本概念

  • 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$不断减半直到满足单调性条件。

重点应用

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

Summary_page_5

参考文章

  • 看完这篇你还不知道这些队列,我这些图白作了
  • 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的对应关系。

    按列序存放(高下标优先)

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

  • 对于Aabc,有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 文件名,可检查文件类型。
  • 拖入文件
  • f5反汇编成c语言伪代码。也可View-open subviews-Generate pseudocode。
  • Alt+T搜索文本。更多搜索选项可见Search栏。
  • 查看变量地址:双击这个变量。

参考文章

  • 非线性,一对多。(定义是递归形式的)

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

  • 森林:m棵互不相交的数的集合,如F={T1,T2,T3},任何一棵非空树可表示为Tree=(root,F),F是子树森林。

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

二叉树

  • 递归定义:根节点,左子树右子树。每个结点的孩子是不会重复的。
  • 每个结点至多两个子树,是有序树。
  • 叶子结点的个数n0=度为2的结点数n2+1。(不直观,需要记)

    总数n=n0+n1+n2,孩子的个数=n-1=2n2+n1

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

    利用n0=n2+1,空链域数=2n0+n1

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

    完全二叉树

  • 每个结点都和同深度的满二叉树中的编号从1至n的结点一一对应。其叶结点只可能出现在层次最大或者第二大的层上。结点数2k-1-1<n<=2k
  • 对于完全二叉树的第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并输入这个文件夹的相对路径,访问这个文件夹的内容。也就是,如果把快捷方式全部放到一个文件夹里并且为它添加环境变量,就可以用键盘呼出应用和资料,不需要鼠标点点点,也不用把快捷方式放桌面上

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

前言

  由于官网修复了左右翻页重新获取数据的bug,原脚本不再适用,需刷新之后重新进才可以实现页面更新。所以要不用下auto.js?(手机)
  auto.js挺简单的,但是拿手机蹲很容易没电而且不能玩手机。同时不知道你们的浏览器刷新键是否叫做刷新,兼容性不一定强。

test.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
var m = require("module.js");
var name = "城市与文化遗产(在线课程)"; //课堂全名
var key = "20202w125011001"; //课堂编号
var number = "189/190"; //期望人数
var type = "历史与文化(原 人文社会科学类)"; //课程类型
var c = desc("刷新").findOne();
while (true) {
if (text("选课系统更新公告").findOne(100)) {
sleep(50);
desc("选课").findOne().click();
sleep(50);
} else if (text("选课提示信息").findOne(100)) {
m.clicktext("下一步");
sleep(50);
} else if (text(key).findOne(100)) {
if (text(number).findOne(100)) {
home();
break;
} else {
sleep(50);
c.click();
sleep(50);
}
} else if (text(name).findOne(100) && text(type).findOne(100)) {
m.clicktext("查看课堂");
sleep(100);
} else if (text("课程名称: ").findOne(100)) {
sleep(50);
input(name);
sleep(50);
m.clicktext("查询");
sleep(100);
}
sleep(100);
}

module.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var m = {};
m.clicktext = (item) => {
while (true) {
var a = text(item).findOne(1000);
if (a) {
a = a.bounds();
if (a) {
var x = a.centerX();
var y = a.centerY();
click(x, y);
break;
}
}
}
}
module.exports = m;

使用方法

  1. 下载Auto.js;
  2. 浏览器调至电脑版;
  3. 复制粘贴成两个文件,test.js,module.js;
  4. 修改test.js的name,key,number;
  5. 运行test.js;
  6. 打开选课页面并登录进入首页,会发现脚本已经开始运行,将页面缩放至最小。

    以下是原博客,已经不太行了

    1. 撰写过程中学到的几点

    一、如何用js绕开页面中的confirm判断。

    这里的页面本身非常简陋,直接把按钮对应的原函数写了出来。
    所以我采用的方法是直接改变按钮的onclick事件,并重写onclick事件对应的函数,覆盖掉,把其中的confirm去掉。非常简单粗暴。
1
2
3
4
var what1=document.getElementsByTagName("input")[10];
what1.onclick =function () {
selectKT(what1.id,nowRenshu,renshu,where.cells[2].innerText,bianhao,xuefen);
};

后话:由于学校网站经久失修,其实只要读取对应的并且填写表单即可,即使用抓包和发包之类的也很容易,根本就不需要用js模拟。

二、修改网页DOM元素,给使用者一点小惊喜

本来页面上想蹲的课的按钮是“选课”,由于改页面元素着实简单,顺手改成“加油”了,自我感觉极好,但是这里有一个需要注意的点。(看代码)

1
2
3
4
5
6
what1.value = '加油';
var btn=document.creatElement("button");
btn.onclick=function(){
what1.value = '加油';
};
btn.onclick();

我这里额外加了一个btn按钮,而不是只修改value值。因为众所周知,这玩意改完之后不会立即重新渲染。(也就是,只写第一行代码是基本没用的)所以添加一个小小的点击事件就能让它立即生效。

三、sleep函数在js中的极有效写法

不瞒您说,这个sleep函数我抄的。但是真的好香,记小本本。

1
2
3
4
5
6
7
8
9
10
function sleep(n) {
var start = new Date().getTime();
// console.log('休眠前:' + start);
while (true) {
if (new Date().getTime() - start > n) {
break;
}
}
// console.log('休眠后:' + new Date().getTime());
}

四、油猴的脚本和朴素的js代码的区别

区别极小,只是它需要加一个头,而且这个头必须加(开头被注释掉的那一大片)。好像不止可以用js,还可以用别的语言,可惜我不会。至于这个头怎么写嘛,这里讲的还不错,随便看一下先入个门就行

五、油猴是啥?咋用?(这个是顺便一提)

这篇文章,往下翻,包安装包会。这篇文章我也发在了csdn上,mooc小助手那篇。

2. 使用说明

清空并复制粘贴以下代码。并阅读下面的说明。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
// ==UserScript==
// @name 华科公选抢课
// @namespace http://tampermonkey.net/
// @version 0.1.3
// @description 抢课前后刷新,并自动选课
// @author shandianchengzi
// @require http://cdn.bootcss.com/jquery/1.8.3/jquery.min.js
// @match http://*/*
// @grant none
// @include http://wsxk.hust.edu.cn/*
// ==/UserScript==
var shuaxin=500;//刷新频率(单位毫秒)
function sleep(n) {
var start = new Date().getTime();
// console.log('休眠前:' + start);
while (true) {
if (new Date().getTime() - start > n) {
break;
}
}
// console.log('休眠后:' + new Date().getTime());
}

function selectKT(ktbh,ktrl,ktrs,kcmc,kcbh,kczxf){
document.getElementById("ktbh").value=ktbh;
document.getElementById("ktrl").value=ktrl;
document.getElementById("ktrs").value=ktrs;
document.getElementById("kcmc1").value=kcmc;
document.getElementById("kczxf").value=kczxf;
document.getElementById("kcbh").value=kcbh;
document.form.submit();
}
(function() {
;

var what = document.getElementsByTagName("table")[0].rows[3];
var what3=what.cells[0].className;
if(what3=="pagebar"){
var where=document.getElementsByTagName("table")[0].rows[2];
var what10=where.cells[9].innerText;
var what2=where.cells[2].innerHTML;
var xuefen=where.cells[4].innerText.split('/')[1];
var bianhao=what2.split('=\'+')[1];
bianhao=bianhao.split(')')[0];
var renshu=what10.split('/')[1];
var nowRenshu=what10.split('/')[0];
var bili=renshu+'/'+renshu;
var noChance=what10.indexOf(bili);

var what1=document.getElementsByTagName("input")[10];
what1.value = '加油';
var btn=document.creatElement("button");
btn.onclick=function(){
what1.value = '加油';
};
btn.onclick();
what1.onclick =function () {
selectKT(what1.id,nowRenshu,renshu,where.cells[2].innerText,bianhao,xuefen);};

if(noChance!= -1)
{
history.go(-1);
}
else {
what1.onclick();
return;}
}
else history.go(1);
sleep(shuaxin);
// Your code here...
})();

使用说明:

  1. 前提:你没有满课。
  2. 来到华中大选课的页面,左上角按课堂选课,然后打开脚本。
  3. 查询你想蹲的课程并回车。
  4. 然后就会自动刷了。过程略鬼畜,如果有人退了就会自动抢。不可以挂后台,请让这个页面一直在窗口上,可以把窗口拉到很小,然后用DeskPins固定不管。

补充说明:
5. 其他的浏览器不清楚,谷歌是可以的。
6. 暂时只支持课程名称查询之后只有一个结果的课,比如华科学子走世界查得到很多课,这个就不支持。
7. 如果觉得刷新频率不满意,把开头的shuaxin改成对应的毫秒数。
8. 放弃刷这一门了就先停止脚本,再打开别的重复1~4步骤。刷到了脚本会自动挂掉,但是也要手动关上,不然可能会继续重复跳页面。

确认过眼神,hexo-admin是我想找的功能,赞呀,在线编辑!

根目录下 复制粘贴以下代码

1
2
3
4
5
npm install --save hexo-admin
echo "hexo clean && hexo g -d">hexo-deploy.bat
echo admin:>>"_config.yml"
echo " deployCommand: 'hexo-deploy.bat'">>"_config.yml"
hexo server -d

然后在浏览器打开localhost:4000/admin/即可编辑博文。
编辑完直接左上角Deploy,跳出一个页面,什么也不用输入,直接点deploy按钮,就可以完成博客的部署。
可能遇到的问题:如果每次都要输入密码,就查看一下你的_config.yml,里面的deploy的repo从http网址改为git@github类型。

以下是代码解释

第一行,下载插件,
第二行,生成一个内容为”hexo clean && hexo g -d”,名为”hexo-deploy”的bat文件,
第三、四行,配置_config.yml文件,
第五行,开启hexo服务。

用admin插入图片

复制图片,粘贴到编辑页面。出现大概这样的东西:
![upload successful](\\images\pasted-2.png\)
,然后改成:
![upload successful](/images/pasted-2.png)。就出图片了。
upload successful