Bisection and Newton root finding
引入| English | 释义 | 拼音 |
|---|---|---|
| Newton–Raphson method/ˈnjuːtn ˈræfsn ˈmeθəd/ | 牛顿–拉弗森法 | niú dùn – lā fú sēn fǎ |
| interval bisection/ˈɪntəvl baɪˈsekʃn/ | 区间二分法 | qū jiān èr fēn fǎ |
| linear interpolation/ˈlɪnɪə ɪnˌtɜːpəˈleɪʃn/ | 线性插值 | xiàn xìng chā zhí |
| continuous/kənˈtɪnjuːəs/ | 连续的 | lián xù de |
| tangent/ˈtændʒənt/ | 切线 | qiē xiàn |
Raphson's improving guess, 1690
- In 1690, Joseph Raphson, a Fellow of the Royal Society in London, published Analysis Aequationum Universalis, a method that turns one guess at a root into a much better one. Isaac Newton had used a similar idea, so we call it the Newton–Raphson method 牛顿–拉弗森法.
- FP1 has three numerical methods for roots: interval bisection 区间二分法, linear interpolation 线性插值 and Newton–Raphson. All begin with a sign change.
Bracketing a root
- If $f$ is continuous 连续的 on $[a, b]$ and $f(a)$, $f(b)$ have opposite signs, then a root lies in $(a, b)$.
- $f(x) = x^3 + 2x - 5$: $f(1) = -2$ and $f(2) = 7$, so a root lies in $(1, 2)$.
$f(x) = x^3 - 4x + 1$ has a root in $(0, 1)$.
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
$f(0) = 1 > 0$ and $f(1) = -2 < 0$, and $f$ is continuous.
Bisection and interpolation
- Bisection tests the midpoint and keeps the half with a sign change: $f(1.5) = 1.375 > 0$, so the root is in $(1, 1.5)$; $f(1.25) = -0.547 < 0$, so it is in $(1.25, 1.5)$.
- Interpolation draws a straight line from $(a, f(a))$ to $(b, f(b))$. By similar triangles, $\dfrac{x - 1}{2} = \dfrac{2 - x}{7}$ for the points $(1, -2)$ and $(2, 7)$, so $x = 1 + \dfrac{2}{9} = 1.222$.
Bisection and Newton root finding
For a continuous function with a sign change, bisect a root bracket and keep the half with opposite endpoint signs
Compare the model with the worked case and explain one change.
支持 $f(x) = x^3 - 4x + 1$ on $(0, 1)$: $f(0.5) = -0.875$. Which interval holds the root now?
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
The sign change is between $f(0) = 1$ and $f(0.5) = -0.875$.
Use linear interpolation on $(0, 1)$ for $f(x) = x^3 - 4x + 1$ to estimate the root, to 3 d.p.
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
The line from $(0, 1)$ 到 $(1, -2)$ crosses at $x = \tfrac{1}{3}$.
Worked example: Newton–Raphson
Use $x_{n+1} = x_n - \dfrac{f(x_n)}{f'(x_n)}$ with $x_0 = 1.5$ for $f(x) = x^3 + 2x - 5$, then show the root is $1.328$ to 3 d.p.
- Derivative: $f'(x) = 3x^2 + 2$, so $f'(1.5) = 8.75$ and $x_1 = 1.5 - \dfrac{1.375}{8.75} = 1.3429$.
- Repeat: $x_2 = 1.3284$, $x_3 = 1.3283$.
- Proof: $f(1.3275) = -0.0056 < 0$ and $f(1.3285) = 0.0017 > 0$. A sign change of a continuous function, so the root is $1.328$ to 3 d.p.
Use one step of Newton–Raphson on $f(x) = x^2 - 7$ from $x_0 = 3$, to 4 d.p.
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
$3 - \dfrac{2}{6} = 2.6667$; $\sqrt{7} = 2.6458$.
Why Newton–Raphson is fast
- Each step follows the tangent 切线 at $x_n$ down to the $x$-axis; near the root the tangent is almost the curve.
- The number of correct decimal places roughly doubles each step: from $1.5$ to $1.343$, $1.3284$, $1.32827$.
When the methods fail
- Bisection and interpolation need a sign change: $f(x) = (x - 2)^2$ touches the axis at 2 but never changes sign.
- Newton–Raphson fails if $f'(x_n) = 0$ (a horizontal tangent), and can jump to a different root if $x_0$ is near a turning point.
支持 $f(x) = x^3 - 3x + 1$, why is $x_0 = 1$ a bad start for Newton–Raphson?
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
$f'(x) = 3x^2 - 3 = 0$ at $x = 1$: a turning point, and the formula divides by zero.
Bisection can find the root of $f(x) = (x - 2)^2$.
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
The curve touches the axis without crossing, so there is no sign change to bracket.
Proving a root with a sign change across an asymptote. $f(x) = \dfrac{1}{x - 1}$ has $f(0) = -1$ and $f(2) = 1$, but no root — it is not continuous at $x = 1$. Always state that the function is continuous on the interval.
Bracket a root with a sign change of a continuous function. Bisection halves the bracket, interpolation uses a straight line between the end points, and Newton–Raphson $x_{n+1} = x_n - \tfrac{f(x_n)}{f'(x_n)}$ follows the tangent and converges fast — unless $f'(x_n) = 0$ or the start is poor.
Show that $f(x) = x^3 + 2x - 5$ has a root in $(1, 2)$. Apply Newton–Raphson from $x_0 = 1$ twice, giving each value to 4 d.p.
Bracket, then refine.