牛顿迭代法与GNSS

2024-06-09 02:17| 来源: 网络整理| 查看: 265

牛顿迭代（Newton's method），也称为牛顿-拉夫逊方法（Newton-Raphson method），是一种用于寻找实数或复数方程的根（或称零点）的迭代数值解法，也是用于求解非线性方程和非线性方程组得常用方法。这个方法是基于牛顿的插值公式和不动点迭代的思想。简单来说是通过不断改进猜测值，逼近方程的根。其迭代思路如下[1]：

为了简单起见，先从一元非线性方程的求解开始讲起。假设我们需要求解以下一个非线性方程式的根 x : f(x) = 0 （式1）

式中 f(x) 是一个关于未知数 x 的非线性函数。给定一个根的估计值 $x_{n-1}$ ,如果 f(x)在点 $x_{n-1}$ 附近连续且可导，那么 f(x) 在点 $x_{n-1}$ 处的泰勒展开式为：（这里参考线性化-泰勒公式）

$f(x) = f(x_{n-1})+{f}'(x_{n-1})(x-x_{n-1})$ （式2）

上式只保留了泰勒展开式中的一阶余项，忽略了其他各个高阶余项，而 ${f}'(x_{n-1})$ 代表 $f(x)$ 的一阶导数在 $x_{n-1}$ 处的值，即

这样，非线性方程式1就近似地转化为以下一个线性方程式：

如果一阶导数值 ${f}'(x_{n-1})$ 不等于0，那么求解上述线性方程式就相当简单，将式3进行变换得：

牛顿迭代法是将线性方程式3 的解 x 作为原非线性方程式1 的根的更新值 $x_{n}$ ，即式4所示。有了更新后的解 $x_{n}$ ，方程式1 就又可以在点 $x_{n}$ 处线性化，然后重复上述计算，得到再次更新后的解 $x_{n+1}$ 。我们一般可以通过检查 $x_{n+1}$ 与 $x_{n}$ 之间的差异量幅值大小来判定是否可以结束循环迭代计算：如果 $\left | x_{k+1}-x_{k} \right |$ 的值小于一个预先设定的精度门限值，那么我们认定解 $x_{n+1}$ 已经达到所要求的精度，它就是非线性方程式1 的数值解；否则，继续进行下一次迭代计算。这一循环迭代求解过程就是牛顿迭代法，其迭代计算的收敛速度与函数 $f(x)$ 的特点有关。这里给出其他博主对于牛顿迭代法的讲解，可以互相参考理解。牛顿迭代法（Newton’s Method）迭代求根的Python程序

机器学习-牛顿迭代法原理和公式推导

举例1：（通过设置迭代次数求解）

假设要解方程 $f(x)=3x^{2}-5$ ,使用牛顿迭代来逼近其根。

解决：

step1：首先给出初始猜测值 $x_{0}$ = 3

step2：设置迭代次数为5（为了更好地展示，我将迭代次数设置为5。在实际应用中，可能需要更多的迭代次数以达到所需的精度。）

step3：进行第一次求解，

step4：在 $x_{1}$ 处泰勒展开，再次求解

step5：依次进行迭代......

matlab求解代码如下：

