数值分析总结

type

status

date

slug

summary

函数零点

二分法

首先我们要确定一个区间，其中在该区间上是连续且单调的，且满足条件

然后计算

如果则令

否则令

跳转至步骤2直到满足精度条件

牛顿法

对于，我们首先求解其导数

然后选取一个合适的初始值

然后根据递推公式计算出下一个值

反复求解直到满足精度条件

对于牛顿法，如果一开始选取的初始值不合理，可能会导致在递推的过程中，的值不收敛，因此选取合适的初始值显得特别重要。

牛顿下山法

相比于牛顿法，牛顿下山法带入了一个下山因子，具体过程如下：

对于，求解其导数

选取一个任意的初始值

对于每一个和，其递推公式为，首先令，然后对逐次取半直到满足条件

牛顿下山法将牛顿法和下山法结合，保证了函数值稳定下降的前提，又用牛顿法加快了收敛速度。

弦截法

弦截法的递推公式为，其中弦截法需要确定2个初始值和，然后分别带入递推公式进行求解，直到满足精度条件。

代码

方程组求解

列主元高斯消去法

将线性方程组的系数矩阵通过行初等变换变成上三角矩阵，可以证明变换后的线性方程组与原方程组等价，通过回带求解变换后的方程组。该消去法有效的条件是主元全不为零。因此，在进行第步消元的时候要寻找合适的主元。具体算法如下：

LU分解

对矩阵进行一次初等变换，相当于用相应的初等矩阵去左乘原来的矩阵，使用这种思路将Gauss消元用矩阵乘法来表示，即可求得线性方程组的另一种直接解法，即矩阵的三角分解。

Doolittle分解

我们将矩阵进行如下分解：

即可将线性方程组的求解过程进行如下转换：

那么问题就转换成了，如何求解矩阵和，最终的通项公式如下：

然后通过求解，通过和求解线性方程组的解

上面两种都是线性方程组的直接解法，直接解法的通用性高，由于其时间复杂度都比较大，为，因此只适合求解阶数较低的方程组，对于高阶的稀疏矩阵，往往采用迭代法。

Cholesky分解

若矩阵是正定矩阵，则可以进行如下分解：

然后分别求解和：

迭代法

对于线性方程组，我们采用类似不动点迭代法来构造（其中与原方程等价）考虑到迭代的计算量，通常我们会选取简单的线性函数，如：，其中为常矩阵。将初始的解向量带入方程，求出来逼近准确值。

对于方程，任意初始向量，只有当，该迭代才是收敛的，其中表示矩阵所有特征值中的最大绝对值，这在我们后续的求解过程中十分重要，如果方程不收敛，迭代是毫无意义的。

设系数矩阵

令，，

Jacobi迭代法

递推公式：

对于雅克比迭代法，，对其求解谱半径即可判断是否收敛。

雅克比实现较为简单，但是收敛速度较慢。

Gauss Seidel迭代法

递推公式：

和Jacobi相比，Gauss Seidel迭代法不需要保留上一次迭代的解

SOR迭代法

递推公式：

SOR算法实在Gauss-Seidel算法的基础上带入了一个参数所得到的，收敛的速度受因子的影响，因此的选取十分重要。

共轭梯度法

设是对称正定的，则对方程组的求解等价于求解元二次函数的极小值。

最速下降法：假设当前位置为，则下降最快的方向是其梯度方向：，沿最速下降方向搜索，则，为步长应该使得最小，则。

在最速下降法中，虽然每步都能找到局部最优解，但是整体效率低，因此迭代收敛速度较慢。因此引入了共轭梯度法（Conjugate Gradient Method）。

假设当前点，下降的最速方向是，其前一个搜索方向是，则我们在过，由上述两个方向张成的平面上找函数的最小值，即有：

算法流程如下：

共轭梯度法的收敛速度极快，理论上步以内就能收敛，但是考虑到求解的精度，实际上会略大于，且随着迭代次数的增加，舍入误差会很严重，且对于病态矩阵，收敛很慢甚至不收敛。

代码

拟合

实验目的

使用最小二乘法来对离散点进行拟合，并将拟合的结果与拉格朗日及牛顿插值所得的结果进行比较

求下列离散点的三次拟合：

x	0	0.1	0.2	0.3	0.5	0.6	1.0
f(x)	1.0	0.41	0.50	0.61	0.91	2.02	2.46

区间上函数，考虑等距划分，分点为，不断增大分点数目，计算时的值

最佳平方逼近法

设，线性无关，令，求，使得：

即称为在中的最佳平方逼近函数：

对于任意，设，求解等价于求下列多元函数的最小值点

这就变成了一个求解线性方程组的问题：

最小二乘法

在现实中我们无法获取原函数的值，只能靠离散的点去近似拟合原函数，假设我们现在有$m$个离散点，我们需要拟合出一个函数，使得尽可能的小。

我们通常使用来进行求解。

其实最小二乘法实质上是最佳平方问题的离散形式，现在我们已知函数值表，需要在函数空间中求解，使得：

其中，等价于求多元函数的最小值：

其中

若定点集以及各点的权系数，如果函数族满足：

则称关于点集带权正交，若满足这一条件，则可以使用如下递推公式：

该方法非常适合编程实现，只用递推公式，并且当逼近次数增加时，只要将相应地增加程序中的循环次数即可。

代码

插值

实验目的

分别使用Lagrange法和Newton法来实现插值，并比较两种方法的插值结果

根据下表进行插值，分别计算的值：

x	0.2	0.4	0.6	0.8	1.0
f(x)	0.98	0.92	0.81	0.64	0.38

区间上函数，考虑等距划分，分点为，不断增大分点数目，分析比较原函数和差值多项式的结果

Lagrange法

拉格朗日插值法（Lagrange Method）简单方便，只需要取定节点就可以写出基函数，进而得到插值多项式，易于计算机实现，其表达式为：

但是倘若要添加新节点时，全部基函数都需要重新计算，很不方便。

Newton法

当使用牛顿插值法（Newton Method）新增加节点时，牛顿插值法只需要在原来的基础上增加一项，之前的计算结果仍然可以使用，与拉格朗日插值相比，具有灵活增加节点的优点，其表达式如下：

对于牛顿法，关键点在于如何求解，我们将该值定义为差商，其定义如下：

上述差商的求解需要用递归求解，对上述递归式求解后可以得到更直接的式子如下：

代码

积分

实验目的

分别使用Simpson法，符合Simpson法和变步长Simpson法求解积分

使用复合Simpson法时，取

使用变步长Simpson法时，误差小于

Simpson法

复合Simpson法

其中，

变步长Simpson法

输入

计算

计算

如果，则停止

否则return 3