形式为 f ( x ) = 0 {\displaystyle f(x)=0}
例如，以下方程是代数方程。
2 x = 5 ; x 2 + x = 1 ; x 7 = x ( 1 + 2 x ) . {\displaystyle 2x=5;\quad x^{2}+x=1;\quad x^{7}=x(1+2x).} 而以下方程是超越方程
sin x = 0 ; e x = π ; tan x = x . {\displaystyle \sin x=0;\quad \quad e^{\sqrt {x}}=\pi ;\quad \tan x=x.} 虽然四阶或更低阶的代数方程以及一些特殊的超越方程的根可以被直接找到，但在实践中，我们还需要求解更高阶的方程以及任意超越方程。
由于解析解往往过于繁琐或者根本不存在，我们需要找到一种近似解法。这就是数值分析发挥作用的地方。
一个代数方程可以拥有的根的数量与其次数相同。
一个代数方程最多可以拥有与 f ( x ) {\displaystyle f(x)}
一个代数方程最多可以拥有与 f ( − x ) {\displaystyle f(-x)}
在具有实系数的代数方程中，复数根以共轭对出现。
如果 f ( x ) = a 0 x n + a 1 x n − 1 + a 2 x n − 2 + . . . + a n − 1 x + a n {\displaystyle f(x)=a_{0}x^{n}+a_{1}x^{n-1}+a_{2}x^{n-2}+...+a_{n-1}x+a_{n}} α 1 , α 2 , . . . , α n {\displaystyle \alpha _{1},\alpha _{2},...,\alpha _{n}} ∑ i α i = − a 1 a 0 {\displaystyle \sum _{i}\alpha _{i}={\frac {-a_{1}}{a_{0}}}} ∑ i < j α i α j = a 2 a 0 {\displaystyle \sum _{i<j}{\alpha _{i}\alpha _{j}}={\frac {a_{2}}{a_{0}}}} ∏ i α i = ( − 1 ) n a n a 0 {\displaystyle \prod _{i}\alpha _{i}=(-1)^{n}{\frac {a_{n}}{a_{0}}}}
如果 f ( x ) {\displaystyle f(x)} [ a , b ] {\displaystyle [a,b]} f ( a ) f ( b ) < 0 {\displaystyle f(a)f(b)<0} ( a , b ) {\displaystyle (a,b)} 关于区间最后一点是数值方法用来寻找根的最有用的性质之一。所有数值方法都需要我们对根进行初始猜测。实际上，这很容易通过图形方式完成。只需绘制方程式并对解进行粗略估计。在分析上，我们通常可以在符号发生变化的任何区间内选择任何点。但是，这受制于不同的方法之间不同的特定条件。
求解方程的数值方法是一个漫长的过程。我们想知道该方法是否会产生一个解（接近精确解）或会使我们远离解。如果该方法产生了解，则我们说该方法是收敛的。否则，该方法被称为发散的。例如，在线性和非线性插值的情况下，收敛意味着趋于 0。
各种方法以不同的速度收敛于根。也就是说，某些方法收敛速度慢，需要很长时间才能到达根，而其他方法可以更快地引导我们到达根。这通常是在计算简便性和时间之间的权衡。
但是，对于计算机程序来说，通常最好考虑收敛速度快的算法。收敛速度可以是线性的，也可以是更高阶的。阶数越高，方法收敛越快。
如果 e i {\displaystyle e_{i}} i {\displaystyle i} n {\displaystyle n} e i + 1 e i n {\displaystyle {\frac {e_{i+1}}{e_{i}^{n}}}}
同样重要的是要注意，只有当 e i + 1 < e i {\displaystyle e_{i+1}<e_{i}}
这是一种最简单的方法之一，它强依赖于区间的性质。为了使用该方法找到根，第一步是找到一个区间 [ a , b ] {\displaystyle [a,b]} f ( a ) ⋅ f ( b ) < 0 {\displaystyle f(a)\cdot f(b)<0} ( c , f ( c ) ) {\displaystyle (c,f(c))} a {\displaystyle a} b {\displaystyle b} f ( c ) {\displaystyle f(c)}
求解 e x − 2 x 2 + 3 x + 1 {\displaystyle e^{x}-2x^{2}+3x+1}
f ( x ) = e x − 2 x 2 + 3 x + 1 {\displaystyle f(x)=e^{x}-2x^{2}+3x+1} ⇒ f ( 2 ) ⋅ f ( 3 ) < 0 {\displaystyle \Rightarrow f(2)\cdot f(3)<0} ⇒ ϵ = 1 2 10 − 2 {\displaystyle \Rightarrow \epsilon ={\frac {1}{2}}10^{-2}} ⇒ i = 2.3010 0.3010 = 8 {\displaystyle \Rightarrow i={\frac {2.3010}{0.3010}}=8} ⇒ x 1 = 2.5 {\displaystyle \Rightarrow x_{1}=2.5}
f ( x 1 ) = 5.625 > 0 {\displaystyle f(x_{1})=5.625>0} ⇒ x 2 = 2.25 {\displaystyle \Rightarrow x_{2}=2.25} ⇒ . . . x 8 = 2.09 {\displaystyle \Rightarrow ...x_{8}=2.09}
使用此过程，第 i {\displaystyle i}
ϵ i = | b − a | 2 i {\displaystyle \epsilon _{i}={\frac {|b-a|}{2^{i}}}} ⇒ i ≥ [ log ( b − a ) − log ϵ i ] log 2 {\displaystyle \Rightarrow i\geq {\frac {[\log(b-a)-\log \epsilon _{i}]}{\log 2}}}
每次迭代的间隔减半，我们有 ϵ i + 1 ϵ i = 1 2 {\displaystyle {\frac {\epsilon _{i+1}}{\epsilon _{i}}}={\frac {1}{2}}}
如果我们对 *二分法* 为了收敛到某个容差范围内的根所需要的迭代次数感兴趣，那么我们可以使用最大误差公式。
如果从 *a* = 1 和 *b* = 2 开始，并且容差为 10−4 ，你需要多少次迭代才能得到根？
误差 ϵ i {\displaystyle \epsilon _{i}} −4 。使用最大误差公式
ϵ i = 2 − i ⋅ ( 2 − 1 ) < 10 − 4 {\displaystyle \epsilon _{i}=2^{-i}\cdot (2-1)<10^{-4}} ϵ i = 2 − i < 10 − 4 {\displaystyle \epsilon _{i}=2^{-i}<10^{-4}} 使用对数规则解 *i*
log 10 2 − i < log 10 10 − 4 {\displaystyle \displaystyle \log _{10}{2^{-i}}<\log _{10}{10^{-4}}} − i ⋅ log 10 2 < − 4 {\displaystyle \displaystyle -i\cdot \log _{10}{2}<-4} i > 4 log 10 2 = 13.29 = 14 {\displaystyle \displaystyle i>{\frac {4}{\log _{10}{2}}}=13.29=14} 因此，14 次迭代将确保对根的近似值精确到 10 − 4 {\displaystyle \displaystyle 10^{-4}}
假位置法（有时称为试位法）本质上与二分法相同 - 只是我们没有对间隔进行二分，而是找到了连接两点的弦与 X 轴的交点。根是使用弦的方程计算的，即在 y = 0 {\displaystyle y=0}
y − f ( x 0 ) = f ( x 1 ) − f ( x 0 ) x 1 − x 0 ( x − x 0 ) {\displaystyle y-f(x_{0})={\frac {f(x_{1})-f(x_{0})}{x_{1}-x_{0}}}(x-x_{0})} 收敛速度仍然是线性的，但比二分法更快。如果 *f* 有一个二重根，则这两种方法都会失败。
考虑 *f*(*x*)=*x*2 -1。我们已经知道该方程的根，因此我们可以轻松地检查试位法收敛的速度。
对于我们的初始猜测，我们将使用间隔 [0,2]。
由于 *f* 向上凹且递增，快速绘制几何图形表明，弦将始终与 *x* 轴相交，位于解的左侧。这可以通过一些代数来证实。
我们将调用我们第 *n* 次迭代的间隔 [*a**n* , 2]
弦与 *x* 轴相交时
− ( a n 2 − 1 ) = ( 2 2 − 1 ) − ( a n 2 − 1 ) 2 − a n ( x − a n ) {\displaystyle -(a_{n}^{2}-1)={\frac {(2^{2}-1)-(a_{n}^{2}-1)}{2-a_{n}}}(x-a_{n})} 整理并化简得到
x = 1 + 2 a n 2 + a n {\displaystyle x={\frac {1+2a_{n}}{2+a_{n}}}} 由于这始终小于根，它也是 a n +1
a n e n a n
e n + 1 = 1 + 2 a n 2 + a n − 1 = a n − 1 a n + 2 = 1 a n + 2 e n {\displaystyle e_{n+1}={\frac {1+2a_{n}}{2+a_{n}}}-1={\frac {a_{n}-1}{a_{n}+2}}={\frac {1}{a_{n}+2}}e_{n}} 当 a n e n a n
此方法的收敛阶为 2/3，为线性收敛。
在这种情况下，区间的下限趋近于根，最小误差趋近于零，但上限和最大误差保持不变。这种情况并不少见。
如果我们可以将 f (x )=0 写成 x =g (x ) 的形式，那么点 x 应该是函数 g 的一个不动点 （即，g 的输入也是输出）。然后可以考虑一个明显的序列
x n + 1 = g ( x n ) {\displaystyle x_{n+1}=g(x_{n})\,} 如果我们在图形上查看这一点，我们可以看到它如何收敛到交点。
如果我们定义 x =g (x )，那么任何函数都可以写成这种形式，尽管在某些情况下，其他重排可能更有用（必须满足条件 |g (x )|<1）。这种方法对于找到无限级数的正根也很有用。
不动点定理（陈述 ）
如果 g 在[a,b ] 上是连续的，并且对于 [a,b ] 中的所有 x 都有 a ≤ g(x) ≤ b ，那么 g 在 [a,b ] 中至少有一个不动点。
此外，假设 g'(x) 在 (a,b ) 上是连续的，并且存在一个正常数 c 使得 |g'(x)| ≤ c <1，对于 (a,b ) 中的所有 x 都成立。那么，g 在 [a,b ] 中有一个唯一的不动点 α 。此外，对于 [a,b ] 中的任何 x0 选择，迭代 xn+1 = g(xn ) n≥0 将收敛于 α。
我们将第 n 步的误差定义为
e n = x n − x where x = g ( x ) {\displaystyle e_{n}=x_{n}-x{\mbox{ where }}x=g(x)\,} 然后我们有
e n + 1 = x n + 1 − x = g ( x n ) − x = g ( x + e n ) − x = − x + g ( x ) + e n g ′ ( x ) + ⋯ = e n g ′ ( x ) + ⋯ since g ( x ) = x {\displaystyle {\begin{matrix}e_{n+1}&=&x_{n+1}-x&\\&=&g(x_{n})-x&\\&=&g(x+e_{n})-x&\\&=&-x+g(x)+e_{n}g^{\prime }(x)+\cdots &\\&=&e_{n}g^{\prime }(x)+\cdots &{\mbox{since }}g(x)=x\end{matrix}}} 因此，当 |g ′(x )|<l 时，此序列收敛于根，误差将近似地与 n 成正比。
因为 e n +1e n 线性的 ，如果它收敛，我们就说这种方法线性收敛 。
当 g (x )=f (x )+x 时，这意味着如果
x n + 1 = x n + f ( x n ) {\displaystyle x_{n+1}=x_{n}+f(x_{n})\,} 收敛于 f 的根 x ，那么
− 2 < f ′ ( x ) < 0 {\displaystyle -2<f^{\prime }(x)<0\,} 请注意，这种收敛只在特定范围内的 *x* 值上发生。如果第一个估计值不在该范围内，则不会找到任何解。
另外请注意，虽然这是收敛的必要条件，但它并不能保证收敛。在误差分析中，我们忽略了 *e**n* 的更高次幂，但这只有在 *e**n* 很小的情况下才能做到。如果初始误差很大，即使满足条件，更高次幂也可能会阻止收敛。
如果在根处 |*g*′(*x*)|<1 成立，则迭代序列将在围绕根的某个区间内收敛，该区间可能小于 |*g*′(*x*)|<1 的区间。如果在根处 |*g*′(*x*)| 不小于 1，则迭代不会收敛到该根。
让我们考虑 f ( x ) = x 3 + x − 2 {\displaystyle f(x)=x^{3}+x-2}
最简单的方法是
1): x n + 1 = x n + f ( x n ) = x n 3 + 2 x n − 2 {\displaystyle x_{n+1}=x_{n}+f(x_{n})=x_{n}^{3}+2x_{n}-2}
在这种情况下， g ′ ( x ) = 3 x 2 + 2 {\displaystyle g'(x)=3x^{2}+2}
1 > | g ′ ( x ) | = 3 x 2 + 2 , − 1 > 3 x 2 {\displaystyle 1>|g'(x)|=3x^{2}+2,\qquad -1>3x^{2}} 由于这永远不可能成立，所以它不会收敛到根。
2)另一种重新排列是
x n + 1 = 2 − x n 3 {\displaystyle x_{n+1}=2-x_{n}^{3}} 当以下情况成立时，它会收敛：
1 > | g ′ ( x ) | = | − 3 x 2 | , x 2 < 1 3 , | x | < 1 3 {\displaystyle 1>|g'(x)|=|-3x^{2}|,\qquad x^{2}<{\frac {1}{3}},\qquad |x|<{\frac {1}{\sqrt {3}}}} 由于此范围不包含根，因此此方法也不会收敛。
3)另一种明显的重新排列是
x n + 1 = 2 − x n 3 {\displaystyle x_{n+1}={\sqrt[{3}]{2-x_{n}}}} 在这种情况下，收敛条件变为
1 3 | ( 2 − x n ) − 2 3 | < 1 , ( 2 − x n ) − 2 < 3 3 , | x n − 2 | > 27 {\displaystyle {\frac {1}{3}}\left|(2-x_{n})^{-{\frac {2}{3}}}\right|<1,\qquad \left(2-x_{n}\right)^{-2}<3^{3},\qquad |x_{n}-2|>{\sqrt {27}}} 同样，此区域排除了根。
4)另一个可能性是通过 *x*2 +1 除得到
x n + 1 = 2 x n 2 + 1 {\displaystyle x_{n+1}={\frac {2}{x_{n}^{2}+1}}} 在这种情况下，收敛条件变为
4 | x | ( 1 + x 2 ) 2 < 1 , 4 | x | < ( 1 + x 2 ) 2 {\displaystyle {\frac {4|x|}{(1+x^{2})^{2}}}<1,\qquad 4|x|<(1+x^{2})^{2}} 如果x >1，则该不等式成立，因此，如果我们从这样的x 开始，它将收敛于根。
显然，找到一种收敛的此类方法并不总是直接的。
在数值分析中，牛顿法（也称为牛顿-拉夫森法或牛顿-傅里叶法）是一种用于寻找实值函数的零点（或根）的近似值的有效算法。因此，它是求根算法的一个例子。
任何求零方法（二分法、错位法、牛顿-拉夫森法等）也可以用于找到此类函数的最小值或最大值，方法是找到函数一阶导数中的零点，参见牛顿法作为优化算法。
牛顿-拉夫森法 的思路如下：从一个足够接近真实根的初始猜测开始，然后用函数的切线（可以使用微积分工具计算）近似函数，然后计算该切线的x轴截距（这可以通过初等代数轻松完成）。这个x轴截距通常比原始猜测更接近函数的根，并且该方法可以迭代。假设f : [a, b] → R是定义在区间[a, b]上，取值为实数R的可微函数。收敛于根的公式很容易推导出。假设我们有一些当前近似值xn。然后，我们可以通过参考右侧的图表推导出更好近似值xn+1的公式。我们知道从给定点的导数定义，它是该点切线的斜率。
如果我们了解函数的导数，我们可以获得更好的收敛性。考虑函数的切线
切线用红色表示；函数本身用蓝色表示。 在任何点附近，该点的切线都近似等于f ('x) 本身，因此我们可以使用切线来近似函数。
通过点(x n f (x n
y − f ( x n ) x − x n = f ′ ( x n ) {\displaystyle {\frac {y-f(x_{n})}{x-x_{n}}}=f'(x_{n})} 下一个近似值x n +1y =0的位置。重新排列，我们找到
x n + 1 = x n − f ( x n ) f ′ ( x n ) {\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}} 再次，我们将根定义为x ，第n 步的误差为
e n = x n − x {\displaystyle e_{n}=x_{n}-x\,} 那么下一步的误差是
e n + 1 = e n − f ( x ) + e n f ′ ( x ) + 1 2 e n 2 f ″ ( x ) + ⋯ f ′ ( x ) + e n f ″ ( x ) + ⋯ {\displaystyle e_{n+1}=e_{n}-{\frac {f(x)+e_{n}f'(x)+{\frac {1}{2}}e_{n}^{2}f''(x)+\cdots }{f'(x)+e_{n}f''(x)+\cdots }}} 其中我们将f 写成围绕其根x 的泰勒级数。重新排列它，并使用f (x )=0，我们得到
e n + 1 = e n − e n ( f ′ ( x ) + 1 2 e n f ″ ( x ) ) / f ′ ( x ) + ⋯ = − f ″ ( x ) f ′ ( x ) e n 2 + ⋯ {\displaystyle {\begin{matrix}e_{n+1}&=&e_{n}&-&e_{n}\left(f'(x)+{\frac {1}{2}}e_{n}f''(x)\right)/f'(x)+\cdots \\&=&-{\frac {f''(x)}{f'(x)}}e_{n}^{2}&+&\cdots \end{matrix}}} 我们忽略了误差的三次方和更高次方，因为当误差本身很小时，它们将远小于平方项。
请注意，误差在每一步都被平方。这意味着正确的小数位数在每一步都会翻倍 ，这比线性收敛快得多。
这个序列将在以下情况下收敛
| f ″ ( x ) f ′ ( x ) e n 2 | < | e n | , | e n | < f ′ ( x ) f ″ ( x ) {\displaystyle \left|{\frac {f''(x)}{f'(x)}}e_{n}^{2}\right|<|e_{n}|,\qquad |e_{n}|<{\frac {f'(x)}{f''(x)}}} 如果 *f*′ 在根处不为零，则根周围总是存在一个范围，使该方法收敛。
如果 *f*′ 在根处为零，则再次查看 (1) 我们发现会得到
e n + 1 = e n / 2 {\displaystyle e_{n+1}=e_{n}/2\,} 收敛仅变为线性。
总的来说，这种方法效果很好，前提是 *f* 在其根附近没有最小值，但它只能在导数已知的情况下使用。
让我们考虑 *f*( *x* ) = *x*2 - *a*。在这里，我们确切地知道根，因此我们可以更好地了解该方法收敛的效果。
我们有
x n + 1 = x n − f ( x n ) f ′ ( x n ) = x n − x n 2 − a 2 x n = x n 2 + a 2 x n = 1 2 ( x n + a x n ) {\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}=x_{n}-{\frac {x_{n}^{2}-a}{2x_{n}}}={\frac {x_{n}^{2}+a}{2x_{n}}}={\frac {1}{2}}\left(x_{n}+{\frac {a}{x_{n}}}\right)} 这种方法很容易实现，即使只用笔和纸，并且在牛顿之前很早就被用来快速估计平方根。
*n* 次误差为 *e**n* = *x**n* - √*a*，因此我们有
e n + 1 = ( e n + a ) 2 + a 2 ( a + e n ) − a = 2 a + 2 e n a + e n 2 2 ( a + e n ) − a = 2 ( a + e n ) a + e n 2 2 ( a + e n ) − a = e n 2 2 ( a + e n ) {\displaystyle {\begin{matrix}e_{n+1}&=&{\frac {(e_{n}+{\sqrt {a}})^{2}+a}{2({\sqrt {a}}+e_{n})}}-{\sqrt {a}}\\&=&{\frac {2a+2e_{n}{\sqrt {a}}+e_{n}^{2}}{2({\sqrt {a}}+e_{n})}}-{\sqrt {a}}\\&=&{\frac {2({\sqrt {a}}+e_{n}){\sqrt {a}}+e_{n}^{2}}{2({\sqrt {a}}+e_{n})}}-{\sqrt {a}}\\&=&{\frac {e_{n}^{2}}{2({\sqrt {a}}+e_{n})}}\end{matrix}}} 如果 *a* = 0，这简化为 *e**n* / 2，正如预期的那样。
如果 *a* > 0，*e**n* + 1 将为正，前提是 *e**n* 大于 -√*a*，即前提是 *x**n* 为正。因此，从任何正数开始，除了可能第一个之外的所有误差都将为正。
当以下情况发生时，该方法收敛：
| e n + 1 | = | e n 2 2 ( a + e n ) | < | e n | {\displaystyle |e_{n+1}|=\left|{\frac {e_{n}^{2}}{2({\sqrt {a}}+e_{n})}}\right|<|e_{n}|} 因此，假设 *e**n* 为正，它在以下情况收敛：
e n < 2 ( e n + a ) {\displaystyle e_{n}<2\left(e_{n}+{\sqrt {a}}\right)} 这始终为真。
这种方法从 *任何正数* 开始，以二次方式收敛到平方根。
存在比牛顿-拉夫森收敛速度更快的的方法。例如
x n + 1 = x n − f ( x n ) f ′ ( x n ) + 1 2 f ″ ( x n ) f 2 ( x n ) f ′ 3 ( x n ) {\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}+{\frac {1}{2}}{\frac {f''(x_{n})f^{2}(x_{n})}{{f'}^{3}(x_{n})}}} 该方法具有三次收敛性，每次迭代都能将正确数字的数量增加三倍，比牛顿-拉夫森法快 50%。然而，如果由于公式更复杂，每次迭代需要更长时间（比如慢 50%），那么速度上就没有净收益。因此，很少使用这种方法。奥斯特洛夫斯基的效率指数很好地描述了这种权衡：如果每一步需要 n p n 1/p [ 1]
这里值得一提的是 ITP 方法 ，它是对试位法的改进。它提供了一种保证的（可调的，通常情况下） 2 {\displaystyle {\sqrt {2}}}
主页 - 数学书架 - 数值方法
↑ A. M. Ostrowski，"方程和方程组的解法"，学术出版社，纽约，1960 年。 
![{\displaystyle [a,b]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9c4b788fc5c637e26ee98b45f89a5c08c85f7935)
![{\displaystyle \Rightarrow i\geq {\frac {[\log(b-a)-\log \epsilon _{i}]}{\log 2}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/00217548e8022ab16b3146a85af5fc8c897de172)
![{\displaystyle x_{n+1}={\sqrt[{3}]{2-x_{n}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fefe78901578bc14d8e18655a5603d3e903491a1)