% 牛顿迭代法求解方程 f(x) = 3x^2 - 5 % 定义方程及其导数 f = @(x) 3*x.^2 - 5; df = @(x) 6*x ; x0 = 3; % 设置初始猜测值 max_iterations = 5; % 设定迭代次数 % 初始化图形 figure; x_range = linspace(-4, 4, 200); y = f(x_range); tangent_line = f(x0) + df(x0) * (x_range - x0); %计算各点切线 hold on; plot(x_range, f(x_range), 'o-', 'MarkerSize',1.5, 'MarkerFaceColor', 'b'); plot(x_range, tangent_line, 'LineWidth', 1); grid on; line([0, 0], ylim, 'Color', 'k', 'LineWidth', 0.5); % 在 x=0 处添加水平黑线 line(xlim, [0, 0], 'Color', 'k', 'LineWidth', 0.5); % 在 y=0 处添加水平黑线 xlabel('x轴'); ylabel('y轴'); legend('f(x)函数', '初始x0点切线'); % 添加图例 line([x0, x0], [f(x0),0 ], 'Color', 'k', 'LineWidth', 1,'Color', 'r');% 在某一点到 y=0 处添加黑线,即垂线 % 迭代过程 for n = 1:max_iterations % 牛顿迭代公式 x1 = x0 - f(x0) / df(x0); % 计算函数值和导数值 y = f(x_range); tangent_line1 = f(x0) + df(x0) * (x_range - x0); %初始值切线 tangent_line2 = f(x1) + df(x1) * (x_range - x1); %更新值切线 plotCustom(x_range,f(x_range),x_range,tangent_line1,x_range,tangent_line2,x0,f(x0),x1,f(x1)); % 更新猜测值 x0 = x1; end %输出迭代后结果 fprintf('第%d次迭代后,函数f(x)=3x^2 - 5的近似根是 %f,f(x)在该根处的值为%.16f\n', max_iterations,x0,f(x0)); % 定义绘图函数 function plotCustom(x1, y1, x2, y2,x3,y3,x_0,y_0,x_1,y_1) % 绘制图形 figure; hold on; % 循环绘制每组数据 plot(x1, y1, 'o-', 'MarkerSize',1.5, 'MarkerFaceColor', 'b');%绘制原函数 plot(x2, y2, 'LineWidth', 1);%绘制x0处切线 plot(x3, y3, 'LineWidth', 1);%绘制更新的x0处切线 % 添加轴标签 xlabel('X轴'); ylabel('Y轴'); line([0, 0], ylim, 'Color', 'k', 'LineWidth', 0.5); % 在 x=0 处添加水平黑线 line(xlim, [0, 0], 'Color', 'k', 'LineWidth', 0.5); % 在 y=0 处添加水平黑线 line([x_0, x_0], [y_0,0 ], 'Color', 'k', 'LineWidth', 1,'Color', 'r');% 在某一点到 y=0 处添加黑线,即垂线 line([x_1, x_1], [y_1,0 ], 'Color', 'k', 'LineWidth', 1,'Color', 'r');% 在某一点到 y=0 处添加黑线,即垂线 legend('f(x)函数', '初始x0点切线','迭代更新点切线'); % 添加图例 grid on;% 显示网格 hold off; % 结束保持图形 end

当初始值 $x_{0}$ 为3时，对应的切线如下图所示。

第一次牛顿迭代后结果与初始值对比如下：

第二次牛顿迭代后结果与第一次迭代结果对比如下，可以看到已经非常接近于该函数根的真实值。

第三次牛顿迭代后的结果与真实值已经非常接近。

当迭代3、4、5次的最终输出结果为：

举例2：（通过迭代步长即 $\left | x_{k+1}-x_{k} \right |$ 与阈值比较来判定迭代终止）

假设要解方程 $f(x)=e^{x}-7$ ,使用牛顿迭代来逼近其根。

解决：（同样进行以下步骤）

step1：首先给出初始猜测值 $x_{0}$ = 3

step2：设置阈值tolerance为 $1* 10^{-6}$

step3：进行第一次求解，

step4：在 $x_{1}$ 处泰勒展开，再次求解

step5：依次进行迭代......

matlab求解代码如下：

% 牛顿迭代法求解方程 f(x) = e^x - 7，以步长作为终止准则 % 定义方程及其导数 f = @(x) exp(x) - 7; df = @(x) exp(x); x0 = 3; % 初始猜测值 max_iterations = 100; % 设定最大迭代次数，防止无限循环 tolerance = 1e-8; % 设定阈值 % 初始化图形 figure; x_range = linspace(-1, 5, 200); y = f(x_range); tangent_line = f(x0) + df(x0) * (x_range - x0); %计算初始点切线 hold on; plot(x_range,y, 'o-', 'MarkerSize',1.5, 'MarkerFaceColor', 'b'); plot(x_range,tangent_line, 'LineWidth', 1); grid on; line([0, 0], ylim, 'Color', 'k', 'LineWidth', 0.5); % 在 x=0 处添加水平黑线 line(xlim, [0, 0], 'Color', 'k', 'LineWidth', 0.5); % 在 y=0 处添加水平黑线 xlabel('x轴'); ylabel('y轴'); legend('f(x)函数', '初始x0点切线'); % 添加图例 line([x0, x0], [f(x0),0 ], 'Color', 'k', 'LineWidth', 1,'Color', 'r');% 在某一点到 y=0 处添加黑线,即垂线 for n = 1:max_iterations x1 = x0 - f(x0) / df(x0); %牛顿迭代公式 % 计算函数值和导数值 y = f(x_range); tangent_line1 = f(x0) + df(x0) * (x_range - x0); %初始值切线 tangent_line2 = f(x1) + df(x1) * (x_range - x1); %更新值切线 plotCustom(x_range,f(x_range),x_range,tangent_line1,x_range,tangent_line2,x0,f(x0),x1,f(x1),n); % 检查停止准则 if abs(x1 - x0) < tolerance break; end x0 = x1; end %输出迭代后结果 fprintf('第%d次迭代后,函数f(x)=e^x - 7的近似根是 %f,f(x)在该根处的值为%.16f\n', n,x0,f(x0)); % 定义绘图函数 function plotCustom(x1, y1, x2, y2,x3,y3,x_0,y_0,x_1,y_1,n) % 绘制图形 figure; hold on; % 循环绘制每组数据 plot(x1, y1, 'o-', 'MarkerSize',1.5, 'MarkerFaceColor', 'b');%绘制原函数 plot(x2, y2, 'LineWidth', 1);%绘制x0处切线 plot(x3, y3, 'LineWidth', 1);%绘制更新的x0处切线 % 添加轴标签 xlabel('X轴'); ylabel('Y轴'); title(sprintf('第 %d 次迭代', n)); line([0, 0], ylim, 'Color', 'k', 'LineWidth', 0.5); % 在 x=0 处添加水平黑线 line(xlim, [0, 0], 'Color', 'k', 'LineWidth', 0.5); % 在 y=0 处添加水平黑线 line([x_0, x_0], [y_0,0 ], 'Color', 'k', 'LineWidth', 1,'Color', 'r');% 在某一点到 y=0 处添加黑线,即垂线 line([x_1, x_1], [y_1,0 ], 'Color', 'k', 'LineWidth', 1,'Color', 'r');% 在某一点到 y=0 处添加黑线,即垂线 legend('f(x)函数', '初始x0点切线','迭代更新点切线'); % 添加图例 grid on;% 显示网格 hold off; % 结束保持图形 end

