非线性方程求解

非线性方程求解介绍¶

本章讨论单变量情况下的非线性方程求解。根据数值线性代数的知识，我们知道线性方程组往往可以计算出准确解或者最小二乘解，这些结果都是精确且可以直接计算得到的。但现实生活中很多问题实际并不是线性的，往往需要用一个非线性函数去描述。一般情况下，非线性方程很难通过直接计算求解出其精确根，因此在计算数学中我们往往采用迭代法构建一个序列 \(x_1,\cdots,x_n,\cdots\) 不断去逼近真实解 \(x\) 。

我们把问题重新描述一遍，假设我们已知非线性函数 \(f(x)\) ，希望得到 \(f(x) = 0\) 的解 \(x\)，在一般情况下我们无法通过公式直接计算得到该结果（例如高阶多项式就没有求根公式），这时就需要借助数值算法，构建一个序列 \(x_1,\cdots,x_n\) ，使得\(\lim \limits _{n \rightarrow \infty} x_n = x\)，当 \(n\) 取得足够大时，以 \(x_n\) 去代替 \(x\) 也可以满足我们实际的精度需求。

收敛的概念¶

大家在微积分/数学分析中都学过数列收敛的概念，这里再重复说明一遍：

定义(数列收敛)

给定数列 \({x_n} \subset \mathbb{R}\)、 实数 \(x \in \mathbb{R}\)，若对 \(\forall \epsilon > 0, \exists N > 0\) 当 \(n > N\) 时满足：

\[ |x_n - x| < \epsilon, \]

则称 \(x_n\) 收敛到 \(x\)，记为 \(\lim \limits _{n \rightarrow \infty} x_n = x\)。

从计算数学的角度看数列收敛的定义，有以下两个重点：

• 使用一个数值算法的前提是保证其是收敛的，如果在一种情况下数值算法不收敛，则该算法毫无意义。
• 如果把 \(\epsilon\) 视为误差，且算法是收敛的，则从数列定义可以看出无论我们希望达到的误差是多少，只要迭代次数足够多，总能够达到我们的精度要求。

收敛阶的概念¶

既然我们的目标是构建序列 \(x_1,\cdots,x_n\) 去逼近 \(x\) ，那么一个最基本的问题是 \(x_n\) 能多快地逼近 \(x\)，也就是说随着 \(n\) 的增大，误差 \(|x - x_n|\) 下降的速度如何？这一点决定着非线性方程算法的好坏。

对于一个算法而言，常用的下降速度衡量方式是其收敛阶，也就是每迭代一次，误差（从数量级上）是上一次迭代的几次方。

定义(非线性方程收敛阶)

若数列 \(x_n\) 收敛至 \(x \in \mathbb{R}\)，且其满足

\[ \lim \limits _{n \rightarrow \infty} \frac{|x_{n+1} - x|}{|x_n - x|^p} = c > 0 \]

则称 \(x_n\) 收敛到 \(x\) 的收敛阶为 \(p\)。特别地，若 \(p = 1\) 则称为线性收敛，\(p = 2\) 称为二次收敛。

值得注意的是，收敛阶的概念是建立于 \(x_n\) 数列收敛的基本条件上的，如果 \(x_n\) 不收敛，则谈收敛阶其实毫无意义。