# Week 10 - Linear Approximation

## 1. What is Linear Approximation

• We call the tangent line is the linear approximation to the function at $x=a$.
• $f(x+h) \approx f(x) + h \cdot f'(x)$

## 2. Euler's Method

• AKA, Repeated Linear Approximation
• 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 :
• So, $\log(1+\frac{1}{4}) \approx \log{1} + \frac{1}{4} \cdot f'(1+\frac{1}{8}) = 0 + \frac{1}{4} \cdot \frac{1}{1+\frac{1}{8}} = \frac{2}{9}$
• PS, instead of using $f'(1)$, we used $f'(1+\frac{1}{8}) = f'(1+\frac{\frac{1}{4}}{2})$, which is more accurate.
• $f'(x) = \frac{1}{x}$
• Then use Euler's Method: $\log(1+\frac{1}{4}+\frac{1}{4}) \approx \log{(1+\frac{1}{4})} + \frac{1}{4} \cdot f'(1+\frac{1}{4}+\frac{1}{8}) = \frac{40}{99}$
• Keep doing this, we got: \begin{aligned}\log(2) &\approx 0.693... \\ \log(3) &\approx 1.098... \\ \frac{\log(3)}{\log(2)} &\approx 1.584962... \end{aligned}
• And $\frac{19}{12} = 1.58\bar{3}$, pretty close.

## 3. Newton's Method

• Also called the Newton-Raphson method
• 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$.

### 3.1. Use Newton's Method to Divide Quickly

• Suppose we want to calculate $\frac{1}{b}$
• Here is one choice: $f(x) = \frac{1}{x} - b$:
• Because $f(\frac{1}{b}) = \frac{1}{\frac{1}{b}} - b = b - b = 0$
• So we can use Newton's Method to find 1/b.
• \begin{aligned} f'(x) &= - \frac{1}{x^2} \\ x_{n+1} &= x_n - \frac{f(x_n)}{f'(x_n)} \\ &= x_n - \frac{\frac{1}{x_n} - b}{-\frac{1}{x_n^2}} \cdot \frac{-x_n^2}{-x_n^2} \\ &= x_n - (-x_n + bx_n^2) \\ &= 2x_n - bx_n^2 \\ &= x_n \cdot (2 - bx_n) \end{aligned}