可以看到，其实在第二次迭代之后就已经接近于实际值了，根据设定的阈值，最终的结果为：

牛顿迭代法求解多元非线性方程组：

其求解过程与以上求解一元非线性方程的过程完全相同，即给出方程组解的初始估计值，将各个非线性方程在此估计值处线性化，然后求解线性化后的方程组而得到原非线性方程组解的更新值，接着重复这种运算，直到满足所要求的精度为止。

例如，某系统有一个输入量 u 和一个输出量 v ，他们之间的关系可以用以下一个非线性函数来描述：

$v=f(x,y,z,u)$ 式5

式中，x、y、z为三个值待定的函数系数。为了确定这三个系数的值，我们对该系统进行了多次测定：当系统输入为 $u_{1}$ 时系统输出为 $v_{1}$ ，当输入为 $u_{2}$ 时输出为 $v_{2}$ ，等等。假设我们一共测定了N对数据，那么这些数据对集中在一起就可以组成以下的N个方程式：

$\left\{\begin{matrix} v_{1}=f(x,y,z,u_{1}) & & \\ v_{2}=f(x,y,z,u_{2}) & & \\ \vdots & & \\v_{N}=f(x,y,z,u_{N}) \end{matrix}\right.$ 式6

它是一个三元非线性方程组。在用牛顿迭代算法求解方程组式6的三个未知系数x、y、z的第 k 次迭代中，假设解（x、y、z）的初始值为（ $x_{k-1}$ ， $y_{k-1}$ ， $z_{k-1}$ ），那么式6 中的每一个方程式可在该点（ $x_{k-1}$ ， $y_{k-1}$ ， $z_{k-1}$ ）处线性化。以方程组中的第n个方程为例，该方程组的泰勒展开式为：

G通常称为雅可比矩阵，把方程组表达成矩阵形式，不但写起来简洁、方便，而且有助于我们运用成熟的矩阵理论知识来分析方程组的特性和求解方程组。当求得 $\bigtriangleup x$ 后，非线性方程组式6 的解就可以从 $x_{k-1}$ 更新到 $x_{k}$ ,即

$x_{k}=x_{k-1}+\bigtriangleup x$

若更新后的解 $x_{k}$ 尚未达到求解精度，则 $x_{k}$ 可作为第 k+1 次迭代的起始点，继续进行上述牛顿迭代运算。

牛顿迭代法与GNSS：（这里先简单介绍，后续会在单点定位里结合代码详细讲解）

线性化-泰勒公式-GNSS-CSDN博客在这篇文章后面我写出，经过泰勒展开线性化后，后续所求结果变为概略位置与实际值的偏差，即dx、dy、dz，那么在单点定位中的迭代过程如下：

[1]全球导航卫星系统原理——GPS、格洛纳斯和伽利略系统，谢钢著

【本文地址】

公司简介

联系我们