形式為 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)
