Definition: Approximate values for the solution of the initial-value problem $y’ = F(x,y)$, $y(x_0) = y_0$, with step size h, at $x_n = x_{n-1} + h$, are $$y_n = y_{n-1} + hF(x_{n-1},y_{n-1}) \text{, } n=1,2,3,…$$
Let’s say $f(0) = a$, $a \in \mathbb{R}$, and h is small number.
So,
$$\begin{aligned}
f(h) &\approx f(0) + h \cdot F(0) \\ f(2h) &\approx f(h) + h \cdot F(h) \\ f(3h) &\approx f(h) + h \cdot F(2h)
\end{aligned}$$
Since this is just an approximation of the derivative, it’s better not to pick a point which is all the way on the left hand side of the interval, instead with the middle value:
$$\begin{aligned}
f(h) &\approx f(0) + h \cdot F(\frac{h}{2}) \\ f(2h) &\approx f(h) + h \cdot F(\frac{3h}{2}) \\ f(3h) &\approx f(h) + h \cdot F(\frac{5h}{2})
\end{aligned}$$
Take another example, why is $\log_{2}{3} \approx 19/12$?
Since $\log_{2}{3} = \frac{\log3}{\log2}$, Let’s separate it, to estimate $\log2$ first.
Set our function $f(x) = \log{x}$, then $\log(1) = 0$, so let’s start with $\log(1)$ with step size: 1/4 :
To solve the equation of the form $f(x) = 0$, so the roots of the equation(方程的根) correspond to the x-intercepts of the graph of $f$. The root that we are trying to find is labeled $r$ in the figure.
We start with a first approximation $x_1$ , which is obtained by guessing,
Consider the tangent line L to the curve $y = f(x)$ at the point $(x_1, f(x_1))$ and look at the x-intercept of L, labeled $x_2$.
The idea behind Newton’s method is that the tangent line is close to the curve and so its x-intercept, $x_2$, is close to the x-intercept of the curve (namely, the root $r$ that we are seeking). Because the tangent is a line, we can easily find its x-intercept.
To find a formula for $x_2$ in terms of $x_1$ we use the fact that the slope of L is $f’(x_1)$, so its equation is:
$y - f(x_1) = f’(x_1)(x - x_1)$
Since the x-intercept of L is $x_2$, we know that point ($x_2, 0$) is on the line, and so:
$0 - f(x_1) = f’(x_1)(x_2 - x_1)$
If $f’(x_1) \ne 0$, we can solve this equation for $x_2$:
$x_2 = x_1 - \frac{f(x_1)}{f’(x_1)}$
Then $x_3 = x_2 - \frac{f(x_2)}{f’(x_2)}$
If we keep repeating this process, we obtain a sequence of approximations $x_1, x_2, x_3, x_4, \dots$ as shown:
In general, if the $n$th approximation is $x_n$ and $f’(x_n) \ne 0$, then the next approximation is given by:
$x_{n+1} = x_n - \frac{f(x_n)}{f’(x_n)}$
If the number $x_n$ become closer and closer to $r$ as $n$ becomes large, then we say that the sequence converges to $r$ and we write $$\lim_{n \to \infty}x_n = r$$
Sometimes The Newton’s method fails:
For example, if we choose $x_2$, then the approximation falls outside the domain of $f$:
Then we need a better initial approximation $x_1$.
